中科院学习课件 模式识别 第二章

第二章聚类分析第二章聚类分析2.1聚类分析的相关概念2.2模式相似性的测度和聚类准则2.3基于试探的聚类搜索算法2.4系统聚类法2.5动态聚类法2.6聚类结果的评价2.1聚类分析的相关概念•定义对一批没有标出类别的模式样本集，按照样本之间的相似程度分类，相似的归为一类，不相似的归为另一类，这种分类称为聚类分析，也称为无监督分类。2.1聚类分析的相关概念•模式相似/分类的依据把整个模式样本集的特征向量看成是分布在特征空间中的一些点，点与点之间的距离即可作为模式相似性的测量依据。聚类分析是按不同对象之间的差异，根据距离函数的规律（大小）进行模式分类的。2.1聚类分析的相关概念•聚类分析的有效性聚类分析方法是否有效，与模式特征向量的分布形式有很大关系。–若向量点的分布是一群一群的，同一群样本密集（距离很近），不同群样本距离很远，则很容易聚类；–若样本集的向量分布聚成一团，不同群的样本混在一起，则很难分类；–对具体对象做聚类分析的关键是选取合适的特征。特征选取得好，向量分布容易区分，选取得不好，向量分布很难分开。2.1聚类分析的相关概念•两类模式分类的实例：一摊黑白围棋子–选颜色作为特征进行分类，用“1”代表白，“0”代表黑，则很容易分类；–选大小作为特征进行分类，则白子和黑子的特征相同，不能分类（把白子和黑子分开）。2.1聚类分析的相关概念•特征选择的维数在特征选择中往往会选择一些多余的特征，它增加了维数，从而增加了聚类分析的复杂度，但对模式分类却没有提供多少有用的信息。在这种情况下，需要去掉相关程度过高的特征（进行降维处理）。•降维方法–结论：若rij-1，则表明第i维特征与第j维特征所反映的特征规律接近，因此可以略去其中的一个特征，或将它们合并为一个特征，从而使维数降低一维。2.1聚类分析的相关概念•模式对象特征测量的数字化计算机只能处理离散的数值，因此根据识别对象的不同，要进行不同的数据化处理。–连续量的量化：用连续量来度量的特性，如长度、重量、面积等等，仅需取其量化值；–量级的数量化：度量时不需要详尽的数值，而是相应地划分成一些有次序的量化等级的值。•病人的病程–名义尺度：指定性的指标，即特征度量时没有数量关系，也没有明显的次序关系，如黑色和白色的关系，男性和女性的关系等，都可将它们分别用“0”和“1”来表示。•超过2个状态时，可用多个数值表示。2.2模式相似性的测度和聚类准则2.2.1相似性测度•目的：为了能将模式集划分成不同的类别，必须定义一种相似性的测度，来度量同一类样本间的类似性和不属于同一类样本间的差异性。–欧氏距离•量纲对分类的影响（下页图例）–马氏距离•特点：排除了模式样本之间的相关性•问题：协方差矩阵在实际应用中难以计算–一般化的明氏距离–角度相似性函数•特点：反映了几何上相似形的特征，对于坐标系的旋转、放大和缩小等变化是不变的。•当特征的取值仅为(0,1)两个值时的特例量纲对分类的影响（图例）2.2模式相似性的测度和聚类准则2.2.2聚类准则有了模式的相似性测度，还需要一种基于数值的聚类准则，能将相似的模式样本分在同一类，相异的模式样本分在不同的类。•试探方法•聚类准则函数法2.2模式相似性的测度和聚类准则2.2.2聚类准则•试探方法凭直观感觉或经验，针对实际问题定义一种相似性测度的阈值，然后按最近邻规则指定某些模式样本属于某一个聚类类别。–例如对欧氏距离，它反映了样本间的近邻性，但将一个样本分到不同类别中的哪一个时，还必须规定一个距离测度的阈值作为聚类的判别准则。2.2模式相似性的测度和聚类准则2.2.2聚类准则•聚类准则函数法–依据：由于聚类是将样本进行分类以使类别间可分离性为最大，因此聚类准则应是反映类别间相似性或分离性的函数；–由于类别是由一个个样本组成的，因此一般来说类别的可分离性和样本的可分离性是直接相关的；–可以定义聚类准则函数为模式样本集{x}和模式类别{Sj,j=1,2,…,c}的函数，从而使聚类分析转化为寻找准则函数极值的最优化问题。2.2模式相似性的测度和聚类准则2.2.2聚类准则•聚类准则函数法–一种聚类准则函数J的定义•J代表了属于c个聚类类别的全部模式样本与其相应类别模式均值之间的误差平方和。•对于不同的聚类形式，J值是不同的。•目的：求取使J值达到最小的聚类形式。2.3基于试探的聚类搜索算法2.3.1按最近邻规则的简单试探法•算法•讨论–这种方法的优点：计算简单，若模式样本的集合分布的先验知识已知，则可通过选取正确的阈值和起始点，以及确定样本的选取次序等获得较好的聚类结果。2.3基于试探的聚类搜索算法2.3.1按最近邻规则的简单试探法•讨论（续）–在实际中，对于高维模式样本很难获得准确的先验知识，因此只能选用不同的阈值和起始点来试探，所以这种方法在很大程度上依赖于以下因素：•第一个聚类中心的位置•待分类模式样本的排列次序•距离阈值T的大小•样本分布的几何性质2.3基于试探的聚类搜索算法2.3.1按最近邻规则的简单试探法•讨论（续）–距离阈值T对聚类结果的影响2.3基于试探的聚类搜索算法2.3.2最大最小距离算法•基本思想：以试探类间欧氏距离为最大作为预选出聚类中心的条件。2.3基于试探的聚类搜索算法2.3.2最大最小距离算法•算法（实例）2.4系统聚类法•基本思想将模式样本按距离准则逐步分类，类别由多到少，直到获得合适的分类要求为止。•算法2.4系统聚类法•距离准则函数进行聚类合并的一个关键就是每次迭代中形成的聚类之间以及它们和样本之间距离的计算，采用不同的距离函数会得到不同的计算结果。主要的距离计算准则：–最短距离法–最长距离法–中间距离法–重心法–类平均距离法2.4系统聚类法•[举例]–设有6个五维模式样本如下，按最小距离准则进行聚类分析：x1:0,3,1,2,0x2:1,3,0,1,0x3:3,3,0,0,1x4:1,1,0,2,0x5:3,2,1,2,1x6:4,1,1,1,02.4系统聚类法•[举例]–系统聚类的树状表示作业•画出给定迭代次数为n的系统聚类法的算法流程框图•对如下5个6维模式样本，用最小聚类准则进行系统聚类分析：x1:0,1,3,1,3,4x2:3,3,3,1,2,1x3:1,0,0,0,1,1x4:2,1,0,2,2,1x5:0,0,1,0,1,02.5动态聚类法•基本思想–首先选择若干个样本点作为聚类中心，再按某种聚类准则（通常采用最小距离准则）使样本点向各中心聚集，从而得到初始聚类；–然后判断初始分类是否合理，若不合理，则修改分类；–如此反复进行修改聚类的迭代算法，直至合理为止。•K-均值算法•ISODATA算法（迭代自组织数据分析算法）2.5.1K-均值算法•思想：基于使聚类性能指标最小化，所用的聚类准则函数是聚类集中每一个样本点到该类中心的距离平方之和，并使其最小化。•算法2.5.1K-均值算法•[举例]–对如图模式样本用K-均值算法进行分类2.5.1K-均值算法•讨论–K-均值算法的结果和效率受如下选择的影响：•所选聚类的数目•聚类中心的初始分布•读入次序–在实际应用中，需要试探不同的K值和选择不同的聚类中心的起始值。–如果模式样本可以形成若干个相距较远的孤立的区域分布，一般都能得到较好的收敛效果。–K-均值算法比较适合于分类数目已知的情况。2.5.1K-均值算法•作业（选k=2,z1(1)=x1,z2(1)=x10,用K-均值算法进行聚类分析）计算机编程•编写K-均值聚类算法程序，对下图所示数据进行聚类分析(选k=2)：2.5.2ISODATA算法•与K-均值算法的比较–K-均值算法通常适合于分类数目已知的聚类，而ISODATA算法则更加灵活；–从算法角度看，ISODATA算法与K-均值算法相似，聚类中心都是通过样本均值的迭代运算来决定的；–ISODATA算法加入了一些试探步骤，并且可以结合成人机交互的结构，使其能利用中间结果所取得的经验更好地进行分类。2.5.2ISODATA算法•基本步骤和思路（1）选择某些初始值。可选不同的参数指标，也可在迭代过程中人为修改，以将N个模式样本按指标分配到各个聚类中心中去。（2）计算各类中诸样本的距离指标函数。（3）~（5）按给定的要求，将前一次获得的聚类集进行分裂和合并处理（（4）为分裂处理，（5）为合并处理），从而获得新的聚类中心。（6）重新进行迭代运算，计算各项指标，判断聚类结果是否符合要求。经过多次迭代后，若结果收敛，则运算结束。2.5.2ISODATA算法•算法•[举例]–对如图模式样本用ISODATA算法进行分类2.6聚类结果的评价•迅速评价聚类结果，在上述迭代运算中是很重要的，特别是具有高维特征向量的模式，不能直接看清聚类效果，因此，可考虑用以下几个指标来评价聚类效果：–聚类中心之间的距离•距离值大，通常可考虑分为不同类–聚类域中的样本数目•样本数目少且聚类中心距离远，可考虑是否为噪声–聚类域内样本的距离方差•方差过大的样本可考虑是否属于这一类•讨论：模式聚类目前还没有一种通用的放之四海而皆准的准则，往往需要根据实际应用来选择合适的方法。作业•画出ISODATA算法的流程框图•试用ISODATA算法对如下模式分布进行聚类分析：{x1(0,0),x2(3,8),x3(2,2),x4(1,1),x5(5,3),x6(4,8),x7(6,3),x8(5,4),x9(6,4),x10(7,5)}计算机编程•编写ISODATA聚类算法程序，对如下数据进行聚类分析：{x1(0,0),x2(3,8),x3(2,2),x4(1,1),x5(5,3),x6(4,8),x7(6,3),x8(5,4),x9(6,4),x10(7,5)}