大二下大礼包-模式识别chapter

模式识别

PatternRecognition

2015Wuhan,Hubei,ChinaTel.:+86-27-68771218Email:Mobile:8Web:Dr.Prof.JianYao

（姚剑）SchoolofRemoteSensingandInformationEngineering

WuhanUniversity,Wuhan,Hubei,P.R.China第一章概论第二章贝叶斯决策理论第三章判别函数与确定性分类器第四章聚类分析第五章模式特征分析与选取第六章模糊集合理论在模式识别中的应用第七章句法模式识别第八章神经网络在模式识别中的应用教学纲要模式识别§4.1相关概念§4.2模式相似性测度与聚类准则§4.3聚类算法§4.4聚类结果评价第四章聚类分析

第四章聚类分析第四章聚类分析

第四章聚类分析引言

§4.1相关概念没有训练样本存在，属于非监督分类。目的是将一批数据（模式）组成一些“有意义”的集合（聚类）。这个思想在生物学、社会学、医学、地球科学等学科都是很常见的。下面举一个生物学中的例子：假设我们有下列动物：羊，狗，猫，麻雀，海鸥，小毒蛇，金鱼，红色mullet（一种小海鱼，可以吃），蓝色鲨鱼和青蛙。将为它们分成不同的类别，我们需要一定的规则。如果我们用不同的准则来聚类，可以形成不同的结果，如下面所示。引言

§4.1相关概念麻雀、青蛙、海鸥、小毒蛇鲨鱼金鱼、红mullet羊、狗、猫以产后代的方式和是否有肺联合标准来分羊、狗、猫、鲨鱼麻雀、海鸥、小毒蛇、金鱼、青蛙、红mullet以产后代的方式分金鱼、鲨鱼、红mullet羊、麻雀、狗、海鸥……以肺是否存在分金鱼、鲨鱼、红mullet羊、麻雀、狗、海鸥……以生活环境分引言

§4.1相关概念这个例子说明两个问题：1）聚类在生物分类中很常见；2）不同的准则结果有很大差别。人类总是将获取的信息再聚类，否则，不可能处理每个信息后根据每个类的共同特征来表征这个类。比如当我们看见草地上一条狗的时候，我们会推断它的叫声，因为狗的叫声是一个共同特征。聚类过程如下：特征的选择相似性度量聚类准则聚类算法聚类评价聚类结果的解译定义：

对一批没有标出类别的模式样本集，按照样本之间的相似程度分类，相似的归为一类，不相似的归为另一类，这种分类称为聚类分析，也称为无监督分类。相关概念

§4.1相关概念分类与聚类的区别：分类：用已知类别的样本训练集来设计分类器（监督学习）。聚类（集群）：用事先不知样本的类别，而利用样本的先验知识来构造分类器（无监督学习）。§4.1相关概念相关概念

模式相似/分类的依据：

把整个模式样本集的特征向量看成是分布在特征空间中的一些点，点与点之间的距离即可作为模式相似性的测量依据。 聚类分析是按不同对象之间的差异，根据距离函数的规律（大小）进行模式分类的。§4.1相关概念相关概念

聚类分析的有效性：聚类分析方法是否有效，与模式特征向量的分布形式有很大关系。若向量点的分布是一群一群的，同一群样本密集（距离很近），不同群样本距离很远，则很容易聚类；若样本集的向量分布聚成一团，不同群的样本混在一起，则很难分类；对具体对象做聚类分析的关键是选取合适的特征。特征选取得好，向量分布容易区分，选取得不好，向量分布很难分开。§4.1相关概念相关概念

两类模式分类的实例：一摊黑白围棋子选颜色作为特征进行分类，用“1”代表白，“0”代表黑，则很容易分类；选大小作为特征进行分类，则白子和黑子的特征相同，不能分类（把白子和黑子分开）。§4.1相关概念相关概念

特征选择的维数在特征选择中往往会选择一些多余的特征，它增加了维数，从而增加了聚类分析的复杂度，但对模式分类却没有提供多少有用的信息。在这种情况下，需要去掉相关程度过高的特征（进行降维处理）。降维方法：结论：若rij->1，则表明第i维特征与第j维特征所反映的特征规律接近，因此可以略去其中的一个特征，或将它们合并为一个特征，从而使维数降低一维数。§4.1相关概念相关概念

模式对象特征测量的数字化计算机只能处理离散的数值，因此根据识别对象的不同，要进行不同的数据化处理。连续量的量化：用连续量来度量的特性，如长度、重量、面积等等，仅需取其量化值；量级的数量化：度量时不需要详尽的数值，而是相应地划分成一些有次序的量化等级的值。病人的病例名义尺度：指定性的指标，即特征度量时没有数量关系，也没有明显的次序关系，如黑色和白色的关系，男性和女性的关系等，都可将它们分别用“0”和“1”来表示。超过2个状态时，可用多个数值表示。§4.1相关概念相关概念

按最小距离聚类的概念特征向量：标准模式：能代表模式类别的模式或模式集合。距离聚类：n个样本，m个类别，标准模式为Z1,Z2…Zm。聚类准则（最小距离准则）:

§4.1相关概念相关概念

第四章聚类分析第四章聚类分析

§4.1相关概念§4.2模式相似性测度与聚类准则§4.3聚类算法§4.4聚类结果评价目的：为了能将模式集划分成不同的类别，必须定义一种相似性的测度，来度量同一类样本间的类似性和不属于同一类样本间的差异性。欧氏距离马氏距离一般化的明氏距离（Minkowaki）汉明距离（Hamming）角度相似性函数§4.2模式相似性测度与聚类准则相似性测度

欧氏距离：量纲对分类的影响§4.2模式相似性测度与聚类准则相似性测度

当采用某一相似性测度如欧式距离对所有模式进行判别时，将距离数值计算出来，必须确定一个阈值，在小于此阈值时，判为同类，否则在大于它时，定为异类。怎样确定阈值才比较正确、合理，这就是聚类准则问题。一般有两种方式来确定这一准则试探方法聚类准则函数法§4.2模式相似性测度与聚类准则聚类准则

试探方法根据经验和直观，确定相似性度量中的阈值，或在确定这些阈值后试行分类，视结果对尚不够合理的阈值加以整理、修正，直至满意为止。这就是所谓经验法，或称为试探法。

§4.2模式相似性测度与聚类准则聚类准则

聚类准则函数法依据：由于聚类是将样本进行分类以使类别间可分离性为最大，因此聚类准则应是反映类别间相似性或分离性的函数；由于类别是由一个个样本组成的，因此一般来说类别的可分离性和样本的可分离性是直接相关的；可以定义聚类准则函数为模式样本集{x}和模式类别{Sj,j=1,2,…,c}的函数，从而使聚类分析转化为寻找准则函数极值的最优化问题。这是根据理论分析确定阈值的方法，它采用聚类准则函数进行分析。§4.2模式相似性测度与聚类准则聚类准则

一种聚类准则函数J的定义J代表了属于c个聚类类别的全部模式样本与其相应类别模式均值之间的误差平方和。对于不同的聚类形式，J值是不同的。目的：求取使J值达到最小的聚类形式。三种常见的准则函数：误差平方和准则与最小方差有关的准则散布准则§4.2模式相似性测度与聚类准则聚类准则

§4.2模式相似性测度与聚类准则聚类准则

1）误差平方和准则对于c类模式，准则函数为是类的均值向量当J最小时，认为聚类合理。在各类样本密集，类别间距明显时，最宜采用这一准则。§4.2模式相似性测度与聚类准则聚类准则

2）与最小方差有关的准则式中，

是类的样本数，是相似性算子：它是类中所有点间距离平方的均值，相似性算子

也可以由其它形式取代，如夹角余弦算子。这一准则也是以J最小作为判断聚类合理的依据。§4.2模式相似性测度与聚类准则聚类准则

3）散布准则若类的均值向量为：所有向量（不论它属于哪一类）的均值向量为其中，则类的散布矩阵为由此定义类内散布矩阵为§4.2模式相似性测度与聚类准则聚类准则

并定义类间散布矩阵为总体散布矩阵为可以推导出：§4.2模式相似性测度与聚类准则聚类准则

推导过程如下：§4.2模式相似性测度与聚类准则聚类准则

所以，§4.2模式相似性测度与聚类准则聚类准则

准则函数根据各种散布矩阵的“大小”来定义。度量矩阵“大小”可按矩阵迹（矩阵对角线元素之和）进行。例如当J最小时，也就是类内散步矩阵迹最小时，认为聚类合理。同样可以定义：当J最大时，即类间散布矩阵迹最大时，认为聚类合理。§4.1相关概念§4.2模式相似性测度与聚类准则§4.3聚类算法§4.4聚类结果评价第四章聚类分析

第四章聚类分析§4.3聚类算法聚类算法

在选择了某一聚类准则函数J之后，需要对模式总体进行分类，并计算J值。对于不同的阈值，各种可能的分类结果，都要计算J值，以求达到最优。这样做需要大量计算，实际上是不可能的。一般采取一些被认为是可以达到最优结果的聚类算法。一、基于试探的聚类搜索算法二、系统聚类法三、动态聚类法§4.3聚类算法聚类算法

1.按最近邻规则的简单试探法（简单搜索算法）算法：1.n个样本，任选一个作为第一个聚类中心z1，并确定一个非负阈值T。2.计算xi到zc距离,若则确定一个新的聚类中心，否则按最小距离聚类。3.依此方式继续搜索，直至得到n个样本的所有聚类中心。

讨论：这种方法的优点：计算简单，若模式样本的集合分布的先验知识已知，则可获得较好的聚类结果。§4.3聚类算法基于试探的聚类搜索算法

讨论（续）在实际中，对于高维模式样本很难获得准确的先验知识，因此只能选用不同的阈值和起始点来试探，因此这种方法在很大程度上依赖于以下因素：第一个聚类中心的位置待分类模式样本的排列次序距离阈值T的大小样本分布的几何性质§4.3聚类算法基于试探的聚类搜索算法

讨论（续）距离阈值T对聚类结果的影响§4.3聚类算法基于试探的聚类搜索算法

2.最大最小距离算法基本思想：以试探类间欧氏距离为最大作为预选出聚类中心的条件。算法：1.任选一模式样本作为第一聚类中心z1。2.确定离z1距离最远的样本作为第二聚类中z2。3.逐一计算各样本与z1z2间的距离，即§4.3聚类算法基于试探的聚类搜索算法

算法（续）3.计算： 上述条件不满足时则转5。4.有z3存在，计算若此最大值大于

则z4存在，否则聚类中心的搜寻计算结束。5.对所有模式样本，逐一计算它们到各聚类中心的距离，按最小距离法则进行聚类。§4.3聚类算法基于试探的聚类搜索算法

最大最小距离法-算法实例取:=0.5z1=x1

1(x1,x3,x4)z2=x6

2(x2,x6)z3=x73(x5,x7,x8,x9,x10)基于试探的聚类搜索算法

§4.3聚类算法一、基于试探的聚类搜索算法二、系统聚类法三、动态聚类法§4.3聚类算法聚类算法

基本思想：

先把每个样本各作为一类，然后将模式样本按距离准则逐步聚类，类别由多到少，直到获得合适的分类要求为止。§4.3聚类算法系统聚类法

算法：1.样本{x1,x2,…,xn}自成一类，即:

G1(0),G2(0),…Gn(0)，计算各类间距离矩阵:Dnn(0)2.求Dnn(0)中的最小元素，其对应的类别合并，建立新的分类:G1(1),G2(1),…Gn-1(1)。3.重复：求D(N)，建新的分类:G1(N+1),G2(N+1),…。当D(N)中的最小值大于阈值T或类别数等于K,迭代结束，输出分类结果。§4.3聚类算法系统聚类法

距离准则函数：

进行聚类合并的一个关键就是每次迭代中形成的聚类之间以及它们和样本之间距离的计算，采用不同的距离函数会得到不同的计算结果。§4.3聚类算法系统聚类法

主要的距离计算准则：1、最短距离法：两类中相距最近的两样本间的距离。2、最长距离法：两类中相距最远的两样本间的距离。3、中间距离法：最短距离和最长距离都有片面性，因此有时用中间距离。设ω1类与ω2

和ω3类间的最短距离为d12，最长距离为d13，ω2

和ω3类间的距离为d23，则中间距离为：推广形式：§4.3聚类算法系统聚类法

主要的距离计算准则：4、重心距离法：均值间的距离。5、类平均距离法：两类中各个元素两两之间的距离平方相加后取平均值§4.3聚类算法系统聚类法

系统聚类法—算法实例：例：如下图所示

用系统聚类法按最小距离分成二类。§4.3聚类算法系统聚类法—例子11、设全部样本分为6类，作距离矩阵D(0)G1（０）G２（０）G３（０）G４（０）G５（０）G６（０）G1（０）０G２（０）３０G３（０）1４０G４（０）７４８０G５（０）５２６２０G６（０）８５９1３０§4.3聚类算法系统聚类法—例子12、求最小元素：把G1,G3合并，G4,G6合并，作距离矩阵D(1)若合并的类数没有达到要求，转3。否则输出结果。G2G5G1,G3G4,G6G2(5)0G5(7)20G1,G3(2,1)350G4,G6(9,10)4270§4.3聚类算法系统聚类法—例子13、求最小元素：，G2,G5,(G4G6)合并。满足二类条件，分类结果为：1(G1,G3),2(G2,G4,G5,G6)树状图：X3=112X1=2X2=5X5=7X4=9X6=10§4.3聚类算法系统聚类法—例子1

模式样本的选取和初始聚类中心的确定：待识别分类的模式集合有时是一个很大的集合，如遥感数字影像等。而在采取聚类分析方法时，大都进行迭代计算，若将所有模式反复进行迭代计算，是不经济的。为此，需要进行抽样，在样本集合中先实施迭代，以确定各类中心，然后对模式集合的全体进行分类。另一方面，迭代计算的初始聚类中心的确定往往具有一定的盲目性，如何尽可能地减少这种盲目性的程度，也成为一个课题。下面以法国国家地理研究院自动分类软件中的一种作法为例，说明在解决上述两方面问题过程中的进展。§4.3聚类算法系统聚类法—例子2

模式样本的选取和初始聚类中心的确定：以二维遥感影像数据为例。在二维灰度平面角分线上选取50个点作为初始聚类中心（如图a），然后在此平面上7像元7像元的格网点（图b）上进行迭代聚类，迭代次数限值为10，最后的类别中心限值为20，迭代完毕，即转入对所有像元的分类。

图a图b§4.3聚类算法系统聚类法—例子2

可以将法国的方法加以改善，即首先确定二维分布范围，这是比较容易做到的（如图c）。然后在这一分布空间内等间隔地确定一些点（图c中处）作为初始聚类中心，开始对某一确定的格网上的点进行迭代运算。

图c§4.3聚类算法系统聚类法—例子2画出给定迭代次数为n的系统聚类法的算法流程框图。对如下5个6维模式样本，用中间和重心距离两种聚类准则进行系统聚类分析：

x1:0,1,3,1,3,4 x2:3,3,3,1,2,1 x3:1,0,0,0,1,1 x4:2,1,0,2,2,1 x5:0,0,1,0,1,0§4.3聚类算法作业作业提交Deadline：2015年5月4日一、基于试探的聚类搜索算法二、系统聚类法三、动态聚类法§4.3聚类算法聚类算法基本思想:首先选择若干个样本点作为聚类中心，再按某种聚类准则（通常采用最小距离准则）使样本点向各中心聚集，从而得到初始聚类；然后判断初始分类是否合理，若不合理，则修改分类；如此反复进行修改聚类的迭代算法，直至合理为止。 1、K-均值算法 2、ISODATA算法（迭代自组织数据分析算法）§4.3聚类算法动态聚类法思想：

基于使聚类性能指标最小化，所用的聚类准则函数是聚类集中每一个样本点到该类中心的距离平方之和，并使其最小化。§4.3聚类算法K-均值算法算法：（1）任选K个初始聚类中心。一般以开头K个样本作为初始中心。（2）将模式样本集的每一样本按最小距离原则分配给K个聚类中心，即在第m次迭代时，若:则，表示第m次迭代时，以第j个聚类中心为代表的聚类域。§4.3聚类算法K-均值算法算法：（3）由步骤（2），计算新的聚类中心，即:

式中Ni为第i个聚类域中的样本个数。其均值向量作为新的聚类中心，因为这样可以使误差平方和准则函数:达到最小值。（4）若，算法收敛，计算完毕。否则返回到步骤（2），进行下一次迭代。§4.3聚类算法K-均值算法例：已知有20个样本，每个样本有2个特征，数据分布如下图：样本序号x1x2x3x4x5x6x7x8x9x10特征x10101212367特征x20011122266x11x12x13x14x15x16x17x18x19x2086789789896777788899§4.3聚类算法K-均值算法—例子§4.3聚类算法K-均值算法—例子第一步：令K=2，选初始聚类中心为§4.3聚类算法K-均值算法—例子第二步：§4.3聚类算法K-均值算法—例子第三步：根据新分成的两类建立新的聚类中心第四步：判断是否终止？

因为，

所以，转第二步。第二步：重新计算到z1(2),z2(2)的距离，

把它们归为最近聚类中心，重新分为两类。§4.3聚类算法K-均值算法—例子第三步，更新聚类中心§4.3聚类算法K-均值算法—例子第四步，判断是否终止？第二步，第三步，更新聚类中心§4.3聚类算法K-均值算法—例子讨论K-均值算法的结果受如下选择的影响：所选聚类的数目模式样本的几何性质聚类中心的初始分布读入次序在实际应用中，需要试探不同的K值和选择不同的聚类中心的起始值。如果模式样本可以形成若干个相距较远的小块孤立的区域分布，一般都能得到较好的收敛效果。K-均值算法比较适合于分类数目已知的情况。§4.3聚类算法K-均值算法

（选k=2, z1(1)=x1, z2(1)=x10,

用K-均值算法 进行聚类分析）§4.3聚类算法作业作业提交Deadline：2015年5月4日编写K-均值聚类算法程序，对下图所示数据进行聚类分析（选k=2）：§4.3聚类算法编程练习作业提交Deadline：2015年5月4日ISODATA（IterativeSelforganizingDataAnalysisTechniquesAlgorithm）-迭代自组织数据分析算法

ISODATA算法是在k-均值算法的基础上，增加对聚类结果的“合并”和“分裂”两个操作，并设定算法运行控制参数的一种聚类算法。迭代次数会影响最终结果，迭代参数选择很重要。“合并”操作：当聚类结果某一类中样本数太少，或两个类间的距离太近时，进行合并。“分裂”操作：当聚类结果某一类中样本某个特征类内方差太大，将该类进行分裂§4.3聚类算法ISODATA算法与K-均值算法的比较K-均值算法通常适合于分类数目已知的聚类，而ISODATA算法则更加灵活；从算法角度看，ISODATA算法与K-均值算法相似，聚类中心都是通过样本均值的迭代运算来决定的；ISODATA算法加入了一些试探步骤，并且可以结合人机交互的结构，使其能利用中间结果所取得的经验更好地进行分类。§4.3聚类算法ISODATA算法基本步骤（1） 选择某些初始值。可选不同的指标，也可在迭代过程中人为修改，以将N个模式样本按指标分配到各个聚类中心中去。（2） 计算各类中诸样本的距离指标函数。（3）~（5）按给定的要求，将前一次获得的聚类集进行分裂和合并处理（（4）为分裂处理，（5）为合并处理），从而获得新的聚类中心。（6） 重新进行迭代运算，计算各项指标，判断聚类结果是否符合要求。经过多次迭代后，若结果收敛，则运算结束。§4.3聚类算法ISODATA算法详细步骤：该算法需要确定并在计算中可以调整的参数有：K:所要求的聚类中心数。:一个类别至少应具有的样本数目。:一个类别样本标准差阈值。:聚类中心之间距离的阈值，即归并系数。L:在一次迭代中可以归并的类别的最多对数。I:允许迭代的最多次数。第一步：对于N个模式样本的集合，确定C个初始聚类中心，C不一定等于K。这些聚类中心可为模式集合中的任意样本。第二步：确定上述六个参数，即。

§4.3聚类算法ISODATA算法第三步：将N个样本按最小距离分类，即若

第四步：若对于某一聚类域fj，其样本数目则取消该子集fj和Zj，并且C=C-1，即类别数减少1。第五步：修正各聚类中心值：第六步：对每一聚类域fj，计算其所有样本到其聚类中心的距离的平均值。§4.3聚类算法ISODATA算法第七步：计算所有样本到其相应聚类中心的距离的平均值。第八步：①若迭代次数达到I次，置，转入第十二步，运算结束；②若，即聚类中心数目等于或不到规定数目的二分之一，则转入第九步，以对现有类别进行分裂；③若迭代次数为偶次，或，不进行分裂处理，跳到第十二步，否则进行分裂处理。§4.3聚类算法ISODATA算法第九步：计算每一类别中样本与聚类中心距离的标准差向量：

其中每一分量为：

n为模式样本的维数，xil是fj中第l个样本的第i分量，zij是zj的第i分量。第十步：对每一标准差向量，求其最大分量，以表示，用S记下它是第几分量。§4.3聚类算法ISODATA算法第十一步：在最大分量集中，若有并且满足下列条件之一：和，即该类中样本到聚类中心的平均

距离大于总体平均距离且该类样本总数超过规定数目二倍。则将分裂成两个新的聚类中心和，去掉，且令C=C+1。的确定方法是对应于的zj的分量即第S分量加上,其它分量不变，构成。第S分量减去，其它分量不变，构成。分裂完毕，转入第三步。如果没有可分裂的类别，则继续进行。§4.3聚类算法ISODATA算法第十三步：将每一值与值比较，凡有，均取出以组成一个集合。

第十二步：计算每两个聚类中心之间的距离：这里：§4.3聚类算法ISODATA算法第十四步：从开始，逐一合并的类别和，每一类别只能归并一次，合并后新的类别以新的聚类中心作为标志：第十五步：如果是最后一次迭代计算（即第I次），

算法结束。否则，如果需要改变参数则转入第二步，

不需要改变参数则转入第三步。§4.3聚类算法ISODATA算法例：对如图模 式样本用

ISODATA

算法进行 分类§4.3聚类算法ISODATA算法—例子第一步，取初值C=1，令。第二步，确定参数K=2，

这是在假设没有样本先验知识可利用的情况下任意取值确定的。在迭代过程中，这些参数还可以视情况加以修正。第三步，因只一个聚类中心，无从分析所谓最小距离，故第四步，因，无子集可取消。第五步，修改聚类中心，第六步，计算。§4.3聚类算法ISODATA算法—例子第七步，计算:

第十一步，因，且，可将分裂成两个新的聚类中心。设，则第八步，由于不是最后一次迭代，且，故进入第九步。第九步，求中的标准差向量。第十步，中最大分量为1.99，故。

为方便起见，将和改名为和，C亦增加1，然后返回第三步。§4.3聚类算法ISODATA算法—例子第六步，计算:第三步，计算每一样本到和的距离，按最小距离进行分类，得到两个聚类域：第四步，因和均大于，故无可取消之类别。第五步，修改聚类中心:§4.3聚类算法ISODATA算法—例子第十四步，根据第十三步比较的情况，无可进行合并的类别对。第七步，计算:第八步，因为这是偶数次迭代，满足第八步第③项条件，故进入第十二步第十二步，计算聚类中心之间的距离。第十三步，比较与，有。§4.3聚类算法ISODATA算法—例子第三—第七步，与前一次迭代计算结果相同。第八步，条件均不能满足，故继续下一步。第十五步，因为这还不是最后一次迭代，需要判断是否需要修改给定的参数。由于：①已获得所要求的聚类数目；②聚类之间的分离度（两聚类中心之间的距离）大于类别之间样本分离的标准差③每一聚类子集的样本数目都具有样本总数中的足够大的百分比。因此，可以认为两聚类中心能代表各子集样本。返回第三步。第九步，计算