《模式识别课件第五章聚类分析.ppt》由会员分享，可在线阅读，更多相关《模式识别课件第五章聚类分析.ppt（130页珍藏版）》请在三一办公上搜索。
1、在已知类别的样本集基础上，用确定的或统计的判别函数对模式进行分类，设计分类器，这些已知的样本集称为训练集。根据判读好的训练集解决分类问题，称为有人管理或有教师的分类法。,第五章 聚类分析,第五章 聚类分析,没有训练集的情况下的样本分类问题，所选用的样本是预先不知其所属的类别，需要根据样本间的距离或相似性的程度自动地进行分类。这种无人参预（或没有教师的）识别问题，称为聚类或无人管理的分类。,聚类分析方法是决定描述一个经验数据集的结构类型的一种非参数方法。相似的数据被集中在一起，从数据集中分离出来，包含在特征空间中的一个模式集，其模式的密度比起周围区域中的密度大，就为一个聚类。,第五章 聚类分析,
2、聚类原则：根据样本集，找出各点内在的相似性进行分类，相似的分为一类。直观的相似性：从几何距离考虑，设阈值T，它是相似性度量的标准，靠经验确定，对分类影响很大。可用于粗分。样本集群性（紧致性）：同一类的应该群集，不同类的应该远离。,第五章 聚类分析,特征空间量纲标尺的选择：量纲选择不同，分类也有差异。,第五章 聚类分析,为了克服这个缺点，常使特征数据标准化，使它与变量量纲标尺没有关系。,第五章 聚类分析,5.1相似性度量和聚类准则,一般用归并相似的模式和分开不相似的模式以形成聚类。相似性归并是聚类最普通的形式。各式各样的相似性和距离度量已经作为特征空间中模式样本的聚类准则。,第五章 聚类分析,5
3、.1.1相似性度量(Similarity measure),相似性度量将建立一个把模式分到一聚类中心域的原则。欧氏距离(Euclidean distance)(常用)对两个样本xi和xj，其欧氏距离定义为,若dij小，相似性大。,5.1相似性度量和聚类准则,加权欧氏距离也是一种常用的相似性度量。,wk是系数，其重要，wk大；次要的，wk小。,欧氏距离(Euclidean distance)(常用),5.1.1相似性度量,马氏距离(Mahalanobis distance)(不常用),x是待识别样本，m是均值向量，是协方差矩阵。若为单位阵，则马氏距离与欧氏距离相似。马氏距离的优点是排除了模式样本
4、之间的相关性的影响。例如取一个模式特征向量，可能其中九个分量是反映同一特征A，而只有一个分量反映另一特征B，这时如用欧氏距离计算，主要反映了特征A，而用马氏距离则可避免这个缺点。,5.1.1相似性度量,明氏距离(Minkowsky distance),m=2时为欧氏距离；m=1为绝对距离(用绝对值)；dij=|xi1xj1|+|xidxjd|相似性度量不一定只限于距离，可以是下面的形式：,5.1.1相似性度量,角度相似性度量函数,sij是向量xi和xj之间夹角的余弦，当xi和xj相对于原点是同一方向时，函数值最大。当聚类区域有扇形分布时往往采用这种相似性度量。如图5.1所示。,5.1.1相似性
5、度量,0,图 5.1相似性度量的说明,从图中可以看到，由于s(x，x1)比s(x，x2)大，因此x与x1比与x2更相似。,5.1.1相似性度量,距离和角度相似性函数作为相似性的测度各有其局限性。,距离对于坐标系的旋转和位移是不变的，对于放大缩小并不具有不变性的性质。角度相似性函数对于坐标系的旋转放大缩小是不变的，但对于位移不具有不变性的性质。用角度相似性函数作为相似性的测度还有一个缺点，当本属不同类的样本分布在从模式空间原点出发的一条直线上时，所有样本之间角度相似性函数几乎都等于l，造成归为一类的错误。,5.1.1相似性度量,Tanimoto 度量(常用),若模式向量取二进制值0，1时有特殊意
6、义，样本x具有第k个特征，xiTxj是两者共同的特征数；,是xi和xj各自具有的特征数的几何均值。这种度量称为Tanimoto 度量。,5.1.1相似性度量,Tanimoto 度量(常用),适用于疾病诊断、动植物分类和情报检索等方面。上述介绍的相似性量度不是仅有的形式，而是属于比较简单和典型的。,5.1.1相似性度量,距离函数应满足三个条件：,非负性：对于一切i，j，dij(xi，xj)0，当xi=xj时，等号成立。对称性：对于一切i，j，dij(xi，xj)=dji(xj，xi)，即距离是标量而不是向量。三角不等式：dij(xi，xj)djk(xj，xk)+dkj(xk，xj)，即相当于三角
7、形两边之和必大于第三边。,5.1.1相似性度量,5.1.2 聚类准则,假定有一组样本x1，x2，xN，要求对其进行确切分成1，2，c类。同一类里的样本比不同类里的样本相似性高一些，于是可存在多种分类，到底何种分类方法最好？需要定义一个准则函数，则聚类问题就变成对准则函数求极值的问题。,5.1相似性度量和聚类准则,试探方式：,针对具体的实际问题，定义一种相似性度量的阈值T，按最近邻原则分类，须不断检验、修正阈值T。这种方法的误判率受T及起始样本影响。,5.1.2 聚类准则,误差平方和准则(最小方差划分)(常用),误差平方和准则是聚类问题中最简单而又广泛应用的准则。准则函数为,c是类别数，Xi是第
8、i类聚类中心域的样本集合，mi是第i类均值向量(类中心),Ni是Xi中的样本数。使J最小化的聚类就是最合理的聚类。,5.1.2 聚类准则,误差平方和准则(最小方差划分),此种准则函数适用于集群性好，且各类容积相近情况。如果类间距离小，容积相差悬殊，容易发生错误。,5.1.2 聚类准则,误差平方和准则(最小方差划分),如图(a)中所示的模式分类，使用这种准则进行聚类可获得最好的效果。,5.1.2 聚类准则,误差平方和准则(最小方差划分),而如图(b)中的模式分布，使用这种准则得到的效果就不理想。,5.1.2 聚类准则,误差平方和准则(最小方差划分),当各类中的样本数相差很大而类间距离较小时，有可
9、能把样本数多的一类一拆为二，这样聚类的结果，误差平方和准则函数J比保持完整时为小(如图5.3所示)。因此有可能将1和2分错，发生错误聚类。,5.1.2 聚类准则,误差平方和准则(最小方差划分),图5.3 把大群拆开的问题(b)的误差平方和小于(a)的误差平方和,5.1.2 聚类准则,与最小方差有关的准则,经过简单的代数运算，可以将上述J的表达式中均值向量mi消去，得到另一种准则函数表示形式,式中c是聚类数；Ni是第i个聚类域中的样本数；Si是相似性算子。,它是第i类点间距离平方的平均，是以欧氏距离作为相似性度量。,5.1.2 聚类准则,与最小方差有关的准则,若以非尺寸的相似性函数s(x，x)来
10、取代相似性算子Si中的欧氏距离,并把它代入准则函数J的表示式中，可得到准则函数的另一种表示形式。,5.1.2 聚类准则,散布准则（离散度准则）,用多元判别式分析中的散布矩阵可以推出另一种准则函数。第i类的均值向量(第i类的中心),总平均向量(总体中心),5.1.2 聚类准则,散布准则（离散度准则）,第i类的散布矩阵,类内散布矩阵,类间散布矩阵,5.1.2 聚类准则,散布准则(离散度准则),总散布矩阵,根据上述定义可以证明，总散布矩阵等于类内散布矩阵与类间散布矩阵之和。即：ST=SW+SB,5.1.2 聚类准则,证明：ST=SW+SB,5.1.2 聚类准则,5.1.2 聚类准则,散布准则(离散度
11、准则),总散布矩阵与如何划分类别无关，仅与全部样本有关。但类内和类间散布矩阵都与类别划分有关。这两矩阵有一互补关系，因此使类内散布矩阵最小就是使类间散布矩阵最大。由于度量矩阵大小的方法有“迹”和行列式，故利用散布矩阵提出以下准则：,5.1.2 聚类准则,迹准则,迹是散布矩阵大小的最简单的度量，迹等于散布矩阵的对角线元素之和，最小化SW的迹准则,使其(J)取最小值，是一种最优化的准则。,5.1.2 聚类准则,迹准则,或最大化SB的迹作为另一种最优化的准则。,5.1.2 聚类准则,行列式准则,散布矩阵的行列式可作为散布矩阵的另一种大小度量。在类数小于或等于维数时，SB是奇异的，所以不能选择SB的行
12、列式作为准则函数，一般选择SW的行列式，行列式准则函数为,这是因为矩阵行列式的大小正比于主轴方向方差的乘积。,5.1.2 聚类准则,5.2 聚 类 算 法,按最近邻原则试探算法 特点：简单、快速。缺点：粗糙。假设有N个样本x1，x2，xN，x在d维特征空间，类别数未知。,第五章 聚类分析,应用于无训练样本集，无教师（或无人）参与分类过程。,算法步骤(依据试探性准则),选定一个非负的阈值T。在x1，x2，xN中任取xi，i=1，2，N，令任一个样本xi为第一个聚类中心z1，即z1=xi，例如，可选z1=x1作为第一个聚类中心。取x2计算(根据具体问题选定计算方法),5.2.1按最近邻原则试探算法
13、,算法步骤(依据试探性准则),判断：d21T，则建立一个新的聚类中心z2，z2=x2。d21T，则x2X1，X1是以z1为聚类中心的模式的集合。,例如，选定欧氏距离作为相似性度量，计算x2到z1的距离,5.2.1按最近邻原则试探算法,算法步骤(依据试探性准则),取下一个样本xj，xj是余下的样本中的任一个，计算dj1=|xjz1|，dj2=|xjz2|，dj1=|xjzk|，,接着分别计算x3到z1和z2的距离得d31和d32，如果判断d31T，d32T，则再建立一个新的聚类中心z3，z3=x3。d31d32T，则x3X1，否则x3X2，X2是以z2为聚类中心的模式的集合。即将x3分到最近的聚
14、类中心的域中。,5.2.1按最近邻原则试探算法,算法步骤(依据试探性准则),所有样本全部处理完毕否？没有处理完，转4。处理完，算法结束。,若,否则，xj属于离它最近的聚类中心所属的类。,判断：,5.2.1按最近邻原则试探算法,算法讨论,此算法的聚类结果受阈值T的大小、初始值z1的选择、样本的顺序及数据的几何特性等四个因素的影响。其中T和z1的影响大一些。如图5.4所示。,(a),(b),T3,(c),图 5.4按最近邻原则试探算法中阈值和起始点的影响,T2,T2,T1,5.2.1按最近邻原则试探算法,改进措施：,具有待分类样本集的几何分布的先验知识，用来指导选择T和z1，可以改善聚类结果(在d
15、较小时，如d=1，2，3等)。在d较大的高维情况，要进行反复验算、修正T和z1(验算采用误差平方和等准则)。否则，此算法只能用于粗糙分类，进行预分。,5.2.1按最近邻原则试探算法,5.2.2 小中取大距离算法(最大最小距离算法),此算法以欧氏距离为基础，选集合中最不相似(距离最大)的点或样本作为各类的聚类中心。举例说明如图所示样本的此聚类算法步骤：,5.2.2 小中取大距离算法,如图所示模式：任选一模式样本x1，令z1=x1为第一个聚类中心。,5.2.2 小中取大距离算法,在图(b)中由z1标志，图中箭头上的数字标志了聚类中心赋值的步骤。,x1x2x3x4x5x6x7x8x9x10,z1,(
16、1),(b)样本和种类表,计算欧氏距离di1=|xiz1|，i=1，2，N。,5.2.2 小中取大距离算法,则令z2=xj为新的聚类中心。,在此例中 最大，故z2=x6。,判断：,若,5.2.2 小中取大距离算法,在图(b)中由z2标志,x1x2x3x4x5x6x7x8x9x10,z1z2z3,(1),(2),(b)样本和种类表,5.2.2 小中取大距离算法,找新的聚类中心设当前已有z1，z2，zk个聚类中心，分别计算其余样本到各聚类中心的距离：,di1=|xiz1|，di2=|xiz2|，dik=|xizk|，i=1，2，N,5.2.2 小中取大距离算法,取，m=1，2，k。取，i=1，2，
17、N。,若djmmax|zizl|，i，l=1，2，k。则令zk+1=xj。,此例中，z3=x7，。,是系数，。,5.2.2 小中取大距离算法,在图(b)中由z3标志，图中箭头上的数字标志了聚类中心赋值的步骤。,5.2.2 小中取大距离算法,若取得大，划分的类少；若取得小，划分的类多。一般根据经验试探选。每确定一个新的聚类中心后，重复3。若djmmax|zizl|，i，l=1，2，k。则寻找聚类中心的工作结束。,5.2.2 小中取大距离算法,计算距离后分类 dil=|xixl|，i=1，2，N；l=1，2，k。根据最近邻原则分类。本例中，X1=x1，x3，x4，X2=x2，x6，X3=x5，x7
18、，x8，x9，x10。,5.2.2 小中取大距离算法,对每一聚类域，取样本的平均作为新的聚类中心。,5.2.2 小中取大距离算法,算法讨论：本算法相当于最近邻试探法的改进，但仍受到z1的选择、的大小的影响，对于几何分布集群性比较好的分类问题，效果较好。,5.2.2 小中取大距离算法,分级聚类方法(层次聚类法),由于聚类分析只是把N个没有类别标签的样本分成一些合理的类，在极端的情况下，最多可分为N类，最少只有一个类，因此可以把问题看成是将N个样本划分成c个类的划分序列。第一个划分是把样本分成N个类，每类包含一个样本；第二个划分是把样本分成N1个类；下一个划分是把样本分成N2个类等等，直到第N个划
19、分时，把样本仅分成一个类。,5.2.3分级聚类方法,如果类数c=NK+l，则称这个划分处于K水平。例如1水平就相当于分成N类，N水平就相当于把所有样本归为1类。任何两个样本xi和xj总会在某一水平被分为同一类。,5.2.3分级聚类方法,分级聚类就是这样一种划分序列。这种划分序列具有如下的性质：只要在K水平时样本被归入同一类后，在进行更高水平的划分时，它们也永远属于同一类。生物分类就是分级聚类的一个例子。先是把许多个体集合成种，然后种集合成类，类集合成族等等。如生物界=动物，门=脊索动物类，纲=脊椎动物，类=鱼类，子类=鳍类，目=鲑鱼类，科=鲑鱼，等等。,5.2.3分级聚类方法,分级聚类方法的最
20、自然的表示就是树。,5.2.3分级聚类方法,另一种表达分级聚类的方法是集合，每个层次上的类都可能含有子类集合，如图所示。,纯符号的表示方法，如x1，x2，x3，x4，x5，x6，x7，x8。这些方法虽能够表达层次关系，但无法定量地体现相似性。树图是较好的方法。,5.2.3分级聚类方法,层次聚类可以通过合并(agglomerative)和分裂(divisive)两种方法实现。合并（自低向上）时，每个样本各成一类，通过合并不同的类，减少类别数目。分裂（自顶向下）时，所有样本先归入一类，通过后续分裂，增加类别数目。下面主要介绍合并的方法。,5.2.3分级聚类方法,基于合并的分级聚类方法,对于N个d维
21、未知样本，其算法步骤为：,设初始的类别数，X=xi，i=1，2，N。,计算类间相似性度量距离矩阵D0，D0是xi间的两两距离矩阵。,找出最相似的两类(相似性度量距离最小)，假设为Xh，Xk，将其合并，Xj=Xh，Xk。,5.2.3分级聚类方法,计算合并后的类别之间的相似性程度的度量距离矩阵Dl。,若给定的类别数是c，算法结束。,，算法结束。,若没有给定类别数c，则,设定阈值T，当两类之间最小距离T时，算法结束。,-基于合并的分级聚类方法,5.2.3分级聚类方法,讨论类间相似性度量的方法，假定每个样本之间用欧氏距离：最近距离 属于近邻算法，适用于类间分布较散，链状聚合。,如果Xj=Xh，Xk，即
22、Xj是由Xh、Xk合并的。,-基于合并的分级聚类方法,5.2.3分级聚类方法,假设有三种如图5.7所示的两维点集(a)、(b)、(c)。,在用最近距离作为相似性度量进行聚类时，若类别数等于2，则各点集的相应聚类结果如图5.8所示。,-基于合并的分级聚类方法,5.2.3分级聚类方法,-基于合并的分级聚类方法,5.2.3分级聚类方法,-基于合并的分级聚类方法,5.2.3分级聚类方法,-基于合并的分级聚类方法,5.2.3分级聚类方法,图5.7(a)和(b)点集的唯一差别是(b)中出现了两个干扰点。从图5.8(b)中可见，这种相似性度量的缺点是只要在两个各自密集的点集之间存在一些位置互相靠近的点的路径
23、，那么就很可能会把两个密集的点集(本应分属于两类的点集)聚集成一个类。,-基于合并的分级聚类方法,5.2.3分级聚类方法,从图可见，当最终类别数为1时，以最近距离作为相似性度量进行样本点聚类的过程就是一棵最小生成树形成的过程。因此这是一种最小生成树算法。如果给出了最小生成树，可以根据它得到最近邻的聚类结果。只要把最小生成树中长度(距离)最大的一支去掉就得到2类的聚类结果，去掉第二长的分支，数据就分为3类，如此继续下去，就导出了基于分裂的层次聚类方法。,-基于合并的分级聚类方法,5.2.3分级聚类方法,最远距离属于近邻算法，适用于团状集群。,取其中dmax最大的一对合并。如Xj=Xh，Xk，dm
24、ax(Xi，Xj)=maxdmax(Xi，Xh)，dmax(Xi，Xk),-基于合并的分级聚类方法,5.2.3分级聚类方法,在用最远距离作为相似性度量时，可以把聚类算法看成是产生一个图，图中同一个类的结点都是用棱线联结起来的。用图论的术语来说就是每个类构成一个完备子图。两个类之间的距离现在是由这两个类中相距最远的结点来确定的，对于图5.7的三种点集，当类别数等于2时，其相应的聚类结果见图5.9。,-基于合并的分级聚类方法,5.2.3分级聚类方法,-基于合并的分级聚类方法,5.2.3分级聚类方法,从图(b)可见，它防止了两个密集点集通过某个路径聚为一类的可能性。,-基于合并的分级聚类方法,5.2
25、.3分级聚类方法,图(c)的结果则说明了这种相似性度量不能检出具有长条形状的聚类。,显然，这种度量将使个别的远离点对聚类结果产生十分大的影响。,-基于合并的分级聚类方法,5.2.3分级聚类方法,均值距离,这种相似性度量的效果介于上述两者之间。中心距离,适用于球状、近似球状分布。,-基于合并的分级聚类方法,5.2.3分级聚类方法,例5.1：c=2，N=5，n=2，X=x1=(0,1)T，x2=(7,5)T，x3=(2,2)T，x4=(1,1)T，x5=(5,5)T。试用分级聚类方法进行分类。样本集如图5.10所示。,-基于合并的分级聚类方法,5.2.3分级聚类方法,解：采用。,l=2，dmean
26、(X2，X5)最小。则X2=X2，X5=x2，x5，算法结束。,，l=0，dmean=(X1，X4)最小，X1=X1，X4=x1，x4，,X1=x1，x3，x4，X2=x2，x5。,-基于合并的分级聚类方法,5.2.3分级聚类方法,算法讨论：,适用于样本总数不太多情况。若类别数c未知，受阈值T影响。采用不同相似性度量，会影响聚类结果。实际上，可以多选几种距离度量来试验。,-基于合并的分级聚类方法,5.2.3分级聚类方法,5.2.4 k-均值算法和ISODATA算法(动态聚类方法),动态聚类方法是一种普遍采用的方法，它具有以下三个要点：选定某种距离度量作为样本间的相似性度量。确定某个评价聚类结果
27、质量的准则函数。给定某个初始分类，然后用迭代算法找出使准则函数取极值的最好聚类结果。先讨论在误差平方和准则基础上的k-均值算法，然后结合对这算法的分析给出一些其它的动态聚类算法。,5.2.4 k-均值算法和ISODATA算法,k-均值算法使聚类域中所有样本到聚类中心的距离平方和最小，这是在误差平方和准则的基础上得来的。k是类别数，已知或任选。相似性度量采用欧氏距离。分类准则采用平方误差和准则。,一、k-(或c)均值算法(k-mean Algorithm),准则函数：,zi是第i类的聚类中心。样本集X=x1，x2，xNxi是d维特征向量。,5.2.4 k-均值算法和ISODATA算法,算法步骤：
28、,任意选择k个初始聚类中心，z1(1)，z2(1)，zk(1)作为初始聚类中心。第l次迭代，将待分类的N个样本按最小距离原则分配到k个聚类中，对待识别样本x，若|x-zj(l)|x-zi(l)|，式中j=1，2，k，ij，则xXj(l)，Xi(l)是聚类中心为zi(l)的样本集。,5.2.4 k-均值算法和ISODATA算法,算法步骤：,由第2步结果，计算新的聚类中心。,，i=1，2，k,5.2.4 k-均值算法和ISODATA算法,算法步骤：,若zi(l+1)=zi(l)，i=1，2，k，算法收敛，则检验J是否最小，并结束。若zi(l+1)zi(l)，令l=l+1，转2，经过多次迭代M次(自
29、己设定)，停机，修改参数，重新计算或取最小J情况下的聚类输出。,5.2.4 k-均值算法和ISODATA算法,算法讨论,收敛问题尚无证明收敛问题与几何分布有关，样本各类有类超球体分布，各类容积相近，易收敛；收敛与否，与k=1时的z1zk的选择有关，选的好，有可能收敛，否则不然，故要试探。初始聚类中心z(1)的选择凭先验知识，将样本集大致分类，取代表点。将全部样本人为地分k类，取代表点(均值)。,5.2.4 k-均值算法和ISODATA算法,算法讨论,密度法：以每个样本为中心，定义某个正数r为半径，在球内落入的点的个数作为密度，取最大密度点为z1，然后再找出与z1的距离r的次大密度做新的聚类中心
30、，依次选定。选择给定样本集的前k个样本做聚类中心。从(k-1)聚类划分解中，产生k类划分代表点。k的确定可采用试探法，令k=2，3，4，对应算出准则函数J做曲线，一般kJ，k=N，J=0。,5.2.4 k-均值算法和ISODATA算法,算法讨论,当J下降变慢时，对应的k较为合适，如果分不清J下降快慢的界限，则应试探进行。,如图5.11所示，从5 6下降较小，认为5较合适。故k=5。,5.2.4 k-均值算法和ISODATA算法,例5.2 如图5.12给出20个二维的样本，用k均值算法进行聚类。,5.2.4 k-均值算法和ISODATA算法,解：令k=2，选择z1(1)=x1=(0,0)T，z2
31、(1)=x2(1,0)T。因为|x1-z1(1)|x1-zi(1)|和|x3-z1(1)|x1-zi(1)|，i=2，所以X1(1)=x1，x3，N1=2。同样剩余的样本接近于z2(1)，因此，X2(1)=x2，x4，x5，x20，N2=18。更新聚类中心,例5.2 如图5.12给出20个二维的样本，用k均值算法进行聚类。,5.2.4 k-均值算法和ISODATA算法,例5.2 如图5.12给出20个二维的样本，用k均值算法进行聚类。,5.2.4 k-均值算法和ISODATA算法,因为zj(2)zj(1)，j=1，2，转到第二步。因为|xl-z1(2)|xl z2(2)|，l=1，2，8，所以
32、X1(2)=x1，x2，x3,，x8，N1=8。又因为|xl z2(2)|xl z1(1)|，l=9，10，11，20，因此，X2(2)=x9，x10，x11，x20，N2=12。更新聚类中心,例5.2 如图5.12给出20个二维的样本，用k均值算法进行聚类。,5.2.4 k-均值算法和ISODATA算法,例5.2 如图5.12给出20个二维的样本，用k均值算法进行聚类。,5.2.4 k-均值算法和ISODATA算法,因为zj(3)zj(2)，j=1，2，转到第二步。与前面一次迭代产生同样的结果，X1(4)=X1(3)，X2(4)=X2(3)。也产生同样的结果。因为zj(4)=zj(3)，j=
33、1，2，故算法收敛。产生的聚类中心为,例5.2 如图5.12给出20个二维的样本，用k均值算法进行聚类。,5.2.4 k-均值算法和ISODATA算法,结果与观察给定模式所得的结果是相符的。,例5.2 如图5.12给出20个二维的样本，用k均值算法进行聚类。,5.2.4 k-均值算法和ISODATA算法,二、ISODATA算法,ISODATA算法(Iterative Self-organizing Data Analysis Techniques A迭代自组织数据分析技术)在k-均值算法基础上，在迭代过程中增加了某种产生和消除某些类别的方法，具有自动合并和分裂类，自动寻找类别数k的功能。在每一
34、次迭代时，首先，在不改变类别数目的前提下来改变分类，然后，将样本平均矢量之差小于某一预定阈值的每一类别对合并起来，或根据样本协方差矩阵来决定其分裂与否，一次一次地迭代，并不断地进行合并和分开，这种算法具有人机交互和启发式的特点。,5.2.4 k-均值算法和ISODATA算法,算法参数,k 要找的聚类中心数；N 每一类中至少应具有的样本个数（少于此值的样本点集去掉）；s 类内的样本标准差阈值（判别类是否太大，若太大分2类），取总体分布各个特征分量轴上标准差i，取其一部分用i表示，01，i=1，2，N；,5.2.4 k-均值算法和ISODATA算法,算法参数,L 一次迭代运算中可合并的最多对数（一
35、般取一对）；I 允许迭代的次数（相当于k-均值算法中的M）；c 两类中心距的最小距离（c，可合并）。,5.2.4 k-均值算法和ISODATA算法,算法步骤,基本步骤：初始化，任意选定c个聚类中心，z1(1)，z2(1)，zc(1)，定义算法参数，k，N，s，c，L，I。分配N个样本到c类中，按最近邻原则计算，若|x-zi|x-zj|，i=1，2，c，ij，则xXi，其中Xi表示分到聚类中心zi的样本子集，Ni为Xi中的样本数。若对任意的i，NiN，则去除Xi，并使c=c-1，即将样本数比N少的样本子集去除。,5.2.4 k-均值算法和ISODATA算法,算法步骤,以下三步计算距离：修正聚类中
36、心zi，,，i=1，2，c,计算Xi中样本与其对应的中心的平均距离,，i=1，2，c,5.2.4 k-均值算法和ISODATA算法,算法步骤,计算总体的平均距离,其中N为样本集中的样本总数。判断：,若是最后一次迭代，l=I，置c=0，转步算法结束。,若，直接转到第步，分裂类操作。,5.2.4 k-均值算法和ISODATA算法,算法步骤,若c2k，直接转到步，合并类操作。若、类不满足，继续。,计算标准差ij,其中d是样本模式的维数，xkj是Xj中第k个样本的第j个分量，zij是zi的第j个分量。,j=1，2，d；i=1，2，c,的每个分量表示Xi中样本沿主要坐标轴的标准差。,5.2.4 k-均值
37、算法和ISODATA算法,算法步骤,如果imaxs，i=1，2，c，同时满足以下条件之一：,找出 中的最大分量，i=1，2，c。,且(样本数不能太小)；,则将Xi分成两类，出现两个新的聚类中心 和，删去，并使c=c+1。,5.2.4 k-均值算法和ISODATA算法,算法步骤,对应于 的 的分量上加上一个给定量，而 的其它分量保持不变来构成，对应于 的 的分量上减去，而 的其它分量保持不变来构成。,规定 是 的一部分，。,选择 的基本要求是，使任意样本到这两个新的聚类中心 和 之间有一个足够可检测的距离差别，被区别并能完全将Xi分到 和 中。,5.2.4 k-均值算法和ISODATA算法,算法
38、步骤,如果完成分裂，迭代次数加1，l=l+1。转。否则继续进行。以下三步为合并：计算全部的聚类中心的两两距离dij dij=|zi-zj|，ij，i，j=1，2，c 比较：如果dijc，转到第步，否则如果dijc，把当前L对聚类中心排序，di1j1，di2j2，diLjL其中di1j1di2j2diLjL。,5.2.4 k-均值算法和ISODATA算法,算法步骤,从di1j1开始，逐对合并，算出新的聚类中心：,删去zil和zjl，并使c=c1。注意：只允许一对对合并，并且一个聚类中心只能合并一次。,l=1，2，L,5.2.4 k-均值算法和ISODATA算法,算法步骤,迭代处理：如果是最后一次
39、迭代，l=I，或zi(l+1)=zi(l)，算法结束。输出 c个类别：Xi，zi，i=1，2，c。否则 l=l+1，转，不修改参数(可能l I)。人工参与修改参数l=l+1，转。每次回到算法的第一步或第二步就计为一次迭代。,5.2.4 k-均值算法和ISODATA算法,例5.3：如图5.13所示8个二维的样本模式，用ISODATA 算法进行聚类。,5.2.4 k-均值算法和ISODATA算法,解：假设初始聚类中心数c=1，z1=x1=(0,0)T。第一次迭代规定算法的参数：k=2，N=1，s=1，c=4，L=0，I=4。若分析的模式中无法得到先验信息，则任意选择这些参数，然后通过算法在逐次迭代
40、中进行调整。因为只有一个聚类中心z1，所以X1=x1，x2，x8，N1=8。,5.2.4 k-均值算法和ISODATA算法,由于N1N，故无子类要去除。更新聚类中心z1,计算，此时。,计算：,因为这不是最后一次迭代且，(k=2，c=1)，所以转第八步。,找X1的标准差,5.2.4 k-均值算法和ISODATA算法,取 的最大值。,因，则z1分裂成两个新的聚类中心。,5.2.4 k-均值算法和ISODATA算法,第二次迭代将样本模式重新分配给z1和z2的聚类域，现在样本集为：X1=x4，x5，x6，x7，x8，X2=x1，x2，x3，N1=5，N2=3,令，则,为方便起见，令，分别为z1和z2，
41、c=c+1=2，转第二步I=I+1=2。,5.2.4 k-均值算法和ISODATA算法,更新聚类中心,计算，i=1，2,计算，,5.2.4 k-均值算法和ISODATA算法,因为N1N和N2N，故无子集要去除。,因I=2，是偶次迭代，转第十一步。计算两两距离D12：D12=|z1-z2|=4.72 D12 c(c=4)。由上步结果表明无归并。,5.2.4 k-均值算法和ISODATA算法,因为不是最后一次迭代，所以需要作出是转到第一步还是转到第二步的判别。此例中：已得到k=2的聚类数；其可分性比由标准差所指出的平均散布大；每一个聚类中包括一定量的样本总数，因此得出的聚类中心z1和z2 具有代表
42、性。下一次迭代不需要更改算法参数，于是转到第二步，I=3。,5.2.4 k-均值算法和ISODATA算法,第三次迭代第二步和第六步，象上次迭代一样，产生同样的结果。没有满足条件，继续进行计算。计算X1和X2的标准差：,5.2.4 k-均值算法和ISODATA算法,得到与上次迭代时相同的结果：D12=|z1-z2|=4.72 得到与上次迭代时相同的结果。,这里 和。,，不满足分裂条件，继续计算。,5.2.4 k-均值算法和ISODATA算法,无归并。除标准差计算外，在这次迭代中，无新的增加，转到第二步，I=4。第四次迭代第二步和第六步，象上次迭代一样，产生同样的结果。因是最后一次迭代，置c=0，
43、转第十一步。D12=4.72同样的结果。无归并发生。因I=4是最后一次迭代，故算法结束。,5.2.4 k-均值算法和ISODATA算法,上例表明：一组较复杂的模式用Isodata算法聚类，需要经过较多次的迭代才能得到有意义的结论。然而，正确地组织每次迭代中所得到的数据资料，能深入了解给出的一组复杂模式的结构，也能指导算法执行期间的参数调整。,5.2.4 k-均值算法和ISODATA算法,三、基于样本和核的相似性度量的动态聚类方法,k-均值算法的缺点是只采用均值作为一个类的代表点。这只有当类的自然分布为球状或接近于球状时，即每类中各分量的方差接近相等时，才可能有较好的效果。对于各分量方差不等而呈
44、椭圆状的正态分布，k-均值算法的效果不是很好。,5.2.4 k-均值算法和ISODATA算法,例如图中的A点，应属于1类，但由于它离2类的均值m2更近，因此利用k-均值法就会将它分到2类。,5.2.4 k-均值算法和ISODATA算法,三、基于样本和核的相似性度量的动态聚类方法,为了解决这个问题，定义一个核Kj=K(y;Vj)来表示一个类j。其中Vj是定义Kj的一个参数集。核Kj可以是一个函数、一个点集或其它适当的分类模型。,5.2.4 k-均值算法和ISODATA算法,三、基于样本和核的相似性度量的动态聚类方法,既然用核Kj表示一个类j那么某个样本是否应属于这个类就应当在样本和核Kj之间所建
45、立的某种度量的基础上来加以考虑，因此在定义核Kj之后，还需规定一个样本y与核Kj之间的某种度量(y,Kj)来表示y与j之间的相似程度。利用这样一种相似性度量的聚类算法就是基于样本和核的相似性度量的动态聚类算法。,5.2.4 k-均值算法和ISODATA算法,三、基于样本和核的相似性度量的动态聚类方法,5.2.5 对聚类的评价,人们无法目测高维空间中样本模式的几何特性，因此对评价聚类结果的好坏产生一定的困难。为了便于说明聚类的原理，前面均以二维模式为例，但在实际的模式识别中，通常碰到的是维数很高的模式。为此，要严格地评价一个聚类算法的结果，可以借助几个图表，这些图表至少能反映出算法结果所得到的聚
46、类域的几何特性，从而再来进行评价。,5.2.5 对聚类的评价,聚类中心的距离聚类最远的可能是一个聚类中心。用聚类中心间的距离表描述，如表5.1所示。,假设对某组样本模式通过聚类算法，得到五个聚类中心z1、z2、z3、z4、z5。从表5.1看到z1和z2间的距离与z1和z4间的距离比较接近，z5与其它四个聚类中心间的距离都很大。但单从距离表要得出有意义的结论还是不够的，最好再列出每个聚类域中的样本数，这样两者结合可作出更好的评价。,5.2.5 对聚类的评价,z5远离其他四个聚类中心，若z5聚类域中的样本数在整个样本集中占有一定的比例，则认为z5是正确的聚类中心，假使z5聚类城中仅有一、二个样本，
47、则须进一步研究是否是由于实验误差或噪音等引起的，然后再考虑z5的取舍。,5.2.5 对聚类的评价,每类中的样本数，距离近的两类中样本数少，可合并。如两个聚类中心间的距离很小，并且域中的样本数又占一定的比例，则有时也可考虑合并这两个聚类域。,5.2.5 对聚类的评价,各个聚类中子域中的标准差聚类域的方差能用来推断聚类城中样本的相对分布，如表5.2所示。,5.2.5 对聚类的评价,为简化起见，假设样本模式是四维的，Xi表示第i个聚类域，每一方差元素沿着一个方向的坐标轴。从表中可推断样本总体的若干特性。,因此将方差表与距离表及聚类城中样本数结合起来分析，可以较好地评价聚类的结果。此外，这些图表中的数据资料能对迭代算法中的参数选择起指导作用。,Xi的、的值比较接近，它的聚类域可能是接近球形的。,X5的 比其它几个方向的值大，则说明沿第三个坐标轴方向上拉长，这个聚类域的模式分布可能是长的。,5.2.5 对聚类的评价,
