第二章--聚类分析.

第一节聚类分析核心思想第二节相似性的量度第三节系统聚类分析法第四节K均值聚类分析第五节实例分析与计算机实现第二章聚类分析第一节核心思想“物以类聚，人以群分”。“近朱者赤,近墨者黑”在生物学中，为了研究生物的演变，生物学家需要根据各种生物不同的特征对生物进行分类。在经济学中，根据经济发展的不同阶段对世界各个国家进行分类.医学研究中,阑尾炎类型的划分:性单纯性阑尾炎,急性化脓性阑尾炎,坏疽性及穿孔性阑尾炎。在社会学研究中，需要构造人口生育分类模式、人口死亡分类状况，以此来研究人口的生育和死亡规律。聚类分析的核心思想就是根据具体的指标(变量)对你所研究的样品进行分类.指标是什么?书上的例子.将居民户按户主收入状况进行分类,那么衡量收入状况的指标有:标准工资收入\职工奖金…..样品是什么?你所研究的11户居民.进一步解读指标:间隔尺度有序尺度名义尺度思考:能不能对指标进行聚类?所以,聚类分析包括两种类型:Q型聚类:根据指标(变量)对样品进行分类R型聚类:对指标(变量)进行分类问题:大家认为聚类的结果是什么呢?第二节相似性的量度一样品相似性的度量二变量相似性的度量一、样品相似性的度量Q型聚类分析，常用距离来测度样品之间的相似程度。选择p个变量对n个样品聚类:可以把n个样品看成p维空间中的n个点，则两个样品间相似程度就可用p维空间中的两点距离来度量。：不同的距离公式:1．明考夫斯基距离令dij表示样品Xi与Xj的距离（1）绝对距离（1q）1(1)pijikjkkdXX（2）欧氏距离（2q）21/21(2)()pijikjkkdXX（3）切比雪夫距离（q）1()maxijikjkkpdXX1/1()()pqqijikjkkdqXX明考夫斯基距离的缺陷:容易受变量的量纲影响.没有考虑变量间的相关性两种改进措施:“马氏距离”法和变量标准化处理法(见书)高校科研的样本学校参加科研人数(人)投入经费(元)立项课题数()1410438000019233617300002134902200008欧氏距离元万元(1,2)26500081.6(1,3)218000193.7(2,3)47000254.8从距离的定义来看,所有变量都会在距离中做出贡献,若变量间存在较高的线形相关性,能够相互替代,那么计算距离就会重复替代,将在距离计算中有较高的权重,从而使最终的聚类结果更倾向此变量21()()()ijijijdMXXΣXX2．马氏距离两个样品间的马氏距离为马氏距离又称为广义欧氏距离。优点:(1)考虑了观测变量之间的相关性。如果各变量之间相互独立，即观测变量的协方差矩阵是对角矩阵。(2)不再受各指标量纲的影响。4．距离选择的原则（1）要考虑所选择的距离公式在实际应用中有明确的意义。如欧氏距离就有非常明确的空间距离概念。马氏距离有消除量纲影响的作用。（2）要综合考虑对样本观测数据的预处理和将要采用的聚类分析方法。如在进行聚类分析之前已经对变量作了标准化处理，则通常就可采用欧氏距离。（3）要考虑研究对象的特点和计算量的大小。样品间距离公式的选择是一个比较复杂且带有一定主观性的问题，我们应根据研究对象的特点不同做出具体分折。实际中，聚类分析前不妨试探性地多选择几个距离公式分别进行聚类，然后对聚类分析的结果进行对比分析，以确定最合适的距离测度方法。二、变量相似性的度量R型聚类分析中,常用相似系数表示变量间的相似性。1、夹角余弦变量i的第k个取值变量j的第k个取值显然，∣cosij∣1。1221/211cos[()()]nkikjkijnnkikjkkxxxxkixkjx二氧化碳影响因素聚类2．相关系数相关系数经常用来度量变量间的相似性。变量Xi与Xj的相关系数定义为分别为变量i和j的均值显然也有，∣rij∣1。1221/211()()[()()]nkiikjjkijnnkiikjjkkxXxXrxXxXijXX和有了对单个样品和单个指标相似形的度量方法后,如何根据类间距离大小和相关系数大小来进行分类呢?会用到以下聚类方法:系统聚类模糊聚类K均值聚类有序样品聚类第三节系统聚类一系统聚类的基本思想二类间距离与系统聚类法三类间距离的统一性一、系统聚类的基本思想系统聚类的基本思想是：距离相近的样品（或变量）先聚成类，距离相远的后聚成类，过程一直进行下去，每个样品（或变量）总能聚到合适的类中。系统聚类过程是：假设总共有n个样品（或变量）第一步:将每个样品（或变量）独自聚成一类，共有n类；第二步:根据所确定的样品（或变量）“距离”公式，把距离较近的两个样品（或变量）聚合为一类，其它的样品（或变量）仍各自聚为一类，共聚成n1类；第三步:将“距离”最近的两个类进一步聚成一类，共聚成n2类；……，以上步骤一直进行下去，最后将所有的样品（或变量）全聚成一类。有两个关键问题:类与类间的距离如何衡量?如何选择分几类呢?二、类间距离最短距离法、最长距离法、类平均法、重心法和离差平方和法等。它们的归类步骤基本上是一致的，主要差异是类间距离的计算方法不同。以下用dij表示样品(指标)Xi与Xj之间距离，用D表示类Gi与Gj之间的距离。,(,)min{|}kijpqDpqdiGjG1.最短距离法定义类与之间的距离为两类最近样品(指标)的距离，即为....2.最长距离法定义类iG与jG之间的距离为两类最远样品的距离，即为(,)max{|,}kijPqDpqdiGjG....3．类平均法两类间距离为类中任意两样品（指标）距离的平均。1(,)ipjjGijGGpqDpqdnn....1234131423242*2ddddD4.重心法重心法定义类间距离为两类重心（各类样品的均值）的距离。(,)pqcxxDpqd注意：每次得到一个新的合并类后要重新计算重心5.离差平方和法又称为Ward法。如果分类正确，同类样品的离差平方和应当较小，类与类的离差平方和较大。具体做法是先将n个样品各自成一类，然后每次缩小一类，每缩小一类，离差平方和就要增大，选择使方差增加最小的两类合并，直到所有的样品归为一类为止。2wpqpqDDDDDp为p类的离差平方和Dq为q类的离差平方和Dpq为p和q组成总类的离差平方和5.组间平均链接该个体与小类中每个个体距离的平均6.组内平均链接该个体与小类中每个给体距离,以及小类内部每个个体距离的平均case欧氏距离12345108.06217.80426.90730.41428.062025.45634.65538.21317.80425.45609.2212.806426.90734.6559.2203.606530.41438.2112.8063.6060三、分类数的确定可以根据碎石图确定:X轴表示分几类Y轴表示聚合系数四、聚类分析步骤以最短距离法步骤为例：（1）选择样品(指标)距离公式，计算样品的两两距离，得距离阵记为D（0），开始每个样品自成一类，这时Dij=dij。（2）找出距离最小元素，设为Dpq，则将Gp和Gq合并成一个新类，记为Gr，即Gr=｛Gp，Gq｝。（3）根据最短距离法计算新类与其它类的距离。（4）重复（2）、（3）两步.如果某一步距离最小的元素不止一个，则对应这些最小元素的类同时合并。G1G2G3G4G5G6G10G210G3430G46520G587420G6985310【例5.1】设有六个样品，每个只测量一个指标，分别是1，2，5，7，9，10，试用最短距离法将它们分类。（1）选择样品距离公式，绝对距离最简单,形成D（0）G7G3G4G8G70G330G4520G87420（2）D（0）中最小的元素是D12＝D56＝1，于是将G1和G2合并成G7，G5和G6合并成G8，并利用（5.12）式计算新类与其它类的距离D（1）G7G9G70G930（3）在D（1）中最小值是D34＝D48＝2，由于G4与G3合并，又与G8合并，因此G3、G4、G8合并成一个新类G9，其与其它类的距离D（2）（4）最后将G7和G9合并成G10，这时所有的六个样品聚为一类，其过程终止。上述聚类的可视化过程如下:G1G2G3G4G5G6G10G210G31690G4362540G564491640G6816425910【例5.2】针对例5.1的数据，试用重心法将它们聚类。（1）假设样品采用欧氏距离，样品间的平方距离阵D2（0）G1G2G3G4G10G212.250G330.2540G46420.256.250（2）D2（0）中最小的元素是D212＝D256＝1，于是将G1和G2合并成G7，G5和G6合并成G8，新类与其它类的距离得到距离阵D2（1）G7G9G8G70G920.250G86412.50（3）在D2（1）中最小值是D234＝4，那么G3与G4合并一个新类G9，其与与其它类的距离D2（2）G7G10G70G1039.06250（4）在中最小值是＝12.5，那么与合并一个新类，其与与其它类的距离（5）最后将G7和G10合并成G11，这时所有的六个样品聚为一类，其过程终止。上述重心法聚类的可视化过程见图5.3所示，横坐标的刻度表示并类的距离。系统聚类总结:要选择初始样品(指标)的相似形测度公式聚成新类后要选择类与类间的距离公式在选择哪些样品(指标)或是哪些类聚合为一类时统一的标准都是距离最近.引申出一个问题,到底选择哪一种类间距离公式更好呢?最短距离法是用得比较多的第四节K均值聚类一、核心思想这种算法的基本思想是将每一个样品分配给最近中心（均值）的类中，具体的算法至少包括以下三个步骤：1.指定聚类数；2.确定初始类的中心.用户指定或系统指定.3.根据距离最近原则进行分类.计算每个样本到各类中心点的距离,并按距离最近原则对所有样品进行分类.4.重新确定各类中心。利用分配过来的样本重新计算类均值.5.判断是否满足终止聚类的条件.跌代次数:SPSS默认为10类中心点偏移程度:新确定的类中心点距离上个类中心点的最大偏移量小于指定量.系统聚类与K均值聚类的区别与联系K均值法和系统聚类法一样，都是以距离的远近亲疏为标准进行聚类的.系统聚类可以选择分类数,而K—均值法只能产生指定类数的聚类结果。所以有时也借助系统聚类法以一部分样品为对象进行聚类，其结果作为K—均值法确定类数的参考。样品变量1X2XA53B-11C1-2D-3-2【例5.3】假定我们对A、B、C、D四个样品分别测量两个变量,得到结果。试将以上的样品聚成两类。中心坐标聚类1X2X（A、B）22（C、D）-1-2第一步：按要求取K=2，为了实施均值法聚类，我们将这些样品随意分成两类，比如（A、B）和（C、D），然后计算这两个聚类的中心坐标，见表5.10所示。中心坐标是通过原始数据计算得来的，比如（A、B）类的15(1)22X10)23()25())(,(222ABAd61)23()15())(,(222CDAd第二步：计算某个样品到各类中心的欧氏平方距离，然后将该样品分配给最近的一类。对于样品有变动的类，重新计算它们的中心坐标，为下一步聚类做准备。先计算A到两个类的平方距离：由于A到（A、B）的距离小于到（C、D）的距离，因此A不用重新分配。计算B到两类的平方距离：由于B到（A、B）的距离大于到（C、D）的距离，因此B要分配给（C、D）类10)21()21())(,(222ABBd9)21()11())(,(222CDBd中心坐标聚类1X2X（A）53（B、C、D）-1-1得到新的聚类是（A）和（B、C、D）。更新中心坐标样品到中心的距离平方聚类ABCD（A）0404189（B、C、D）52455第三步：再次检查每个样品，以决定是否需要重新分类。计算各样品到各中心的距离平方。到现在为止，每个样品都已经分配给距离中心最近的类，因此聚类过程到此结束。最终得