模式识别导论(六)

1、 第六章 聚类分析 61 分类与聚类的区别 分类：用已知类别的样本训练集来设计分类器（监督学习） 聚类（集群）：用事先不知样本的类别，而利用样本的先验知识来构造分类器（无监督学习）6-2 系统聚类 系统聚类：先把每个样本作为一类，然后根据它们间的相似性和相邻性聚合。 相似性、相邻性一般用距离表示 （1）两类间的距离 1、最短距离：两类中相距最近的两样品间的距离。ijxxpqdDqjpi min 2、最长距离 ：两类中相距最远的两个样本间的距离。 3、中间距离：最短距离和最长距离都有片面性，因此有时用中间距离。设1类和23类间的最短距离为d12，最长距离为d13， 23类的长度为d23，则中间距

2、离为：上式推广为一般情况：ijxxpqdDqjpi max2231321220412121dddd12312d0d23d13d04121212231321220为参数，其中dddd 4、重心距离：均值间的距离 5、类平均距离：两类中各个元素两两之间的距离平方相加后取平均值 qjpipqxxijqpdNND221之间的距离类点与类点为样本数样本数其中jidNNqpijqqpp:,: 6、 离差平方和： 设N个样品原分q类，则定义第i类的离差平方和为： 离差平方和增量：设样本已分成p,q两类，若把p,q合为r类，则定义离差平方： .,)()(1类的样本数为第的均值为样品其中iNxxxxxxSiij

3、iiijTiNjijqii。增量愈小，合并愈合理类的离差平方和为类的离差平方和类于分别为其中rrqpqpqprpqSSSSSSD,)(2 （2）系统聚类的算法（略） 例：如下图所示 1、设全部样本分为6类， 2、作距离矩阵D(0)3G1G2G5G4G6Gx1234529311644916645254364664258119 3、求最小元素： 4、把1,3合并7=(1,3) 4,6合并8=(4,6) 5、作距离矩阵D(1)16431 dd728298491652544 6、若合并的类数没有达到要求，转3。否则停止。 3、求最小元素： 4、8,5,2合并, 9=（2,5,4,6）45852 dd枝

4、状图152346789106-2 分解聚类 分解聚类：把全部样本作为一类，然后根据相似性、相邻性分解。 目标函数 两类均值方差 )()(212121xxxxTNNNEN：总样本数， ：1类样本数 ：2类样本数，两类均值:,21xx1N2Nv分解聚类框图：初始分类调整分类方案最终结果目标函数达到最优？NY 对分算法：略 例：已知21个样本，每个样本取二个特征，原始资料矩阵如下表： 样本号 12345678910 x10022445667x2655343121011 12 13 14 15 16 17 18 19 20 21-4-2-3-3-5100-1-1-3322021-1-2 -1-3-5目

5、标函数0)()(212121xxxxNNNET)333. 1714. 0()0(1x)00()0(2x0,21)0(2)0(1NN解：第一次分类时计算所有样本，分别划到时的E值，找出最大的。1、开始时，G2),.,(2121)0(1xxxG空G)0(2 2、分别计算当 划入G2 时的E值把 划入G2时有2121,.,xxx1x40.23)610.1(75.021120)60(),10.175.0()121()60()333.1714.0()333.1714.0(122)1(2)0(11)0(1)0(1)1(1ENxxxxx 然后再把 划入 时对应的E值，找出一个最大的E值。 把 划为 的E值最

6、大。 2132,.,xxxG2G2x21),.,(2021)1(1xxxG)(21)1(2xG),65.19.0(1x1,20),53()1(2)1(12NNxE(1)=56.6再继续进行第二，第三次迭代计算出 E(2) , E(3) , 次数 E值 1 56.6 2 79.16 3 90.90 4 102.61 5 120.11 6 137.15 7 154.10 8 176.15 9 195.26 10 213.07 11 212.01G2G1x21x20 x18x14x15x19x11x13x12x17x16 第10次迭代 划入 时，E最大。于是分成以下两类： G2x17),.,(161

7、0211xxxxG ),(212019181715,141312112xxxxxxxxxxG 每次分类后要重新计算 的值。可用以下递推公式：21, xx)1/()()1/()()(2)(2)(2)1(2)(1)(1)(1)1(1kikkkkikkkNxxxxNxxxx为二类样品数时的两类均值划到从是下一次对分时把步对分时两类均值是第)(2)(1)(2)(1)1(2)1(1)(2)(1,kkkkikkkkNNGGxxxkxx10 x2x3x4x15x11x12x13x14x16x17x18x19x7x8x9x20 x21x6x1x5x6543211234561X2X432156654321 作业

8、： 样本 1 2 3 4 5 6 7 8 0 2 1 5 6 5 6 7 0 2 1 3 3 4 4 5 用对分法编程上机，分成两类画出图形。 1x2x6-3 动态聚类兼顾系统聚类和分解聚类一、动态聚类的方法概要 先选定某种距离作为样本间的相似性的度量; 确定评价聚类结果的准则函数; 给出某种初始分类，用迭代法找出使准则函数取极值的最好的聚类结果。选代表点初始分类分类合理否最终分类修改分类YN动态聚类框图 二、代表点的选取方法：代表点就是初始分类的聚类中心数k 凭经验选代表点，根据问题的性质、数据分布，从直观上看来较合理的代表点k; 将全部样本随机分成k类，计算每类重心，把这些重心作为每类的代

9、表点; 按密度大小选代表点： 以每个样本作为球心，以d为半径做球形;落在球内的样本数称为该点的密度，并按密度大小排序。首先选密度最大的作为第一个代表点，即第一个聚类中心。再考虑第二大密度点，若第二大密度点距第一代表点的距离大于d1（人为规定的正数）则把第二大密度点作为第二代表点，否则不能作为代表点，这样按密度大小考察下去，所选代表点间的距离都大于d1。d1太小，代表点太多，d1太大，代表点太小，一般选d12d。对代表点内的密度一般要求大于T。T0为规定的一个正数。 用前k个样本点作为代表点。 三、初始分类和调整 选一批代表点后，代表点就是聚类中心，计算其它样本到聚类中心的距离，把所有样本归于最

10、近的聚类中心点，形成初始分类，再重新计算各聚类中心，称为成批处理法。 选一批代表点后,依次计算其它样本的归类，当计算完第一个样本时，把它归于最近的一类，形成新的分类。再计算新的聚类中心，再计算第二个样本到新的聚类中心的距离，对第二个样本归类。即每个样本的归类都改变一次聚类中心。此法称为逐个处理法。 直接用样本进行初始分类，先规定距离d,把第一个样品作为第一类的聚类中心，考察第二个样本，若第二个样本距第一个聚类中心距离小于d，就把第二个样本归于第一类，否则第二个样本就成为第二类的聚类中心，再考虑其它样本，根据样本到聚类中心距离大于还是小于d，决定分裂还是合并。 最佳初始分类。 如图所示，随着初始

11、分类k的增大，准则函数下降很快，经过拐点A后，下降速度减慢。拐点A就是最佳初始分类。准则函数JK最佳初始分类A拐点03217654下降快下降慢 四、K次平均算法：成批处理法（ 算法略） 例：已知有20个样本，每个样本有2个特征，数据分布如下图第一步：令K=2，选初始聚类中心为TTxZxZ)0,1()1(;)0,0()1(2211样本序号x1x2x3x4x5x6x7x8x9x10特征x10101212367特征x20011122266x11x12x13x14x15x16x17x18x19x20867897898967777888991543126654321X101099887702X1x2x3

12、x4x5x6x7x8x9x10 x11x12x13x14x15x16x17x18x19x20 x10001)1 ()1 ()1 ()1 (10100)1 (00000)1 (121121112111）（所以因为）（）（第二步：ZxZxZxZxZxZx18,2),.,()1 (),()1 ()1 (.)1 (, 1)1 (2)1 ()1 (,2)1 (1)1 ()1 (,)1 ()1 (0)01()01()1 (2120542131122065206524241413231322221222NNxxxxGxxGZxxxxxxZxZxZxZxZxZxZxZxZxZx二、一、因此分为两类：都属于、离

13、计算出来，判断与第二个聚类中心的距、同样把所有同理所以因为 第三步：根据新分成的两类建立新的聚类中心TGxxxXNZ)5 . 0 , 0()10(21)10()00(21)(211)2(31)1(111TGxxxxxXNZ)33.5,67.5().(1811)2(20542)1(222 第四步： 转第二步。 第二步：重新计算 到z1(2) , z2(2) 的距离，把它们归为最近聚类中心，重新分为两类，)(2 , 1),1 ()2(新旧聚类中心不等JZZJJ2021,.,xxx 第三步，更新聚类中心TGxxxxxXNZ)13. 1 ,25. 1 ().(811) 3(8321)2(111TGxxxxXNZ)33. 7 ,67. 7().(1211) 3(20109)2(2228),.,()2(18211NxxxG12),.,()2(2201092NxxxG 第四步， 第二步， 第三步，更新聚类中心转第二步因, 2 , 1),2() 3(jZZjj12, 8),.,()4(),.,()4(,.,)3(),3(,.,2120109282112021212021NNxxxGxxxGxxxZZxxx重新分