模糊核c均值算法研究

模糊核c均值算法研究

模糊c-平均值算法（rcm）不能用于非超球数据、噪声数据、混合模式数据和不对称数据等数据结构。这是因为人们提出了许多不同的模糊算法来适应不同的数据结构。例如，对于不同的集群原型，建议基于壳体原型和任意二次曲线原型的模糊剂原型。这种算法的弱点是，另一方面，它需要使用首先的知识来选择合适的集群原型，另一方面，它不能处理混合聚类原型的数据结构。Girolami和张莉、焦李成等在结合核方法和聚类算法方面做了开创性工作,他们通过把模式空间的数据非线性映射到高维特征空间,增加了模式的线性可分概率,即扩大模式类之间的差异,在高维特征空间达到线性可聚的目的.文献只适合硬聚类,而文献没有给出模糊核聚类的具体算法,而且仅对不同高斯分布密度的数据进行了研究.笔者将核方法的思想推广到FCM算法,构造了基于核函数的模糊核C-均值算法(FKCM),使其能够对非超球体数据、被噪声污染的数据、多种模式原型混合的数据以及不对称数据等多种数据结构进行聚类分析,这样的推广使FCM算法的聚类性能得到明显提高.并指出FCM算法是FKCM算法在一阶多项式下的特例.在经典FCM不能聚类时,FKCM算法在给定合适的核函数及其参数的情况下,一般均能得到较好的结果.人工和实际数据的测试实验也证实了该方法的有效性.1基于mercer的算法支撑矢量机的成功重新引起了人们对核方法的研究兴趣,核方法的基本思想就是用非线性变换ϕ(·)把输入模式空间Rp映射到一个高维特征空间Rq,再在高维特征空间中设计线性学习算法.若算法中各模式矢量间的相互作用仅限于内积运算,则不需要知道非线性变换ϕ(·)的具体形式,只要用满足Mercer条件的核函数替换线性算法中的内积,就能得到原输入空间中对应的非线性算法这种称为“核技巧”的方法,即用Mercer核函数来简化计算,可以解决非线性变换带来的“维数灾难”问题.除支撑矢量机外,还有基于核函数的Fisher判别法和基于核的主分量分析法等若干基于核函数方法的算法获得了成功的应用.以ϕ(xi)表示模式矢量xi,i=1,2,…,N在高维特征空间的像,而ϕ(·)表示非线性映射函数.常用的满足Mercer条件的核函数有多项式核函数和径向基核函数等.若选用核函数K,则在特征空间Rq,模式矢量xi和xj之间的Euclid距离可表示为dΚij=[Κ(xi,xi)-2Κ(xi,xj)+Κ(xj,xj)]1/2.(1)2模糊聚类分析依照核方法的思想,用非线性映射ϕ(·)把输入模式矢量空间变换到一个高维特征空间,在该特征空间扩展FCM算法,对变换后的特征矢量ϕ(xj),i=1,2,…,N进行模糊聚类分析.2.1模糊加权算法令X={x1,x2,…,xN}为模式空间Rp中的一个有限数据集;xi为该模式空间中的一个模式矢量;该N个p维数据表示成的一个p×N的数据矩阵X;模糊聚类算法把数据集X划分成为C个模糊簇,并获得一个最优模糊划分矩阵U*,该矩阵的元素uji∈[0‚1]表示模式矢量xi隶属于第j类(簇)的程度.Bezdek提出的FCM算法是分别关于U,V最小化目标函数,可表示为Jm(X;U,V)=C∑j=1Ν∑i=1umji|xi-vj|2A‚2≤C＜Ν‚(2)其中V=(v1,v2,…,vC),vj∈Rp是聚类中心或第i类的模式原型.C是事先确定的簇数,m∈(1,∞)是模糊加权指数,对聚类的模糊程度有重要的调节作用;|xi-vj|2A是Rp中的内积范数,度量xi到vj的距离,其中A为任意的p×p阶的对称正定方阵,一般常令A=E,即用xi和vj的Euclid距离dij(xi,vj)来作距离测度.模糊C-均值算法对式(2)做极小值优化.Bezdek给出的FCM算法通过目标函数Jm(X;U,V)极小化的必要条件之间的迭代收敛到一个局极小点或鞍点,得到的一个模糊C划分U*.为避免出现平凡解,U必须满足下面约束:C∑j=1uji=1‚∀i和0＜Ν∑i=1uji＜Ν‚∀j.(3)2.2特征空间模糊模糊fkcm算法若在高维特征空间Rq采用Euclid距离,由式(2)可推出特征空间的模糊聚类目标函数为JΚm(X;U,V)=C∑j=1Ν∑i=1umji|ϕ(xi)-ϕ(vj)|2E=C∑j=1Ν∑i=1umji(Κ(xi,xi)-2Κ(xi,vj)+Κ(vj,vj))=C∑j=1Ν∑i=1umjid2Κji(xi,vj)‚2≤C≤Ν.(4)按FCM算法优化方法,在特征空间隶属度函数应满足:uji=(1/d2Κji(xi,vj))1/(m-1)/C∑j=1(1/d2Κji(xi,vj))1/(m-1).(5)在特征空间Rq,新的类中心为ϕ(ˆvj)=Ν∑i=1(uji)mϕ(xi)/Ν∑i=1(uji)m‚j=1‚2‚⋯‚C.(6)则可计算得Κ(xi,ˆvj)=ϕ(xi)⋅ϕ(ˆvj)=Ν∑k=1(ujk)mΚ(xk,xi)/Ν∑k=1(ujk)m‚(7)Κ(ˆvj,ˆvj)=ϕ(ˆvj)⋅ϕ(ˆvj)=Ν∑k=1Ν∑l=1(ujk)m(ujl)mΚ(xi,xl)/(Ν∑k=1(ujk)m)2‚(8)所以在特征空间新隶属度函数ˆuji更新为ˆuji=(1/d2Κji(xi‚ˆvj))1/(m-1)C∑j=1(1/d2Κji(xi,ˆvj))1/(m-1)=(1/(Κ(xi,xi)-2Κ(xi,ˆvj)+Κ(ˆvj,ˆvj)))1/(m-1)C∑j=1(1/(Κ(xi,xi)-2Κ(xi,ˆvj)+Κ(ˆvj,ˆvj)))1/(m-1).(9)类似FCM算法,推出高维特征空间的FKCM算法.并且可证明在高维特征空间,FKCM算法是收敛的.FKCM算法:⑴选择类数C和迭代停止条件ε∈(0,1),迭代次数T;⑵选择核函数K及其参数;⑶初始化类中心vj,j=1,…,C;⑷按式(5)计算每个样本在特征空间的隶属度函数uji,j=1,…,C;i=1,…,N;⑸由式(7),(8)计算新的核函数值K(xi,ˆvj)和K(ˆvj,ˆvj),并按式(9)更新隶属度uji为ˆuji;⑹若maxj,i|uji-ˆuji|＜ε或迭代次数等于预定迭代次数T则算法停止,否则转到⑷.对于模糊核C-均值聚类算法,有如下命题:命题当b=0,d=1时,基于一阶多项式核函数的模糊核C-均值算法等价于模糊C-均值算法.证明由条件可知,核函数为K(xi,xj)=(xi·xj+b)d=xi·xj,于是在特征空间中,模式xi和xj的Euclid距离为dKijdΚij=[Κ(xi,xj)-2Κ(xi,xj)+Κ(xj,xj)]1/2=[(xi⋅xi)-2(xi⋅xj)+(xj⋅xj)]1/2=(|xi-xj|2)1/2=dEij.(10)由式(7)有Κ(xi,ˆvj)=ϕ(xi)⋅ϕ(ˆvj)=Ν∑k=1(ujk)mΚ(xk‚xi)/Ν∑k=1(ujk)m=Ν∑k=1(ujk)m(xk⋅xi)/Ν∑k=1(ujk)m=xi⋅[Ν∑k=1(ujk)mxk/Ν∑k=1(ujk)m]=xi⋅ˆvj‚(11)即在特征空间Rq,Euclid距离dKij等价于模式空间Rp的Euclid距离dEij,特征空间Rq中的类中心ϕ(ˆvj)等价于模式空间Rp的类中心ˆvj,也就是基于一阶多项式核函数的FKCM算法等价于FCM算法,证毕.3实验数据测试为了评价FKCM算法的聚类性能,分别使用人造和实际数据进行了两组测试实验,并与传统FCM算法进行了比较.所有实验均使用MATLAB6.1在PⅡ400内存128M的PC机上运行.3.1实验结果和分析实验1构造了一个二维空间的两个不同聚类原型的非团状数据Data1,一类是圆心在原点,半径为3,且均匀分布的环形数据,样本点为100个.另一类为中心在原点,边长为1,且均匀分布的正方形数据,样本点为100个.两类数据均加了均值为零,方差为分别为0.01,0.1的高斯噪声.如图1所示.实验采用多项式核函数K(X,Y)=ϕ(X)·ϕ(Y)=(X·Y+b)d,参数为m=2‚d=2‚b=1‚ε=10-4.随机做20次实验,其中一次实验结果见图19,(A),分别为FKCM算法和算法FCM的输出结果.实验2构造了一个二维数据集Data2,该数据集由两类半圆数据组成(半径分别是3和1.5),每类数据有100个样本.实验采用多项式核函数,参数为m=2,d=60,b=1,ε=10-5.随机做20次实验,其中一次实验结果见图29,(A),分别为FKCM和FCM算法的输出结果.表1和表2分别给出两组人工数据测试实验的详细实验结果,比较两种算法的性能可得,FKCM算法可以适用于两种类型的数据,且具有相当高的分类精度和相对较少的迭代次数,而FCM算法在数据呈团状分布且各类数目大致相当时相当有效,而对其他情况则性能严重下降.3.2实验结果和分析实验3用著名的IRIS实际数据作为测试样本集.IRIS数据由四维空间中的150个样本组成,分别隶属于3个不同类别,每类50个样本.数据集中,一类IRIS数据与其他两类间较好分离,IRIS数据经常被作为标准的测试数据.该实验核函数选用径向基核函数K(X,Y)=ϕ(X)·ϕ(Y)=exp(-(X-Y)2/(2σ2)),参数为m=2‚σ2=0.4‚ε=10-5.FKCM算法仅聚错8个样本,而FCM算法错聚个数达16个,实验结果见表3.实验4用Fossil实际数据作为测试样本集.Fossil数据由六维空间中的87个样本组成,分别隶属于3个不同类别,第1类40个样本(序号为1～40),第2类34个样本(序号为41～74),第3类13个样本(序号为75～87).该实验核函数选用多项式核函数,参数为m=2‚d=1/8‚b=1.FKCM算法仅聚错2个样本(32号和33号样本错聚为第3类),而FCM算法错聚个数达28个,详细实验结果见表4.实际数据的测试结果与人工数据的测试结果相吻合,再一次证实了FKCM算法优于传统FCM算法的性能,分类精度大大提高.4模糊算法fkcm算法从实验中可以看出,FKCM算法对不同聚类原型、不同分布密度、悬殊的类中样本数目、