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