聚类分析基本讲义

聚类分析•“物以类聚，人以群分”。对事物进行分类，是人们认识事物的出发点，也是人们认识世界的一种重要方法。因此，分类学已成为人们认识世界的一门基础科学。•在生物、经济、社会、人口等领域的研究中，存在着大量量化分类研究。例如：在生物学中，为了研究生物的演变，生物学家需要根据各种生物不同的特征对生物进行分类。在经济研究中，为了研究不同地区城镇居民生活中的收入和消费情况，往往需要划分不同的类型去研究。在地质学中，为了研究矿物勘探，需要根据各种矿石的化学和物理性质和所含化学成分把它们归于不同的矿石类。在人口学研究中，需要构造人口生育分类模式、人口死亡分类状况，以此来研究人口的生育和死亡规律。32.1聚类的基本概念似圆度2.1.1聚类分析的基本思想ClusteringAnalysis据相似程度分类无监督分类（Unsupervised）1x2x42.1聚类的基本概念2.1.2特征量的类型物理量：直接反映特征的实际物理意义如:长度、重量、速度等。处理前需要离散化。次序量：按某种规则确定的只反映特征的次序关系或等级如:产品的等级、病症的级或期。已是离散量。名义量：反映样本的状态特征非数值的，如男性与女性、事物的状态、种类等。需要数值化。这些特征的数值指标既无数量含义，也无次序关系，只是用数字代表各种状态。52.1聚类的基本概念2.1.3方法的有效性(1)特征选取不当或不足使分类无效；(2)特征选取过多可能有害无益，且增加分析负担。x1(a)12213x1x2x2(b)62.1聚类的基本概念(3)特征量纲对聚类结果的影响财富（万）510年龄6030财富（十万）年龄603051072.1.4聚类准则对聚类结果的影响羊,狗,猫,鲨鱼蜥蜴,蛇,麻雀，海鸥,金鱼,青蛙(a)繁衍后代的方式金鱼,鲨鱼羊,狗,猫,蜥蜴,蛇,麻雀，海鸥,青蛙(b)肺的存在金鱼,鲨鱼羊,狗,猫,蜥蜴,蛇,麻雀，海鸥,青蛙(c)生存环境金鱼蜥蜴,蛇,麻雀，海鸥,青蛙(d)繁衍后代的方式和是否存在肺鲨鱼羊,狗,猫,2.1聚类的基本概念2.1.5距离测度对聚类结果的影响2.1聚类的基本概念8数据的粗聚类是两类,细聚类为4类92.2模式相似性测度2.2.1距离测度2.2.2相似测度2.2.3匹配测度•在聚类之前，要首先分析样品间的相似性，常用距离来测度样品之间的相似程度。每个样品有p个指标（变量）从不同方面描述其性质，形成一个p维的向量。如果把n个样品看成p维空间中的n个点，则两个样品间相似程度就可用p维空间中的两点距离公式来度量。两点距离公式可以从不同角度进行定义。112.2.1距离测度(差值测度)Distance(orDissimilarity)Measure设特征矢量和的距离为则一般应满足如下公理x(,)0,(,)=0dxyxydxyxy当且仅当时等号成立，即y(,)dxy(,)dxy(,)=(,)dxydyx(,)(,)(,)dxydxzdzy(1)(2)(3)(triangularinequality)12（一）距离测度(差值测度)⑴欧氏(Euclidean)距离1212(,,,)'(,,,)'nnxxxxyyyy设，21/21(,)[()]niiidxyxyxy⑵绝对值距离(街坊距离或Manhattan距离)1(,)||niiidxyxy(3)切氏(Chebyshev)距离(,)max||iiidxyxy13（一）距离测度(差值测度)(4)明氏(Minkowski)距离1/1(,)[()]nmmiiidxyxy(5)Cambera距离(Lance距离、Willims距离)1||(,)(,0,0)||niiiiiiiiixydxyxyxyxy该距离能克服量纲的影响，但不能克服分量间的相关性。14（一）距离测度(差值测度)(6)马氏(Mahalanobis)距离21(,)()'()ijijijdxxxxVxx11()()'1miiiVxxxxm11miixxm其中（协方差矩阵的无偏估计）（均值向量的估计）性质：对一切非奇异线性变换都是不变的。即，具有坐标系比例、旋转、平移不变性，并且从统计意义上尽量去掉了分量间的相关性。15马氏距离的一般定义设、是从期望矢量为、协方差矩阵为的母体G中抽取的两个样本，则它们间的马氏距离定义为当和是分别来自两个数据集中的样本时，设C是它们的互协方差阵，则它们间的马氏距离定义为21(,)()'()dxyxyxyxyxy21(,)()'()dxyxyCxy当、V、C为单位矩阵时，马氏距离欧氏距离。对于正态分布，等概率密度点轨迹是到均值矢量的马氏距离为常数的点所构成的超椭球面。16例2.1求点和至均值点的距离。解：由题设，可得从而马氏距离它们之比达倍。若用欧氏距离，则算得的距离值相同：由分布函数知，A、B两点的概率密度分别为010.9,00.91N1:1A1:1B0:0M10.90.91110.910.910.192110.2(,)110.191MdAM2113.8(,)110.191MdBM192(,)2EdAM2(,)2EdBM(1,1)0.2157p(1,1)0.00001658p已知一个二维正态母体G的分布为距离选择的原则一般说来，同一批数据采用不同的距离公式，会得到不同的分类结果。产生不同结果的原因，主要是由于不同的距离公式的侧重点和实际意义都有不同。因此我们在进行聚类分析时，应注意距离公式的选择。通常选择距离公式应注意遵循以下的基本原则：（1）要考虑所选择的距离公式在实际应用中有明确的意义。如欧氏距离就有非常明确的空间距离概念。马氏距离有消除量纲影响的作用。（2）要综合考虑对样本观测数据的预处理和将要采用的聚类分析方法。如在进行聚类分析之前已经对变量作了标准化处理，则通常就可采用欧氏距离。（3）要考虑研究对象的特点和计算量的大小。样品间距离公式的选择是一个比较复杂且带有一定主观性的问题，我们应根据研究对象的特点不同做出具体分折。实际中，聚类分析前不妨试探性地多选择几个距离公式分别进行聚类，然后对聚类分析的结果进行对比分析，以确定最合适的距离测度方法。多元数据中的变量表现为向量形式，在几何上可用多维空间中的一个有向线段表示。在对多元数据进行分析时，相对于数据的大小，我们更多地对变量的变化趋势或方向感兴趣。因此，变量间的相似性，我们可以从它们的方向趋同性或“相关性”进行考察，从而得到“夹角余弦法”和“相关系数”等度量方法。192.2.2相似测度•重点考虑两矢量的方向是否相近，而忽略矢量长度。(1)角度相似系数(夹角余弦）矢量之间的相似性可用它们的夹角余弦来度量1/2''cos(,)[(')(')]xyxyxyxyxxyy1/2()'()(,)[()'()()'()]xxyyrxyxxxxyyyy(2)相关系数数据中心化后的矢量夹角余弦性质：相关系数具有坐标系平移、旋转、比例不变性。20221()13(,)exp[]4niiiixyexyn性质：不受量纲变化的影响。(3)指数相关系数这里假设和的维数n相同、概率分布相同。是第i个分量的方差。xy2i无论是夹角余弦还是相关系数，它们的绝对值都小于1，作为变量近似性的度量工具，我们把它们统记为cij。当∣cij∣=1时，说明变量Xi与Xj完全相似；当∣cij∣近似于1时，说明变量Xi与Xj非常密切；当∣cij∣=0时，说明变量Xi与Xj完全不一样；当∣cij∣近似于0时，说明变量Xi与Xj差别很大。据此，我们把比较相似的变量聚为一类，把不太相似的变量归到不同的类内。在实际聚类过程中，为了计算方便，我们把变量间相似性的度量公式作一个变换为dij=1∣cij∣或者dij2=1cij2用表示变量间的距离远近，小则与先聚成一类，这比较符合人们的一般思维习惯。22（三）匹配测度若特征只有两个状态：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维特征矢量可定义如下相似性测度：23（三）匹配测度(1)Tanimoto测度(1-1)匹配的特征数目(0-1)匹配的特征数目(1-0)匹配的特征数目(0-0)匹配的特征数目(1)(1)(1)(1)iiiiiiiiiiiiaxybyxcxyexy令'(,)'''axysxyabcxxyyxy注意，这里只考虑（1-1）匹配，而不考虑（0-0）匹配。24（三）匹配测度(2)Rao测度(3)简单匹配系数(4)Dice系数(5)Kulzinsky系数'(,)axysxyabcen(,)aemxyn（1-1）匹配特征数目与特征总数之比22'(,)2''axymxyabcxxyy'(,)''2'axymxybcxxyyxy（1-1）匹配+（0-0）匹配/特征总数只对（1-1）匹配加权（1-1）匹配/（1-0）匹配+（0-1）匹配25例2.2设(1)Tanimoto测度(2)Rao测度(3)简单匹配测度(4)Dice系数(5)Kulzinsky系数(,1,0,,1,0)'(,0,011,,00,1)'1xy'3,'3,'1xxyyxy'1(,)6xysxyn111(,)63aemxyn2'21(,)''333xymxyxxyy'1(,)''2'4xymxyxxyyxy则'11(,)'''3315xysxyxxyyxy26小结一、影响分类的因数（1）分类准则；（2）特征量的选择；（3）量纲。二、模式相似性测度（一）距离测度(1)欧氏距离(2)马氏距离对坐标系平移、旋转、比例不变。（二）相似测度相关系数（特征矢量的方向）对坐标系平移、旋转、比例不变。（三）匹配测度（0-1）匹配系数21(,)()'()ijijijdxxxxVxx1/2()'()(,)[()'()()'()]xxyyrxyxxxxyyyy272.3类的定义与类间距离2.3.1类的定义类的划分具有人为规定性，这反映在类的定义的选取及参数的选择上。分类结果的优劣最后只能根据实际来评价。定义1设集合S中任意元素xi与xj间的距离dij有dijh其中h为给定的阈值，称S对于阈值h组成一类。11jijxSdhk定义2其中k为S中元素的个数。（类内平均距离）282.3.1类的定义定义3设集合S中任意元素xi与xj间的距离dij有其中k为S中元素的个数，称S对于阈值h,r组成一类。1(1)ijijxSxSijdhkkdr定义4xiS，xjS，使dijh成立，则称S对于阈值h组成一类。（最近距离）定义5若将集合S任意分成两类S1，S2，这两类间的距离D(S1,S2)h，则称S对于阈值h组成一类。292.3.2类间距离测度（一）最近距离两个聚类k和l之间的最近距离定义为式中，dij表示xik与xjl间的距离。如果l由p和q两类合并而成，则有递推公式,min[]klijijDdmin[,]klkpkqDDD302.3.2类间距离测度（二）最远距离递推公式,max[]klijijDdmax[,]klkpkqDDD312.3.2类间距离测度（三）中间距离递推公式2222111224klkpkqpqDDDDpqkpqkpqDkqDklDkpDl322.3.2类间距离测度（四）重心距离递推公式式中，和分别是i和j的重心，i,j