模式识别中聚类分析算法综述(论文).doc

毕业设计 (论 文)模式识别中聚类分析算法综述院 别专业名称信息与计算科学班级学号学生姓名指导教师2013年06月10日 模式识别中聚类分析算法综述摘 要聚类分析是将数据分类到不同的类或者簇的过程，聚类分析是一种探索性的分析，在分类的过程中，人们不必事先给出一个分类的标准，聚类分析能够从样本数据出发，自动进行分类从实际应用的角度看，聚类分析是数据挖掘的主要任务之一而且聚类能够作为一个独立的工具获得数据的分布状况，观察每一簇数据的特征，集中对特定的聚簇集合作进一步地分析聚类分析还可以作为其他算法（如分类和定性归纳算法）的预处理步骤本文对模式识别中聚类分析算法进行了综述，主要论述了顺序算法、层次算法和基于代价函数最优的聚类算法，其中层次算法分为合并算法和分裂算法，其中合并算法又包括最短距离法、最长距离法、中间距离法、重心法、类平均距离法；而基于代价函数最优的聚类算法则分为K均值算法和迭代自组织的数据分析算法本文首先介绍了聚类算法的应用范围及其意义，并对聚类算法的基本分类进行了简单介绍，同时对可能聚类的数量进行了阐述之后，详细介绍了上述各类算法的算法思想及其具体的实现步骤，并在顺序算法一章中给出了BSAS算法的改进，并运用MATLAB对层次算法和基于代价函数最优的聚类算法中的几个具体算法进行了代码实现，通过对样品图片的识别分类认识了聚类算法的具体应用，并且认识到了几类算法各自的特点。

其中，层次算法中的五个算法实现步骤较为简单，但在其实现过程中需要输入一个合适的阈值，阈值的大小直接影响最后的结果，而且相同的阈值，不同的算法可能得到不同的结果而K均值算法的实现结果则与阈值无关，只需定义迭代次数和类中心个数与之相比，ISODATA算法则具有自组织性，会在计算过程中不断调整类中心的个数关键词： 聚类分析，顺序算法，层次算法，基于代价函数最优的聚类算法The Overview of Pattern Recognition Clustering AlgorithmAuthor:Whuenkmnkn Tutor:CnunnknhcfjujAbstractCluster analysis is a data classification into different classes or clusters in the process, Cluster analysis is an exploratory analysis, in the classification process, people do not give a classification criterion in advance, cluster analysis to the data from the sample starting, automatic classification. From a practical perspective, Cluster analysis is one of the main tasks of data mining. Moreover clustering can be used as a separate tool to obtain the distribution of the data, observe characteristics of the data in each cluster and make a further analysis on particular clustered sets. Cluster analysis can also be used as other algorithms’ (such as classification and qualitative induction algorithm) preprocessing step.In this paper, clustering algorithms in pattern recognition are reviewed, mainly discussing the sequential algorithm, hierarchical algorithms and clustering algorithm based on cost function optimization. Hierarchical algorithm is divided into division algorithm and merging algorithm, which also includes the shortest distance algorithm, the longest distance algorithm, the middle distance algorithm, center of gravity algorithm, the class average distance algorithm; while the clustering algorithm based on cost function optimization is divided into K-means algorithm and iterative self-organizing data analysis algorithms. At first this paper describes the application of clustering algorithm and its significance, and give a brief introduction of the basic clustering algorithm, while the possible number of clusters are described. And then the algorithm ideas and concrete steps to achieve of various algorithms above are detailed. At the same time, the improved BSAS algorithm is gave in the chapter about the sequential algorithm and several specific algorithms in the hierarchical clustering algorithm and the algorithm based on cost function optimization are coded by MATLAB. Through identifying sample images, I get to know the specific application and the characteristics of different clustering algorithms. The five specific hierarchical algorithms’ are easy to achieve by several simple steps, while its implementation process need to enter an appropriate threshold value. The threshold value directly affects the final clustering results and different algorithms may produce different results with the same threshold value. While the results of K-means algorithm is independent of the threshold, simply define the number of iterations and the number of cluster center. In contrast, ISODATA algorithm is self-organization and will adjust the number of cluster center continuously during the calculation process.Key Words: Cluster Analysis, Sequential Algorithm, Hierarchical Algorithm, Clustering Algorithm Based on Cost Function Optimization目 录1 绪论 11.1 课题背景及意义 11.2 聚类算法的种类 11.3 可能聚类的数量 22 聚类算法Ⅰ：顺序算法 42.1 基本顺序算法方案描述 42.2 聚类数的估计 52.3 BSAS的改进 62.4 改进阶段 73 聚类算法Ⅱ：层次算法 93.1 合并算法 93.1.1 最短距离法 103.1.2 最长距离法 113.1.3 中间距离法 123.1.4 重心法 123.1.5 类平均距离法 133.2 分裂算法 144 聚类算法Ⅲ：基于代价函数最优的聚类算法 164.1 K均值算法 164.2 迭代自组织的数据分析算法 16结 论 19致 谢 20参考文献 21附 录 A 22附 录 B 26 毕 业 设 计 （ 论文 ） 第 38 页1 绪论将物理或抽象对象的集合分成由类似的对象组成的多个类的过程被称为聚类。

由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其他簇中的对象相异物以类聚，人以群分”，在自然科学和社会科学中，存在着大量的分类问题聚类分析又称群分析，它是研究（样品或指标）分类问题的一种统计分析方法聚类分析起源于分类学，但是聚类不等于分类聚类与分类的不同在于，聚类所要求划分的类是未知的[1]1.1 课题背景及意义聚类分析的应用范围很广，常常应用于商业，生物，地理，保险行业，因特网和电子商务等领域例如，在商业中，聚类分析既可以被用来发现不同的客户群，并且通过购买模式刻画不同的客户群的特征，也可用于研究消费者行为，寻找新的潜在市场、选择实验的市场，并作为多元分析的预处理；在生物领域，聚类分析被用来动植物分类和对基因进行分类，获取对种群固有结构的认识；在保险行业，聚类分析通过一个高的平均消费来鉴定汽车保险单持有者的分组，同时根据住宅类型，价值，地理位置来鉴定一个城市的房产分组等等所以，研究聚类分析的相关算法对于我们以后在各个领域中解决问题显得十分必要1.2 聚类算法的种类聚类算法可以视为：通过考虑包含在X中的所有可能划分集合的一小部分，就可以得到可判断聚类的方案，这个结果依赖于使用的算法和准则。

因此，聚类算法是一个试图识别数据集合聚类的特殊性质的学习过程聚类算法主要包括以下几种[2]1）顺序算法（Sequential algorithm）：这些算法产生一个独立的聚类，它们是非常直接和快速的算法这种算法的大多数都至少将所有特征向量使用一次或几次（一般不超过五六次），最后的结果依赖于向量参与算法的顺序这种方法会产生致密和超球面或超椭圆面形状的聚类（取决于使用的距离度量）。