ch08-聚类分析与判别分析

第8章聚类分析与判别分析武汉大学计算机学院第8章聚类分析与判别分析8.1聚类分析8.2判别分析8.1聚类分析8.1.1聚类分析的一般概念8.1.2系统聚类法的基本思想和步骤8.1.3用CLUSTER过程和TREE过程进行系统聚类8.1.4用VARCLUS过程进行变量聚类8.1.1聚类分析的一般概念设有n个样品(多元观测值)，每个样品测得m项指标(变量)，得到观测数据xij（i=1,…,n；j=1,…,m），如表所示。X1X2…XmX(1)x11x12…x1mX(2)x21x22…x2m……………X(n)xn1xn2…xnm表中数据又称为观测数据阵或简称为数据阵，其数学表示为：其中列向量Xj=(x1j，x2j，…，xnj)'，表示第j项指标（j=1，2，…，m），行向量X(i)=(xi1，xi2，…，xin)表示第i个样品。1.两种聚类分析根据分类对象的不同，聚类分析分为两种：

(1)样品聚类：样品聚类是对样品（观测）进行的分类处理，又称为Q型分类，相当于对观测数据阵按行分类。

(2)变量聚类：变量聚类是对变量（指标）进行的分类处理，又称为R型分类，相当于对观测数据阵按列分类。两种聚类在形式上是对称的，处理方法也是相似的。2.聚类分析的方法聚类方法大致可归纳如下：(1)系统聚类法（谱系聚类）

先将l个元素（样品或变量）看成l类，然后将性质最接近（或相似程度最大）的2类合并为一个新类，得到l–1类，再从中找出最接近的2类加以合并变成了l–2类，如此下去，最后所有的元素全聚在一类之中。(2)分解法（最优分割法）

其程序与系统聚类相反。首先所有的元素均在一类，然后按照某种最优准则将它分成2类、3类，如此下去，一直分裂到所需的k类为止。(3)动态聚类法（逐步聚类法）开始将l个元素粗糙地分成若干类，然后用某种最优准则进行调整，一次又一次地调整，直至不能调整为止。(4)有序样品的聚类

n个样品按某种因素（时间或年龄或地层深度等）排成次序，要求必须是次序相邻的样品才能聚在一类。

其他还有：有重叠聚类、模糊聚类、图论聚类等方法。3.聚类统计量

聚类分析实质上是寻找一种能客观反映元素之间亲疏关系的统计量，然后根据这种统计量把元素分成若干类。常用的聚类统计量有距离系数和相似系数两类。距离系数一般用于对样品分类，而相似系数一般用于对变量聚类。距离的定义很多，如马氏距离、明考斯基距离、兰氏距离、切比雪夫距离以及常见的欧氏距离：相似系数有相关系数、夹角余弦、列联系数等。如何度量远近？如果想要对100个学生进行分类，如果仅仅知道他们的数学成绩，则只好按照数学成绩来分类；这些成绩在直线上形成100个点。这样就可以把接近的点放到一类。如果还知道他们的物理成绩，这样数学和物理成绩就形成二维平面上的100个点，也可以按照距离远近来分类。“近朱者赤，近墨者黑”，人们往往根据事物间的远近距离来判定类别。两个距离概念按照远近程度来聚类需要明确两个概念：一个是点和点之间的距离，一个是类和类之间的距离。点间距离有很多定义方式。最简单的是欧氏距离，还有绝对距离等。类间距离是基于点间距离定义的：比如两类之间最近点之间的距离可以作为这两类之间的距离，也可以用两类中最远点之间的距离作为这两类之间的距离；当然也可以用各类的中心之间的距离来作为类间距离。定义不同的距离结果会不同，但一般不会差太多。8.1.2系统聚类法的基本思想和步骤下面以样品聚类为例介绍系统聚类法。

系统聚类法的基本思想

设有n个样品，每个样品测得m项指标（见表8-1）。系统聚类方法的基本思想是：首先定义样品间的距离（或相似系数）和类与类之间的距离。一开始将n个样品各自自成一类，这时类间的距离与样品间的距离是等价的；然后将距离最近的两类合并，并计算新类与其他类的类间距离，再按最小距离准则并类。这样每次减少一类，直到所有的样品都并成一类为止。这个并类过程可以用谱系聚类图形象地表达出来。根据类间距离计算方法的不同，有11种不同的聚类方法：(1)类平均法类平均法(AverageLinkage)用两类样品两两观测间距离的平均作为类间距离。类平均法是一种应用较广泛，聚类效果较好的方法(2)重心法重心法(CentroidMethod)用两个类重心(均值)之间的（平方）欧氏距离定义类间距离(3)最长距离法最长距离法(CompleteMethod)用两类观测间最远一对观测的距离定义类间距离(4)最短距离法最短距离法(SingleLinkage)用两类观测间最近一对观测的距离定义类间距离(5)Ward最小方差法（离差平方和法）

Ward最小方差法(Ward'sMininum-VarianceMethod)也称Ward离差平方和法。Ward方法并类时总是使得并类导致的类内离差平方和增量最小。还有最大似然法(EML)法可变类平均法(Flexible-BetaMethod)McQuitty相似分析法(McQuitty‘sSimilarityAnalysis)中间距离法(MedianMethod)两阶段密度估计法(Two–StageDensityLinkage)等。类平均法和Ward最小方差法使用最广泛。最短距离分类的基本原理例:为考察公司的经营业绩并对其分类,可依据它们的年盈利额进行归类.公司年盈利(十万元)甲1乙3丙9丁14单一指标的系统聚类过程谱系聚类图，简称谱系图系统聚类，也称谱系聚类或层次聚类最短距离分类的基本原理例：为考察投资者的盈利能力，从资金的投入和回报两方面进行考察投资者资金投入（万元）回报（万元）A3560B1540C305D808E9035多指标的系统聚类过程采用欧式距离计算距离按聚类过程依次画出谱系聚类图表格表示初始状态系统聚类流程图4.系统聚类类数的确定

(1)由适当的阀值确定选定某种聚类方法，按系统聚类的方法并类后，得到一张谱系聚类图，聚类图（又称谱系图）只反映样品间（或变量间）的亲疏关系，它本身并没有给出分类，需要给定一个临界相似尺度，用以分割谱系图而得到样品（或变量）的分类，如给定临界值（阀值）为d，那么，当样品间或已并类间距离小于d时，认为这些样品和类的关系密切，应该归属一类。(2)根据统计量确定分类个数在SAS的CLUSTER过程中，提供一些统计量可以近似检验类个数如何选择更合适，用统计量决定类数的方法来自统计的方差分析思想，下面作一些介绍。

1)R2统计量其中PG为分类数为G个类时的总类内离差平方和，T为所有样品或变量的总离差平方和。R2越大，说明分为G个类时每个类内的离差平方和都比较小，也就是分为G个类是合适的。但是，显然分类越多，每个类越小，R2越大，所以我们只能取G使得R2足够大，但G本身比较小，而且R2不再大幅度增加。

2)半偏R2统计量在把类CK和类CL合并为下一水平的类CM时，定义半偏相关其中BKL=WM–(WK+WL)为合并类引起的类内离差平方和的增量，Wt为类Ct的类内离差平方和。半偏R2用于评价一次合并的效果，其值是上一步R2与该步R2的差值。其值越大，说明上一次合并的效果越好。

3)伪F统计量伪伪F统计量评价分为G个类的效果。伪F统计量越大，表示分为G个类越合理。通常取伪F统计量较大而类数较小的聚类水平。

4)伪t2统计量伪用此统计量评价合并类CK和类CL的效果，该值大说明合并的两个类CK和CL是很分开的，不应合并这两个类，而应该取合并前的水平。当然，采用不同的分类方法会得到不同的分类结果，有时即使是同一种聚类方法，因距离的定义方法不同也会得到不同的分类结果。对任何观测数据都没有唯一“正确的”分类方法。实际应用中，常采用不同的分类方法对数据进行分类，可以提出多种分类意见，由实际工作者决定所需要的分类数和分类情况。SAS的聚类分析过程CLUSTER

谱系聚类(Q型聚类分析)VARCLUS

变量聚类(R型聚类分析)FASTCLUSK均值快速聚类，适用于大样本(Q型聚类分析)MODECLUS

非参数聚类(Q型聚类分析)TREE

绘制树结构图，通过CLUSTER和VARCLUS过程计算得到的聚类结果，绘制出系统聚类的谱系图。8.1.3用CLUSTER过程和TREE过程进行系统聚类1.CLUSTER过程系统聚类CLUSTER过程的一般格式为：PROCCLUSTERmethod=…<选项列表>；

VAR<聚类用变量>；ID<变量名>；/*标记样本RUN；其中：

1)PROCCLUSTER语句为调用CLUSTERS过程的开始，其常用选项及功能见表8-2。其中method=..是必选项!

2)VAR语句指定用来聚类的数值型变量。如果缺省，则使用没有列在其他语句中的所有数值型变量。

3)COPY语句把指定的变量复制到OUTTREE=的数据集中，以备后用。

4)ID语句中指定的变量用于区分聚类过程中的输出及OUTTREE数据集中的观测。2.TREE过程

TREE过程可以把CLUSTER过程产生的OUTTREE=数据集作为输入，画出聚类谱系图，并按照用户指定的聚类水平(类数)产生分类结果数据集。一般格式如下：PROCTREE<选项列表>；ID<变量>；RUN；其中：

1)PROCTREE语句为调用TREE过程的开始，其常用选项及功能见表8-3。表8-3PROCTREE语句的常用选项

2)COPY语句把输入数据集中的变量复制到输出数据集。

3)ID语句用于指定在输出树状图中的识别对象，ID变量可以是字符或数值变量。如果省略，TREE过程将使用变量_NAME_。选项名称功能说明DATA=数据集指定从CLUSTER过程生成的OUTTREE数据集作为输入。OUT=数据集指定包含最后分类结果(每一个观测属于哪一类，用一个CLUSTER变量区分)的输出数据集。NCLUSTERS指定最后把样本观测分为多少个类。HORIZONTAL横向画聚类谱系图。3.应用实例【例8-1】表8-4是全国沿海10省市农民2004年支出情况的汇总资料，表中涉及生活消费支出情况的八个指标。假定上述数据已经存放在数据集Mylib.nm10。地区食品衣着居住家庭设备及服务医疗保健交通和通讯文教、娱乐及服务其他商品及服务天津1017.72181.21508.06108.51177.10230.41376.8742.23河北780.09127.06340.8880.42115.97176.60182.5631.33辽宁962.00154.97290.0872.58145.19186.77217.9543.42上海2191.15279.731446.15344.41424.55720.37805.55116.94江苏1317.88163.53467.62141.43163.16293.07373.3972.47浙江1838.57258.58798.88242.09326.12496.86597.96100.05福建1408.54159.60430.14154.43136.40306.06313.09107.32山东1000.13139.18365.97110.12155.85221.93298.2397.85广东1581.68116.83494.89131.17153.17350.27314.3498.44广西1047.5864.42311.4864.8783.64140.13178.8337.65试利用汇总资料对10个地区进行分类(1)使用CLUSTER过程为了进行系统聚类并产生帮助确定类数的统计量，使用如下代码：procclusterdata=mylib.nm10standardmethod=ward

outtree=otreepseudo;copygroup;/*group是城市名的变量名称*/run;把此变量复制到数据集otree中,以备制作谱系聚类图结果的最后部分为聚类分析的完整过程(ClusterHistory)，如图，内容按列划分从左到右依次为：“NCL”为类别数量，表示新类别形成后类别的总数；“--ClustersJoined---”为合并的类别，指明这一步合并了哪两个类，有两列。其中OBxxx表示某一个原始样品，而CLxxx表示在某一个聚类水平上产生的类。“FREQ”表示这次合并得到的类有多少个样品。“SPRSQ”是半偏R2，“RSQ”是R2，“PSF”为伪F统计量，“PST2”为伪t2统计量，“Tie”指示距离最小的候选类对是否有多对，本例全无。(2)确定分类个数

1)R2统计量（列标题为RSQ）用于评价每次合并成NCL个类时的聚类效果。R2越大说明NCL个类越分开，故聚类的效果好。R2的值总是在0和1之间，而且R2的值总是随着分类个数NCL的减少而变小。通过查看R2值的变化，可以确定n个样品分为几类最为合适。本例中，分为3个类之前(NCL>3)的并类过程中R2的减少是逐渐的，改变不大；当分为3类时的R2=0.838，而下一次合并后分为2类时R2下降较多(R2=0.721)。这时通过分析R2统计量可得出分为3个类是较合适的。查看R2变化的大小也可以由合并类时的半偏R2(列标题为SPRSQ)得到。半偏R2的值是上一步R2与该步R2的差值，故某步的半偏R2值越大，说明上一步合并的效果好。本例中半偏R2最大和次大分别为NCL=1和2，说明根据半偏R2准则分为两个类或三个类是较合适的。

2)伪F统计量(列标题为PSF)用于评价分为NCL个类的聚类效果。伪F值越大表示这些观测样品可显著地分为NCL个类。本例中伪F最大和次大依次为NCL=2和5（局部），说明根据伪F准则分为两个类、五个类是较合适的。

3)伪t2统计量用以评价此步合并类的效果。由该统计量的定义知伪t2值大表明上一次合并的两个类是很分开的，也就是上一次聚类的效果是好的。本例中伪t2最大和次大分别为NCL=1和2，说明根据伪t2准则分为两个类或三个类是较合适的。由此看出：R2准则支持分为两类和三类；伪F统计量支持分为两类和五类；伪t2统计量支持分为两类和三类。综合分析认为，用Ward法10个地区分为两类或三类较合适。

使用如下代码画出谱系图proctreedata=otreehorizontal;IDGroup;run;

两类的结果为：G1={上海,浙江}，G2={天津,江苏,福建,广东,山东,河北,辽宁,广西}。三类的结果为：G1={上海,浙江}，G2={天津,江苏,福建,广东,山东}，G3={河北,辽宁,广西}。半偏R的平方相仿地，可以使用类平均法、中间距离法、可变类平均法等方法。不同的聚类方法得到的聚类结果或多或少会有些差别，在实际应用中，应综合各种计算结果，提出合适的分类个数。Try:作聚类分析投资者comp资金投入（万元）pay回报（万元）incomeA3560B1540C305D808E90358.1.4VARCLUS变量聚类VARCLUS聚类对数值型变量进行分离或分层聚类PROCVARCLUSDATA=数据集聚类方法MAXC=n;VAR变量;RUN;绘制树状图PROCTREEDATA=..ID_NAME_;RUN;例城镇居民消费水平通常用八项指标描述：X1：人均粮食支出X2：人均副食支出X3：烟酒茶支出X4：人均其他副食支出X5：人均衣着商品支出X6：人均日用品支出X7：人均燃料支出X8：人均非商品支出为研究城镇居民消费结构,需将相关性强的指标归并到一起,即指标聚类.dataex18_1;inputx1-x8;cards;7.7848.44820.5122.1215.731.1516.6110.8544.687.3214.5117.1312.081.2611.579.0928.127.49.6217.2611.122.4912.658.3523.537.518.6217.42101.0411.219.2523.756.619.1917.7710.481.7210.517.939.778.4912.9419.2711.052.0413.298.1930.54.729.7816.287.62.5210.327.7329.25.429.4319.298.492.52108.2864.34822.2220.0615.520.7222.897.2145.797.6610.3616.5612.862.2511.697.6850.3711.3513.319.2514.592.7514.878.1437.759.618.4913.159.761.2811.2810.652.417.79.9812.5311.72.3114.696.2535.024.726.2810.037.151.9310.398.8233.77.5910.9818.8214.731.7810.19.4227.938.28.1416.179.421.559.768.6736.057.317.7516.6711.682.3812.886.7738.696.018.8214.7911.441.7413.2912.4776.395.5211.2414.52225.4625.57.2752.653.849.1613.0315.261.9814.5713.4555.855.57.459.559.522.2116.37.1840.917.328.9417.612.751.141