模式识别与人工智能之五PPT教案.pptx

《模式识别与人工智能之五PPT教案.pptx》由会员分享，可在线阅读，更多相关《模式识别与人工智能之五PPT教案.pptx（52页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、模式识别模式识别(m sh sh bi)与人工智能之与人工智能之五五第一页，共52页。聚类的定义聚类的定义聚类算法聚类算法(sun f)(sun f)分类分类典型聚类算法典型聚类算法(sun f)(sun f)讲解讲解第1页/共52页第二页，共52页。聚类的定义聚类的定义(dngy)(dngy)典型的非监督(jind)式机器学习数据类别不被事先标识通过学习模型推断出数据的一些内在结构，进而进行聚类。第3页/共52页第四页，共52页。聚类算法聚类算法(sun f)(sun f)分类分类第4页/共52页第五页，共52页。聚类算法聚类算法(sun(sun f)f)分类分类划分方法：首先得到初始的划分

2、方法：首先得到初始的K个划分的集合。如个划分的集合。如K-平均、平均、K-中心点、中心点、CLARANS以及对它们的改进。以及对它们的改进。层次方法：创建给定数据对象集合的一个层次性的分解。根据层次分解层次方法：创建给定数据对象集合的一个层次性的分解。根据层次分解的过程的过程(guchng)可以分为凝聚（自底向上）或分裂（自顶向下）。可以分为凝聚（自底向上）或分裂（自顶向下）。基于密度的方法：根据密度的概念来聚类对象，如基于密度的方法：根据密度的概念来聚类对象，如DBSCAN、DENCLUE、OPTICS。第5页/共52页第六页，共52页。聚类算法聚类算法(sun(sun f)f)分类分类基于

3、网格的方法：首先将对象空间量化为有限数目基于网格的方法：首先将对象空间量化为有限数目(shm)的单元，形成网格结构，然后在网格结构上进行聚类，如的单元，形成网格结构，然后在网格结构上进行聚类，如STING、CLIQUE、WaveCluster。基于模型的方法：为每个簇假设一个模型，发现数据对模型基于模型的方法：为每个簇假设一个模型，发现数据对模型的最好匹配，如的最好匹配，如COBWEB、CLASSIT，GCM,AutoClass,SOM。基于降维的方法：如基于降维的方法：如Spectral clustering，Ncut等等第6页/共52页第七页，共52页。聚类算法聚类算法(sun(sun f

4、)f)分类分类类别类别算法算法分裂/划分方法K-MEANS（K-平均）、K-MEDOIDS算法（K-中心点）、CLARANS算法（基于选择的方法）层次法BIRCH算法（平衡迭代规约和聚类）、CURE算法（代表聚类）、CHAMELEON算法（动态模型）基于密度的方法DBSCAN算法（基于高密度连接区域）、OPTICS算法（对象排序识别）、DENCURE算法（密度分布函数）基于网格的方法STING算法（统计信息网格）、CLIQUE算法（聚类高维空间）、WAVE-CLUSTER算法（小波变换）基于模型的方法统计学方法、神经网络方法基于降维的方法Spectral clusteringSpectral

5、clustering，NcutNcut第7页/共52页第八页，共52页。典型聚类算法讲解典型聚类算法讲解 -基于划分的聚类算法基于划分的聚类算法第8页/共52页第九页，共52页。划分(hu fn)聚类法 K-meansSummary：k-means是采用均值算法把数据分成K个类的算法！Q1Q1：k k是什么？是什么？A1A1：k k是聚类算法当中类的个数。是聚类算法当中类的个数。Q2Q2：meansmeans是什么？是什么？A2A2：meansmeans是均值算法。是均值算法。第9页/共52页第十页，共52页。k-meansk-meansk-meansk-means算法，亦称算法，亦称算法，亦

6、称算法，亦称k-k-k-k-均值或均值或均值或均值或k-k-k-k-平均，是一种基于质心的启发平均，是一种基于质心的启发平均，是一种基于质心的启发平均，是一种基于质心的启发式聚类算法。式聚类算法。式聚类算法。式聚类算法。基本思想：通过迭代把数据集划分为不同的类别（或称簇），基本思想：通过迭代把数据集划分为不同的类别（或称簇），基本思想：通过迭代把数据集划分为不同的类别（或称簇），基本思想：通过迭代把数据集划分为不同的类别（或称簇），使得评价聚类性能的准则函数达到最优，使得每个聚类类内紧使得评价聚类性能的准则函数达到最优，使得每个聚类类内紧使得评价聚类性能的准则函数达到最优，使得每个聚类类内紧使

7、得评价聚类性能的准则函数达到最优，使得每个聚类类内紧凑，类间独立。凑，类间独立。凑，类间独立。凑，类间独立。对于连续型属性对于连续型属性对于连续型属性对于连续型属性(shxng)(shxng)(shxng)(shxng)具有较好的聚类效果，不适合处理具有较好的聚类效果，不适合处理具有较好的聚类效果，不适合处理具有较好的聚类效果，不适合处理离散型属性离散型属性离散型属性离散型属性(shxng)(shxng)(shxng)(shxng)。划分(hu fn)聚类法 K-means算法算法(sun f)概述概述第10页/共52页第十一页，共52页。平方误差和准则函数 即SSE（sum of the s

8、quared error）SSE是数据库中所有对象的平方误差总和(zngh)，其中 为数据对象；为簇 的平均值。这个准则函数使得生成的簇尽可能的紧凑和独立。划分(hu fn)聚类法 K-means准则准则(zhnz)函数函数第11页/共52页第十二页，共52页。1.随机抽取k个点作为初始聚类的中心，由各中心代表各聚类2.计算所有点到这k个中心的距离，并将点归到离其最近的聚类3.调整聚类中心，即将聚类的中心移动到聚类的几何中心（即平均值）4.重复第2、3步直到聚类的中心不再移动，此时算法收敛划分(hu fn)聚类法 K-means算法算法(sun f)流程流程第12页/共52页第十三页，共52页

9、。迭代计算迭代计算中心点中心点收敛！收敛！选择初始中心点选择初始中心点各点划分进最近聚类各点划分进最近聚类调整聚类中心调整聚类中心划分(hu fn)聚类法 K-meansSimple Example第13页/共52页第十四页，共52页。Step 1从数据集中任意选择从数据集中任意选择k k个对象个对象C C1 1,C,C2 2,C,Ck k作为作为初始的簇中心；初始的簇中心；Step2把每个对象分配到与之最相似的聚合。每个把每个对象分配到与之最相似的聚合。每个聚合用其中所有对象的均值来代表，聚合用其中所有对象的均值来代表，“最相最相似似”就是指距离最小。对于每个点就是指距离最小。对于每个点V

10、Vi i，找出，找出一个质心一个质心C Cj j，使它们之间的距离，使它们之间的距离d(d(V Vi i,C Cj j)最小，最小，并把并把V Vi i分到第分到第j j组。组。Step3把所有的点分配到相应的簇之后，重新计算每个组的质把所有的点分配到相应的簇之后，重新计算每个组的质心心C Cj j 。Step4Step4循环执行循环执行Step2Step2和和step3step3，直到数据的划分不再发生变化，直到数据的划分不再发生变化划分(hu fn)聚类法 K-means算法实现算法实现(shxin)的具体流程的具体流程第14页/共52页第十五页，共52页。初始初始中心点中心点输入数据输入

11、数据及及k k值的值的选择选择距离距离度量度量FactorsFactors影响影响(yngxing)(yngxing)聚类聚类效果！效果！一般采用欧氏距离、曼哈顿距离或者(huzh)名考斯距离的一种，作为样本间的相似性度量划分(hu fn)聚类法 K-means算法特点：影响主要因素算法特点：影响主要因素第15页/共52页第十六页，共52页。划分(hu fn)聚类法 K-means不足：不足：k-means算法只有在簇的平均值被定义的情况下才能使用。算法只有在簇的平均值被定义的情况下才能使用。k-means算法的不足之处在于它要多次扫描数据库。算法的不足之处在于它要多次扫描数据库。k-mean

12、s算法只能找出球形的类，而不能发现任意形状的类。算法只能找出球形的类，而不能发现任意形状的类。初始质心的选择对聚类结果有较大的影响。初始质心的选择对聚类结果有较大的影响。k-means算法对于噪声和孤立点数据是敏感的，少量算法对于噪声和孤立点数据是敏感的，少量(sholing)的该类数据能够对平均值产生极大的影响。的该类数据能够对平均值产生极大的影响。第16页/共52页第十七页，共52页。问题描述：如图所示，一只遥望大海的小狗。此图为100100像素(xin s)的JPG图片，每个像素(xin s)可以表示为三维向量（分别对应红绿蓝三基色）。要求使用k-means算法，将图片分割为合适的背景区

13、域（三个）和前景区域（小狗）。划分(hu fn)聚类法 K-means应用应用(yngyng)实例实例第17页/共52页第十八页，共52页。MatlabMatlab程序实现程序实现程序实现程序实现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,:)=m

14、ean(X(find(j=k),:);end end划分(hu fn)聚类法 K-means第18页/共52页第十九页，共52页。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;endMatlabMatlab程序实现（续）程序实现（续）程序实现（续）程序实现（续）划分(hu fn)聚类法 K-means第19页/共52页第二十页，共52页。close all;clear all;clc;C_Segments=5;img_original=imread(dog.

15、png);%读入图像读入图像figure,imshow(img_original),title(原始图像原始图像);%显示原图像显示原图像m,n,depth=size(img_original);%获取图像的长宽获取图像的长宽%将图像进行将图像进行RGB3通道分解通道分解%将将RGB分量各转为分量各转为kmeans使用的数据格式使用的数据格式n行，一样本行，一样本A=reshape(img_original(:,:,1),m*n,1);B=reshape(img_original(:,:,2),m*n,1);C=reshape(img_original(:,:,3),m*n,1);dat=A

16、B C;%r g b分量组成分量组成(z chn)样本的特征，每个样本有三个属性样本的特征，每个样本有三个属性值，共值，共width*height个样本个样本cRGB=kmeans(double(dat),C_Segments,20);rRGB=reshape(cRGB,m,n);%反向转化为图片形式反向转化为图片形式figure,imshow(label2rgb(rRGB),),title(分类结果分类结果);%显示分割结果显示分割结果划分(hu fn)聚类法 K-means第20页/共52页第二十一页，共52页。分割分割(fng)(fng)后的效果后的效果应用应用(yngyng)实例实例划

17、分(hu fn)聚类法 K-means第21页/共52页第二十二页，共52页。划分(hu fn)聚类法 K-means应用应用(yngyng)实例实例注：聚类中心(zhngxn)个数为5，最大迭代次数为10。第22页/共52页第二十三页，共52页。思路思路思路思路将聚将聚将聚将聚类问题类问题中的中的中的中的类类定定定定义为义为模糊集合模糊集合模糊集合模糊集合(jh)(jh)，用模糊集的，用模糊集的，用模糊集的，用模糊集的隶属度函数定量描述隶属度函数定量描述隶属度函数定量描述隶属度函数定量描述样样本点与本点与本点与本点与类类之之之之间间的从属关系，并通的从属关系，并通的从属关系，并通的从属关系，

18、并通过寻过寻找使目找使目找使目找使目标标函数最小化的隶属度函数，函数最小化的隶属度函数，函数最小化的隶属度函数，函数最小化的隶属度函数，实现实现聚聚聚聚类类。算法关算法关算法关算法关键键点点点点隶属度函数的数学定隶属度函数的数学定隶属度函数的数学定隶属度函数的数学定义义模糊模糊模糊模糊类类中心的更新中心的更新中心的更新中心的更新划分聚类法 模糊(m hu)C均值聚类 fuzzy c-means第23页/共52页第二十四页，共52页。变变量定量定量定量定义义数据集数据集数据集数据集X=x1,x2,xnX=x1,x2,xnc c个模糊个模糊个模糊个模糊(m hu)(m hu)类类样样本本本本xkx

19、k对对第第第第i i类类的模糊的模糊的模糊的模糊(m hu)(m hu)隶属度隶属度隶属度隶属度为为uikuik，满满足条件足条件足条件足条件隶属度矩隶属度矩隶属度矩隶属度矩阵阵U=uik U=uik 第第第第i i类类的的的的类类中心中心中心中心为为vivi聚聚聚聚类类中心矩中心矩中心矩中心矩阵为阵为V=v1,v2,vcV=v1,v2,vc建立基于隶属度矩建立基于隶属度矩建立基于隶属度矩建立基于隶属度矩阵阵U U和聚和聚和聚和聚类类中心矩中心矩中心矩中心矩阵阵V V的目的目的目的目标标函数函数函数函数Jm(U,V)Jm(U,V)划分(hu fn)聚类法 模糊C均值聚类 fuzzy c mea

20、ns第24页/共52页第二十五页，共52页。目目目目标标函数函数函数函数(hnsh)(hnsh)最小化求解最小化求解最小化求解最小化求解划分聚类法 模糊(m hu)C均值聚类 fuzzy c means这里这里m1,是隶属度的加权指数是隶属度的加权指数;为第为第i个聚类中心与第个聚类中心与第k个数据个数据(shj)样本之间的欧几里得距离样本之间的欧几里得距离;限定条件：限定条件：最小化上述函数可以用拉格朗日乘子法求解最小化上述函数可以用拉格朗日乘子法求解第25页/共52页第二十六页，共52页。目目目目标标函数最小化求解函数最小化求解函数最小化求解函数最小化求解(qi ji)(qi ji)对对上

21、式上式上式上式进进行求行求行求行求导导，使其达到最小的必要条件，使其达到最小的必要条件，使其达到最小的必要条件，使其达到最小的必要条件为为：划分聚类法 模糊(m hu)C均值聚类 fuzzy c means公式公式(gngsh)（1）公式（公式（2）第26页/共52页第二十七页，共52页。模糊模糊模糊模糊C C均均均均值值(jn zh)(jn zh)聚聚聚聚类类算法具体步算法具体步算法具体步算法具体步骤骤划分(hu fn)聚类法 模糊C均值聚类 fuzzy c-means(FCM)1.确定聚类类别数目确定聚类类别数目c、加权指标、加权指标m，用，用01的的随机值初始化隶属矩阵随机值初始化隶属矩

22、阵U(0)，并满足，并满足2.令迭代次数为令迭代次数为b，b=0,1,2bmax3.根据公式（根据公式（2）计算各个类的中心）计算各个类的中心Vi(b);4.根据公式（根据公式（1）更新）更新U(b)为为U(b+1)；5.比较比较U(b)和和U(b+1)之间的差别，如果之间的差别，如果 或者迭代达到最大次数，则聚类结束；否或者迭代达到最大次数，则聚类结束；否则，置则，置b=b+1并返回第并返回第3步。步。第27页/共52页第二十八页，共52页。划分聚类法 模糊(m hu)C均值聚类 fuzzy c meansMATLAB中提供了FCM函数：center,U,obj_fcn=fcm(data,c

23、luster_n,options);%输入：%data -nxm矩阵(j zhn),表示n个样本,每个样本具有m的维特征值%N_cluster -标量,表示聚合中心数目,即类别数%options -4x1矩阵(j zhn)，其中%options(1):隶属度矩阵(j zhn)U的指数，1 (缺省值:2.0)%options(2):最大迭代次数 (缺省值:100)%options(3):隶属度最小变化量,迭代终止条件 (缺省值:1e-5)%options(4):每次迭代是否输出信息标志 (缺省值:1)%输出：%center -聚类中心%U -隶属度矩阵(j zhn)%obj_fcn -目标函数值

24、第28页/共52页第二十九页，共52页。划分(hu fn)聚类法 模糊C均值聚类 fuzzy c means应用应用(yngyng)实例实例close all;clear all;clc;C_Segments=4;img_original=imread(pepper.png);%读入图像读入图像figure,imshow(img_original),title(原始图像原始图像);%显示原图像显示原图像m,n,p=size(img_original);%获取图像的长宽获取图像的长宽%将图像进行将图像进行RGB3通道分解通道分解%将将RGB分量各转为分量各转为kmeans使用使用(shyng)的

25、数据格式的数据格式n行，一样行，一样本本A=reshape(img_original(:,:,1),m*n,1);B=reshape(img_original(:,:,2),m*n,1);C=reshape(img_original(:,:,3),m*n,1);dat=A B C;%r g b分量组成样本的特征，每个样本有三个属性分量组成样本的特征，每个样本有三个属性值，共值，共width*height个样本个样本第29页/共52页第三十页，共52页。聚类法 模糊(m hu)C均值聚类 fuzzy c means应用应用(yngyng)实例实例center,U,fct=fcm(double(d

26、at),C_Segments);,label=max(U,1);figure;LAB=reshape(label,m,n);imshow(LAB,)figure;map=0 0 0;center(1,1)/255,center(1,2)/255,center(1,3)/255;imshow(LAB=1),colormap(map)figure;map=0 0 0;center(2,1)/255,center(2,2)/255,center(2,3)/255;imshow(LAB=2),colormap(map)figure;map=0 0 0;center(3,1)/255,center(3,

27、2)/255,center(3,3)/255;imshow(LAB=3),colormap(map)figure;map=0 0 0;center(4,1)/255,center(4,2)/255,center(4,3)/255;imshow(LAB=4),colormap(map)第30页/共52页第三十一页，共52页。聚类法 模糊(m hu)C均值聚类 fuzzy c means应用应用(yngyng)实例实例分割(fng)结果第31页/共52页第三十二页，共52页。划分(hu fn)聚类法 K-medoidsk-中心点中心点(k-Medoids):不采用簇中不采用簇中对对象的平均象的平均

28、值值作作为为参参照点照点,而是而是选选用簇用簇中位置中位置(wi zhi)最中心的最中心的对对象象,即中心点即中心点(medoid)作作为为参参照点照点.012345678910012345678910012345678910012345678910012345678910012345678910第32页/共52页第三十三页，共52页。划分(hu fn)聚类法 K-medoids基本思想基本思想:找聚类中的代表对象找聚类中的代表对象(中心点中心点)PAM(Partitioning Around Medoids)首先为每个簇随意选择一个代表对象首先为每个簇随意选择一个代表对象,剩余的对象根剩余的

29、对象根据其与代表对象的距离分配给最近的一个簇据其与代表对象的距离分配给最近的一个簇;然后反然后反复地用非代表对象来替代代表对象，以改进聚类的复地用非代表对象来替代代表对象，以改进聚类的质量质量 PAM 对于较小的数据集非常有效对于较小的数据集非常有效(yuxio),但不能但不能很好地扩展到大型数据集。很好地扩展到大型数据集。第33页/共52页第三十四页，共52页。划分(hu fn)聚类法 K-medoids为了判定一个非代表对象为了判定一个非代表对象Orandom 是否是当前一个代表对象是否是当前一个代表对象Oj的好的的好的替代替代,对于每一个非代表对象对于每一个非代表对象p,考虑下面的四种情

30、况：考虑下面的四种情况：第一种情况：第一种情况：p当前隶属于代表对象当前隶属于代表对象 Oj.如果如果(rgu)Oj被被Orandom所代所代替替,且且p离离Oi最近最近,ij,那么那么p被重新分配给被重新分配给Oi 第二种情况：第二种情况：p当前隶属于代表对象当前隶属于代表对象 Oj.如果如果(rgu)Oj 被被Orandom代代替替,且且p离离Orandom最近最近,那么那么p被重新分配给被重新分配给Orandom 第34页/共52页第三十五页，共52页。划分(hu fn)聚类法 K-medoids第三种情况第三种情况第三种情况第三种情况(qngkung)(qngkung)：p p当前隶属

31、于当前隶属于当前隶属于当前隶属于OiOi，ijij。如果。如果。如果。如果OjOj被被被被OrandomOrandom代替，而代替，而代替，而代替，而p p仍然离仍然离仍然离仍然离OiOi最近，那么对象的隶属不发生变最近，那么对象的隶属不发生变最近，那么对象的隶属不发生变最近，那么对象的隶属不发生变化化化化 第四种情况第四种情况第四种情况第四种情况(qngkung)(qngkung)：p p当前隶属于当前隶属于当前隶属于当前隶属于OiOi，ijij。如果。如果。如果。如果OjOj被被被被OrandomOrandom代替，且代替，且代替，且代替，且p p离离离离OrandomOrandom最近，

32、那么最近，那么最近，那么最近，那么p p被重新分配给被重新分配给被重新分配给被重新分配给Orandom Orandom 第35页/共52页第三十六页，共52页。划分(hu fn)聚类法 K-medoids算法算法算法算法:k-:k-中心点中心点中心点中心点(1)(1)随机选择随机选择随机选择随机选择k k个对象作为初始的代表个对象作为初始的代表个对象作为初始的代表个对象作为初始的代表(dibio)(dibio)对象；对象；对象；对象；(2)repeat(2)repeat(3)(3)指指指指派派派派每每每每个个个个剩剩剩剩余余余余的的的的对对对对象象象象给给给给离离离离它它它它最最最最近近近近的

33、的的的代代代代表表表表(dibio)(dibio)对象所代表对象所代表对象所代表对象所代表(dibio)(dibio)的簇；的簇；的簇；的簇；(4)(4)随意地选择一个非代表随意地选择一个非代表随意地选择一个非代表随意地选择一个非代表(dibio)(dibio)对象对象对象对象OrandomOrandom；(5)(5)计计计计算算算算用用用用OrandomOrandom代代代代替替替替OjOj的的的的总总总总距距距距离离离离E,E,如如如如果果果果E E比比比比取取取取代代代代前前前前下下下下降降降降则则则则则则则则用用用用OrandomOrandom替替替替 换换换换OjOj，形形形形成成成

34、成新新新新的的的的k k个个个个代代代代表表表表(dibio)(dibio)对对对对象的集合，返回（象的集合，返回（象的集合，返回（象的集合，返回（4 4）；）；）；）；(6)until(6)until 不发生变化不发生变化不发生变化不发生变化(7)(7)如如如如果果果果所所所所有有有有非非非非代代代代表表表表(dibio)(dibio)对对对对象象象象都都都都无无无无法法法法取取取取代代代代已已已已存存存存在在在在的的的的簇簇簇簇中中中中心心心心，则结束替代过程，并输出结果则结束替代过程，并输出结果则结束替代过程，并输出结果则结束替代过程，并输出结果第36页/共52页第三十七页，共52页。划

35、分(hu fn)聚类法 K-medoids012345678910012345678910K=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

36、pUntil no change012345678910012345678910第37页/共52页第三十八页，共52页。划分(hu fn)聚类法 K-medoids当存在噪音和孤立当存在噪音和孤立(gl)点时点时,PAM 比比 k-平均方法更健壮平均方法更健壮.这是这是因为中心点不象平均值那么容易因为中心点不象平均值那么容易被极端数据影响被极端数据影响 PAM对于小数据集工作得很好对于小数据集工作得很好,但不能很好地用于大数据集但不能很好地用于大数据集 每次迭代每次迭代O(k(n-k)2)其中其中 n 是数据对象数目是数据对象数目,k 是聚类数是聚类数第38页/共52页第三十九页，共52页。C

37、LARA(Clustering LARge Applications)Improvement over PAMFinds medoids in a sample from the datasetIdea:If the samples are sufficiently random,the medoids of the sample approximate the medoids of the datasetHeuristics:5 samples of size 40+2k gives satisfactory resultsWorks well for large datasets(n=10

38、00,k=10)划分(hu fn)聚类法 K-medoids第39页/共52页第四十页，共52页。CLARA(Clustering LARge Applications)划分(hu fn)聚类法 K-medoidsDraw multiple samples of the datasetSample should be able to represent the datasetApply PAM to each sampleReturn the best clustering第40页/共52页第四十一页，共52页。uSet mincost to MAXIMUM;uRepeat q times/d

39、raws q sampleslCreate S by drawing s objects randomly from D;lGenerate the set of medoids M from S by applying the PAM algorithm;lCompute cost(M,D)lIf cost(M,D)mincost Mincost=cost(M,D);Bestset=M;lEnd if;uEnd repeat;uReturn Bestset;Algorithms:CLARA(Clustering LARge Applications)划分(hu fn)聚类法 K-medoid

40、s第41页/共52页第四十二页，共52页。us:the size of the sampleuk:number of clustersun:number of objectsComplexity of each iteration is:O(ks2+k(n-k)CLARA(Clustering LARge Applications)划分(hu fn)聚类法 K-medoidsPAM find the best K medoids from a given dataset;CLARA finds the best kMedoids from several selected samples.Pr

41、oblems:The best k-medoids may not be selected during the sampling Process,in this case,CLARA will never find the best clusteringIf the sampling is biased,we can not have a good clustering.Trade off-of efficiency.第42页/共52页第四十三页，共52页。CLARANS(Clustering Large Applications based on Randomized Search)划分(

42、hu fn)聚类法 K-medoidsIt was proposed to improve the quality and scalability of CLARAIt combines sampling techniques with PAMIt does not confine itself to any sample at a given timeIt draws a sample with some randomness in each step of the search第43页/共52页第四十四页，共52页。CLARANS draws sample in solution spac

43、e dynamicallyA solution is a set of k medoidsThe solutions space contains Cnk solutions in totalThe solution space can be represented by a graph where every node is a potential solution,i.e.,a set of k medoidsCLARANS 划分(hu fn)聚类法 K-medoids第44页/共52页第四十五页，共52页。Every node is a potential solution(k-medo

44、id)Every node is associated with a squared errorTwo nodes are adjacent if they differ by one medoidEvery node has k(n k)adjacent nodesO1,O2,OkOk+1,O2,OkOk+n,O2,Okn-k neighbors for one medoidk(n k)neighbors for one node 划分(hu fn)聚类法 K-medoids:CLARANS第45页/共52页第四十六页，共52页。Start with a randomly selected

45、node,check at most m neighbors randomlyIf a better adjacent node is found,moves to node and continue;otherwise,current node is local optimum;re-starts with another randomly selected node to search for another local optimumWhen h local optimum have been found,returns best result as overall result划分(h

46、u fn)聚类法 K-medoids:CLARANS第46页/共52页第四十七页，共52页。NNNCCNNNLocal minimumCompare no more than maxneighbor timesnumlocalBest NodeLocal minimumLocal minimumLocal minimum划分(hu fn)聚类法 K-medoids:CLARANS第47页/共52页第四十八页，共52页。Algorithms:Set mincost to MAXIMUM;For i=1 to h do /find h local optimumRandomly select a

47、node as the current node C in the graph;J=1;/counter of neighborsRepeatRandomly select a neighbor N of C;If Cost(N,D)mUpdate mincost with Cost(C,D)if applicable End for;End ForReturn bestnode;划分(hu fn)聚类法 K-medoids:CLARANS第48页/共52页第四十九页，共52页。Algorithms:第49页/共52页第五十页，共52页。Notes:Each vertex is a set o

48、f k-representative objects(means,modes,medoids)Each iteration produces a new set of k-representative objects with lower overall dissimilarityIterations correspond to a hill descent process in a landscape(graph)of vertices划分(hu fn)聚类法 K-medoids:CLARANSAdvantages:CLARANS is more effective than both PA

49、M and CLARAHandles outliersDisadvantages:Computational complexity of CLARANS is O(N2).The clustering quality depends on the sampling method第50页/共52页第五十一页，共52页。小小 结结掌握划分聚类算法掌握划分聚类算法(sun f)的基本思想和局限性的基本思想和局限性掌握常用的划分聚类的思想和优缺点以及适用范围掌握常用的划分聚类的思想和优缺点以及适用范围 k-means,FCM,k-medoids(PAM,CLARA,CLARANS)能够利用代码实现上述方法，并且结合实际应用设计相应的输能够利用代码实现上述方法，并且结合实际应用设计相应的输入输出入输出第51页/共52页第五十二页，共52页。