基于屬性加權(quán)的不完全數(shù)模糊c均值聚類算法

李 丹， 顧 宏， 張 立 勇

（大連理工大學 控制科學與工程學院，遼寧 大連 116024）

0 引 言

聚類是數(shù)據(jù)挖掘、模式識別等領(lǐng)域的重要研究內(nèi)容之一，在識別數(shù)據(jù)內(nèi)在結(jié)構(gòu)方面具有重要作用.模糊c均值（fuzzyc－means，F(xiàn)CM）算法[1]是一種基于目標函數(shù)的有效的聚類算法，該算法能夠?qū)維完整的目標數(shù)據(jù)集X＝ ｛x1，x2，…，xn｝Rp劃分為若干模糊子類.然而，在模式分類應用中，由于數(shù)據(jù)采集失敗及隨機噪聲等原因，很多數(shù)據(jù)集是不完全的，即數(shù)據(jù)集包含缺失部分（非全部）屬性值的樣本，而FCM算法不能直接應用于不完全數(shù)據(jù)集的聚類分析.

為了消除缺失屬性對聚類分析的影響，有關(guān)文獻提出了各種不完全數(shù)據(jù)集的模糊聚類算法[2－8].Miyamoto等[2]提 出 了 幾 種 在 模 糊c均 值算法中處理不完全數(shù)據(jù)的方法，其中一種簡單方法是以相應屬性的加權(quán)平均值估算缺失屬性值，另一種方法則忽略數(shù)據(jù)集中的缺失屬性并通過完備屬性進行距離測算，這兩種方法即后來解決不完全數(shù)據(jù)聚類問題的常用策略：估算（imputation）法及舍棄（discarding/ignoring）法.之后，Hathaway等[3]提出了基于FCM進行不完全數(shù)據(jù)聚類的幾種具體方法，其中 WDS（whole data strategy）是一種最簡單的方法，該方法舍棄樣本集中所有包含缺失屬性的樣本，利用剩余完備樣本得到聚類中心及完備樣本的類屬，不完全樣本的類屬則通過其與各聚類中心的局部距離[9]確定，但這種對數(shù)據(jù)集的約簡將造成信息的大量丟失；另一種方法為PDS（partial distance strategy），即忽略不完全樣本的缺失屬性，F(xiàn)CM算法中的距離仍采用Dixon提出的局部距離[9]計算；文獻[3]還提出了兩種依據(jù)數(shù)據(jù)集信息對不完全樣本的缺失屬性進行估算的方法，其中 OCS（optimal completion strategy）方法將缺失屬性的估算看作優(yōu)化問題，并在聚類迭代過程中逐步尋求更優(yōu)的估計值，而NPS（nearest prototype strategy）方法則在每次聚類迭代中將缺失屬性設(shè)置為距離最近的聚類中心的相應屬性值.此外，考慮到樣本集中屬性的缺失原因，Timm等提出了一種基于Gath－Geva算法的不完全數(shù)聚類方法[4]；對于不完全關(guān)系數(shù)據(jù)集，Hathaway等根據(jù)三角不等式近似規(guī)則提出了一種基于FCM的聚類方法[5]；Honda等則通過局部主成分分析法將不完全數(shù)據(jù)集劃分到若干線性模糊子類中[6]；Lim等提出通過神經(jīng)網(wǎng)絡(luò)訓練缺失屬性以解決不完全數(shù)聚類問題[7].鑒于不完全數(shù)據(jù)中缺失屬性的不確定性，作者在前期工作中提出了缺失屬性的最近鄰區(qū)間描述[8]，通過將不完全數(shù)據(jù)集轉(zhuǎn)化為區(qū)間型數(shù)據(jù)集求解不完全數(shù)據(jù)集的聚類問題.

上述算法均隱含假定待分析樣本的各維屬性對聚類的貢獻均勻，在實際應用中有一定的局限性.目前，針對完全數(shù)據(jù)集的屬性加權(quán)聚類研究十分活躍，研究者已提出了多種屬性加權(quán)模糊聚類算 法[10－13]，通 過 極 小 化 屬 性 評 價 函 數(shù)[10]、利 用ReliefF算法[14]進行屬性賦權(quán)[11]、聚類與屬性權(quán)重協(xié)同學習[12]，以及對權(quán)重進行區(qū)間監(jiān)督[13]等策略強調(diào)重要屬性的作用，有效提高了完全數(shù)據(jù)集的聚類準確率.本文將屬性加權(quán)的思路引入不完全數(shù)據(jù)集的模糊聚類問題，利用ReliefF算法分析各維屬性的聚類貢獻并結(jié)合入模糊c均值聚類，進而改善不完全數(shù)據(jù)集的聚類效果.

1 屬性加權(quán)模糊c均值聚類算法

屬性加權(quán)模糊c均值（weighted fuzzycmeans，WFCM）算法[10－13]將完備 數(shù)據(jù)集X＝｛x1，x2，…，xn｝Rp劃分為c個模糊類，對于給定屬性權(quán)重w＝（w1w2…wp）T，j：wj＞0，通常使得聚類目標函數(shù)

取得極小值.其中xk＝ （x1kx2k…xpk）T為樣本數(shù)據(jù)；vi∈Rp為第i類的聚類中心，記V＝（vji）∈Rp×c為聚類中心矩陣；uik∈ [0，1]表示樣本xk隸屬于第i類的程度，且滿足記U＝（uik）∈Rc×n為模糊劃分矩陣；m＞1為模糊化參數(shù)表示如下加權(quán)歐式距離：

式中：W＝diag｛w1，w2，…，wp｝為對角陣.

采用拉格朗日乘子法，可得聚類目標函數(shù)取得極小值的必要條件為

屬性加權(quán)模糊c均值算法采用交替優(yōu)化（alternating optimization，AO）策略對聚類目標函數(shù)（1）進行優(yōu)化，當各屬性權(quán)重相等時，算法為基本FCM算法.

2 ReliefF屬性評價算法

Relief系列算法是基于樣本類內(nèi)相似性及類間相異性的屬性評價方法[14，15]，最初的 Relief算法僅局限于求解兩類的分類問題[15]，后擴展為ReliefF算法[14]以解決有噪聲及多類問題的屬性評價.

設(shè)X＝ ｛x1，x2，…，xn｝Rp為待評價的完整數(shù)據(jù)集，xk＝（x1kx2k…xpk）T，為樣本數(shù)據(jù)，對于任意選取的基準樣本xk（1≤k≤n），ReliefF算法首先在同類中搜索其z個最近鄰樣本hr（r＝1，2，…，z），然后在各不同類中分別搜索其z個最近鄰樣本mlr（r＝1，2，…，z；l≠class（xk）），并通過下式度量基準樣本xk與近鄰樣本xb在第j個屬性上的差異：

其中λj＝（xj1xj2…xjn）T，為數(shù)據(jù)集中各樣本第j個屬性組成的向量，max（λj）和min（λj）分別表示各樣本第j個屬性取值的最大及最小值.通過取nr個隨機基準樣本，ReliefF算法中權(quán)值由下式更新[14]：其中P（l）為第l類出現(xiàn)的概率.

3 基于屬性加權(quán)的不完全數(shù)模糊c均值聚類算法

本文采用ReliefF算法獲得屬性權(quán)重向量w用于無監(jiān)督的不完全數(shù)據(jù)加權(quán)聚類分析，但該算法是一種有監(jiān)督學習模式下的屬性評價方法，即在已知樣本類屬的基礎(chǔ)上評價屬性的重要程度.針對完全數(shù)據(jù)集，文獻[11]將有監(jiān)督的ReliefF算法應用于無監(jiān)督聚類分析，本文借鑒文獻[11]的方法，采用如下針對不完全數(shù)據(jù)集的屬性加權(quán)策略：鑒于經(jīng)典的OCS－FCM算法能夠同時獲取數(shù)據(jù)集劃分及對缺失屬性的估算，因而，可首先對不完全數(shù)據(jù)集利用OCS－FCM算法進行聚類，獲得樣本類屬及由缺失屬性估算值“還原”的完備數(shù)據(jù)集，則在此基礎(chǔ)上可通過ReliefF算法實現(xiàn)對屬性較為合理的評價，使得將屬性加權(quán)的思路引入不完全數(shù)據(jù)集的模糊聚類問題成為可能.

在已確定的屬性權(quán)重基礎(chǔ)上，本文采用如式（2）所示的加權(quán)歐式距離作為距離度量，將屬性加權(quán)引入經(jīng)典的OCS－FCM算法，提出了基于屬性加權(quán)的不完全數(shù)模糊c均值（WOCS－FCM）聚類算法.令珟X＝｛槇x1，槇x2，…，槇xn｝為不完全數(shù)據(jù)集，WOCS－FCM算法將缺失屬性作為變量優(yōu)化如下目標函數(shù)：

借鑒文獻[3]，可得使得目標函數(shù)（7）達到極小值的必要條件為式（3）、（4）以及下式：

WOCS－FCM算法流程如下：

（1）利用ReliefF算法得屬性權(quán)重向量w＝（w1w2…wp）T；

（2）設(shè)定聚類類別數(shù)c，設(shè)定迭代停止閾值ε，初始化缺失屬性及劃分矩陣U（0）；

（3）當?shù)螖?shù)為l（l＝1，2，…）時，根據(jù)U（l－1），利用式（3）更新聚類原型V（l）；

（4）根據(jù)V（l），利用式（4）更新劃分矩陣U（l）；

（5）利用式（8）估算缺失屬性槇xjk；

4 數(shù)值實驗

4.1 數(shù)據(jù)集

本文對兩個著名數(shù)據(jù)集IRIS[16]及 Crude－Oil[17]進行了聚類分析，這兩個數(shù)據(jù)集常被用作檢驗聚類算法性能的標準數(shù)據(jù).

IRIS數(shù)據(jù)集由150個樣本組成，每個樣本有4個屬性，分別表示IRIS的Petal Length、Petal Width、Sepal Length和Sepal Width.整個樣本集包含了3個IRIS種類，分別為Setosa、Versicolor和Virginica，每類各有50個樣本，其中Setosa與其他兩類間能較好地分離，而Versicolor和Virginica之間存在交疊.Hathaway等[18]給出這組數(shù)據(jù)的實際類原型位置為

Crude－Oil數(shù)據(jù)集由56個樣本組成，每個樣本有5個屬性，用于描述產(chǎn)自3個地區(qū)原油的化學成分.數(shù)據(jù)集中，7個樣本來自 Wilhelm，另各有11個和38個樣本分別來自Sub Mulinia及Upper Mulinia.

本文討論屬性隨機缺失（missing completely at random，MCAR）不完全數(shù)據(jù)集的模糊聚類問題.通過人為隨機舍棄完備數(shù)據(jù)集X中若干屬性可得不完全數(shù)據(jù)集珟X，缺失屬性的隨機選取應滿足下述條件[3]：

（1）數(shù)據(jù)集中任意樣本槇xk至少保留一個完備屬性；

（2）任意屬性在數(shù)據(jù)集中至少保留一個完備值.

4.2 實驗結(jié)果

為了測試 WOCS－FCM算法的聚類性能，將其與 WDS－FCM、PDS－FCM、OCS－FCM 及 NPSFCM 算法[3]對不完全IRIS、Crude－Oil數(shù)據(jù)集的聚類結(jié)果進行比較.本文中，各種聚類算法均選取模糊化參數(shù)m＝2，迭代停止閾值ε＝10－5，使用滿足的劃分矩陣U（0）作為初始值，相應的算法結(jié)束條件設(shè)置為并將 OCS－FCM、NPS－FCM 及 WOCS－FCM 算法中缺失屬性的初始值設(shè)置為隨機值.在ReliefF算法中，選取所有樣本為基準樣本評價屬性權(quán)重，對于IRIS數(shù)據(jù)集，ReliefF算法搜索基準樣本的近鄰樣本數(shù)z＝10；由于Crude－Oil數(shù)據(jù)集樣本較少，近鄰樣本數(shù)取為z＝min｛各類中樣本數(shù)目最小值，5｝.

在實驗過程中發(fā)現(xiàn)，在相同的屬性缺失程度（如IRIS數(shù)據(jù)缺失5%的屬性值）下，數(shù)據(jù)集缺失不同的屬性將可能造成聚類結(jié)果的差異.因此，為避免這種差異對算法性能評價的影響，本文在每種屬性缺失程度下依4.1節(jié)中所述方法隨機生成10個不完全數(shù)據(jù)集，取其聚類結(jié)果平均值用于算法分析.

以IRIS數(shù)據(jù)缺失5%屬性值的情況為例，圖1所示為在隨機生成的10個不完全數(shù)據(jù)集（集1～10）上ReliefF算法所得各維屬性權(quán)值.

由圖1可以看出，當IRIS數(shù)據(jù)缺失5%的屬性值時，在隨機生成的10個數(shù)據(jù)集中，ReliefF算法確定屬性Sepal Length及Sepal Width的權(quán)值均較大，而屬性Petal Length及Petal Width的權(quán)值相對較小.因而，在 WOCS－FCM算法中，屬性Sepal Length及Sepal Width的作用將通過如式（2）所示的加權(quán)歐式距離被強調(diào)，進而引導聚類過程.類似地，在其他缺失程度的不完全IRIS數(shù)據(jù)集及不完全Crude－Oil數(shù)據(jù)集上，重要屬性也將獲得較大權(quán)重以強調(diào)其在聚類過程中的作用.

表1及表2統(tǒng)計了兩個數(shù)據(jù)集在不同屬性缺失程度下10個不完全數(shù)據(jù)集的聚類結(jié)果平均值.由于已知如式（9）所示的IRIS實際類原型位置V＊，表1的后5列為各算法的聚類中心誤差平方和，其計算如下[3]：

圖1 IRIS數(shù)據(jù)缺失5%屬性值時在10個數(shù)據(jù)集上所得各維屬性權(quán)重Fig.1 The attribute weights on 10incomplete IRIS datasets with 5%attribute values missing

表1 不完全IRIS數(shù)據(jù)集的聚類結(jié)果平均值Tab.1 Averaged results of clustering using incomplete IRIS datasets

表2 不完全Crude－Oil數(shù)據(jù)集的聚類結(jié)果平均值Tab.2 Averaged results of clustering using incomplete Crude－Oil datasets

由表1、2可以看出，在不完全IRIS及Crude－Oil數(shù)據(jù)集的不同屬性缺失程度下，基于屬性加權(quán)的WOCS－FCM算法在迭代次數(shù)方面與其他4種算法基本相當；而在兩個數(shù)據(jù)集的錯分數(shù)及IRIS數(shù)據(jù)集聚類中心誤差平方和方面，WOCS－FCM算法通過強調(diào)重要屬性的貢獻得到了更合理的數(shù)據(jù)集劃分，改善了不完全數(shù)據(jù)集的聚類效果.以上結(jié)果表明本文提出的基于屬性加權(quán)的模糊c均值聚類算法是合理有效的.

5 結(jié) 語

本文從強化重要屬性在不完全數(shù)據(jù)集聚類分析中作用的角度考慮，提出了一種基于屬性加權(quán)的不完全數(shù)模糊c均值聚類算法.該算法在ReliefF算法獲得的屬性權(quán)重基礎(chǔ)上，將屬性加權(quán)思路引入不完全數(shù)據(jù)集模糊聚類，能夠?qū)崿F(xiàn)對缺失屬性及聚類結(jié)果的一體化求解.實驗結(jié)果表明了本文所提算法的有效性和相比已有結(jié)果的優(yōu)越性.下一步工作是將屬性加權(quán)思路應用于部分缺失圖像的處理中.

[1] Bezdek J C.Pattern Recognition with Fuzzy Objective Function Algorithms[M].New York：Plenum Press，1981.

[2] Miyamoto S，Takata O，Uayahara K.Handling missing values in fuzzyc－means[C]//Proceedings of the 3rd Asian Fuzzy System Symposium.Seoul：Packsan Publishers Inc.，1998：139－142.

[3] Hathaway R J，Bezdek J C.Fuzzyc－means clustering of incomplete data [J].IEEE Transactions on Systems，Man，and Cybernetics，Part B：Cybernetics，2001，31（5）：735－744.

[4] Timm H，Doring C，Kruse R.Different approaches to fuzzy clustering of incomplete datasets [J].International Journal of Approximate Reasoning，2004，35（3）：239－249.

[5] Hathaway R J，Bezdek J C.Clustering incomplete relational data using the non－Euclidean relational fuzzyc－means algorithm [J].Pattern Recognition Letters，2002，23（1－3）：151－160.

[6] Honda K，Ichihashi H.Linear fuzzy clustering techniques with missing values and their application to local principle component analysis [J].IEEE Transactions on Fuzzy System，2004，12（2）：183－193.

[7] Lim C P，Leong J H，Kuan M M.A hybrid neural network system for pattern classification tasks with missing features[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（4）：648－653.

[8] LI Dan，GU Hong，ZHANG Li－yong，etal.A fuzzyc－means clustering algorithm based on nearestneighbor intervals for incomplete data [J].Expert Systems with Applications，2010，37（10）：6942－6947.

[9] Dixon J K.Pattern recognition with partly missing data[J].IEEE Transactions on Systems，Man，and Cybernetics，1979，9（10）：617－621.

[10] WANG X Z，WANG Y D，WANG L J.Improving fuzzyc－means clustering based on feature－weight learning [J].Pattern Recognition Letters，2004，25（10）：1123－1132.

[11] 李 潔，高新波，焦李成.基于特征加權(quán)的模糊聚類新算法[J].電子學報，2006，34（1）：89－92.LI Jie，GAO Xin－bo，JIAO Li－cheng.A new feature weighted fuzzy clustering algorithm [J]. Acta Electronica Sinica，2006，34（1）：89－92.（in Chinese）

[12] ZHANG Li－yong，LI Dan，ZHONG Chong－quan.Collaborative optimization of clustering by fuzzycmeans and weight determination by ReliefF[C]//Proceedings of the 6th International Conference on Fuzzy Systems and Knowledge Discovery.Minneapolis：IEEE Computer Society Press，2009：454－459.

[13] 李 丹，顧 宏，張立勇.基于屬性權(quán)重區(qū)間監(jiān)督的模糊C均值聚類算法[J].控制與決策，2010，25（3）：457－460.LI Dan，GU Hong，ZHANG Li－yong.A fuzzycmeans algorithm with interval－supervised attribute weights[J].Control and Decision，2010，25（3）：457－460.（in Chinese）

[14] Kononenko I.Estimating attributes：Analysis and extensions of Relief[C]//Proceedings of the 7th European Conference on Machine Learning.Catania：Springer－Verlag，1994：171－182.

[15] Kira K，Rendell L A.A practical approach to feature selection [C]// Proceedings of the 9th International Conference on Machine Learning.San Mateo：Morgan Kaufmann Publishers，1992：249－256.

[16] Blzke C L，Merz C J.UCI repository of machine learning databases [EB/OL]. [2010－02－12].http：//www. ics. uci. edu/～ mlearn.MLResitory.html.

[17] Johnson R A，Wichern D W.Applied Multivariate Statistical Analysis[M].New Jersey：Prentice－Hall，1982.

[18] Hathaway R J，Bezdek J C. Optimization of clustering criteria by reformulation [J].IEEE Transactions on Fuzzy Systems，1995，3（2）：241－245.