第6章_聚类分析

1第6章聚类分析南通大学理学院2聚类分析的基本思想及意义聚类分析是研究分类问题的多元数据分析方法聚类分析是数值分类学的一分支在经济学中有广泛的应用背景城镇居民收入分析产品质量指标等等3聚类分析的基本思想及意义基本思想:在样品之间定义距离，在变量之间定义相似系数，距离或相似系数代表样品或变量之间的相似程度。按相似程度的大小，将样品（或变量）逐一分类，关系密切的类聚集到一个小的分类单位，然后逐步扩大，使得关系疏远的聚合到一个大的分类单位，直到所有的样品（或变量）都聚集完毕，形成一个表示亲疏关系的谱系图，依次按照某些要求对样品（或变量）进行分类。4聚类分析的基本思想及意义多元数据形成数据矩阵，在这个数据矩阵中，共有n个样品（列向），p个指标（行向）。聚类分析有两种类型：按样品聚类或按变量聚类。12,,,nxxx12pxxx12jnxxxx11211112222212jnjnppjpnpxxxxxxxxxxxx指标样品5聚类分析与判别分析的区别和联系区别：聚类分析一般寻求客观的分类方法。在进行聚类之前，对总体到底有几类类型未知（究竟分几类较为合适，需从计算中探索调整）。判别分析则是在总体类型划分已知，在各总体分布或来自总体训练样本基础上，对当前的新样本判定它们属于哪个总体。联系:当我们对研究的多元数据的特征不熟悉，就要先进行聚类分析，才能考虑判别分析问题。6聚类分析的方法重点介绍快速聚类法谱系聚类法7样品间的相似性度量－距离设有n个样品的多元观测数据：每个样品可看成p元空间的一个点，n个样品组成p元空间的n个点。我们用各点之间的距离来衡量各种样品之间的相似程度。12(,,,),1,2,,.Tiiiipxxxxin8样品间的相似性度量－距离设是样品之间的距离，一般要求它满足下列条件：在聚类分析中,有些距离不满足3）,我们在广义上仍称它为距离。(,)ijdxx,ijxx1)(,)0(,)0;2)(,)(,);3)(,)(,)(,).ijijijijjiijjkkjdxxdxxxxdxxdxxdxxdxxdxx且当且仅当＝9聚类分析中的常用距离欧式距离令，形成一个距离矩阵其中.1221(,)().(6.1)pijikjkkdxxxx(,)ijijddxx()ijppDdijjidd1212121200,(6.2)0nnnndddddd10例6.1为研究辽宁、浙江、河南、甘肃、青海5省份1991年城镇居民生活消费规律，需要利用调查资料对这5个省分类。指标变量共8个，含义如下：x1：人均粮食支出，x2：人均副食支出，x3：人均烟酒茶支出，x4：人均其他副食支出，x5：人均衣着商品支出，x5：人均日用品支出，x7：人均燃料支出，x8：人均非商品支出。数据资料示于表6.2。将每个省份的数据看成一个样品，计算样品之间的欧式距离矩阵。11例6.1表6.21991年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指标省份12例6.1解：以1，2，3，4，5分别表示辽宁、浙江、河南、甘肃、青海5个省（样品）。计算每两个样品之间的欧式距离：,,1,2,3,4,5.ijdij221221122222332122[(7.907.68)(39.7750.37)(13.2914.87)]11.67,[(7.689.42)(50.3727.93)(14.879.76)]24.63,dddd13例6.1从而得到距离矩阵如下：（因是对称矩阵，故只用下三角部分表示）D中各元素数值的大小，反映了5个省消费水平的接近程度。011.670,13.8024.63013.1224.062.20012.8023.643.512.210D14聚类分析中的常用距离绝对距离Minkowski距离当时分别是欧式距离、绝对距离。Minkowski距离又称距离，距离即欧式距离，距离即绝对距离。1(,).(6.3)pijikjkkdxxxx11(,),1(6.4)pmmijikjkkdxxxxm2,1mmL2L1L15聚类分析中的常用距离Chebyshev距离Chebyshev距离是Minkowski距离当时的极限。1(,)max.(6.5)ijikjkkpdxxxxm16聚类分析中的常用距离以上距离与各变量指标的量纲有关，为消除量纲的影响，有时应先对数据进行标准化，然后用标准化数据计算距离。标准化数据其中*,1,2,,;1,2,,.(6.6)kikikkxxxinkps221111,().1nnkkikkikiixxsxxnn17聚类分析中的常用距离方差加权距离对标准化数据计算欧式距离时，即是方差加权距离。12221()(,).(6.7)pikjkijkkxxdxxs*ikx18聚类分析中的常用距离马氏距离其中是由样品算得的协方差矩阵：其中112(,)[()()](6.8)TijijijdxxxxSxxS12,,,nxxx11()()1nTiiiSxxxxn11.niixxn19快速聚类法在谱系聚类法中，因为样品一旦被归到某个类后就不变了，所以要求分类方法比较准确。而样品容量较大时，谱系聚类法的计算量过大。因此，为了弥补谱系聚类法的不足，产生了快速聚类法，又称动态聚类法。快速聚类法先将样品粗糙地分一下类，然后再按照某种原则进行修正，直至分类比较合理为止。20快速聚类法选择聚点最终分类合理初始分类分类是否合理修改分类不合理21快速聚类法的步骤选择聚点聚点（种子）是一批有代表性的样品，它的选择决定了初始分类，对最终分类有较大影响。在进行快速聚类法前，要根据研究问题的要求及了解程度先定下分类数k，这样就可以在每一类中选择一个有代表性的样品作为聚点（初始聚点）。22快速聚类法的步骤如何选择聚点？1）经验选择。如果对研究对象比较了解，根据以往的经验定下k个样品作为聚点。2）将n个样品人为地（或随机地）分成k类，以每类的重心作为聚点。23快速聚类法的步骤3）最小最大原则。设要将n个样品分成k类，先选择所有样品中距离最远的两个样品为前两个聚点，即选择和，然后，选择第3个聚点，使得与前两个聚点的距离最小者等于所有其余的与的最小距离中最大的，用公式表示为12,iixx1ix2ix1212(,)max{}iiiiijdxxdd3ix3ix12,iixx24快速聚类法的步骤然后按相同的原则选取，依次下去，直至选定个聚点。若已选了L个聚点（Lk）,则第L+1个聚点选取的原则为312min{(,),1,2}max{min[(,),1,2],,}.rriijidxxrdxxrjii4ix12,,,kiiixxx11min{(,),1,2,,}max{min[(,),1,2,,],,,}.lrriijildxxrldxxrljii25快速聚类法的步骤注：在SAS系统procfastclus过程中，分类数k是事先给定的。在给定k以后，procfastclus过程会按上述方法算出初始聚点的。26快速聚类法的计算步骤先假设聚类中采用的距离是欧式距离，即1）设k个初始聚点的集合是用下列原则实现初始分类。记这样，将样品分成不相交的k类。以上初始分类的原则是每个样品以最靠近的初始聚点归类。12(,)||||[()()].Tijijijijdxxxxxxxx(0)(0)(0)(0)12{,,,},kLxxx(0)(0)(0){:(,)(,),1,2,,,},1,2,,.iijGxdxxdxxjkjiik27快速聚类法的计算步骤依照以上计算，得到一个初始分类2）从出发，计算新的聚点集合。以的重心作为新的聚点：其中是类中的样品数。这样，得到新的聚点集合：(0)(0)(0)(0)12{,,,}.kGGGG(0)G(1)L(0)iG(0)(1)1,1,2,,.liilxGixxiknin(0)iG(1)(1)(1)(1)12{,,,}.kLxxx28快速聚类法的计算步骤从出发，将样品作新的分类。记得到分类这样，依次重复计算下去。(1)L(1)(1)(1){:(,)(,),1,2,,,},1,2,,.iijGxdxxdxxjkjiik(1)(1)(1)(1)12{,,,},kGGGG29快速聚类法的计算步骤3）设在第m步得到分类在以上递推计算过程中，是类的重心。不一定是样品，又一般不是的重心。当m逐渐增大时，分类趋于稳定。此时，就会近似为的重心，从而算法即可结束。实际计算时，从某一步m开始，分类()()()()12{,,,}.mmmmkGGGG()mix(1)miG()miG()miG()mix(1)(1)(1)(1)12{,,,}.mmmmkGGGG(1)()(1)(),,mmmmiiiixxGG30快速聚类法的计算步骤与完全相同，计算即告结束。记理论上可以证明：当m增加时，为单调减下有界序列，故存在，即会逐步趋于稳定。因此，分类结果也将逐步稳定，即上述快速聚类法具有收敛性。()()()()12{,,,}mmmmkGGGG()()()()()()1(,)(,),(,).mlimmmiilixGkmmmiiiDxGdxxuDxGmu(0)mulimmmumu31快速聚类法的计算步骤设给定，若则递推计算过程结束。注：在procfastclus过程中，的默认值是0.02。()()(1)(0)(0)(0)max{(,),1,2,,},min{(,),,1,2,,}.mmmiiijddxxikddxxijk0()(0),mdd32快速聚类－procfastclus过程该过程适合于观测数目较大的数据集的不相交聚类（即各类之间互不相交）。但对于小数据集，此过程对于观测的次序较为敏感。此过程在聚类之前要求指定类的个数，因为要对不同的类的个数作分析，需要多次运行该过程。主要语句形式为procfastclusoptions；varvariables；IDvariable；33快速聚类－procfastclus过程procfastclusoptions；1）maxcluster（或maxc）＝n：指定所允许的最大分类个数，若省略，则默认n＝100。2）radius＝t：为选择新的“聚点”指定的最小距离准则。t的默认值为0。用户必须规定以上两个选项之一。34快速聚类－procfastclus过程procfastclusoptions；3）data＝SASdataset：指出用以分析的SAS数据集名称。此过程中，数据性质是原始观测数据，而不能是距离或相似矩阵。4）mean＝SASdataset：生成一个输出数据集，其中包括每个类的均值和其他统计量的值。5）out＝SASdataset：生成一个输出数据集，其中包括原始数据及两个新变量cluster（用以指示观测属于哪个类的变量）和距离distance。35快速聚类－procfastclus过程procfastclusoptions；6）cluster＝name：规定在4）和5）的输出数据集中用以指示观测数据属于哪一类的变量名称。缺省时系统自动命名为cluster。7）distance：要求打印类均值之间的距离。8）list：要求列出所有观测的ID变量值，观测所归入类的类号