聚类分析-PPT课件.ppt

1、第五章第五章 聚类分析聚类分析第一节第一节 引言引言 第二节第二节 相似性的量度相似性的量度 第三节第三节 系统聚类分析法系统聚类分析法 第四节第四节 K均值聚类分析均值聚类分析 第五节第五节 K中心点聚类中心点聚类第六节第六节 R codes第一节第一节 引言引言n “物以类聚，人以群分物以类聚，人以群分”n无监督分类无监督分类聚类分析聚类分析n分析如何对样品（或变量）进行量化分类的分析如何对样品（或变量）进行量化分类的问题问题Q型聚类型聚类对样品进行分类对样品进行分类R型聚类型聚类对变量进行分类对变量进行分类3相似性和相异性相似性和相异性nSimilarity数值测量两个数据对象类似程度数

2、值测量两个数据对象类似程度目标越相似时值越大目标越相似时值越大通常介于通常介于 0,1nDissimilarity (e.g., 距离距离distance)数值测量两个数据对象差异程度数值测量两个数据对象差异程度Lower when objects are more alikeMinimum dissimilarity is often 0Upper limit variesn邻近度邻近度Proximity refers to a similarity or dissimilarity4数据矩阵和相异度矩阵数据矩阵和相异度矩阵nData matrixn data points with p d

3、imensionsnDissimilarity matrixn data points, but registers only the distance A triangular matrix npx.nfx.n1x.ipx.ifx.i1x.1px.1fx.11x 0.)2 ,()1 ,(:)2 , 3().ndnd0dd(3,10d(2,1)05例例: 数据矩阵和相异度矩阵数据矩阵和相异度矩阵Dissimilarity Matrix (with Euclidean Distance)Data Matrix第二节第二节 相似性的量度相似性的量度 一一 样品相似性的度量样品相似性的度量 二二 变

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

5、为称为配合的配合的，否则否则称为称为不配合的不配合的记配合的变量数为记配合的变量数为m1，不配合的变量数为，不配合的变量数为m2，则，则样本样本之间之间的距离可定义为的距离可定义为本例中本例中X1 与与X2 之间的距离为之间的距离为2/321212mdmm8二进制属性的邻近度量二进制属性的邻近度量n二进制数据的列联表二进制数据的列联表contingency table n对称二元变量的距离侧度对称二元变量的距离侧度: n不对称二元变量的距离侧度不对称二元变量的距离侧度: nJaccard系数系数(不对称二元变量不对称二元变量的相似性侧度的相似性侧度): nNote: Jaccard coeff

6、icient is the same as “coherence”:Object iObject j9二进制属性的相异度量二进制属性的相异度量nExample性别是对称属性性别是对称属性The remaining attributes are asymmetric binary令令Y and P 值为值为1, 且且N值为值为0Name Gender Fever Cough Test-1 Test-2 Test-3 Test-4JackMYNPNNNMaryFYNPNPNJimMYPNNNN75.021121),(67.011111),(33.010210),( maryjimdjimjackd

7、maryjackd10有序变量有序变量Ordinal Variablesn一个序变量可以离散的或连续的一个序变量可以离散的或连续的nOrder is important, e.g., ranknCan be treated like interval-scaled 用他们的序代替用他们的序代替xif映射每一个变量的范围于映射每一个变量的范围于0,1，用如下，用如下值值代替第代替第f-th变量变量的的i-th对象对象11fififMrz,.,1fifMr11混合型属性混合型属性 nA database may contain all attribute typesNominal, symmetr

8、ic 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 zif as interval-scaled)(1)()(1),(fijpffijfijpfdjid11fifMrzif12规范数值数据规范数值数

9、据nZ-score: X: 需标准化的原始数值需标准化的原始数值, : 总体均值总体均值, : 标准差标准差在标准偏差单位下，原始分数和总体均值之间的距离在标准偏差单位下，原始分数和总体均值之间的距离“-”, “+”n另一种方法另一种方法: Calculate the mean absolute deviation其中其中standardized measure (z-score):n使用平均绝对偏差比使用标准差更稳健使用平均绝对偏差比使用标准差更稳健.).211nffffxx(xn m|)|.|(|121fnffffffmxmxmxnsffififsmx zx z一、样品相似性的度量一、样品

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

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

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

13、高度偏倚的数据；据；但它没有考虑指标之间的相关性；但它没有考虑指标之间的相关性；一、样品相似性的度量一、样品相似性的度量n不同的距离公式的侧重点和实际意义都有所不同不同的距离公式的侧重点和实际意义都有所不同n同一批数据采用不同的距离公式，可能会得到不同的分类结果同一批数据采用不同的距离公式，可能会得到不同的分类结果n距离公式选择基本原则：距离公式选择基本原则：要考虑所选择的距离公式在实际应用中有明确的意义要考虑所选择的距离公式在实际应用中有明确的意义欧氏距离就有非常明确的空间距离概念欧氏距离就有非常明确的空间距离概念马氏距离有消除量纲影响的作用马氏距离有消除量纲影响的作用要综合考虑对样本观测数

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

15、兴趣向感兴趣n变量间的相似性变量间的相似性-方向趋同性或方向趋同性或“相关性相关性” “夹角余弦法夹角余弦法”“相关系数相关系数”20余弦相似性余弦相似性 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-array

16、s, nApplications: information retrieval, biologic taxonomy, 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 dpiipiipiiiyxyxyx12121),cos(21 Exampl

17、e: Cosine Similarityncos(d1, d2) = (d1 d2) /|d1| |d2| , where indicates vector dot product, |d|: the length of vector 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

18、*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相关系数相关系数变量变量Xi与与Xj的相关系数定义为的相关系数定义为 显然有，显然有， rij 1。二、变量相似性的度量二、变量相似性的度量n它们的绝对值都小于它们的绝对值都小于1，统记为，统记为cij当当 cij = 1时，说明变量时，说明变量Xi与与Xj完全相似；完全相似；当当 cij 近似于近似于1时，说明

19、变量时，说明变量Xi与与Xj非常密切；非常密切；当当 cij = 0时，说明变量时，说明变量Xi与与Xj完全不一样；完全不一样；当当 cij 近似于近似于0时，说明变量时，说明变量Xi与与Xj差别很大。差别很大。n变换为距离度量：变换为距离度量： dij = 1 cij 或或 dij2 = 1 cij2 二、变量相似性的度量二、变量相似性的度量距离度量与相似性度量距离度量与相似性度量n由距离来构造相似系数总是可能的：由距离来构造相似系数总是可能的：n由相似系数构造距离并不总是可行的由相似系数构造距离并不总是可行的nGower证明，当相似系数矩阵证明，当相似系数矩阵(cij)为非负定时：为非负定

20、时： 则则dij满足距离定义的四个条件满足距离定义的四个条件11ijijcd2 1ijijdc第三节第三节 系统聚类分析法系统聚类分析法 一一 系统聚类的基本思想系统聚类的基本思想 二二 类间距离与系统聚类法类间距离与系统聚类法 三三 类间距离的统一性类间距离的统一性 一、系统聚类的基本思想一、系统聚类的基本思想n距离相近的样品（或变量）先聚成类，距离相远的距离相近的样品（或变量）先聚成类，距离相远的后聚成类，过程一直进行下去，每个样品（或变量）后聚成类，过程一直进行下去，每个样品（或变量）总能聚到合适的类中总能聚到合适的类中n系统聚类过程：（假设总共有系统聚类过程：（假设总共有n个样品（或变

21、量）个样品（或变量）1. 将每个样品（或变量）独自聚成一类，共有将每个样品（或变量）独自聚成一类，共有n类；类；2. 根据所确定的样品（或变量）的根据所确定的样品（或变量）的“距离距离”公式，把距公式，把距离较近的两个样品（或变量）聚合为一类，其它的样品离较近的两个样品（或变量）聚合为一类，其它的样品（或变量）仍各自聚为一类，共聚成（或变量）仍各自聚为一类，共聚成n 1类；类；3. 将将“距离距离”最近的两个类进一步聚成一类，共聚成最近的两个类进一步聚成一类，共聚成n 2类；类；4. 循环之循环之5. 将所有的样品（或变量）全聚成一类将所有的样品（或变量）全聚成一类n谱系图谱系图描绘聚类过程描

22、绘聚类过程二、类间距离与系统聚类法二、类间距离与系统聚类法n类间距离类间距离-类与类之间的距离类与类之间的距离n定义不同，方法不同，结果不同定义不同，方法不同，结果不同最短距离法最短距离法(Single linkage)最长距离法最长距离法(Complete method)中间距离法中间距离法(Median method)重心法重心法(Centriod method)类平均法类平均法(Avarage linkage)可变类平均法可变类平均法(Flexible-beta method)可变法可变法(McQuitty, MCQ)离差平方和法离差平方和法(Ward)ndij表示样品表示样品Xi与与X

23、j之间距离，用之间距离，用Dij表示类表示类Gi与与Gj之间的距离。之间的距离。1. 最短距离法最短距离法定义类间距离为两类最近样品的距离，即为定义类间距离为两类最近样品的距离，即为 合并成一个新类后，则任一类与之的距离为合并成一个新类后，则任一类与之的距离为 二、类间距离与系统聚类法二、类间距离与系统聚类法n最短距离法步骤如下：最短距离法步骤如下：（1）根据选用的距离计算样品的两两距离，得一距离阵）根据选用的距离计算样品的两两距离，得一距离阵记为记为D（0） ，开始每个样品自成一类，显然这时，开始每个样品自成一类，显然这时Dij =dij（2）找出距离最小元素，设为）找出距离最小元素，设为D

24、pq，则将，则将Gp和和Gq合并成一合并成一个新类，记为个新类，记为Gr，即，即Gr = Gp，Gq（3）计算新类与其它类的距离）计算新类与其它类的距离 （4）重复（）重复（2）、（）、（3）两步，直到所有元素。并成一类）两步，直到所有元素。并成一类为止为止如果某一步距离最小的元素不止一个，则对应这些最小元如果某一步距离最小的元素不止一个，则对应这些最小元素的类可以同时合并素的类可以同时合并二、类间距离与系统聚类法二、类间距离与系统聚类法n例：设有六个样品，每个只测量一个指标，分别是例：设有六个样品，每个只测量一个指标，分别是1，2，5，7，9，10，试用最短距离法将它们分类。，试用最短距离法

25、将它们分类。 （1）样品采用绝对值距离，计算样品间的距离阵）样品采用绝对值距离，计算样品间的距离阵D（0） 二、类间距离与系统聚类法二、类间距离与系统聚类法（2）D（0）中最小的元素是中最小的元素是D12D561，于是将，于是将G1和和G2合合并成并成G7，G5和和G6合并成合并成G8，计算新类与其它类的距离，计算新类与其它类的距离D（1） 二、类间距离与系统聚类法二、类间距离与系统聚类法（3）在）在D（1）中最小值是中最小值是D34D482，由于，由于G4与与G3合并，合并，又与又与G8合并，因此合并，因此G3、G4、G8合并成一个新类合并成一个新类G9，其与其，其与其它类的距离它类的距离D

26、（2） 二、类间距离与系统聚类法二、类间距离与系统聚类法（4）最后将）最后将G7和和G9合并成合并成G10，这时所有的六个样品聚为一，这时所有的六个样品聚为一类，其过程终止。类，其过程终止。n谱系图表示谱系图表示横坐标的刻度表示并类的距离横坐标的刻度表示并类的距离二、类间距离与系统聚类法二、类间距离与系统聚类法二、类间距离与系统聚类法二、类间距离与系统聚类法n再找再找距离最小两类距离最小两类并类，直至所有的样品全归为一类为止并类，直至所有的样品全归为一类为止n最长距离法与最短距离法只有两点不同：最长距离法与最短距离法只有两点不同：一是类与类之间的距离定义不同；一是类与类之间的距离定义不同；一是

27、计算新类与其它类的距离所用的公式不同一是计算新类与其它类的距离所用的公式不同二、类间距离与系统聚类法二、类间距离与系统聚类法3. 中间距离法（折中）中间距离法（折中）中间距离将类中间距离将类Gp与与Gq类合并为类类合并为类Gr，则任意的类，则任意的类Gk和和Gr的距的距离公式为离公式为 ( 14 0) n设设DkqDkp最短距离法，则最短距离法，则Dkr = Dkp；最长距离法，则最长距离法，则Dkr = Dkq。中间距离法：取它们的中间中间距离法：取它们的中间某某一点一点二、类间距离与系统聚类法二、类间距离与系统聚类法n特别当特别当 = 14，它表示取，它表示取中间点中间点算距离，公式为算距

28、离，公式为 二、类间距离与系统聚类法二、类间距离与系统聚类法二、类间距离与系统聚类法二、类间距离与系统聚类法4. 重心法重心法类间距离为两类重心（各类样品的均值）的距离类间距离为两类重心（各类样品的均值）的距离重心指标对类有很好的代表性，但利用各样本的信息不充分重心指标对类有很好的代表性，但利用各样本的信息不充分n n推导如下：推导如下：二、类间距离与系统聚类法二、类间距离与系统聚类法二、类间距离与系统聚类法二、类间距离与系统聚类法n 二、类间距离与系统聚类法二、类间距离与系统聚类法n例例：（：（数据同上例）有六个样品，每个只测量一个指标，分数据同上例）有六个样品，每个只测量一个指标，分别是别

29、是1，2，5，7，9，10n试用重心法将它们聚类试用重心法将它们聚类（1）样品采用欧氏距离，计算样品间的平方距离阵）样品采用欧氏距离，计算样品间的平方距离阵D2（0）二、类间距离与系统聚类法二、类间距离与系统聚类法（2）D2（0）中最小的元素是中最小的元素是D212D2561，于是将，于是将G1和和G2合并成合并成G7，G5和和G6合并成合并成G8，并计算新类与，并计算新类与其它类的距离得到距离阵其它类的距离得到距离阵D2（1） 其中，其中，二、类间距离与系统聚类法二、类间距离与系统聚类法（3）在）在D2（1）中最小值是中最小值是D2344，那么，那么G3与与G4合并一个新合并一个新类类G9，

30、其与其它类的距离，其与其它类的距离D2（2） ： 二、类间距离与系统聚类法二、类间距离与系统聚类法（4）其中最小值是）其中最小值是12.5，那么合并一个新类，其与其它，那么合并一个新类，其与其它类的距离：类的距离：二、类间距离与系统聚类法二、类间距离与系统聚类法（5）最后将）最后将G7和和G10合并成合并成G11，这时所有的六个样品聚为一类，这时所有的六个样品聚为一类，其过程终止。其过程终止。n谱系图表示：谱系图表示：二、类间距离与系统聚类法二、类间距离与系统聚类法二、类间距离与系统聚类法二、类间距离与系统聚类法n与最短距离法比较一下：与最短距离法比较一下：二、类间距离与系统聚类法二、类间距离

31、与系统聚类法5. 类平均法类平均法类间距离平方取为这两类元素两两之间距离平方的平均数类间距离平方取为这两类元素两两之间距离平方的平均数6. 可变类平均法可变类平均法类平均法中没有反映出类平均法中没有反映出Gp和和Gq之间的距离之间的距离Dpq的影的影响响将将Gp和和Gq合并为新类合并为新类Gr，类，类Gk与新并类与新并类Gr的距离公的距离公式推广为：式推广为： 其中其中 是可变的且是可变的且 1二、类间距离与系统聚类法二、类间距离与系统聚类法二、类间距离与系统聚类法二、类间距离与系统聚类法8. 离差平方和法（离差平方和法（Ward方法）方法）n基本思想来自于方差分析基本思想来自于方差分析如果分

32、类正确，同类样品的离差平方和应当较小，类与类的离如果分类正确，同类样品的离差平方和应当较小，类与类的离差平方和较大。差平方和较大。n具体步骤：具体步骤：先将先将n个样品各自成一类，然后每次缩小一类，每缩小一类，个样品各自成一类，然后每次缩小一类，每缩小一类，离差平方和就要增大，选择使其增加最小的两类合并，直到所离差平方和就要增大，选择使其增加最小的两类合并，直到所有的样品归为一类为止。有的样品归为一类为止。二、类间距离与系统聚类法二、类间距离与系统聚类法n设将设将n个样品分成个样品分成k类类G1，G2，Gk，用，用Xit表示表示Gt中的第中的第i个样品，个样品，nt表示表示Gt中样品的个数，中

33、样品的个数， 是是Gt的重心，则的重心，则Gt的样品的样品离差平方和为离差平方和为 tX二、类间距离与系统聚类法二、类间距离与系统聚类法n 二、类间距离与系统聚类法二、类间距离与系统聚类法三、类间距离的统一三、类间距离的统一n上述八种系统聚类法的步骤完全一样，只是距离的递推公式不同。兰斯上述八种系统聚类法的步骤完全一样，只是距离的递推公式不同。兰斯（Lance）和威廉姆斯（）和威廉姆斯（Williams）于）于1967年给出了一个统一的公式。年给出了一个统一的公式。 ap、aq、 、 是参数是参数不同的系统聚类法，它们取不同的值不同的系统聚类法，它们取不同的值n注意注意：不同的聚类方法结果不一

34、定完全相同，一般只是大致相似不同的聚类方法结果不一定完全相同，一般只是大致相似可将聚类结果与实际问题对照，看哪一个结果更符合经验可将聚类结果与实际问题对照，看哪一个结果更符合经验表表 系统聚类法参数表系统聚类法参数表三、类间距离的统一三、类间距离的统一n单调性：单调性：令令Di是系统聚类法中第是系统聚类法中第i次并类时的距离，次并类时的距离，如果一种系统聚类法能满足如果一种系统聚类法能满足D1D2D3 n单调性符合系统聚类法的思想，先合并较相似的类，单调性符合系统聚类法的思想，先合并较相似的类，后合并较疏远的类后合并较疏远的类n最短距离法、最长距离法、可变法、类平均法、可最短距离法、最长距离法

35、、可变法、类平均法、可变类平均法和离差平方和法都具有单调性变类平均法和离差平方和法都具有单调性n中间距离法和重心法中间距离法和重心法不具有不具有单调性单调性四、单调性四、单调性五、类的个数五、类的个数n如果能够分成若干个很分开的类，则类的个数就比如果能够分成若干个很分开的类，则类的个数就比较容易确定；较容易确定；n如果无论怎样分都很难分成明显分开的若干类，则如果无论怎样分都很难分成明显分开的若干类，则类个数的确定就比较困难类个数的确定就比较困难n常用方法：常用方法：给定一个阈值给定一个阈值T通过通过观察谱系图观察谱系图，给出一个合适的阈值，给出一个合适的阈值T，要求类与类之间的距，要求类与类之

36、间的距离要大于离要大于T有较强的主观性有较强的主观性观测样品的散点图观测样品的散点图如果样品只有两个或三个变量，则可通过观测数据的散点图来确如果样品只有两个或三个变量，则可通过观测数据的散点图来确定类的个数定类的个数如果变量个数超过三个，可先降维如果变量个数超过三个，可先降维(费舍尔判别法等）费舍尔判别法等）使用统计量（模型选择）使用统计量（模型选择）n观测散点图可以从直觉上来判断所采用的聚类方法是否合理观测散点图可以从直觉上来判断所采用的聚类方法是否合理n可直接从散点图中进行主观的分类可直接从散点图中进行主观的分类五、类的个数五、类的个数-寻找寻找“自然的自然的”类类五、类的个数五、类的个数

37、画图法画图法n依次尝试不同的依次尝试不同的k值值(x)，计算某个度量（统计量、距离等），计算某个度量（统计量、距离等）(y)n画图，显示画图，显示y随随x的变化趋势的变化趋势n找拐点，作为确定找拐点，作为确定k的根据的根据n当曲线拐点很平缓时，可选择的当曲线拐点很平缓时，可选择的k很多，这时需要用其它很多，这时需要用其它的办法来确定的办法来确定第四节第四节 K均值聚类分析均值聚类分析 n系统聚类法计算量大系统聚类法计算量大n快速聚类方法快速聚类方法-K均值法均值法n由麦奎因由麦奎因(MacQueen,1967)提出的提出的n基本思想：基本思想：将每一个样品分配给最近中心将每一个样品分配给最近中

38、心(均值均值)的类中：的类中：1将所有的样品分成将所有的样品分成K个初始类；个初始类；2通过通过距离距离度量将某个样品划入离中心（度量将某个样品划入离中心（中心怎么定？中心怎么定？）最）最近的类中；近的类中；3. 对获得样品与失去样品的类，重新计算中心坐标；对获得样品与失去样品的类，重新计算中心坐标；4重复步骤重复步骤2、3直到所有的样品都不能再分配时为止。直到所有的样品都不能再分配时为止。0123456789100123456789100123456789100123456789100123456789100123456789100123456789100123456789100123456

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

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

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

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

43、性相对有效性: 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)被

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

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

46、设有20个土壤样品分别对个土壤样品分别对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,

47、 x3, x4, x5) # Create a matrix of variables to be used in the cluster analysis# and a vector of id numbersid-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 cod

48、epar(mfrow=c(3,1)# Use complete linkage (最长距离法最长距离法), 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 Lin

49、kage Cluster Analysis) # Use single linkage (最短距离法最短距离法)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 li

50、nkage clusters are stored as rows in the matrix initialhc - 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