82聚类分析

SWUFE1聚类分析张英1SWUFE2居民月平均消费数据SWUFE3要点•聚类分析思想•主要聚类方法•相关问题讨论SWUFE4聚类分析的基本思想对没有目标变量的数据集根据数据的相似性给出“自然的”分组。目标：类内对象相似性尽量大，类间对象相似性尽量小。根据结果类的分离性，聚类分为重叠聚类与互斥聚类。根据能否得到类的层次关系，聚类分为层次聚类（或嵌套聚类）和划分聚类。根据结果类是否包含所有对象，聚类分为完全聚类和部分聚类。SWUFE55数据的自然分组举例SWUFE6主要聚类方法•划分的方法•层次的方法•基于密度的方法•基于网格的方法•基于模型的方法SWUFE7层次聚类（谱系聚类）凝聚方法（自底向上)将每个对象作为单独的一类，然后合并最近的两个类为一个类，如此循环，直到合成一个类，或达到终止条件为止。分裂方法（自顶向下）将所有的对象看做一个类，然后分解成两个离得最远的类，对新类循环分解，直到一个类只包含一个对象，或达到终止条件为止。SWUFE8类的质心（或重心）•若类中有对象，则其均值称为类的质心（或重心）。pG12,,,pnxxx11pnpiipxxnpG非数值变量如何处理？SWUFE9类间距离•由于类的形式和形状多种多样，所以类与类之间的距离有多种定义与计算方法。类与之间的距离记为。（1）最短距离pGqGpqD,min,(6.16)pqpqijiGjGDdSWUFE10类间距离SWUFE11类间距离SWUFE12SWUFE13类间距离的递推公式SWUFE14类间距离的递推公式（1）最短距离（2）最长距离（3）类平均距离max{,}.(6.23)rkpkqkDDD.(6.24)pqrkpkqkrrnnDDDnnmin{,}.(6.22)rkpkqkDDDSWUFE15类间距离的递推公式（4）重心距离由合并集的重心是152222.(6.26)pqpqrkpkqkpqrrrrnnnnDDDDnnnn,pqGGrG1().rpqpqrxnxnxnSWUFE16类间距离的递推公式（5）离差平方和距离2222.(6.27)pkqkkrkpkqkpqrkrkrknnnnnDDDDnnnnnnSWUFE17类间距离的递推公式•在一定条件下，以上介绍的5种类间距离的递推公式可以构成统一的形式。假定观测样品之间的距离皆采用欧式平方距离，即则类间距离递推公式有统一的形式：222(,)()()||||,Tijijijijijddxxxxxxxx222222||.(6.29)krpkpqkqpqkpkqDDDDDDSWUFE18类间距离的递推公式类间距离的参数距离名称最短距离最长距离类平均距离重心距离离差平方和距离pq121212121200000012prnnprnnqrnnqrnnkqkrnnnnkpkrnnnnkkrnnnpq222222||.(6.29)krpkpqkqpqkpkqDDDDDDSWUFE19凝聚式层次聚类的步骤1）n个样品开始时作为n个类，计算两两之间的距离，构成一个对称距离矩阵121212(0)12000nnnnddddDddSWUFE20层次聚类的步骤2）选择中的非对角线上的最小元素，设这个最小元素是。这时。将合并成一个新类。在中消去所对应的行与列，并加入由新类与剩下的其他未聚合的类间的距离组成的一行和一列，得到一个新的距离矩阵，它是n-1阶方阵。(0)DpqD{},{}ppqqGxGx,pqGG{,}rpqGGG(0)D,pqGGrG(1)DSWUFE21层次聚类的步骤3）从出发重复步骤2的作法得。再由出发重复上述步骤，直到n个样品聚为1个大类为止。在合并过程中要记下合并样品的编号及两类合并时的距离，并绘制聚类层次图。(1)D(2)D(2)DSWUFE22层次聚类举例某年5省城镇居民月均消费（单位：元/人）x1x2x3x4x5x6x7x8辽宁7.9039.778.4912.9419.2711.052.0413.29浙江7.6850.3711.3513.3019.2514.592.7514.87河南9.4227.938.208.1416.179.421.559.76甘肃9.1627.989.019.3215.999.101.8211.35青海10.0628.6410.5210.0516.188.391.9610.81指标省份•x1：人均粮食支出，x2：人均副食支出，x3：人均烟酒茶支出，x4：人均其他副食支出，x5：人均衣着商品支出，x5：人均日用品支出，x7：人均燃料支出，x8：人均非商品支出。类间距离用最短距离进行层次聚类。SWUFE23距离矩阵分别用1，2，3，4，5表示辽宁、浙江、河南、甘肃、青海5个省。将距离矩阵记为，(0){1}0{2}11.670,{3}13.8024.630{4}13.1224.062.200{5}12.8023.543.512.210{1}{2}{3}{4}{5}D(0)DSWUFE24432.20d6{3,4}G613141623242653545min{,}min{13.80,13.12}13.12,min{,}min{24.63,24.06}24.06,min{,}min{3.51,2.21}2.21.DddDddDdd(0){1}0{2}11.670,{3}13.8024.630{4}13.1224.062.200{5}12.8023.543.512.210{1}{2}{3}{4}{5}D(1){3,4}0{1}13.120,{2}24.0611.670{5}2.2112.8023.540{3,4}{1}{2}{5}D(2){3,4,5}0{1}12.800,{2}23.5411.670{3,4,5}{1}{2}D6G6G7{3,4,5}G716151723552min{,}min{13.12,12.80}12.80,min{,}min{24.06,23.54}23.54.DDDDDD8{1,2}G787172min{,}min{12.80,23.54}12.80.DDDSWUFE25123452.20672.21811.6712.8如何确定聚类结果？凝聚过程---SWUFE26类内离差平方和设某层次水平上类的个数是G。类(k=1..G)的类内离差平方和记为：其中是类的重心。越小，说明中各样品越相似。令2()()||||,kkTkkkiiiGkiiGSxxxxxxkxkGkGkSkG1.GGkkPSSWUFE27总离差平方和以T记所有样品的总离差平方和，其中121()()||||nTiiiniiTxxxxxx11niixxn类间离差平方和：T-PGSWUFE28离差平方和的变化28SWUFE29结果类的确定•一个较好的聚类应该在类内各样品尽可能相似的前提下，使得类的个数尽可能少。•主要用到以下几种统计量统计量半偏相关统计量伪F统计量伪统计量2R2tSWUFE30统计量定义统计量为1）n个样品各为一类时，；2）n个样品合并成一类时，。3）的值总是随着分类数目的减少而减小，取快速下降的上一层。2R2R21,GPRT01.R21R20R2RSWUFE31半偏相关统计量类内离差和SWUFE32伪F统计量伪F统计量PSF是PSF值越大表示这些观测可显著地分为G个类。()(1).(6.32)()GGTPGPSFPnGSWUFE33伪统计量伪统计量PST2是PST2大，说明合并为后，使得离差平方和的增量相对于原的类内离差平方和大。这表明合并的两个类是很分开的。也就是上一次聚类效果较好。2t2t2.(6.33)()(2)pqpqpqWPSTSSnn,pqGGrGpqW,pqGGSWUFE34讨论•分裂式层次聚类如何进行类的裂分？•层次聚类有何特点？–类的个数不需事先定好–可以发现类的层次结构–样品一旦被归到某个类后不再进行调整–计算量较大…(0){1}0{2}11.670,{3}13.8024.630{4}13.1224.062.200{5}12.8023.543.512.210{1}{2}{3}{4}{5}DSWUFE35划分聚类法（快速聚类法）选择初始聚点（类的代表点）最终分类不需要初始分类判断分类是否需修正修改分类需要修正确定类个数SWUFE36K均值算法•选择K个对象作为每个类的初始质心，然后将其它每个对象指派到最近的质心；指派到一个质心的对象集合为一个类，更新每个类的质心。•重复上述指派和更新质心的步骤，直至类不发生变化为止。可以找到类内离差和最小的k个类SWUFE37K均值聚类例子SWUFE38选择初始质心与初步分类SWUFE39重新计算质心SWUFE40修正分类SWUFE41重新计算质心并判断重新计算每个对象到新质心的距离，聚类结果不再变化，算法结束。SWUFE42讨论•初始质心如何选择？•类的代表点除质心外是否还其它方法？•K如何确定？•划分方法有何特点？SWUFE43选择初始聚点1）经验选择。如果对研究对象比较了解，根据以往的经验定下k个对象作为聚点。2）随机选定k个对象作为聚点SWUFE44随机选择初始质心SWUFE45初始质心选择•3）将n个样品随机地分成k类，以每类的重心作为聚点。45SWUFE46初始质心选择4）最小最大原则。先选择所有样品中距离最远的两个样品xi1，xi2为前两个聚点，然后，选择第3个聚点xi3，使得其与前两个聚点的距离较小者最大。用公式表示为然后按相同的原则选取xi4，依次下去，直至选定k个聚点312min{(,),1,2}max{min[(,),1,2],,}.rriijidxxrdxxrjiiSWUFE47讨论•初始质心如何选择？•类的代表点除质心外是否还有其它方法？•K如何确定？•划分方法有何特点？SWUFE48K中心点聚类SWUFE49讨论•初始质心如何选择？•类的代表点除质心外是否还其它方法？•K如何确定？•划分方法有何特点？SWUFE50K的确定•经验方法：k=（假定数据集包含N个对象）•肘方法：对不同的K进行快速聚类，做出类内离差和关于不同K的曲线，第一个（或最显著的）拐点暗示合理的K值•交叉验证法：将数据集分成m份，用m-1份进行聚类，剩下的1份进行验证。对每个可能的K值，计算m个类内离差和的平均，选择拟合最好的K值•轮廓系数法•增量聚类法，…SWUFE51增量聚类法•设定聚类阈值•从数据集中取一个对象作为初始类，计算其他对象与该类的相似度；•如果相似度大于阈值则归入该类，否则构建新类。SWUFE52讨论•初始质心如何选择？•类的代表点除质心外是否还其它方法？•K如何确定？•划分方法有何特点？SWUFE53划分方法的特点•效率高•适合发现球形簇，大小、密度均匀的簇，明显分离的簇SWUFE54划分方法的特点•需要预先指定簇数k•可能对噪声数据和孤立点数据敏感（例如K均值法）例如：一维数据集X:1,2,3,8,9,10,25令K等于2，可能划分结果为54SWUFE55划分方法的改进•二分K均值将所有对象划分为2个簇，选择其中一个簇（一般是平均类内离差和SSE最大的簇）继续细分为2个簇，…，直到达到指定K值。•对K均值聚类结果进行后处理分裂簇、合并簇55SWUFE56基于密度的方法（density-basedmethod）•寻找被低密度区域分离的高密度区域•主要有DBSCAN、OPTICS、DENCLUE方法SWUFE57DBSCAN•思想：只要一个核心对象临近区域内包含其它核心对象，就继续扩展该区域（簇）。•特点：–可以过滤噪声和孤立点，发现任意形状的类SWUFE5858基于网格的方法（g