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

李詩瑾　李倩　徐桂瓊

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

關(guān)鍵詞： 數(shù)據(jù)挖掘； 模糊C均值聚類； 屬性約簡； 聚類效果

中圖分類號： TN911.1?34； TP391 文獻(xiàn)標(biāo)識碼： 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 引 言

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

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

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

1 模糊C均值聚類

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

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

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

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

（2） [0

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

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

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

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

FCM算法的具體步驟如下：

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

輸出：[U，V]

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

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

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

2 基于MFCM的屬性約簡算法

2.1 屬性重要性

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

2.2 MFCM算法

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

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

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

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

[uik=j=1puijk] （7）

2.3 基于MFCM的屬性約簡算法

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

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

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

輸出：[U，V，A，]約簡后的數(shù)據(jù)集指標(biāo)

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

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

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

步驟四：當(dāng)[t=T]或[Jt-Jt-1≤ε]時執(zhí)行步驟五；否則，重復(fù)步驟二和步驟三，并且置[t=t+1。]

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

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

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

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

3 實驗與結(jié)果分析

3.1 實驗數(shù)據(jù)集

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

3.2 ARI屬性約簡

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

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

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

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

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

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

3.4 實驗結(jié)果分析

從圖4可以看出，當(dāng)數(shù)據(jù)集的連續(xù)屬性平均標(biāo)準(zhǔn)差較小，即屬性分布差別不大的情況下，通過因子分析和粗糙集理論得到的約簡屬性用于聚類效果要優(yōu)于本文提出的ARI約簡算法，但是隨著數(shù)據(jù)集的屬性平均標(biāo)準(zhǔn)差的增大，粗糙集和因子分析法的聚類效果要逐漸劣于本文算法。依據(jù)RI的提升率趨勢發(fā)現(xiàn)，ARI的聚類效果隨著數(shù)據(jù)集平均標(biāo)準(zhǔn)差的增大而增大。

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

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

4 結(jié) 論

在數(shù)據(jù)挖掘中，F(xiàn)CM算法是一種經(jīng)典的聚類分析方法，廣泛應(yīng)用于諸多領(lǐng)域。為了克服傳統(tǒng)FCM算法的局限性，本文在多屬性模糊C均值聚類的基礎(chǔ)上，提出一種屬性約簡算法。為驗證有效性，在UCI的五個數(shù)據(jù)集上，將新算法與因子分析法和粗糙集理論約簡方法進(jìn)行比較分析。實驗結(jié)果表明，該方法具有更好的泛化作用。特別地，當(dāng)數(shù)據(jù)集的平均類間距離和標(biāo)準(zhǔn)差較大的情況下，聚類效果優(yōu)于常用的粗糙集和因子分析屬性約簡方法。

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

參考文獻(xiàn)

[1] HAN Jiawei， KAMBER Micheline.數(shù)據(jù)挖掘：概念與技術(shù)[M].北京：機(jī)械工業(yè)出版社，2012.

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

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

[4] 周志華.機(jī)器學(xué)習(xí)[M].北京：清華大學(xué)出版社，2016.

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

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

[7] 廖啟明，龍鵬飛.基于屬性重要性的粗糙集屬性約簡方法[J].計算機(jī)工程與應(yīng)用，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] 葉海軍.基于統(tǒng)計特征加權(quán)的模糊聚類方法及其應(yīng)用[J].現(xiàn)代電子技術(shù)，2009，32（12）：99?102.

[11] 楊照峰，時合生.基于改進(jìn)QPSO的模糊C?均值聚類算法[J].現(xiàn)代電子技術(shù)，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] 高新波.模糊聚類分析及其應(yīng)用[M].西安：西安電子科技大學(xué)出版社，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].計算機(jī)應(yīng)用研究，2008，25（6）：1630?1632.endprint