多元统计分析 第5章 聚类分析教学文案.ppt

《多元统计分析 第5章 聚类分析教学文案.ppt》由会员分享，可在线阅读，更多相关《多元统计分析 第5章 聚类分析教学文案.ppt（94页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、多元多元统计分析分析 第第5 5章章 聚聚类分析分析相似性和相异性相似性和相异性nSimilarity数值测量两个数据对象类似程度数值测量两个数据对象类似程度目标越相似时值越大目标越相似时值越大通常介于通常介于 0,1nDissimilarity(e.g.,距离距离distance)数值测量两个数据对象差异程度数值测量两个数据对象差异程度Lower when objects are more alikeMinimum dissimilarity is often 0Upper limit variesn邻近度邻近度Proximity refers to a similarity or diss

2、imilarity数据矩阵和相异度矩阵数据矩阵和相异度矩阵nData matrixn data points with p dimensionsnDissimilarity matrixn data points,but registers only the distance A triangular matrix例例:数据矩阵和相异度矩阵数据矩阵和相异度矩阵Dissimilarity Matrix(with Euclidean Distance)Data Matrix第二节第二节 相似性的量度相似性的量度 一一 样品相似性的度量样品相似性的度量 二二 变量相似性的度量变量相似性的度量 含含名

3、义名义变量变量样本相似性度量样本相似性度量n例例：学学员资员资料料包含包含六个六个属性属性：性：性别别（男男或或女女）；外；外语语语语种种（英、日英、日或或俄俄）；专业专业（统计统计、会、会计计或或金融金融）；职业职业（教教师师或或非教非教师师）；居住；居住处处（校内校内或或校外校外）；学；学历历（本科本科或或本科以本科以下下）现现有两名学有两名学员员：X1=（男，英，（男，英，统计统计，非教，非教师师，校外，本科），校外，本科）X2=（女，英，金融，教（女，英，金融，教师师，校外，本科以下），校外，本科以下）对应变对应变量取量取值值相同相同称称为为配合的配合的，否否则则称称为为不配合的不配合

4、的记记配合的配合的变变量数量数为为m1，不配合的，不配合的变变量数量数为为m2，则则样样本本之之间间的的距离可定距离可定义为义为本例中本例中X1 与与X2 之之间间的距离的距离为为2/3二进制属性的邻近度量二进制属性的邻近度量n二进制数据的列联表二进制数据的列联表contingency table n对称二元变量的距离侧度对称二元变量的距离侧度:n不对称二元变量的距离侧度不对称二元变量的距离侧度:nJaccard系数系数(不对称二元变量不对称二元变量的相似性侧度的相似性侧度):nNote:Jaccard coefficient is the same as“coherence”:Object

5、iObject j二进制属性的相异度量二进制属性的相异度量nExample性别是对称属性性别是对称属性The remaining attributes are asymmetric binary令令Y and P 值为值为1,且且N值为值为0有序变量有序变量Ordinal Variablesn一个序变量可以离散的或连续的一个序变量可以离散的或连续的nOrder is important,e.g.,ranknCan be treated like interval-scaled 用他们的序代替用他们的序代替xif映射每一个变量的范围于映射每一个变量的范围于0,1，用如下值代替第，用如下值代替第f

6、-th变量变量的的i-th对象对象混合型属性混合型属性 nA database may contain all attribute typesNominal,symmetric binary,asymmetric binary,numeric,ordinaln可以用加权法计算合并的影响可以用加权法计算合并的影响f is binary or nominal:dij(f)=0 if xif=xjf,or dij(f)=1 otherwisef is numeric:use the normalized distancef is ordinal Compute ranks rif and Treat

7、 zif as interval-scaled规范数值数据规范数值数据nZ-score:X:需标准化的原始数值需标准化的原始数值,:总体均值总体均值,:标准差标准差在标准偏差单位下，原始分数和总体均值之间的距离在标准偏差单位下，原始分数和总体均值之间的距离“-”,“+”n另一种方法另一种方法:Calculate the mean absolute deviation其中其中standardized measure(z-score):n使用平均绝对偏差比使用标准差更稳健使用平均绝对偏差比使用标准差更稳健一、样品相似性的度量一、样品相似性的度量nQ型聚类分析，常用距离来测度样品之间的相似程型聚类分

8、析，常用距离来测度样品之间的相似程度度n每个样品有每个样品有p个指标（变量）从不同方面描述其性质，个指标（变量）从不同方面描述其性质，形成一个形成一个p维的向量。如果把维的向量。如果把n个样品看成个样品看成p维空间维空间中的中的n个点，则两个样品间相似程度就可用个点，则两个样品间相似程度就可用p维空间维空间中的两点距离公式来度量。中的两点距离公式来度量。n令令dij 表示样品表示样品Xi与与Xj的距离，一般应满足：的距离，一般应满足：(i)dij0，对对一切一切i,j；(ii)dij=0，当且，当且仅仅当第当第i个个样样品与第品与第j个个样样品的各品的各变变量量值值相同；相同；(iii)dij

9、=dji，对对一切一切i,j；(iv)dijdik+dkj，对对一切一切i,j,k。1明考夫斯基距离明考夫斯基距离(明氏距离明氏距离)一、样品相似性的度量一、样品相似性的度量Example:Minkowski DistanceDissimilarity MatricesManhattan(L1)Euclidean(L2)Supremum 2马氏距离马氏距离 设设Xi与与Xj是来自均值向量为是来自均值向量为 ，协方差为，协方差为（0）的总体的总体G中的中的p维样品，则两个样品间的马氏距离为维样品，则两个样品间的马氏距离为 n马氏距离又称为广义欧氏距离马氏距离又称为广义欧氏距离马氏距离考虑了观测变

10、量之间的相关性马氏距离考虑了观测变量之间的相关性若各变量之间相互独立，马氏距离退化加权欧氏距离若各变量之间相互独立，马氏距离退化加权欧氏距离马氏距离还考虑了观测变量之间的变异性，不再受各指标量纲马氏距离还考虑了观测变量之间的变异性，不再受各指标量纲的影响的影响一、样品相似性的度量一、样品相似性的度量3兰氏距离兰氏距离 它仅适用于一切它仅适用于一切Xij0的情况的情况可以克服各个指标之间量纲的影响；可以克服各个指标之间量纲的影响；对大的奇异值不敏感，特别适合于高度偏倚的数对大的奇异值不敏感，特别适合于高度偏倚的数据；据；但它没有考虑指标之间的相关性；但它没有考虑指标之间的相关性；一、样品相似性的

11、度量一、样品相似性的度量n不同的距离公式的侧重点和实际意义都有所不同不同的距离公式的侧重点和实际意义都有所不同n同一批数据采用不同的距离公式，可能会得到不同的分类结果同一批数据采用不同的距离公式，可能会得到不同的分类结果n距离公式选择基本原则：距离公式选择基本原则：要考虑所选择的距离公式在实际应用中有明确的意义要考虑所选择的距离公式在实际应用中有明确的意义欧氏距离就有非常明确的空间距离概念欧氏距离就有非常明确的空间距离概念马氏距离有消除量纲影响的作用马氏距离有消除量纲影响的作用要综合考虑对样本观测数据的预处理和将要采用的聚类分要综合考虑对样本观测数据的预处理和将要采用的聚类分析方法析方法如在进

12、行聚类分析之前已经对变量作了标准化处理，则通常可采用欧氏距如在进行聚类分析之前已经对变量作了标准化处理，则通常可采用欧氏距离离要考虑研究对象的特点和计算量的大小要考虑研究对象的特点和计算量的大小n归根到底：归根到底：Application Driven:根据研究对象的特点不同做出根据研究对象的特点不同做出具体分折具体分折Try一、样品相似性的度量一、样品相似性的度量二、变量相似性的度量二、变量相似性的度量n相对于数据的大小，更多地对变量的变化趋势或方相对于数据的大小，更多地对变量的变化趋势或方向感兴趣向感兴趣n变量间的相似性变量间的相似性-方向趋同性或方向趋同性或“相关性相关性”“夹角余弦法夹

13、角余弦法”“相关系数相关系数”余弦相似性余弦相似性 Cosine SimilaritynA document can be represented by thousands of attributes,each recording the frequency of a particular word(such as keywords)or phrase in the document.nOther vector objects:gene features in micro-arrays,nApplications:information retrieval,biologic taxonomy,

14、gene feature mapping,.nCosine measure:If d1 and d2 are two vectors(e.g.,term-frequency vectors),then cos(d1,d2)=(d1 d2)/|d1|d2|,where indicates vector dot product,|d|:the length of vector d Example:Cosine Similarityncos(d1,d2)=(d1 d2)/|d1|d2|,where indicates vector dot product,|d|:the length of vect

15、or dnEx:Find the similarity between documents 1 and 2.d1=(5,0,3,0,2,0,0,2,0,0)d2=(3,0,2,0,1,1,0,1,0,1)d1 d2=5*3+0*0+3*2+0*0+2*1+0*1+0*1+2*1+0*0+0*1=25|d1|=(5*5+0*0+3*3+0*0+2*2+0*0+0*0+2*2+0*0+0*0)0.5=(42)0.5 =6.481|d2|=(3*3+0*0+2*2+0*0+1*1+1*1+0*0+1*1+0*0+1*1)0.5=(17)0.5 =4.12cos(d1,d2)=0.942相关系数相关系

16、数变量变量Xi与与Xj的相关系数定义为的相关系数定义为 显然有，显然有，rij 1。二、变量相似性的度量二、变量相似性的度量n它们的绝对值都小于它们的绝对值都小于1，统记为，统记为cij当当 cij=1时，说明变量时，说明变量Xi与与Xj完全相似；完全相似；当当 cij 近似于近似于1时，说明变量时，说明变量Xi与与Xj非常密切；非常密切；当当 cij =0时，说明变量时，说明变量Xi与与Xj完全不一样；完全不一样；当当 cij 近似于近似于0时，说明变量时，说明变量Xi与与Xj差别很大。差别很大。n变换为距离度量：变换为距离度量：dij=1 cij 或或 dij2=1 cij2 二、变量相似

17、性的度量二、变量相似性的度量距离度量与相似性度量距离度量与相似性度量n由距离来构造相似系数由距离来构造相似系数总总是可能的：是可能的：n由相似系数构造距离并不由相似系数构造距离并不总总是可行的是可行的nGower证证明，当相似系数矩明，当相似系数矩阵阵(cij)为为非非负负定定时时：则则dij满满足距离定足距离定义义的四个条件的四个条件第三节第三节 系统聚类分析法系统聚类分析法 一一 系统聚类的基本思想系统聚类的基本思想 二二 类间距离与系统聚类法类间距离与系统聚类法 三三 类间距离的统一性类间距离的统一性 一、系统聚类的基本思想一、系统聚类的基本思想n距离相近的样品（或变量）先聚成类，距离相

18、远的距离相近的样品（或变量）先聚成类，距离相远的后聚成类，过程一直进行下去，每个样品（或变量）后聚成类，过程一直进行下去，每个样品（或变量）总能聚到合适的类中总能聚到合适的类中n系统聚类过程：（假设总共有系统聚类过程：（假设总共有n个样品（或变量）个样品（或变量）1.将每个样品（或变量）独自聚成一类，共有将每个样品（或变量）独自聚成一类，共有n类；类；2.根据所确定的样品（或变量）的根据所确定的样品（或变量）的“距离距离”公式，把距离公式，把距离较近的两个样品（或变量）聚合为一类，其它的样品较近的两个样品（或变量）聚合为一类，其它的样品（或变量）仍各自聚为一类，共聚成（或变量）仍各自聚为一类，

19、共聚成n 1类；类；3.将将“距离距离”最近的两个类进一步聚成一类，共聚成最近的两个类进一步聚成一类，共聚成n 2类；类；4.循环之循环之5.将所有的样品（或变量）全聚成一类将所有的样品（或变量）全聚成一类n谱系图谱系图描绘聚类过程描绘聚类过程二、类间距离与系统聚类法二、类间距离与系统聚类法n类间距离类间距离-类与类之间的距离类与类之间的距离n定义不同，方法不同，结果不同定义不同，方法不同，结果不同最短距离法最短距离法(Single linkage)最长距离法最长距离法(Complete method)中间距离法中间距离法(Median method)重心法重心法(Centriod metho

20、d)类平均法类平均法(Avarage linkage)可变类平均法可变类平均法(Flexible-beta method)可变法可变法(McQuitty,MCQ)离差平方和法离差平方和法(Ward)ndij表示样品表示样品Xi与与Xj之间距离，用之间距离，用Dij表示类表示类Gi与与Gj之间的距离。之间的距离。1.最短距离法最短距离法定义类间距离为两类最近样品的距离，即为定义类间距离为两类最近样品的距离，即为 合并成一个新类后，则任一类与之的距离为合并成一个新类后，则任一类与之的距离为 二、类间距离与系统聚类法二、类间距离与系统聚类法n最短距离法步骤如下：最短距离法步骤如下：（1）根据选用的距

21、离计算样品的两两距离，得一距离阵）根据选用的距离计算样品的两两距离，得一距离阵记为记为D（0），开始每个样品自成一类，显然这时，开始每个样品自成一类，显然这时Dij=dij（2）找出距离最小元素，设为）找出距离最小元素，设为Dpq，则将，则将Gp和和Gq合并成一合并成一个新类，记为个新类，记为Gr，即，即Gr=Gp，Gq（3）计算新类与其它类的距离）计算新类与其它类的距离 （4）重复（）重复（2）、（）、（3）两步，直到所有元素。并成一类）两步，直到所有元素。并成一类为止为止如果某一步距离最小的元素不止一个，则对应这些最小元如果某一步距离最小的元素不止一个，则对应这些最小元素的类可以同时合并素

22、的类可以同时合并二、类间距离与系统聚类法二、类间距离与系统聚类法n例：设有六个样品，每个只测量一个指标，分别是例：设有六个样品，每个只测量一个指标，分别是1，2，5，7，9，10，试用最短距离法将它们分类。，试用最短距离法将它们分类。（1）样品采用绝对值距离，计算样品间的距离阵）样品采用绝对值距离，计算样品间的距离阵D（0）二、类间距离与系统聚类法二、类间距离与系统聚类法（2）D（0）中最小的元素是中最小的元素是D12D561，于是将，于是将G1和和G2合合并成并成G7，G5和和G6合并成合并成G8，计算新类与其它类的距离，计算新类与其它类的距离D（1）二、类间距离与系统聚类法二、类间距离与系

23、统聚类法（3）在）在D（1）中最小值是中最小值是D34D482，由于，由于G4与与G3合并，合并，又与又与G8合并，因此合并，因此G3、G4、G8合并成一个新类合并成一个新类G9，其与其，其与其它类的距离它类的距离D（2）二、类间距离与系统聚类法二、类间距离与系统聚类法（4）最后将）最后将G7和和G9合并成合并成G10，这时所有的六个样品聚为一，这时所有的六个样品聚为一类，其过程终止。类，其过程终止。n谱系图表示谱系图表示横坐标的刻度表示并类的距离横坐标的刻度表示并类的距离二、类间距离与系统聚类法二、类间距离与系统聚类法二、类间距离与系统聚类法二、类间距离与系统聚类法n再找再找距离最小两类距离

24、最小两类并类，直至所有的样品全归为一类为止并类，直至所有的样品全归为一类为止n最长距离法与最短距离法只有两点不同：最长距离法与最短距离法只有两点不同：一是类与类之间的距离定义不同；一是类与类之间的距离定义不同；一是计算新类与其它类的距离所用的公式不同一是计算新类与其它类的距离所用的公式不同二、类间距离与系统聚类法二、类间距离与系统聚类法3.中间距离法（折中）中间距离法（折中）中间距离将类中间距离将类Gp与与Gq类合并为类类合并为类Gr，则任意的类，则任意的类Gk和和Gr的距的距离公式为离公式为 (14 0)n设设DkqDkp最短距离法，则最短距离法，则Dkr=Dkp；最长距离法，则最长距离法，

25、则Dkr=Dkq。中间距离法：取它们的中间中间距离法：取它们的中间某某一点一点二、类间距离与系统聚类法二、类间距离与系统聚类法n特别当特别当 =14，它表示取，它表示取中间点中间点算距离，公式为算距离，公式为 二、类间距离与系统聚类法二、类间距离与系统聚类法二、类间距离与系统聚类法二、类间距离与系统聚类法4.重心法重心法类间距离为两类重心（各类样品的均值）的距离类间距离为两类重心（各类样品的均值）的距离重心指标对类有很好的代表性，但利用各样本的信息不充分重心指标对类有很好的代表性，但利用各样本的信息不充分n n推导如下：推导如下：二、类间距离与系统聚类法二、类间距离与系统聚类法二、类间距离与系

26、统聚类法二、类间距离与系统聚类法n 二、类间距离与系统聚类法二、类间距离与系统聚类法n例例：（：（数据同上例）有六个样品，每个只测量一个指标，分数据同上例）有六个样品，每个只测量一个指标，分别是别是1，2，5，7，9，10n试用重心法将它们聚类试用重心法将它们聚类（1）样品采用欧氏距离，计算样品间的平方距离阵）样品采用欧氏距离，计算样品间的平方距离阵D2（0）二、类间距离与系统聚类法二、类间距离与系统聚类法（2）D2（0）中最小的元素是中最小的元素是D212D2561，于是将，于是将G1和和G2合并成合并成G7，G5和和G6合并成合并成G8，并计算新类与，并计算新类与其它类的距离得到距离阵其它

27、类的距离得到距离阵D2（1）其中，其中，二、类间距离与系统聚类法二、类间距离与系统聚类法（3）在）在D2（1）中最小值是中最小值是D2344，那么，那么G3与与G4合并一个新合并一个新类类G9，其与其它类的距离，其与其它类的距离D2（2）：二、类间距离与系统聚类法二、类间距离与系统聚类法（4）其中最小值是）其中最小值是12.5，那么合并一个新类，其与其它类，那么合并一个新类，其与其它类的距离：的距离：二、类间距离与系统聚类法二、类间距离与系统聚类法（5）最后将）最后将G7和和G10合并成合并成G11，这时所有的六个样品聚为一类，这时所有的六个样品聚为一类，其过程终止。其过程终止。n谱系图表示：

28、谱系图表示：二、类间距离与系统聚类法二、类间距离与系统聚类法二、类间距离与系统聚类法二、类间距离与系统聚类法n与最短距离法比较一下：与最短距离法比较一下：二、类间距离与系统聚类法二、类间距离与系统聚类法5.类平均法类平均法类间距离平方取为这两类元素两两之间距离平方的平均数类间距离平方取为这两类元素两两之间距离平方的平均数6.可变类平均法可变类平均法类平均法中没有反映出类平均法中没有反映出Gp和和Gq之间的距离之间的距离Dpq的影的影响响将将Gp和和Gq合并为新类合并为新类Gr，类，类Gk与新并类与新并类Gr的距离公的距离公式推广为：式推广为：其中其中 是可变的且是可变的且 1二、类间距离与系统

29、聚类法二、类间距离与系统聚类法二、类间距离与系统聚类法二、类间距离与系统聚类法8.离差平方和法（离差平方和法（Ward方法）方法）n基本思想来自于方差分析基本思想来自于方差分析如果分类正确，同类样品的离差平方和应当较小，类与类的离如果分类正确，同类样品的离差平方和应当较小，类与类的离差平方和较大。差平方和较大。n具体步骤：具体步骤：先将先将n个样品各自成一类，然后每次缩小一类，每缩小一类，个样品各自成一类，然后每次缩小一类，每缩小一类，离差平方和就要增大，选择使其增加最小的两类合并，直到所离差平方和就要增大，选择使其增加最小的两类合并，直到所有的样品归为一类为止。有的样品归为一类为止。二、类间

30、距离与系统聚类法二、类间距离与系统聚类法n设将设将n个样品分成个样品分成k类类G1，G2，Gk，用，用Xit表示表示Gt中的第中的第i个样品，个样品，nt表示表示Gt中样品的个数，中样品的个数，是是Gt的重心，则的重心，则Gt的样品的样品离差平方和为离差平方和为 二、类间距离与系统聚类法二、类间距离与系统聚类法n 二、类间距离与系统聚类法二、类间距离与系统聚类法三、类间距离的统一三、类间距离的统一n上述八种系统聚类法的步骤完全一样，只是距离的递推公式不同。兰斯上述八种系统聚类法的步骤完全一样，只是距离的递推公式不同。兰斯（Lance）和威廉姆斯（）和威廉姆斯（Williams）于）于1967年

31、给出了一个统一的公式。年给出了一个统一的公式。ap、aq、是参数是参数不同的系统聚类法，它们取不同的值不同的系统聚类法，它们取不同的值n注意注意：不同的聚类方法结果不一定完全相同，一般只是大致相似不同的聚类方法结果不一定完全相同，一般只是大致相似可将聚类结果与实际问题对照，看哪一个结果更符合经验可将聚类结果与实际问题对照，看哪一个结果更符合经验表表 系统聚类法参数表系统聚类法参数表三、类间距离的统一三、类间距离的统一n单调单调性：性：令令Di是系是系统统聚聚类类法中第法中第i次并次并类时类时的距离，的距离，如果一种系如果一种系统统聚聚类类法能法能满满足足D1D2D3 n单调单调性符合系性符合系

32、统统聚聚类类法的思想，先合并法的思想，先合并较较相似的相似的类类，后合并后合并较较疏疏远远的的类类n最短距离法、最最短距离法、最长长距离法、可距离法、可变变法、法、类类平均法、可平均法、可变类变类平均法和离差平方和法都具有平均法和离差平方和法都具有单调单调性性n中中间间距离法和重心法距离法和重心法不具有不具有单调单调性性四、单调性四、单调性五、类的个数五、类的个数n如果能如果能够够分成若干个很分开的分成若干个很分开的类类，则类则类的个数就比的个数就比较较容易确定；容易确定；n如果无如果无论论怎怎样样分都很分都很难难分成明分成明显显分开的若干分开的若干类类，则则类类个数的确定就比个数的确定就比较

33、较困困难难n常用方法：常用方法：给给定一个定一个阈值阈值T通通过过观观察察谱谱系系图图，给给出一个合适的出一个合适的阈值阈值T，要求，要求类类与与类类之之间间的距的距离要大于离要大于T有有较较强强的主的主观观性性观测样观测样品的散点品的散点图图如果如果样样品只有两个或三个品只有两个或三个变变量，量，则则可通可通过观测过观测数据的散点数据的散点图图来确来确定定类类的个数的个数如果如果变变量个数超量个数超过过三个，可先降三个，可先降维维(费费舍舍尔尔判判别别法等）法等）使用使用统计统计量（模型量（模型选择选择）n观测散点图可以从直觉上来判断所采用的聚类方法是否合理观测散点图可以从直觉上来判断所采用

34、的聚类方法是否合理n可直接从散点图中进行主观的分类可直接从散点图中进行主观的分类五、类的个数五、类的个数-寻找寻找“自然的自然的”类类五、类的个数五、类的个数画图法画图法n依次尝试不同的依次尝试不同的k值值(x)，计算某个度量（统计量、距离等），计算某个度量（统计量、距离等）(y)n画图，显示画图，显示y随随x的变化趋势的变化趋势n找拐点，作为确定找拐点，作为确定k的根据的根据n当曲线拐点很平缓时，可选择的当曲线拐点很平缓时，可选择的k很多，这时需要用其它很多，这时需要用其它的办法来确定的办法来确定第四节第四节 K均值聚类分析均值聚类分析 n系统聚类法计算量大系统聚类法计算量大n快速聚类方法快

35、速聚类方法-K均值法均值法n由麦奎因由麦奎因(MacQueen,1967)提出的提出的n基本思想：基本思想：将每一个样品分配给最近中心将每一个样品分配给最近中心(均值均值)的类中：的类中：1将所有的样品分成将所有的样品分成K个初始类；个初始类；2通过通过距离距离度量将某个样品划入离中心（度量将某个样品划入离中心（中心怎么定？中心怎么定？）最）最近的类中；近的类中；3.对获得样品与失去样品的类，重新计算中心坐标；对获得样品与失去样品的类，重新计算中心坐标；4重复步骤重复步骤2、3直到所有的样品都不能再分配时为止。直到所有的样品都不能再分配时为止。0123456789100123456789100

36、12345678910012345678910K=2任意选择任意选择 K个对个对象作为初始聚类象作为初始聚类中心中心将每个将每个对象赋对象赋给最类给最类似的中似的中心心更新聚更新聚类的平类的平均值均值重新分配重新分配更新聚更新聚类的平类的平均值均值K均值聚类分析均值聚类分析n例：对例：对A、B、C、D四个样品分别测量两个变量，得到如下四个样品分别测量两个变量，得到如下结果，试将这些样品聚成结果，试将这些样品聚成两两类。类。K均值聚类分析均值聚类分析K均值聚类分析均值聚类分析n第一步：按要求取第一步：按要求取K=2，先将这些样品随意分成两类，比如，先将这些样品随意分成两类，比如（A、B）和（）和

37、（C、D），然后计算这两个聚类的中心坐标：），然后计算这两个聚类的中心坐标：n第二步：计算某个样品到各类中心的欧氏平方距离，然后将第二步：计算某个样品到各类中心的欧氏平方距离，然后将该样品分配给最近的一类。对于样品有变动的类，重新计算该样品分配给最近的一类。对于样品有变动的类，重新计算它们的中心坐标，为下一步聚类做准备。它们的中心坐标，为下一步聚类做准备。n先计算先计算A到两个类的平方距离：到两个类的平方距离：由于由于A到（到（A、B）的距离小于到（）的距离小于到（C、D）的距离，因此）的距离，因此A不不用重新分配；用重新分配；n计算计算B到两类的平方距离：到两类的平方距离：n对对C、D同样（

38、略）同样（略）K均值聚类分析均值聚类分析n由于由于B到（到（A、B）的距离大于到（）的距离大于到（C、D）的距离，因此）的距离，因此B要分要分配给（配给（C、D）类，得到新的聚类是（）类，得到新的聚类是（A）和（）和（B、C、D）n更新中心坐标：更新中心坐标：K均值聚类分析均值聚类分析n第三步：再次检查每个样品，以决定是否需要重新分类。计第三步：再次检查每个样品，以决定是否需要重新分类。计算各样品到各中心的距离平方：算各样品到各中心的距离平方：n发现：每个样品都已经分配给距离中心最近的类，聚类过发现：每个样品都已经分配给距离中心最近的类，聚类过程到此结束程到此结束n最终得到最终得到K=2的聚类

39、结果是的聚类结果是A独自成一类，独自成一类，B、C、D聚成聚成一类一类K均值聚类分析均值聚类分析K均值聚类分析均值聚类分析n系统聚类与系统聚类与K均值聚类都是距离度量类聚类方法均值聚类都是距离度量类聚类方法n系统聚类对不同的类数产生一系列的聚类结果系统聚类对不同的类数产生一系列的聚类结果nK均值法只能产生指定类数的聚类结果均值法只能产生指定类数的聚类结果n具体类数的确定？具体类数的确定？实践经验的积累（机理研究）实践经验的积累（机理研究）借助系统聚类法以一部分样品为对象进行聚类，其结果作为借助系统聚类法以一部分样品为对象进行聚类，其结果作为K均值法确定类数的参考均值法确定类数的参考n优优点点:

40、相相对对有效性有效性:O(tkn),其中其中 n 是是对对象数目象数目,k 是簇数目是簇数目,t 是迭代次数是迭代次数;通常：通常：k,t n.比比较较:PAM:O(k(n-k)2),CLARA:O(ks2+k(n-k)PAM(Partitioning Around Medoid,围绕代表点的划分围绕代表点的划分)CLARA(Clustering LARge Applications)n当当结结果簇是密集的，而簇与簇之果簇是密集的，而簇与簇之间间区区别别明明显时显时，它的效果，它的效果较较好好K均值聚类分析均值聚类分析n弱点弱点只有在簇的平均值只有在簇的平均值(mean)被定义的情况下才能使用

41、被定义的情况下才能使用.可可能不适用于某些应用能不适用于某些应用涉及有分类属性的数据涉及有分类属性的数据需要预先指定簇的数目需要预先指定簇的数目k 不能处理噪音数据和孤立点不能处理噪音数据和孤立点(outliers)n常常常常终终止于止于局部最局部最优优（初初值值依依赖赖）.尝试尝试不同的初不同的初值值全局最全局最优优 可以使用可以使用诸诸如如模模拟拟退火退火(simulated annealing)和和遗遗传传算法算法(genetic algorithms)等技等技术术得到得到K均值聚类分析均值聚类分析nK均值方法的变种均值方法的变种,它们在以下方面有所不同它们在以下方面有所不同初始初始k个

42、平均值的选择个平均值的选择距离的度量距离的度量计算聚类平均值的策略计算聚类平均值的策略 n处理分类属性处理分类属性:k-模模(k-modes)方法方法(Huang98)用模用模(modes众数众数)替代聚类的平均值替代聚类的平均值使用新的距离度量方法来处理分类对象使用新的距离度量方法来处理分类对象 用基于频率的方法用基于频率的方法nk-原型原型(k-prototype)方法方法:k-平均和平均和k-模的结合模的结合,处理具有数值处理具有数值和分类属性的数据和分类属性的数据K均值聚类分析均值聚类分析 R codes一一 例一例一二二 例二例二 例例 一一n设有设有20个土壤样品分别对个土壤样品分

43、别对5个变量的观测数据如表所示，试个变量的观测数据如表所示，试利用系统聚类法对其进行样品聚类分析。利用系统聚类法对其进行样品聚类分析。表表 土壤样本的观测数据土壤样本的观测数据例例 一一R code#This program performs cluster analysis on the given data.#Enter the data and assign variable names.data-read.table(file=datasets/turang.txt,header=T,col.names=c(bh,x1,x2,x3,x4,x5)#Create a matrix of v

44、ariables to be used in the cluster analysis#and a vector of id numbers id-data,1data.x-data,2:6#Standardize the datadata.mean-apply(data.x,2,mean)data.std-sqrt(apply(data.x,2,var)data.sx-sweep(data.x,2,data.mean,FUN=-)data.sx-sweep(data.sx,2,data.std,FUN=/)R codepar(mfrow=c(3,1)#Use complete linkage

45、(最长距离法最长距离法),this is also the default methodhc-hclust(dist(data.sx),method=complete)plclust(hc,label=id)title(Complete Linkage Cluster Analysis)#Use average linkage(类平均值法类平均值法)hc-hclust(dist(data.sx),method=average)plclust(hc,label=id)title(Average Linkage Cluster Analysis)#Use single linkage(最短距离法最

46、短距离法)hc-hclust(dist(data.sx),method=single)plclust(hc,label=id)title(Single Linkage Cluster Analysis)R code#Compute K-means cluster analysis starting with the results from#an average linkage cluster analysis.The centroids from seven#aveargae linkage clusters are stored as rows in the matrix initialh

47、c-hclust(dist(data.sx),method=average)initial-tapply(as.matrix(data.sx),list(rep(cutree(hc,3),ncol(data.sx),col(data.sx),mean)km-kmeans(data.sx,initial)cbind(as.character(data$bh),km$cluster)#Compute K-means cluster analysis starting with random intializationskm-kmeans(x=data.sx,centers=3)cbind(as.c

48、haracter(data$bh),km$cluster)n主要运行结果解释主要运行结果解释n1.在结果输出窗口中可以看到谱系图（在结果输出窗口中可以看到谱系图（Dendrogram）n若将若将20个样品分为两类：个样品分为两类：样品样品2、6、19、7、18和样品和样品1为一类为一类其余的为另一类；其余的为另一类；n若将样品分为三类：若将样品分为三类：样品样品8、9、4从第二类中分离出来，自成一类；从第二类中分离出来，自成一类；依此类推依此类推例例 一一图图 系统聚类法谱系图系统聚类法谱系图例例 一一例例 二二n我国各地区我国各地区2003年三个产业产值年三个产业产值如表所示，试根如表所示，

49、试根据三个产业产值据三个产业产值利用利用K均值法对均值法对我国我国31个省、自个省、自治区和直辖市进治区和直辖市进行聚类分析。行聚类分析。R code#This program performs cluster analysis on the given data.#Enter the data and assign variable names.par(mfrow=c(3,1)data-read.table(file=datasets/chanzhi.txt,header=T,col.names=c(Province,x1,x2,x3)#Create a matrix of variable

50、s to be used in the cluster analysis#and a vector of id numbers id-data,1data.x-data,2:4#Standardize the datadata.mean-apply(data.x,2,mean)data.std-sqrt(apply(data.x,2,var)data.sx-sweep(data.x,2,data.mean,FUN=-)data.sx-sweep(data.sx,2,data.std,FUN=/)R code#Use complete linkage,this is also the defau