模式识别导论.pptxVIP

1 §6-2 系统聚类 系统聚类：先把每个样本作为一类，然后根据它们间的相 似性和相邻性聚合。 相似性、相邻性一般用距离表示 （1）两类间的距离 1、最短距离：两类中相距最近的两样品间的距离。 第1页/共53页 2 2、最长距离 ：两类中相距最远的两个样本间的距离。 3、中间距离：最短距离和最长距离都有片面性，因此有时用中间距离。设ω1类和ω23类间的最短距离为d12，最长距离为d13，ω 23类的长度为d23，则中间距离为： 上式推广为一般情况： 第2页/共53页 3 4、重心距离：均值间的距离 5、类平均距离：两类中各个元素两两之间的距离平方相加后取平均值 第3页/共53页 4 6、 离差平方和： 设N个样品原分q类，则定义第i类的离差平方和为： 离差平方和增量：设样本已分成ωp,ωq两类，若把ωp,ωq合为ωr类，则定义离差平方： 第4页/共53页 5 （2）系统聚类的算法 设参加聚类的样本共N个，先选定样本间距离和类间距离的计算公式，再按以下步骤聚类。 1、假定N个样本各成一类，记作ω1,ω2,……ωN。 2、作距离矩阵D(0),因D(0)矩阵是对称的N×N矩阵，我们　　　　只计算下三角部分，第i行第j列处的元素dij用i和j两样本的距离平方表示。 第5页/共53页 6 3、求D(0)的最小元素 dpq＝min dij p≠q 因此， ω p和ω q是目前最近的两类。 4、把ω p与ω q合并成新的类，并求新类与原有其它各类间的距离。 5、作下一距离矩阵D(1)。 6、若分的类数已满足预先要求或全部样本已合成一类，则算法结束。否则，重复以上步骤。 ω1 ω2 …… ω2 ω3 d2ij …. 第6页/共53页 7 例：有六个样本X={x1,x2,x3,x4,x5,x6} 其分布如下图所示 ： 1、设全部样本分为6类， 2、作距离矩阵D(0) ω1 ω2 ω3 ω4 ω5 ω2 9 ω3 1 16 ω4 49 16 64 ω5 25 4 36 4 ω6 64 25 81 1 9 第7页/共53页 8 3、求最小元素： 4、把ω1,ω3合并ω7=(1,3) ω4,ω6合并ω8=(4,6) 5、作距离矩阵D(1) ω7 ω2 ω8 ω2 9 ω8 49 16 ω5 25 4 4 第8页/共53页 9 6、若合并的类数没有达到要求，转3。否则停止。 3、求最小元素： 4、ω8,ω5,ω2合并, ω9=（2,5,4,6） 第9页/共53页 10 §6-2 分解聚类 分解聚类：把全部样本作为一类，然后根据相似性、相邻性分解。 目标函数 两类均值方差 N：总样本数， ：ω1类样本数 ：ω2类样本数， 第10页/共53页 11 分解聚类框图： 第11页/共53页 12 对分算法： 1、选取目标函数，把全体样品分成两类 2、分别计算把x1,x2,……,xN并入G2类时的E值，设当xi并入G2时的E值最大，则把它并入G2得: 3、再分别计算把x1,…,xi-1, xi+1 ……,xN并入G2的E值，若当xj并入G2时E最大，则并入G2得： 第12页/共53页 13 4、若E(k+1)≥E(k),则重复上述步骤，直到某个E(K)达到最大值为止。这时最好的分类是G 1(k) 共有n-k个样品， G 2(k)有k个样品。 每次分类后都要重新计算 之值。可用以下递推公式： 第13页/共53页 14 例：已知21个样本，每个样本取二个特征，原始资料矩阵如下表： 样本号 1 2 3 4 5 6 7 8 9 10 x1 0 0 2 2 4 4 5 6 6 7 x2 6 5 5 3 4 3 1 2 1 0 11 12 13 14 15 16 17 18 19 20 21 -4 -2 -3 -3 -5 1 0 0 -1 -1 -3 3 2 2 0 2 1 -1 -2 -1 -3 -5 第14页/共53页 15 解：第一次分类时计算所有样本，分别划到G2时的E值，找出最大的。 1、开始时， ∴目标函数 2、分别计算当x1,x2,….x21划入G2时的E值。把x1划入G2时有：利用递推公式 第15页/共53页 16 然后再把x2,….x21划入G2时对应的E值，计算出来进行比较，找出一个最大的E值。即把x21划为G2的E值最大。 ∴ 　　再继续进行第二，第三次迭代…… 　　计算出E(2),E(3),…… 　　如下表： 第16页/共53页 17 第17页/共53页 18 第10次迭代x1划入G2时，E最大。于是分成以下 　两类： ∴ 第18页/共53页 19 作业：