基于多屬性模糊C均值聚類的屬性約簡算法

李詩瑾　李倩　徐桂瓊

摘 要： 模糊C均值聚類算法在處理高維數據集時，存在計算復雜度高，算法泛化能力差，計算精度低等問題。考慮到特征屬性對聚類的貢獻程度的差異，在多屬性模糊C均值聚類的思想上，提出一種基于屬性重要性的約簡算法。為驗證有效性，在UCI數據集上，將新算法與因子分析法和粗糙集理論約簡方法進行比較分析。實驗結果表明，該方法具有更好的泛用性，在平均標準差大或類間中心距離較遠的數據集上具有更好的性能。

關鍵詞： 數據挖掘； 模糊C均值聚類； 屬性約簡； 聚類效果

中圖分類號： TN911.1?34； TP391 文獻標識碼： A 文章編號： 1004?373X（2017）21?0112?05

Attribute reduction algorithm based on multiattribute fuzzy C?means clustering

LI Shijin， LI Qian， XU Guiqiong

（School of Management， Shanghai University， Shanghai 200444， China）

Abstract： The fuzzy C?means clustering algorithm used to process the high?dimensional datasets has the problems of high computational complexity， poor algorithm generalization ability and low calculation accuracy. Considering the difference of feature attribute for clustering contribution， a new reduction algorithm based on attribute importance is proposed on the basis of the thought of multiattribute fuzzy C?means clustering. In order to verify its validity， the comparative analysis was performed in UCI datasets for the proposed algorithm， factor analysis method and reduction method based on rough set theory. The experimental results show this method has wider application range， and better performance on the datasets whose average standard deviation is large or the inter?class centre distance is far.

Keywords： data mining； fuzzy C?means clustering； attribute reduction； clustering effect

0 引 言

隨著大數據時代的到來，各行各業中都累計了海量和高維度的數據資料。數據挖掘技術可以從這些大量的數據中挖掘出有價值的信息[1]，而這些高維度的數據資料卻對目前大多數數據挖掘算法的效果造成了嚴重的阻礙， 這種阻礙被稱之為 “維數災難”[2]。數據降維，又稱屬性約簡，是一種有效解決維數災難的方法，它將原有高維空間上的點映射到低維空間，在不降低精度的前提下剔除冗余屬性對挖掘所造成的誤差，提高挖掘任務的效率與精度。常見的方法有主成分分析（PCA）、因子分析、線性判別分析（LDA）、局部線性嵌入算法（LLE）和粗糙集理論等[3?4]。因子分析可以看作是 PCA 的進一步推廣，它從研究變量內部依賴關系出發，把一些具有錯綜復雜關系的變量歸結為少數幾個綜合因子的一種多變量統計分析方法，能在損失很小信息的前提下減小維數。但是在使用前需要進行KMO統計量檢驗，當KMO小于0.6時，數據集不適合通過因子分析進行屬性重要性排序[5]。粗糙集理論最早由Pawlak提出，是一種處理不確定信息的數據分析方法[6]。它根據已有的信息或知識對論域進行劃分，在保證知識庫的分類能力不變的條件下，剔除冗余與不相關的特征。然而，大多數據集具有連續屬性值，若通過離散化方法來構造等價類，往往無法得到較合理的劃分[7]。另外，粗糙集是一種監督的屬性約簡算法，在決策屬性缺失的情況下并不適用。

模糊C均值聚類（FCM）最早由Bexdek提出，是聚類分析中最流行的算法之一，其主要思想是將數據集中的樣本劃分成為不同的子集，使得相似的樣本盡可能劃分到同一類，不相似的樣本則歸為不同類[8]。最早的FCM通過歐式距離度量樣本與原型之間的相似性，未考慮到樣本的不同屬性之間有差別，無法檢測超球體。文獻[9]提出用馬氏距離替代歐式距離，可以滿足不同度量單位數據的要求。文獻[10]在傳統目標函數聚類方法的思想上提出基于統計特征加權的FCM算法。文獻[11]針對FCM算法容易陷入局部極值等缺陷，提出了基于改進QPSO的FCM方法。雖然這些優化算法能有效地解決傳統FCM在度量相似性上的缺陷，但是它們卻沒有考慮不同屬性對簇劃分的貢獻是不同的。

文獻[12]提出一種多屬性FCM算法（MFCM），它從數據集中提取了更多屬性對于聚類的信息，提高了聚類質量。受該研究工作的啟發，本文在MFCM算法的基礎上，提出一種基于屬性重要性的約簡算法（ARI）。該算法通過對屬性重要性進行排序，剔除對聚類無關或貢獻較小的屬性，從而提高二次聚類的精度。實驗證明，ARI算法可以有效剔除冗余屬性，并且其屬性約簡效果隨著平均類間距離和平均類間標準差的增大而上升。endprint

1 模糊C均值聚類

FCM的基本思想是將[n]個樣本[X=x1，x2，…，xn]分為[c]個簇，簇心用[V=v1，v2，…，vc]表示。通過建立表示樣本數據點與聚類簇心之間加權相似性測度的目標函數，并對其進行迭代最小化，最終確定最佳的聚類結果。聚類結果通過模糊隸屬度矩陣[U=uik∈R，][i=1，2，…，c；][k=1，2，…，n]表示。FCM算法的目標函數[J]可由式（1）給出[13?14]：

[minJ（U，V）=i=1c k=1numikxk-vi2] （1）

其中：[uik]表示樣本點[xk]屬于第[i]個類的隸屬程度，它反映了樣本點與簇的相似程度，若接近1，表示屬于此類的程度高；若接近0，表示屬于此類的程度低。[m]代表加權指數（模糊指標），[1

（1） [uik∈[0，1]， i=1，2，…，c；k=1，2，…，n]；

（2） [0

（3）[i=1cuik=1，k=1，2，…，n]。

在滿足條件（3）的前提下，根據Lagrange乘子法，可以得到目標函數取得極小值的必要條件為：

[uik=j=1cxk-vixk-vj2m-1-1， i≠j] （2）

[vi=k=1nuikmxkk=1nuikm] （3）

FCM算法的具體步驟如下：

輸入：數據集、聚類個數[c、]模糊度[m、]迭代閾值[ε、]最大迭代次數[T]

輸出：[U，V]

步驟一：隨機初始化聚類中心[V，]令[t=0。]

步驟二：根據式（2）更新隸屬度矩陣[U，]代入式（3）更新聚類簇心[V。]

步驟三：若[t=T]或[vi，t-vi，t-1≤ε，]則停止；否則，重復步驟二，并且置[t=t+1。]

2 基于MFCM的屬性約簡算法

2.1 屬性重要性

FCM算法以樣本點與聚類中心之間的歐式距離作為相似性指標，默認每一個屬性對聚類作出的貢獻相等。圖1包含10個樣本點，該圖直觀地表現出不同屬性對于聚類的貢獻程度不同：假設樣本1～5屬于第一個簇，樣本6～10屬于第二個簇。通過FCM算法得樣本5隸屬于簇2的程度卻要高于簇1。分別考慮屬性[x]和[y]可以發現，當僅考慮屬性[x]時，樣本5屬于簇1的程度高；當僅考慮屬性[y]時，樣本5屬于簇2的程度高。由此可見，不同屬性對于聚類有著不同的貢獻程度，樣本的每個特征屬性并不都對聚類結果起決定性作用[11]。

2.2 MFCM算法

Pimentel和Souza考慮到FCM算法在計算隸屬度時，默認樣本的每個屬性對于聚類的貢獻均相同。因此需要進一步細化在數據樣本中每個屬性對于分簇的貢獻程度。假設數據集[X]中的每個樣本包含[p]個特征屬性，樣本點可記作[xk=x1k，x2k，…，xpk，k∈1，2，…，n，] 簇心記為[vi=vi1，vi2，…，vip， i∈1，2，…，c]。目標函數[J]則調整為：

[minJU，V=i=1c k=1n j=1pumijkxjk-vij2] （4）

此時的目標函數考慮到每一個屬性的累計貢獻，通過基于屬性[j]計算樣本[xk]距離簇心[vi]的距離。考慮到不同屬性對于聚類的貢獻程度，基于每一個屬性計算對象的隸屬度：

[uijk=h=1cl=1pxjk-vijxlk-vhlA2m-1 -1，i≠h，j≠l] （5）

式中[uijk]代表樣本[xk]在屬性[j]上隸屬于簇[vi]的程度，需要滿足以下限制條件：

（1）[uijk∈[0，1]， i=1，2，…，c； k=1，2，…，n； j=1，2，…，p；]

（2） [0

（3）[i=1c j=1puijk=1，k=1，2，…，n]。

此時，簇心可由式（6）計算得出：

[vij=k=1nuijkmxkjk=1nuijkm] （6）

MFCM算法實則是將傳統的FCM中的樣本屬于不同簇的隸屬度拓展成一個樣本基于每個屬性在不同簇的隸屬度，將傳統FCM隸屬度矩陣的每個行向量替換為一個[p×c]矩陣，如式（7）所示，MFCM累加所有屬性的隸屬度得到每個樣本的隸屬度用于分簇。

[uik=j=1puijk] （7）

2.3 基于MFCM的屬性約簡算法

MFCM算法雖然考慮了不同屬性對于聚類的貢獻程度，但仍保留了所有屬性，冗余屬性的存在影響了聚類的效率和精度。由此，本文在MFCM的基礎上提出一種屬性約簡算法，計算每一個樣本的不同屬性對整體聚類的重要性，并根據重要性大小，在不降低聚類精度的條件下，選擇剔除對聚類貢獻程度較低的幾個屬性，用于屬性約簡。

ARI屬性約簡算法的具體步驟如下：

輸入：數據集[X、]聚類數量[c、]模糊度參數[m、]迭代閾值[ε、]最大迭代次數[T]

輸出：[U，V，A，]約簡后的數據集指標

步驟一：隨機初始化隸屬度矩陣[U=uijk，]滿足限制條件[i=1c j=1puijk=1，uijk∈[0，1]]。

步驟二：固定[uijk，]根據式（6）更新原型矩陣[V=vij]。

步驟三：固定[vij，]根據式（5）更新隸屬度矩陣[U=uijk]。

步驟四：當[t=T]或[Jt-Jt-1≤ε]時執行步驟五；否則，重復步驟二和步驟三，并且置[t=t+1。]

步驟五：通過式（8）計算[A=[aj]，j=1，2，…，]其中[aj]表示屬性[j]對聚類的重要性。

[aj=k=1n i=1cuijk] （8）

步驟六：對屬性的重要性[aj]進行降序排列，排序高的屬性對FCM聚類時的重要性高，反之，對聚類重要性低。

步驟七：剔除若干個排序較低的[aj]屬性，只留下[y]個對聚類有意義的屬性，使得屬性約簡后的聚類有效性指數最高。本文ARI算法選取RI指數[15]作為有效性指標，比較計算刪除[y]個屬性后二次聚類的RI值，選擇使得RI值最大的[y]個屬性作為約簡結果。具體屬性約簡方法可參照實驗3.2節，以數據集wine為例介紹屬性篩選的過程。

3 實驗與結果分析

3.1 實驗數據集

為測試算法的有效性和泛用性，本文選取UCI公開數據庫中的五個帶標簽的具有連續屬性的數據集，即Wine，Iris，Seeds，Pima Indians diabetes，Abalone。數據集分簇后的平均類間中心距離和平均標準差可以表示數據集的分布特點。五個數據集及聚類特征分布如表1所示。

3.2 ARI屬性約簡

實驗通過參考FCM并使用Matlab軟件編寫ARI算法，這里以Wine數據集為例說明ARI屬性約簡算法，表2給出屬性重要性排序結果。

選擇排序較高的[y]個屬性做二次聚類，并計算聚類精度，本文利用RI指數作為聚類有效性指標，結果如表2所示，通過計算取不同屬性個數的聚類結果的RI值，如圖2所示，發現當篩選的屬性個數[y=3]時，聚類效果最好。對于Wine數據集，選擇Nonflavanoid phenols，Ash和Hue三個屬性做二次聚類時的精度最高，ARI算法能起到屬性約簡的作用。

3.3 不同屬性約簡算法的對比實驗

本文運用ARI算法與因子分析法、粗糙集理論進行屬性約簡，三種算法的比較結果如表3所示。

從表3中可以發現，由于因子分析與粗糙集理論自身的缺陷，無法絕對地對連續的數據集進行屬性約簡。在Iris數據集中，KMO統計量為0.536，不適合作因子分析；在Seeds和Pima數據集中，對數據離散化之后，無法通過粗糙集理論找到等價條件，刪除冗余屬性。ARI方法能夠通過計算每個屬性在聚類時的貢獻度，剔除重要性較低的屬性，留下能使得聚類精度最高的[y]個屬性，不受到方法自身缺陷的約束。

對約簡后的五個數據集進行二次聚類，并利用Rand指數比較聚類結果的有效性，結果如圖3所示。實驗結果表明，對于每一個數據集，對其中4個數據集基于ARI算法的聚類效果均有一定的提升，僅對于Iris數據集，新算法相比于粗糙集約簡結果略差，原因在于屬性個數較小，易于數據的離散化，而對于屬性個數較多的數據集，該方法使用范圍有限。

3.4 實驗結果分析

從圖4可以看出，當數據集的連續屬性平均標準差較小，即屬性分布差別不大的情況下，通過因子分析和粗糙集理論得到的約簡屬性用于聚類效果要優于本文提出的ARI約簡算法，但是隨著數據集的屬性平均標準差的增大，粗糙集和因子分析法的聚類效果要逐漸劣于本文算法。依據RI的提升率趨勢發現，ARI的聚類效果隨著數據集平均標準差的增大而增大。

從圖5可以看出，當數據集類間平均中心距離較小的情況下，通過因子分析和粗糙集理論得到的屬性約簡后的聚類效果要優于ARI約簡算法，但是隨著類間中心距離的增大，其屬性約簡的效果要逐漸劣于本文算法。隨著類間中心距離的增大，ARI聚類效果有所提升。因此，在平均類間中心距離較大的情況下可以考慮本文的算法做屬性約簡。

雖然粗糙集約簡對于某些數據集可以篩選出有意義的特征屬性，但是由于只能對帶有標簽的數據集進行約簡，并且對于連續性屬性需要先進行離散化，因此使用范圍有限。雖然因子分析能篩選出具有連續性屬性且無標簽的數據集中有意義的特征屬性，但是當KMO值接近0時，意味著樣本間的相關性越弱，數據集越不適合做因子分析。ARI雖然在某些時候表現劣于前兩者，但是無其他使用限制條件，且當數據集的平均標準差與類間中心距離較大時，屬性約簡效果更好。因此，在這種情況下可以考慮采用本文提出的ARI算法。

4 結 論

在數據挖掘中，FCM算法是一種經典的聚類分析方法，廣泛應用于諸多領域。為了克服傳統FCM算法的局限性，本文在多屬性模糊C均值聚類的基礎上，提出一種屬性約簡算法。為驗證有效性，在UCI的五個數據集上，將新算法與因子分析法和粗糙集理論約簡方法進行比較分析。實驗結果表明，該方法具有更好的泛化作用。特別地，當數據集的平均類間距離和標準差較大的情況下，聚類效果優于常用的粗糙集和因子分析屬性約簡方法。

在實際應用問題中，數據集不僅有連續屬性，還有離散型屬性的數據，如何將ARI算法進一步完善，使之應用于離散型數據的處理，是值得繼續研究的工作。

參考文獻

[1] HAN Jiawei， KAMBER Micheline.數據挖掘：概念與技術[M].北京：機械工業出版社，2012.

[2] WANG J. Geometric structure of high?dimensional data and dimensionality reduction [M]. Berlin： Springer Berlin Heidelberg， 2011.

[3] 約翰遜.實用多元統計分析[M].北京：清華大學出版社，2008.

[4] 周志華.機器學習[M].北京：清華大學出版社，2016.

[5] 王學民.因子分析和因子分析應用中值得注意的問題[J].統計與決策，2007（11）：142?143.endprint

[6] PAWLAK Z. Rough sets [J]. International Journal of computer & information sciences， 1982， 11（5）： 341?356.

[7] 廖啟明，龍鵬飛.基于屬性重要性的粗糙集屬性約簡方法[J].計算機工程與應用，2013，49（15）：130?132.

[8] BEZDEK J C. Pattern recognition with fuzzy objective function algorithms [M]. New York： Plenum Press， 1981.

[9] GROENEN PJ F， JAJUGAB K. Fuzzy clustering with squared Minkowsky distances [J]. Fuzzy sets and systems， 2001， 120（2）： 227?237.

[10] 葉海軍.基于統計特征加權的模糊聚類方法及其應用[J].現代電子技術，2009，32（12）：99?102.

[11] 楊照峰，時合生.基于改進QPSO的模糊C?均值聚類算法[J].現代電子技術，2014，37（7）：118?120.

[12] PIMENTEL B A， SOUZA R M C R. A multivariate fuzzy C?means method [J]. Applied soft computing， 2013， 13（4）： 1592?1607.

[13] 高新波.模糊聚類分析及其應用[M].西安：西安電子科技大學出版社，2004.

[14] KANNAN S R， RAMATHILAGAM S， CHUNG P C. Effective fuzzy C?means clustering algorithms for data clustering problems [J]. Expert systems with applications， 2012， 39（7）： 6292?6300.

[15] 楊燕，靳蕃，KAMEL Mohamed.聚類有效性評價綜述[J].計算機應用研究，2008，25（6）：1630?1632.endprint