模式识别中聚类分析算法综述(论文).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附 录 a22附 录 b26 毕 业 设 计 （ 论文 ） 第 41 页1 绪论将物理或抽象对象的集合分成由类似的对象组成的多个类的过程被称为聚类。由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其他簇中的对象相异。“物以类聚，人以群分”，在自然科学和社会科学中，存在着大量的分类问题。聚类分析又称群分析，它是研究（样品或指标）分类问题的一种统计分析方法。聚类分析起源于分类学，但是聚类不等于分类。聚类与分类的不同在于，聚类所要求划分的类是未知的1。1.1 课题背景及意义聚类分析的应用范围很广，常常应用于商业，生物，地理，保险行业，因特网和电子商务等领域。例如，在商业中，聚类分析既可以被用来发现不同的客户群，并且通过购买模式刻画不同的客户群的特征，也可用于研究消费者行为，寻找新的潜在市场、选择实验的市场，并作为多元分析的预处理；在生物领域，聚类分析被用来动植物分类和对基因进行分类，获取对种群固有结构的认识；在保险行业，聚类分析通过一个高的平均消费来鉴定汽车保险单持有者的分组，同时根据住宅类型，价值，地理位置来鉴定一个城市的房产分组等等。所以，研究聚类分析的相关算法对于我们以后在各个领域中解决问题显得十分必要。1.2 聚类算法的种类聚类算法可以视为：通过考虑包含在x中的所有可能划分集合的一小部分，就可以得到可判断聚类的方案，这个结果依赖于使用的算法和准则。因此，聚类算法是一个试图识别数据集合聚类的特殊性质的学习过程。聚类算法主要包括以下几种2。（1）顺序算法（sequential algorithm）：这些算法产生一个独立的聚类，它们是非常直接和快速的算法。这种算法的大多数都至少将所有特征向量使用一次或几次（一般不超过五六次），最后的结果依赖于向量参与算法的顺序。这种方法会产生致密和超球面或超椭圆面形状的聚类（取决于使用的距离度量）。（2）层次聚类算法（hierarchical clustering algorithm）：这种方法被进一步分为1、合并算法（agglomerative algorithm）。这些算法会在每一步产生减少聚类数量的聚类序列，聚类生成的结果都来自于前一步的两个聚类的合并。合并算法的典型代表是单一和完全连接算法。合并算法被进一步分为由矩阵理论得到的算法和由图形理论得到的算法，这些算法适用于长轴聚类（用单一链接算法）和致密聚类（用完全链接算法）。2、分裂算法（divisive algorithm）。这种算法的原理与合并算法的原理相反，在每一步产生增加聚类数量的聚类序列。在每一步聚类产生的结果都是将前一步的一个聚类分裂成两个得到的。（3）基于代价函数最优的聚类算法（clustering algorithms based on cost function optimization）：这种方法用代价函数j来量化可判断性，通常聚类数量是固定的。这种算法用微分学概念，通过最优j产生连续的聚类，当j的局部最优确定时，算法才结束。这种类型的算法也称为迭代函数最优方法，这类算法又可细分为1、硬或脆聚类算法（hard or crisp clustering algorithm）。其中一个向量绝对属于特定聚类。根据选择的最优准则，以最优分类将向量分到各个聚类中。这种类型中最著名的算法是isodata或者lloyd算法。2、概率聚类算法（probabilistic clustering algorithm）。它是硬聚类算法的特例，采用贝叶斯分类方法，并且每个向量被分到使最大的聚类中，通过适当地定义优化任务完成概率估计。3、模糊聚类算法（fuzzy clustering algorithm）。在这种算法中，向量属于超过特定阈值的聚类。4、可能聚类算法（possibilistic clustering algorithm）。在这种情况下，我们测量向量属于聚类的可能性。5、边界检测算法（boundary detection aigorithm）。不同于用向量本身来确定聚类，这些算法迭代调整聚类的边界。这些算法虽然包括了代价函数优化原理，但它们与以上算法有本质的区别。前述所有算法使用聚类表达，目的是用最优方法来确定局部空间，相反地，边界检测算法则是寻找聚类间边界最优放置的方法。（4）其他算法：最后一类包括一些特殊的聚类技术，这些技术不能归结到上述任何一类中。这些算法主要有分支和约束聚类算法（branch and bound clustering algorithm）、遗传聚类算法（genetic clustering algorithm）、随机松弛算法（stochatic relaxation method）、竞争学习算法（competitive learning algorithm）等。1.3 可能聚类的数量给定时间和资源，将集合中的特征向量分到聚类中的最好方法是识别所有可能的划分，并根据事先确定的准则选择可判断的聚类。然而，对于中等值这都是不可能的。令表示将个向量聚类到组的所有可能结果。由定义可能，聚类不可能是空的，很明显需要满足下列条件：（1）（2）（3）令表示个向量分到类的所有可能，其中。第个向量（1）或者添加到的任一个成员的聚类中（2）或者对的每个成员形成一个新聚类因此可以得出 (1.1)式（1.1）的解就是所谓的第二类的stirling数量 (1.2)显然，如果聚类固定，则这种计算是有效的。如果不是这种情况，则需要对所有可能的值计算所有可能的聚类。由上面的分析可知，即使对于中等值，评估所有的聚类来寻找最可判断的一个也是不现实的。例如，如果要评估100个对象分到5类的所有可能类聚，用计算机计算每个聚类要用秒，大约需年之后才会得到最可判断的聚类2。2 聚类算法：顺序算法2.1 基本顺序算法方案描述令表示从向量到聚类的距离（或不相似性），这种定义既考虑了中所有的向量，也考虑了它的表达向量。这个算法方案需要用户定义参数的不相似性阈值和允许的最大聚类数。算法的基本思想如下：由于要考虑每个新向量，根据向量到已有聚类的距离，将它分配到一个已有聚类中，或者一个新生成的聚类中。设由算法生成的聚类数为，那么这个算法方案可以描述如下2。基本顺序算法方案（bsas） - * *- * *如果必要，更新向量表达- 选择不同的会产生不同的算法。当由一个单向量表达时，变为其中是的表达。在以均值向量为表达的情况下，更新会以迭代形式出现，即其中是将分到该聚类后的势，（）是将分到该聚类后的表达。不难看出，这些向量在bsas中的顺序非常重要。无论是聚类的数量还是聚类本身，不同的顺序会导致完全不同的聚类结果。另一个影响聚类算法结果的重要因素是阈值的选择，这个值直接影响由bsas产生的聚类数量。如果选得太小，会生成不必要的聚类：另一方面，如果选得太大，则聚类的数量又会不够。在这两种情况下都不会生成最适合数据集的聚类数量。2.2 聚类数的估计本节介绍一种确定聚类数的简单方法，该方法适用于bsas，也适用于其它算法，其聚类数不是输入参数。下面，指具有给定不相似阈值的bsas算法。for = a to b step c-算法执行s次，每一次都用不同的顺序表示数据。-估计聚数类，作为从s次算法得出来的最常出现的聚类数。nexta值和b值是x的所有向量对的最小和最大不相似级别，即，。c的选择直接受的影响。s值越大，统计采样就越大，因此，结果的精度就越高。接下来，画出聚类数与的关系图。该图有一定数量的平坦区域。我们估计聚类数将对应最宽的平坦区域。至少对于分离性很好的致密聚类情况，这个聚类数是理想的。下面直观地解释这个参数。假设数据形成两个分离性很好的致密聚类和。的两个向量间的最大距离是，并且假设。另是所有距离中的最小值，这里，且。很明显，对于，由bsas得到的聚类数是2。另外，如果，区间很大，因此在与关系图中对应着一个很宽的范围。在上述过程中，隐含假设了特征向量确实能够组成聚类。如果不是这种情况，这种方法就没有用了。如果向量是致密聚类，但是分离得不好，这种方法给出的结果是不可靠的，因为与的图中不可能包含宽的平坦区域。在有些情况下，应该考虑在与图中比较大的平坦区域对应的所有聚类数。例如，如果有三个聚类，前两个很近，而远离第三个，最平坦区域的聚类数可能是=2，次平坦区域的聚类数可能是= 3.如果放弃次平坦的区域，就会丢掉三个聚类的解决方法。2.3 bsas的改进已经讲过，bsas的基本思想是每个输入向量x被分配到已有聚类或新形成的聚类中。因此，对于x的分配是在最后的聚类形成之前决定的，而最后的聚类是在所有的向量都处理后才形成的。下面介绍克服了这个缺点的bsas，称之为改进的bsas（mbsas），这种改进的代价是x的向量必须参与算法两次。算法包括两个阶段，第一阶段是将x的一些向量分配到聚类中来形成类；在第二阶段中，没有被分配的向量第二次参与算法，并分配到合适的类中。mbsas具有形式如下。聚类的确定-for i = 2 to n-find -if()and(m q)then*m = m+1*-endifendfor模式分类for i = 1to n-如果没有分配到一个聚类中，那么 *find *如果必要，更新向量表达-endifendfor聚类数在第一阶段确定，然后不许改变。因此，在第二阶段，对每个向量做决定时，都要考虑所有的聚类。同bsas情况一样，mbsas也对向量参与算法的顺序敏感。另外，因为mbsas在数据集x上执行两遍（每个阶段一遍），按预期，它的速度应该慢于bsas。但是，它的时间复杂度应该与bsas处在统一数量级上，用o(n)表示。最后必须指出，在改进之后，当使用相似性测度时，也可以使用mbsas。2.4 改进阶段在所有上述算法中，可能出现两个聚类的位置离得很近的情况，把它们合并成一类是最理想的。对这种情况。上述所有算法都无能为力。解决这种问题的方法是在上述过程结束后，执行下面的合并过程。合并过程找到，（i t，即两类间的最小距离大于阈值，则退出循环。最短距离法的编程代码详见附录b。3.1.2 最长距离法在最长距离法中，两类中的所有样品间的距离必须都小于阈值，才能将两类合并。定义为类中所有样品和类中所有样品间的最大距离，则有其中表示类中的样品u与类中的样品v之间的距离。若类是由，两类合并而成，则，递推可得最长距离法的实现步骤如下（1） 获得所有样品特征。（2） 输入阈值t（计算所有样品距离的最大值与最小值，输出，作为阈值的参考）。（3） 将所有样品各分一类，聚类中心数centernum = 样品总数patternnum，m_pattern(i).category = i；m_center(i).feature = m_pattern(i).feature。（4） 对所有样品循环：计算所有聚类中心间的距离，两类间的距离等于两类间样品的最大距离maxdis。取所有maxdis中的最小值。设类和类的距离最小，为mindis。若mindis t，则将类号较大的类归入类号较小的类，重新排序类号，centernum = centernum-1.否则mindis t，即所有类间距离均大于阈值，则退出循环，归类完成。最长距离法的编程代码详见附录b。3.1.3 中间距离法最短距离法和最长距离法采用的是分类距离的两个极端。中间距离法则介于两者之间，若类由，两类合并而成，则，两类的中间距离定义为 （3.1）中间距离法的实现步骤如下（1） 获得所有样品特征。（2） 输入阈值t（计算所有样品距离的最大值与最小值，输出，作为阈值的参考）。（3） 将所有样品各分一类，聚类中心数centernum = 样品总数patternnum。m_pattern(i).category = i；m_center(i).feature = m_pattern(i).feature。（4） 建立距离矩阵centerdistance，记录各类之间的距离，初始值为各样品间的距离。（5） 对所有样品循环：找到centerdistance中的最小值 = centerdistance(,)，即类和类距离最小。若 t，则将所有类成员归入类；centernum = centernum-1；重新顺序排列类号；根据式（3.1）重新计算距离矩阵centerdistance，否则（）终止循环，分类结束。中间距离法的编程代码详见附录b。3.1.4 重心法重心法的提出考虑了类中样品个数对类间距离的影响。设类由类和类合并而成，类有个样品，类中有个样品。则重心法定义类和类间的距离为 （3.2）重心法的实现步骤如下（1） 获得所有样品特征。（2） 输入阈值t（计算所有样品距离的最大值与最小值，输出，作为阈值的参考）。（3） 将所有样品各分一类，聚类中心数centernum = 样品总数patternnum。m_pattern(i).category = i；m_center(i).feature = m_pattern(i).feature。（4） 建立距离矩阵centerdistance，记录各类之间的距离，初始值为各样品间的距离。（5） 对所有样品循环：找到centerdistance中的最小值 = centerdistance(,)，即类和类距离最小（）。若 t，则将所有类成员归入类；centernum = centernum-1；重新顺序排列类号；根据式（3.2）重新计算距离矩阵centerdistance，否则（）终止循环，分类结束。中间距离法的编程代码详见附录b。3.1.5 类平均距离法类平均距离的定义也考虑了样品的整体分布特性对其分类的影响。设类由类和类合并而成，类有个样品，类中有个样品，类中有个样品。定义为类和类间的平均距离，为类和类间的平均距离。则递推可得 （3.3）类平均距离法的实现步骤如下（1） 获得所有样品特征。（2） 输入阈值t（计算所有样品距离的最大值与最小值，输出，作为阈值的参考）。（3） 将所有样品各分一类，聚类中心数centernum = 样品总数patternnum。m_pattern(i).category = i；m_center(i).feature = m_pattern(i).feature。（4） 建立距离矩阵centerdistance，记录各类之间的距离，初始值为各样品间的距离。（5） 对所有样品循环：找到centerdistance中的最小值 = centerdistance(,)，即类和类距离最小（）。若 2*centernum，或者进行了偶数次迭代并且precenternum centernum/2，则进入第（9）步，合并处理。否则，转第（10）步分裂处理。（9） 合并操作，计算全部聚类中心的距离，设，（）距离最近，设最小距离。若 equation，则precenternum+，新中心特征值等于m_center()的特征值，只是第位需要调整，m_center().feature() = m_center().feature() + a*mequation，m_center(precenternum-1).feature() = m_center().feature() - a*mequation；其中a =（0,1），取a = 0.5。（11） 如果是最后一次迭代运算（即第iternum次迭代）则结束循环。否则循环继续第（4）步，迭代次数加1。迭代自组织的数据分析算法的编程代码详见附录b。结 论本文主要是讨论了模式识别中聚类分析的几类算法，并以层次算法中的最短距离法、最长距离法、中间距离法、重心法、类平均距离法和基于代价函数最优的聚类算法中的k均值算法、迭代自组织的数据分析算法为例对其进行了较为详细的介绍并将其编程实现。论文首先简单介绍了聚类分析的应用及其算法的分类，并给出了聚类分析可能聚类的数量。之后详细介绍了聚类分析算法中的顺序算法、层次算法和基于代价函数最优的聚类算法，介绍了算法的基本思想及其特点并以其中的几类典型算法为例，给出了其实现需要的matlab程序。通过写这篇论文，我学到了很多以前没学过的知识。对模式识别以及其中的聚类分析算法有了初步的认识，学习了聚类分析中的几个算法，对其原理以及代码实现有了详细的认识，锻炼了自己的编程能力也熟悉了matlab的编程语言，提高了自己应用matlab解决实际问题的能力。致 谢参考文献附 录 a译文1 ga-based clusteringgenetic algorithm (gas) is a simple, robust and efficient optimization technique guided by principles of natural genetics in natural selection and survival of the fittest mechanisms. ga-based clustering algorithms have a history of being applied into clustering analysis. in this paper, the ga-based clustering is performed by selecting proper cluster centers such that a similarity metric of the resulting clusters is optimized. they obviously are centroid-based and tend to generate hyperspherical clusters. in this paper, a graph-based genetic approach for sequence clustering is proposed.the ga-based algorithm starts with an initial population of individuals representing feasible solutions to the k clustering problem. ujjwal malulik uses strings of real number to encode the k cluster centers. so for an n-dimensional space, the length of individual chromosome is n k words. hwei-jenlin uses binary representation rather than string representation to encode k cluster centers to speed up the fitness evaluation. another encoding scheme is the group numbers to denote which cluster the object belongs to.the fitness is a measure of how good a solution is and is used as a basis for selecting individuals for reproduction. each individual is assigned a fitness value. the higher the fitness value is, the better the solution is. most of existing ga-based k clustering algorithms use the sum of squared euclidean distance of each object from its cluster center as their fitness function.in each generation, individuals are selected based on their fitness values from the current population. the most widely used selection mechanisms are roulette wheel selection and tournament selections. the operators of crossover and mutation is use to form a new population.this process is iterative for a number of generations. at the end the best solution available in the population is chosen as the solution for the clustering.基于遗传算法的聚类遗传算法（gas）是一种简单，可靠，高效的优化算法，它以自然遗传学机制中优胜劣汰的自然选择和生存原则为指导。基于遗传算法的聚类算法被应用到聚类分析已经有了一段历史。在论文中遗传算法通过选择适当的聚类中心使得聚类分析结果的相似性度量得到优化。显然，它们基于形心，并且容易产生超球集群。这篇论文提出了基于图的基因顺序分析和聚类分析的方法。基于遗传算法的算法以初始人口开始，代表k聚类问题的可行的解决方案ujjwal malulik使用字符串实数编码的k个聚类中心。因此，对于一个n维空间中，个体的染色体的长度为nk千字。hwei-jenlin用二进制表示，而不是用字符串表示k个聚类中心的编码，以加快身体素质评估。在论文中用另一种编码方案组数字来表示对象属于哪个集群。身体素质是衡量一个好的解决方案是如何被用作再现个人选择的基础。每个人都分配了一个身体素质价值。身体素质价值越高，表明解决方案越好。大多数现有的基于遗传算法的k聚类算法使用每个对象的聚类中心的平方欧氏距离的总和作为他们的身体素质函数。在每一代中，都是基于现在人口的身体素质价值来选择个人的。使用最广泛的选择机制是轮盘赌选择和比赛的选择。运用交叉和变异的方法从而形成一个新的人种。这个过程要迭代数代。结束时，选择在人口中的最好的解决方案作为的集群解决方案。译文2 analysis of landsat 5tm data of malaysian land covers using isodata clustering technique studies on classification of remote sensing data have long been carried out by numerous researchers worldwide, with more efforts made regionally than globally. many regional studies have be