聚类分析的资料

聚类分析的资料第1页/共93页2聚类分析起源于分类学，在考古的分类学中，人们主要依靠经验和专业知识来实现分类。随着生产技术和科学的发展，人类的认识不断加深，分类越来越细，要求也越来越高，有时光凭经验和专业知识是不能进行确切分类的，往往需要定性和定量分析结合起来去分类。于是,数学工具逐渐被引进分类学中，形成了数值分类学。后来随着多元分析的引进，聚类分析又逐渐从数值分类学中分离出来而形成一个相对独立的分支。第2页/共93页3

与多元分析的其他方法相比，聚类分析方法较为粗糙，理论上还不够完善，正处于发展阶段。但是，由于该方法应用方便，分类效果较好，因此越来越为人们所重视。近些年来聚类分析的方法发展较快，内容越来越丰富。第3页/共93页4社会经济领域中存在着大量分类问题：例如：对我国30个省市自治区独立核算工业企业经济效益进行分析，一般不是逐个省市自治区去分析，而较好地做法是选取能反映企业经济效益的代表性指标，如百元固定资产实现利税、资金利税率、产值利税率、百元销售收入实现利润、全员劳动生产率等等，根据这些指标对30个省市自治区进行分类，然后根据分类结果对企业经济效益进行综合评价，就易于得出科学的分析。

第4页/共93页5总之，需要分类的问题很多，聚类分析正是研究这类“物以类聚”问题的一种多元统计分析方法。因此聚类分析这个有用的数学工具越来越受到人们的重视，它在许多领域中都得到了广泛的应用。要提出的是，若将聚类分析和其它方法联合起来使用，如判别分析、主成分分析、回归分析等往往效果更好。第5页/共93页6这里的聚类分析与其他分类方法不同的是在分类之前，并不知道分类的标准，甚至对类的个数、类的属性并不清楚，是在没有任何先验知识的情况下进行的，只是希望通过样品或变量间的相似、相近或关系密切程度等较为模糊的概念将它们加以适当的归类，客观地确定分类标准。第6页/共93页一个简单例子：对学生进行分类学号数学成绩英语成绩00173680026669003848200491880059490第7页/共93页8对这5名学生的分类结果若分成两类，则001号和002号学生应是同一类的，而003、004、005号学生是另一类的。若分成三类，则001号和002号学生应是一类的，003号自成一类，而004号与005号学生是一类的。可见，对学生的分类是在没有指定任何分类标准的前提下进行的，分类的依据完全从数据本身出发，完全依据样品的相似程度来划分的。001号与002号之所以在一类中，完全是由于他们的成绩非常接近，之所以没有与005号分在同一类中，也完全是由于他们的成绩相差很远。这一点与我们经常遇到的分类问题不同（如人类按照性别标准划分，可分为男性与女性，等等，这里是有指定的分类标准的）第8页/共93页9聚类分析正是基于这种出发点，实现对样本数据的自动分类的。第9页/共93页10§5.2距离和相似系数为了将样品(或指标)进行分类，就需要研究样品之间关系。目前用得最多的方法有两个：一种方法是用相似系数，性质越接近的样品，它们的相似系数的绝对值越接近1，而彼此无关的样品，它们的相似系数的绝对值越接近于零。比较相似的样品归为一类，不怎么相似的样品归为不同的类。另一种方法是将一个样品看作p维空间的一个点，并在空间定义距离，距离越近的点归为一类，距离较远的点归为不同的类。

第10页/共93页11变量的类型由于相似系数和距离有各种各样的定义，而这些定义与变量的类型关系极大，因此，首先，介绍变量的类型。由于实际问题中，遇到的变量有的是定量变量(如长度、重量等)，有的是定性变量(如产品等级、性别、职业等)。通常将变量(指标)的类型按以下三种尺度划分：第11页/共93页12变量的类型分为以下三类：间隔尺度scale：变量是用连续的量来表示的，如长度、重量、压力、速度等等。有序尺度ordinal：变量度量时没有明确的数量表示，而是划分一些等级，等级之间有次序关系，如某产品分上、中、下三等，此三等有次序关系，但没有数量表示。名义尺度nominal：变量度量时既没有数量表示，也没有次序关系，如某物体有红、黄、白三种颜色，又如医学化验中的阴性与阳性，市场供求中的“产”和“销”，还有性别、职业、产品的型号等。第12页/共93页13不同类型的变量，在定义距离和相似系数时，其方法有很大差异，使用时必须注意。通常研究比较多的是间隔尺度的变量，因此本章主要给出间隔尺度的距离和相似系数的定义。第13页/共93页14第14页/共93页15问题转变为矩阵的行与行、列与列向量间的相似关系的讨论第15页/共93页16问题转变为矩阵的行与行、列与列的向量间的相似关系的讨论对样品分类(研究行与行之间的相似关系，称为Q-型聚类分析)

对指标分类(研究列与列之间的相似关系，称为R-型聚类分析)第16页/共93页17需要引入所谓的“距离”概念来度量样品间的相似、相近或相关程度的量这里的“距离”是广义的，只要能够度量样品间的相似、相近或相关程度的量都可以称为距离。因此有很多种定义距离的方法。但有三条原则是任何一种距离定义都应该满足的：用d(X,Y)表示样品X与Y间的距离，则它需要满足：1.非负性：d(X,Y)》0，且d(X,Y)=0的充分必要条件是X=Y2.对称性：d(X,Y)=d(Y,X)3.三角不等式：

d(X,Z)《d(X,Y)+d(Y,Z)第17页/共93页

1、Q型聚类分析

常用的距离和相似系数定义(1)距离如果把n个样品(X中的n个行)看成p维空间中n个点，则两个样品间相似程度可用p维空间中两点的距离来度量。令表示样品与的距离。常用的距离有：i)明氏(Minkowski)距离

ii)马氏(Mahalanobis)距离

iii)兰氏(Canberra)距离

iv)斜交叉空间距离第18页/共93页19i)明氏(Minkowski)距离第19页/共93页20采用明氏距离时要注意:一定要采用相同量纲的变量。如果各变量的量纲不同，或当各变量的量纲相同但各变量的测量值相差悬殊时，不能直接采用明氏距离。需要先对数据进行标准化处理，然后再用标准化处理后的数据计算距离。最常用的标准化处理方法是：第20页/共93页21在明氏距离中，最常用的是欧氏距离。主要优点：当坐标轴进行正交旋转时，欧氏距离是保持不变的。因此，如果对原坐标系进行平移和旋转变换，则变换后样品点间的相似情况(即它们间的距离)完全等同于变换前的情形。不足之处：第一、它与各指标的量纲有关第二、它没有考虑指标之间的相关性第21页/共93页22即，变量的数量级和量纲影响着欧氏距离的大小，请看下面的例1（参见下表）：样品号投入的科研人数（人）研&发投入经费（元）研&发课题数（项）1410438000019233617300002134902200008举例说明欧氏距离的明显的不足之处第22页/共93页23欧氏距离受量纲的影响

可见，以元为计量单位时，距离由近到远依次为样品2和3、1和3、1和2，这时经费投入起了决定性作用。以万元为单位时，距离由近到远依次为样品1和2、1和3、2和3，这时人员数投入起了关键作用。可见不同量纲对距离的影响程度。两个样品对样品的欧氏距离元万元（1，2）26500081.623（1，3）218000193.700（2，3）47000254.897第23页/共93页24举例说明欧氏距离的明显的不足之处当改变测量单位时，算出的距离数值不同；再则当数量指标X的各分量代表不同质的东西或者分量的差异很大时，欧氏距离常会出现“大数吃小数”的现象。请看下面的例2：第24页/共93页25这时讨论距离时，需要进行加权，加权的办法之一是从X的分量的离散程度考虑，离差大的分量在距离中应相应地削弱它的影响程度。为此引入马氏距离。马氏距离是由印度统计学家马哈拉诺比斯（Mahalanobis）于1936年引入的，故称为马氏距离。这一距离在多元统计分析中起着十分重要的作用，下面给出它的定义。第25页/共93页26ii)马氏(Mahalanobis)距离第26页/共93页27马氏距离的优缺点

马氏距离既排除了各指标之间相关性的干扰，而且还不受各指标量纲的影响。除此之外，它还有一些优点，如可以证明，将原始数据作一线性交换后，马氏距离仍不改变等等。马氏距离与测量单位无关，但是它夸大了变化微小的变量(或指标)的作用（因为赋予的权重较大），这是马氏距离在实用中的缺点。第27页/共93页28距离矩阵第28页/共93页292.相似系数对样品或变量进行聚类，除了用距离度量对象之间的相似和亲疏程度，还可以使用相似系数来度量，特别是对变量聚类时更常用相似系数。顾名思义，相似系数是描述样品或变量之间相似程度的一个量。与距离的定义一样，可有多种定义相似系数的方法，但是所有的定义一般都满足如下三个条件：第29页/共93页30相似系数的性质用cij表示变量Xi与Xj间的相似系数，则它需要满足：1.cij=+-1的充分必要条件是Xi=a+bXj2.对任意i和j，都有|cij|《13.对称性：cij=cji常用的相似系数有：

i)夹角余弦ii)相关系数第30页/共93页31

i)夹角余弦第31页/共93页32相似矩阵第32页/共93页33

ii)相关系数第33页/共93页34相关系数矩阵第34页/共93页35

2R型聚类分析

P个指标(变量)之间相似性的定义与样品相似性定义类似，但此时是在n维空间中来研究的，变量之间的相似性是通过原始资料矩阵X中P列之间的相似关系来研究的。类似的也有常用的距离和相似系数定义。与Q型聚类分析相比，只是空间的维数不同。常用的距离

i)明氏(Minkowski)距离

ii)马氏(Mahalanobis)距离

iii)兰氏(Canberra)距离常用的相似系数i)夹角余弦

ii)相关系数第35页/共93页36常用的距离和相似系数定义常用的距离

i)明氏(Minkowski)距离

ii)马氏(Mahalanobis)距离

iii)兰氏(Canberra)距离常用的相似系数i)夹角余弦

ii)相关系数在实际问题中的做法是：对样品分类常用距离对变量分类常用相似系数。

并且变量之间的距离常常借助于相似系数来定义距离：第36页/共93页37

聚类分析的内容1.系统聚类法（SPSS能够实现）2.有序样品聚类法3.动态聚类法（SPSS能够实现）4.模糊聚类法5.图论聚类法6.聚类预报法等。本章主要介绍常用的系统聚类法（即第一种方法）第37页/共93页38系统聚类法的基本思想系统聚类法是目前在实际应用中使用最多的一种方法，它是将类由多变少的一种聚类过程。基本思想是：首先定义样品间的距离（或相似系数）以及类与类之间的距离。开始将每个研究对象(样品或指标)各自看成一类、按某种顺序分别称作第1，第2，…，第h类(这时样品间距离与类与类间距离是等价的)；然后根据对象间的相似度量，将h类中最相似的两类合并成一个新类，这样得到h-1类，再在这h-1类中找出最相似的两类合并，得到h-2类，如此下去，直至将所有的对象并成一个大类为止。第38页/共93页39上面聚类的过程可以用谱系聚类图（也叫树形图dendrogram）形象地表达出来。第39页/共93页40在如上的并类过程中会面临这样一个问题：两类之间如何度量其相似程度?为此，需要引进两类之间的“距离”或“相似系数”的概念。正如样品之间的距离可以有不同的定义方法一样，类与类之间的距离也有各种定义。例如，可以定义类与类之间的距离为两类之间最近样品的距离，或者定义为两类之间最远样品的距离，也可以定义为两类重心之间的距离等等。类与类之间采用不同的方法来定义距离，就产生了不同的系统聚类方法。第40页/共93页41§5.3八种系统聚类方法系统聚类分析尽管方法很多，但归类的步骤基本上是一样的，所不同的仅是类与类之间的距离有不同的定义方法，从而得到不同的计算距离的公式。这些公式在形式上不大一样，但最后可将它们统一为一个公式，为上机计算带来很大的方便。1.最短距离法2.最长距离法3.中间距离法4.重心法5.类平均法6.可变类平均法7.可变法8.离差平方和法第41页/共93页42一、系统聚类法的具体步骤：第42页/共93页43二、系统聚类法的八种方法基本内容1.最短距离法（Singlelinkagemethod）2.最长距离法(Completelinkagemethod)3.中间距离法（Medianmethod）4.重心法(Centroidmethod)5.类平均法(Averagelinkagemethod)6.可变类平均法(flexible)7.可变法8.离差平方和法(Ward’sminimumvariancemethod)第43页/共93页44以下用dij表示样品Xi与Xj之间的距离，用Dij表示类Gi与Gj之间的距离第44页/共93页45第45页/共93页46第46页/共93页47第47页/共93页48第48页/共93页49第49页/共93页50第50页/共93页51谱系图(dendrogram)为(横轴为坐标轴，并标注了并类的距离)：第51页/共93页52做R型聚类分析的情形但是，常常采用相似系数来对变量进行防呢类，这时应改为取最大的相似系数（用Cij表示）的两类进行合并。也可以将相似系数转化为距离，这时转化公式可取为第52页/共93页53接下来，再找非对角线上的最小元素的两类合并，直至到所有的样品都归结为一类为止第53页/共93页54如下图所示第54页/共93页55第55页/共93页56第56页/共93页57谱系聚类图展示了系统聚类的全过程：最短与最长距离法容易受到异常值的干扰，从而严重扭曲了类有类的实际距离，应该在应用中加以注意。第57页/共93页583.中间距离法

（Medianmethod）类与类之间的距离既不取两类最近样品之间的距离，也不取两类最远样品间的距离，而是取介于两者中间的距离，这被称为中间距离法。该方法在一定程度上克服了最短距离法与最长距离法的不足。第58页/共93页59如果在某一步将类Gp与类Gq合并为Gr，则任意一类Gk与Gr的距离的平方的递推公式为（此公式来自于三角形中线长度的计算公式）这是一个合并两类的递推公式第59页/共93页604.可变法将中间距离法的公式推广为更一般的情形，将公式中的三项的系数依赖于某个可取不同值的参数，那么合并两类距离平方的递推公式就可写为这里的变参数，称为可变法第60页/共93页615.重心法（Centroidmethod）前面的定义两类距离方法都没有体现出每类中包含的样品数，为此，重心法就定义两类之间距离为两类重心之间的距离。设Gp与Gq的重心（即该类样品的均值，视为虚拟的样品点）分别为，则Gp与Gq的距离定义为第61页/共93页626.类平均法重心法虽然有较好的代表性，但是并未充分利用各个样品的信息，为此给出类平均法，它定义两类间距离的平方为这两类中的所有两两样品（构成一个样品对）距离平方的平均：递推公式为第62页/共93页63类平均法利用了所有样品的信息，是一种较好的聚类方法。在类的浓缩与扩张方面也比较适中，值得推荐。请参阅第4小节。

第63页/共93页647.可变类平均法由于类平均法中的递推公式中没有反映出Gp与Gq之间距离Dpq的影响，所以将任意一类Gk与新类Gr的距离平方的递推公式改写为加入Dpq和变参数的形式：而两类的距离定义仍是第64页/共93页658.离差平方和法该方法的基本思想来源于方差分析：如果分类正确的话，同类样品间的离差平方和就应当较小，而类与类间的离差平方和就应当较大。具体做法是，首先各个样品各自成为一类，每次缩小一类，而每缩小一类，总的离差平方和就要增大，应选择使总离差平方和S增加最少的那样两类合并，直到所有的样品都归为一类为止。第65页/共93页66若定义两类Gp与Gq之间的距离平方为（S为平方和）就可使Ward法与前七种系统聚类法统一起来，并可以证明，Ward法合并类的递推公式为；第66页/共93页67这八种方法可统一起来上述八种系统聚类方法的步骤是完全一致的（都是类数由多到少的类合并的过程），所不同的仅仅是两类之间的距离定义的不同，从而推导出来的合并后的新类与任意一类的距离递推公式不同，但这些公式在1967年由Lance和Williams统一起来，当样品间距离采用欧氏距离时，八种递推公式有如下统一的形式：第67页/共93页68统一的合并类的递推公式第68页/共93页69八种系统聚类法的比较各种系统聚类方法都有其适合的场所，选用哪种方法需视实际问题和对聚类结果的要求而定。这里要考虑各种方法的性质（此处略去）相比较而言，类平均法与离差平方和法的数学性质和效果都是比较理想的。建议使用。第69页/共93页70SPSS提供了两种聚类方法一种是分层聚类分析法（即系统聚类方法，HierarchicalCluster，）另一种是快速聚类分析法(属于动态聚类法或逐步聚类法中的一种，即k均值法：K-MeansCluster，)第70页/共93页71SPSS提供的度量两类距离的方法1.最短距离法

(Nearestneighbor）2.最长距离法(Furthestneighbor)3.中间距离法（Medianclustering）4.重心法

(Centroidclustering)5.组间平均连接法（Between-groupsLinkage）6.组内平均连接法（Within-groupsLinkage）7.离差平方和法（Ward’smethod）第71页/共93页72各种方法的基本含义1.最短距离法

(Nearestneighbor）2.最长距离法(Furthestneighbor)这两种定义类与类之间距离的含义与前面一样，在此不赘述。3.组间平均连接法（Between-groupsLinkage）:定义两类间距离为两类之间的所有的样品对间的平均距离。实际上这就是前面的类平均法。第72页/共93页73各种方法的基本含义4.组内平均连接法（Within-groupsLinkage）:与组间平均连接法有些类似，也是定义两类间距离为所有样品对之间的平均距离，只是这里的样品对不仅包括两类之间的样品对，还包括同一类内部的样品对。第73页/共93页745.中间距离法（Medianclustering）6.重心法

(Centroidclustering)与前面一样，已经介绍过了。7.离差平方和法（Ward’smethod）该方法的出发点是，在聚类过程中，使得本类内各个样品对的欧氏距离平方总和增加最少的那样两类合并为一类。第74页/共93页75动态聚类法之一：k均值法系统聚类法的缺陷是，当样品数n很大时，其计算量很大，需要占用较大的计算机内存和较多时间。动态聚类法正是基于克服该缺点而产生的。动态聚类法的基本思想：选择一批凝聚点，或给出一个初始分类，让样品按照某中原则向凝聚点凝聚，对凝聚点进行不断的修改或迭代，直至分类比较合理或迭代稳定为止。类的个数k可以事先给定，也可以在聚类过程中确定。选择初始凝聚点（或给出初始分类）的一种简单方法是随机分割样品的方法。第75页/共93页76K均值聚类法（k-meansCluster）的基本步骤该方法是麦奎因（MacQueen)于1967年提出的一种算法。其基本步骤为：（1）选择k个样品作为凝聚点，或者将所有样品分成k个初始类，然后以这k个类的重心（均值）作为初始凝聚点。（2）对除了凝聚点以外的所有样品逐个归类，将每个样品归入凝聚点离它最近的那个类（通常采用欧氏距离），该类的凝聚点就更新为这一类目前的均值，直至所有的样品都归了类（3）重复步骤（2），直至所有的样品都不能再分配为止。第76页/共93页77该方法的最终聚类结果在一定程度上依赖于初始凝聚点或初始分类的选择。经验表明，聚类过程中的绝大多数变化都发生在第一次再分配中。第77页/共93页78一个简单的例子假设有五个样品，每个只测量了一个指标，分别为1，2，6，8，11，试用k均值法将它们分类，指定k=2。具体步骤为：第78页/共93页79第79页/共93页80第80页/共93页81第81页/共93页82三、类个数的确定

聚类分析中，类的个数如何确定的问题是一个十分困难的问题，人们至今仍未找到令人满意的方法；但这又是一个不可回避的问题．迄今为止，我们只是直观地叙述了“类”的概念，并未给出严格的定义，但要对各种不同的类给予统一的定义是比较困难的，“类”的概念是一个模糊的概念．当然可以从不同的角度给出类的不同定义，但在实际应用中，人们并不完全从类的定义来确定类．

下面介绍确定类个数的几种常见方法第82页/共93页831．由适当的阀值确定选定某种聚