《模式识别课件第五章聚类分析.ppt》由会员分享，可在线阅读，更多相关《模式识别课件第五章聚类分析.ppt（130页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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.15.1.1
4、相似性度量相似性度量马氏距离马氏距离(Mahalanobis distance)(不常用不常用)nx是待识别样本，m是均值向量，是协方差矩阵。若为单位阵，则马氏距离与欧氏距离相似。n马氏距离的优点是排除了模式样本之间的相关性的影响。例如取一个模式特征向量，可能其中九个分量是反映同一特征A，而只有一个分量反映另一特征B，这时如用欧氏距离计算，主要反映了特征A，而用马氏距离则可避免这个缺点。5.1.15.1.1相似性度量相似性度量明氏距离明氏距离(Minkowsky distance)nm=2时为欧氏距离；nm=1为绝对距离(用绝对值)；ndij=|xi1xj1|+|xidxjd|n相似性度量不一
5、定只限于距离，可以是下面的形式：5.1.15.1.1相似性度量相似性度量角度相似性度量函数角度相似性度量函数 nsij是向量xi和xj之间夹角的余弦，当xi和xj相对于原点是同一方向时，函数值最大。n当聚类区域有扇形分布时往往采用这种相似性度量。如图5.1所示。5.1.15.1.1相似性度量相似性度量210ij图 5.1相似性度量的说明从图中可以看到，由于s(x，x1)比s(x，x2)大，因此x与x1比与x2更相似。x1x2x5.1.15.1.1相似性度量相似性度量距离和角度相似性函数作为相似性的距离和角度相似性函数作为相似性的测度各有其局限性。测度各有其局限性。n距离对于坐标系的旋转和位移是
6、不变的，对于放大缩小并不具有不变性的性质。n角度相似性函数对于坐标系的旋转放大缩小是不变的，但对于位移不具有不变性的性质。n用角度相似性函数作为相似性的测度还有一个缺点，当本属不同类的样本分布在从模式空间原点出发的一条直线上时，所有样本之间角度相似性函数几乎都等于l，造成归为一类的错误。5.1.15.1.1相似性度量相似性度量Tanimoto 度量度量(常用常用)n若模式向量取二进制值0，1时有特殊意义，样本x具有第k个特征，xiTxj是两者共同的特征数；n 是xi和xj各自具有的特征数的几何均值。这种度量称为Tanimoto 度量。5.1.15.1.1相似性度量相似性度量Tanimoto 度
7、量度量(常用常用)n适用于疾病诊断、动植物分类和情报检索等方面。n上述介绍的相似性量度不是仅有的形式，而是属于比较简单和典型的。5.1.15.1.1相似性度量相似性度量距离函数应满足三个条件：距离函数应满足三个条件：n非负性：对于一切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，x
8、N，要求对其进行确切分成1，2，c类。n同一类里的样本比不同类里的样本相似性高一些，于是可存在多种分类，到底何种分类方法最好？n需要定义一个准则函数，则聚类问题就变成对准则函数求极值的问题。5.15.1相似性度量和聚类准则相似性度量和聚类准则 试探方式：试探方式：n针对具体的实际问题，定义一种相似性度量的阈值T，按最近邻原则分类，须不断检验、修正阈值T。n这种方法的误判率受T及起始样本影响。5.1.2 聚类准则聚类准则 误差平方和准则误差平方和准则(最小方差划分最小方差划分)(常用常用)n误差平方和准则是聚类问题中最简单而又广泛应用的准则。n准则函数为 nc是类别数，Xi是第i类聚类中心域的样
9、本集合，mi是第i类均值向量(类中心)Ni是Xi中的样本数。使J最小化的聚类就是最合理的聚类。5.1.2 聚类准则聚类准则 误差平方和准则误差平方和准则(最小方差划分最小方差划分)n此种准则函数适用于集群性好，且各类容积相近情况。n如果类间距离小，容积相差悬殊，容易发生错误。5.1.2 聚类准则聚类准则 误差平方和准则误差平方和准则(最小方差划分最小方差划分)n如图(a)中所示的模式分类，使用这种准则进行聚类可获得最好的效果。123x1x2(a)5.1.2 聚类准则聚类准则 误差平方和准则误差平方和准则(最小方差划分最小方差划分)n而如图(b)中的模式分布，使用这种准则得到的效果就不理想。12
10、x1x2(b)5.1.2 聚类准则聚类准则 误差平方和准则误差平方和准则(最小方差划分最小方差划分)n当各类中的样本数相差很大而类间距离较小时，有可能把样本数多的一类一拆为二，这样聚类的结果，误差平方和准则函数J比保持完整时为小(如图5.3所示)。n因此有可能将1和2分错，发生错误聚类。5.1.2 聚类准则聚类准则 误差平方和准则误差平方和准则(最小方差划分最小方差划分)图5.3 把大群拆开的问题(b)的误差平方和小于(a)的误差平方和5.1.2 聚类准则聚类准则 与最小方差有关的准则与最小方差有关的准则 n经过简单的代数运算，可以将上述J的表达式中均值向量mi消去，得到另一种准则函数表示形式
11、n式中c是聚类数；Ni是第i个聚类域中的样本数；Si是相似性算子。它是第i类点间距离平方的平均，是以欧氏距离作为相似性度量。5.1.2 聚类准则聚类准则 与最小方差有关的准则与最小方差有关的准则 n若以非尺寸的相似性函数s(x，x)来取代相似性算子Si中的欧氏距离n并把它代入准则函数J的表示式中，可得到准则函数的另一种表示形式。5.1.2 聚类准则聚类准则 散布准则（离散度准则）散布准则（离散度准则）n用多元判别式分析中的散布矩阵可以推出另一种准则函数。n第i类的均值向量(第i类的中心)n总平均向量(总体中心)5.1.2 聚类准则聚类准则 散布准则（离散度准则）散布准则（离散度准则）n第i类的
12、散布矩阵 n类内散布矩阵n类间散布矩阵 5.1.2 聚类准则聚类准则 散布准则散布准则(离散度准则离散度准则)n总散布矩阵 n根据上述定义可以证明，总散布矩阵等于类内散布矩阵与类间散布矩阵之和。n即：ST=SW+SB 5.1.2 聚类准则聚类准则 证明：证明：ST=SW+SB n n 5.1.2 聚类准则聚类准则 5.1.2 聚类准则聚类准则 散布准则散布准则(离散度准则离散度准则)n总散布矩阵与如何划分类别无关，仅与全部样本有关。n但类内和类间散布矩阵都与类别划分有关。这两矩阵有一互补关系，因此使类内散布矩阵最小就是使类间散布矩阵最大。n由于度量矩阵大小的方法有“迹”和行列式，故利用散布矩阵
13、提出以下准则：5.1.2 聚类准则聚类准则 迹准则 n迹是散布矩阵大小的最简单的度量，迹等于散布矩阵的对角线元素之和，最小化SW的迹准则n使其(J)取最小值，是一种最优化的准则。5.1.2 聚类准则聚类准则 迹准则 n或最大化SB的迹作为另一种最优化的准则。5.1.2 聚类准则聚类准则 行列式准则 n散布矩阵的行列式可作为散布矩阵的另一种大小度量。n在类数小于或等于维数时，SB是奇异的，所以不能选择SB的行列式作为准则函数，一般选择SW的行列式，行列式准则函数为n这是因为矩阵行列式的大小正比于主轴方向方差的乘积。5.1.2 聚类准则聚类准则 5.2 聚聚 类类 算算 法法按最近邻原则试探算法按
14、最近邻原则试探算法 n特点：简单、快速。n缺点：粗糙。n假设有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判断：d21T，则建立一个新的聚类中心
15、z2，z2=x2。nd21T，则x2X1，X1是以z1为聚类中心的模式的集合。n例如，选定欧氏距离作为相似性度量，计算x2到z1的距离5.2.15.2.1按最近邻原则试探算法按最近邻原则试探算法算法步骤算法步骤(依据试探性准则依据试探性准则)n取下一个样本xj，xj是余下的样本中的任一个，计算dj1=|xjz1|，dj2=|xjz2|，dj1=|xjzk|，n接着分别计算x3到z1和z2的距离得d31和d32，如果判断d31T，d32T，则再建立一个新的聚类中心z3，z3=x3。d31d32T，则x3X1，否则x3X2，X2是以z2为聚类中心的模式的集合。即将x3分到最近的聚类中心的域中。5.
16、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.2.15.2.1按最近邻原则试探算法按最近邻原则试探算法改进措施：n具有待
17、分类样本集的几何分布的先验知识，用来指导选择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 小中取大距离算法小中取大距离算法如图所示模式：任选一模式样本x1，令z1=x1为第一
18、个聚类中心。112 345 6 782345678x1x20 x1x4x3x2x6x5x7x8x9x10(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 在此例中 最大，故z2=x6。112 345 6 782345678x1x20 x1x4x3x2x6x5x7x8x9x10(a)算
19、法所用的样本模式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 782345678x1x20 x1x4x3x2x6x5x7x8x9x10(a)算法所用的样本模式ndi1=|xiz1|，ndi2=|xiz2|，ndik=|xizk|，ni=1，2，N5.2.2 5.2.2 小中取大距离算法小中取大距离算法
20、n取 ，nm=1，2，k。n取 ，ni=1，2，N。n若djmmax|zizl|，ni，l=1，2，k。n则令zk+1=xj。n此例中，z3=x7，。是系数，。5.2.2 5.2.2 小中取大距离算法小中取大距离算法112 345 6 782345678x1x20 x1x4x3x2x6x5x7x8x9x10(a)算法所用的样本模式n在图(b)中由z3标志，图中箭头上的数字标志了聚类中心赋值的步骤。x1x2x3x4x5x6x7x8x9x10z1z2z3(1)(2)(3)(b)样本和种类表5.2.2 5.2.2 小中取大距离算法小中取大距离算法若取得大，划分的类少；若取得小，划分的类多。一般根据经
21、验试探选。每确定一个新的聚类中心后，重复3。若djmmax|zizl|，i，l=1，2，k。则寻找聚类中心的工作结束。5.2.2 5.2.2 小中取大距离算法小中取大距离算法112 345 6 782345678x1x20 x1x4x3x2x6x5x7x8x9x10(a)算法所用的样本模式n计算距离后分类 dil=|xixl|，i=1，2，N；l=1，2，k。根据最近邻原则分类。n本例中，nX1=x1，x3，x4，nX2=x2，x6，nX3=x5，x7，x8，x9，x10。5.2.2 5.2.2 小中取大距离算法小中取大距离算法112 345 6 782345678x1x20 x1x4x3x2
22、x6x5x7x8x9x10(a)算法所用的样本模式n对每一聚类域，取样本的平均作为新的聚类中心。5.2.2 5.2.2 小中取大距离算法小中取大距离算法n算法讨论：n本算法相当于最近邻试探法的改进，但仍受到z1的选择、的大小的影响，对于几何分布集群性比较好的分类问题，效果较好。5.2.2 5.2.2 小中取大距离算法小中取大距离算法分级聚类方法分级聚类方法(层次聚类法层次聚类法)n由于聚类分析只是把N个没有类别标签的样本分成一些合理的类，在极端的情况下，最多可分为N类，最少只有一个类，因此可以把问题看成是将N个样本划分成c个类的划分序列。n第一个划分是把样本分成N个类，每类包含一个样本；第二个
23、划分是把样本分成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分级聚类就是这样一种划分序列。这种划分序列具有如下的性质：只要在K水平时样本被归入同一类后，在进行更高水平的划分时，它们也永远属于同一类。n生物分类就是分级聚类的一个例子。先是把许多个体集合成种，然后种集合成类，类集合成族等等。如生物界=动物，门=
24、脊索动物类，纲=脊椎动物，类=鱼类，子类=鳍类，目=鲑鱼类，科=鲑鱼，等等。5.2.35.2.3分级聚类方法分级聚类方法n分级聚类方法的最自然的表示就是树。5.2.35.2.3分级聚类方法分级聚类方法n另一种表达分级聚类的方法是集合，每个层次上的类都可能含有子类集合，如图所示。纯符号的表示方法，如x1，x2，x3，x4，x5，x6，x7，x8。这些方法虽能够表达层次关系，但无法定量地体现相似性。树图是较好的方法。5.2.35.2.3分级聚类方法分级聚类方法n层次聚类可以通过合并(agglomerative)和分裂(divisive)两种方法实现。n合并（自低向上）时，每个样本各成一类，通过合并
25、不同的类，减少类别数目。n分裂（自顶向下）时，所有样本先归入一类，通过后续分裂，增加类别数目。n下面主要介绍合并的方法。5.2.35.2.3分级聚类方法分级聚类方法基于合并的基于合并的分级聚类方法分级聚类方法n对于N个d维未知样本，其算法步骤为：设初始的类别数 ，X=xi，i=1，2，N。计算类间相似性度量距离矩阵D0，D0是xi间的两两距离矩阵。找出最相似的两类(相似性度量距离最小)，假设为Xh，Xk，将其合并，Xj=Xh，Xk。5.2.35.2.3分级聚类方法分级聚类方法n计算合并后的类别之间的相似性程度的度量距离矩阵Dl。n若给定的类别数是c，算法结束。n ，算法结束。n若没有给定类别数
26、c，则n设定阈值T，当两类之间最小距离T时，算法结束。-基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法5.2.35.2.3分级聚类方法分级聚类方法n讨论类间相似性度量的方法，假定每个样本之间用欧氏距离：n最近距离 n属于近邻算法，适用于类间分布较散，链状聚合。n如果Xj=Xh，Xk，即Xj是由Xh、Xk合并的。-基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法5.2.35.2.3分级聚类方法分级聚类方法n假设有三种如图5.7所示的两维点集(a)、(b)、(c)。(a)(b)(c)图5.7n在用最近距离作为相似性度
27、量进行聚类时，若类别数等于2，则各点集的相应聚类结果如图5.8所示。-基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法5.2.35.2.3分级聚类方法分级聚类方法(a)(a)-基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法5.2.35.2.3分级聚类方法分级聚类方法(b)(b)-基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法5.2.35.2.3分级聚类方法分级聚类方法(c)(c)-基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法5.
28、2.35.2.3分级聚类方法分级聚类方法n图5.7(a)和(b)点集的唯一差别是(b)中出现了两个干扰点。n从图5.8(b)中可见，这种相似性度量的缺点是只要在两个各自密集的点集之间存在一些位置互相靠近的点的路径，那么就很可能会把两个密集的点集(本应分属于两类的点集)聚集成一个类。-基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法5.2.35.2.3分级聚类方法分级聚类方法n从图可见，当最终类别数为1时，以最近距离作为相似性度量进行样本点聚类的过程就是一棵最小生成树形成的过程。因此这是一种最小生成树算法。n如果给出了最小生成树，可以根据它得到最近邻的聚类
29、结果。只要把最小生成树中长度(距离)最大的一支去掉就得到2类的聚类结果，去掉第二长的分支，数据就分为3类，如此继续下去，就导出了基于分裂的层次聚类方法。-基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法5.2.35.2.3分级聚类方法分级聚类方法n最远距离n属于近邻算法，适用于团状集群。n取其中dmax最大的一对合并。n如Xj=Xh，Xk，ndmax(Xi，Xj)=maxdmax(Xi，Xh)，dmax(Xi，Xk)-基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法5.2.35.2.3分级聚类方法分级聚类方法n在用
30、最远距离作为相似性度量时，可以把聚类算法看成是产生一个图，图中同一个类的结点都是用棱线联结起来的。n用图论的术语来说就是每个类构成一个完备子图。两个类之间的距离现在是由这两个类中相距最远的结点来确定的，对于图5.7的三种点集，当类别数等于2时，其相应的聚类结果见图5.9。-基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法5.2.35.2.3分级聚类方法分级聚类方法(a)(a)-基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法5.2.35.2.3分级聚类方法分级聚类方法n从图(b)可见，它防止了两个密集点集通过某个路
31、径聚为一类的可能性。(b)(b)-基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法5.2.35.2.3分级聚类方法分级聚类方法n图(c)的结果则说明了这种相似性度量不能检出具有长条形状的聚类。(c)(c)显然，这种度量将使个别的远离点对聚类结果产生十分大的影响。-基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法5.2.35.2.3分级聚类方法分级聚类方法n均值距离 n这种相似性度量的效果介于上述两者之间。n中心距离 n适用于球状、近似球状分布。-基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法基于
32、合并的分级聚类方法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 8x1x2011023456x2x19x3x4x5-基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法5.2.35.2.3分级聚类方法分级聚类方法n解：采用 。nl=2，dmean(X2，X5)最小。则X2=X2，X5=x2，x5，算法结束。n ，l=0，dmea
33、n=(X1，X4)最小，X1=X1，X4=x1，x4，X1=x1，x3，x4，X2=x2，x5。-基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法5.2.35.2.3分级聚类方法分级聚类方法算法讨论：n适用于样本总数不太多情况。n若类别数c未知，受阈值T影响。n采用不同相似性度量，会影响聚类结果。实际上，可以多选几种距离度量来试验。-基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法基于合并的分级聚类方法5.2.35.2.3分级聚类方法分级聚类方法5.2.4 k-均值算法和均值算法和ISODATA算算法法(动态聚类方法动态聚类方法)n动态
34、聚类方法是一种普遍采用的方法，它具有以下三个要点：n选定某种距离度量作为样本间的相似性度量。n确定某个评价聚类结果质量的准则函数。n给定某个初始分类，然后用迭代算法找出使准则函数取极值的最好聚类结果。n先讨论在误差平方和准则基础上的k-均值算法，然后结合对这算法的分析给出一些其它的动态聚类算法。5.2.4 5.2.4 k-k-均值算法和均值算法和ISODATAISODATA算法算法nk-均值算法使聚类域中所有样本到聚类中心的距离平方和最小，这是在误差平方和准则的基础上得来的。nk是类别数，已知或任选。n相似性度量采用欧氏距离。n分类准则采用平方误差和准则。一一、k-(或或 c)均均 值值 算算
35、 法法(k-mean Algorithm)n准则函数：nzi是第i类的聚类中心。n样本集X=x1，x2，xNnxi是d维特征向量。5.2.4 5.2.4 k-k-均值算法和均值算法和ISODATAISODATA算法算法算法步骤：n任意选择k个初始聚类中心，z1(1)，z2(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 5.2.4 k-k-均值算法和均值算法和ISODATAISODATA算法算法算
36、法步骤：n由第2步结果，计算新的聚类中心。，i=1，2，k n这样使Xi(l)中的所有样本点到新的聚类中心的距离平方和准则函数，i=1，2，k最小。5.2.4 5.2.4 k-k-均值算法和均值算法和ISODATAISODATA算法算法算法步骤：n若zi(l+1)=zi(l)，i=1，2，k，算法收敛，则检验J是否最小，并结束。n若zi(l+1)zi(l)，令l=l+1，转2，经过多次迭代M次(自己设定)，停机，修改参数，重新计算或取最小J情况下的聚类输出。5.2.4 5.2.4 k-k-均值算法和均值算法和ISODATAISODATA算法算法算法讨论算法讨论n收敛问题尚无证明n收敛问题与几何
37、分布有关，样本各类有类超球体分布，各类容积相近，易收敛；收敛与否，与k=1时的z1zk的选择有关，选的好，有可能收敛，否则不然，故要试探。n初始聚类中心z(1)的选择n凭先验知识，将样本集大致分类，取代表点。n将全部样本人为地分k类，取代表点(均值)。5.2.4 5.2.4 k-k-均值算法和均值算法和ISODATAISODATA算法算法算法讨论算法讨论n密度法：以每个样本为中心，定义某个正数r为半径，在球内落入的点的个数作为密度，取最大密度点为z1，然后再找出与z1的距离r的次大密度做新的聚类中心，依次选定。n选择给定样本集的前k个样本做聚类中心。n从(k-1)聚类划分解中，产生k类划分代表
38、点。nk的确定n可采用试探法，令k=2，3，4，对应算出准则函数J做曲线，一般kJ，k=N，J=0。5.2.4 5.2.4 k-k-均值算法和均值算法和ISODATAISODATA算法算法算法讨论算法讨论n当J下降变慢时，对应的k较为合适，如果分不清J下降快慢的界限，则应试探进行。12 3 4 56 7 NkJ0图 5.11如图5.11所示，从5 6下降较小，认为5较合适。故k=5。5.2.4 5.2.4 k-k-均值算法和均值算法和ISODATAISODATA算法算法例例5.2 如图如图5.12给出给出20个二维的样本，用个二维的样本，用k均值算法进行聚类。均值算法进行聚类。图 5.12 k
39、均值算法所用的样本模式12345678x1x2011023456789910 x1x2x3x4x5x6x7x8x9x10 x11x12x13x14x15x16x17x18x19x205.2.4 5.2.4 k-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.
40、12 k均值算法所用的样本模式123 456 78x1x2011023456789910 x1x2x3x4x5x6x7x8x9x10 x11x12x13x14x15x16x17x18x19x20例例5.2 如图如图5.12给出给出20个二维的样本，用个二维的样本，用k均值算法进行聚类。均值算法进行聚类。5.2.4 5.2.4 k-k-均值算法和均值算法和ISODATAISODATA算法算法例例5.2 如图如图5.12给出给出20个二维的样本，用个二维的样本，用k均值算法进行聚类。均值算法进行聚类。5.2.4 5.2.4 k-k-均值算法和均值算法和ISODATAISODATA算法算法图 5.1
41、2 k均值算法所用的样本模式123 456 78x1x2011023456789910 x1x2x3x4x5x6x7x8x9x10 x11x12x13x14x15x16x17x18x19x20n因为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.12给出给出20个二维的样本，用个二维的样本，用k均值算法进行聚类
42、。均值算法进行聚类。5.2.4 5.2.4 k-k-均值算法和均值算法和ISODATAISODATA算法算法图 5.12 k均值算法所用的样本模式123 456 78x1x2011023456789910 x1x2x3x4x5x6x7x8x9x10 x11x12x13x14x15x16x17x18x19x20例例5.2 如图如图5.12给出给出20个二维的样本，用个二维的样本，用k均值算法进行聚类。均值算法进行聚类。5.2.4 5.2.4 k-k-均值算法和均值算法和ISODATAISODATA算法算法图 5.12 k均值算法所用的样本模式123 456 78x1x20110234567899
43、10 x1x2x3x4x5x6x7x8x9x10 x11x12x13x14x15x16x17x18x19x20n因为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.12给出给出20个二维的样本，用个二维的样本，用k均值算法进行聚类。均值算法进行聚类。5.2.4 5.2.4 k-k-均值算法和均值算法和ISODATAISODATA算法算法图 5.12 k均值算法所用的样本模式123 456 78x
44、1x2011023456789910 x1x2x3x4x5x6x7x8x9x10 x11x12x13x14x15x16x17x18x19x20n结果与观察给定模式所得的结果是相符的。例例5.2 如图如图5.12给出给出20个二维的样本，用个二维的样本，用k均值算法进行聚类。均值算法进行聚类。5.2.4 5.2.4 k-k-均值算法和均值算法和ISODATAISODATA算法算法图 5.12 k均值算法所用的样本模式123 456 78x1x2011023456789910 x1x2x3x4x5x6x7x8x9x10 x11x12x13x14x15x16x17x18x19x20二、二、ISODA
45、TA算法算法nISODATA算 法(Iterative Self-organizing Data Analysis Techniques A迭代自组织数据分析技术)在k-均值算法基础上，在迭代过程中增加了某种产生和消除某些类别的方法，具有自动合并和分裂类，自动寻找类别数k的功能。n在每一次迭代时，首先，在不改变类别数目的前提下来改变分类，然后，将样本平均矢量之差小于某一预定阈值的每一类别对合并起来，或根据样本协方差矩阵来决定其分裂与否，一次一次地迭代，并不断地进行合并和分开，这种算法具有人机交互和启发式的特点。5.2.4 5.2.4 k-k-均值算法和均值算法和ISODATAISODATA算法
46、算法 算法参数n k 要找的聚类中心数；nN 每一类中至少应具有的样本个数（少于此值的样本点集去掉）；ns 类内的样本标准差阈值（判别类是否太大，若太大分2类），取总体分布各个特征分量轴上标准差i，取其一部分用i表示，01，i=1，2，N；5.2.4 5.2.4 k-k-均值算法和均值算法和ISODATAISODATA算法算法 算法参数n L 一次迭代运算中可合并的最多对数（一般取一对）；n I 允许迭代的次数（相当于k-均值算法中的M）；nc 两类中心距的最小距离（c，可合并）。5.2.4 5.2.4 k-k-均值算法和均值算法和ISODATAISODATA算法算法 算法步骤n基本步骤：n初
47、始化，任意选定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 5.2.4 k-k-均值算法和均值算法和ISODATAISODATA算法算法 算法步骤n对应于 的 的分量上加上一个给定量
48、 ，而 的其它分量保持不变来构成 ，对应于 的 的分量上减去 ，而 的其它分量保持不变来构成 。n规定 是 的一部分，。n选择 的基本要求是，使任意样本到这两个新的聚类中心 和 之间有一个足够可检测的距离差别，被区别并能完全将Xi分到 和 中。5.2.4 5.2.4 k-k-均值算法和均值算法和ISODATAISODATA算法算法 算法步骤n如果完成分裂，迭代次数加1，l=l+1。转。否则继续进行。n以下三步为合并：n计算全部的聚类中心的两两距离dij dij=|zi-zj|，ij，i，j=1，2，c n比较：如果dijc，转到第步，否则如果dijc，把当前L对聚类中心排序，di1j1，di2
49、j2，diLjL其中di1j1di2j2diLjL。5.2.4 5.2.4 k-k-均值算法和均值算法和ISODATAISODATA算法算法 算法步骤n从di1j1开始，逐对合并，算出新的聚类中心：n删去zil和zjl，并使c=c1。n注意：只允许一对对合并，并且一个聚类中心只能合并一次。l=1，2，L 5.2.4 5.2.4 k-k-均值算法和均值算法和ISODATAISODATA算法算法 算法步骤n迭代处理：如果是最后一次迭代，l=I，或zi(l+1)=zi(l)，算法结束。n输出 c个类别：Xi，zi，i=1，2，c。否则n l=l+1，转，不修改参数(可能l N，故无子类要去除。n更新
50、聚类中心z1计算 ，此时 。计算 ：因为这不是最后一次迭代且 ，(k=2，c=1)，所以转第八步。找X1的标准差5.2.4 5.2.4 k-k-均值算法和均值算法和ISODATAISODATA算法算法取 的最大值 。因 ，则z1分裂成两个新的聚类中心。5.2.4 5.2.4 k-k-均值算法和均值算法和ISODATAISODATA算法算法n第二次迭代n将样本模式重新分配给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.4 5.2.4 k-k