聚类分析—K-means-and-K-medoids聚类(课堂PPT).ppt

,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,数据挖掘,Topic3-,聚类分析,K-means&K-medoids,聚类,2025/8/27 周三,主要内容,K-means,算法,Matlab,程序实现,在图像分割上的简单应用,K-,medoids,算法,k-,中心点聚类算法,-PAM,K-,medoids,改进,算法,2025/8/27 周三,基于划分的聚类方法,构造,n,个对象数据库,D,的划分,将其划分成,k,个聚类,启发式方法:,k-,平均值(,k-,means,),和,k-,中心点(,k-,medoids,),算法,k-,平均值,(MacQueen67):,每个簇用该簇中对象的平均值来表示,k-,中心点或,PAM(Partition around medoids)(Kaufman&Rousseeuw87):,每个簇用接近聚类中心的一个对象来表示,这些启发式算法适合发现中小规模数据库中的球状聚类,对于大规模数据库和处理任意形状的聚类,这些算法需要进一步扩展,2025/8/27 周三,K-means,聚类算法,算法描述,为中心向量,c,1,c,2,c,k,初始化,k,个种子,分组,:,将样本分配给距离其最近的中心向量,由这些样本构造不相交（,non-overlapping,）的聚类,确定中心,:,用各个聚类的中心向量作为新的中心,重复分组和确定中心的步骤，直至算法收敛,2025/8/27 周三,K-means,聚类算法,（续）,算法的具体过程,从数据集 中任意选取,k,个赋给初始的聚类中心,c,1,c,2,c,k,；,对数据集中的每个样本点,x,i,，计算其与各个聚类中心,c,j,的欧氏距离并获取其类别标号：,按下式重新计算,k,个聚类中心；,重复步骤,2,和步骤,3,，直到达到最大迭代次数为止。,2025/8/27 周三,Matlab,程序实现,function,M,j,e=kmeans(X,K,Max_Its),N,D=size(X);,I=randperm(N);,M=X(I(1:K),:);,Mo=M;,for n=1:Max_Its,for k=1:K,Dist(:,k)=sum(X-repmat(M(k,:),N,1).2,2);,end,i,j=min(Dist,2);,for k=1:K,if size(find(j=k)0,M(k,:)=mean(X(find(j=k),:);,end,end,2025/8/27 周三,Matlab,程序实现,（续）,Z=zeros(N,K);,for m=1:N,Z(m,j(m)=1;,end,e=sum(sum(Z.*Dist)./N);,fprintf(%d Error=%fn,n,e);,Mo=M;,end,2025/8/27 周三,k-,平均聚类算法(续),例,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,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,个对象作为初始聚类中心,将每个对象赋给最类似的中心,更新簇的平均值,重新赋值,更新簇的平均值,重新赋值,2025/8/27 周三,在图像分割上的简单应用,例,1,：,图片：一只遥望大海的小狗；,此图为,100 x 100,像素的,JPG,图片，每个像素可以表示为三维向量（分别对应,JPEG,图像中的红色、绿色和蓝色通道）,；,将图片分割为合适的背景区域（三个）和前景区域（小狗）；,使用,K-means,算法对图像进行分割。,2025/8/27 周三,在图像分割上的简单应用,（续）,分割后的效果,注：最大迭代次数为,20,次，需运行多次才有可能得到较好的效果。,2025/8/27 周三,在图像分割上的简单应用,（续）,例,2,：,注：聚类中心个数为,5,，最大迭代次数为,10,。,2025/8/27 周三,k-,平均聚类算法(续),优点:,相对有效性:,O,(,tkn,),其中,n,是对象数目,k,是簇数目,t,是迭代次数;通常,k,t,n,.,当结果簇是密集的，而簇与簇之间区别明显时，它的效果较好,Comment:,常常终止于,局部最优,.,全局最优,可以使用诸如确定性的退火(,deterministic annealing),和遗传算法(,genetic algorithms,),等技术得到,2025/8/27 周三,k-,平均聚类算法(续),弱点,只有在簇的平均值(,mean),被定义的情况下才能使用.可能不适用于某些应用,例如涉及有,分类属性,的数据,需要预先指顶簇的数目,k,不能处理噪音数据和孤立点,(,outliers,),不适合用来发现具有非凸形状(,non-convex shapes),的簇,2025/8/27 周三,k-,中心点聚类方法,k,-,平均值算法对孤立点很敏感,!,因为具有特别大的值的对象可能显著地影响数据的分布,.,k-,中心点,(,k,-Medoids):,不采用簇中对象的平均值作为参照点,而是,选用簇中位置最中心的对象,即中心点(,medoid),作为参照点,.,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,2025/8/27 周三,k-,中心点聚类方法(续),找聚类中的代表对象(中心点),PAM,(Partitioning Around Medoids,1987),首先为每个簇随意选择选择一个代表对象,剩余的对象根据其与代表对象的距离分配给最近的一个簇;然后反复地用非代表对象来替代代表对象，以改进聚类的质量,PAM,对于较小的数据集非常有效,但不能很好地扩展到大型数据集,CLARA,(Kaufmann&Rousseeuw,1990),抽样,CLARANS,(Ng&Han,1994):,随机选样,2025/8/27 周三,k-,中心点聚类方法(续),基本思想：,首先为每个簇随意选择选择一个代表对象;剩余的对象根据其与代表对象的距离分配给最近的一个簇,然后反复地用非代表对象来替代代表对象,以改进聚类的质量,聚类结果的质量用一个代价函数来估算,该函数评估了对象与其参照对象之间的平均相异度,2025/8/27 周三,k-,中心点聚类方法(续),为了判定一个非代表对象,O,random,是否是当前一个代表对象,O,j,的好的替代,对于每一个非代表对象,p,考虑下面的四种情况：,第一种情况：,p,当前隶属于代表对象,O,j,.,如果,O,j,被,O,random,所代替,且,p,离,O,i,最近,ij,那么,p,被重新分配给,O,i,第二种情况：,p,当前隶属于代表对象,O,j,.,如果,O,j,被,O,random,代替,且,p,离,O,random,最近,那么,p,被重新分配给,O,random,第三种情况：,p,当前隶属于,O,i,，ij。,如果,O,j,被,O,random,代替，而,p,仍然离,O,i,最近，那么对象的隶属不发生变化,第四种情况：,p,当前隶属于,O,i,，ij。,如果,O,j,被,O,random,代替，且,p,离,O,random,最近，那么,p,被重新分配给,O,random,2025/8/27 周三,k-,中心点聚类方法(续),1.,重新分配给,Oi 2.,重新分配给,Orandom,3.,不发生变化 4.重新分配给,Orandom,k-,中心点聚类代价函数的四种情况,2025/8/27 周三,k-,中心点聚类方法(续),算法:,k-,中心点,(1)随机选择,k,个对象作为初始的代表对象；,(2),repeat,(3)指派每个剩余的对象给离它最近的代表对象所代表的簇；,(4)随意地选择一个非代表对象,O,random,；,(5),计算用,O,random,代替,O,j,的总代价,S；,(6),如果,S0，,则用,O,random,替换,O,j,，,形成新的,k,个代表对象的集合；,(7),until,不发生变化,2025/8/27 周三,PAM,PAM(Partitioning Around Medoids)(Kaufman and Rousseeuw,1987),是最早提出的,k-,中心点聚类算法,基本思想:,随机选择,k,个代表对象,反复地试图找出更好的代表对象:分析所有可能的对象对，每个对中的一个对象被看作是代表对象,而另一个不是.对可能的各种组合,估算聚类结果的质量,2025/8/27 周三,PAM(,续),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,O,ramdom,Compute total cost of swapping,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,Total Cost=26,Swapping O and O,ramdom,If quality is improved.,Do loop,Until no change,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,2025/8/27 周三,PAM(,续),当存在噪音和孤立点时,PAM,比,k-,平均方法更健壮.这是因为中心点不象平均值那么容易被极端数据影响,PAM,对于小数据集工作得很好,但不能很好地用于大数据集,每次迭代,O,(,k,(,n-k,),2,),其中,n,是数据对象数目,k,是聚类数,基于抽样的方法,CLARA(Clustering,LARge,Applications),2025/8/27 周三,CLARA,(Clustering Large Applications),(1990),CLARA,(Kaufmann and Rousseeuw in 1990),不考虑整个数据集,而是选择数据的一小部分作为样本,它从数据集中抽取多个样本集,对每个样本集使用,PAM,并以最好的聚类作为输出,优点,:可以处理的数据集比,PAM,大,缺点:,有效性依赖于样本集的大小,基于样本的好的聚类并不一定是 整个数据集的好的聚类,样本可能发生倾斜,例如,Oi,是最佳的,k,个中心点之一,但它不包含在样本中,CLARA,将找不到最佳聚类,2025/8/27 周三,CLARA-,效率,由取,样,大小,决,定,PAM,利用完整,资,料集,CLARA,利用取,样资,料集,盲点,：取,样范围,不包含最佳解,sampled,best,Trade-off,24,2025/8/27 周三,CLARA 改良,解決：,CLARANS(Clustering Large Application based upon RANdomized Search),应,用,graph,考虑紧邻节点,不,局限于区域性,负杂,度：,O(n2),缺,点,25,2025/8/27 周三,CLARANS,(“Randomized”CLARA),(1994),CLARANS,(A Clustering Algorithm based on Randomized Search)(Ng and Han94),CLARANS,将采样技术和,PAM,结合起来,CLARA,在搜索的每个阶段有一个固定的样本,CLARANS,任何时候都不局限于固定样本,而是在搜索的每一步带一定随机性地抽取一个样本,聚类过程可以被描述为对一个图的搜索,图中的每个节点是一个潜在的解,也就是说,k,-medoids,相邻节点：代表的集合只有一个对象不同,在替换了一个代表对象后得到的聚类结果被称为当前聚类结果的邻居,2025/8/27 周三,CLARANS,(,续),如果一个更好的邻居被发现,CLARANS,移到该邻居节点,处理过程重新开始,否则当前的聚类达到了一个局部最优,如果找到了一个局部最优,CLARANS,从随机选择的节点开始寻找新的局部最优,实验显示,CLARANS,比,PAM,和,CLARA,更有效,CLARANS,能够探测孤立点,聚焦技术和空间存取结构可以进一步改进它的性能,(Ester et al.95),2025/8/27 周三,综合比较,K means,K medoids,CLARA,CLARANS,优点,简单,不受,极值影响,可,处理大数据,找到最佳解,缺,点,受极值影响,无法处理大数据,不一定,是,最佳解,速度慢,复杂,度,O(nkt),O(,k(n-k)2,),O(ks2+k(n-k),O(n2),精確度,速度,28,2025/8/27 周三,作业,编程实现,K,-means,算法针对,UCI,的,waveform,数据集中每类数据取,100,个；对一副无噪图像进行分割；,编程实现,PAM,对部分,waveform,数据集加,20%,的高斯噪声；同时对一副噪声图像进行分割；,编程实现,CLARA,在全部的,waveform,数据集上的聚类；,due date,：,4,月,25,日,2025/8/27 周三,K-means,聚类算法,（续）,分组,:,将样本分配给距离它们最近的中心向量，并使目标函数值减小,确定中心,:,亦须有助于减小目标函数值,2025/8/27 周三,k-,中心点聚类方法(续),1.,重新分配给,Oi 2.,重新分配给,Orandom,3.,不发生变化 4.重新分配给,Orandom,k-,中心点聚类代价函数的四种情况,2025/8/27 周三,k-,中心点聚类方法(续),基本思想：,首先为每个簇随意选择选择一个代表对象;剩余的对象根据其与代表对象的距离分配给最近的一个簇,然后反复地用非代表对象来替代代表对象,以改进聚类的质量,聚类结果的质量用一个代价函数来估算,该函数评估了对象与其参照对象之间的平均相异度,2025/8/27 周三,