模式识别第五章聚类分析

在已知类别的样本集基础上，用确定的或统计的判别函数对模式进行分类，设计分类器，这些已知的样本集称为训练集。根据判读好的训练集解决分类问题，称为有人管理或有教师的分类法。

第五章聚类分析整理ppt第五章聚类分析没有训练集的情况下的样本分类问题，所选用的样本是预先不知其所属的类别，需要根据样本间的距离或相似性的程度自动地进行分类。这种无人参预（或没有教师的）识别问题，称为聚类或无人管理的分类。整理ppt聚类分析方法是决定描述一个经验数据集的结构类型的一种非参数方法。相似的数据被集中在一起，从数据集中分离出来，包含在特征空间中的一个模式集，其模式的密度比起周围区域中的密度大，就为一个聚类。第五章聚类分析整理ppt聚类原则：根据样本集，找出各点内在的相似性进行分类，相似的分为一类。⑴直观的相似性：从几何距离考虑，设阈值T，它是相似性度量的标准，靠经验确定，对分类影响很大。可用于粗分。⑵样本集群性（紧致性）：同一类的应该群集，不同类的应该远离。第五章聚类分析整理ppt⑶特征空间量纲标尺的选择：量纲选择不同，分类也有差异。第五章聚类分析整理ppt为了克服这个缺点，常使特征数据标准化，使它与变量量纲标尺没有关系。第五章聚类分析整理ppt5.1相似性度量和聚类准则一般用归并相似的模式和分开不相似的模式以形成聚类。相似性归并是聚类最普通的形式。各式各样的相似性和距离度量已经作为特征空间中模式样本的聚类准则。第五章聚类分析整理ppt5.1.1相似性度量(Similaritymeasure)

相似性度量将建立一个把模式分到一聚类中心域的原则。⒈欧氏距离(Euclideandistance)(常用)对两个样本xi和xj，其欧氏距离定义为若dij小，相似性大。5.1相似性度量和聚类准则整理ppt加权欧氏距离也是一种常用的相似性度量。wk是系数，其重要，wk大；次要的，wk小。

⒈欧氏距离(Euclideandistance)(常用)5.1.1相似性度量整理ppt⒉马氏距离

(Mahalanobisdistance)(不常用)x是待识别样本，m是均值向量，∑是协方差矩阵。若∑为单位阵，则马氏距离与欧氏距离相似。马氏距离的优点是排除了模式样本之间的相关性的影响。例如取一个模式特征向量，可能其中九个分量是反映同一特征A，而只有一个分量反映另一特征B，这时如用欧氏距离计算，主要反映了特征A，而用马氏距离则可避免这个缺点。5.1.1相似性度量整理ppt⒊明氏距离(Minkowskydistance)m=2时为欧氏距离；m=1为绝对距离(用绝对值)；dij=|xi1－xj1|+…+|xid－xjd|相似性度量不一定只限于距离，可以是下面的形式：5.1.1相似性度量整理ppt⒋角度相似性度量函数sij是向量xi和xj之间夹角的余弦，当xi和xj相对于原点是同一方向时，函数值最大。当聚类区域有扇形分布时往往采用这种相似性度量。如图5.1所示。5.1.1相似性度量整理pptθ2θ10ωiωj图5.1相似性度量的说明从图中可以看到，由于s(x，x1)比s(x，x2)大，因此x与x1比与x2更相似。x1x2x5.1.1相似性度量整理ppt距离和角度相似性函数作为相似性的测度各有其局限性。距离对于坐标系的旋转和位移是不变的，对于放大缩小并不具有不变性的性质。角度相似性函数对于坐标系的旋转放大缩小是不变的，但对于位移不具有不变性的性质。用角度相似性函数作为相似性的测度还有一个缺点，当本属不同类的样本分布在从模式空间原点出发的一条直线上时，所有样本之间角度相似性函数几乎都等于l，造成归为一类的错误。5.1.1相似性度量整理ppt⒌Tanimoto度量(常用)

若模式向量取二进制值0，1时有特殊意义，样本x具有第k个特征，xiTxj是两者共同的特征数；是xi和xj各自具有的特征数的几何均值。这种度量称为Tanimoto

度量。

5.1.1相似性度量整理ppt⒌Tanimoto度量(常用)

适用于疾病诊断、动植物分类和情报检索等方面。上述介绍的相似性量度不是仅有的形式，而是属于比较简单和典型的。5.1.1相似性度量整理ppt距离函数应满足三个条件：⑴非负性：对于一切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)，即相当于三角形两边之和必大于第三边。5.1.1相似性度量整理ppt5.1.2聚类准则

假定有一组样本{x1，x2，…，xN}，要求对其进行确切分成ω1，ω2，…，ωc类。同一类里的样本比不同类里的样本相似性高一些，于是可存在多种分类，到底何种分类方法最好？需要定义一个准则函数，则聚类问题就变成对准则函数求极值的问题。5.1相似性度量和聚类准则整理ppt⒈试探方式：针对具体的实际问题，定义一种相似性度量的阈值T，按最近邻原则分类，须不断检验、修正阈值T。这种方法的误判率受T及起始样本影响。

5.1.2聚类准则

整理ppt⒉误差平方和准则(最小方差划分)(常用)

误差平方和准则是聚类问题中最简单而又广泛应用的准则。准则函数为

c是类别数，Xi是第i类聚类中心域的样本集合，mi是第i类均值向量(类中心)

Ni是Xi中的样本数。使J最小化的聚类就是最合理的聚类。5.1.2聚类准则

整理ppt⒉误差平方和准则(最小方差划分)

此种准则函数适用于集群性好，且各类容积相近情况。如果类间距离小，容积相差悬殊，容易发生错误。5.1.2聚类准则

整理ppt⒉误差平方和准则(最小方差划分)如图(a)中所示的模式分类，使用这种准则进行聚类可获得最好的效果。ω1ω2ω3x1x2(a)5.1.2聚类准则

整理ppt⒉误差平方和准则(最小方差划分)而如图(b)中的模式分布，使用这种准则得到的效果就不理想。

ω1ω2x1x2(b)5.1.2聚类准则

整理ppt⒉误差平方和准则(最小方差划分)当各类中的样本数相差很大而类间距离较小时，有可能把样本数多的一类一拆为二，这样聚类的结果，误差平方和准则函数J比保持完整时为小(如图5.3所示)。因此有可能将ω1和ω2分错，发生错误聚类。5.1.2聚类准则

整理ppt⒉误差平方和准则(最小方差划分)图5.3把大群拆开的问题(b)的误差平方和小于(a)的误差平方和5.1.2聚类准则

整理ppt⒊与最小方差有关的准则经过简单的代数运算，可以将上述J的表达式中均值向量mi消去，得到另一种准则函数表示形式式中c是聚类数；Ni是第i个聚类域中的样本数；Si是相似性算子。它是第i类点间距离平方的平均，是以欧氏距离作为相似性度量。5.1.2聚类准则

整理ppt⒊与最小方差有关的准则若以非尺寸的相似性函数s(x，x’)来取代相似性算子Si中的欧氏距离并把它代入准则函数J的表示式中，可得到准则函数的另一种表示形式。5.1.2聚类准则

整理ppt⒋散布准则（离散度准则）用多元判别式分析中的散布矩阵可以推出另一种准则函数。第i类的均值向量(第i类的中心)

总平均向量(总体中心)

5.1.2聚类准则

整理ppt⒋散布准则（离散度准则）第i类的散布矩阵类内散布矩阵类间散布矩阵5.1.2聚类准则

整理ppt⒋散布准则(离散度准则)总散布矩阵

根据上述定义可以证明，总散布矩阵等于类内散布矩阵与类间散布矩阵之和。即：ST

=SW+SB

5.1.2聚类准则

整理ppt证明：ST

=SW+SB∵∴

5.1.2聚类准则

整理ppt5.1.2聚类准则

整理ppt散布准则(离散度准则)总散布矩阵与如何划分类别无关，仅与全部样本有关。但类内和类间散布矩阵都与类别划分有关。这两矩阵有一互补关系，因此使类内散布矩阵最小就是使类间散布矩阵最大。

由于度量矩阵大小的方法有“迹”和行列式，故利用散布矩阵提出以下准则：

5.1.2聚类准则

整理ppt⒈迹准则

迹是散布矩阵大小的最简单的度量，迹等于散布矩阵的对角线元素之和，最小化SW的迹准则使其(J)取最小值，是一种最优化的准则。5.1.2聚类准则

整理ppt⒈迹准则或最大化SB的迹作为另一种最优化的准则。

5.1.2聚类准则

整理ppt⒉行列式准则散布矩阵的行列式可作为散布矩阵的另一种大小度量。在类数小于或等于维数时，SB是奇异的，所以不能选择SB的行列式作为准则函数，一般选择SW的行列式，行列式准则函数为这是因为矩阵行列式的大小正比于主轴方向方差的乘积。5.1.2聚类准则

整理ppt5.2聚类算法5.2.1按最近邻原则试探算法

特点：简单、快速。缺点：粗糙。假设有N个样本{x1，x2，…，xN}，x在d维特征空间，类别数未知。

第五章聚类分析应用于无训练样本集，无教师（或无人）参与分类过程。整理ppt㈠算法步骤(依据试探性准则)

⒈选定一个非负的阈值T。⒉在{x1，x2，…，xN}中任取xi，i=1，2，…，N，令任一个样本xi为第一个聚类中心z1，即z1=xi，例如，可选z1=x1作为第一个聚类中心。⒊取x2计算(根据具体问题选定计算方法)5.2.1按最近邻原则试探算法整理ppt㈠算法步骤(依据试探性准则)

判断：①d21＞T，则建立一个新的聚类中心z2，z2=x2。②d21≤T，则x2∈X1，X1是以z1为聚类中心的模式的集合。例如，选定欧氏距离作为相似性度量，计算x2到z1的距离5.2.1按最近邻原则试探算法整理ppt㈠算法步骤(依据试探性准则)

⒋取下一个样本xj，xj是余下的样本中的任一个，计算dj1=||xj－z1||，dj2=||xj－z2||，…，dj1=||xj－zk||，接着分别计算x3到z1和z2的距离得d31和d32，如果判断①d31＞T，d32＞T，则再建立一个新的聚类中心z3，z3=x3。②d31≤d32≤T，则x3∈X1，否则x3∈X2，X2是以z2为聚类中心的模式的集合。即将x3分到最近的聚类中心的域中。5.2.1按最近邻原则试探算法整理ppt㈠算法步骤(依据试探性准则)

⒌所有样本全部处理完毕否？没有处理完，转4。处理完，算法结束。

若

否则，xj属于离它最近的聚类中心所属的类。判断：5.2.1按最近邻原则试探算法整理ppt㈡算法讨论此算法的聚类结果受阈值T的大小、初始值z1的选择、样本的顺序及数据的几何特性等四个因素的影响。其中T和z1的影响大一些。如图5.4所示。

(a)(b)T3(c)图5.4按最近邻原则试探算法中阈值和起始点的影响T2T2T15.2.1按最近邻原则试探算法整理ppt改进措施：①具有待分类样本集的几何分布的先验知识，用来指导选择T和z1，可以改善聚类结果(在d较小时，如d=1，2，3等)。②在d较大的高维情况，要进行反复验算、修正T和z1(验算采用误差平方和等准则)。否则，此算法只能用于粗糙分类，进行预分。5.2.1按最近邻原则试探算法整理ppt5.2.2小中取大距离算法(最大最小距离算法)

此算法以欧氏距离为基础，选集合中最不相似(距离最大)的点或样本作为各类的聚类中心。举例说明如图所示样本的此聚类算法步骤：5.2.2小中取大距离算法整理ppt如图所示模式：⒈任选一模式样本x1，令z1=x1为第一个聚类中心。1123456782345678x1x20x1x4x3x2x6x5x7x8x9x10(a)算法所用的样本模式5.2.2小中取大距离算法整理ppt⒈在图(b)中由z1标志，图中箭头上的数字标志了聚类中心赋值的步骤。x1x2x3x4x5x6x7x8x9x10z1(1)(b)样本和种类表⒉计算欧氏距离di1=||xi－z1||，i=1，2，…，N。5.2.2小中取大距离算法整理ppt则令z2=xj为新的聚类中心。在此例中最大，故z2=x6。

1123456782345678x1x20x1x4x3x2x6x5x7x8x9x10(a)算法所用的样本模式判断：若5.2.2小中取大距离算法整理ppt在图(b)中由z2标志x1x2x3x4x5x6x7x8x9x10z1z2z3(1)(2)(b)样本和种类表5.2.2小中取大距离算法整理ppt⒊找新的聚类中心设当前已有z1，z2，…，zk个聚类中心，分别计算其余样本到各聚类中心的距离：1123456782345678x1x20x1x4x3x2x6x5x7x8x9x10(a)算法所用的样本模式di1=||xi－z1||，di2=||xi－z2||，……，dik=||xi－zk||，i=1，2，…，N5.2.2小中取大距离算法整理ppt取，m=1，2，…，k。取，i=1，2，…，N。若djm＞θmax||zi－zl||，i，l=1，2，…k。则令zk+1=xj。此例中，z3=x7，。θ是系数，。5.2.2小中取大距离算法1123456782345678x1x20x1x4x3x2x6x5x7x8x9x10(a)算法所用的样本模式整理ppt在图(b)中由z3标志，图中箭头上的数字标志了聚类中心赋值的步骤。x1x2x3x4x5x6x7x8x9x10z1z2z3(1)(2)(3)(b)样本和种类表5.2.2小中取大距离算法整理pptθ若取得大，划分的类少；θ若取得小，划分的类多。一般根据经验试探选。⒋每确定一个新的聚类中心后，重复3。若djm≤θmax||zi－zl||，i，l=1，2，…，k。则寻找聚类中心的工作结束。

5.2.2小中取大距离算法1123456782345678x1x20x1x4x3x2x6x5x7x8x9x10(a)算法所用的样本模式整理ppt⒌计算距离后分类dil=||xi－xl||，i=1，2，…，N；l=1，2，…，k。根据最近邻原则分类。本例中，X1={x1，x3，x4}，X2={x2，x6}，X3={x5，x7，x8，x9，x10}。5.2.2小中取大距离算法1123456782345678x1x20x1x4x3x2x6x5x7x8x9x10(a)算法所用的样本模式整理ppt⒍对每一聚类域，取样本的平均作为新的聚类中心。

5.2.2小中取大距离算法整理ppt算法讨论：本算法相当于最近邻试探法的改进，但仍受到z1的选择、θ的大小的影响，对于几何分布集群性比较好的分类问题，效果较好。5.2.2小中取大距离算法整理ppt5.2.3分级聚类方法(层次聚类法)

由于聚类分析只是把N个没有类别标签的样本分成一些合理的类，在极端的情况下，最多可分为N类，最少只有一个类，因此可以把问题看成是将N个样本划分成c个类的划分序列。第一个划分是把样本分成N个类，每类包含一个样本；第二个划分是把样本分成N－1个类；下一个划分是把样本分成N－2个类等等，直到第N个划分时，把样本仅分成一个类。5.2.3分级聚类方法整理ppt如果类数c=N－K+l，则称这个划分处于K水平。例如1水平就相当于分成N类，N水平就相当于把所有样本归为1类。任何两个样本xi和xj总会在某一水平被分为同一类。5.2.3分级聚类方法整理ppt分级聚类就是这样一种划分序列。这种划分序列具有如下的性质：只要在K水平时样本被归入同一类后，在进行更高水平的划分时，它们也永远属于同一类。

生物分类就是分级聚类的一个例子。先是把许多个体集合成种，然后种集合成类，类集合成族等等。如生物界=动物，门=脊索动物类，纲=脊椎动物，类=鱼类，子类=鳍类，目=鲑鱼类，科=鲑鱼，等等。5.2.3分级聚类方法整理ppt分级聚类方法的最自然的表示就是树。5.2.3分级聚类方法整理ppt另一种表达分级聚类的方法是集合，每个层次上的类都可能含有子类集合，如图所示。纯符号的表示方法，如{{x1，{x2，x3}}，{{x4，x5}，{x6，x7}}，x8}}。这些方法虽能够表达层次关系，但无法定量地体现相似性。树图是较好的方法。5.2.3分级聚类方法整理ppt层次聚类可以通过合并(agglomerative)和分裂(divisive)两种方法实现。合并（自低向上）时，每个样本各成一类，通过合并不同的类，减少类别数目。分裂（自顶向下）时，所有样本先归入一类，通过后续分裂，增加类别数目。下面主要介绍合并的方法。5.2.3分级聚类方法整理ppt基于合并的分级聚类方法对于N个d维未知样本，其算法步骤为：⒈设初始的类别数，X={xi}，i=1，2，…，N。计算类间相似性度量距离矩阵D0，D0是xi间的两两距离矩阵。⒉找出最相似的两类(相似性度量距离最小)，假设为Xh，Xk，将其合并，Xj={Xh，Xk}。

5.2.3分级聚类方法整理ppt⒊计算合并后的类别之间的相似性程度的度量距离矩阵Dl。⒋若给定的类别数是c，，算法结束。①，算法结束。若没有给定类别数c，则②设定阈值T，当两类之间最小距离＞T时，算法结束。----基于合并的分级聚类方法5.2.3分级聚类方法整理ppt讨论类间相似性度量的方法，假定每个样本之间用欧氏距离：⒈最近距离属于近邻算法，适用于类间分布较散，链状聚合。如果Xj

={Xh，Xk}，即Xj是由Xh、Xk合并的。----基于合并的分级聚类方法5.2.3分级聚类方法整理ppt假设有三种如图5.7所示的两维点集(a)、(b)、(c)。(a)(b)(c)图5.7在用最近距离作为相似性度量进行聚类时，若类别数等于2，则各点集的相应聚类结果如图5.8所示。

----基于合并的分级聚类方法5.2.3分级聚类方法整理ppt(a)(a)----基于合并的分级聚类方法5.2.3分级聚类方法整理ppt(b)(b)----基于合并的分级聚类方法5.2.3分级聚类方法整理ppt(c)(c)----基于合并的分级聚类方法5.2.3分级聚类方法整理ppt图5.7(a)和(b)点集的唯一差别是(b)中出现了两个干扰点。从图5.8(b)中可见，这种相似性度量的缺点是只要在两个各自密集的点集之间存在一些位置互相靠近的点的路径，那么就很可能会把两个密集的点集(本应分属于两类的点集)聚集成一个类。----基于合并的分级聚类方法5.2.3分级聚类方法整理ppt从图可见，当最终类别数为1时，以最近距离作为相似性度量进行样本点聚类的过程就是一棵最小生成树形成的过程。因此这是一种最小生成树算法。如果给出了最小生成树，可以根据它得到最近邻的聚类结果。只要把最小生成树中长度(距离)最大的一支去掉就得到2类的聚类结果，去掉第二长的分支，数据就分为3类，如此继续下去，就导出了基于分裂的层次聚类方法。----基于合并的分级聚类方法5.2.3分级聚类方法整理ppt⒉最远距离属于近邻算法，适用于团状集群。取其中dmax最大的一对合并。如Xj

={Xh，Xk}，dmax(Xi，Xj)=max{dmax(Xi，Xh)，dmax(Xi，Xk)}----基于合并的分级聚类方法5.2.3分级聚类方法整理ppt在用最远距离作为相似性度量时，可以把聚类算法看成是产生一个图，图中同一个类的结点都是用棱线联结起来的。用图论的术语来说就是每个类构成一个完备子图。两个类之间的距离现在是由这两个类中相距最远的结点来确定的，对于图5.7的三种点集，当类别数等于2时，其相应的聚类结果见图5.9。----基于合并的分级聚类方法5.2.3分级聚类方法整理ppt(a)(a)----基于合并的分级聚类方法5.2.3分级聚类方法整理ppt从图(b)可见，它防止了两个密集点集通过某个路径聚为一类的可能性。(b)(b)----基于合并的分级聚类方法5.2.3分级聚类方法整理ppt图(c)的结果则说明了这种相似性度量不能检出具有长条形状的聚类。(c)(c)显然，这种度量将使个别的远离点对聚类结果产生十分大的影响。----基于合并的分级聚类方法5.2.3分级聚类方法整理ppt⒊均值距离

这种相似性度量的效果介于上述两者之间。中心距离适用于球状、近似球状分布。----基于合并的分级聚类方法5.2.3分级聚类方法整理ppt例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.1012345678x1x2011023456x2x19x3x4x5----基于合并的分级聚类方法5.2.3分级聚类方法整理ppt解：采用。②l=2，，dmean(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分级聚类方法整理ppt算法讨论：适用于样本总数不太多情况。若类别数c未知，受阈值T影响。采用不同相似性度量，会影响聚类结果。实际上，可以多选几种距离度量来试验。

----基于合并的分级聚类方法5.2.3分级聚类方法整理ppt5.2.4k-均值算法和ISODATA算法(动态聚类方法)

动态聚类方法是一种普遍采用的方法，它具有以下三个要点：⒈选定某种距离度量作为样本间的相似性度量。⒉确定某个评价聚类结果质量的准则函数。⒊给定某个初始分类，然后用迭代算法找出使准则函数取极值的最好聚类结果。先讨论在误差平方和准则基础上的k-均值算法，然后结合对这算法的分析给出一些其它的动态聚类算法。整理ppt5.2.4k-均值算法和ISODATA算法k-均值算法使聚类域中所有样本到聚类中心的距离平方和最小，这是在误差平方和准则的基础上得来的。k是类别数，已知或任选。相似性度量采用欧氏距离。分类准则采用平方误差和准则。

一、k-(或c)均值算法(k-meanAlgorithm)整理ppt准则函数：

zi是第i类的聚类中心。样本集X={x1，x2，…，xN}xi是d维特征向量。5.2.4k-均值算法和ISODATA算法整理ppt㈠算法步骤：⒈任意选择k个初始聚类中心，z1(1)，z2(1)，…，zk(1)作为初始聚类中心。⒉第l次迭代，将待分类的N个样本按最小距离原则分配到k个聚类中，对待识别样本x，若||x-zj(l)||＜||x-zi(l)||，式中j=1，2，…，k，i≠j，则x∈Xj(l)，Xi(l)是聚类中心为zi(l)的样本集。5.2.4k-均值算法和ISODATA算法整理ppt㈠算法步骤：⒊由第2步结果，计算新的聚类中心。，i=1，2，…，k

这样使Xi(l)中的所有样本点到新的聚类中心的距离平方和准则函数，i=1，2，…，k最小。

5.2.4k-均值算法和ISODATA算法整理ppt㈠算法步骤：⒋若zi(l+1)=zi(l)，i=1，2，…，k，算法收敛，则检验J是否最小，并结束。若zi(l+1)≠zi(l)，令l=l+1，转2，经过多次迭代M次(自己设定)，停机，修改参数，重新计算或取最小J情况下的聚类输出。

5.2.4k-均值算法和ISODATA算法整理ppt㈡算法讨论⒈收敛问题尚无证明收敛问题与几何分布有关，样本各类有类超球体分布，各类容积相近，易收敛；收敛与否，与k=1时的z1~zk的选择有关，选的好，有可能收敛，否则不然，故要试探。⒉初始聚类中心z(1)的选择①凭先验知识，将样本集大致分类，取代表点。②将全部样本人为地分k类，取代表点(均值)。5.2.4k-均值算法和ISODATA算法整理ppt㈡算法讨论③密度法：以每个样本为中心，定义某个正数r为半径，在球内落入的点的个数作为密度，取最大密度点为z1，然后再找出与z1的距离＞r的次大密度做新的聚类中心，依次选定。④选择给定样本集的前k个样本做聚类中心。⑤从(k-1)聚类划分解中，产生k类划分代表点。⒊k的确定可采用试探法，令k=2，3，4…，对应算出准则函数J做曲线，一般k↑→J↓，k=N，J=0。5.2.4k-均值算法和ISODATA算法整理ppt㈡算法讨论当J下降变慢时，对应的k较为合适，如果分不清J下降快慢的界限，则应试探进行。1234567…NkJ0图5.11如图5.11所示，从5~6下降较小，认为5较合适。故k=5。5.2.4k-均值算法和ISODATA算法整理ppt例5.2如图5.12给出20个二维的样本，用k均值算法进行聚类。

图5.12k均值算法所用的样本模式12345678x1x2011023456789910x1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16x17x18x19x205.2.4k-均值算法和ISODATA算法整理ppt解：⒈令k=2，选择z1(1)=x1=(0,0)T，z2(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.12k均值算法所用的样本模式12345678x1x2011023456789910x1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16x17x18x19x20例5.2如图5.12给出20个二维的样本，用k均值算法进行聚类。

5.2.4k-均值算法和ISODATA算法整理ppt例5.2如图5.12给出20个二维的样本，用k均值算法进行聚类。

5.2.4k-均值算法和ISODATA算法图5.12k均值算法所用的样本模式12345678x1x2011023456789910x1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16x17x18x19x20整理ppt⒋因为zj(2)≠zj(1)，j=1，2，转到第二步。⒌因为||xl-z1(2)||＜||xl–z2(2)||，l=1，2，…，8，所以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.4k-均值算法和ISODATA算法图5.12k均值算法所用的样本模式12345678x1x2011023456789910x1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16x17x18x19x20整理ppt例5.2如图5.12给出20个二维的样本，用k均值算法进行聚类。

5.2.4k-均值算法和ISODATA算法图5.12k均值算法所用的样本模式12345678x1x2011023456789910x1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16x17x18x19x20整理ppt⒎因为zj(3)≠zj(2)，j=1，2，转到第二步。⒏与前面一次迭代产生同样的结果，X1(4)=X1(3)，X2(4)=X2(3)。⒐也产生同样的结果。⒑因为zj(4)=zj(3)，j=1，2，故算法收敛。产生的聚类中心为例5.2如图5.12给出20个二维的样本，用k均值算法进行聚类。

5.2.4k-均值算法和ISODATA算法图5.12k均值算法所用的样本模式12345678x1x2011023456789910x1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16x17x18x19x20整理ppt结果与观察给定模式所得的结果是相符的。

例5.2如图5.12给出20个二维的样本，用k均值算法进行聚类。

5.2.4k-均值算法和ISODATA算法图5.12k均值算法所用的样本模式12345678x1x2011023456789910x1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16x17x18x19x20整理ppt二、ISODATA算法ISODATA算法(IterativeSelf-organizingDataAnalysisTechniquesA迭代自组织数据分析技术)在k-均值算法基础上，在迭代过程中增加了某种产生和消除某些类别的方法，具有自动合并和分裂类，自动寻找类别数k的功能。在每一次迭代时，首先，在不改变类别数目的前提下来改变分类，然后，将样本平均矢量之差小于某一预定阈值的每一类别对合并起来，或根据样本协方差矩阵来决定其分裂与否，一次一次地迭代，并不断地进行合并和分开，这种算法具有人机交互和启发式的特点。5.2.4k-均值算法和ISODATA算法整理ppt㈠

算法参数

k—要找的聚类中心数；θN

—每一类中至少应具有的样本个数（少于此值的样本点集去掉）；θs—类内的样本标准差阈值（判别类是否太大，若太大分2类），取总体分布各个特征分量轴上标准差σi，取其一部分用ασi表示，0<α<1，i=1，2，…，N；5.2.4k-均值算法和ISODATA算法整理ppt㈠

算法参数

L—一次迭代运算中可合并的最多对数（一般取一对）；

I—允许迭代的次数（相当于k-均值算法中的M）；θc

—两类中心距的最小距离（＜θc，可合并）。5.2.4k-均值算法和ISODATA算法整理ppt㈡

算法步骤基本步骤：

⑴初始化，任意选定c个聚类中心，z1(1)，z2(1)，…，zc(1)，定义算法参数，k，θN，θs，θc，L，I。

⑵分配N个样本到c类中，按最近邻原则计算，若||x-zi||<||x-zj|，i=1，2，…，c，i≠j，则x∈Xi，其中Xi表示分到聚类中心zi的样本子集，Ni为Xi中的样本数。⑶若对任意的i，Ni<θN，则去除Xi，并使c=c-1，即将样本数比θN少的样本子集去除。5.2.4k-均值算法和ISODATA算法整理ppt㈡

算法步骤以下三步计算距离：⑷修正聚类中心zi，，i=1，2，…，c

⑸计算Xi中样本与其对应的中心的平均距离，i=1，2，…，c

5.2.4k-均值算法和ISODATA算法整理ppt㈡

算法步骤⑹计算总体的平均距离

其中N为样本集中的样本总数。⑺判断：①若是最后一次迭代，l=I，置θc

=0，转⑾步算法结束。②若，直接转到第⑻步，分裂类操作。5.2.4k-均值算法和ISODATA算法整理ppt㈡

算法步骤③若c≥2k，直接转到⑾步，合并类操作。④若②、③类不满足，继续。⑻计算标准差σij

其中d是样本模式的维数，xkj是Xj中第k个样本的第j个分量，zij是zi的第j个分量。j=1，2，…，d；

i=1，2，…，c

的每个分量表示Xi中样本沿主要坐标轴的标准差。

5.2.4k-均值算法和ISODATA算法整理ppt㈡

算法步骤⑽如果σimax>θs，i=1，2，…，c，同时满足以下条件之一：⑼找出中的最大分量，i=1，2，…，c。

①且(样本数不能太小)；②则将Xi分成两类，出现两个新的聚类中心和，删去，并使c=c+1。5.2.4k-均值算法和ISODATA算法整理ppt㈡

算法步骤对应于的的分量上加上一个给定量，而的其它分量保持不变来构成，对应于的的分量上减去，而的其它分量保持不变来构成。规定是的一部分，，。

选择的基本要求是，使任意样本到这两个新的聚类中心和之间有一个足够可检测的距离差别，被区别并能完全将Xi分到和中。5.2.4k-均值算法和ISODATA算法整理ppt㈡

算法步骤如果完成分裂，迭代次数加1，l=l+1。转⑵。否则继续进行⑾。以下三步为合并：⑾计算全部的聚类中心的两两距离dij

dij=||zi-zj||，i≠j，i，j=1，2，…，c

⑿比较：如果dij≥θc，转到第⒁步，否则如果dij<θc，把当前L对聚类中心排序，[di1j1，di2j2，…，diLjL]其中di1j1<di2j2<…<diLjL。

5.2.4k-均值算法和ISODATA算法整理ppt㈡

算法步骤⒀从di1j1开始，逐对合并，算出新的聚类中心：删去zil和zjl，并使c=c－1。注意：只允许一对对合并，并且一个聚类中心只能合并一次。l=1，2，…，L

5.2.4k-均值算法和ISODATA算法整理ppt㈡

算法步骤⒁迭代处理：如果是最后一次迭代，l=I，或zi(l+1)=zi(l)，算法结束。输出

c个类别：{Xi}，{zi}，i=1，2，…，c。否则①l=l+1，转⑵，不修改参数(可能l<I)。②人工参与修改参数l=l+1，转⑴。每次回到算法的第一步或第二步就计为一次迭代。5.2.4k-均值算法和ISODATA算法整理ppt例5.3：如图5.13所示8个二维的样本模式，用ISODATA算法进行聚类。1123456782345678x1x20x1x2x3x4x5x6x7x8图5.13ISODATA算法所用的样本模式5.2.4k-均值算法和ISODATA算法整理ppt解：假设初始聚类中心数c=1，z1=x1=(0,0)T。㈠第一次迭代⑴规定算法的参数：k=2，θN=1，θs=1，θc=4，L=0，I=4。若分析的模式中无法得到先验信息，则任意选择这些参数，然后通过算法在逐次迭代中进行调整。⑵因为只有一个聚类中心z1，所以X1={x1，x2，…，x8}，N1=8。

5.2.4k-均值算法和ISODATA算法整理ppt⑶由于N1>θN，故无子类要去除。⑷更新聚类中心z1⑹计算，此时。⑸计算：⑺因为这不是最后一次迭代且，(k=2，c=1)，所以转第八步。⑻找X1的标准差5.2.4k-均值算法和ISODATA算法整理ppt⑼取的最大值。

⑽因，，则z1分裂成两个新的聚类中心。5.2.4k-均值算法和ISODATA算法整理ppt㈡第二次迭代⑴将样本模式重新分配给z1和z2的聚类域，现在样本集为：X1={x4，x5，x6，x7，x8}，X2={x1，x2，x3}，N1=5，N2=3令，则为方便起见，令，分别为z1和z2，c=c+1=2，转第二步I=I+1=2。5.2.4k-均值算法和ISODATA算法整理ppt⑶更新聚类中心⑷计算，i=1，2⑸计算，

5.2.4k-均值算法和ISODATA算法⑵因为N1>θN和N2>θN，故无子集要去除。整理ppt⑹因I=2，是偶次迭代，转第十一步。⑺计算两两距离D12：D12=||z1-z2||=4.72⑻D12>θc(θc=4)。⑼由上步结果表明无归并。5.2.4k-均值算法和ISODATA算法整理ppt⑽因为不是最后一次迭代，所以需要作出是转到第一步还是转到第二步的判别。此例中：①已得到k=2的聚类数；②其可分性比由标准差所指出的平均散布大；③每一个聚类中包括一定量的样本总数，因此得出的聚类中心z1和z2

具有代表性。下一次迭代不需要更改算法参数，于是转到第二步，I=3。5.2.4k-均值算法和ISODATA算法整理ppt㈢第三次迭代⑴第二步和第六步，象上次迭代一样，产生同样的结果。⑵没有满足条件，继续进行计算。⑶计算X1和X2的标准差：5.2.4k-均值算法和ISODATA算法整理ppt⑹得到与上次迭代时相同的结果：D12=||z1-z2||=4.72⑺得到与上次迭代时相同的结果。⑷这里和。

⑸，，不满足分裂条件，继续计算。5.2.4k-均值算法和ISODATA算法整理ppt⑻无归并。⑼除标准差计算外，在这次迭代中，无新的增加，转到第二步，I=4。㈣第四次迭代⑴第二步和第六步，象上次迭代一样，产生同样的结果。⑵因是最后一次迭代，置θc=0，转第十一步。⑶D12=4.72⑷同样的结果。⑸无