張 鴻

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

0 引 言

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

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

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

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

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

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

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

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

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

1.2 原始ReliefF算法

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

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

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

其次找出與xi不同類的樣本實(shí)例中k個(gè)最近鄰的樣本集合 M（c）。設(shè) diff＿miss［A，xi，M（c）］是n×1矩陣，為xi在與M（c）內(nèi)各對象在樣本屬性特征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）找到與樣本同類的k個(gè)最近鄰樣本集合H；

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

（6）找到與樣本xi不同類的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表示與對象同類的k個(gè)最近鄰的對象集合，M（c）表示與對象不同類的k個(gè)最近鄰對象集合，diff＿h(yuǎn)it（A，xi，H）為對象xi與H內(nèi)各對象在特征A 上的差異量化表示，diff＿miss（A，xi，M）表示對象xi與M（c）內(nèi)各對象在特征A上的差異量化表示，上述兩公式的計(jì)算方式見公式（4）、（5）。

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

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

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

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

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

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

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

（3）根據(jù)Xd大小，把該類樣本分成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ì)算該類中樣本點(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同類的k個(gè)最近鄰樣本集合H；

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

（9）找到與樣本xi不同類的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ū)間，值越高的特征對分類越有利，值為負(fù)的特征則不利于分類，并且可以得到穩(wěn)定的W。

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

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

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

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

式中：m∈［1，＋∞］，為一個(gè)加權(quán)指數(shù)，隨著m的增大，聚類的模糊性增大；N為樣本數(shù)據(jù)集的個(gè)數(shù)；μij為第j個(gè)樣本點(diǎn)隸屬于第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）找到聚類中心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ù)庫，該數(shù)據(jù)庫是由加州大學(xué)提供，從中選擇Iris、Disbetes等2個(gè)數(shù)據(jù)集，如表1所示。

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

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

本實(shí)驗(yàn)從分類正確率和分類標(biāo)準(zhǔn)差指標(biāo)方面，在本實(shí)驗(yàn)數(shù)據(jù)集上對 ReliefF－WFCM、IReliefFWFCM、IG－WFCM以及原始FCM等4種聚類方法的性能進(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均值聚類。

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

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

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

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

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

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

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

4 結(jié)束語

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

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

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

［3］高瀅，劉大有，徐益.一種特征加權(quán)的聚類算法框架［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.