聚类分析-K-meansandK-medoids聚类1

智能数据挖掘Topic3--聚类分析K-means&K-medoids

聚类2023/2/1主要内容K-means算法Matlab程序实现在图像分割上的简单应用K-medoids算法k-中心点聚类算法--PAMK-medoids改进算法2023/2/1基于划分的聚类方法构造n个对象数据库D的划分,将其划分成k个聚类启发式方法:k-平均值(k-

means)和k-中心点(k-

medoids)算法k-平均值(MacQueen’67):每个簇用该簇中对象的平均值来表示k-中心点或PAM(Partitionaroundmedoids)(Kaufman&Rousseeuw’87):每个簇用接近聚类中心的一个对象来表示这些启发式算法适合发现中小规模数据库中的球状聚类对于大规模数据库和处理任意形状的聚类,这些算法需要进一步扩展2023/2/1K-means聚类算法算法描述为中心向量c1,c2,…,ck初始化k个种子分组:将样本分配给距离其最近的中心向量由这些样本构造不相交（non-overlapping

）的聚类确定中心:用各个聚类的中心向量作为新的中心重复分组和确定中心的步骤，直至算法收敛2023/2/1K-means聚类算法（续）算法的具体过程从数据集中任意选取k个赋给初始的聚类中心c1,c2,…,ck；对数据集中的每个样本点xi，计算其与各个聚类中心cj的欧氏距离并获取其类别标号：

按下式重新计算k个聚类中心；重复步骤2和步骤3，直到达到最大迭代次数、聚类目标函数达到最优值或者两次迭代得到的目标函数变化小于给定的为止。2023/2/1k-平均聚类算法(续)例012345678910012345678910012345678910012345678910K=2任意选择

K个对象作为初始聚类中心将每个对象赋给最类似的中心更新簇的平均值重新赋值更新簇的平均值重新赋值2023/2/1Matlab程序实现function[M,j,e]=kmeans(X,K,Max_Its)[N,D]=size(X);I=randperm(N);M=X(I(1:K),:);Mo=M;forn=1:Max_Itsfork=1:K

Dist(:,k)=sum((X-repmat(M(k,:),N,1)).^2,2)';end

[i,j]=min(Dist,[],2);fork=1:Kifsize(find(j==k))>0

M(k,:)=mean(X(find(j==k),:));endend2023/2/1Matlab程序实现（续）Z=zeros(N,K);form=1:N

Z(m,j(m))=1;end

e=sum(sum(Z.*Dist)./N);

fprintf('%dError=%f\n',n,e);Mo=M;end2023/2/1在图像分割上的简单应用例1：图片：一只遥望大海的小狗；此图为100x100像素的JPG图片，每个像素可以表示为三维向量（分别对应JPEG图像中的红色、绿色和蓝色通道）

；将图片分割为合适的背景区域（三个）和前景区域（小狗）；使用K-means算法对图像进行分割。2023/2/1在图像分割上的简单应用（续）分割后的效果注：最大迭代次数为20次，需运行多次才有可能得到较好的效果。2023/2/1在图像分割上的简单应用（续）例2：注：聚类中心个数为5，最大迭代次数为10。2023/2/1k-平均聚类算法(续)优点:相对有效性:O(tkn),其中n

是对象数目,k

是簇数目,t是迭代次数;通常,k,t<<n.当结果簇是密集的，而簇与簇之间区别明显时，它的效果较好2023/2/1k-平均聚类算法(续)弱点只有在簇的平均值(mean)被定义的情况下才能使用.可能不适用于某些应用,例如涉及有分类属性的数据需要预先指顶簇的数目k,不能处理噪音数据和孤立点(outliers)不适合用来发现具有非凸形状(non-convexshapes)的簇2023/2/1k-中心点聚类方法k-平均值算法对孤立点很敏感!因为具有特别大的值的对象可能显著地影响数据的分布.k-中心点(k-Medoids):不采用簇中对象的平均值作为参照点,而是选用簇中位置最中心的对象,即中心点(medoid)作为参照点.0123456789100123456789100123456789100123456789100123456789100123456789102023/2/1k-中心点聚类方法(续)找聚类中的代表对象(中心点)PAM(PartitioningAroundMedoids,1987)首先为每个簇随意选择选择一个代表对象,剩余的对象根据其与代表对象的距离分配给最近的一个簇;然后反复地用非代表对象来替代代表对象，以改进聚类的质量

PAM

对于较小的数据集非常有效,但不能很好地扩展到大型数据集2023/2/1k-中心点聚类方法(续)基本思想：首先为每个簇随意选择选择一个代表对象;剩余的对象根据其与代表对象的距离分配给最近的一个簇；然后反复地用非代表对象来替代代表对象,以改进聚类的质量；聚类结果的质量用一个代价函数来估算。2023/2/1k-中心点聚类方法(续)为了判定一个非代表对象Orandom

是否是当前一个代表对象Oj的好的替代,对于每一个非代表对象p,考虑下面的四种情况：

第一种情况：p当前隶属于代表对象Oj.如果Oj被Orandom所代替,且p离Oi最近,i≠j,那么p被重新分配给Oi

第二种情况：p当前隶属于代表对象Oj.如果Oj

被Orandom代替,且p离Orandom最近,那么p被重新分配给Orandom

1.重新分配给Oi 2.重新分配给Orandom2023/2/1k-中心点聚类方法(续)第三种情况：p当前隶属于Oi，i≠j。如果Oj被Orandom代替，而p仍然离Oi最近，那么对象的隶属不发生变化

第四种情况：p当前隶属于Oi，i≠j。如果Oj被Orandom代替，且p离Orandom最近，那么p被重新分配给Orandom

3.不发生变化4.重新分配给Orandom2023/2/1k-中心点聚类方法(续)算法:k-中心点(1)随机选择k个对象作为初始的代表对象；(2)repeat (3)指派每个剩余的对象给离它最近的代表对象所代表的簇； (4)随意地选择一个非代表对象Orandom； (5)计算用Orandom代替Oj的总距离E,如果E比取代前下降则则用Orandom替换Oj，形成新的k个代表对象的集合，返回（4）；(6)until不发生变化(7)如果所有非代表对象都无法取代已存在的簇中心，则结束替代过程，并输出结果2023/2/1PAM(续)TotalCost=20012345678910012345678910K=2ArbitrarychoosekobjectasinitialmedoidsAssigneachremainingobjecttonearestmedoidsRandomlyselectanonmedoid

object,OramdomComputetotalcostofswapping012345678910012345678910TotalCost=26SwappingOandOramdom

Ifqualityisimproved.DoloopUntilnochange0123456789100123456789102023/2/1PAM(续)当存在噪音和孤立点时,PAM比

k-平均方法更健壮.这是因为中心点不象平均值那么容易被极端数据影响

PAM对于小数据集工作得很好,但不能很好地用于大数据集

每次迭代O(k(n-k)2)

其中

n

是数据对象数目,

k是聚类数基于抽样的方法, CLARA(ClusteringLARgeApplications)2023/2/1CLARA

(ClusteringLargeApplications)

(1990)CLARA(KaufmannandRousseeuwin1990)不考虑整个数据集,而是选择数据的一小部分作为样本它从数据集中抽取多个样本集,对每个样本集使用PAM,并以最好的聚类作为输出优点:可以处理的数据集比PAM大缺点:有效性依赖于样本集的大小基于样本的好的聚类并不一定是整个数据集的好的聚类,样本可能发生倾斜

例如,Oi是最佳的k个中心点之一,但它不包含在样本中,CLARA将找不到最佳聚类2023/2/1CLARA--效率由取样大小决定PAM→利用完整资料集

CLARA→利用取样资料集

盲点：取样范围不包含最佳解

sampledbestTrade-off232023/2/1CLARA改良解決：CLARANS(ClusteringLargeApplicationbaseduponRANdomizedSearch)应用

graph考虑紧邻节点不局限于区域性复杂度：O(n^2)→缺点242023/2/1CLARA的有效性主要取决于样本的大小。如果任何一个最佳抽样中心点不在最佳的K个中心之中，则CLARA将永远不能找到数据集合的最佳聚类。同时这也是为了聚类效率做付出的代价。

CLARANS聚类则是将CLARA和PAM有效的结合起来，CLARANS在任何时候都不把自身局限于任何样本，CLARANS在搜素的每一步都以某种随机性选取样本。算法步骤如下CLARANS(“Randomized”CLARA)(1994)2023/2/1CLARANS

(“Randomized”CLARA)(1994)CLARANS(AClusteringAlgorithmbasedonRandomizedSearch)(NgandHan’94)CLARANS将采样技术和PAM结合起来CLARA在搜索的每个阶段有一个固定的样本CLARANS任何时候都不局限于固定样本,而是在搜索的每一步带一定随机性地抽取一个样本聚类过程可以被描述为对一个图的搜索,图中的每个节点是一个潜在的解,也就是说k-medoids相邻节点：代表的集合只有一个对象不同在替换了一个代表对象后得到的聚类结果被称为当前聚类结果的邻居2023/2/1CLARANS(续)如果一个更好的邻居被发现,CLARANS移到该邻居节点,处理过程重新开始,否则当前的聚类达到了一个局部最优如果找到了一个局部最优,CLARANS从随机选择的节点开始寻找新的局部最优实验显示CLARANS比PAM和CLARA更有效CLARANS能够探测孤立点聚焦技术和空间存取结构可以进一步改进它的性能(Esteretal.’95)2023/2/11、输入参数numlocal和maxneighbor。numlocal

表示抽样的次数，maxneighbor

表示一个节点可以与任意特定邻居进行比较的数目。令：i=1，i用来表示已经选样的次数mincost为最小代价，初始时设为大数。

2、设置当前节点current为Gn中的任意一个节点。

3、令j=1。（j用来表示已经与current进行比较的邻居的个数）

4、考虑当前点的一个随机的邻居S，并计算两个节点的代价差。5、如果S的代价较低，则current:=S，转到步骤3。

6、否则，令j=j+1。如果j<=maxneighbor,则转到步骤4。

7、否则，当j>maxneighbor，当前节点为本次选样最小代价节点.如果其代价小于mincost,令mincost为当前节点的代价，bestnode为当前的节点。

8、令i=i+1，如果i〉numlocal,输出bestnode，运算中止.否则，转到步骤2。CLARANS(“Randomized”CLARA)(1994)2023/2/11）代价值，主要描述一个对象被分到一个类别中的代价值，该代价值由每个对象与其簇中心点间的相异度（距离或者相似度）的总和来定义。代价差则是两次随机领域的代价差值。

（2）更新邻接点，CLARANS不会把搜索限制在局部区域，如果发现一个更好的近邻，CLARANS就移到该近邻节点，处理过程从新开始；否则，当前的聚类则产生了一个局部最小。如果找到一个局部最小，CLARANS从随机选择的新节点开始，搜索新的局部最小。当搜索的局部最小解达到用户指定的数目时，最好的局部最小作为算法的输出。从上面的算法步骤也可以看出这一思想。在第5步中更新节点current。CLARANS(“Randomized”CLARA)(1994)2023/2/1综合比较KmeansKmedoidsCLARACLARANS优点简单不受极值影响可处理大数据找到最佳解缺点受极值影响无法