《基于孤立因子的层次聚类算法与应用 ——随机抽样与图像压缩-毕业论文》由会员分享，可在线阅读，更多相关《基于孤立因子的层次聚类算法与应用 ——随机抽样与图像压缩-毕业论文（24页珍藏版）》请在金锄头文库上搜索。
1、本科毕业论文(科研训练、毕业设计)题 目：基于孤立因子的层次聚类算法与应用随机抽样与图像压缩姓 名：学 院：软件学院系：专 业：软件工程年 级：学 号：指导教师（校内）： 职称： 指导教师（校内）： 职称： 年 月 日基于孤立因子的层次聚类算法与应用随机抽样与图像压缩第 2 页 共 25 页基于孤立因子的层次聚类算法与应用基于孤立因子的层次聚类算法与应用A A ClusteringClustering AlgorithmAlgorithm BasedBased onon Outlier-handlingOutlier-handling FactorFactor andand itsits Ap
2、plicationsApplications 摘要摘要 数据挖掘是数据库系统和新的数据库应用的一个有希望的、欣欣向荣的学科前沿。作为一个数据挖掘的功能，聚类分析能作为一个独立的工具来获得数据分布的情况，观察每 个簇的特点，集中对特定的某些簇做进一步的分析。此外，聚类分析可以作为其他算法的预 处理步骤，这些算法再在生成的簇上进行处理。由于数据库中收集了大量的数据，聚类分析 已经成为数据挖掘研究领域中一个非常活跃的研究课题。 本文在分析 BIRCH 算法与 CLAP 算法的优缺点基础上，结合孤立点挖掘算法，提出一 种基于孤立点预测的层次聚类算法，并且用 Visual C+实现了 CLOF 算法系统
3、。系统包含 了输入/输出、数据预处理、CLOF 算法核心和图像还原预处理四个模块。CLOF 算法首先 采用随机抽样，通过初步聚类的结果定义子聚类和数据项的孤立因子，并采用全局因子和局 部因子定义相结合，改进了孤立点的去除和吸收算法，提高了聚类的质量，降低了对数据输 入顺序的敏感性，增强了对噪声数据处理的稳健性，并在大型数据库聚类、图像压缩和图像 分割等方面进一步得到验证。 关键词关键词 聚类 BIRCH 算法 CLAP 算法 图像压缩A Clustering Algorithm Based on Outlier-handling Factor and its ApplicationsAbstr
4、actAbstract：Data mining is a promising and flourishing frontier in database systems and new database applications. As a data mining function, cluster analysis can be used as a stand-alone tool to gain insight into the distribution of data, to observe the characteristics of each cluster, and to focus
5、 on a particular set of clusters for further analysis. Alternatively, it may serve as a preprocessing step for other algorithms, such as characterization and classification, which would then operate on the detected clusters. Owing to the huge amounts of data collected in databases, cluster analysis
6、has recently become a highly active topic in data mining research.In this paper, we propose a new hierarchical clustering algorithm to improve the performance of the BIRCH algorithm and CLAP algorithm, furthermore, we achieve the system of CLOF algorithm using Visual C+. The system contains four mod
7、ules: input/output, data preprocess, the kernel of CLOF algorithm, the preprocess of image revivification. Keyword： ClusteringBIRCHCLAP K-means基于孤立因子的层次聚类算法与应用随机抽样与图像压缩第 4 页 共 25 页目目 录录第一章 引言.5第二章 CLOF 算法系统设计需求分析72.1 引言72.1.1 编写目的72.1.2 项目背景72.2 任务概述92.2.1 目标92.3 数据描述92.3.1 静态数据92.3.2 动态数据102.4 功能需求
8、102.4.1 流程图102.4.3 数据与功能的对应关系112.5 性能需求112.5.1 时间要求112.5.2 适应性122.6 运行环境描述122.6.1 硬件设备122.6.2 支持软件12第三章随机抽样与图像压缩.133.1 数据库的输入输出143.1.1 目的.143.1.3 处理流程163.2 图像处理.163.2.1 目的163.2.2 图片背景知识163.2.2.1BMP 文件组成163.2.3 图片处理类183.2.4 重构图片方法思想183.2.5 处理图像实例193.2.6 程序输入输出接口与实例20第四章 CLOF 算法系统测试结果.21第五章 结论.23致谢语.2
9、3参考文献.25基于孤立因子的层次聚类算法与应用随机抽样与图像压缩第 5 页 共 25 页第一章第一章 引言引言本文在分析 BIRCH1算法与 CLAP4算法的优缺点基础上，结合孤立点挖掘算法，提 出一种基于孤立点预测的层次聚类算法，并且用 Visual C+实现了 CLOF 算法系统。系统 包含了输入/输出、数据预处理、CLOF 算法核心和图像还原预处理四个模块。数据挖掘（Data Mining）就是从大量的、不完全的、有噪声的、模糊的、随机的数据 中，提取隐含在其中的，人们事先不知道的、但又是潜在的有用信息和知识的过程。它是 一门涉及面很广的交叉学科，包括机器学习、数理统计、神经网络、数据
10、库、模式识别、 粗糙集、模糊数学等相关技术。由于数据挖掘是一门受到来自各种不同领域的研究者关注的交叉性学科，因此导致了 很多不同的术语名称。其中，最常用的术语是“知识发现“和“数据挖掘“。相对来讲，数据 挖掘主要流行于统计界（最早出现于统计文献中）、数据分析、数据库和管理信息系统界； 而知识发现则主要流行于人工智能和机器学习界。数据挖掘可粗略地理解为三部曲：数据准备（Data Preparation）、数据挖掘，以及 结果的解释评估（Interpretation and Evaluation）。 根据数据挖掘的任务分类有如下几种：分类或预测模型数据挖掘、数据总结、数据聚 类、关联规则发现、序列
11、模式发现、依赖关系或依赖模型发现、异常和趋势发现等等。根据数据挖掘的对象分类有如下若干种数据源：关系数据库、面向对象数据库、空间 数据库、时态数据库、文本数据源、多媒体数据、异质数据库、遗产（Legacy）数据库， 以及 Web 数据源。根据数据挖掘的方法可粗分为：统计方法、机器学习方法、神经网络方法和数据库方 法。统计方法中，可细分为：回归分析（多元回归、自回归等）、判别分析（贝叶斯判别、 费歇尔判别、非参数判别等）、聚类分析（系统聚类、动态聚类等）、探索性分析（主元 分析法、相关分析法等）、以及模糊集、粗糙集、支持向量机等。机器学习中，可细分为： 归纳学习方法（决策树、规则归纳等）、基于范
12、例的推理 CBR、遗传算法、贝叶斯信念网 络等。神经网络方法，可细分为：前向神经网络（BP 算法等）、自组织神经网络（自组织 特征映射、竞争学习等）等。数据库方法主要是基于可视化的多维数据分析或 OLAP 方法， 另外还有面向属性的归纳方法。聚类（Clustering）就是将物理或抽象对象的集合分组成为由类似的对象组成的多个类 的过程。聚类分析源于许多研究领域，包括数据挖掘统计学、生物学、以及机器学习。聚类 分析是以相似性为基础，把一组个体划分成若干个具有一定意义的子类,即“物以类聚” ，其 目的是使得属于同一类别的个体之间尽可能相同，而不同类别上的个体间尽可能相异。聚类 分析也称群分析，簇群
13、分析等，是数值分类学的一个分支，并在数据挖掘、图像分割、模式 分类及决策制定等众多领域中广泛应用，同时由于不需要任何应用领域知识，因而受到广大 数据挖掘研究人员的广泛重视。其中在面向大型数据库方面，目前流行的主要算法有BIRCH1、CURE6等。BIRCH 算法通过采用多阶段聚类技术，利用计算机有限的主存和辅存资源，尽可能多 地去除孤立点，实现对大规模数据库的聚类分析，它具有良好的伸缩性和处理噪音能力，许 多数据挖掘研究人员在 BIRCH 算法的基础上提出了改进算法，提高了运行速度和改进了聚基于孤立因子的层次聚类算法与应用随机抽样与图像压缩第 6 页 共 25 页类质量，CLAP4算法就是其中
14、代表之一。 数据挖掘的大多数算法主要研究的问题是发现“大模式” ，即输入数据的主要特征；另 一方面是研究“小模式”问题即孤立点挖掘，孤立点探测和分析有非常广泛的应用，如欺诈 监测、定制市场、医疗分析等领域。10 在 BIRCH 算法中，孤立点是指在那些密度较低或数量相对少得多的子聚类，它们对整 体的聚类模型影响很小，因而在重建 CF 树时，把它们当成孤立点从内存写入硬盘，留出更 多的内存空间吸收余下的数据项；而在孤立点挖掘中，孤立点的定义是指那些没有“足够多” 邻居的对象，它代表一些特别的意义。 其实两者定义是一致的，都是指在它的某个领域中 只有相对少的邻居，另外 BIRCH 算法检测孤立点是
15、为了去除它，而孤立点挖掘则是为了寻 找一些有特别意义的数据对象。 我们考虑把对孤立点的检测与对孤立点的去除结合在一起，在 BIRCH 算法和 CLAP 算 法基础上，提出一个基于孤立因子的层次聚类算法 CLOF（Clustering aLgorithm based on Outlier-handling Factor and random-sampling） 。第二章第二章 CLOFCLOF 算法系统设计需求分析算法系统设计需求分析2.1 引言我们通过本节内容来说明关于整个需求规格说明书的综述，包括本文的编写目的、 范围、名词和术语、参考资料等。2.1.1 编写目的1.明确程序的编写目的及在整
16、个项目过程中的作用。 2.提高开发效率。 3.作为以后工作的重要参考。2.1.2 项目背景在分析 BIRCH 算法与 CLAP 算法的优缺点基础上，结合孤立点挖掘算法，提出一种基 于孤立点预测的层次聚类算法（CLOF） 。 BIRCH（Balance Iterative Reducing and Clustering using Hierarchies）算法由四阶段 组成：（）装载；（）有选择地压缩；（）全局聚类；（）有选择地提炼。阶段 的主要任务是利用计算机可用的主存和辅存空间，通过一次扫描数据库的所有数据，建立起 初始的驻留内存的 CF 树；阶段是可选的阶段，决定于阶段 3 采取的全局算法；阶段的 主要任务是采用一个全局或局部的聚类算法对 CF 树的子聚类进行聚类。阶段 4 也是可选的， 通过数据库的再次扫描，进一步去除孤立点，提高聚类精度。可见 BIRCH 算法是通过采用
