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

1、智能数据挖掘智能数据挖掘Topic3-聚类分析聚类分析K-means &K-medoids 聚类聚类2022-6-26主要内容K-means算法Matlab程序实现在图像分割上的简单应用K-medoids算法k-中心点聚类算法中心点聚类算法-PAMK-medoids改进算法2022-6-26基于划分的聚类方法基于划分的聚类方法n构造构造n个对象数据库个对象数据库D的划分的划分, 将其划分成将其划分成k个聚类个聚类n启发式方法启发式方法: k-平均值平均值(k- means)和和 k-中心点中心点(k- medoids) 算算法法nk-平均值平均值(MacQueen67): 每个簇用该簇

2、中对象的平均值来表示每个簇用该簇中对象的平均值来表示 nk-中心点或中心点或 PAM (Partition around medoids) (Kaufman & Rousseeuw87): 每个簇用接近聚类中心的一个对象来表示每个簇用接近聚类中心的一个对象来表示 n这些启发式算法适合发现中小规模数据库中的球状聚类这些启发式算法适合发现中小规模数据库中的球状聚类n对于大规模数据库和处理任意形状的聚类对于大规模数据库和处理任意形状的聚类,这些算法需要进这些算法需要进一步扩展一步扩展2022-6-26K-means聚类算法聚类算法n算法描述算法描述1. 为中心向量c1, c2, , ck初始

3、化k个种子2. 分组: 将样本分配给距离其最近的中心向量 由这些样本构造不相交（ non-overlapping ）的聚类3. 确定中心: 用各个聚类的中心向量作为新的中心4. 重复分组和确定中心的步骤，直至算法收敛2022-6-26K-means聚类算法聚类算法（续）（续）n算法的具体过程算法的具体过程1.从数据集 中任意选取k个赋给初始的聚类中心c1, c2, , ck；2.对数据集中的每个样本点xi，计算其与各个聚类中心cj的欧氏距离并获取其类别标号： 3.按下式重新计算k个聚类中心；4.重复步骤2和步骤3，直到达到最大迭代次数、聚类目标函数达到最优值或者两次迭代得到的目标函数变化小于给

4、定的为止。1Nnnx2( )argmin | ,1,.,1,.,ijjlabel iiN jkxc:( ),1,2,.,ss label sjjjcjkNx2022-6-26k-平均聚类算法平均聚类算法(续续)n例例012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910K=2任意选择任意选择 K个对个对象作为初始聚类象作为初始聚类中心中心将每个将每个对象赋对象赋给最类给最类似的中似的中心心更新簇更新簇的平均的平

5、均值值重新赋值重新赋值更新簇更新簇的平均的平均值值重新赋值重新赋值2022-6-26Matlab程序实现程序实现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), :);

6、end end2022-6-26Matlab程序实现程序实现（续）（续） 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;end2022-6-26在图像分割上的简单应用在图像分割上的简单应用例例1：1. 图片：一只遥望大海的小狗；2. 此图为100 x 100像素的JPG图片，每个像素可以表示为三维向量（分别对应JPEG图像中的红色、绿色和蓝色通道） ；3. 将图片分割为合适的背景区域（三个）和前景区域（小狗）；4. 使用K-m

7、eans算法对图像进行分割。2022-6-26在图像分割上的简单应用在图像分割上的简单应用（续）（续）分割后的效果注：最大迭代次数为20次，需运行多次才有可能得到较好的效果。2022-6-26在图像分割上的简单应用在图像分割上的简单应用（续）（续）例例2：注：聚类中心个数为5，最大迭代次数为10。2022-6-26k-平均聚类算法平均聚类算法(续续)n优点优点: 相对有效性相对有效性: O(tkn), 其中其中 n 是对象数目是对象数目, k 是簇数目是簇数目, t 是迭代次数是迭代次数; 通常通常, k, t n.n当结果簇是密集的，而簇与簇之间区别明显时，它的效果当结果簇是密集的，而簇与簇

8、之间区别明显时，它的效果较好较好2022-6-26k-平均聚类算法平均聚类算法(续续)n弱点弱点n只有在簇的平均值只有在簇的平均值(mean)被定义的情况下才能使用被定义的情况下才能使用.可能不适用于可能不适用于某些应用某些应用, 例如涉及有例如涉及有分类属性分类属性的数据的数据n需要预先指顶簇的数目需要预先指顶簇的数目k, n不能处理噪音数据和孤立点不能处理噪音数据和孤立点(outliers)n不适合用来发现具有非凸形状不适合用来发现具有非凸形状(non-convex shapes)的簇的簇2022-6-26k-中心点聚类方法中心点聚类方法nk-平均值算法对孤立点很敏感平均值算法对孤立点很敏

9、感!n因为具有特别大的值的对象可能显著地影响数据的分布因为具有特别大的值的对象可能显著地影响数据的分布.nk-中心点中心点(k-Medoids): 不采用簇中对象的平均值作为参照不采用簇中对象的平均值作为参照点点, 而是而是选用簇中位置最中心的对象选用簇中位置最中心的对象, 即中心点即中心点(medoid)作作为参照点为参照点. 0123456789100123456789100123456789100123456789100123456789100123456789102022-6-26k-中心点聚类方法中心点聚类方法(续续)n找聚类中的代表对象找聚类中的代表对象(中心点中心点)nPAM (

10、Partitioning Around Medoids, 1987)n首先为每个簇随意选择选择一个代表对象首先为每个簇随意选择选择一个代表对象, 剩余的对象根据剩余的对象根据其与代表对象的距离分配给最近的一个簇其与代表对象的距离分配给最近的一个簇; 然后反复地用然后反复地用非代表对象来替代代表对象，以改进聚类的质量非代表对象来替代代表对象，以改进聚类的质量 nPAM 对于较小的数据集非常有效对于较小的数据集非常有效, 但不能很好地扩展到大但不能很好地扩展到大型数据集型数据集2022-6-26k-中心点聚类方法中心点聚类方法(续续)n基本思想：基本思想：n首先为每个簇随意选择选择一个代表对象首先

11、为每个簇随意选择选择一个代表对象; 剩余的对象剩余的对象根据其与代表对象的距离分配给最近的一个簇；根据其与代表对象的距离分配给最近的一个簇；n然后反复地用非代表对象来替代代表对象然后反复地用非代表对象来替代代表对象, 以改进聚类以改进聚类的质量；的质量；n聚类结果的质量用一个代价函数来估算。聚类结果的质量用一个代价函数来估算。 21|jkijp CEpo2022-6-26k-中心点聚类方法中心点聚类方法(续续)n为了判定一个非代表对象为了判定一个非代表对象Orandom 是否是当前一个代表对象是否是当前一个代表对象Oj的好的替代的好的替代, 对于每一个非代表对象对于每一个非代表对象p,考虑下面

12、的四种情况：考虑下面的四种情况： n第一种情况：第一种情况：p当前隶属于代表对象当前隶属于代表对象 Oj. 如果如果Oj被被Orandom所代替所代替, 且且p离离Oi最近最近, ij, 那么那么p被重新分配给被重新分配给Oi n第二种情况：第二种情况：p当前隶属于代表对象当前隶属于代表对象 Oj. 如果如果Oj 被被Orandom代替代替, 且且p离离Orandom最最近近, 那么那么p被重新分配给被重新分配给Orandom 1.重新分配给重新分配给Oi 2. 重新分配给重新分配给Orandom2022-6-26k-中心点聚类方法中心点聚类方法(续续)n第三种情况：第三种情况：p当前隶属于当

13、前隶属于Oi，ij。如果如果Oj被被Orandom代替，而代替，而p仍然离仍然离Oi最近，最近，那么对象的隶属不发生变化那么对象的隶属不发生变化 n第四种情况：第四种情况：p当前隶属于当前隶属于Oi，ij。如果如果Oj被被Orandom代替，且代替，且p离离Orandom最近，最近，那么那么p被重新分配给被重新分配给Orandom 3. 不发生变化不发生变化 4.重新分配给重新分配给Orandom2022-6-26k-中心点聚类方法中心点聚类方法(续续)n算法算法: k-中心点中心点(1) 随机选择随机选择k个对象作为初始的代表对象；个对象作为初始的代表对象；(2) repeat(3) 指派每

14、个剩余的对象给离它最近的代表对象所代表的簇；指派每个剩余的对象给离它最近的代表对象所代表的簇；(4) 随意地选择一个非代表对象随意地选择一个非代表对象Orandom；(5) 计算用计算用Orandom代替代替Oj的总距离的总距离E, 如果如果E比取代前下降则则用比取代前下降则则用Orandom替替 换换Oj，形成新的形成新的k个代表对象的集合，返回（个代表对象的集合，返回（4）；）； (6) until 不发生变化不发生变化(7) 如果所有非代表对象都无法取代已存在的簇中心，则结束替代过程，并输如果所有非代表对象都无法取代已存在的簇中心，则结束替代过程，并输出结果出结果2022-6-26PAM

15、(续续)Total Cost = 20012345678910012345678910K=2Arbitrary choose k object as initial medoidsAssign each remaining object to nearest medoidsRandomly select a nonmedoid object,OramdomCompute total cost of swapping012345678910012345678910Total Cost = 26Swapping O and Oramdom If quality is improved.Do loo

16、pUntil no change0123456789100123456789102022-6-26PAM(续续)n当存在噪音和孤立点时当存在噪音和孤立点时, PAM 比比 k-平均方法更健壮平均方法更健壮. 这是因为中心点不象平均值那么容易被极端数据影这是因为中心点不象平均值那么容易被极端数据影响响 nPAM对于小数据集工作得很好对于小数据集工作得很好, 但不能很好地用于但不能很好地用于大数据集大数据集 n每次迭代每次迭代O(k(n-k)2 )其中其中 n 是数据对象数目是数据对象数目, k 是聚类数是聚类数基于抽样的方法基于抽样的方法, CLARA(Clustering LARge Appl

17、ications)2022-6-26CLARA (Clustering Large Applications) (1990)nCLARA (Kaufmann and Rousseeuw in 1990)n不考虑整个数据集不考虑整个数据集, 而是选择数据的一小部分作为样本而是选择数据的一小部分作为样本n它从数据集中抽取多个样本集它从数据集中抽取多个样本集, 对每个样本集使用对每个样本集使用PAM, 并并以最好的聚类作为输出以最好的聚类作为输出n优点优点: 可以处理的数据集比可以处理的数据集比 PAM大大n缺点缺点:n有效性依赖于样本集的大小有效性依赖于样本集的大小n基于样本的好的聚类并不一定是基

18、于样本的好的聚类并不一定是 整个数据集的好的聚类整个数据集的好的聚类, 样本可能发生倾斜样本可能发生倾斜n 例如例如, Oi是最佳的是最佳的k个中心点之一个中心点之一, 但它不包含在样本中但它不包含在样本中, CLARA将找不到将找不到最佳聚类最佳聚类2022-6-26CLARA - 效率n由取样大小决定nPAM 利用完整资料集CLARA 利用取样资料集盲点：取样范围不包含最佳解 sampledbestTrade-off232022-6-26CLARA 改良n解決：CLARANS (Clustering Large Application based upon RANdomized Searc

19、h)n应用 graphn考虑紧邻节点n不局限于区域性n复杂度：O(n2) 缺点242022-6-26nCLARA的有效性主要取决于样本的大小。如果任何一个最佳抽样中心点不在最佳的K个中心之中，则CLARA将永远不能找到数据集合的最佳聚类。同时这也是为了聚类效率做付出的代价。 n CLARANS聚类则是将CLARA和PAM有效的结合起来，CLARANS在任何时候都不把自身局限于任何样本，CLARANS在搜素的每一步都以某种随机性选取样本。算法步骤如下 CLARANS (“Randomized” CLARA) (1994)2022-6-26CLARANS (“Randomized” CLARA)

20、(1994)nCLARANS (A Clustering Algorithm based on Randomized Search) (Ng and Han94)nCLARANS将采样技术和将采样技术和PAM结合起来结合起来nCLARA在搜索的每个阶段有一个固定的样本在搜索的每个阶段有一个固定的样本nCLARANS任何时候都不局限于固定样本任何时候都不局限于固定样本, 而是在搜索的每一步带一而是在搜索的每一步带一定随机性地抽取一个样本定随机性地抽取一个样本 n聚类过程可以被描述为聚类过程可以被描述为对一个图的搜索对一个图的搜索, 图中的每个节点图中的每个节点是一个潜在的解是一个潜在的解, 也就

21、是说也就是说 k -medoidsn相邻节点：代表的集合只有一个对象不同相邻节点：代表的集合只有一个对象不同n在替换了一个代表对象后得到的聚类结果被称为当前聚类在替换了一个代表对象后得到的聚类结果被称为当前聚类结果的邻居结果的邻居 2022-6-26CLARANS(续续)n如果一个更好的邻居被发现如果一个更好的邻居被发现, CLARANS移到该邻居节点移到该邻居节点, 处处理过程重新开始理过程重新开始, 否则当前的聚类达到了一个局部最优否则当前的聚类达到了一个局部最优n如果找到了一个局部最优如果找到了一个局部最优, CLARANS从随机选择的节点开从随机选择的节点开始寻找新的局部最优始寻找新的

22、局部最优n实验显示实验显示CLARANS比比PAM和和CLARA更有效更有效 nCLARANS能够探测孤立点能够探测孤立点 n聚焦技术和空间存取结构可以进一步改进它的性能聚焦技术和空间存取结构可以进一步改进它的性能 (Ester et al.95)2022-6-26n1、输入参数numlocal和maxneighbor。numlocal 表示抽样的次数， maxneighbor 表示一个节点可以与任意特定邻居进行比较的数目。 令：i=1，i用来表示已经选样的次数 mincost为最小代价，初始时设为大数。 n2、设置当前节点current为Gn中的任意一个节点。 n3、令j =1。（j用来表示

23、已经与current进行比较的邻居的个数） n4、考虑当前点的一个随机的邻居S，并计算两个节点的代价差。n5、如果S的代价较低，则current:=S，转到步骤3。 n6、否则，令j=j+1。如果jmaxneighbor，当前节点为本次选样最小代价节点. 如果其代价小于mincost,令mincost为当前节点的代价，bestnode为当前的节点。 n8、令 i= i+1，如果inumlocal,输出bestnode，运算中止.否则，转到步骤2。 CLARANS (“Randomized” CLARA) (1994)2022-6-26n1）代价值，主要描述一个对象被分到一个类别中的代价值，该代

24、价值由每个对象与其簇中心点间的相异度（距离或者相似度）的总和来定义。代价差则是两次随机领域的代价差值。 n （2）更新邻接点，CLARANS不会把搜索限制在局部区域，如果发现一个更好的近邻，CLARANS就移到该近邻节点，处理过程从新开始；否则，当前的聚类则产生了一个局部最小。如果找到一个局部最小，CLARANS从随机选择的新节点开始，搜索新的局部最小。当搜索的局部最小解达到用户指定的数目时，最好的局部最小作为算法的输出。从上面的算法步骤也可以看出这一思想。在第5步中更新节点current。CLARANS (“Randomized” CLARA) (1994)2022-6-26综合比较K meansK medoidsCLARACLARANS优点优点简单简单不受不受极值影响极值影响可可处理大数据处理大数据找到最佳解找到最佳解缺缺点点受极值影响受极值影响无法处理大数据无法处理大数据不一定不一定是是最佳解最佳解速度慢速度慢复杂复杂度度O(nkt)O(k(n-k)2)O(ks2+k(n-k)O(n2)精確度精確度速度速度302022-6-26作业作业n编程实现编程实现K-means算法针对算法针对UCI的的waveform数数据集中每类数据取据集中每类数据取100个；对一副无噪图像进行个；对一副无