R语言-聚类分析

聚类的基本步骤•什么是类：粗略地讲，相似样品（或指标）的集合成为类。•聚类的两个基本步骤1.邻近度度量的选择：检验每一对观测值（对象）取值的相似性。一个相似性（邻近度）的度量定义为对象间的“接近”程度。越接近越同质。2.组别构建算法的选择：根据邻近度的度量，被分配到各组的对象间的差别变大，而被分配到同一组的观测值应尽可能接近。关于聚类：聚类应用领域•仓储管理：对不同类的商品在入库过程中进行聚类储存•营销:发现客户集群并进行直销和重组•天文:发现相似恒星群以及星系群•地震研究:观测到的地震震源应聚集在大陆断层带•基因分析:发现具有相似表达式的基因群•…关于聚类：探索性的分析方法•作为一种探索性技术，EVERITT(1993)评价到：“聚类方法基本上是用于产生一些假设而不是检验假设”。•有多少作聚类分析的人就有多少聚类方法。聚类的分类：•划分聚类方法•层次聚类方法•密度聚类方法•网格聚类方法•模型聚类方法在基于划分的聚类中，任务就是将数据划分成K个不相交的点集，使每个子集中的点尽可能同质。基于划分的方法，其代表算法有k-means算法、K-medoids等划分聚类方法K-MEANS算法•K-MEANS算法基本步骤1.从N个数据对象任意选择K个对象作为初始聚类中心；2.根据每个聚类对象的均值(中心对象)，计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；3.重新计算每个(有变化)聚类的均值(中心对象)；4.计算标准测度函数，当满足一定条件，如函数收敛时，则算法终止；如果条件不满足则回到步骤2。K-MEANS优缺点•主要优点：•是解决聚类问题的一种经典算法，简单、快速。•对处理大数据集，该算法是相对可伸缩和高效率的。•当结果簇是密集的，它的效果较好。•主要缺点•在簇的中心（平均值）被定义的情况下才能使用。•必须事先给出K（要生成的簇的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果。•不适合于发现非凸面形状的簇或者大小差别很大的簇。而且，它对于“躁声”和孤立点数据是敏感的。层次聚类方法•层次聚类方法对给定的数据集进行层次的分解，直到某种条件满足为止。具体又可分为：凝聚的层次聚类：一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。分裂的层次聚类：采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件。•层次凝聚的代表是AGNES算法。层次分裂的代表是DIANA算法。层次聚类优缺点•层次聚类方法是不可逆的，也就是说，当通过凝聚式的方法将两组合并后，无法通过分裂式的办法再将其分离到之前的状态，反之亦然。•另外，层次聚类过程中调查者必须决定聚类在什么时候停止，以得到某个数量的分类。•在不必要的情况下应该小心使用层次聚类方法。1、距离的定义距离的定义有很多，但是必须遵循一定的规则。假设表示样本之间的距离，则一般要求它满足如下条件：（1）对一切i,j都大于等于0（2）等于0当且仅当i=j（3）对一切i和j可以互换（4）如果距离的定义仅满足前三条，则称此距离为广义距离。常用的距离有，明氏距离，兰氏距离，马氏距离，斜交空间距离，列名变量的相似性度量。ijdjixx与ijdijdijd都成立,,对一切kjidddkjikij2、常用的距离kplkjlilijxxd11)||(pljlilijxxd1明氏距离特别地，当k＝1时，即为绝对值距离(1)明氏距离ixjxijd令表示样品与的距离npnnppxxxxxxxxx212222111211设原始数据为kplkjlilijxxd11)||(pljlilijxxd12)(明氏距离当k＝2时，即为欧氏距离当k＝∞时，即为切比雪夫距离jlilplijxxd1max123452018104471055325.236.328.911.5171x2x3x3124224)(lllxxd222)5.113.36()510()418(欧氏距离切比雪夫距离lllxxd423124max8.245.113.3624d计算例：明考夫斯基距离有以下两个缺点：①明氏距离的数值与指标的量纲有关。当各变量的测量值相差悬殊时，常发生“大数吃小数”的现象，为消除量纲的影响，通常先将每个变量进行标准化。②明氏距离的定义没有考虑各个变量之间相关性的影响。年龄收入家庭人口数甲3030001乙4032003222)31()32003000()4030(d(2)标准化的欧氏距离npnnppxxxxxxxxx212222111211设原始数据为ijd22222221111...ppjpipjijisxxsxxsxx222222211111...11jppippjijixxsxxsxxspllljlilsxx12pppnpnnppppppppSxxSxxSxxSxxSxxSxxSxxSxxSxx222211112222221112112221211111(3)马氏距离马氏距离是由印度著名统计学家马哈拉诺比斯(MAHALANOBIS)所定义的一种距离，其计算公式为：ijd21221112211,,,pjpijijipjpijijixxxxxxSxxxxxx=211jijixxSxx马氏距离又称为广义欧氏距离。马氏距离考虑了观测变量之间的相关性。如果假定各变量之间相互独立，即观测变量的协方差矩阵是对角矩阵，此时马氏距离就是标准化的欧氏距离。马氏距离不受指标量纲及指标间相关性的影响系统聚类法系统聚类法的基本思想先将N个样品各自看成一类，然后规定样品之间的“距离”和类与类之间的距离。选择距离最近的两类合并成一个新类，计算新类和其它类（各当前类）的距离，再将距离最近的两类合并。这样，每次合并减少一类，直至所有的样品都归成一类为止。系统聚类法的基本步骤：1.计算n个样品两两间的距离，记作D=。2.构造n个类，每个类只包含一个样品。3.合并距离最近的两类为一新类。4.计算新类与各当前类的距离。5.重复步骤3、4，合并距离最近的两类为新类，直到所有的类并为一类为止。6.画聚类谱系图。7.决定类的个数和类。ijdijd1.最短距离法2.最长距离法3.中间距离法4.重心法5.类平均法6.离差平方和法（Ward法）系统聚类方法：上述6种方法归类的基本步骤一致，只是类与类之间的距离有不同的定义。定义类p与q之间的距离为两类最近样品的距离，即ijqjpipqdd,minxq1•xp2•xq2•xp1•pqdxq3•一、最短距离法qrprkrddd,min设类p与q合并成一个新类，记为k，则k与任一类r的距离是pqkr例最短距离法设抽取5个样品，每个样品观察2个指标，：您每月大约喝多少瓶啤酒，：您对“饮酒是人生的快乐”这句话的看法如何？观察数据如下，对这5个样品分类。1x2x12345201810447105531x2x②③④⑤①②③④3.610.216.1216.499.4314.8715.6566.322②③④⑤①②③④3.610.216.1216.499.4314.8715.6566.322ijdnnijdD)(1.计算5个样品两两之间的距离记为距离矩阵（采用欧氏距离），为最小，245d2.合并距离最小的两类为新类，按顺序定为第６类。5,4⑥＝87.1465.15,87.14min,min524262ddd6,min534363ddd12.1649.16,12.16min,min514161ddd3、计算新类⑥与各当前类的距离，得距离矩阵如下：②③⑥①②③3.610.216.129.4314.87643.9,min231373ddd87.14,min261676ddd6.312d2,1为最小，⑦=⑥⑦③⑥69.4314.874、重复步骤2、3，合并距离最近的两类为新类，直到所有的类并为一类为止。43.9,min673787ddd636d6,3为最小，⑧=5、6、按聚类的过程画聚类谱系图45⑥⑨⑧并类距离312⑦7、决定类的个数与类。观察此图，我们可以把5个样品分为3类，2,135,4、、。43.966.328,76,32,15,4dddd•••x11•x21••••12d二、最长距离法定义类p与q之间的距离为两类最远样品的距离，即ijqjpipqdd,max三、中间距离法定义类与类之间的距离既不采用两类之间最近的距离，也不采用两类之间最远的距离，而是采用介于两者之间的距离，故称为中间距离法。••krd•rpqk2222412121pqqrprkrdddd四、重心法（CENTROID)••11,xy22,xypx和qxqpxxpqdd类与类之间的距离就考虑用重心之间的距离表示。设p与q的重心分别是，则类p和q的距离为五、类平均法（AVERAGE))(61262524232221dddddd定义两类之间的距离平方为这两类元素两两之间距离平方的平均piqjijqppqdnnd221•••••pq六、差平方和法（WARD法）2112221211)(nipipniiniixxxxxx)()(1XXXXinii反映样品之间的差异程度npnnppxxxxxxxxx212222111211设变量X的n个样品观察值为：n个样品的离差平方和为：•••••••••••q•••••••••••••pqSpSk设类p和q分别含有np、nq个样品，其离差平方和分别记为psqs和•直观上容易想到把两群样品聚为一大群，大群的离差平方和将超过原来两个群的离差平方和之和。2qxpxdnnnnSSSqpqpqpk如果将p和q并类得到新类k，则类k的离差平方和为pqs把增加的量记为定义类p和q之间的距离为：22qxpxdnnnnSdqpqppqpq设类p和q分别含有np、nq个样品，其离差平方和分别记为psqs和动态聚类法----K均值法系统聚类法是一种比较成功的聚类方法。然而当样本点数量十分庞大时，则是一件非常繁重的工作，且聚类的计算速度也比较慢。比如在市场抽样调查中，有4万人就其对衣着的偏好作了回答，希望能迅速将他们分为几类。这时，采用系统聚类法就很困难，而动态聚类法就会显得方便，适用。动态聚类适用于对大型数据的聚类。动态聚类法•基本思想：选取若干个样品作为凝聚点，计算每个样品和凝聚点的距离，进行初始分类，然后根据初始分类计算其重心，再进行第二次分类，一直到所有样品不再调整为止。选择凝聚点分类修改分类分类是否合理分类结束YesNo用一个简单的例子来说明动态聚类法的工作过程。例如我们要把图中的点分成两类。快速聚类的步骤：1、随机选取两个点和作为凝聚点。2、对于任何点，分别计算3、若，则将划为第一类，否则划给第二类。于是得图（）的两个类。)1(1x)1(2xkx),(),()1(2)1(1xxdxxdkk和),(),()1(2)1(1xxdxxdkkkx4、分别计算两个类的重心，则得和，以其为新的凝聚点，对空间中的点进行重新分类，得到新分类。)2(1x)2(2xc(b)任取两个凝聚点(c)第一次分类(d)求各类中心（a）空间的群点(e)第二次分类动态聚类法•优点：计算量小，方法简便，可以根据经验，先作主观分类。•缺点：结果受选择