多元统计分析聚类分析

1、第五章 聚类分析第一节 引言 第二节 相同性量度 第三节 系统聚类分析法 第四节 K均值聚类分析 第五节 K中心点聚类第六节 R codes多元统计分析聚类分析第1页第一节 引言 “物以类聚，人以群分”无监督分类聚类分析分析怎样对样品（或变量）进行量化分类问题Q型聚类对样品进行分类R型聚类对变量进行分类多元统计分析聚类分析第2页相同性和相异性Similarity数值测量两个数据对象类似程度目标越相同时值越大通常介于 0,1Dissimilarity (e.g., 距离distance)数值测量两个数据对象差异程度Lower when objects are more alikeMinimum

2、dissimilarity is often 0Upper limit varies邻近度Proximity refers to a similarity or dissimilarity多元统计分析聚类分析第3页数据矩阵和相异度矩阵Data matrixn data points with p dimensionsDissimilarity matrixn data points, but registers only the distance A triangular matrix多元统计分析聚类分析第4页例: 数据矩阵和相异度矩阵Dissimilarity Matrix (with Eu

3、clidean Distance)Data Matrix多元统计分析聚类分析第5页第二节 相同性量度 一 样品相同性度量 二 变量相同性度量 多元统计分析聚类分析第6页含名义变量样本相同性度量例： 学员资料包含六个属性：性别（男或女）；外语语种（英、日或俄）；专业（统计、会计或金融）；职业（教师或非教师）；居住处（校内或校外）；学历（本科或本科以下）现有两名学员： X1=（男，英，统计，非教师，校外，本科） X2=（女，英，金融，教师，校外，本科以下）对应变量取值相同称为配合，不然称为不配合记配合变量数为m1，不配合变量数为m2，则样本之间距离可定义为本例中X1 与X2 之间距离为2/3多元统

4、计分析聚类分析第7页二进制属性邻近度量二进制数据列联表contingency table 对称二元变量距离侧度: 不对称二元变量距离侧度: Jaccard系数(不对称二元变量相同性侧度): Note: Jaccard coefficient is the same as “coherence”:Object iObject j多元统计分析聚类分析第8页二进制属性相异度量Example性别是对称属性The remaining attributes are asymmetric binary令Y and P 值为1, 且N值为0多元统计分析聚类分析第9页有序变量Ordinal Variables一

5、个序变量能够离散或连续Order is important, e.g., rankCan be treated like interval-scaled 用他们序代替xif映射每一个变量范围于0,1，用以下值代替第f-th变量i-th对象多元统计分析聚类分析第10页混合型属性 A database may contain all attribute typesNominal, symmetric binary, asymmetric binary, numeric, ordinal能够用加权法计算合并影响f is binary or nominal:dij(f) = 0 if xif = xj

6、f , or dij(f) = 1 otherwisef is numeric: use the normalized distancef is ordinal Compute ranks rif and Treat zif as interval-scaled多元统计分析聚类分析第11页规范数值数据Z-score: X: 需标准化原始数值, : 总体均值, : 标准差在标准偏差单位下，原始分数和总体均值之间距离“-”, “+”另一个方法: Calculate the mean absolute deviation其中standardized measure (z-score):使用平均绝对偏

7、差比使用标准差更稳健多元统计分析聚类分析第12页一、样品相同性度量Q型聚类分析，惯用距离来测度样品之间相同程度每个样品有p个指标（变量）从不一样方面描述其性质，形成一个p维向量。假如把n个样品看成p维空间中n个点，则两个样品间相同程度就可用p维空间中两点距离公式来度量。令dij 表示样品Xi与Xj距离，普通应满足： (i) dij0，对一切i,j；(ii) dij=0，当且仅当第i个样品与第j个样品各变量值相同；(iii) dij=dji，对一切i,j；(iv) dijdik+dkj，对一切i,j,k。多元统计分析聚类分析第13页1明考夫斯基距离(明氏距离) 一、样品相同性度量多元统计分析聚类

8、分析第14页Example: Minkowski DistanceDissimilarity MatricesManhattan (L1)Euclidean (L2)Supremum 多元统计分析聚类分析第15页2马氏距离 设Xi与Xj是来自均值向量为 ，协方差为 （0）总体G中p维样品，则两个样品间马氏距离为 马氏距离又称为广义欧氏距离马氏距离考虑了观察变量之间相关性若各变量之间相互独立，马氏距离退化加权欧氏距离马氏距离还考虑了观察变量之间变异性，不再受各指标量纲影响一、样品相同性度量多元统计分析聚类分析第16页3兰氏距离 它仅适合用于一切Xij0情况能够克服各个指标之间量纲影响；对大奇异值

9、不敏感，尤其适合于高度偏倚数据；但它没有考虑指标之间相关性；一、样品相同性度量多元统计分析聚类分析第17页不一样距离公式侧重点和实际意义都有所不一样同一批数据采取不一样距离公式，可能会得到不一样分类结果距离公式选择基本标准：要考虑所选择距离公式在实际应用中有明确意义欧氏距离就有非常明确空间距离概念马氏距离有消除量纲影响作用要综合考虑对样本观察数据预处理和将要采取聚类分析方法如在进行聚类分析之前已经对变量作了标准化处理，则通常可采取欧氏距离要考虑研究对象特点和计算量大小归根到底：Application Driven: 依据研究对象特点不一样做出详细分折Try一、样品相同性度量多元统计分析聚类分析

10、第18页二、变量相同性度量相对于数据大小，更多地对变量改变趋势或方向感兴趣变量间相同性-方向趋同性或“相关性” “夹角余弦法”“相关系数”多元统计分析聚类分析第19页余弦相同性 Cosine SimilarityA document can be represented by thousands of attributes, each recording the frequency of a particular word (such as keywords) or phrase in the document.Other vector objects: gene features in mi

11、cro-arrays, Applications: information retrieval, biologic taxonomy, gene feature mapping, .Cosine 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多元统计分析聚类分析第20页 Example: Cosin

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

13、+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.94多元统计分析聚类分析第21页2相关系数变量Xi与Xj相关系数定义为 显然有，rij 1。二、变量相同性度量多元统计分析聚类分析第22页它们绝对值都小于1，统记为cij当cij= 1时，说明变量Xi与Xj完全相同；当cij近似于1时，说明变量Xi与Xj非常亲密；当cij = 0时，说明变量Xi与Xj完全不一样；当cij近似于0时，说明变

14、量Xi与Xj差异很大。变换为距离度量： dij = 1 cij或 dij2 = 1 cij2 二、变量相同性度量多元统计分析聚类分析第23页距离度量与相同性度量由距离来结构相同系数总是可能：由相同系数结构距离并不总是可行Gower证实，当相同系数矩阵(cij)为非负定时： 则dij满足距离定义四个条件多元统计分析聚类分析第24页第三节 系统聚类分析法 一 系统聚类基本思想 二 类间距离与系统聚类法 三 类间距离统一性 多元统计分析聚类分析第25页一、系统聚类基本思想距离相近样品（或变量）先聚成类，距离相远后聚成类，过程一直进行下去，每个样品（或变量）总能聚到适当类中系统聚类过程：（假设总共有n

15、个样品（或变量）1. 将每个样品（或变量）独自聚成一类，共有n类；2. 依据所确定样品（或变量）“距离”公式，把距离较近两个样品（或变量）聚合为一类，其它样品（或变量）仍各自聚为一类，共聚成n 1类；3. 将“距离”最近两个类深入聚成一类，共聚成n 2类；4. 循环之5. 将全部样品（或变量）全聚成一类谱系图描绘聚类过程多元统计分析聚类分析第26页二、类间距离与系统聚类法类间距离-类与类之间距离定义不一样，方法不一样，结果不一样最短距离法(Single linkage)最长距离法(Complete method)中间距离法(Median method)重心法(Centriod method)类

16、平均法(Avarage linkage)可变类平均法(Flexible-beta method)可变法(McQuitty, MCQ)离差平方和法(Ward)多元统计分析聚类分析第27页dij表示样品Xi与Xj之间距离，用Dij表示类Gi与Gj之间距离。1. 最短距离法定义类间距离为两类最近样品距离，即为 合并成一个新类后，则任一类与之距离为 二、类间距离与系统聚类法多元统计分析聚类分析第28页最短距离法步骤以下：（1）依据选取距离计算样品两两距离，得一距离阵记为D（0） ，开始每个样品自成一类，显然这时Dij =dij（2）找出距离最小元素，设为Dpq，则将Gp和Gq合并成一个新类，记为Gr，

17、即Gr = Gp，Gq（3）计算新类与其它类距离 （4）重复（2）、（3）两步，直到全部元素。并成一类为止假如某一步距离最小元素不止一个，则对应这些最小元素类能够同时合并二、类间距离与系统聚类法多元统计分析聚类分析第29页例：设有六个样品，每个只测量一个指标，分别是1，2，5，7，9，10，试用最短距离法将它们分类。 （1）样品采取绝对值距离，计算样品间距离阵D（0） 二、类间距离与系统聚类法多元统计分析聚类分析第30页（2）D（0）中最小元素是D12D561，于是将G1和G2合并成G7，G5和G6合并成G8，计算新类与其它类距离D（1） 二、类间距离与系统聚类法多元统计分析聚类分析第31页（

18、3）在D（1）中最小值是D34D482，因为G4与G3合并，又与G8合并，所以G3、G4、G8合并成一个新类G9，其与其它类距离D（2） 二、类间距离与系统聚类法多元统计分析聚类分析第32页（4）最终将G7和G9合并成G10，这时全部六个样品聚为一类，其过程终止。谱系图表示横坐标刻度表示并类距离二、类间距离与系统聚类法多元统计分析聚类分析第33页二、类间距离与系统聚类法多元统计分析聚类分析第34页再找距离最小两类并类，直至全部样品全归为一类为止最长距离法与最短距离法只有两点不一样：一是类与类之间距离定义不一样；一是计算新类与其它类距离所用公式不一样二、类间距离与系统聚类法多元统计分析聚类分析第

19、35页3. 中间距离法（折中）中间距离将类Gp与Gq类合并为类Gr，则任意类Gk和Gr距离公式为 (14 0) 设DkqDkp最短距离法，则Dkr = Dkp；最长距离法，则Dkr = Dkq。中间距离法：取它们中间某一点二、类间距离与系统聚类法多元统计分析聚类分析第36页尤其当 = 14，它表示取中间点算距离，公式为 二、类间距离与系统聚类法多元统计分析聚类分析第37页二、类间距离与系统聚类法4. 重心法类间距离为两类重心（各类样品均值）距离重心指标对类有很好代表性，但利用各样本信息不充分多元统计分析聚类分析第38页 推导以下：二、类间距离与系统聚类法多元统计分析聚类分析第39页二、类间距离

20、与系统聚类法多元统计分析聚类分析第40页 二、类间距离与系统聚类法多元统计分析聚类分析第41页例：（数据同上例）有六个样品，每个只测量一个指标，分别是1，2，5，7，9，10试用重心法将它们聚类（1）样品采取欧氏距离，计算样品间平方距离阵D2（0）二、类间距离与系统聚类法多元统计分析聚类分析第42页（2）D2（0）中最小元素是D212D2561，于是将G1和G2合并成G7，G5和G6合并成G8，并计算新类与其它类距离得到距离阵D2（1） 其中，二、类间距离与系统聚类法多元统计分析聚类分析第43页（3）在D2（1）中最小值是D2344，那么G3与G4合并一个新类G9，其与其它类距离D2（2） ：

21、 二、类间距离与系统聚类法多元统计分析聚类分析第44页（4）其中最小值是12.5，那么合并一个新类，其与其它类距离：二、类间距离与系统聚类法多元统计分析聚类分析第45页（5）最终将G7和G10合并成G11，这时全部六个样品聚为一类，其过程终止。谱系图表示：二、类间距离与系统聚类法多元统计分析聚类分析第46页二、类间距离与系统聚类法与最短距离法比较一下：多元统计分析聚类分析第47页二、类间距离与系统聚类法5. 类平均法类间距离平方取为这两类元素两两之间距离平方平均数多元统计分析聚类分析第48页6. 可变类平均法类平均法中没有反应出Gp和Gq之间距离Dpq影响将Gp和Gq合并为新类Gr，类Gk与新

22、并类Gr距离公式推广为： 其中是可变且 1二、类间距离与系统聚类法多元统计分析聚类分析第49页二、类间距离与系统聚类法多元统计分析聚类分析第50页8. 离差平方和法（Ward方法）基本思想来自于方差分析假如分类正确，同类样品离差平方和应该较小，类与类离差平方和较大。详细步骤：先将n个样品各自成一类，然后每次缩小一类，每缩小一类，离差平方和就要增大，选择使其增加最小两类合并，直到全部样品归为一类为止。二、类间距离与系统聚类法多元统计分析聚类分析第51页设将n个样品分成k类G1，G2，Gk，用Xit表示Gt中第i个样品，nt表示Gt中样品个数， 是Gt重心，则Gt样品离差平方和为 二、类间距离与系

23、统聚类法多元统计分析聚类分析第52页 二、类间距离与系统聚类法多元统计分析聚类分析第53页三、类间距离统一上述八种系统聚类法步骤完全一样，只是距离递推公式不一样。兰斯（Lance）和威廉姆斯（Williams）于1967年给出了一个统一公式。 ap、aq、 、 是参数不一样系统聚类法，它们取不一样值注意：不一样聚类方法结果不一定完全相同，普通只是大致相同可将聚类结果与实际问题对照，看哪一个结果更符合经验多元统计分析聚类分析第54页表 系统聚类法参数表三、类间距离统一多元统计分析聚类分析第55页单调性：令Di是系统聚类法中第i次并类时距离，假如一个系统聚类法能满足D1D2D3 单调性符合系统聚类

24、法思想，先合并较相同类，后合并较疏远类最短距离法、最长距离法、可变法、类平均法、可变类平均法和离差平方和法都含有单调性中间距离法和重心法不含有单调性四、单调性多元统计分析聚类分析第56页五、类个数假如能够分成若干个很分开类，则类个数就比较轻易确定；假如不论怎样分都极难分成显著分开若干类，则类个数确实定就比较困难惯用方法：给定一个阈值T经过观察谱系图，给出一个适当阈值T，要求类与类之间距离要大于T有较强主观性观察样品散点图假如样品只有两个或三个变量，则可经过观察数据散点图来确定类个数假如变量个数超出三个，可先降维(费舍尔判别法等）使用统计量（模型选择）多元统计分析聚类分析第57页观察散点图能够从

25、直觉上来判断所采取聚类方法是否合理可直接从散点图中进行主观分类五、类个数-寻找“自然”类多元统计分析聚类分析第58页五、类个数画图法依次尝试不一样k值(x)，计算某个度量（统计量、距离等）(y)画图，显示y随x改变趋势找拐点，作为确定k依据当曲线拐点很平缓时，可选择k很多，这时需要用其它方法来确定多元统计分析聚类分析第59页第四节 K均值聚类分析 系统聚类法计算量大快速聚类方法-K均值法由麦奎因(MacQueen,1967)提出基本思想：将每一个样品分配给最近中心(均值)类中：1将全部样品分成K个初始类；2经过距离度量将某个样品划入离中心（中心怎么定？）最近类中；3. 对取得样品与失去样品类，

26、重新计算中心坐标；4重复步骤2、3直到全部样品都不能再分配时为止。多元统计分析聚类分析第60页012345678910012345678910012345678910012345678910K=2任意选择 K个对象作为初始聚类中心将每个对象赋给最类似中心更新聚类平均值重新分配更新聚类平均值K均值聚类分析多元统计分析聚类分析第61页例：对A、B、C、D四个样品分别测量两个变量，得到以下结果，试将这些样品聚成两类。 K均值聚类分析多元统计分析聚类分析第62页K均值聚类分析第一步：按要求取K=2，先将这些样品随意分成两类，比如（A、B）和（C、D），然后计算这两个聚类中心坐标：多元统计分析聚类分析第

27、63页第二步：计算某个样品到各类中心欧氏平方距离，然后将该样品分配给最近一类。对于样品有变动类，重新计算它们中心坐标，为下一步聚类做准备。先计算A到两个类平方距离：因为A到（A、B）距离小于到（C、D）距离，所以A不用重新分配；计算B到两类平方距离：对C、D一样（略）K均值聚类分析多元统计分析聚类分析第64页因为B到（A、B）距离大于到（C、D）距离，所以B要分配给（C、D）类，得到新聚类是（A）和（B、C、D）更新中心坐标：K均值聚类分析多元统计分析聚类分析第65页第三步：再次检验每个样品，以决定是否需要重新分类。计算各样品到各中心距离平方：发觉：每个样品都已经分配给距离中心最近类，聚类过程

28、到此结束最终得到K=2聚类结果是A独自成一类，B、C、D聚成一类K均值聚类分析多元统计分析聚类分析第66页K均值聚类分析系统聚类与K均值聚类都是距离度量类聚类方法系统聚类对不一样类数产生一系列聚类结果K均值法只能产生指定类数聚类结果详细类数确实定？实践经验积累（机理研究）借助系统聚类法以一部分样品为对象进行聚类，其结果作为K均值法确定类数参考多元统计分析聚类分析第67页优点: 相对有效性: O(tkn), 其中 n 是对象数目, k 是簇数目, t 是迭代次数; 通常：k, t n.比较: PAM: O(k(n-k)2), CLARA: O(ks2 + k(n-k)PAM (Partition

29、ing Around Medoid,围绕代表点划分)CLARA (Clustering LARge Applications)当结果簇是密集，而簇与簇之间区分显著时，它效果很好K均值聚类分析多元统计分析聚类分析第68页弱点只有在簇平均值(mean)被定义情况下才能使用.可能不适合用于一些应用包括有分类属性数据需要预先指定簇数目k 不能处理噪音数据和孤立点(outliers)经常终止于局部最优（初值依赖）. 尝试不一样初值全局最优 能够使用诸如模拟退火(simulated annealing)和遗传算法(genetic algorithms)等技术得到K均值聚类分析多元统计分析聚类分析第69页K

30、均值方法变种, 它们在以下方面有所不一样初始k个平均值选择距离度量计算聚类平均值策略 处理分类属性: k- 模(k-modes) 方法(Huang98)用模(modes众数)替换聚类平均值使用新距离度量方法来处理分类对象 用基于频率方法k-原型(k-prototype)方法: k-平均和k-模结合, 处理含有数值和分类属性数据K均值聚类分析多元统计分析聚类分析第70页 R codes一 例一二 例二 多元统计分析聚类分析第71页例 一设有20个土壤样品分别对5个变量观察数据如表所表示，试利用系统聚类法对其进行样品聚类分析。表 土壤样本观察数据多元统计分析聚类分析第72页例 一多元统计分析聚类分

31、析第73页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, s = c(bh, x1, x2, x3, x4, x5) # Create a matrix of variables to be used in the cluster analysis# and a vector of id numbers

32、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=/)多元统计分析聚类分析第74页R codepar(mfrow=c(3,1)# Use complete linkage (最长距离法), this is also the default methodhc - hclust(

33、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 (最短距离法)hc-hclust(dist(data.sx),method=single)plclust(hc,la

34、bel=id)title(Single Linkage Cluster Analysis) 多元统计分析聚类分析第75页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 initialhc - hclust(dist(data.sx),method=avera

35、ge) 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.character(data$bh),k

36、m$cluster)多元统计分析聚类分析第76页主要运行结果解释1. 在结果输出窗口中能够看到谱系图（Dendrogram）若将20个样品分为两类：样品2、6、19、7、18和样品1为一类其余为另一类；若将样品分为三类：样品8、9、4从第二类中分离出来，自成一类；依这类推例 一多元统计分析聚类分析第77页图 系统聚类法谱系图例 一多元统计分析聚类分析第78页例 二我国各地域三个产业产值如表所表示，试依据三个产业产值利用K均值法对我国31个省、自治区和直辖市进行聚类分析。 多元统计分析聚类分析第79页R code# This program performs cluster analysis o

37、n the given data.# Enter the data and assign variable names.par(mfrow=c(3,1)data - read.table(file = datasets/chanzhi.txt, header=T, s = c(Province, x1, x2, x3) # Create a matrix of variables to be used in the cluster analysis# and a vector of id numbersid-data ,1data.x-data ,2:4# Standardiz

38、e 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=/)多元统计分析聚类分析第80页R code# Use complete linkage, this is also the default methodhc - hclust(dist(data.sx),method=complete)plclust(hc,label=id)title(Comple

39、te Linkage Cluster Analysis) # Use average linkagehc - hclust(dist(data.sx),method=average)plclust(hc,label=id)title(Average Linkage Cluster Analysis) # Use single linkagehc-hclust(dist(data.sx),method=single)plclust(hc,label=id)title(Single Linkage Cluster Analysis) 多元统计分析聚类分析第81页R code# Compute K-

40、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 initialhc - hclust(dist(data.sx),method=average) initial - tapply(as.matrix(data.sx), list(rep(cutree(hc,3),ncol(data.sx),c

41、ol(data.sx), mean)km - kmeans(data.sx, initial)cbind(as.character(data$Province),km$cluster)# Compute K-means cluster analysis starting with random intializations# Note that this is the default and is controlled by nstart # (by default,this is one).km - kmeans(x = data.sx, centers = 3, nstart = 1000

42、0)cbind(as.character(data$Province),km$cluster)多元统计分析聚类分析第82页表 各观察量所属类组员表例 二 （SPSS结果）多元统计分析聚类分析第83页能够看出31个地域被分成3类第一类包含：江苏、浙江、山东和广东4个省。这一类类中心三个产业产值分别为1102.14亿元、6423.01亿元和4454.26亿元，属于三个产业都比较发达地域；第二类包含：天津、山西、内蒙古、吉林、江西、广西、海南、重庆、贵州、云南、西藏、陕西、甘肃、青海、宁夏和新疆16个地域。这一类类中心三个产业产值分别为307.61亿元、795.41亿元和673.63亿元，属于欠发达

43、地域；剩下11个地域为第三类。这一类类中心三个产业产值分别为713.28亿元、2545.20亿元和212.87亿元，属于中等发达地域。比较初始值vs自动例 二多元统计分析聚类分析第84页k-均值聚类算法对孤立点(异常点)很敏感!因为含有尤其大值对象可能显著地影响数据分布.k-中心点(k-Medoids): 不采取簇中对象平均值作为参考点, 而是选取簇中位置最中心对象, 即中心点(medoid，代表点)作为参考点. 012345678910012345678910012345678910012345678910K中心点聚类分析多元统计分析聚类分析第85页PAM (Partitioning Aro

44、und Medoids) (Kaufman and Rousseeuw, 1987)是最早提出k-中心点聚类算法基本思想：首先为每个簇随意选择一个代表对象; 剩下对象依据其与代表对象距离分配给最近一个簇然后重复地用非代表对象来替换代表对象, 以改进聚类质量聚类结果质量用一个代价函数来估算, 该函数评定了对象与其参考对象之间平均距离 K中心点聚类分析多元统计分析聚类分析第86页为了判定一个非代表对象Orandom 是否是当前一个代表对象Oj好替换, 对于每一个非代表对象p,考虑下面四种情况： 第一个情况：p当前隶属于代表对象 Oj. 假如Oj被Orandom所代替, 且p离Oi最近, ij, 那

45、么p被重新分配给Oi 第二种情况：p当前隶属于代表对象 Oj. 假如Oj 被Orandom代替, 且p离Orandom最近, 那么p被重新分配给Orandom 第三种情况：p当前隶属于Oi，ij。假如Oj被Orandom代替，而p依然离Oi最近，那么对象隶属不发生改变 第四种情况：p当前隶属于Oi，ij。假如Oj被Orandom代替，且p离Orandom最近，那么p被重新分配给Orandom K中心点聚类分析多元统计分析聚类分析第87页1. 重新分配给Oi 2. 重新分配给Orandom 3. 不发生改变 4.重新分配给Orandom 数据对象+ 簇中心 替换前 替换后 图 k-中心点聚类代价

46、函数四种情况+OrandomOiOjp+OrandomOiOjp +OrandomOiOjp+OrandomOiOjpK中心点聚类分析多元统计分析聚类分析第88页算法: k-中心点(1) 随机选择k个对象作为初始代表对象（中心点）；(2) repeat(3) 指派每个剩下对象给离它最近代表对象所代表簇；(4) 随意地选择一个非代表对象Orandom；(5) 计算用Orandom代替Oj总代价S；S=代替后点平方误差函数-原来平方误差函数(6) 假如S0，则用Orandom替换Oj，形成新k个代表对象集合；(7) until 不发生改变K中心点聚类分析多元统计分析聚类分析第89页Total Cost = 2001234567891001234567891