模糊c-均值聚类算法的f统计量

模糊c-均值聚类算法的f统计量

模糊f统计量与模糊聚类有效性聚类分析是一种重要的方法。最著名、最常用的模糊聚类算法是模糊c-中旬聚类算法（rcm）。当使用模糊聚类算法时,一个事先必须确定的参数是数据集的分类数。这个问题属于“聚类有效性问题”。到目前为止,已提出了多种聚类有效性标准。文献中Hubert的Γ统计量就是最早基于统计信息而被应用于分类数判决的有效性函数,文献中比较系统地研究了Hubert的Γ统计量的使用效果,文献中针对Hubert的Γ统计量的不足提出了修改的Γ统计量,文献中也对修改的Γ统计量的使用效果作了尽一步的实验研究。由于Γ统计量是通过对数据的分布本身与聚类算法对数据得到的划分之间的匹配程度来判定数据的分类情况,这实际上对数据强加人为的假设而造成实际使用中很难有效。文献中提出了基于数据集的类内统计信息和类间统计信息的伪F统计量用于数据聚类分析,并能在聚类过程中确定数据集的最佳分类数。文献中将数理统计学中的F统计量用于数据划分最佳分类数的确定。文献中针对数理统计学中的F统计量不适合多维数据而提出了混合F统计量。由于Γ统计量、伪F统计量、F统计量以及混合F统计量等对数据带有模糊性分类的情况很难凑效,甚至要将数据模糊性分类的结果进行分明处理后,才能使用这些基于分明统计信息的聚类有效性函数,势必造成要抹杀数据模糊性分类的许多细节信息,将给实际最佳分类数的判定造成不利和不便。文献将文献中的伪F统计量进行模糊化修改,提出了适合模糊C-均值聚类算法的模糊伪F统计量的聚类有效性函数,就能够处理数据具有模糊分类情况的最佳分类的确定。本文将文献中用于方差分析的F统计量模糊化修改,也提出了适合模糊C-均值聚类算法的模糊F统计量的聚类有效性函数。模糊F统计量不仅能够处理数据具有模糊分类情况的最佳分类数的判决;而且,它的分类性能比模糊伪F统计量要好。1基于fcm的聚类中心数的规划算法模糊聚类问题可表示成下面的数学规划问题minJm(U,V)=n∑i=1c∑j=1umijd2ij使得c∑j=1uij=1,1≤i≤n;uij≥0,1≤i≤n,1≤j≤c;n＞n∑i=1uij＞0,1≤j≤c。这里X={x1,x2,…,xn}⊂Rs是欧氏空间的s维数据集,n是数据集中样本个数,c是聚类中心数(1<c<n),m是权重系数(m>1),dij=‖xi-Vj‖是样本点xi和聚类中心Vj的距离,Vj⊂Rs(1≤j≤c)。uij是第i个样本属于第j类的隶属度,U=[uij]是一个n×c矩阵,V=[V1,V2,…,Vc]是一个s×c矩阵。在文献中,Bezdek提出解决上述数学规划问题的下列算法(记为FCM)。初始化选取ε>0,初始聚类中心V(1),令k=1。步骤1使用(1)和(2)两式计算U(k)如果∀i,r,dir(k)>0,则uij(k)=1/c∑r=1[(dij(k)/dir(k)2/(m-1)](1)如果存在i,r使得dir(k)=0,则uir(k)=1且对j≠r,uij(k)=0,(2)步骤2使用(3)计算V(k+1)∀jVj(k+1)=n∑i=1umij(k)xi/n∑i=1umij(k)(3)步骤3如果‖V(k)-V(k+1)‖<ε停止,否则令k=k+1,回到步骤1。2多维聚类分析方法—F统计量与伪F统计量在数理统计学的方差分析中,为了检验同方差的多个正态总体均值是否相等的问题,而引入了下面的F统计量,其目的是检验多个同方差的正态总体均值是否有显著差异。定义1F统计量为设方差分析中有关单因素试验的因素A有s个水平Aj(j=1,…,s),在给定水平Aj(j=1,…,s)下,进行了nj(nj≥2)次独立实验,实验观测值为yij(i=1,…,nj)。我们假定:各个水平Aj(j=1,…,s)下的样本yij(i=1,…,nj)来自具有同方差σ2,均值分别为μj(j=1,…,s)的正态总体N(μj,σ2),μj与σ2未知。且设不同水平Aj下的样本之间相互独立。方差分析的目的就是用F统计量检验s个正态总体N(μj,σ2)(j=1,…,s)的均值是否相等或存在显著差异。F=SA/(s-1)SE/(n-1)=s∑j=1nj∑i=1(ˉyj-ˉy)2⋅(n-s)s∑j=1nj∑i=1(yij-ˉy)2⋅(s-1)=s∑j=1nj(ˉyj-ˉy)2⋅(n-s)s∑j=1nj∑i=1(yij-ˉyj)2⋅(s-1)(4)其中n=s∑j=1nj,它表示所有不同水平Aj下的全部观测值总数;ˉy=1ns∑j=1nj∑i=1yij,它表示所有观测数据的总均值;ˉyj=1njnj∑i=1yij,它表示水平Aj下的样本平均值;SA=s∑j=1nj∑i=1(ˉyj-ˉy)2=s∑j=1nj(ˉyj-ˉy)2=s∑j=1nj(ˉyj)2-n(ˉy)2,它表示因素A在不同水平Aj(j=1,…,s)下的样本均值与数据总平均的差异之和,这是水平Aj(j=1,…,s)和随机误差引起的,SA叫做效应平方和;SE=s∑j=1nj∑i=1(yij-ˉyj)2,它表示所有不同水平Aj下,样本观测值与样本均值的差异,这是由随机误差引起的,SE叫做误差平方和;假设SΤ=s∑j=1nj∑i=1(yij-ˉy)2,它能反映全部实验数据之间的差异,因此ST又称为总变差。总变差ST与误差平方和SE以及效应平方和SA之间满足下面等式关系。ST=SE+SA(5)也即有∑j=1s∑i=1nj(yij-y¯)2=∑j=1s∑i=1nj(yij-y¯j)2+∑j=1s∑i=1nj(y¯j-y¯)2(6)数理统计学中的F统计量最早用于单因素试验中评判同方差正态分布样本均值之间是否有显著差异的统计量;但是,单因素试验并未要求试验观测值是1维数据,因而文献中谈到F统计量只适合1维数据样本,对多维数据样本采用混合F统计量的作法是不妥的。文献中为了样本聚类分析的需要,引入了F统计比率和伪F统计量两个概念,作为样本聚类评价准则和判定样本集最佳分类数的聚类有效性函数。定义2F统计比率为FS=SSB/(s-1)SSW/(n-s)=∑j=1s∑i=1nj(y¯j)2⋅(n-s)∑j=1s∑i=1n(yij-y¯j)2⋅(s-1)=∑j=1snj(y¯j)2⋅(n-s)∑j=1s∑i=1n(yij-y¯j)2⋅(s-1)(7)其中n=∑j=1snj,表示所有类的样本总数之和;nj表示第j类样本数;s表示类数;yij表示第j类中第i个样本;y¯=1n∑j=1s∑i=1njyij,它表示全部样本的均值;y¯j=1nj∑i=1njyij,它表示第j类的样本均值;SSB=∑j=1s∑i=1nj(y¯j)2=∑j=1snj⋅(y¯j)2,它并非反映数据样本偏差的信息;SSW=∑j=1s∑i=1nj(yij-y¯j)2,它反映了所有类的数据样本偏差信息;又假设SSΤ=∑j=1s∑i=1nj(yij)2,则SSB,SSW和SSW满足下面等式关系SST=SSW+SSB(8)也即有∑j=1s∑i=1nj(yij)2=∑j=1s∑i=1nj(yij-y¯j)2+∑j=1s∑i=1nj(y¯j)2(9)现在我们比较式(6)和(9),可以看出它们之间的差别在于:式(6)是反映不同类型偏差之间的关系,而式(9)并非反映了不同类型偏差之间的关系。数理统计中方差分析本质是研究相同试验水平下观测数据的偏差和不同水平下观测数据的偏差之间的关系,其F统计量是建立在观测数据的不同偏差基础之上,检测不同试验水平下观测数据的均值是否存在显著差别。文献中的F统计比率和推广到多维数据情形的伪F统计量都未完全反映数据样本的类内偏差和类间偏差之间的关系;严格地讲,文献中的F统计比率和推广到多维数据情形的伪F统计量都不是F统计量,甚至作者将不是F统计量的F统计比率在多维数据情形下才称为伪F统计量更无道理;同时,文献中也未澄清文献中的错误说法,直接将文献中的伪F统计量进行模糊化修改而提出了模糊伪F统计量。下面我们将研究数理统计学中的F统计量和文献中的F统计比率之间的紧密联系。因F统计量中的效应平方和为SA=∑j=1snj(y¯j)2-n(y¯)2,从而F统计量可以展开为F=∑j=1snj(y¯j-y¯)2⋅(n-s)∑j=1s∑i=1nj(yij-y¯j)2⋅(s-1)=∑j=1snj(y¯j)2⋅(n-s)∑j=1s∑i=1nj(yij-y¯j)2⋅(s-1)-n(y¯)2⋅(n-s)∑j=1s∑i=1nj(yij-y¯j)2⋅(s-1)这样可以得到数理统计学中的F统计量和文献中的F统计比率之间的关系为F=FS-n(y¯)2⋅(n-s)∑j=1s∑i=1nj(yij-y¯j)2⋅(s-1)(10)3模糊c-均值聚类算法聚类有效性分析在应用模糊C-均值聚类算法时,必须给定数据的分类数。为了确定数据集的分类数,文献中将文献用于方差分析的F统计量作为模糊C-均值聚类算法的聚类有效性函数。利用F统计量判定数据集的最佳分类数时,首先要对样本模糊聚类结果进行分明化(按照最大隶属度原则或最近邻原理)处理。定义1若数据具有分明分类信息条件下,判定数据最佳分类数的F统计量为F(c)=∑j=1cnj∥V′j-V0∥2*(n-c)∑j=1c∑i=1nj∥xij-V′j∥2*(c-1)(11)其中xij表示第j类中的第i个样本,V0=1n∑i=1nxi表示数据样本的平均中心;nj表示样本聚类成c类时,第j类中的样本个数;V′j=1nj∑i=1njxij表示样本聚类成c类时,第j类的平均中心;如果存在c*满足F(c*)=maxc{maxΩcF(c)}(Ωc表示数据样本分成c类时的所有可能划分的集合),则c*是数据样本的最佳分类数。式(11)与(4)在形式上完全一致,只不过它是式(4)在聚类有效性方面的具体应用和对多维数据样本情况下的推广。定义2若数据具有分明分类信息条件下,判定数据最佳分类数的伪F统计量为ΡF(c)=∑j=1cnj∥V′j∥2*(n-c)∑j=1c∑i=1nj∥xij-Vj∥2*(c-1)(12)其中xij表示第j类中的第i个样本,V0=1n∑i=1nxi表示数据样本的平均中心;nj表示样本聚类成c类时,第j类中的样本个数;Vj=1nj∑i=1njxij表示样本聚类成c类时,第j类的中心;如果存在c*满足F(c*)=maxc{maxΩcΡF(c)}(Ωc表示数据样本分成c类时的所有可能划分的集合),则c*是数据样本的最佳分类数。式(12)与式(7)在形式上完全一致,只不过它是式(7)在聚类有效性方面的具体应用和对多维数据情况下的推广。现将F统计量中的∑j=1cnj∥V′j-V0∥2展开分析,可以获得文献中的伪F统计量与F统计量之间的内在联系为F(c)=ΡF(c)-n⋅V0V0Τ*(n-c)∑j=1c∑i=1nj∥xi-V′j∥2*(c-1)(13)式(13)也可以看成是式(10)针对多维数据情况下的推广。若将式(12)作为模糊C-均值聚类算法的聚类有效性函数,必须将模糊C-均值聚类算法对数据模糊划分的结果按照最大隶属度或距离类中心最近原则进行样本分明归类后才能使用。数据经模糊C-均值聚类得到的模糊划分进行分明处理,必然要抹杀掉数据具有的模糊划分信息,同时也失去了与模糊C-均值聚类算法之间的联系;因此,文献将文献中的伪F统计量进行模糊化修改,提出了适合模糊C-均值聚类算法的聚类有效性函数。定义3模糊伪F统计量为FPF(U;c)=∑j=1c∑i=1nuijm∥Vj∥2*(n-c)∑j=1c∑i=1nuijm∥xi-Vj∥2*(c-1)(14)其中第j类的中心Vj是由模糊C-均值聚类算法的公式Vj=∑i=1nuijmxi∑i=1nuijm得到的。如果存在(U*;c*)满足FPF(U*;c*)=maxc{maxΩcFΡF(U;c)}(Ωc表示数据样本分成c类时的所有可能划分的集合),则(U*;c*)是样本最佳的有效聚类;c*是数据样本的最佳分类数。模糊伪F统计量利用了模糊C-均值聚类算法的目标函数,使得模糊伪F统计量与数据样本模糊划分紧密相关,并能够处理数据带有模糊分类信息的分类数判定。但是,式(14)的分母表达式反映了数据类内紧致性程度,分子表达式并未完全反映数据类间分离性程度,从而导致该函数作为聚类有效性函数的分类性能并非很理想。本文针对这一事实,直接将数理统计学中的F统计量进行了模糊化修改,得到下面的模糊F统计量。定义4模糊F统计量为FF(U;c)=∑j=1c∑i=1nuijm∥Vj-V0∥2*(n-c)∑j=1c∑i=1nuijm∥xi-Vj∥2*(c-1)(15)如果存在(U*;c*)满足FF(U*;c*)=maxc{maxΩcFF(U;c)}(Ωc表示数据样本分成c类时的所有可能划分的集合),则(U*;c*)是样本最佳的有效聚类,c*是数据样本的最佳分类数。将聚类目标函数∑j=1c∑i=1nuijm∥xi-Vj∥2中的‖xi-Vj‖2展开为‖xi-V0+V0-Vj‖2,可以得到下面等式∑j=1c∑i=1nuijm⋅∥xi-Vj∥2=∑j=1c∑i=1nuijm⋅∥xi-V0∥2-∑j=1c∑i=1nuijm⋅∥Vj-V0∥2(16)模糊F统计量不仅利用了模糊C-均值聚类算法的目标函数;而且,也利用等式(16)中由目标函数推导出反映数据类间分离性程度的函数∑j=1c∑i=1njuijm∥Vj-V0∥2。这样使得模糊F统计量处理数据带有模糊分类信息的分类数判定比模糊伪F统计量更加有效。现将模糊F统计量的∑j=1c∑i=1nuijm∥Vj-V0∥2进行展开分析,可以得到它与模糊伪F统计量之间的内在联系为FF(U;c)=FPF(U;c)-∑j=1c∑i=1nuijm(2V0*-V0)V0Τ*(n-c)∑j=1c∑i=1nuijm∥xi-Vj∥2*(c-1)(17)其中V0=1n∑i=1nxi=∑j=1c∑i=1nuijxi∑j=1c∑i=1nuij;V0*=∑j=1c(∑i=1nuijm)Vj∑j=1c∑i=1nuijm=∑j=1c(∑i=1nuijmxi)∑j=1c∑i=1nuijm。在式(17)中,当m∈(1,+∞)时,有∑j=1c∑i=1nuijm(2V0*-V0)V0Τ≈∑j=1c∑i=1nuijmV0V0Τ的结论。通过比较式(17)和式(13),可以认为式(17)是式(13)在模糊情况下的拓广和延伸,从而更加证实将数理统计中用于方差分析的F统计量进行模糊法修改是可行的。4数据处理在文中,Pal和Bezdek讨论了权重因子m对FCM聚类有效性的影响,指出m的取值范围可选为[1.5,2.5]。本节,我们通过3个人造数据和著名的IRIS数据来测试F(c)、PF(c)、FPF(U;c)和FF(U;c)的分类性能。为了方便,我们限制最大分类数cmax=10且选择权重因子的三个典型值m=1.5,m=2.0和m=2.5。具体实验时,我们采用随机初始化聚类中心法对数据样本进行聚类,从10次不同初始化聚类中心所得结果中选取最优划分。表1给出了不同聚类有效性函数对数据样本分类数的检测情况。5类数据:由均值分别为(0,0),(0,2),(2,0),(2,2),(1,1),各维方差均为0.5或0.7的正态分布生成的平面数据。每类30个样本,共计150个数据样本。图1给出方差为0.5时数据的分布图,该数据应分为5类。从表1来看,F(c)、PF(c)、FPF(U;c)和FF(U;c)都能检测出该数据的实际分类数。立方体数据:由均值分别为(1,0,0)、(0,1,0)、(0,0,1)和