聚类分析 课件.ppt

《聚类分析 课件.ppt》由会员分享，可在线阅读，更多相关《聚类分析 课件.ppt（94页珍藏版）》请在三一办公上搜索。

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

2、ten 0Upper limit varies邻近度Proximity refers to a similarity or dissimilarity,4,数据矩阵和相异度矩阵,Data matrixn data points with p dimensionsDissimilarity matrixn data points,but registers only the distance A triangular matrix,5,例:数据矩阵和相异度矩阵,Dissimilarity Matrix(with Euclidean Distance),Data Matrix,第二节 相似性的量度

3、,一 样品相似性的度量,二 变量相似性的度量,含名义变量样本相似性度量,例：学员资料包含六个属性：性别（男或女）；外语语种（英、日或俄）；专业（统计、会计或金融）；职业（教师或非教师）；居住处（校内或校外）；学历（本科或本科以下）现有两名学员：X1=（男，英，统计，非教师，校外，本科）X2=（女，英，金融，教师，校外，本科以下）对应变量取值相同称为配合的，否则称为不配合的记配合的变量数为m1，不配合的变量数为m2，则样本之间的距离可定义为本例中X1 与X2 之间的距离为2/3,8,二进制属性的邻近度量,二进制数据的列联表contingency table 对称二元变量的距离侧度:不对称二元变量

4、的距离侧度:Jaccard系数(不对称二元变量的相似性侧度):,Note:Jaccard coefficient is the same as“coherence”:,Object i,Object j,9,二进制属性的相异度量,Example性别是对称属性The remaining attributes are asymmetric binary令Y and P 值为1,且N值为0,10,有序变量Ordinal Variables,一个序变量可以离散的或连续的Order is important,e.g.,rankCan be treated like interval-scaled 用他们

5、的序代替xif映射每一个变量的范围于0,1，用如下值代替第f-th变量的i-th对象,11,混合型属性,A database may contain all attribute typesNominal,symmetric binary,asymmetric binary,numeric,ordinal可以用加权法计算合并的影响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

6、and Treat zif as interval-scaled,12,规范数值数据,Z-score:X:需标准化的原始数值,:总体均值,:标准差在标准偏差单位下，原始分数和总体均值之间的距离“-”,“+”另一种方法:Calculate the mean absolute deviation其中standardized measure(z-score):使用平均绝对偏差比使用标准差更稳健,一、样品相似性的度量,Q型聚类分析，常用距离来测度样品之间的相似程度每个样品有p个指标（变量）从不同方面描述其性质，形成一个p维的向量。如果把n个样品看成p维空间中的n个点，则两个样品间相似程度就可用p维空间

7、中的两点距离公式来度量。令dij 表示样品Xi与Xj的距离，一般应满足：(i)dij0，对一切i,j；(ii)dij=0，当且仅当第i个样品与第j个样品的各变量值相同；(iii)dij=dji，对一切i,j；(iv)dijdik+dkj，对一切i,j,k。,1明考夫斯基距离(明氏距离),一、样品相似性的度量,15,Example:Minkowski Distance,Dissimilarity Matrices,Manhattan(L1),Euclidean(L2),Supremum,2马氏距离 设Xi与Xj是来自均值向量为，协方差为（0）的总体G中的p维样品，则两个样品间的马氏距离为 马氏距

8、离又称为广义欧氏距离马氏距离考虑了观测变量之间的相关性若各变量之间相互独立，马氏距离退化加权欧氏距离马氏距离还考虑了观测变量之间的变异性，不再受各指标量纲的影响,一、样品相似性的度量,3兰氏距离 它仅适用于一切Xij0的情况可以克服各个指标之间量纲的影响；对大的奇异值不敏感，特别适合于高度偏倚的数据；但它没有考虑指标之间的相关性；,一、样品相似性的度量,不同的距离公式的侧重点和实际意义都有所不同同一批数据采用不同的距离公式，可能会得到不同的分类结果距离公式选择基本原则：要考虑所选择的距离公式在实际应用中有明确的意义欧氏距离就有非常明确的空间距离概念马氏距离有消除量纲影响的作用要综合考虑对样本观

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

10、equency of a particular word(such as keywords)or phrase in the document.Other vector objects:gene features in micro-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|d

11、2|,where indicates vector dot product,|d|:the length of vector d,21,Example:Cosine Similarity,cos(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

12、+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.94,2相关系数变量Xi与Xj的相关系数定义为 显然有，rij 1。,二、变量相似性的度量,它们的绝对值都小于1，统记为cij当cij=1时，说明变量Xi与Xj完全相似；当cij近似于1时，说明变量Xi与Xj非常密切；当cij=0时，说明变量Xi与Xj完全不一样；当ci

13、j近似于0时，说明变量Xi与Xj差别很大。变换为距离度量：dij=1 cij或 dij2=1 cij2,二、变量相似性的度量,距离度量与相似性度量,由距离来构造相似系数总是可能的：由相似系数构造距离并不总是可行的Gower证明，当相似系数矩阵(cij)为非负定时：则dij满足距离定义的四个条件,第三节 系统聚类分析法,一 系统聚类的基本思想,二 类间距离与系统聚类法,三 类间距离的统一性,一、系统聚类的基本思想,距离相近的样品（或变量）先聚成类，距离相远的后聚成类，过程一直进行下去，每个样品（或变量）总能聚到合适的类中系统聚类过程：（假设总共有n个样品（或变量）1.将每个样品（或变量）独自聚成

14、一类，共有n类；2.根据所确定的样品（或变量）的“距离”公式，把距离较近的两个样品（或变量）聚合为一类，其它的样品（或变量）仍各自聚为一类，共聚成n 1类；3.将“距离”最近的两个类进一步聚成一类，共聚成n 2类；4.循环之5.将所有的样品（或变量）全聚成一类谱系图描绘聚类过程,二、类间距离与系统聚类法,类间距离-类与类之间的距离定义不同，方法不同，结果不同最短距离法(Single linkage)最长距离法(Complete method)中间距离法(Median method)重心法(Centriod method)类平均法(Avarage linkage)可变类平均法(Flexible-

15、beta method)可变法(McQuitty,MCQ)离差平方和法(Ward),dij表示样品Xi与Xj之间距离，用Dij表示类Gi与Gj之间的距离。1.最短距离法定义类间距离为两类最近样品的距离，即为 合并成一个新类后，则任一类与之的距离为,二、类间距离与系统聚类法,最短距离法步骤如下：（1）根据选用的距离计算样品的两两距离，得一距离阵记为D（0），开始每个样品自成一类，显然这时Dij=dij（2）找出距离最小元素，设为Dpq，则将Gp和Gq合并成一个新类，记为Gr，即Gr=Gp，Gq（3）计算新类与其它类的距离（4）重复（2）、（3）两步，直到所有元素。并成一类为止如果某一步距离最小的

16、元素不止一个，则对应这些最小元素的类可以同时合并,二、类间距离与系统聚类法,例：设有六个样品，每个只测量一个指标，分别是1，2，5，7，9，10，试用最短距离法将它们分类。（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（2）,二、类间距离与系统聚类法,（4）最后将G7和G9合并成

17、G10，这时所有的六个样品聚为一类，其过程终止。谱系图表示横坐标的刻度表示并类的距离,二、类间距离与系统聚类法,二、类间距离与系统聚类法,再找距离最小两类并类，直至所有的样品全归为一类为止最长距离法与最短距离法只有两点不同：一是类与类之间的距离定义不同；一是计算新类与其它类的距离所用的公式不同,二、类间距离与系统聚类法,3.中间距离法（折中）中间距离将类Gp与Gq类合并为类Gr，则任意的类Gk和Gr的距离公式为(14 0)设DkqDkp最短距离法，则Dkr=Dkp；最长距离法，则Dkr=Dkq。中间距离法：取它们的中间某一点,二、类间距离与系统聚类法,特别当=14，它表示取中间点算距离，公式为

18、,二、类间距离与系统聚类法,二、类间距离与系统聚类法,4.重心法类间距离为两类重心（各类样品的均值）的距离重心指标对类有很好的代表性，但利用各样本的信息不充分,推导如下：,二、类间距离与系统聚类法,二、类间距离与系统聚类法,二、类间距离与系统聚类法,例：（数据同上例）有六个样品，每个只测量一个指标，分别是1，2，5，7，9，10试用重心法将它们聚类（1）样品采用欧氏距离，计算样品间的平方距离阵D2（0）,二、类间距离与系统聚类法,（2）D2（0）中最小的元素是D212D2561，于是将G1和G2合并成G7，G5和G6合并成G8，并计算新类与其它类的距离得到距离阵D2（1）其中，,二、类间距离与

19、系统聚类法,（3）在D2（1）中最小值是D2344，那么G3与G4合并一个新类G9，其与其它类的距离D2（2）：,二、类间距离与系统聚类法,（4）其中最小值是12.5，那么合并一个新类，其与其它类的距离：,二、类间距离与系统聚类法,（5）最后将G7和G10合并成G11，这时所有的六个样品聚为一类，其过程终止。谱系图表示：,二、类间距离与系统聚类法,二、类间距离与系统聚类法,与最短距离法比较一下：,二、类间距离与系统聚类法,5.类平均法类间距离平方取为这两类元素两两之间距离平方的平均数,6.可变类平均法类平均法中没有反映出Gp和Gq之间的距离Dpq的影响将Gp和Gq合并为新类Gr，类Gk与新并类

20、Gr的距离公式推广为：其中是可变的且 1,二、类间距离与系统聚类法,二、类间距离与系统聚类法,8.离差平方和法（Ward方法）基本思想来自于方差分析如果分类正确，同类样品的离差平方和应当较小，类与类的离差平方和较大。具体步骤：先将n个样品各自成一类，然后每次缩小一类，每缩小一类，离差平方和就要增大，选择使其增加最小的两类合并，直到所有的样品归为一类为止。,二、类间距离与系统聚类法,设将n个样品分成k类G1，G2，Gk，用Xit表示Gt中的第i个样品，nt表示Gt中样品的个数，是Gt的重心，则Gt的样品离差平方和为,二、类间距离与系统聚类法,二、类间距离与系统聚类法,三、类间距离的统一,上述八种

21、系统聚类法的步骤完全一样，只是距离的递推公式不同。兰斯（Lance）和威廉姆斯（Williams）于1967年给出了一个统一的公式。ap、aq、是参数不同的系统聚类法，它们取不同的值注意：不同的聚类方法结果不一定完全相同，一般只是大致相似可将聚类结果与实际问题对照，看哪一个结果更符合经验,表 系统聚类法参数表,三、类间距离的统一,单调性：令Di是系统聚类法中第i次并类时的距离，如果一种系统聚类法能满足D1D2D3 单调性符合系统聚类法的思想，先合并较相似的类，后合并较疏远的类最短距离法、最长距离法、可变法、类平均法、可变类平均法和离差平方和法都具有单调性中间距离法和重心法不具有单调性,四、单调

22、性,五、类的个数,如果能够分成若干个很分开的类，则类的个数就比较容易确定；如果无论怎样分都很难分成明显分开的若干类，则类个数的确定就比较困难常用方法：给定一个阈值T通过观察谱系图，给出一个合适的阈值T，要求类与类之间的距离要大于T有较强的主观性观测样品的散点图如果样品只有两个或三个变量，则可通过观测数据的散点图来确定类的个数如果变量个数超过三个，可先降维(费舍尔判别法等）使用统计量（模型选择）,观测散点图可以从直觉上来判断所采用的聚类方法是否合理可直接从散点图中进行主观的分类,五、类的个数-寻找“自然的”类,五、类的个数画图法,依次尝试不同的k值(x)，计算某个度量（统计量、距离等）(y)画图

23、，显示y随x的变化趋势找拐点，作为确定k的根据当曲线拐点很平缓时，可选择的k很多，这时需要用其它的办法来确定,第四节 K均值聚类分析,系统聚类法计算量大快速聚类方法-K均值法由麦奎因(MacQueen,1967)提出的基本思想：将每一个样品分配给最近中心(均值)的类中：1将所有的样品分成K个初始类；2通过距离度量将某个样品划入离中心（中心怎么定？）最近的类中；3.对获得样品与失去样品的类，重新计算中心坐标；4重复步骤2、3直到所有的样品都不能再分配时为止。,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,K=2任意选择 K个对象作为初始聚类中心,将每

24、个对象赋给最类似的中心,更新聚类的平均值,重新分配,更新聚类的平均值,K均值聚类分析,例：对A、B、C、D四个样品分别测量两个变量，得到如下结果，试将这些样品聚成两类。,K均值聚类分析,K均值聚类分析,第一步：按要求取K=2，先将这些样品随意分成两类，比如（A、B）和（C、D），然后计算这两个聚类的中心坐标：,第二步：计算某个样品到各类中心的欧氏平方距离，然后将该样品分配给最近的一类。对于样品有变动的类，重新计算它们的中心坐标，为下一步聚类做准备。先计算A到两个类的平方距离：由于A到（A、B）的距离小于到（C、D）的距离，因此A不用重新分配；计算B到两类的平方距离：对C、D同样（略）,K均值聚

25、类分析,由于B到（A、B）的距离大于到（C、D）的距离，因此B要分配给（C、D）类，得到新的聚类是（A）和（B、C、D）更新中心坐标：,K均值聚类分析,第三步：再次检查每个样品，以决定是否需要重新分类。计算各样品到各中心的距离平方：发现：每个样品都已经分配给距离中心最近的类，聚类过程到此结束最终得到K=2的聚类结果是A独自成一类，B、C、D聚成一类,K均值聚类分析,K均值聚类分析,系统聚类与K均值聚类都是距离度量类聚类方法系统聚类对不同的类数产生一系列的聚类结果K均值法只能产生指定类数的聚类结果具体类数的确定？实践经验的积累（机理研究）借助系统聚类法以一部分样品为对象进行聚类，其结果作为K均值

26、法确定类数的参考,优点:相对有效性: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)当结果簇是密集的，而簇与簇之间区别明显时，它的效果较好,K均值聚类分析,弱点只有在簇的平均值(mean)被定义的情况下才能使用.可能不适用于某些应用涉及有分类属性的数据需要预先指定簇的数目k 不能处理噪音数据和孤立点(outliers)常常终止于局部最优（

27、初值依赖）.尝试不同的初值全局最优 可以使用诸如模拟退火(simulated annealing)和遗传算法(genetic algorithms)等技术得到,K均值聚类分析,K均值方法的变种,它们在以下方面有所不同初始k个平均值的选择距离的度量计算聚类平均值的策略 处理分类属性:k-模(k-modes)方法(Huang98)用模(modes众数)替代聚类的平均值使用新的距离度量方法来处理分类对象 用基于频率的方法k-原型(k-prototype)方法:k-平均和k-模的结合,处理具有数值和分类属性的数据,K均值聚类分析,R codes,一 例一,二 例二,例 一,设有20个土壤样品分别对5个

28、变量的观测数据如表所示，试利用系统聚类法对其进行样品聚类分析。,表 土壤样本的观测数据,例 一,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 variables to be used in the cluster analysis#

29、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 code,par(mfrow=c(3,1)#Use complete linkage(最长距离法),this is also the default methodhc-h

30、clust(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,labe

31、l=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 initialhc-hclust(dist(data.sx),method=average)initial-tapply(as.

32、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),km$cluster),主要运行结果解释1.在结果输出窗口中可以看到谱系图（

33、Dendrogram）若将20个样品分为两类：样品2、6、19、7、18和样品1为一类其余的为另一类；若将样品分为三类：样品8、9、4从第二类中分离出来，自成一类；依此类推,例 一,图 系统聚类法谱系图,例 一,例 二,我国各地区2003年三个产业产值如表所示，试根据三个产业产值利用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-rea

34、d.table(file=datasets/chanzhi.txt,header=T,col.names=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#Standardize the datadata.mean-apply(data.x,2,mean)data.std-sqrt(apply(data.x,2,var)data.sx-sweep(data.x,2,data.

35、mean,FUN=-)data.sx-sweep(data.sx,2,data.std,FUN=/),R code,#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 linkagehc-hclust(dist(data.sx),method=average)plclust(hc,label=id)title(Aver

36、age Linkage Cluster Analysis)#Use single linkagehc-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 clust

37、ers 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$Province),km$cluster)#Compute K-means cluster analysis starting with random int

38、ializations#Note that this is the default and is controlled by nstart#(by default,this is one).km-kmeans(x=data.sx,centers=3,nstart=10000)cbind(as.character(data$Province),km$cluster),表 各观测量所属类成员表,例 二（SPSS结果）,可以看出31个地区被分成3类第一类包括：江苏、浙江、山东和广东4个省。这一类的类中心三个产业的产值分别为1102.14亿元、6423.01亿元和4454.26亿元，属于三个产业都比较

39、发达的地区；第二类包括：天津、山西、内蒙古、吉林、江西、广西、海南、重庆、贵州、云南、西藏、陕西、甘肃、青海、宁夏和新疆16个地区。这一类的类中心三个产业的产值分别为307.61亿元、795.41亿元和673.63亿元，属于欠发达地区；剩下的11个地区为第三类。这一类的类中心三个产业的产值分别为713.28亿元、2545.20亿元和212.87亿元，属于中等发达地区。比较初始值vs自动,例 二,k-均值聚类算法对孤立点(异常点)很敏感!因为具有特别大的值的对象可能显著地影响数据的分布.k-中心点(k-Medoids):不采用簇中对象的平均值作为参照点,而是选用簇中位置最中心的对象,即中心点(m

40、edoid，代表点)作为参照点.,K中心点聚类分析,PAM(Partitioning Around Medoids)(Kaufman and Rousseeuw,1987)是最早提出的k-中心点聚类算法基本思想：首先为每个簇随意选择一个代表对象;剩余的对象根据其与代表对象的距离分配给最近的一个簇然后反复地用非代表对象来替代代表对象,以改进聚类的质量聚类结果的质量用一个代价函数来估算,该函数评估了对象与其参照对象之间的平均距离,K中心点聚类分析,为了判定一个非代表对象Orandom 是否是当前一个代表对象Oj的好的替代,对于每一个非代表对象p,考虑下面的四种情况：第一种情况：p当前隶属于代表对象

41、 Oj.如果Oj被Orandom所代替,且p离Oi最近,ij,那么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中心点聚类分析,1.重新分配给Oi 2.重新分配给Orandom 3.不发生变化 4.重新分配给Orandom 数据对象+簇中心 替代前 替代

42、后 图 k-中心点聚类代价函数的四种情况,+,+,+,Orandom,Oi,Oj,p,+,+,+,Orandom,Oi,Oj,p,+,+,+,Orandom,Oi,Oj,p,+,+,+,Orandom,Oi,Oj,p,K中心点聚类分析,算法:k-中心点(1)随机选择k个对象作为初始的代表对象（中心点）；(2)repeat(3)指派每个剩余的对象给离它最近的代表对象所代表的簇；(4)随意地选择一个非代表对象Orandom；(5)计算用Orandom代替Oj的总代价S；S=代替后的点的平方误差函数-原来的平方误差函数(6)如果S0，则用Orandom替换Oj，形成新的k个代表对象的集合；(7)un

43、til 不发生变化,K中心点聚类分析,Total Cost=20,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,K=2,Arbitrary choose k object as initial medoids,Assign each remaining object to nearest medoids,Randomly select a nonmedoid object,Oramdom,Compute total cost of swapping,Total Cost=26,Swapping O and Oramdom If quality is

44、 improved.,Do loopUntil no change,K中心点聚类分析-PAM,当存在噪音和孤立点时,PAM 比 k-平均方法更健壮因为中心点不象平均值那么容易被极端数据影响 PAM对于小数据集工作得很好,但不能很好地用于大数据集 每次迭代O(k(n-k)2)其中 n 是数据对象数目,k 是聚类数CLARA(Kaufmann&Rousseeuw,1990)抽样,K中心点聚类分析-PAM,PAM algorithm is inefficient for clustering large data,the CLARA algorithm is an enhanced techniqu

45、e of PAM by drawing multiple samples of data,appling PAM on each sample and then returning the best clustering.pam()and clara()in package“cluster”which need user to specify kEnhanced version of pam(),function pamk()in package“fpc”does not require a user to choose k.,K中心点聚类分析-PAM,iris2-iris#remove sp

46、ecies from the data to clusteriris2$Species-NULLlibrary(fpc)pamk.result-pamk(iris2)#number of clusterspamk.result$nc#check clustering against real speciestable(pamk.result$pamobject$clustering,iris$Species)layout(matrix(c(1,2),1,2)#2 graphs per pageplot(pamk.result$pamobject)layout(matrix(1)#change back to one graph per page,K中心点聚类分析-PAM,#we try pam()with k=3.library(cluster)pam.result-pam(iris2,3)table(pam.result$clustering,iris$Species)layout(matrix(c(1,2),1,2)#2 graphs per pageplot(pam.result)layout(matrix(1)#change back to one graph per page,K中心点聚类分析-PAM,