《现代控制专题》.doc

现代控制专题报 告报告题目： 模式识别聚类分析算法 学生姓名： 胡家滨 学 号： 5901112211 专业班级： 机械设计制造及其自动化125班 2013年12 月10 日 摘要 将数据分类到不同的类或者簇的过程即为聚类分析，这是一种探索性的分析，它并不需要分类的标准，它能够从样本数据来自动进行分类。在运用上，聚类分析是数据分析的主要任务，它能够获得数据的分布状况，通过观察每簇数据的特征，集中对特定的聚簇集合做进一步的分析。同时还能为其他算法，比如分类和定性归纳算法的预处理步骤。本文对模式识别中聚类分析算法进行了综述，主要论述了顺序算法、层次算法和基于代价函数最优的聚类算法，其中层次算法分为合并算法和分裂算法，而基于代价函数最优的聚类算法则分为K均值算法和迭代自组织的数据分析算法。本文首先介绍了聚类算法的应用范围及其意义，并对聚类算法的基本分类进行了简单介绍。随后简单的介绍了聚类算法的具体应用，并且认识到了几类算法各自的特点。其中，层次算法中实现步骤较为简单，但在其实现过程中需要输入一个合适的阈值，阈值的大小直接影响最后的结果，而且相同的阈值，不同的算法可能得到不同的结果。而K均值算法的实现结果则与阀值无关，只需定义迭代次数和类中心个数，与之相比，ISODATA算法可以在计算过程中不断调整类中心的个数。关键词：聚类分析，层次算法，顺序算法，基于代价函数最优的聚类算法。目 录（二号宋体）1、 介绍 12、聚类算法：顺序算法 33、聚类算法：层次算法 34、聚类算法：基于代价函数最优的聚类算法 45、结论 5 1.介绍聚类是将物理或抽象的集合分成类似对象组成的多个类的过程。在聚类所生成的簇是一组数据对象的集合，它们与同一个簇中的对象相似，与其他簇对象不同。在科学研究中经常需要进行分类问题的解决。所以聚类分析也就诞生了。聚类分析也成为群分析，它是分类问题的一种统计分析方法。这个方法起源与分类学，但要注意的是聚类要求划分的类是未知的，这是与分类不同的地方。聚类分析应用于很多方面，经常应用于生物，地理，网络，商务等等领域。就比如在商业上，这种方法可以用来发现各种客户群，同时通过客户的需求来确定他们的特征，从而可以研究人们的需求和行为，继续发掘潜在的商业商机。在生物的领域中，经常需要对动物植物基因等等进行分类，这种方法很有利于生物结构组成的研究。聚类分析还可以用于许多领域中，所以聚类分析这种方法对我们在其他许多领域中有着十分重要的作用。 聚类算法可以视为通过考虑包含在X中的所有可能划分集合的一小部分，得到可判断聚类的方案。聚类算法主要包括以下几种： （1）顺序算法：这些算法产生一个独立的聚类，它们是非常直接和快速的算法。这种算法的大多数都至少将所有特征向量使用一次或几次（一般不超过五六次），最后的结果依赖于向量参与算法的顺序。这种方法会产生致密和超球面或超椭圆面形状的聚类（取决于使用的距离度量）。（2）层次聚类算法：这种方法被进一步分为 1、合并算法。这些算法会在每一步产生减少聚类数量m的聚类序列，聚类生成的结果都来自于前一步的两个聚类的合并。合并算法的典型代表是单一和完全连接算法。合并算法被进一步分为由矩阵理论得到的算法和由图形理论得到的算法，这些算法适用于长轴聚类（用单一链接算法）和致密聚类（用完全链接算法）。 2、分裂算法：这种算法的原理与合并算法的原理相反，在每一步产生增加聚类数量m的聚类序列。在每一步聚类产生的结果都是将前一步的一个聚类分裂成两个得到的。（3）基于代价函数最优的聚类算法：这种方法用代价函数J来量化可判断性，通常聚类数量m是固定的。这种算法用微分学概念，通过最优J产生连续的聚类，当J的局部最优确定时，算法才结束。这种类型的算法也称为迭代函数最优方法，这类算法又可细分为 1、硬或脆聚类算法：其中一个向量绝对属于特定聚类。根据选择的最优准则，以最优分类将向量分到各个聚类中。这种类型中最著名的算法是Isodata或者Lloyd算法。 2、概率聚类算法：它是硬聚类算法的特例，采用贝叶斯分类方法，并且每个向量x被分到使P(C|x）最大的聚类C中，通过适当的定义优化任务完成概率估计。 3、模糊聚类算法：在这种算法中，向量属于超过特定阈值的聚类。 4、可能聚类算法：在这种情况下测量的向量x属于聚类C的可能性。 5、边界检测算法：不同于用向量本身来确定聚类，这些算法迭代调整聚类的边界。这些算法虽然包括了代价函数优化原理，但它们与以上算法有本质的区别。前述所有算法使用聚类表达，目的是用最优方法来确定局部空间，相反地，边界检测算法则是寻找聚类间边界最优放置的方法。（4） 其他算法：这些算法主要有分支和约束聚类算法遗传聚类算法、随机松弛算法、竞争学习算法等。2、聚类算法：顺序算法 令表示从向量到聚类的距离（或不相似性），这种定义既考虑了中所有的向量，也考虑了它的表达向量。这个算法方案需要用户定义参数的不相似性阈值和允许的最大聚类数。算法的基本思想如下：由于要考虑每个新向量，根据向量到已有聚类的距离，将它分配到一个已有聚类中，或者一个新生成的聚类中。向量在BSAS中的顺序非常重要。无论是聚类的数量还是聚类本身，不同的顺序会导致完全不同的聚类结果。另一个影响聚类算法结果的重要因素是阈值的选择，这个值直接影响由BSAS产生的聚类数量。如果选得太小，会生成不必要的聚类：另一方面，如果选得太大，则聚类的数量又会不够。在这两种情况下都不会生成最适合数据集的聚类数量。3、聚类算法：层次算法层次聚类算法与顺序聚类算法有所不同。具体地说，它不产生单一聚类，而是产生层次聚类。层次算法通常应用于社会科学和生物学等领域。另外，其它领域也会用到这种算法，包括现代生物学、医学和考古学。计算机科学与工程领域也经常应用层次聚类算法。假设是将要聚类的l维向量集。层次聚类算法产生一个嵌套聚类的层次。更具体地说，这些算法包含N步，与数据向量的数量一样多。在第t步，要在前t-1步的聚类基础上生成新聚类。有两种不同的算法：合并和分裂层次算法。合并算法中，初始聚类由N个聚类组成，每个聚类仅包含X中的一个元素。第一步生成聚类，它包含N-1个集合，如。重复此过程直到产生最后一个聚类，它只包含一个单个的聚类集合，即数据集X。因而得到聚类的层次为分裂算法与合并算法的思路恰好相反。在这种算法中，初始聚类仅包括一个集合X。第一步产生聚类，它由个集合组成，如。重复此过程直到产生最后一个聚类，它包含N个集合，每个集合仅包含X中的一个元素，在这种情况下可得4 、聚类算法：基于代价函数最优的聚类算法基于代价函数最优的聚类算法：这种方法用代价函数J来量化可判断性，通常聚类数量是固定的。这种算法用微分学概念，通过最优J产生连续的聚类，当J的局部最优确定时，算法才结束，这种类型的算法也称为迭代函数最优方法。本章将简单介绍K均值算法和迭代自组织的数据分析算法。K均值算法能够使聚类域中所有样品到聚类中心距离的平方和最小。其原理为：先取k个初始距离中心，计算每个样品到这k个中心的距离，找出最小距离把样品归入最近的聚类中心；修改中心点的值为本类所有样品的均值，再计算各个样品到k个中心的距离，重新归类、修改新的中心点。直到新的距离中心等于上一次的中心点时结束。此算法的结果受到聚类中心的个数以及初始聚类中心的选择影响，也受到样品几何性质及排列次序影响。如果样品的几何特性表明它们能形成几个相距较远的小块孤立区域，则算法多能收敛。迭代自组织的数据分析算法也称ISODATA算法。此算法与K均值算法有相似之处，即聚类中心也是通过样品均值的迭代运算来决定的。但ISODATA加入了一些试探性的步骤，能吸引中间结果所得到的经验，在迭代过程中可以将一类一分为二，也可以将两类合并。5、结论 本文主要是对聚类分析的几种算法作一个简单的介绍并且介绍各个算法的原理思路。论文首先简单介绍了聚类分析的应用及其算法的分类，并给出了聚类分析可能聚类