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

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

1、聚类的定义聚类的定义聚类算法分类聚类算法分类典型聚类算法讲解典型聚类算法讲解第1页/共52页聚类的定义聚类的定义典型的非监督式机器学习数据类别不被事先标识通过学习模型推断出数据的一些内在结构，进而进行聚类。第3页/共52页聚类算法分类聚类算法分类第4页/共52页聚类算法分类聚类算法分类划分方法：首先得到初始的K个划分的集合。如K-平均、K-中心点、CLARANS以及对它们的改进。层次方法：创建给定数据对象集合的一个层次性的分解。根据层次分解的过程可以分为凝聚（自底向上）或分裂（自顶向下）。基于密度的方法：根据密度的概念来聚类对象，如DBSCAN、DENCLUE、OPTICS。第5页/共52页聚

2、类算法分类聚类算法分类基于网格的方法：首先将对象空间量化为有限数目的单元，形成网格结构，然后在网格结构上进行聚类，如STING、CLIQUE、WaveCluster。基于模型的方法：为每个簇假设一个模型，发现数据对模型的最好匹配，如COBWEB、CLASSIT，GCM,AutoClass,SOM。基于降维的方法：如Spectral clustering，Ncut等第6页/共52页聚类算法分类聚类算法分类类别类别算法算法分裂/划分方法K-MEANS（K-平均）、K-MEDOIDS算法（K-中心点）、CLARANS算法（基于选择的方法）层次法BIRCH算法（平衡迭代规约和聚类）、CURE算法（代表

3、聚类）、CHAMELEON算法（动态模型）基于密度的方法DBSCAN算法（基于高密度连接区域）、OPTICS算法（对象排序识别）、DENCURE算法（密度分布函数）基于网格的方法STING算法（统计信息网格）、CLIQUE算法（聚类高维空间）、WAVE-CLUSTER算法（小波变换）基于模型的方法统计学方法、神经网络方法基于降维的方法Spectral clustering，Ncut第7页/共52页典型聚类算法讲解 -基于划分的聚类算法第8页/共52页划分聚类法 K-meansSummary：k-means是采用均值算法把数据分成K个类的算法！Q1Q1：k k是什么？是什么？A1A1：k k是聚

4、类算法当中类的个数。是聚类算法当中类的个数。Q2Q2：meansmeans是什么？是什么？A2A2：meansmeans是均值算法。是均值算法。第9页/共52页k-meansk-means算法，亦称k-均值或k-平均，是一种基于质心的启发式聚类算法。基本思想：通过迭代把数据集划分为不同的类别（或称簇），使得评价聚类性能的准则函数评价聚类性能的准则函数达到最优，使得每个聚类类内紧凑，类间独立。对于连续型属性具有较好的聚类效果，不适合处理离散型属性。划分聚类法 K-means算法概述第10页/共52页 平方误差和准则函数平方误差和准则函数 即SSE（sum of the squared error

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

6、meansSimple Example第13页/共52页Step 1从数据集中任意选择从数据集中任意选择k k个对象个对象C C1 1,C,C2 2,C,Ck k作为初始的簇中心；作为初始的簇中心；Step2把每个对象分配到与之最相似的聚合。每个聚合用其中所把每个对象分配到与之最相似的聚合。每个聚合用其中所有对象的均值来代表，有对象的均值来代表，“最相似最相似”就是指距离最小。对于就是指距离最小。对于每个点每个点V Vi i，找出一个质心，找出一个质心C Cj j，使它们之间的距离，使它们之间的距离d(d(V Vi i,C Cj j)最小，最小，并把并把V Vi i分到第分到第j j组。组。S

7、tep3把所有的点分配到相应的簇之后，重新计算每个组把所有的点分配到相应的簇之后，重新计算每个组的质心的质心C Cj j 。Step4Step4循环执行循环执行Step2Step2和和step3step3，直到数据的划分不再发生变化，直到数据的划分不再发生变化划分聚类法 K-means算法实现的具体流程第14页/共52页初始初始中心点中心点输入数据输入数据及及k k值的值的选择选择距离距离度量度量Factors影响聚类影响聚类效果！效果！一般采用欧氏距离、曼哈顿距离或者名考斯距离的一种，作为样本间的相似性度量划分聚类法 K-means算法特点：影响主要因素第15页/共52页划分聚类法 K-me

8、ans不足：k-means算法只有在簇的平均值被定义的情况下才能使用。k-means算法的不足之处在于它要多次扫描数据库。k-means算法只能找出球形的类，而不能发现任意形状的类。初始质心的选择对聚类结果有较大的影响。k-means算法对于噪声和孤立点数据是敏感的，少量的该类数据能够对平均值产生极大的影响。第16页/共52页问题描述：如图所示，一只遥望大海的小狗。此图为100100像素的JPG图片，每个像素可以表示为三维向量（分别对应红绿蓝三基色）。要求使用k-means算法，将图片分割为合适的背景区域（三个）和前景区域（小狗）。划分聚类法 K-means应用实例第17页/共52页Matla

9、b程序实现程序实现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划分聚类法 K-means第18页/共52页 Z=zeros(N,K);for m=1:N Z(m,j(m)=1;end e=

10、sum(sum(Z.*Dist)./N);fprintf(%d Error=%fn,n,e);Mo=M;endMatlab程序实现（续）程序实现（续）划分聚类法 K-means第19页/共52页close all;clear all;clc;C_Segments=5;img_original=imread(dog.png);%读入图像figure,imshow(img_original),title(原始图像);%显示原图像m,n,depth=size(img_original);%获取图像的长宽%将图像进行RGB3通道分解%将RGB分量各转为kmeans使用的数据格式n行，一样本A=resh

11、ape(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个样本cRGB=kmeans(double(dat),C_Segments,20);rRGB=reshape(cRGB,m,n);%反向转化为图片形式figure,imshow(label2rgb(rRGB),),title(分类结果);%显示分割结果划分聚类法 K-means第20页/共

12、52页分割后的效果分割后的效果应用实例划分聚类法 K-means第21页/共52页划分聚类法 K-means应用实例注：聚类中心个数为5，最大迭代次数为10。第22页/共52页思路思路将聚类问题中的类定定义为模糊集合模糊集合，用模糊集的隶属度函数定量描述样本点与类之间的从属关系，并通过寻找使目目标函数最小化函数最小化的隶属度函数，实现聚类。算法关算法关键点点隶属度函数的数学定义模糊类中心的更新划分聚类法 模糊C均值聚类 fuzzy c-means第23页/共52页变量定量定义数据集X=x1,x2,xnc个模糊类样本xk对第i类的模糊隶属度为uik，满足条件隶属度矩阵U=uik 第i类的类中心为

13、vi聚类中心矩阵为V=v1,v2,vc建立基于隶属度矩阵U和聚类中心矩阵V的目标函数Jm(U,V)划分聚类法 模糊C均值聚类 fuzzy c means第24页/共52页目目标函数最小化求解函数最小化求解划分聚类法 模糊C均值聚类 fuzzy c means这里m1,是隶属度的加权指数;为第i个聚类中心与第k个数据样本之间的欧几里得距离;限定条件：最小化上述函数可以用拉格朗日乘子法求解第25页/共52页目目标函数最小化求解函数最小化求解对上式上式进行求行求导，使其达到最小的必要条件，使其达到最小的必要条件为：划分聚类法 模糊C均值聚类 fuzzy c means公式（1）公式（2）第26页/共

14、52页模糊模糊C均均值聚聚类算法具体步算法具体步骤划分聚类法 模糊C均值聚类 fuzzy c-means(FCM)1.确定聚类类别数目c、加权指标m，用01的随机值初始化隶属矩阵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页划分聚类法 模糊C均值聚类 fuzzy c meansMATLAB中提供了FCM函数：center,U,obj_fcn=fcm(data,c

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

16、 fuzzy c means应用实例应用实例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使用的数据格式n行，一样本A=reshape(img_original(:,:,1),m*n,1);B=reshape(img_original(:,:,2),m*n,1);C=reshap

17、e(img_original(:,:,3),m*n,1);dat=A B C;%r g b分量组成样本的特征，每个样本有三个属性值，共width*height个样本第29页/共52页聚类法 模糊C均值聚类 fuzzy c means应用实例应用实例center,U,fct=fcm(double(dat),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

18、),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,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页

19、聚类法 模糊C均值聚类 fuzzy c means应用实例应用实例分割结果第31页/共52页划分聚类法 K-medoidsk-中心点(k-Medoids):不采用簇中对象的平均值作为参照点,而是选用簇中位置最中心的对象,即中心点(medoid)作为参照点.012345678910012345678910012345678910012345678910012345678910012345678910第32页/共52页划分聚类法 K-medoids基本思想:找聚类中的代表对象(中心点)PAM(Partitioning Around Medoids)首先为每个簇随意选择一个代表对象,剩余的对象根据其

20、与代表对象的距离分配给最近的一个簇;然后反复地用非代表对象来替代代表对象，以改进聚类的质量 PAM 对于较小的数据集非常有效,但不能很好地扩展到大型数据集。第33页/共52页划分聚类法 K-medoids为了判定一个非代表对象Orandom 是否是当前一个代表对象Oj的好的替代,对于每一个非代表对象p,考虑下面的四种情况：第一种情况：p当前隶属于代表对象 Oj.如果Oj被Orandom所代替,且p离Oi最近,ij,那么p被重新分配给Oi 第二种情况：p当前隶属于代表对象 Oj.如果Oj 被Orandom代替,且p离Orandom最近,那么p被重新分配给Orandom 第34页/共52页划分聚类

21、法 K-medoids第三种情况：第三种情况：p当前隶属于当前隶属于Oi，ij。如果如果Oj被被Orandom代替，而代替，而p仍然离仍然离Oi最近，那么对象的隶属不发生变化最近，那么对象的隶属不发生变化 第四种情况：第四种情况：p当前隶属于当前隶属于Oi，ij。如果如果Oj被被Orandom代替，且代替，且p离离Orandom最近，那么最近，那么p被重新分配给被重新分配给Orandom 第35页/共52页划分聚类法 K-medoids算法算法:k-中心点中心点(1)随机选择随机选择k个对象作为初始的代表对象；个对象作为初始的代表对象；(2)repeat(3)指派每个剩余的对象给离它最近的代表

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

23、10012345678910K=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 loopUntil no change012345678910012

24、345678910第37页/共52页划分聚类法 K-medoids当存在噪音和孤立点时当存在噪音和孤立点时,PAM 比比 k-平均方法更健壮平均方法更健壮.这这是因为中心点不象平均值那么容易被极端数据影响是因为中心点不象平均值那么容易被极端数据影响 PAM对于小数据集工作得很好对于小数据集工作得很好,但不能很好地用于大数但不能很好地用于大数据集据集 每次迭代每次迭代O(k(n-k)2)其中其中 n 是数据对象数目是数据对象数目,k 是聚类数是聚类数第38页/共52页CLARA(Clustering LARge Applications)Improvement over PAMFinds med

25、oids 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=1000,k=10)划分聚类法 K-medoids第39页/共52页CLARA(Clustering LARge Applicati

26、ons)划分聚类法 K-medoidsDraw multiple samples of the datasetSample should be able to represent the datasetApply PAM to each sampleReturn the best clustering第40页/共52页uSet mincost to MAXIMUM;uRepeat q times/draws q sampleslCreate S by drawing s objects randomly from D;lGenerate the set of medoids M from S

27、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)划分聚类法 K-medoids第41页/共52页us:the size of the sampleuk:number of clustersun:number of objectsComplexity of each iteration i

28、s:O(ks2+k(n-k)CLARA(Clustering LARge Applications)划分聚类法 K-medoidsPAM find the best K medoids from a given dataset;CLARA finds the best kMedoids from several selected samples.Problems:The best k-medoids may not be selected during the sampling Process,in this case,CLARA will never find the best cluste

29、ringIf the sampling is biased,we can not have a good clustering.Trade off-of efficiency.第42页/共52页CLARANS(Clustering Large Applications based on Randomized Search)划分聚类法 K-medoidsIt was proposed to improve the quality and scalability of CLARAIt combines sampling techniques with PAMIt does not confine

30、itself to any sample at a given timeIt draws a sample with some randomness in each step of the search第43页/共52页CLARANS draws sample in solution space dynamicallyA solution is a set of k medoidsThe solutions space contains Cnk solutions in totalThe solution space can be represented by a graph where ev

31、ery node is a potential solution,i.e.,a set of k medoidsCLARANS 划分聚类法 K-medoids第44页/共52页Every node is a potential solution(k-medoid)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 neigh

32、bors for one medoidk(n k)neighbors for one node 划分聚类法 K-medoids:CLARANS第45页/共52页Start with a randomly selected 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

33、 search for another local optimumWhen h local optimum have been found,returns best result as overall result划分聚类法 K-medoids:CLARANS第46页/共52页NNNCCNNNLocal minimumCompare no more than maxneighbor timesnumlocalBest NodeLocal minimumLocal minimumLocal minimum划分聚类法 K-medoids:CLARANS第47页/共52页Algorithms:Set

34、 mincost to MAXIMUM;For i=1 to h do /find h local optimumRandomly select a 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;划分聚类法 K-medoids:CLARANS第48页/共52页A

35、lgorithms:第49页/共52页Notes:Each vertex is a set of 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划分聚类法 K-medoids:CLARANSAdvantage

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