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

龐 寧,靳黎忠

(太原科技大學(xué)應(yīng)用科學(xué)學(xué)院,山西 太原 030024)

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

1 相關(guān)工作

1.1 高維數(shù)據(jù)聚類

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

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

1.2 分類數(shù)據(jù)聚類算法

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

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

本文提出一種基于屬性分組的軟子空間聚類算法SSC,該算法采用屬性分組技術(shù)將相關(guān)屬性劃分到同一組別中,根據(jù)組內(nèi)屬性間的相關(guān)性為各屬性賦權(quán)值,構(gòu)造不同屬性子空間,以最大化簇集質(zhì)量為聚類目標(biāo),在不同子空間上提取各自類簇.

2 問題描述

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

表1 符號(hào)表示

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

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

3.1 屬性分組

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

(1)

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

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

算法1 屬性分組算法 輸入 分類屬性集A={A1,A2…Ad},Ai是數(shù)據(jù)集DB上的第i維屬性.輸出 屬性組AC={AC1,AC2…ACk},ACi是第i個(gè)屬性組.Step1.隨機(jī)選擇一個(gè)屬性,作為初始組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沒有被劃分到任何屬性組內(nèi)then AC=AC∪{ACNEW}= AC∪{{Ai}};endfor Step3.重復(fù)step2 直到各屬性組AC內(nèi)的屬性基本不變;

通過算法1,可形成若干屬性組,組內(nèi)屬性高度相關(guān).在高維數(shù)據(jù)聚類過程中,屬性子空間上的屬性彼此相關(guān)程度很高,往往更能預(yù)示出不同類簇的隱含信息.因此,基于屬性相關(guān)技術(shù)劃分出的屬性組是構(gòu)建屬性子空間的關(guān)鍵環(huán)節(jié).

3.2 去除冗余屬性

在算法1所形成的屬性組中,有一些屬性組內(nèi)只包含了一個(gè)屬性,可認(rèn)為這些屬性與其他屬性不相關(guān)或是冗余屬性,需要被刪除.識(shí)別并刪除冗余屬性的過程,見算法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 計(jì)算權(quán)重

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

(2)

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

計(jì)算各屬性權(quán)重值是構(gòu)建屬性子空間的關(guān)鍵環(huán)節(jié),軟子空間聚類的價(jià)值在于所有屬性均參與聚類過程,但參與度卻決于其權(quán)重值.算法SSC計(jì)算屬性權(quán)值的具體過程,見算法3:

3.4 子空間聚類

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

(3)

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

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

(4)

其中,P(aij)表示屬性值aij在屬性Aj上的出現(xiàn)頻率,P(aij|Cs)表示在簇Cs內(nèi),屬性值aij在屬性Aj上的出現(xiàn)頻率,W(Aj)表示屬性Aj的權(quán)值.

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

(5)

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

SSC算法在所構(gòu)建的屬性子空間的基礎(chǔ)上,以最大化簇集質(zhì)量為聚類目標(biāo),迭代調(diào)整各類簇內(nèi)的數(shù)據(jù)分布.具體算法過程如下:

4 實(shí)驗(yàn)與分析

4.1 測(cè)試數(shù)據(jù)集與評(píng)價(jià)標(biāo)準(zhǔn)

4.1.1 測(cè)試數(shù)據(jù)集

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

表2 測(cè)試數(shù)據(jù)集

4.1.2 評(píng)價(jià)標(biāo)準(zhǔn)

本文采用外部評(píng)價(jià)指標(biāo),調(diào)整蘭德系數(shù)ARI、純度Purity、雅克比系數(shù)Jaccard以及蘭德系數(shù)RI,作為算法SSC與其他對(duì)比算法的評(píng)測(cè)依據(jù).ARI主要測(cè)試聚類結(jié)果和真實(shí)類簇之間數(shù)據(jù)分布的吻合程度;Purity評(píng)測(cè)每個(gè)類簇中的主導(dǎo)數(shù)據(jù)占總數(shù)據(jù)的比例;Jaccard系數(shù)度量同類數(shù)據(jù)對(duì)在同一類簇中的占比;RI評(píng)測(cè)同類數(shù)據(jù)對(duì)被聚合以及異類數(shù)據(jù)對(duì)被分離的比例[15].

4.2 對(duì)比算法

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

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

5 實(shí)驗(yàn)結(jié)論

5.1 聚類性能對(duì)比實(shí)驗(yàn)

本實(shí)驗(yàn)主要測(cè)試算法SSC與其他對(duì)比算法在UCI數(shù)據(jù)集和人工合成數(shù)據(jù)集上的聚類效果,分別從聚類指標(biāo)ARI、Purity、Jaccard以及RI四方面對(duì)比各算法在聚類性能上的差異并分析其原因.

5.1.1 UCI數(shù)據(jù)集上的對(duì)比實(shí)驗(yàn)

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

(a)ARI值對(duì)比

5.1.2 人工合成數(shù)據(jù)集上的對(duì)比實(shí)驗(yàn)

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

圖2 各算法在人工合成數(shù)據(jù)集上的性能對(duì)比

5.2 算法效率對(duì)比實(shí)驗(yàn)

5.2.1 數(shù)據(jù)量上的可擴(kuò)展性實(shí)驗(yàn)

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

圖3 數(shù)據(jù)量上的可擴(kuò)展性實(shí)驗(yàn)

5.2.2 維度上的可擴(kuò)展性實(shí)驗(yàn)

圖4表明了隨著數(shù)據(jù)集DB1屬性的增加,四種算法在運(yùn)行時(shí)間上的差異.算法DHCC的維度可擴(kuò)展性最優(yōu),而算法PROCAD是四種算法中受維度增長(zhǎng)影響最大的.在數(shù)據(jù)量擴(kuò)展性能對(duì)比實(shí)驗(yàn)中,算法SSC僅比算法DHCC的表現(xiàn)略差,而在維度可擴(kuò)展性上,算法SSC僅優(yōu)于算法PROCAD,分析原因可知,算法SSC利用屬性分組技術(shù)對(duì)所有屬性的相關(guān)性進(jìn)行分析計(jì)算,同時(shí),利用多屬性組之間的相互作用評(píng)價(jià)屬性權(quán)重,這樣的度量方式會(huì)受到屬性數(shù)量的影響,當(dāng)屬性量遞增時(shí),算法在權(quán)重計(jì)算上所花費(fèi)的時(shí)間也隨之增加,特別是,當(dāng)屬性量大,屬性之間的相互關(guān)系逐漸復(fù)雜時(shí),這種時(shí)間成本增加的趨勢(shì)也越加明顯.

6 結(jié)論與展望

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

本文下一步的研究方向?qū)⒓?xì)化權(quán)重計(jì)算度量粒度,以屬性取值為度量單位,而非整個(gè)屬性;升級(jí)冗余屬性的判斷依據(jù),在屬性成組之前去除冗余屬性的干擾;設(shè)計(jì)并實(shí)現(xiàn)算法并行化以適應(yīng)海量數(shù)據(jù)的聚類需求.