7 第七章 聚类分析

1第七章聚类分析分类与聚类的区别分类：用已知类别的样本训练集来设计分类器（监督学习）聚类（集群）：事先不知样本的类别，而利用样本的先验知识来构造分类器（无监督学习）27.1聚类的基本概念7.2模式相似性测度7.3类的定义与类间距离7.4聚类算法启发式聚类：简单聚类层次（分级）聚类（hierarchicalclustering):分裂聚类、合并聚类、动态聚类。其它聚类算法337.1聚类的基本概念似圆度7.1.1聚类分析的基本思想据相似程度聚类无监督聚类（Unsupervised）1x2x447.1.2聚类准则对聚类结果的影响羊,狗,猫,鲨鱼蜥蜴,蛇,麻雀，海鸥,金鱼,青蛙(a)繁衍后代的方式金鱼,鲨鱼羊,狗,猫,蜥蜴,蛇,麻雀，海鸥,青蛙(b)肺的存在金鱼,鲨鱼羊,狗,猫,蜥蜴,蛇,麻雀，海鸥,青蛙(c)生存环境金鱼蜥蜴,蛇,麻雀，海鸥,青蛙(d)繁衍后代的方式和是否存在肺鲨鱼羊,狗,猫,7.1聚类的基本概念57.1.3距离测度对聚类结果的影响2.1聚类的基本概念5数据的粗聚类是两类,细聚类为4类667.2模式相似性测度7.2.1距离测度7.2.2相似测度7.2.3匹配测度777.2.1距离测度(差值测度)Distance(orDissimilarity)Measure设特征矢量和的距离为则一般应满足如下公理x(,)0,(,)=0dxyxydxyxy当且仅当时等号成立，即y(,)dxy(,)dxy(,)=(,)dxydyx(,)(,)(,)dxydxzdzy(1)(2)(3)(triangularinequality)8距离测度(差值测度)⑴欧氏(Euclidean)距离1212(,,,)(,,,)TTnnxxxxyyyy设，21/21(,)[()]niiidxyxyxy⑵绝对值距离(街坊距离或Manhattan距离)1(,)||niiidxyxy(3)切氏(Chebyshev)距离(,)max||iiidxyxy9距离测度(差值测度)(4)明氏(Minkowski)距离1/1(,)[()]nmmiiidxyxy(5)Cambera距离(Lance距离、Willims距离)1||(,)(,0,0)||niiiiiiiiixydxyxyxyxy该距离能克服量纲的影响，但不能克服分量间的相关性。10距离测度(差值测度)(6)马氏(Mahalanobis)距离21(,)()()TijijijdxxxxVxx11()()1mTiiiVxxxxm11miixxm其中（协方差矩阵的无偏估计）（均值向量的估计）性质：对一切非奇异线性变换都是不变的。即，具有坐标系比例、旋转、平移不变性，并且从统计意义上尽量去掉了分量间的相关性。11马氏距离具有线性变换不变性证明：设，有非奇异线性变换：则yAx111111mmmiiiiiiyyAxAxAxmmm11111()()11()()11()()11[()()]1mTyiiimTiiimTTiiimTTTiixiVyyyymAxAxAxAxmAxxxxAmAxxxxAAVAm12故1111112211()()()()()()()()()()()(,)())(()(),TijyijTijyijTTijyijTTTijxijTTTijxijTijxixijijyjyyVyyAxAxVAxAxxxAVAxxxxAAVAAxxxxAAVAAxxxxVdxxyyxdx111{()}ABBA13马氏距离的一般定义设、是从期望矢量为、协方差矩阵为的母体G中抽取的两个样本，则它们间的马氏距离定义为当和是分别来自两个数据集中的样本时，设C是它们的互协方差阵，则它们间的马氏距离定义为21(,)()()Tdxyxyxyxyxy21(,)()()TdxyxyCxy当、V、C为单位矩阵时，马氏距离欧氏距离。对于正态分布，等概率密度点轨迹是到均值矢量的马氏距离为常数的点所构成的超椭球面。147.2.2相似测度•重点考虑两矢量的方向是否相近，而忽略矢量长度。(1)角度相似系数(夹角余弦）矢量之间的相似性可用它们的夹角余弦来度量1/2cos(,)[()()]TTTTxyxyxyxyxxyy1/2()()(,)[()()()()]TTTxxyyrxyxxxxyyyy(2)相关系数数据中心化后的矢量夹角余弦性质：相关系数具有坐标系平移、旋转、比例不变性。1515221()13(,)exp[]4niiiixyexyn性质：不受量纲变化的影响。(3)指数相关系数这里假设和的维数n相同、概率分布相同。是第i个分量的方差。xy2i167.2.3匹配测度若特征只有两个状态：0=有此特征；1=无此特征。称之为二值特征。对于给定的二值特征矢量x和y中的某两个相对应的分量xi与yj若xi=1,yj=1，则称xi与yj(1-1)匹配；若xi=1,yj=0，则称(1-0)匹配；若xi=0,yj=1，则称(0-1)匹配；若xi=0,yj=0，则称(0-0)匹配。对于二值n维特征矢量可定义如下相似性测度：17匹配测度(1)Tanimoto测度(1-1)匹配的特征数目(0-1)匹配的特征数目(1-0)匹配的特征数目(0-0)匹配的特征数目(1)(1)(1)(1)iiiiiiiiiiiiaxybyxcxyexy令(,)TTTTaxysxyabcxxyyxy注意，这里只考虑（1-1）匹配，而不考虑（0-0）匹配。18匹配测度(2)Rao测度(3)简单匹配系数(4)Dice系数(5)Kulzinsky系数(,)Taxysxyabcen(,)aemxyn（1-1）匹配特征数目与特征总数之比22(,)2TTTaxymxyabcxxyy(,)2TTTTaxymxybcxxyyxy（1-1）匹配+（0-0）匹配/特征总数只对（1-1）匹配加权（1-1）匹配/（1-0）匹配+（0-1）匹配1919例1设(1)Tanimoto测度(2)Rao测度(3)简单匹配测度(4)Dice系数(5)Kulzinsky系数(,1,0,,1,0)(,0,1,,0001,1)1TTxy3,3,1TTTxxyyxy1(,)6Txysxyn111(,)63aemxyn221(,)333TTTxymxyxxyy1(,)24TTTTxymxyxxyyxy则11(,)3315TTTTxysxyxxyyxy207.3类的定义与类间距离217.3.2类间距离测度方法⑴最近距离法⑵最远距离法⑶中间距离法⑷重心距离法⑸平均距离法⑹离差平方和法2222,min[]klijijDdmin[,]klkpkqDDDkpq23（二）最远距离递推公式,max[]klijijDdmax[,]klkpkqDDDkpq24（三）中间距离递推公式2222111224klkpkqpqDDDDpqkpqkpqDkqDklDkpDl25（四）重心距离递推公式式中，和分别是i和j的重心，i,j=k,l,p,q。22222()klkpkqpqpqpqpqpqpqnnnnDDDDnnnnnn2()()TijijijDxxxxixjx26（五）平均距离两类p和q间的距离平方定义为这两类元素两两之间的平均平方距离，即设l=pq，类平均距离的递推公式为22,1pqipjpijxxpqDdnn222klkpkqpqpqpqnnDDDnnnn2727（六）离差平方和法设类t的重心是，t的类内离差平方和定义为设l=pq，则sl要变大。把两类合并所增加的离差平方和定义为两类平方距离，即，可以证明k与l=pq的离差平方和的递推公式2222klkpkqpqkpkqkklklklnnnnnDDDDnnnnnntx()()itTtititxsxxxx2pqlpqDsss2()()pqTpqpqpqpqnnDxxxxnn28222222kqkppqkqqkppklDDDDDD最近距离法1/21/20-1/2最远距离法1/21/201/2中间距离法1/21/2-1/40重心距离法0平均距离法00可变平均法0可变法0离差平方和法0pqqppnnnqpqnnnqpqppnnnqpqnnnqppnnn)1(qpqnnn)1(112121lkpknnnnlkqknnnnlkknnn297.3.3聚类准则函数评估分类过程或分类结果优劣的准则函数（一）类内距离准则（误差平方和准则）2()()()1111()()minjjnnccjjTjWijijijjijiJxmxmxm()11(1,2,,)jnjjiijmxjcn()1,(1,2,,),cjijjjxjcnN式中，nj是j中的样本个数，加权类内距离准则21cjWWjjnJdN＝()()22()()2(1)jkjjijjjjikxjjxdxxnn式中，是j内样本间的均方距离。适用于各类模式呈团状分布的情况。302.3.3聚类准则函数（二）类间距离准则1()()maxcTBjjjJmmmm()11(1,2,,)jnjjiijmxjcn式中，是总的样本均值矢量，加权类间距离准则11NiimxN1()()maxcjTWBjjjnJmmmmN对于两类问题，可以定义21212()()TBJmmmm1222WBBnnJJN31（三）基于类内类间距离的准则函数构造能同时使Jwmin和JBmax的准则函数类内离差矩阵（ScatterMatrix）()()()()()1111()(),,,(1,2,,)jjnnjjjTjjWijijijjiiijjSxmxmxmxjcnn总的类内离差矩阵()1cjjWWjnSSN总的离差矩阵11()()NTTiiiSxmxmN13452m1m类间离差矩阵1()()cjTBjjjnSmmmmN11NiimxN3232ST=SW+SB证明：1()()11()()11()()()11()()1()()1()()1[()()2()()()(jjNTTiiincjjjTiijijncjjjTijjijjjijcjjjTjTijijjijjjjjSxmxmNnxmxmNnnxmmmxmmmNnnxmxmmmxmmmmNn1()()()111()()111)]11[()()2()()()()]1[()()2()()()()]jjjjnTinncjjjTjTTijijjijjjjiijjncjjjTTTijijjjjjjjijcjWjmnxmxmmmxmmmmmNnnnxmxmmmmmmmmmNnnSN()1()()cjjTjjjWBnmmmmNSS33（三）基于类内类间距离的准则函数聚类的基本目标是使JWB=Tr[SB]max和JWW=Tr[SW]min因此可定义如下聚类准则函数11WBJTrSS12WBJSS13WTJTrSS14WTJSSJimax，(i=1,2,3,4)即，类内越“紧”，类间越“开”，聚类效果越好。347·4聚类算法(1)简单聚类方法(2)分裂聚类法(4)动态聚类法(3)合并聚类法357·4简单