西安交大-模式识别-基于IRIS的K-means聚类与ISODATA聚类算法

一．K-means聚类算法1.1实验目的练习K-means聚类算法，对IRIS数据进行分类，加深对K-means聚类算法的理解。1.2实验原理K-means聚类算法有如下几个步骤：Step1:选择K个初始的聚类中心Step2:将样本集中的样本按照最小距离准则分配到最临近聚类（本实验中采用欧式距离）Step3:分配完成后计算各个聚类中心Step4:如果聚类中心改变则返回step2重复，进行迭代。如果聚类中心不改变，则算法收敛，结束。1.3聚类效果评价经过文献学习，我采取了基于人工标注簇的F值来评价聚类效果的优劣。对每个人工标注的簇jP假设在C结构中存在一个与之对应的簇iC，但这个对应关系是未知的。为了发现iC，我们遍历聚类结果C中的m个簇，分别计算准确率、召回率和F值，从中挑选最优指标值及其对应的簇，以最优的指标值来判定jP的质量。对于任何的人工标注簇jP和聚类簇iC相应的准确率、召回率和F值计算公式如下：a.准确率(),jijiiPCPPCC=(1)b.召回率(),jijijPCRPCP=(2)c.F值()2(,)(,),(,)(,)jijijijijiPPCRPCFPCPPCRPC⋅⋅=+(3)利用(3)式，对于每一个人工标注簇jP，我们可以定义其F值1()max(,)jjiimFPFPC≤≤=(4)进一步，对所有簇的F值作加权平均，则可得到整个聚类结果的F值11(),sjjjjjsjiiPPFFPnPωω===⋅==∑∑(5)其中，公式(4)计算某个人工标注簇的F值；公式(5)通过评价全局所有的人工标注簇来评价整个聚类结果，最终的F值我们成为Class_F值。Class_F值强调以人工标注簇为基准，聚类的结果尽量地逼近事先确定的人工标注结构，该指标是一个非常有用的指标，目前在相关文献中使用比较频繁。Class_F值指标对聚类结果的优劣的整体区分能力比较强。1.4实验结果与分析实验中在150个数据样本中随机抽取3个作为初始聚类中心。经实验可知，样本数据的第3维和第4维在不用类之间区分度较大。所以为使分类更直观，我使用各数据的3、4维数据绘制数据原始分类图和聚类效果图。下面考察一次实验结果：由图可以直观看出，本次聚类效果较为理想。本次聚类随机选出的初始聚类中心为第42,136,149个样本。第i类数据被聚类至第j簇的数量如表所示第1簇第2簇第3簇第1类数据0500第2类数据4802第3类数据14036由表可看出，第1类数据对应第2聚类簇；第2类数据对应第1聚类簇；第3类数据对应第3聚类簇。各类数据的F值为第1类第2类第3类F值1.00000.85710.8182整个聚类结果的Class_F值为0.8918。可见本次聚类效果较优。但实际上，并非每次实验结果都有如此优良的效果，例如如下这次实验。由图可以直观看出，本次聚类效果并不理想。本次聚类随机选出的初始聚类中心为第14,48,88个样本。第i类数据被聚类至第j簇的数量如表所示第1簇第2簇第3簇第1类数据4190第2类数据2048第3类数据0050由表可看出，第1类数据对应第1聚类簇；但第2类与第3类数据并没有成功分类。这主要是因为初始聚类中心中有2个都取自第1类样本，而第1类样本距离第2,3类样本距离较远，在聚类过程中聚类中心不易转移到2,3类样本附近，因此，2,3类数据附近只有一个聚类中心，所以没能成功将2,3类分开。各类数据的F值为第1类第2类第3类F值0.88170.64860.6757整个聚类结果的Class_F值为0.7353。可见本次聚类效果不佳。由这两次实验对比发现，K-means聚类算法高度依赖于初始聚类中心，当初始聚类中心选地较接近实际分类情况时聚类效果会较好，否则聚类效果有可能会不佳。对K-means聚类算法进行200次MonteCarlo实验，得到平均Class_F_MC值为0.8369。可判断K-means聚类算法对IRIS数据分类的整体平均F值约为0.8369，整体聚类效果较好。1.5程序实现%Auther:XXX%StudentNumber:XXX%Date:2014.5.1.%Purpose:PractiseofK-meanscloseall;clearall;clc;%数据导入iris_dataset=load('iris_dataset.txt');%导入iris数据集x=iris_dataset;%待分类样本%给数据添加类别标签label=[ones(50,1);ones(50,1)*2;ones(50,1)*3];iris_dataset=[iris_dataset,label];%使用数据前两维画出真实分类图subplot(2,1,1);plot(x(1:50,3),x(1:50,4),'r*');%红色*表示第1类holdon;plot(x(51:100,3),x(51:100,4),'b+');%红色*表示第1类holdon;plot(x(100:150,3),x(100:150,4),'go');%红色*表示第1类holdon;title('数据原始分类图');legend('第1类','第2类','第3类');%给定聚类数目k=3;MonteCarlo=200;F_MC=0;%MonteCarlo平均F值forr=1:MonteCarlo%随机选取3个初始聚类中心n=randperm(150);center(1,:)=x(n(1),:);center(2,:)=x(n(2),:);center(3,:)=x(n(3),:);disp('3个初始聚类中心为');disp('第'),n(1),n(2),n(3),disp('个样本')%调用K-means函数[class,num,center]=kmeans(x,k,center);%调用K-均值函数%统计聚类效果%result(i,j)代表第i类数据被聚类至第j簇的数量result=zeros(k,k);form=1:3fori=(50*(m-1)+1):1:50*mforj=1:3ifclass(i)==jresult(m,j)=result(m,j)+1;endendendenddisp('result(i,j)表示第i类数据被聚类至第j簇的数量');result%计算准确率,召回率,F值%P(i,j)代表第i类数据与第j簇相应的准确率%R(i,j)代表第i类数据与第j簇相应的召回率fori=1:3forj=1:3P(i,j)=result(i,j)/num(j);R(i,j)=result(i,j)/50;F(i,j)=2*P(i,j)*R(i,j)/(P(i,j)+R(i,j));endenddisp('F(i,j)代表第i类数据与第j簇相应的F值');Fdisp('FF(i)代表第i类数据的F值');FF=max(F,[],2)disp('整个聚类结果的F值')F_final=mean(FF)F_MC=F_MC+F_final;enddisp('200次MonteCarlo后，F的均值为');F_MC=F_MC/MonteCarlo%绘制聚类效果图subplot(2,1,2);index1=find(class==1);plot(x(index1,3),x(index1,4),'r*');%红色*表示第1簇holdon;index2=find(class==2);plot(x(index2,3),x(index2,4),'b+');%红色*表示第1簇holdon;index3=find(class==3);plot(x(index3,3),x(index3,4),'go');%红色*表示第1簇holdon;title('聚类效果图');legend('第1簇','第2簇','第3簇');二、ISODATA聚类算法2.1实验目的练习ISODATA聚类算法，对IRIS数据进行分类，加深对ISODATA聚类算法聚类算法的理解，体验不同初始参数对聚类的影响。2.2实验原理ISODATA算法，即迭代自组织分析算法，通过设定初始参数引入人机对话环节，并使用归并与分裂的机制，当某类样本数目少于某阈值时，需将其取消；当某类标准差大于某一阈值或其样本数目超过某一阈值时，将其分为两类；当某两类聚类中心距离小于某一阈值时，将它们合并为一类。根据初始聚类中心和设定的类别数目等参数迭代，最终得到一个比较理想的分类结果。ISODATA算法的具体步骤如下。K：预期的聚类中心数据；Nθ：一个聚类中最少的样本数目，若小于此数目，则不能独立成类；Sθ：为一个聚类域中样本距离分布的标准差；Cθ：两聚类中心间的最小距离，小于此类，则合并两类；L：在一次迭代算法中，可以合并的聚类中心个数I：为迭代运算次数。第一步：将N个样本的模式读入，预选Nc个初始聚类中心，他可以不必等于所要求的聚类中心个数，可以从样本中任选；确定初始参数K，Nθ，Sθ，Cθ，L，I。第二步：将各个样本按最小距离准则划分到各类。若Dj=min{‖x-zj‖}，则x∈Sj第三步：如果Sj中的样本数NjNθ，取消该样本子集，Nc=Nc-1。第四步：修正各聚类中心。Zj=∑∈SjxNjx1，j=1,2，…，Nc第五步：计算Sj中的样本到聚类中心的平均距离∑∈−=SjxjZjxNjD1第六步：计算全部模式样本与其相应聚类中心的总平均距离jNCjDNjNjD∑==11第七步：判别分裂、合并及迭代运算等步骤：(1)如果迭代运算次数已达I次，即最后一次迭代，置Cθ=0,跳到第十一步，运算结束。(2)如果Nc≤K/2，即聚类中心的数目等于或不到规定值的一半，则进入第八步，将已有的聚类分裂。(3)如迭代运算的次数是偶次，或Nc≥2K，不进行分裂处理，跳到第十一步；如不符合以上两个条件（即既不是偶次迭代，也不是≥2K），则进入第八步，进行分裂处理。第八步：分裂处理。计算每个聚类Sj中各样本到聚类中心的标准差。第九步：求每一标准差向量σj中的最大分量，以{σjmax}代表。第十步：在最大分量集{σjmax}中，如有σjmaxSθ，同时又满足：1.jDD子集平均距离大于总体平均距离，和Nj(Nθ+1)*2，Sj中样本总数超过最少数目的一倍以上；2.Nc≤K/2，即类别不到规定的一半。则将Zj分裂为两个新的聚类中心，且Nc=Nc+1。完成分裂运算后，则跳回第二步,迭代次数加1。第十一步：计算全部聚类中心的距离。jiijZZD−=，i=1,2,…,Nc-1，j=i+1,…,Nc第十二步：比较Dij与Cθ值，将DijCθ的值按最小距离次序递增排列第十三步：将距离为Di1j1的两个聚类中心Zi1和Zj1合并。第十四步：如果是最后一次迭代运算（即第I次），算法结束。否则回到第一步且迭代次数加1（如果需由操作者改变输入参数；或返回到第二步，如果输入参数不变时）。2.3聚类效果评价同1.32.4实验结果与分析为简化程序，每次迭代最多只进行一次合并，即L=2。在全部样本中随机抽取cN个样本作为初始聚类中心。2.4.1实验1当初始参数设置为10,3,5,1.8,1.5,100cnscNKIθθθ======，且不引入人机交互时。单次实验结果如下：最终聚类结果聚类数Nc=3，且由上图可知聚类速度较快。各类数据的F值为第1类第2类第3类F值1.00000.85710.8182整个聚类结果的Class_F值为0.8918，可见本次聚类效果较好。2.4.2实验2在2.4.1的基础上改变两聚类间的最小距离，即参数cθ的大小，观察其对聚类结果的影响。a.当1.8cθ=时单次实验结果如下：最终聚类结果聚类数Nc=2，聚类数目变少，第2,3类数据没有被分类开。各类数据的F值为第1类第2类第3类F值0.97090.63950.6803整个聚类结果的Class_F值为0.7635，可见本次聚类效果不佳。b.当1.2cθ=时单次实验结果如下：最终聚类结果聚类数Nc=4，聚类数目变多，第2,3类被分为3簇。各类数据的F值为第1类第2类第3类F值10.69230.6842整个聚类结