模式识别课件-聚类分析v10

第二章聚类分析分类与聚类的区别分类：用已知类别的样本训练集来设计分类器（监督学习）聚类（集群）：用事先不知类别的样本，而利用样本的先验知识来构造分类器（无监督学习）2.1聚类分析的概念基本思想：对一批没有标明类别及类数的模式样本集，根据模式间的相似程度，按照物以类聚、人以群分的思想，将相似的模式分为一类，不相似的分为另一类。特征的类型1.低层特征：①无序尺度：有明确的数量和数值。②有序尺度：有先后、好坏的次序关系，如酒分为上，中，下三个等级。③名义尺度：无数量、无次序关系，如有红，黄两种颜色2.中层特征：经过计算，变换得到的特征3.高层特征：在中层特征的基础上有目的的经过运算形成例如：椅子的重量=体积*比重体积与长，宽，高有关；比重与材料，纹理，颜色有关。这里低、中、高三层特征都有了。方法的有效性特征选取不当特征过少特征过多量纲问题主要聚类分析技术谱系法（系统聚类，层次聚类法）基于目标函数的聚类法（动态聚类）图论聚类法模糊聚类分析法2.2模式相似度度量各种距离表示相似性：①绝对值距离已知两个样本xi=(xi1,xi2,xi3,…,xin)Txj=(xj1,xj2,xj3,…,xjn)TnkjkikijXXd1||②欧几里德距离③明考夫斯基距离其中当q=1时为绝对值距离，当q=2时为欧氏距离nkjkikijXXd12nkjkikqijXXqqd1||1)(④切比雪夫距离q趋向无穷大时明氏距离的极限情况⑤马哈拉诺比斯距离其中xi，xj为特征向量，为协方差。使用的条件是样本符合正态分布||max)(1jkiknkijXXd1)(jijiTijXXXXMd⑥夹角余弦为xixj的均值即样本间夹角小的为一类，具有相似性例：x1,x2,x3的夹角如图：因为x1,x2的夹角小，所以x1,x2最相似。nkjknkiknkjkikijXXXXC12121x1x1x2x2x3⑦相关系数为xixj的均值注意：在求相关系数之前，要将数据标准化12211nkikjkikjknnkikjkikjkkXXXXrijXXXX2.3类的定义和与类间距离用距离进行定义类（书19）非监督学习方法分类1、基于概率密度函数估计的直接方法2、基于样本间相似性度量的间接聚类方法两类间的距离1、最短距离：两类中相距最近的两样品间的距离。ijxxpqdDqjpimin•2、最长距离：两类中相距最远的两个样本间的距离。•3、中间距离：最短距离和最长距离都有片面性，因此有时用中间距离。设ω1类和ω23类间的最短距离为d12，最长距离为d13，ω23类的长度为d23，则中间距离为：•上式推广为一般情况：ijxxpqdDqjpimax2231321220412121dddd12312d0d23d13d04121212231321220为参数，－其中dddd•4、重心距离：均值间的距离•5、类平均距离：两类中各个元素两两之间的距离平方相加后取平均值qjpipqxxijqpdNND221之间的距离类点与类点为样本数样本数其中jidNNqpijqqpp:,::6、离差平方和：设N个样品原分q类，则定义第i类的离差平方和为：离差平方和增量：设样本已分成ωp,ωq两类，若把ωp,ωq合为ωr类，则定义离差平方：.,)()(1类的样本数为第的均值为样品其中iNxxxxxxSiijiiijTiNjijqii2(),,pqrpqpqpqrrDSSSSSS其中分别为类与类的离差平方和为类的离差平方和增量愈小，合并愈合理。聚类准则类内距离越小越好类间距离越大越好一些准则函数MinJwMaxJBMaxSSTrJBw][11聚类分析三要素相似性(距离）测度聚类准则聚类算法2.4聚类的算法（1)根据相似性阈值和最小距离原则的简单聚类法（2）按照最小距离原则不断进行两类合并的方法（3）依据准则函数的动态动态聚类算法§系统聚类的算法•谱系聚类的算法•原理、步骤•例：如下图所示•1、设全部样本分为6类，•2、作距离矩阵D(0)3G1G2G5G4G6Gxω1ω2ω3ω4ω5ω29ω3116ω4491664ω5254364ω6642581193、求最小元素：4、把ω1,ω3合并ω7=(1,3)ω4,ω6合并ω8=(4,6)5、作距离矩阵D(1)16431ddω7ω2ω8ω29ω84916ω525446、若合并的类数没有达到要求，转3。否则停止。3、求最小元素：4、ω8,ω5,ω2合并,ω9=（2,5,4,6）45852dd枝状图15234678910§分解聚类分解聚类：把全部样本作为一类，然后根据相似性、相邻性分解。目标函数两类均值方差)()(212121xxxxTNNNEN：总样本数，：ω1类样本数：ω2类样本数，两类均值:,21xx1N2N分解聚类框图：初始分类调整分类方案最终结果目标函数达到最优先？NY对分算法：略例：已知21个样本，每个样本取二个特征，原始资料矩阵如下表：样本号12345678910x10022445667x265534312101112131415161718192021-4-2-3-3-5100-1-1-3322021-1-2-1-3-5∴目标函数0)()(212121xxxxNNNET∴)333.1714.0()0(1x)00()0(2x0,21)0(2)0(1NN解：第一次分类时计算所有样本，分别划到时的E值，找出最大的。1、开始时，G2),...,,(2121)0(1xxxG空G)0(22、分别计算当划入G2时的E值把划入G2时有2121,...,,xxx1x40.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(1ENxxxxx然后再把划入时对应的E值，找出一个最大的E值。把划为的E值最大。∴2132,...,,xxxG2G2x21),,...,,(2021)1(1xxxG)(21)1(2xG),65.19.0(1x1,20),53()1(2)1(12NNxE(1)=56.6再继续进行第二，第三次迭代…计算出E(2),E(3),…次数E值156.6279.16390.904102.615120.116137.157154.108176.159195.2610213.0711212.01G2G1x21x20x18x14x15x19x11x13x12x17x16第10次迭代划入时，E最大。于是分成以下两类：∴G2x17),,...,,(1610211xxxxG),,,,,,,,(212019181715,141312112xxxxxxxxxxG•每次分类后要重新计算的值。可用以下递推公式：21,xx)1/()()1/()()(2)(2)(2)1(2)(1)(1)(1)1(1kikkkkikkkNxxxxNxxxx为二类样品数时的两类均值划到从是下一次对分时把步对分时两类均值是第)(2)(1)(2)(1)1(2)1(1)(2)(1,,,,kkkkikkkkNNGGxxxkxx10x2x3x4x15x11x12x13x14x16x17x18x19x7x8x9x20x21x6x1x5x6543211234561X2X432156654321§动态聚类——兼顾系统聚类和分解聚类一、动态聚类的方法概要①先选定某种距离作为样本间的相似性的度量;②确定评价聚类结果的准则函数;③给出某种初始分类，然后用迭代法找出使准则函数取极值的最好的聚类结果。选代表点初始分类分类合理否最终分类修改分类YN动态聚类框图准则函数21ijcijjxJxz所有模式到所属类的类心的距离和二、代表点的选取方法：代表点就是初始分类的聚类中心数k①凭经验选代表点，根据问题的性质、数据分布，从直观上看来较合理的代表点k;②将全部样本随机分成k类，计算每类重心，把这些重心作为每类的代表点;③按密度大小选代表点：以每个样本作为球心，以d为半径做球形;落在球内的样本数称为该点的密度，并按密度大小排序。首先选密度最大的作为第一个代表点，即第一个聚类中心。再考虑第二大密度点，若第二大密度点距第一代表点的距离大于d1（人为规定的正数）则把第二大密度点作为第二代表点，，否则不能作为代表点，这样按密度大小考察下去，所选代表点间的距离都大于d1。d1太小，代表点太多，d1太大，代表点太小，一般选d1＝2d。对代表点内的密度一般要求大于T。T0为规定的一个正数。④用前k个样本点作为代表点。三、初始分类和调整①选一批代表点后，代表点就是聚类中心，计算其它样本到聚类中心的距离，把所有样本归于最近的聚类中心点，形成初始分类，再重新计算各聚类中心，称为成批处理法。②选一批代表点后,依次计算其它样本的归类，当计算完第一个样本时，把它归于最近的一类，形成新的分类。再计算新的聚类中心，再计算第二个样本到新的聚类中心的距离，对第二个样本归类。即每个样本的归类都改变一次聚类中心。此法称为逐个处理法。③直接用样本进行初始分类，先规定距离d,把第一个样品作为第一类的聚类中心，考察第二个样本，若第二个样本距第一个聚类中心距离小于d，就把第二个样本归于第一类，否则第二个样本就成为第二类的聚类中心，再考虑其它样本，根据样本到聚类中心距离大于还是小于d，决定分裂还是合并。④最佳初始分类。如图所示，随着初始分类k的增大，准则函数下降很快，经过拐点A后，下降速度减慢。拐点A就是最佳初始分类。准则函数JK最佳初始分类A拐点03217654下降快下降慢四、C－平均算法例：已知有20个样本，每个样本有2个特征，数据分布如下图第一步：令C=2，选初始聚类中心为TTxZxZ)0,1()1(;)0,0()1(2211样本序号x1x2x3x4x5x6x7x8x9x10特征x10101212367特征x20011122266x11x12x13x14x15x16x17x18x19x20867897898967777888991543126654321X101099887702X1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16x17x18x19x20x10001)1()1()1()1(10100)1(00000)1(121121112111＝））－（（＝所以因为＝））－（（＝＝））－（（＝第二步：ZxZxZxZxZxZx18,2),...,,()1(),,()1()1(......)1(,1)1(2)1()1(,2)1(1)1()1(,)1()1(0)01()01()1(2120542131122065206524241413231322221222NNxxxxGxxGZxxxxxxZxZxZxZxZxZxZxZxZxZx二、一、因此分为两类：都属于、、离计算出来，判断与第二个聚类中心的距、、同样把所有＝＝同理所以因为第三步：根据新分成的两类建立新的聚类中心TGxxxXNZ)5.0,0()10(21)10()00(21)(211)2(31)1(111TGxxxxxXNZ)33.5,67.5()...(1811)2(20542)1(222•第四步：•∵转第二步。•第二步：重新计算到z1(2),z2(2)的距离，把它们归为最近聚类中心，重新分为两类，)(2,1),1()2(新旧聚类中心不等JZZJJ2021,...,,xxx第三步，更新聚类中心TGxxxxxXNZ)13.1,25.1