基于屬性分組的子空間聚類算法研究

龐 寧,靳黎忠

(太原科技大學應用科學學院,山西 太原 030024)

聚類分析是將數據集自動劃為若干類簇的數據分析過程.高維屬性空間的稀疏性使得全屬性空間下距離度量失去意義,不同的類簇存在于不同的屬性子空間上.因此,在聚類分析過程中,應考慮不同屬性組(即屬性子空間)對類簇形成作用的差異性.子空間聚類算法成為自動探索屬性子集,以及提高高維數據聚類結果理解性的有效途徑之一.

1 相關工作

1.1 高維數據聚類

子空間聚類是解決高維數據聚類分析的有效手段之一.作為最早被提出的子空間聚類算法,CLIQUE算法[1]是一種基于網格的子空間聚類,采用類Apriori方法,以自底向上的方式遞歸地尋找高密度子空間.ENCLUS算法[2]是在CLIQUE算法基礎上提出的,ENCLUS算法采用熵值小于預定閾值方法,作為提取類簇子空間的準則.MAFIA算法[3]采用基于直方圖的專門技術合并網格,可有效減少分區數量.但上述方法均采用基于網格的方法,導致嚴重依賴網格的位置.

由于使用降維技術,譜聚類也用于解決高維數據聚類問題.稀疏子空間聚類使用系數矩陣構造數據的相似度矩陣,再采用譜聚類形成最終結果[4].文獻[5]通過在樣本自表示框架中進行特征選擇和子空間學習,以低維空間學習的親和矩陣作為最終的聚類結果.上述基于譜聚類的聚類方法適合聚類類別較小且均衡分類的情況,對聚類參數的選擇較敏感.

1.2 分類數據聚類算法

K-modes算法[6]及其各種改進算法是分類數據聚類分析的典型研究代表.fuzzy k-modes算法[7]利用模糊中心的概念解決分類數據類簇的不穩定性.COOLCAT算法[8]是一種基于熵的模糊聚類算法,該算法使用信息熵去度量類內屬性值分布的差異性.在k-modes算法基礎上,文獻[9]為類簇的每維屬性計算雙權重值,并以此識別不同類簇的重要屬性子空間.上述基于mode聚類方法的不足在于只能獲取類簇中數據的部分信息.

針對高維分類數據聚類問題,硬子空間聚類使用0或1,表示屬性子空間的權值,例如,SUBCAD算法[10]需要反復迭代更新屬性權值,存在時間復雜度高等問題.軟子空間聚類需給各類的屬性賦予不同的權值,以度量不同屬性對各類簇的聚類貢獻程度,例如,PROCAD算法[11]利用屬性值的出現頻率度量其屬性權值;文獻 [9,12-13]提出的算法均是在K-modes的基礎上擴展改進而來,各算法在優化權重計算上有所區別,但權重計算容易產生對屬性重要性的偏差判斷.

本文提出一種基于屬性分組的軟子空間聚類算法SSC,該算法采用屬性分組技術將相關屬性劃分到同一組別中,根據組內屬性間的相關性為各屬性賦權值,構造不同屬性子空間,以最大化簇集質量為聚類目標,在不同子空間上提取各自類簇.

2 問題描述

設DB是一個包含n個數據對象的分類數據集,可表示為DB={Oi| 1≤i≤n},其中,每個數據對象Oi有d維屬性,Oi={aij| aij∈Aj,1≤j≤d},aij代表第i個數據對象在第j維屬性上的取值,是一個分類數據值,Aj表示第j維屬性.SSC算法需要解決的問題是:將數據集DB劃分為若干類簇Ci,不同的類簇Ci對應不同的屬性子集SAi,SAi?A,A是DB的屬性集,本文所使用的主要符號詳見表1.

表1 符號表示

3 基于屬性分組的軟子空間聚類算法

本文提出的基于屬性分組軟子空間聚類算法SSC由以下四個重要步驟組成,分別為屬性分組、去除冗余屬性、計算權重、軟子空間聚類.

3.1 屬性分組

挖掘具有強相關性的屬性組,有利于區分不同屬性在聚類過程中重要程度,從而搭建屬性子空間.本文采用基于屬性相關性的屬性分組技術,將所有屬性劃分成若干組,組內的屬性具有強相關性,屬性分組的目的是找到彼此相關的屬性,進而挖掘屬性相關性對屬性權值的影響.分析可知,組內屬性的相關度越高,其對聚類的作用越大.借鑒文獻[14]的方法,本文采用互信息和熵的比值計算屬性Ai和屬性Aj的相關度FR(Ai:Aj),可表示為公式(1).

(1)

其中,MI(Ai:Aj)和 H(Ai:Aj)分別指屬性Ai和屬性Aj之間的互信息和熵.FR(Ai:Aj)取值范圍是[0,1],該值越大,則表示屬性Ai和屬性Aj之間的相關性越強.

由于屬性子空間數量無法預先設定,同時,不同的屬性子空間之間可能會有重疊,即,某些屬性會出現在不同的子空間上,所以,不能采用傳統的聚類方法進行屬性分組.本文采用一種類似聚類的方法將相關性高的屬性分到同一組內,所有屬性都要參與每組的分配過程.只要符合分組條件,無論該屬性是否已經歸到某個屬性組內,均可被再次分配到其他組內.具體屬性分組算法如下:

算法1 屬性分組算法 輸入 分類屬性集A={A1,A2…Ad},Ai是數據集DB上的第i維屬性.輸出 屬性組AC={AC1,AC2…ACk},ACi是第i個屬性組.Step1.隨機選擇一個屬性,作為初始組AC1的初始屬性,即AC={AC1}={{A1}}; Step2. for i=1 to |A| for m=1 to |AC|for j=1 to |ACm|if FR(Ai:Aj)<0.5 then {flag=false;continue;}endforif flag then ACm=ACm∪{Ai};endforif Ai沒有被劃分到任何屬性組內then AC=AC∪{ACNEW}= AC∪{{Ai}};endfor Step3.重復step2 直到各屬性組AC內的屬性基本不變;

通過算法1,可形成若干屬性組,組內屬性高度相關.在高維數據聚類過程中,屬性子空間上的屬性彼此相關程度很高,往往更能預示出不同類簇的隱含信息.因此,基于屬性相關技術劃分出的屬性組是構建屬性子空間的關鍵環節.

3.2 去除冗余屬性

在算法1所形成的屬性組中,有一些屬性組內只包含了一個屬性,可認為這些屬性與其他屬性不相關或是冗余屬性,需要被刪除.識別并刪除冗余屬性的過程,見算法2:

算法2 去除冗余屬性算法 輸入 屬性組AC={AC1,AC2…ACk}.輸出 非冗余屬性組集CAN.Step1.for i=1 to |AC| if |ACi|==1 then R=R∪{ACi};endfor Step2.CAN←AC-R;

3.3 計算權重

在高維數據聚類過程中,各屬性的重要程度顯然不同.屬性之間相關度越高,說明彼此相互影響程度越深,聚類作用越大,其賦權比例應該越大.基于屬性相關度的分組技術可以有效地將相似屬性分為一組,屬性權重值受到組內其他屬性影響,同時,某些屬性可能屬于不同的屬性組,因此,屬性權重值的度量要綜合考慮所有相關屬性組,即,屬性權重值應為其在各屬性組內與其他屬性相關度平均值的總和,可表示為:

(2)

其中,CRk是屬性所屬的第k個屬性組,其值為屬性Ai的組內所有相關屬性Aj相關度FR(Ai:Aj)的平均值,m表示屬性組CRk內屬性數量.

計算各屬性權重值是構建屬性子空間的關鍵環節,軟子空間聚類的價值在于所有屬性均參與聚類過程,但參與度卻決于其權重值.算法SSC計算屬性權值的具體過程,見算法3:

3.4 子空間聚類

子空間聚類算法是將高維空間的數據映射到多個低維子空間上,并在低維空間上的聚類過程.在聚類過程中,聚類目標的設定與聚類準確性息息相關.本文的聚類目標為最大化類內數據之間相似度,最小化類間數據的相似度.采用多目標聚類質量函數在不同屬性子空間上進行聚類,SSC算法的具體聚類目標可表示為多目標聚類函數Q(C),見公式(3).

(3)

其中, P(Cs)表示簇Cs在整個簇集C中的數量占比,代表了該簇在簇集中的重要程度,相當于整個表達式的權重值;C(Cs) 表示簇Cs的簇內緊湊程度;S(Cs)則表示簇Cs與其他簇的離散程度.

簇內緊湊度C(Cs)通過度量簇Cs內數據Oi的每個屬性Aj上屬性值aij概率值P(aij)與條件概率值P(aij|Cs),刻畫了簇內緊湊度C(Cs),具體計算如公式(4)所示.

(4)

其中,P(aij)表示屬性值aij在屬性Aj上的出現頻率,P(aij|Cs)表示在簇Cs內,屬性值aij在屬性Aj上的出現頻率,W(Aj)表示屬性Aj的權值.

簇間離散度S(Cs)取決于屬性取值aij相對于簇Cs的專屬程度,即屬性Aj上的屬性取值aij出現在簇Cs中的比例越大,說明該屬性取值對于簇Cs與其他簇的離散作用越大,其數學形式表示如公式(5)所示.

(5)

其中,P(Cs|aij)表示在屬性Aj上屬性取值為aij的數據,在簇Cs中出現頻率.

SSC算法在所構建的屬性子空間的基礎上,以最大化簇集質量為聚類目標,迭代調整各類簇內的數據分布.具體算法過程如下:

4 實驗與分析

4.1 測試數據集與評價標準

4.1.1 測試數據集

本文使用UCI數據集和人工合成數據集對算法進行測試.UCI數據集與人工合成數據集內的屬性值均為分類型數據.測試數據集具體情況詳見表2,其中Voting、Mushroom和Splice均來自加州大學歐文分校用于機器學習的數據庫(簡稱UCI);人工合成數據集包括:DB1、DB2和DB3.數據集DB1的屬性總數為200維,主要用于測試屬性數量的改變對于各算法運行時間的影響;數據集DB3的數據總數為40 000,可以用于評測各算法運行時間與數據點之間的關系.

表2 測試數據集

4.1.2 評價標準

本文采用外部評價指標,調整蘭德系數ARI、純度Purity、雅克比系數Jaccard以及蘭德系數RI,作為算法SSC與其他對比算法的評測依據.ARI主要測試聚類結果和真實類簇之間數據分布的吻合程度;Purity評測每個類簇中的主導數據占總數據的比例;Jaccard系數度量同類數據對在同一類簇中的占比;RI評測同類數據對被聚合以及異類數據對被分離的比例[15].

4.2 對比算法

本文選擇子空間聚類算法PROCAD[11]、AT-DC[16]、DHCC[17]作為對比算法.這三種算法無須預先輸入閾值并且都以分類數據作為分析對象.

PROCAD算法通過屬性值在維度上的出現頻率度量屬性權重,聚類過程兼顧緊湊性和分離性的聚類目標.該算法將屬性值作為度量屬性權值的基本單元,有利于提高聚類精度,但也增加算法運行成本.AT-DC算法和DHCC算法均采用層次聚類,區別在于:前者以屬性值在簇中的條件概率作為屬性權重度量標準,使用兩階段聚類思想,實現劃分最優解;后者采用多元對應分析思想描述各屬性的聚類重要程度,使用分裂層次聚類思想構造類簇樹狀圖.AT-DC算法和DHCC算法對于數據分布結構不敏感,有利于處理不同數據集,但卻無法給出類簇相應的屬性子空間.

5 實驗結論

5.1 聚類性能對比實驗

本實驗主要測試算法SSC與其他對比算法在UCI數據集和人工合成數據集上的聚類效果,分別從聚類指標ARI、Purity、Jaccard以及RI四方面對比各算法在聚類性能上的差異并分析其原因.

5.1.1 UCI數據集上的對比實驗

圖1顯示了算法SSC與其他對比算法在三個UCI數據集上的聚類性能差異,圖1(a)、圖1(b)、圖1(c)和圖1(d)分別從四個聚類評價指標上進行了聚類性能對比.從圖1可見,算法SSC在數據集Voting和Splice上的聚類性能優于其他三種算法,尤其是,在數據集Splice上,算法SSC四個聚類指標的優勢均非常明顯,而算法PROCAD在數據集Mushroom上的聚類效果領先于其他算法.造成上述聚類性能差異的主要原因是:①算法PROCAD的屬性權重賦值粒度小于算法SSC,給屬性取值賦權重更有利于精確刻畫屬性子空間,尤其是類似數據集Mushroom,屬性值域范圍較大;②算法SSC使用屬性分組技術,利用屬性之間的強相關性度量屬性權重值,強化了屬性之間相互影響對聚類的作用,對于數據集Voting和Splice而言,屬性取值在各屬性上基本呈現均勻分布的特點,僅用屬性出現頻率無法有效區分聚類重要性,算法SSC可有效地解決該問題;③算法SSC通過迭代調整數據劃分,直至類簇結構最優,追求簇內緊湊和簇間分離多目標的聚類效果,保證了類簇的整體聚類精度.

(a)ARI值對比

5.1.2 人工合成數據集上的對比實驗

本文針對人工合成數據集分別測試了算法SSC與其他對比算法,圖2顯示了在人工合成數據集DB1、DB2和DB3上四種算法的ARI指標性能對比.觀察實驗結果可知:①算法SSC在三類人工合成數據集上的ARI指標值之間的差別不大,說明算法SSC對各種數據分布上的聚類性能很穩定;②算法SSC在三個合成數據集上的ARI指標值均優于其他三種算法,這一優勢在數據集DB3上表現得尤為明顯,在數據集DB1上四種算法之間的差異較小,主要原因是數據集DB3的屬性空間重疊程度會造成屬性賦權上的偏差,而數據集DB1相互獨立的屬性子空間和數據子集對各類子空間算法都很友好;③其他三種算法在各人工合成數據集上的聚類性能差異不明顯,主要是由于該三種算法對數據分布不敏感造成的.

圖2 各算法在人工合成數據集上的性能對比

5.2 算法效率對比實驗

5.2.1 數據量上的可擴展性實驗

圖3顯示了隨著數據集DB3數據量的增加,算法SSC與三種對比算法運行時間的變化趨勢,從圖可知,四種算法均基本呈現線性增長.其中,算法PROCAD增速最為明顯,DHCC在所有算法中的時間消耗最小,算法SSC的表現位于算法DHCC和算法AT-DC之間.主要原因是算法PROCAD的主要時間成本集中在屬性取值賦權的計算過程上,顯然,相比以整個屬性為權重計算單位的方法,這種計算方式更為耗費時間,這一結論在維度的可擴展性實驗上同樣得到驗證(見圖4).

圖3 數據量上的可擴展性實驗

5.2.2 維度上的可擴展性實驗

圖4表明了隨著數據集DB1屬性的增加,四種算法在運行時間上的差異.算法DHCC的維度可擴展性最優,而算法PROCAD是四種算法中受維度增長影響最大的.在數據量擴展性能對比實驗中,算法SSC僅比算法DHCC的表現略差,而在維度可擴展性上,算法SSC僅優于算法PROCAD,分析原因可知,算法SSC利用屬性分組技術對所有屬性的相關性進行分析計算,同時,利用多屬性組之間的相互作用評價屬性權重,這樣的度量方式會受到屬性數量的影響,當屬性量遞增時,算法在權重計算上所花費的時間也隨之增加,特別是,當屬性量大,屬性之間的相互關系逐漸復雜時,這種時間成本增加的趨勢也越加明顯.

6 結論與展望

為了解決高維分類數據的聚類問題,本文提出一種基于屬性分組的子空間聚類算法SSC,該算法利用屬性之間的相關性,度量不同屬性聚類重要度的差異,以多目標聚類質量最大化為目標,通過多次迭代,實現最佳的類簇劃分.在人工合成數據集以及UCI數據集上,實驗證明該算法具有正確性、有效性和良好的可擴展性.

本文下一步的研究方向將細化權重計算度量粒度,以屬性取值為度量單位,而非整個屬性;升級冗余屬性的判斷依據,在屬性成組之前去除冗余屬性的干擾;設計并實現算法并行化以適應海量數據的聚類需求.