模式识别与人工智能之五课件

《模式识别与人工智能之五课件》由会员分享，可在线阅读，更多相关《模式识别与人工智能之五课件（53页珍藏版）》请在装配图网上搜索。

1、Click to edit Master title style,,Click to edit Master text styles,,Second level,,Third level,,Fourth level,,Fifth level,,*,,*,单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,*,,*,Pattern Recognition,&,artificial Intelligence,,L,ecture,,5:,聚类算法（一）,主要内容,聚类的定义,聚类算法分类,典型聚类算法讲解,,,聚类的定义,聚类的定义,典型的非监督式机器学习

2、,数据类别不被事先标识,通过学习模型推断出数据的一些内在结构，进而进行聚类。,,聚类算法分类,聚类算法分类,划分方法,：首先得到初始的,K,个划分的集合。如,K-,平均、,K-,中心点、,CLARANS,以及对它们的改进。,层次方法,：创建给定数据对象集合的一个层次性的分解。根据层次分解的过程可以分为凝聚（自底向上）或分裂（自顶向下）。,基于密度的方法,：根据密度的概念来聚类对象，如,DBSCAN,、,DENCLUE,、,OPTICS,。,聚类算法分类,基于网格的方法,：首先将对象空间量化为有限数目的单元，形成网格结构，然后在网格结构上进行聚类，如,STING,、,CLIQUE,、,WaveC

3、luster,。,基于模型的方法,：为每个簇假设一个模型，发现数据对模型的最好匹配，如,COBWEB,、,CLASSIT,，,GCM, AutoClass, SOM,。,基于降维的方法,：如,Spectral clustering,，,Ncut,等,,聚类算法分类,类别,算法,分裂,/,划分方法,K-MEANS,（,K-,平均）、,K-MEDOIDS,算法（,K-,中心点）、,CLARANS,算法（基于选择的方法）,层次法,BIRCH,算法（平衡迭代规约和聚类）、,CURE,算法（代表聚类）、,CHAMELEON,算法（动态模型）,基于密度的方法,DBSCAN,算法（基于高密度连接区域）、,O

4、PTICS,算法（对象排序识别）、,DENCURE,算法（密度分布函数）,基于网格的方法,STING,算法（统计信息网格）、,CLIQUE,算法（聚类高维空间）、,WAVE-CLUSTER,算法（小波变换）,基于模型的方法,统计学方法、神经网络方法,基于降维的方法,Spectral clustering,，,Ncut,,典型聚类算法讲解,,-----,基于划分的聚类算法,,划分聚类法,– K-means,,Summary,：,k-means,是采用均值算法把数据分成,K,个类的算法！,,Q1,：,k,是什么？,A1,：,k,是聚类算法当中类的个数。,,,Q2,：,means,是什么？,A2,：

5、,means,是均值算法。,,k-means,算法，亦称,k-,均值或,k-,平均，是一种基于质心的,启发式聚类算法,。,基本思想,：通过迭代把数据集划分为不同的类别（或称簇），使得,评价聚类性能的准则函数,达到最优，使得每个聚类类内紧凑，类间独立。,对于,连续型属性,具有较好的聚类效果，不适合处理离散型属性。,,划分聚类法,– K-means,算法概述,,平方误差和准则函数,,即,SSE,（,sum of the squared error,）,,,,,SSE,是数据库中所有对象的平方误差总和，其中,,为数据对象； 为簇 的平均值。,,这个准则函数使得生成的簇尽可能的紧凑和独立,。,

6、划分聚类法,– K-means,准则函数,,1.,随机抽取k个点作为初始聚类的中心，由,各,中心代表各聚类,,2.,计算所有点到这k个,中心,的距离，,并,将点归到离其最近的聚类,,,3.,调整聚类中心，即将聚类的中心移动到聚类的几何中心（即平均值）,,4.,重复第,2,、,3,步直到聚类的中心不再移动，此时算法收敛,划分聚类法,– K-means,算法流程,迭代计算,,中心点,收敛！,选择初始中心点,,各点划分进最近聚类,,调整聚类中心,划分聚类法,– K-means,Simple Example,Step 1,从数据集中任意选择,k,个对象,C,1,,C,2,, …,C,k,作为初始的簇中

7、心；,Step2,把每个对象分配到与之最相似的聚合。每个聚合用其中所有对象的均值来代表，“最相似”就是指距离最小。对于每个点,V,i,，找出一个质心,C,j,，使它们之间的距离,d(,V,i,,,C,j,),最小，并把,V,i,分到第,j,组。,Step3,把所有的点分配到相应的簇之后，重新计算每个组的质心,C,j,,。,Step4,循环执行,Step2,和,step3,，直到数据的划分不再发生变化,,划分聚类法,– K-means,算法实现的具体流程,,,,初始,中心点,,,,输入数据及,k,值的选择,,,,距离,度量,,Factors,影响聚类,效果！,一般采用欧氏距离、曼哈顿距离或者名考

8、斯距离的一种，作为样本间的相似性度量,划分聚类法,– K-means,算法特点：影响主要因素,划分聚类法,– K-means,不足：,k-means,算法只有在簇的平均值被定义的情况下才能使用。,k-means,算法的不足之处在于它要多次扫描数据库。,k-means,算法只能找出球形的类，而不能发现任意形状的类。,初始质心的选择对聚类结果有较大的影响。,k-means,算法对于噪声和孤立点数据是敏感的，少量的该类数据能够对平均值产生极大的影响。,问题描述：,,如图所示，一只遥望大海的小狗。此图为,100×100,像素的,JPG,图片，每个像素可以表示为三维向量（分别对应红绿蓝三基色）。,要求使

9、用,k-means,算法，将图片分割为合适的背景区域（三个）和前景区域（小狗）。,,划分聚类法,– K-means,应用实例,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

10、==k))>0,,M(k, :) = mean(X(find(j==k), :));,end,end,划分聚类法,– K-means,Z = zeros(N,K);,for m=1:N,Z(m,j(m)) = 1;,end,,e = sum(sum(Z.*Dist)./N);,fprintf('%d Error = %f\n', n, e);,Mo = M;,end,Matlab,程序实现（续）,划分聚类法,– K-means,close all;clear all; clc;,C_Segments=5;,img_original = imread('dog.png');,%,读入图像,fig

11、ure,imshow(img_original),title(',原始图像,');,%,显示原图像,[m,n,depth]=size(img_original );,%,获取图像的长宽,,%,将图像进行,RGB——3,通道分解,%,将,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 B C];,%

12、r g b,分量组成样本的特征，每个样本有三个属性值，共,width*height,个样本,cRGB =,kmeans,(double(dat), C_Segments, 20);,rRGB = reshape(cRGB, m, n);,%,反向转化为图片形式,figure, imshow(label2rgb(rRGB),[]),title(',分类结果,');,%,显示分割结果,划分聚类法,– K-means,分割后的效果,应用实例,划分聚类法,– K-means,,,,,,,,划分聚类法,– K-means,应用实例,注：聚类中心个数为,5,，最大迭代次数为,10,。,思路,将聚类问题中的

13、,类定义为模糊集合,，用模糊集的,隶属度,函数定量描述样本点与类之间的从属关系，并通过寻找使,目标函数最小化,的隶属度函数，实现聚类。,,算法关键点,隶属度函数的数学定义,模糊类中心的更新,,,,,,,划分聚类法,–,模糊,C,均值聚类,fuzzy c-means,变量定义,数据集,X,=,{,x,1,,,,x,2,,,,…,,,,,x,n,},c,个模糊类,样本,x,k,对第,i,类的模糊隶属度为,u,ik,，,满足条件,隶属度矩阵,U,={,u,ik,},,第,i,类的类中心为,v,i,聚类中心矩阵为,V,={,v,1,,,,v,2,,,,…,,,v,c,},建立基于隶属度矩阵,U,和聚类

14、中心矩阵,V,的目标函数,J,m,(,U,,,V,),,,,,,,,划分聚类法,–,模糊,C,均值聚类,fuzzy c means,目标函数最小化求解,,,,,划分聚类法,–,模糊,C,均值聚类,fuzzy c means,这里,m>1,,是隶属度的加权指数,;,,为第,i,个聚类中心与第,k,个数据样本之间的欧几里得距离,;,限定条件：,最小化上述函数可以用拉格朗日乘子法求解,目标函数最小化求解,对上式进行求导，使其达到最小的必要条件为：,,,,划分聚类法,–,模糊,C,均值聚类,fuzzy c means,公式（,1,）,公式（,2,）,模糊,C,均值聚类算法具体步骤,划分聚类法,–,模糊

15、,C,均值聚类,fuzzy c-means (FCM),确定聚类类别数目,c,、加权指标,m,，用,0~1,的随机值初始化隶属矩阵,U,(0),,，并满足,令迭代次数为,b,，,b=0,1,2…bmax,根据公式（,2,）计算各个类的中心,V,i,(b),;,根据公式（,1,）更新,U,(b),为,U,(b+1),；,比较,U,(b),和,U,(b+1),之间的差别，如果 或者迭代达到最大次数，则聚类结束；否则，置,b=b+1,并返回第,3,步。,,,,,,,,划分聚类法,–,模糊,C,均值聚类,fuzzy c means,MATLAB,中提供

16、了,FCM,函数：,[center, U, obj_fcn] = fcm(data, cluster_n, options);,,%,输入：,% data ---- nxm,矩阵,,,表示,n,个样本,,,每个样本具有,m,的维特征值,% N_cluster ----,标量,,,表示聚合中心数目,,,即类别数,% options ---- 4x1,矩阵，其中,% options(1):,隶属度矩阵,U,的指数，,>1 (,缺省值,: 2.0),% options(2):,最大迭代次数,(,缺省值,: 100),% op

17、tions(3):,隶属度最小变化量,,,迭代终止条件,(,缺省值,: 1e-5),% options(4):,每次迭代是否输出信息标志,(,缺省值,: 1),,%,输出：,% center ----,聚类中心,% U ----,隶属度矩阵,% obj_fcn ----,目标函数值,,,,,,划分聚类法,–,模糊,C,均值聚类,fuzzy c means,应用实例,,close all;clear all; clc;,C_Segments=4;,img_original = imread('pepper.png');%,读入图像,fi

18、gure,imshow(img_original),title(',原始图像,'); %,显示原图像,[m,n,p]=size(img_original ); %,获取图像的长宽,,%,将图像进行,RGB——3,通道分解,%,将,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 B C]; %

19、 r g b,分量组成样本的特征，每个样本有三个属性值，共,width*height,个样本,,,,,聚类法,–,模糊,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),co

20、lormap(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(L

21、AB==4),colormap(map),,,,,聚类法,–,模糊,C,均值聚类,fuzzy c means,应用实例,分割结果,,,,,划分聚类法,– K-medoids,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,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

22、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,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-medoids,基本思想,:,,找聚类中的代表对象(中心点),PAM,(Partitioning Around Medoids),首先为每个簇随意选择一个代表对象, 剩余的对象根据其与代表对象

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

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

25、离它最近的代表对象所代表的簇；,(4) 随意地选择一个非代表对象,O,random,；,(5),计算用,O,random,代替,O,j,的总距离,E,,如果,E,比取代前下降则则用,O,random,替 换,O,j,，,形成新的,k,个代表对象的集合，返回（,4,）；,(,6),until,不发生变化,(7),如果所有非代表对象都无法取代已存在的簇中心，则结束替代过程，并输出结果,划分聚类法,– K-medoids,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3

26、,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,,,,

27、,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,,,,划分聚类法,– K-medoids,当存在噪音和孤立点时,,PAM,比,,k-,平均方法更健壮. 这是因为中心点不象平均值那么容易被极端数据影响,,PAM,对于小数据集工作得很好, 但不能很好地用于大数据集,,

28、每次迭代,O,(,k,(,n-k,),2,),,其中,,n,,是数据对象数目,,,,k,是聚类数,CLARA,,(Clustering LARge Applications),Improvement over PAM,Finds medoids in a,sample,from the dataset,[Idea],:,,If the samples are sufficiently random, the medoids of the sample approximate the medoids of the dataset,[Heuristics],:,,5 samples of size

29、 40+2k gives satisfactory results,Works well for large datasets (n=1000, k=10),划分聚类法,– K-medoids,CLARA,,(Clustering LARge Applications),划分聚类法,– K-medoids,Draw multiple samples of the dataset,Sample should be able to represent the dataset,Apply PAM to each sample,Return the best clustering,Set,mincos

30、t,to MAXIMUM;,Repeat,q,times // draws,q,samples,Create,S,by drawing,s,objects randomly from,D,;,Generate the set of medoids,M,from,S,by applying the PAM algorithm;,Compute cost(M,D),If cost(M,D)< mincost,Mincost = cost(M, D);,Bestset = M;,End if;,End repeat;,Return Bestset;,Algorithms:,CLARA,,(Clust

31、ering LARge Applications),划分聚类法,– K-medoids,s: the size of the sample,k: number of clusters,n:number of objects,Complexity of each iteration is: O(ks,2,+k(n-k)),CLARA,,(Clustering LARge Applications),划分聚类法,– K-medoids,PAM,find the best K medoids from a given dataset;,CLARA,,finds the best kMedoids f

32、rom 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 clustering,If the sampling is biased, we can not have a good clustering.,Trade off-of efficiency.,CLARANS,,(Clustering Large Applications based on

33、Randomized Search),划分聚类法,– K-medoids,It was proposed to improve the quality and scalability of CLARA,It combines sampling techniques with PAM,It does not confine itself to any sample at a given time,It draws a sample with some randomness in each step of the search,CLARANS draws sample in,solution sp

34、ace,dynamically,A solution is a set of,k,medoids,The solutions space contains C,n,k,solutions in total,The solution space can be represented by a graph where every node is a potential solution, i.e., a set of,k,medoids,CLARANS,,划分聚类法,– K-medoids,Every node is a potential solution (k-medoid),Every no

35、de is associated with a squared error,Two nodes are adjacent if they differ by one medoid,Every node has,k,(,n,,k,) adjacent nodes,,,{,O,1,,,O,2,,…,O,k,},,{,O,k+1,,,O,2,,…,O,k,},,{,O,k+n,,,O,2,,…,O,k,},,,…,,n-k,,neighbors for one medoid,,k,(,n,,,k,),neighbors for one node,…,,划分聚类法,– K-medoids:,CLA

36、RANS,Start with a randomly selected node, check,at most,m,neighbors,randomly,If 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 optimum,When,h,local optimum,have been foun

37、d, returns best result as overall result,划分聚类法,– K-medoids:,CLARANS,N,N,N,C,,,,,,,,,C,,N,,,N,N,,,,<,,Local minimum,…,,Compare no more than,maxneighbor,,times,,numlocal,,Best Node,,Local minimum,…,,Local minimum,…,,Local minimum,…,划分聚类法,– K-medoids:,CLARANS,Algorithms:,Set mincost to MAXIMUM;,For i=1

38、 to,h,do // find h local optimum,Randomly select a node as the current node C in the graph;,J = 1; // counter of neighbors,Repeat,Randomly select a neighbor N of C;,If Cost(N,D) m,Update mincost with Cost(C,D) if appli

39、cable End for;,End For,Return bestnode;,划分聚类法,– K-medoids:,CLARANS,Algorithms:,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 dissimilarity,Iterations correspond to a,hill descent,proc

40、ess in a landscape (graph) of vertices,划分聚类法,– K-medoids:,CLARANS,Advantages:,CLARANS is more effective than both PAM and CLARA,Handles outliers,,Disadvantages:,Computational complexity of CLARANS is O(N,2,).,The clustering quality depends on the sampling method,小 结,掌握划分聚类算法的基本思想和局限性,掌握常用的划分聚类的思想和优缺

41、点以及适用范围,,k-means, FCM, k-medoids (PAM, CLARA, CLARANS),能够利用代码实现上述方法，并且结合实际应用设计相应的输入输出,内容总结,Pattern Recognition。统计学方法、神经网络方法。对于连续型属性具有较好的聚类效果，不适合处理离散型属性。1. 随机抽取k个点作为初始聚类的中心，由各中心代表各聚类。对于每个点Vi，找出一个质心Cj，使它们之间的距离d(Vi, Cj)最小，并把Vi分到第j组。此图为100×100像素的JPG图片，每个像素可以表示为三维向量（分别对应红绿蓝三基色）。% 将图像进行RGB——3通道分解。注：聚类中心个数为5，最大迭代次数为10。第i类的类中心为vi。建立基于隶属度矩阵U和聚类中心矩阵V的目标函数Jm(U,V)。为第i个聚类中心与第k个数据样本之间的欧几里得距离。确定聚类类别数目c、加权指标m，用0~1的随机值初始化隶属矩阵U(0) ，并满足。否则，置b=b+1并返回第3步。然后反复地用非代表对象来替代代表对象，以改进聚类的质量。如果Oj被Orandom代替，而p仍然离Oi最近，那么对象的隶属不发生变化,