張 鴻

（船舶重工集團(tuán)公司723所，揚(yáng)州225001）

0 引 言

聚類(lèi)分析是多元統(tǒng)計(jì)分析的方法之一，是統(tǒng)計(jì)模式識(shí)別中非監(jiān)督模式分類(lèi)的一個(gè)重要分支［1］。分類(lèi)模式識(shí)別常采用基于歐式距離的最近鄰分類(lèi)器來(lái)實(shí)現(xiàn)。在一般歐式距離中，樣本在個(gè)體特征上的差異對(duì)總距離的貢獻(xiàn)是相同的，對(duì)樣本分類(lèi)所起的作用也是相同的。但是對(duì)象間的距離表示對(duì)象的相近程度，而相似不僅依賴(lài)于對(duì)象間的相似程度，還依賴(lài)于對(duì)象內(nèi)的性質(zhì)，即對(duì)象中每個(gè)變量的重要性是不同的，對(duì)樣本分類(lèi)所起的作用也有所不同。原則上，對(duì)每個(gè)模式知道的信息越多，聚類(lèi)的效果應(yīng)該越好。然而在實(shí)踐中并非如此。有些特征可能是噪音數(shù)據(jù)，這些噪音數(shù)據(jù)對(duì)聚類(lèi)結(jié)果沒(méi)有貢獻(xiàn)甚至可能降低聚類(lèi)效果。

模糊C均值聚類(lèi)（FCM）分析就是一種有效的聚類(lèi)分析方法，在非監(jiān)督模式識(shí)別、模糊控制等領(lǐng)域有著極為廣泛的應(yīng)用［2］。原始的FCM假定待分析樣本的各維特征對(duì)分類(lèi)的貢獻(xiàn)均勻，不考慮各個(gè)特征對(duì)分類(lèi)的不同作用。

利用特征權(quán)值對(duì)分類(lèi)器的距離計(jì)算進(jìn)行加權(quán)，對(duì)樣本分類(lèi)越有利的特征權(quán)值越大，樣本在該特征維上即使出現(xiàn)微小的差異也會(huì)因較大的加權(quán)對(duì)歐式距離的計(jì)算產(chǎn)生較大的影響。因此，采用特征加權(quán)的歐式距離進(jìn)行最近鄰分類(lèi)可以取得更好的分類(lèi)效果［3］。所以本文比較了基于不同的特征權(quán)值計(jì)算方法的加權(quán)FCM的聚類(lèi)效果，并最終提出了一種改進(jìn)的ReliefF算法加權(quán)FCM聚類(lèi)算法。

1 特征權(quán)重計(jì)算方法

1.1 基于信息增益的特征權(quán)重計(jì)算方法

信息增益（IG）特征權(quán)重計(jì)算方法是最簡(jiǎn)單的特征評(píng)價(jià)方法［3］。

令W為樣本實(shí)例的第n個(gè)特征，M為該樣本實(shí)例的類(lèi)變量。在觀(guān)察到W前后，類(lèi)變量M的墑為：

式中：a＝1，2，…，n；c＝1，2，…，C，C 為數(shù)據(jù)集所分成的類(lèi)別。

在觀(guān)察到W 后，類(lèi)變量M的墑的減少量反映了特征W 所承載的關(guān)于W 的信息量，即為信息增益［3］：

1.2 原始ReliefF算法

對(duì)于任意一個(gè)樣本實(shí)例xi，基本的ReliefF算法可以表示為：

首先找出k個(gè)與xi同類(lèi)的最近鄰的樣本實(shí)例集合H。設(shè)diff＿h(yuǎn)it（A，x，H）是n×1矩陣，表示對(duì)象xi與H內(nèi)各對(duì)象在樣本屬性特征A上的差異量化表示：

式中：j＝1，2，3，…，k。

其次找出與xi不同類(lèi)的樣本實(shí)例中k個(gè)最近鄰的樣本集合 M（c）。設(shè) diff＿miss［A，xi，M（c）］是n×1矩陣，為xi在與M（c）內(nèi)各對(duì)象在樣本屬性特征A上的差異量化表示：

設(shè)輸入：訓(xùn)練樣本集X，最近鄰樣本個(gè)數(shù)k，重復(fù)累積次數(shù)m；輸出：樣本特征權(quán)重值矩陣W。由上述描述可以得到基本的ReliefF算法基本步驟如下：

（1）設(shè)置所有的屬性權(quán)重值；（2）for i：＝1to m；

（3）隨機(jī)選擇一個(gè)樣本實(shí)例；

（4）找到與樣本同類(lèi)的k個(gè)最近鄰樣本集合H；

（5）for each class c≠class（xi）；

（6）找到與樣本xi不同類(lèi)的k個(gè)最近鄰樣本集合M（c）；

（7）for A：＝1to n；

（8）W［A］：＝ W［A］－diff＿h(yuǎn)it（A，xi，H）／（k·m）＋diff＿miss［A，xi，M（c）］／（k·m）；

（9）end。

在上述偽代碼中，H表示與對(duì)象同類(lèi)的k個(gè)最近鄰的對(duì)象集合，M（c）表示與對(duì)象不同類(lèi)的k個(gè)最近鄰對(duì)象集合，diff＿h(yuǎn)it（A，xi，H）為對(duì)象xi與H內(nèi)各對(duì)象在特征A 上的差異量化表示，diff＿miss（A，xi，M）表示對(duì)象xi與M（c）內(nèi)各對(duì)象在特征A上的差異量化表示，上述兩公式的計(jì)算方式見(jiàn)公式（4）、（5）。

1.3 改進(jìn)的ReliefF算法

要對(duì)樣本屬性權(quán)重值做出最有效的評(píng)估，必須使選取的累積樣本盡量均勻地覆蓋于每個(gè)樣本類(lèi)別的整個(gè)樣本數(shù)據(jù)集中。如果ReliefF算法不能確保選取的樣本均勻地覆蓋于每個(gè)樣本類(lèi)別的整個(gè)樣本數(shù)據(jù)集中，必然會(huì)造成下列的一些問(wèn)題：

首先基本ReliefF算法重復(fù)了m次從訓(xùn)練樣本集中隨機(jī)挑選樣本xi的操作，m一般要遠(yuǎn)小于樣本總數(shù)量。如果原始數(shù)據(jù)集的樣本集中在某幾個(gè)類(lèi)別中，按照基本的ReliefF算法隨機(jī)選擇樣本數(shù)，必然會(huì)造成以下的缺點(diǎn)：屬性權(quán)重值向樣本數(shù)量多的類(lèi)別傾斜。包含樣本數(shù)較多的類(lèi)別其樣本點(diǎn)被隨機(jī)選中的概率較大，與該類(lèi)別相關(guān)的屬性權(quán)重值累積就會(huì)較高。反之，一些樣本數(shù)較少的類(lèi)別由于其樣本點(diǎn)被選中的幾率小，即使有對(duì)分類(lèi)起明顯作用的屬性權(quán)重值也會(huì)因?yàn)槔鄯e少而被掩蓋［2］。

其次由于F次迭代使用的樣本都是隨機(jī)選擇的，即使是同一組訓(xùn)練樣本集，每運(yùn)行一次該算法，算法隨機(jī)選中的樣本點(diǎn)都不可能完全相同，這樣造成的累積的屬性權(quán)重值也有波動(dòng)。

由于基本的ReliefF算法存在上述缺點(diǎn)，通過(guò)上述算法計(jì)算出來(lái)的屬性特征權(quán)值必然存在一定的偏差，所以本文提出了改進(jìn)的ReliefF算法（IReliefF）。由于基本ReliefF算法的不足之處主要體現(xiàn)在樣本點(diǎn)的選擇上，本文采取下列措施來(lái)對(duì)樣本點(diǎn)選擇方法進(jìn)行改進(jìn)：為保證每類(lèi)樣本均可參與權(quán)值計(jì)算，在選擇樣本時(shí)，從每類(lèi)目標(biāo)樣本分別各抽取m個(gè)樣本點(diǎn)用于屬性特征權(quán)重值的累積。改進(jìn)的樣本點(diǎn)選擇步驟如下：

（1）計(jì)算每一類(lèi)樣本的樣本中心點(diǎn)Xd；

（2）計(jì)算該類(lèi)中樣本點(diǎn)與該樣本中心點(diǎn)的歐式距離；

（3）根據(jù)Xd大小，把該類(lèi)樣本分成f組，每組間隔歐式距離大小為 Δd，Δd＝ ［max（Xd）－min（Xd）］／f ；

（4）在分出的F組的每一組，取中間的樣本做ReliefF分析。

結(jié)合基本的ReliefF算法和上述樣本點(diǎn)選擇辦法，得到了IReliefF算法的基本步驟如下：

（1）設(shè)置所有的屬性權(quán)重值；

（2）for each class，ci，i＝1，2，…，T；

（3）計(jì)算該類(lèi)中樣本點(diǎn)與該樣本中心點(diǎn)的歐式距離dij；

（4）根據(jù)dij大小，計(jì)算每組間隔歐式距離Δd；

（5）選擇距離組內(nèi)的中間樣本xj；

（6）for each xj，j＝1，2，3，…，f；

（7）找到與樣本xi同類(lèi)的k個(gè)最近鄰樣本集合H；

（8）for each class c≠class（xi）do；

（9）找到與樣本xi不同類(lèi)的k個(gè)最近鄰樣本集合 M（c）；

（10）for A：＝ 1to n do，W［A］：＝W［A］－diff＿h(yuǎn)it（A，xi，H）／（f·k·T）＋diff＿miss［A，xi，M（c）］／（f·k·T）；

（11）end。

IReliefF算法可以計(jì)算樣本屬性權(quán)重值矩陣W。權(quán)重值的取值范圍在［－1，1］區(qū)間，值越高的特征對(duì)分類(lèi)越有利，值為負(fù)的特征則不利于分類(lèi)，并且可以得到穩(wěn)定的W。

2 加權(quán)的模糊C均值聚類(lèi)算法

原則上，對(duì)每個(gè)模式知道的信息越多，聚類(lèi)的效果應(yīng)該越好。然而在實(shí)踐中并非如此。有些特征可能是噪音數(shù)據(jù)，這些噪音數(shù)據(jù)對(duì)聚類(lèi)結(jié)果沒(méi)有貢獻(xiàn)甚至可能降低聚類(lèi)效果。參考文獻(xiàn)［3］提到學(xué)習(xí)屬性權(quán)值可以普遍提高聚類(lèi)質(zhì)量，學(xué)習(xí)屬性權(quán)值使無(wú)關(guān)屬性的影響盡量減小，甚至權(quán)值可以為零。所以本文提出用基于IG和改進(jìn)的ReliefF算法來(lái)計(jì)算數(shù)據(jù)特征的權(quán)重值，提出加權(quán)的FCM（WFCM）來(lái)提高聚類(lèi)質(zhì)量，盡量減少噪音數(shù)據(jù)的影響。

在Dunn提出的C－MEANS距離算法的基礎(chǔ)上，Bezedk加以推廣［7］，提出了模糊 C－均值聚類(lèi)算法。FCM是一個(gè)典型的基于距離的聚類(lèi)算法。該算法具有簡(jiǎn)單、高效的特點(diǎn)，并能收斂于局部最優(yōu)解。

FCM的目標(biāo)是使價(jià)值函數(shù)J值達(dá)到最小，價(jià)值函數(shù)J的定義為：

式中：m∈［1，＋∞］，為一個(gè)加權(quán)指數(shù)，隨著m的增大，聚類(lèi)的模糊性增大；N為樣本數(shù)據(jù)集的個(gè)數(shù)；μij為第j個(gè)樣本點(diǎn)隸屬于第i類(lèi)的概率值。

加權(quán)的歐式距離為：

加權(quán)的FCM（WFCM）算法的目標(biāo)函數(shù)為：

式中：w（t）為各個(gè)屬性的權(quán)重值。

WFCM算法實(shí)現(xiàn)基本步驟如下：

（1）設(shè)置隸屬度矩陣U 到［0，1］；

（2）for i：＝1to c do；

（3）找到聚類(lèi)中心vi；

（4）end；

（5）for j：＝1to maxiter；

（6）計(jì)算目標(biāo)函數(shù)值J；

（7）如果2次循環(huán)的目標(biāo)函數(shù)值差值小于設(shè)定值；

（8）break；

（9）更新隸屬度矩陣U；

（10）end。

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)際試驗(yàn)數(shù)據(jù)選用UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)，該數(shù)據(jù)庫(kù)是由加州大學(xué)提供，從中選擇Iris、Disbetes等2個(gè)數(shù)據(jù)集，如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集

3.2 實(shí)驗(yàn)分析

本實(shí)驗(yàn)從分類(lèi)正確率和分類(lèi)標(biāo)準(zhǔn)差指標(biāo)方面，在本實(shí)驗(yàn)數(shù)據(jù)集上對(duì) ReliefF－WFCM、IReliefFWFCM、IG－WFCM以及原始FCM等4種聚類(lèi)方法的性能進(jìn)行比較。

ReliefF－WFCM表示使用原始的ReliefF算法進(jìn)行加權(quán)的FCM，IReliefF－WFCM表示使用改進(jìn)的ReliefF算法進(jìn)行加權(quán)的FCM，IG－WFCM表示利用信息增益算法進(jìn)行進(jìn)行加權(quán)的FCM，F(xiàn)CM表示使用原始的模糊C均值聚類(lèi)。

對(duì)于基本的ReliefF算法，本實(shí)驗(yàn)選擇從訓(xùn)練樣本集合中隨機(jī)抽取的用于特征累積的樣本數(shù)量m占到樣本數(shù)據(jù)集總樣本數(shù)的20%，樣本最近鄰數(shù)k＝10，基本的ReliefF算法每次的結(jié)果不同，本實(shí)驗(yàn)選取10次結(jié)果的平均值作為最終的平均值。對(duì)于IReliefF算法，每類(lèi)抽取的樣本點(diǎn)數(shù)為m／c，從而保證2種算法的抽取樣本點(diǎn)數(shù)一致。樣本最近鄰數(shù)k＝10，m為基本ReliefF算法抽取的樣本點(diǎn)數(shù)，c為樣本數(shù)據(jù)集的類(lèi)別數(shù)。

為了使實(shí)驗(yàn)結(jié)果更加可靠，本實(shí)驗(yàn)采取5折交叉驗(yàn)證的方式。n折交叉驗(yàn)證原理：n就是要拆成幾組。對(duì)于k個(gè)子集，每個(gè)子集均做一次測(cè)試集，其余的作為訓(xùn)練集。交叉驗(yàn)證重復(fù)k次，每次選擇一個(gè)子集作為測(cè)試集，并將k次的平均交叉驗(yàn)證正確率作為結(jié)果。

由表2、表3可得，IG－WFCM、ReliefF－WFCM和IReliefF－WFCM最終得到的誤分率指標(biāo)和標(biāo)準(zhǔn)差指標(biāo)都要優(yōu)于原始的FCM聚類(lèi)算法，從而可驗(yàn)證學(xué)習(xí)屬性權(quán)值確實(shí)可以普遍提高聚類(lèi)質(zhì)量。

表2 數(shù)據(jù)集Iris聚類(lèi)結(jié)果分析

表3 數(shù)據(jù)集Disbetes聚類(lèi)結(jié)果分析

通過(guò)對(duì)IG－WFCM、ReliefF－WFCM、IReliefFWFCM聚類(lèi)結(jié)果的比較可以看出：在誤分率指標(biāo)方面，ReliefF－WFCM、IReliefF－WFCM 聚類(lèi)效果要比IG－WFCM的聚類(lèi)效果好；但是在標(biāo)準(zhǔn)差指標(biāo)方面，IG－WFCM的聚類(lèi)效果要優(yōu)于ReliefF－WFCM，仍然劣于IReliefF－WFCM的聚類(lèi)效果。從而驗(yàn)證了基本ReliefF算法的缺點(diǎn)：得到的屬性權(quán)重值不穩(wěn)定，從而造成加權(quán)FCM結(jié)果不穩(wěn)定。

聚類(lèi)結(jié)果無(wú)論是在誤分率指標(biāo)還是在標(biāo)準(zhǔn)差指標(biāo)上，IReliefF－WFCM算法的誤分率和標(biāo)準(zhǔn)差都比較小，數(shù)值變化幅度也比較小，從而說(shuō)明該算法的性能比較穩(wěn)定。IReliefF－WFCM驗(yàn)證了較高的聚類(lèi)精度?；诟倪M(jìn)ReliefF算法的加權(quán)FCM的聚類(lèi)效果要優(yōu)于基于基本ReliefF算法的加權(quán)FCM。

4 結(jié)束語(yǔ)

本文提出了一種基于改進(jìn)的ReliefF算法的加權(quán)FCM（IReliefF－WFCM）聚類(lèi)方法，對(duì)基本 ReliefF算法樣本選擇方法實(shí)現(xiàn)了改進(jìn)。實(shí)驗(yàn)結(jié)果表明，該算法減少了基本FCM聚類(lèi)結(jié)果的誤分率和標(biāo)準(zhǔn)差，提高了FCM聚類(lèi)結(jié)果的精度和穩(wěn)定性，為以后該算法用于實(shí)際數(shù)據(jù)處理打下了堅(jiān)實(shí)基礎(chǔ)。

［1］何清.模糊聚類(lèi)分析理論與應(yīng)用研究進(jìn)展［J］.模糊系統(tǒng)與數(shù)學(xué)，1998，12（2）：89－94.

［2］李潔，高新波，焦李成.基于特征加權(quán)的模糊聚類(lèi)新算法［J］.電子學(xué)報(bào)，2006，34（1）：89－92.

［3］高瀅，劉大有，徐益.一種特征加權(quán)的聚類(lèi)算法框架［J］.計(jì)算機(jī)科學(xué)，2008，35（10）：152－154.

［4］Liu Chengjun.Gabor－based kernel PCA with fractional power polynomial models for face regcognition［J］.IEEE Transaction on Pattern Analysis and Machine Intelligence，2004（5）：572－581.

［5］Kononenko I.Estimating attributes：analysis and extensions of ReliefF［A］.The Proceedings of The European Conference on Machine Learning on Machine Learning［C］.Italy，Catania：Springer－Verlag New York，Inc.，1994：171－182.

［6］Kira K，Rendell L A.A practical approach to feature selection［A］.The Proceedings of The Ninth International Workshop on Machine Learning［C］.United Kingdom，Aberdeen，Scotland：Morgan Kaufmann Publishers Inc.，1992：249－256.

［7］Bezdek J C，Ehrlich R，F(xiàn)ull W.FCM：the fuzzy c－means clustering algorithms［J］.Computers ＆ Geosciences，1984，10（2）：191－203.