模糊c-均值聚類算法的f統(tǒng)計量

模糊c-均值聚類算法的f統(tǒng)計量

模糊f統(tǒng)計量與模糊聚類有效性聚類分析是一種重要的方法。最著名、最常用的模糊聚類算法是模糊c-中旬聚類算法（rcm）。當(dāng)使用模糊聚類算法時,一個事先必須確定的參數(shù)是數(shù)據(jù)集的分類數(shù)。這個問題屬于“聚類有效性問題”。到目前為止,已提出了多種聚類有效性標(biāo)準(zhǔn)。文獻中Hubert的Γ統(tǒng)計量就是最早基于統(tǒng)計信息而被應(yīng)用于分類數(shù)判決的有效性函數(shù),文獻中比較系統(tǒng)地研究了Hubert的Γ統(tǒng)計量的使用效果,文獻中針對Hubert的Γ統(tǒng)計量的不足提出了修改的Γ統(tǒng)計量,文獻中也對修改的Γ統(tǒng)計量的使用效果作了盡一步的實驗研究。由于Γ統(tǒng)計量是通過對數(shù)據(jù)的分布本身與聚類算法對數(shù)據(jù)得到的劃分之間的匹配程度來判定數(shù)據(jù)的分類情況,這實際上對數(shù)據(jù)強加人為的假設(shè)而造成實際使用中很難有效。文獻中提出了基于數(shù)據(jù)集的類內(nèi)統(tǒng)計信息和類間統(tǒng)計信息的偽F統(tǒng)計量用于數(shù)據(jù)聚類分析,并能在聚類過程中確定數(shù)據(jù)集的最佳分類數(shù)。文獻中將數(shù)理統(tǒng)計學(xué)中的F統(tǒng)計量用于數(shù)據(jù)劃分最佳分類數(shù)的確定。文獻中針對數(shù)理統(tǒng)計學(xué)中的F統(tǒng)計量不適合多維數(shù)據(jù)而提出了混合F統(tǒng)計量。由于Γ統(tǒng)計量、偽F統(tǒng)計量、F統(tǒng)計量以及混合F統(tǒng)計量等對數(shù)據(jù)帶有模糊性分類的情況很難湊效,甚至要將數(shù)據(jù)模糊性分類的結(jié)果進行分明處理后,才能使用這些基于分明統(tǒng)計信息的聚類有效性函數(shù),勢必造成要抹殺數(shù)據(jù)模糊性分類的許多細節(jié)信息,將給實際最佳分類數(shù)的判定造成不利和不便。文獻將文獻中的偽F統(tǒng)計量進行模糊化修改,提出了適合模糊C-均值聚類算法的模糊偽F統(tǒng)計量的聚類有效性函數(shù),就能夠處理數(shù)據(jù)具有模糊分類情況的最佳分類的確定。本文將文獻中用于方差分析的F統(tǒng)計量模糊化修改,也提出了適合模糊C-均值聚類算法的模糊F統(tǒng)計量的聚類有效性函數(shù)。模糊F統(tǒng)計量不僅能夠處理數(shù)據(jù)具有模糊分類情況的最佳分類數(shù)的判決;而且,它的分類性能比模糊偽F統(tǒng)計量要好。1基于fcm的聚類中心數(shù)的規(guī)劃算法模糊聚類問題可表示成下面的數(shù)學(xué)規(guī)劃問題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維數(shù)據(jù)集,n是數(shù)據(jù)集中樣本個數(shù),c是聚類中心數(shù)(1<c<n),m是權(quán)重系數(shù)(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提出解決上述數(shù)學(xué)規(guī)劃問題的下列算法(記為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統(tǒng)計量與偽F統(tǒng)計量在數(shù)理統(tǒng)計學(xué)的方差分析中,為了檢驗同方差的多個正態(tài)總體均值是否相等的問題,而引入了下面的F統(tǒng)計量,其目的是檢驗多個同方差的正態(tài)總體均值是否有顯著差異。定義1F統(tǒng)計量為設(shè)方差分析中有關(guān)單因素試驗的因素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)的正態(tài)總體N(μj,σ2),μj與σ2未知。且設(shè)不同水平Aj下的樣本之間相互獨立。方差分析的目的就是用F統(tǒng)計量檢驗s個正態(tài)總體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下的全部觀測值總數(shù);ˉy=1ns∑j=1nj∑i=1yij,它表示所有觀測數(shù)據(jù)的總均值;ˉ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)下的樣本均值與數(shù)據(jù)總平均的差異之和,這是水平Aj(j=1,…,s)和隨機誤差引起的,SA叫做效應(yīng)平方和;SE=s∑j=1nj∑i=1(yij-ˉyj)2,它表示所有不同水平Aj下,樣本觀測值與樣本均值的差異,這是由隨機誤差引起的,SE叫做誤差平方和;假設(shè)SΤ=s∑j=1nj∑i=1(yij-ˉy)2,它能反映全部實驗數(shù)據(jù)之間的差異,因此ST又稱為總變差?？傋儾頢T與誤差平方和SE以及效應(yīng)平方和SA之間滿足下面等式關(guān)系。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)數(shù)理統(tǒng)計學(xué)中的F統(tǒng)計量最早用于單因素試驗中評判同方差正態(tài)分布樣本均值之間是否有顯著差異的統(tǒng)計量;但是,單因素試驗并未要求試驗觀測值是1維數(shù)據(jù),因而文獻中談到F統(tǒng)計量只適合1維數(shù)據(jù)樣本,對多維數(shù)據(jù)樣本采用混合F統(tǒng)計量的作法是不妥的。文獻中為了樣本聚類分析的需要,引入了F統(tǒng)計比率和偽F統(tǒng)計量兩個概念,作為樣本聚類評價準(zhǔn)則和判定樣本集最佳分類數(shù)的聚類有效性函數(shù)。定義2F統(tǒng)計比率為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,表示所有類的樣本總數(shù)之和;nj表示第j類樣本數(shù);s表示類數(shù);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,它并非反映數(shù)據(jù)樣本偏差的信息;SSW=∑j=1s∑i=1nj(yij-yˉj)2,它反映了所有類的數(shù)據(jù)樣本偏差信息;又假設(shè)SSΤ=∑j=1s∑i=1nj(yij)2,則SSB,SSW和SSW滿足下面等式關(guān)系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)現(xiàn)在我們比較式(6)和(9),可以看出它們之間的差別在于:式(6)是反映不同類型偏差之間的關(guān)系,而式(9)并非反映了不同類型偏差之間的關(guān)系。數(shù)理統(tǒng)計中方差分析本質(zhì)是研究相同試驗水平下觀測數(shù)據(jù)的偏差和不同水平下觀測數(shù)據(jù)的偏差之間的關(guān)系,其F統(tǒng)計量是建立在觀測數(shù)據(jù)的不同偏差基礎(chǔ)之上,檢測不同試驗水平下觀測數(shù)據(jù)的均值是否存在顯著差別。文獻中的F統(tǒng)計比率和推廣到多維數(shù)據(jù)情形的偽F統(tǒng)計量都未完全反映數(shù)據(jù)樣本的類內(nèi)偏差和類間偏差之間的關(guān)系;嚴(yán)格地講,文獻中的F統(tǒng)計比率和推廣到多維數(shù)據(jù)情形的偽F統(tǒng)計量都不是F統(tǒng)計量,甚至作者將不是F統(tǒng)計量的F統(tǒng)計比率在多維數(shù)據(jù)情形下才稱為偽F統(tǒng)計量更無道理;同時,文獻中也未澄清文獻中的錯誤說法,直接將文獻中的偽F統(tǒng)計量進行模糊化修改而提出了模糊偽F統(tǒng)計量。下面我們將研究數(shù)理統(tǒng)計學(xué)中的F統(tǒng)計量和文獻中的F統(tǒng)計比率之間的緊密聯(lián)系。因F統(tǒng)計量中的效應(yīng)平方和為SA=∑j=1snj(yˉj)2-n(yˉ)2,從而F統(tǒng)計量可以展開為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)這樣可以得到數(shù)理統(tǒng)計學(xué)中的F統(tǒng)計量和文獻中的F統(tǒng)計比率之間的關(guān)系為F=FS-n(yˉ)2?(n-s)∑j=1s∑i=1nj(yij-yˉj)2?(s-1)(10)3模糊c-均值聚類算法聚類有效性分析在應(yīng)用模糊C-均值聚類算法時,必須給定數(shù)據(jù)的分類數(shù)。為了確定數(shù)據(jù)集的分類數(shù),文獻中將文獻用于方差分析的F統(tǒng)計量作為模糊C-均值聚類算法的聚類有效性函數(shù)。利用F統(tǒng)計量判定數(shù)據(jù)集的最佳分類數(shù)時,首先要對樣本模糊聚類結(jié)果進行分明化(按照最大隸屬度原則或最近鄰原理)處理。定義1若數(shù)據(jù)具有分明分類信息條件下,判定數(shù)據(jù)最佳分類數(shù)的F統(tǒng)計量為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表示數(shù)據(jù)樣本的平均中心;nj表示樣本聚類成c類時,第j類中的樣本個數(shù);V′j=1nj∑i=1njxij表示樣本聚類成c類時,第j類的平均中心;如果存在c*滿足F(c*)=maxc{maxΩcF(c)}(Ωc表示數(shù)據(jù)樣本分成c類時的所有可能劃分的集合),則c*是數(shù)據(jù)樣本的最佳分類數(shù)。式(11)與(4)在形式上完全一致,只不過它是式(4)在聚類有效性方面的具體應(yīng)用和對多維數(shù)據(jù)樣本情況下的推廣。定義2若數(shù)據(jù)具有分明分類信息條件下,判定數(shù)據(jù)最佳分類數(shù)的偽F統(tǒng)計量為Ρ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表示數(shù)據(jù)樣本的平均中心;nj表示樣本聚類成c類時,第j類中的樣本個數(shù);Vj=1nj∑i=1njxij表示樣本聚類成c類時,第j類的中心;如果存在c*滿足F(c*)=maxc{maxΩcΡF(c)}(Ωc表示數(shù)據(jù)樣本分成c類時的所有可能劃分的集合),則c*是數(shù)據(jù)樣本的最佳分類數(shù)。式(12)與式(7)在形式上完全一致,只不過它是式(7)在聚類有效性方面的具體應(yīng)用和對多維數(shù)據(jù)情況下的推廣。現(xiàn)將F統(tǒng)計量中的∑j=1cnj∥V′j-V0∥2展開分析,可以獲得文獻中的偽F統(tǒng)計量與F統(tǒng)計量之間的內(nèi)在聯(lián)系為F(c)=ΡF(c)-n?V0V0Τ*(n-c)∑j=1c∑i=1nj∥xi-V′j∥2*(c-1)(13)式(13)也可以看成是式(10)針對多維數(shù)據(jù)情況下的推廣。若將式(12)作為模糊C-均值聚類算法的聚類有效性函數(shù),必須將模糊C-均值聚類算法對數(shù)據(jù)模糊劃分的結(jié)果按照最大隸屬度或距離類中心最近原則進行樣本分明歸類后才能使用。數(shù)據(jù)經(jīng)模糊C-均值聚類得到的模糊劃分進行分明處理,必然要抹殺掉數(shù)據(jù)具有的模糊劃分信息,同時也失去了與模糊C-均值聚類算法之間的聯(lián)系;因此,文獻將文獻中的偽F統(tǒng)計量進行模糊化修改,提出了適合模糊C-均值聚類算法的聚類有效性函數(shù)。定義3模糊偽F統(tǒng)計量為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表示數(shù)據(jù)樣本分成c類時的所有可能劃分的集合),則(U*;c*)是樣本最佳的有效聚類;c*是數(shù)據(jù)樣本的最佳分類數(shù)。模糊偽F統(tǒng)計量利用了模糊C-均值聚類算法的目標(biāo)函數(shù),使得模糊偽F統(tǒng)計量與數(shù)據(jù)樣本模糊劃分緊密相關(guān),并能夠處理數(shù)據(jù)帶有模糊分類信息的分類數(shù)判定。但是,式(14)的分母表達式反映了數(shù)據(jù)類內(nèi)緊致性程度,分子表達式并未完全反映數(shù)據(jù)類間分離性程度,從而導(dǎo)致該函數(shù)作為聚類有效性函數(shù)的分類性能并非很理想。本文針對這一事實,直接將數(shù)理統(tǒng)計學(xué)中的F統(tǒng)計量進行了模糊化修改,得到下面的模糊F統(tǒng)計量。定義4模糊F統(tǒng)計量為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表示數(shù)據(jù)樣本分成c類時的所有可能劃分的集合),則(U*;c*)是樣本最佳的有效聚類,c*是數(shù)據(jù)樣本的最佳分類數(shù)。將聚類目標(biāo)函數(shù)∑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統(tǒng)計量不僅利用了模糊C-均值聚類算法的目標(biāo)函數(shù);而且,也利用等式(16)中由目標(biāo)函數(shù)推導(dǎo)出反映數(shù)據(jù)類間分離性程度的函數(shù)∑j=1c∑i=1njuijm∥Vj-V0∥2。這樣使得模糊F統(tǒng)計量處理數(shù)據(jù)帶有模糊分類信息的分類數(shù)判定比模糊偽F統(tǒng)計量更加有效?，F(xiàn)將模糊F統(tǒng)計量的∑j=1c∑i=1nuijm∥Vj-V0∥2進行展開分析,可以得到它與模糊偽F統(tǒng)計量之間的內(nèi)在聯(lián)系為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)中,當(dāng)m∈(1,+∞)時,有∑j=1c∑i=1nuijm(2V0*-V0)V0Τ≈∑j=1c∑i=1nuijmV0V0Τ的結(jié)論。通過比較式(17)和式(13),可以認為式(17)是式(13)在模糊情況下的拓廣和延伸,從而更加證實將數(shù)理統(tǒng)計中用于方差分析的F統(tǒng)計量進行模糊法修改是可行的。4數(shù)據(jù)處理在文中,Pal和Bezdek討論了權(quán)重因子m對FCM聚類有效性的影響,指出m的取值范圍可選為[1.5,2.5]。本節(jié),我們通過3個人造數(shù)據(jù)和著名的IRIS數(shù)據(jù)來測試F(c)、PF(c)、FPF(U;c)和FF(U;c)的分類性能。為了方便,我們限制最大分類數(shù)cmax=10且選擇權(quán)重因子的三個典型值m=1.5,m=2.0和m=2.5。具體實驗時,我們采用隨機初始化聚類中心法對數(shù)據(jù)樣本進行聚類,從10次不同初始化聚類中心所得結(jié)果中選取最優(yōu)劃分。表1給出了不同聚類有效性函數(shù)對數(shù)據(jù)樣本分類數(shù)的檢測情況。5類數(shù)據(jù):由均值分別為(0,0),(0,2),(2,0),(2,2),(1,1),各維方差均為0.5或0.7的正態(tài)分布生成的平面數(shù)據(jù)。每類30個樣本,共計150個數(shù)據(jù)樣本。圖1給出方差為0.5時數(shù)據(jù)的分布圖,該數(shù)據(jù)應(yīng)分為5類。從表1來看,F(c)、PF(c)、FPF(U;c)和FF(U;c)都能檢測出該數(shù)據(jù)的實際分類數(shù)。立方體數(shù)據(jù):由均值分別為(1,0,0)、(0,1,0)、(0,0,1)和