模式识别实验---C-均值算法与模糊C均值聚类的比较

实验一、C-均值算法与模糊C均值聚类的比较一、实验目的1.通过对算法的编程实现，加强对该算法的认识和理解，提高自身的知识水平和编程能力，认识模式识别在生活中的应用；2.深入理解C均值和模糊C均值的基本原理；3.采用两种分类方式进行仿真；二、实验原理1.C均值的原理；C均值聚类算法是一种典型的无监督动态聚类算法。该算法是在类别数目已知（=k）的条件下进行的，能够使聚类结果的距离平方和最小，即算法的基础是误差平方和准则。其基本过程是建立初始的聚心和聚类，通过多次迭代，逐渐调整各类的聚心和各像元的类别，直至得到聚类准则约束下的最好结果为止。本实验的具体过程如下：选择初始类别中心，假设有c个类别，设置其中心分别为(1)(1)(1)12,,,cZZZ在第k步迭代中，对于任何一个像元x(是一个N维向量，N是高光谱图像的波段数目)，按如下方法把它调整到。各类别中的某一个类别中去。令d(x，y)为向量x，y之间的距离，若：()()(,)(,)kkijdxZdxZ，j=12…c(ji)则()kixS，其中()kiS是以()kiZ为中心的类。由上一步得到的()kiS（i=12…c）个类别新的中心(1)kiZ()(1)1kikixSiZxN其中Ni是类别()kiS的数目。(1)kiZ是按照最小J的原则，J的表达式为：()(1)1(,)kickiixSJdxZ对所有的i=12…c。如果，(1)()kkiiZZ，则迭代结束（在程序中，则按照每个类别的对应的那些像素不再变化，则停止迭代），否则转到第二步继续迭代。2．模糊C均值的原理在数字图像由于存在混合像素的原因，也就是说一个像素中不仅存在一类地物，因而采用硬分类方式往往不合适，而模糊C均值就是引入模糊集对每个像素的划分概率不单单是用0或1这样的硬分类方式，而是0和1之间的范围内（包括0和1）。定义,1,2,...,ixin是n个样本组成的样本集合，c为预定的类别数目，,1,2,...,imic为每个聚类中心，()jiux是第i个样本对于第j类的隶属度函数。用隶属度函数定义的聚类损失函数可以写为：211(),cnbfjiijjiJuxxm其中，1b是一个可以控制聚类结果的模糊程度的常数。在不同的隶属度定义方法下最小化式的损失函数，就得到不同的模糊聚类方法。其中最有代表的是模糊C均值方法，它要求一个样本对于各个聚类的隶属度之和为1，即1()1,cjijux1,2,...,in在条件式下求得其极小值，令fJ对im和()jiux的偏导数为0，可得必要条件：11(),1,2,...,()nbjiiiinbjiiuxxmjcux，1/121/1211/(),1,2,...,1/bijjicbijkxmuxinxm1,2,...,jc。用迭代的方法求解上式，就是模糊C均值算法。算法步骤如下：1）.设定聚类数目c和参数b。2）初始化各个聚类中心im。3）重复下面的运算，直到各个样本的隶属度值稳定：当算法收敛时，就得到了各类的聚类中心和各个样本对于各类的隶属度值，从而完成了模糊聚类划分。三、实验要求表1、实验数据(X1、X2、X3是样本的特征)样本12345678910X1-7.82-6.684.366.72-8.64-6.874.476.73-7.71-6.91X2-4.583.16-2.190.883.060.57-2.62-2.012.34-0.49X3-3.972.712.092.803.50-5.455.764.18-6.33-5.68样本11121314151617181920X16.186.72-6.25-6.948.096.81-5.19-6.384.086.27X22.81-0.93-0.26-1.220.200.174.24-1.741.300.93X35.82-4.040.561.132.25-4.154.041.435.33-2.78利用表1数据完成下面的实验：1.编写C-均值算法，并用上表数据按下列条件分别测试。（a）c=2(类别数)；初始聚类的均值：m1(0)=(1,1,1),m2(0)=(-1,1,-1)（b）c=2(类别数)；初始聚类的均值：m1(0)=(0,0,0),m2(0)=(1,1,-1)。将得到的结果与（a）中结果比较，并解释差别，包括迭代次数的差别。（c）c=3(类别数)；初始聚类的均值：m1(0)=(0,0,0),m2(0)=(1,1,1)，m3(0)=(-1,0,2)（d）c=2(类别数)；初始聚类的均值：m1(0)=(-0.1,0,0.1),m2(0)=(0,-0.1,0.1)，m3(0)=(-0.1,-0.1,0.1)。将得到的结果与（a）与（c）中结果比较，并解释差别，包括迭代次数的差别。2.重做（1），但利用模糊C均值聚类，并设置:b=2。并与C-均值算法比较。四、实验结果及分析1、c=2(类别数)；初始聚类的均值：m1(0)=(1,1,1),m2(0)=(-1,1,-1)在设定初始中心m1(0)=(1,1,1),m2(0)=(-1,1,-1)情况下分得的结果如图1，绿色和红色分别是两种不同的种类。C均值聚类（K均值聚类）是采用欧氏距离作为类别的相似性度量，也就是说与某个类别中心相聚最近就判属于这类。由图1可以看出绿色“o”和红色“*”两种种类中间存在着一个较大的间距，因而可以将这两类样本区别开来。-10-50510-505-10-50510X1thefirstresultsofkmeansX2X3图1分类结果在同样的初始聚类中心条件下，我们采用模糊C均值方式对样本进行分类，因为模糊C均值属于一种软分类方式，因而得到的结果只能用隶属度来描述，对于模糊C均值的相似度描述是依赖于样本与类均值间的二范数（欧式距离）。结果如表2所示，P1表示样本属于第一类的概率，P2表示样本属于第二类的概率。从这我们也可以很明显看出C均值和模糊C均值间的差别，C均值是属于一种硬分类方式，所以分类结果只能用0或1来表示，然而，实际中存在着介于“是”与“不是”间的类别，采用硬分类方式就得不到合理的结果。迭代次数比较，C均值经过2次迭代结束，而模糊C均值却需要5次迭代才能结束，这也许引起的一个主要原因是循环结束条件不一致。表2、模糊C均值的分类结果样本12345678910P10.12650.10890.95520.98750.11780.08870.88760.95830.11850.0977P20.87350.89110.04480.01250.88220.91130.11240.04170.88150.9023样本11121314151617181920P10.90210.83910.01760.03740.97810.83680.22240.06000.90420.8807P20.09790.16090.98240.96260.02190.16320.77760.94000.09580.11932、c=2(类别数)；初始聚类的均值：m1(0)=(0,0,0),m2(0)=(1,1,-1)在设定初始中心m1(0)=(0,0,0),m2(0)=(1,1,-1)情况下分得的结果如图2，绿色和红色分别是两种不同的种类。显而易见，实验二的结果和实验一的结果一致，这可能由于初始中心的选取不合理引起的结果。此外，最为主要的原因可能是，绿色“o”和红色“*”两类之间的间隔确实较远，在分两类的情况下确实只会导致这样的结果。-10-50510-505-10-50510X1thesecondresultsofkmeansX2X3图2分类结果由表3可见，在硬分类的条件下，无法对红色“*”类别进行合理的描述，而模糊C均值却能给出一个较为合理的分析。对于C均值迭代结束是3，而模糊C均值的迭代次数为7。由此可见，迭代次数不仅依赖于样本本身，还依赖于初值的选取。表3、模糊C均值的分类结果样本12345678910P10.87240.89280.04510.01270.88380.91010.11390.04230.88050.9009P20.12760.10720.95490.98730.11620.08990.88610.95770.11950.0991样本11121314151617181920P10.09910.15890.98290.96320.02170.16120.77990.94060.09760.1176P20.90090.84110.01710.03680.97830.83880.22010.05940.90240.88243、c=3(类别数)；初始聚类的均值：m1(0)=(0,0,0),m2(0)=(1,1,1)，m3(0)=(-1,0,2)在设定初始中心m1(0)=(0,0,0),m2(0)=(1,1,1)，m3(0)=(-1,0,2)情况下分得的结果如图3，绿色“o”、红色“*”和蓝色“x”分别是三种不同的种类。如图3可见，在实验一和实验二中的某一类被分成两个子类，这主要是C均值只利用到均值特征，而没有利用方差特征，对于上两个实验中某一类的类内方差较大，所以不能简单的把它当做一类对待，采用分三类的方式就能得到一个更好的实验结果。-10-50510-505-10-50510X1thethirdresultsofkmeansX2X3图3分类结果C均值分类迭代次数为3，而模糊C均值迭代次数为11，模糊C均值所需的迭代次数较多。当然不仅影响这个结果主要原因依赖于程序本身的设计。而C均值方法是引用MATLAB自带的程序。表4、模糊C均值的分类结果样本12345678910P10.70740.05800.03430.00740.10120.99000.06700.02600.88340.9934P20.06430.02490.91610.98180.03990.00200.81570.93540.02500.0014P30.22830.91710.04970.01070.85890.00800.11730.03860.09160.0052样本11121314151617181920P10.06070.15170.10470.12820.01470.15350.11430.14350.05630.1119P20.83560.71570.02350.03170.96580.71150.08310.04370.83530.7791P30.10370.13260.87180.84000.01950.13500.80270.81280.10840.10904、c=3(类别数)；初始聚类的均值（初始聚类中心）：m1(0)=(-0.1,0,0.1),m2(0)=(0,-0.1,0.1)，m3(0)=(-0.1,-0.1,0.1)在设定初始中心m1(0)=(-0.1,0,0.1),m2(0)=(0,-0.1,0.1)，m3(0)=(-0.1,-0.1,0.1)情况下分得的结果如图4，绿色“o”、红色“*”和蓝色“x”分别是三种不同的种类。如图4可见，实验四的结果与实验三的结果不一致，从而说明初值的选择对实验结果有较大的影响。对于那种类似较难区分的数据，我们应该根据经验等合理方式来给定。-10-50510-505-10-50510X1thefourthresultsofkmeansX2X3图4分类结果C均值分类迭代次数为4，而模糊C均值迭代次数为17。从以上结果，可以看出迭代次数依赖于程序本身、初始类别中心和样本数据。表5、模糊C均值的分类结果样本12345678910P10.22100.92480.04940.01090.86520.00890.11770.03880.09310.0049P20.06390.02250.91620.98160.03800.00230.81480.93490.02570.0014P30.71510.05270.03430.00750.09