基于屬性加權的不完全數模糊c均值聚類算法

李 丹， 顧 宏， 張 立 勇

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

0 引 言

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

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

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

1 屬性加權模糊c均值聚類算法

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

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

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

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

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

2 ReliefF屬性評價算法

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

設X＝ ｛x1，x2，…，xn｝Rp為待評價的完整數據集，xk＝（x1kx2k…xpk）T，為樣本數據，對于任意選取的基準樣本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，為數據集中各樣本第j個屬性組成的向量，max（λj）和min（λj）分別表示各樣本第j個屬性取值的最大及最小值.通過取nr個隨機基準樣本，ReliefF算法中權值由下式更新[14]：其中P（l）為第l類出現的概率.

3 基于屬性加權的不完全數模糊c均值聚類算法

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

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

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

WOCS－FCM算法流程如下：

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

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

（3）當迭代次數為l（l＝1，2，…）時，根據U（l－1），利用式（3）更新聚類原型V（l）；

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

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

4 數值實驗

4.1 數據集

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

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

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

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

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

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

4.2 實驗結果

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

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

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

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

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

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

表1 不完全IRIS數據集的聚類結果平均值Tab.1 Averaged results of clustering using incomplete IRIS datasets

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

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

5 結 語

本文從強化重要屬性在不完全數據集聚類分析中作用的角度考慮，提出了一種基于屬性加權的不完全數模糊c均值聚類算法.該算法在ReliefF算法獲得的屬性權重基礎上，將屬性加權思路引入不完全數據集模糊聚類，能夠實現對缺失屬性及聚類結果的一體化求解.實驗結果表明了本文所提算法的有效性和相比已有結果的優越性.下一步工作是將屬性加權思路應用于部分缺失圖像的處理中.

[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] 李 潔，高新波，焦李成.基于特征加權的模糊聚類新算法[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] 李 丹，顧 宏，張立勇.基于屬性權重區間監督的模糊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.