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

PatternRecognitionI=randperm(N);M=X(I(1:K),:);Mo=M;forn=1:Max_Itsfork=1:KDist(:,k)=sum(X-repmat(M(k,:),N,1).2,2);endi,j=min(Dist,2);fork=1:Kifsize(find(j=k)0M(k,:)=mean(X(find(j=k),:);endend,划分聚类法K-means,19,.,Z=zeros(N,K);form=1:NZ(m,j(m)=1;ende=sum(sum(Z.*Dist)./N);fprintf(%dError=%fn,n,e);Mo=M;end,Matlab程序实现（续）,划分聚类法K-means,20,.,closeall;clearall;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=reshape(img_original(:,:,1),m*n,1);B=reshape(img_original(:,:,2),m*n,1);C=reshape(img_original(:,:,3),m*n,1);dat=ABC;%rgb分量组成样本的特征，每个样本有三个属性值，共width*height个样本cRGB=kmeans(double(dat),C_Segments,20);rRGB=reshape(cRGB,m,n);%反向转化为图片形式figure,imshow(label2rgb(rRGB),),title(分类结果);%显示分割结果,划分聚类法K-means,21,.,分割后的效果,应用实例,划分聚类法K-means,22,.,划分聚类法K-means,应用实例,注：聚类中心个数为5，最大迭代次数为10。,思路将聚类问题中的类定义为模糊集合，用模糊集的隶属度函数定量描述样本点与类之间的从属关系，并通过寻找使目标函数最小化的隶属度函数，实现聚类。算法关键点隶属度函数的数学定义模糊类中心的更新,划分聚类法模糊C均值聚类fuzzyc-means,变量定义数据集X=x1,x2,xnc个模糊类样本xk对第i类的模糊隶属度为uik，满足条件隶属度矩阵U=uik第i类的类中心为vi聚类中心矩阵为V=v1,v2,vc建立基于隶属度矩阵U和聚类中心矩阵V的目标函数Jm(U,V),划分聚类法模糊C均值聚类fuzzycmeans,目标函数最小化求解,划分聚类法模糊C均值聚类fuzzycmeans,这里m1,是隶属度的加权指数;为第i个聚类中心与第k个数据样本之间的欧几里得距离;,限定条件：,最小化上述函数可以用拉格朗日乘子法求解,目标函数最小化求解对上式进行求导，使其达到最小的必要条件为：,划分聚类法模糊C均值聚类fuzzycmeans,公式（1）,公式（2）,模糊C均值聚类算法具体步骤,划分聚类法模糊C均值聚类fuzzyc-means(FCM),确定聚类类别数目c、加权指标m，用01的随机值初始化隶属矩阵U(0)，并满足令迭代次数为b，b=0,1,2bmax根据公式（2）计算各个类的中心Vi(b);根据公式（1）更新U(b)为U(b+1)；比较U(b)和U(b+1)之间的差别，如果或者迭代达到最大次数，则聚类结束；否则，置b=b+1并返回第3步。,划分聚类法模糊C均值聚类fuzzycmeans,MATLAB中提供了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)%options(3):隶属度最小变化量,迭代终止条件(缺省值:1e-5)%options(4):每次迭代是否输出信息标志(缺省值:1)%输出：%center-聚类中心%U-隶属度矩阵%obj_fcn-目标函数值,划分聚类法模糊C均值聚类fuzzycmeans,应用实例,closeall;clearall;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=reshape(img_original(:,:,3),m*n,1);dat=ABC;%rgb分量组成样本的特征，每个样本有三个属性值，共width*height个样本,聚类法模糊C均值聚类fuzzycmeans,应用实例,center,U,fct=fcm(double(dat),C_Segments);,label=max(U,1);figure;LAB=reshape(label,m,n);imshow(LAB,)figure;map=000;center(1,1)/255,center(1,2)/255,center(1,3)/255;imshow(LAB=1),colormap(map)figure;map=000;center(2,1)/255,center(2,2)/255,center(2,3)/255;imshow(LAB=2),colormap(map)figure;map=000;center(3,1)/255,center(3,2)/255,center(3,3)/255;imshow(LAB=3),colormap(map)figure;map=000;center(4,1)/255,center(4,2)/255,center(4,3)/255;imshow(LAB=4),colormap(map),聚类法模糊C均值聚类fuzzycmeans,应用实例,分割结果,划分聚类法K-medoids,k-中心点(k-Medoids):不采用簇中对象的平均值作为参照点,而是选用簇中位置最中心的对象,即中心点(medoid)作为参照点.,划分聚类法K-medoids,基本思想:找聚类中的代表对象(中心点)PAM(PartitioningAroundMedoids)首先为每个簇随意选择一个代表对象,剩余的对象根据其与代表对象的距离分配给最近的一个簇;然后反复地用非代表对象来替代代表对象，以改进聚类的质量PAM对于较小的数据集非常有效,但不能很好地扩展到大型数据集。,划分聚类法K-medoids,为了判定一个非代表对象Orandom是否是当前一个代表对象Oj的好的替代,对于每一个非代表对象p,考虑下面的四种情况：第一种情况：p当前隶属于代表对象Oj.如果Oj被Orandom所代替,且p离Oi最近,ij,那么p被重新分配给Oi第二种情况：p当前隶属于代表对象Oj.如果Oj被Orandom代替,且p离Orandom最近,那么p被重新分配给Orandom,划分聚类法K-medoids,第三种情况：p当前隶属于Oi，ij。如果Oj被Orandom代替，而p仍然离Oi最近，那么对象的隶属不发生变化第四种情况：p当前隶属于Oi，ij。如果Oj被Orandom代替，且p离Orandom最近，那么p被重新分配给Orandom,划分聚类法K-medoids,算法:k-中心点(1)随机选择k个对象作为初始的代表对象；(2)repeat(3)指派每个剩余的对象给离它最近的代表对象所代表的簇；(4)随意地选择一个非代表对象Orandom；(5)计算用Orandom代替Oj的总距离E,如果E比取代前下降则则用Orandom替换Oj，形成新的k个代表对象的集合，返回（4）；(6)until不发生变化(7)如果所有非代表对象都无法取代已存在的簇中心，则结束替代过程，并输出结果,划分聚类法K-medoids,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,K=2,Arbitrarychoosekobjectasinitialmedoids,Assigneachremainingobjecttonearestmedoids,Randomlyselectanonmedoidobject,Oramdom,Computetotalcostofswapping,TotalCost=26,SwappingOandOramdomIfqualityisimproved.,DoloopUntilnochange,划分聚类法K-medoids,当存在噪音和孤立点时,PAM比k-平均方法更健壮.这是因为中心点不象平均值那么容易被极端数据影响PAM对于小数据集工作得很好,但不能很好地用于大数据集每次迭代O(k(n-k)2)其中n是数据对象数目,k是聚类数,CLARA(ClusteringLARgeApplications),ImprovementoverPAMFindsmedoidsinasamplefromthedatasetIdea:Ifthesamplesaresufficientlyrandom,themedoidsofthesampleapproximatethemedoidsofthedatasetHeuristics:5samplesofsize40+2kgivessatisfactoryresultsWorkswellforlargedatasets(n=1000,k=10),划分聚类法K-medoids,40,.,CLARA(ClusteringLARgeApplications),划分聚类法K-medoids,DrawmultiplesamplesofthedatasetSampleshouldbeabletorepresentthedatasetApplyPAMtoeachsampleReturnthebestclustering,41,.,SetmincosttoMAXIMUM;Repeatqtimes/drawsqsamplesCreateSbydrawingsobjectsrandomlyfromD;GeneratethesetofmedoidsMfromSbyapplyingthePAMalgorithm;Computecost(M,D)Ifcost(M,D)mincostMincost=cost(M,D);Bestset=M;Endif;Endrepeat;ReturnBestset;,Algorithms:,CLARA(ClusteringLARgeApplications),划分聚类法K-medoids,42,.,s:thesizeofthesamplek:numberofclustersn:numberofobjects,Complexityofeachiterationis:O(ks2+k(n-k),CLARA(ClusteringLARgeApplications),划分聚类法K-medoids,PAMfindthebestKmedoidsfromagivendataset;CLARAfindsthebestkMedoidsfromseveralselectedsamples.,Problems:Thebestk-medoidsmaynotbeselectedduringthesamplingProcess,inthiscase,CLARAwillneverfindthebestclusteringIfthesamplingisbiased,wecannothaveagoodclustering.Tradeoff-ofefficiency.,43,.,CLARANS(ClusteringLargeApplicationsbasedonRandomizedSearch),划分聚类法K-medoids,ItwasproposedtoimprovethequalityandscalabilityofCLARAItcombinessamplingtechniqueswithPAMItdoesnotconfineitselftoanysampleatagiventimeItdrawsasamplewithsomerandomnessineachstepofthesearch,44,.,CLARANSdrawssampleinsolutionspacedynamicallyAsolutionisasetofkmedoidsThesolutionsspacecontainsCnksolutionsintotalThesolutionspacecanberepresentedbyagraphwhereeverynodeisapotentialsolution,i.e.,asetofkmedoids,CLARANS,划分聚类法K-medoids,45,.,Everynodeisapotentialsolution(k-medoid)EverynodeisassociatedwithasquarederrorTwonodesareadjacentiftheydifferbyonemedoidEverynodehask(nk)adjacentnodes,O1,O2,Ok,Ok+1,O2,Ok,Ok+n,O2,Ok,n-kneighborsforonemedoid,k(nk)neighborsforonenode,划分聚类法K-medoids:CLARANS,46,.,Startwitharandomlyselectednode,checkatmostmneighborsrandomlyIfabetteradjacentnodeisfound,movestonodeandcontinue;otherwise,currentnodeislocaloptimum;re-startswithanotherrandomlyselectednodetosearchforanotherlocaloptimumWhenhlocaloptimumhavebeenfound,returnsbestresultasoverallresult,划分聚类法K-medoids:CLARANS,47,.,Comparenomorethanmaxneighbortimes,BestNode,划分聚类法K-medoids:CLARANS,48,.,Algorithms:,SetmincosttoMAXIMUM;Fori=1tohdo/findhlocaloptimumRandomlyselectanodeasthecurrentnodeCinthegraph;J=1;/