基于k多數(shù)值代表的混合矩陣對象數(shù)據(jù)聚類

趙 健

(長治學院 計算機系, 山西 長治 046011)

數(shù)據(jù)的多樣性與復雜性導致每個記錄都是一個特征向量, 每個對象都由多個特征向量組成, 每個對象稱為矩陣對象, 這類數(shù)據(jù)廣泛應用于銀行、 保險、 電信、 零售、 醫(yī)學等領域[1-2]. 在大多數(shù)情況下, 矩陣對象由分類屬性和數(shù)字屬性共同描述, 而用戶行為的變化是一個隨時間變化的動態(tài)演化過程, 因此如何實現(xiàn)有效矩陣對象數(shù)據(jù)聚類成為研究的熱點[3].

用傳統(tǒng)聚類算法解決上述問題, 需對矩陣對象數(shù)據(jù)進行變換, 主要有兩種方法： 一種是將矩陣對象壓縮成一個向量, 常用的壓縮方法是分別用分類屬性和數(shù)值屬性的模式和方法表示矩陣對象. 文獻[4]為克服不同初始類中心對聚類結果的影響, 針對分類型矩陣數(shù)據(jù), 提出了一種新的初始聚類中心選擇算法； 文獻[5]提出了三類廣義多實例假設, 并在基于廣義假設條件下建立了一個層次結構； 文獻[6]提出了一種基于簇間信息的分類矩陣對象數(shù)據(jù)的聚類算法, 該算法利用k-modes算法實現(xiàn)矩陣對象聚類. 但上述方法使數(shù)據(jù)大部分信息丟失, 并且只考慮平均值, 不能反映具體的數(shù)據(jù)信息.

另一種方法是將每個屬性值視為一個新的屬性進行處理. 文獻[7]通過給出一種矩陣對象自身的內(nèi)聚度和該矩陣對象與其他矩陣對象之間的耦合度, 定義矩陣對象的孤立因子, 提出了一種基于信息熵的孤立點檢測算法; 文獻[8]基于信息熵定義了一種屬性權重的新度量方法, 并提出一種加權k-prototype算法實現(xiàn)矩陣對象數(shù)據(jù)聚類; 文獻[9]提出了一種基于密度峰值思想的加權猶豫模糊矩陣對象數(shù)據(jù)聚類算法, 該算法不僅降低了簇中心計算的復雜度, 而且提高了對不同規(guī)模以及任意形狀矩陣對象數(shù)據(jù)集的適應性. 但上述方法會使矩陣對象數(shù)據(jù)更稀疏和高維, 從而極大降低了聚類準確性.

為解決傳統(tǒng)聚類方法存在的局限性, 本文提出一種基于k多數(shù)值代表的混合矩陣對象數(shù)據(jù)聚類方法. 通過定義一種新的相異度度量計算兩個數(shù)值矩陣對象之間的差異, 提出k多數(shù)值代表聚類算法實現(xiàn)混合矩陣對象數(shù)據(jù)的聚類. 實驗結果證明了本文方法的有效性.

1 矩陣對象數(shù)據(jù)的聚合

1.1 問題描述

設X={X1,X2,…,Xn}表示由m屬性{A1,A2,…,Am}描述的矩陣對象數(shù)據(jù)集, 其中Xi(1≤i≤n)表示第i個帶有ri個特征向量的矩陣對象, 表示為

(1)

1.2 算法設計

1.2.1 兩個數(shù)值矩陣對象間的相異度

本文將每個矩陣對象作為一個ri_by_m(ri≥1)型矩陣, 且矩陣對象不同, 其ri值也不同.由于由兩個特征向量與兩個矩陣對象間的歐氏距離測得的相異度不符合所有特征向量與矩陣對象觀測分類有關的特征, 所以本文提出一種測量數(shù)值矩陣對象相異度的新方法.已知每個距離需在相同特征空間內(nèi)測量, 假設屬性特征獨立, 兩個矩陣對象間的差異度可通過其特征的差別測得.由于可以將任意矩陣對象視作m型ri維向量, 因此上述問題可轉(zhuǎn)化為測量相同特征空間內(nèi)兩個長度不等的向量之間差異度問題.由于數(shù)值屬性值具有連續(xù)性, 因此上述方法可借助其相鄰值進行測量計算.

定義1[5]假設X為一已知的數(shù)值矩陣對象數(shù)據(jù)集,Vs為X在屬性As內(nèi)的域值集.Xis=(vi1s,vi2s,…,viris)T表示Xi(Xi∈X)的第s個ri維列向量,εs為已知參數(shù), 且?v∈Vs, 上述列向量的相鄰值在Xis內(nèi)的數(shù)量可表示為

(2)

其中

(3)

定義2[6]已知由m屬性{A1,A2,…,Am}定義的數(shù)值矩陣對象Xi和Xj, 則Xi和Xj間的相異度度量可表示為

(4)

其中

(5)

V=Xis∪Xjs, |·|表示絕對值, 并且需加入歸一化因子0.5, 使得0≤n_δ(Xis,Xjs)≤1, 當且僅當Xis∩Xjs=?時,n_δ(Xis,Xjs)=1.

1.2.2 啟發(fā)式聚類中心更新方法

定義3已知由m屬性描述的數(shù)值矩陣對象數(shù)據(jù)集X={X1,X2,…,Xn}.設Vs為X在屬性As內(nèi)的值域集, ?v∈Vs, 其權重表示為

(6)

已知矩陣對象Xi(Xi∈X), 由式(2)可知,n_fi(v)為屬性值v在Xis內(nèi)相鄰值的個數(shù),n_fi(v)/ri為屬性值v在Xis內(nèi)的重要程度.n_fi(v)越高, 表示v在Xis中越重要.被選中的代表聚類中心屬性值應在任一矩陣對象中都較重要.在式(6)中, 有0≤n_fi(v)/ri≤1, 且0≤n_ω(v)≤1.當且僅當n_fi(v)/ri=1(?i∈{1,2,…,n})時, 有n_ω(v)=1.即當且僅當屬性值在任一矩陣對象中很重要時, 該屬性值的權重較高.

算法1啟發(fā)式聚類中心更新算法.

輸入：m屬性描述的n數(shù)值矩陣對象集X, 用于計算相鄰值的參數(shù)集ε={ε1,ε2,…,εm}；

輸出：X的一個聚類中心Q；

步驟1) fors=1∶1∶mdo

步驟2) sum=0,Q=?；

步驟3) fori=1∶1∶ndo

步驟5) end for

步驟6)us=round(sum/n);

步驟7) fort=1∶1∶|Vs| do

步驟9) end for

步驟12)Q=Q∪QAs；

步驟13) end for

步驟14) 返回Q.

1.2.3k-Mnv-Rep算法

已知公式聚類k(?n)內(nèi)的數(shù)值矩陣對象集X={X1,X2,…,Xn}, 使用k-Mnv-Rep算法對下列目標函數(shù)最小化：

(7)

其中W=(ωli)為k_by_n{0,1}矩陣, 當ωli=1時, 將目標Xi分配入聚類l；Q={Q1,Q2,…,Qk},Ql∈Q表示聚類l中的多數(shù)值表示.

對目標函數(shù)的最小化為NP難問題, 一般情況下, 可通過不斷迭代直到完成聚合, 從而解決兩個子問題, 進一步解決F(W,Q)問題: 1) 在迭代t中, 始終令Q=Qt, 利用式(3), 解決F(W,Qt)減小問題, 并找出F(W,Qt)取得最小值時的Wt; 2) 通過運行算法1, 用上述得到的Wt值解決F(Wt,Q)減小問題, 并找出F(Wt,Q)取得最小值時的Qt+1.

算法2k-Mnv-Rep算法.

輸入：m屬性描述的n數(shù)值矩陣對象集X, 需聚合的聚類個數(shù)k, 閾值o;

輸出： 聚合后所有目標的標簽cid;

步驟1) 生成隨機數(shù)k, 通過指數(shù)取得初始中心k；

步驟2) 設Q={Ql,Q2,…,Qk}為初始中心, 且value=0, num=0;

步驟3) while num≤100 do

步驟4) value1=0;

步驟5) fori=1∶1∶ndo

步驟8) end for

步驟9) if |value1-value|≤o, break； else value=value1, 且num=num+1；

步驟10) forl=1∶1∶kdo

步驟11) 運行算法1, 更新聚類中心Ql；

步驟12) end for

步驟13) end while.

對k-Mnv-Rep算法計算復雜性的分析如下.

1) 計算相異度： 屬性As內(nèi)兩個數(shù)值矩陣對象間相異度的復雜性可表示為O(|Vs|), 屬性m內(nèi)兩個數(shù)值矩陣對象間相異度的計算復雜性可表示為O(m|V′|), 其中|V′|=max{|Vs|, 1≤s≤m}.

2) 更新聚類中心： 屬性As屬性值權重的計算復雜性可表示為O(n|Vs|), 屬性m內(nèi)k型聚類中心的計算復雜性可表示為O(kmn|V′|), 其中|V′|=max{|Vs|, 1≤s≤m}.

3) 通過t型迭代進行聚合時,k-Mnv-Rep算法的總計算復雜性可表示為O(tmnk|V′|), 其中|V′|=max{|Vs|, 1≤s≤m}.因此, 該算法的時間復雜性與矩陣對象數(shù)量、 屬性數(shù)量、 聚類數(shù)量和屬性值數(shù)量呈線性正相關.

1.3 用于處理混合矩陣對象數(shù)據(jù)的算法

1.3.1 兩個混合矩陣對象間的相異度

(8)

其中γ為權重, 可使兩種數(shù)據(jù)得到相同處理.As內(nèi)范疇型矩陣對象的距離可表示為

(9)

其中V=Xis∪Xjs, 當兩個參數(shù)相等時,c_g(·,·)=1, 其余情況下,c_g(·,·)=0.需加入歸一化因子0.5, 使得0≤c_δ(Xis,Xjs)≤1.當且僅當Xis∩Xjs=?時,c_δ(Xis,Xjs)=1.

(10)

其中

(11)

定義6設X為由屬性m描述的混合矩陣對象數(shù)據(jù)集.?Xi,Xj∈X,Xi和Xj間的相異度可表示為

(12)

其中

(13)

1.3.2 屬性值的權重更新方法

分別通過數(shù)值屬性和范疇屬性更新聚類中心.在任一屬性中, 更新方法應以較高權重得到若干數(shù)值.權重的定義是更新算法的關鍵.根據(jù)式(10)可知, 當v值已知時, 公式在數(shù)值屬性和范疇屬性內(nèi)一致.因此, 在已知混合數(shù)據(jù)集內(nèi), 屬性值的權重可定義如下.

定義7設X為屬性m描述的含有n個混合矩陣對象的數(shù)據(jù)集,Vs為X在屬性As內(nèi)的域值集, ?v∈Vs, 其權重定義為

(14)

1.3.3k-Mv-Rep算法

設X={X1,X2,…,Xn}為混合矩陣對象數(shù)據(jù)集.k-Mv-Rep算法可以將X聚合入k(≤n)聚類內(nèi), 從而實現(xiàn)下列目標函數(shù)的最小化：

(15)

與k-Mnv-Rep算法相似, 通過使用一種新的啟發(fā)式聚類中心更新方法處理混合矩陣對象數(shù)據(jù)取得F′(W′,Q′)的局部最小值, 取得局部最小的過程與k-Mnv-Rep算法相同.

算法3k-Mv-Rep算法.

輸入： 屬性m描述的n混合矩陣對象數(shù)據(jù)集X, 需聚合的聚類個數(shù)k, 域值o；

輸出： 聚合后所有目標的標簽cid；

步驟1) 生成k個隨機數(shù), 通過指數(shù)取得k個初始中心；

步驟2) 設Q={Q1,Q2,…,Qk}為初始中心, 且value=0, num=0；

步驟3) while num≤100 do

步驟4) value1=0;

步驟5) fori=i∶1∶ndo

步驟8) end for

步驟9) if |value1-value|≤o, break； else, value=value1且num=num+1；

步驟10) forl∶1∶kdo

步驟11) 利用式(14)更新聚類中心Ql；

步驟12) end for

步驟13) end while.

k-Mnv-Rep算法的總計算復雜性可表示為O(tmnk|V′|), 這里t表示迭代, 且|V′|=max{|Vs|, 1≤s≤m}. 因此, 該算法的計算時間復雜性與矩陣對象數(shù)量、 屬性數(shù)量、 聚類數(shù)量和屬性值數(shù)量呈線性正相關.

2 實驗與分析

2.1 評估指標

采用5個外部指標評估上述兩種算法, 分別為精確度(AC)、 準確度(PE)、 召回率(RE)、 調(diào)整蘭德系數(shù)(ARI)和歸一化互信息(NMI)[10].

設X為一矩陣對象數(shù)據(jù)集,C={C1,C2,…,Ck′}為X的聚合結果,P={P1,P2,…,Pk}為X的實分區(qū).nij為Pi和Cj中相同的矩陣對象數(shù)量, 即nij=|Pi∩Cj|,pi和cj分別為Pi和Cj中的矩陣對象數(shù)量.5個評估指標分別定義如下：

2.2 數(shù)值矩陣對象數(shù)據(jù)實驗

2.2.1 真實數(shù)據(jù)集

由于缺少公開數(shù)值矩陣對象, 因此本文實驗使用多示例數(shù)據(jù)集評估k-Mnv-Rep算法, 另一部分實驗圍繞9組真實數(shù)據(jù)集展開, 數(shù)據(jù)集信息列于表1.

表1 數(shù)據(jù)集信息

2.2.2 比較結果

通過表1中9種數(shù)值型數(shù)據(jù)集實驗, 將k-Mnv-Rep算法與使用3種距離表示方式的包級多實例聚類算法(BAMIC)[11]、 自適應鄰域聚類算法(CAN)[12]、 表示自適應鄰域聚類算法(PCAN)[13]、L1范數(shù)垃圾回收算法(CLR-L1)[14]、L2范數(shù)垃圾回收算法(CLR-L2)[15]得出的結果進行比較. 上述后4種算法的輸入數(shù)據(jù)集中, 每個矩陣對象都由一個向量描述. 因此, 以每個矩陣對象的中值作為每個屬性的屬性值.

在實驗過程中, 將8種算法各運行30次, 取最終結果的中值. 設參數(shù)εs大小為第s屬性內(nèi)X標準差的1/2, 在k-Mnv-Rep算法中, 設該參數(shù)為0.2. 不同算法9個數(shù)據(jù)集的對比結果列于表2, 其中符號“±”左側(cè)為中值, 右側(cè)為標準差. 在每個數(shù)據(jù)集中, 對評估指數(shù)值進行排序, 最高值排序為1, 次高值排序為2, 依此類推, 如表2中括號內(nèi)所示. AvgR表示所有算法在9個數(shù)據(jù)集中的平均排序.

由表2可見,k-Mnv-Rep算法的AvgR值在所有評估指數(shù)中排序最高, 即k-Mnv-Rep算法在總體上優(yōu)于上述其他算法. 在8個數(shù)據(jù)集中,k-Mnv-Rep算法的每個評估指標都優(yōu)于其他算法； 在數(shù)據(jù)集Function中, 只有PCAN算法的性能優(yōu)于k-Mnv-Rep算法, 但由于PCAN算法無法處理逆矩陣, 因此該算法不能處理所有數(shù)據(jù)聚類. 并且在數(shù)據(jù)集Messidor,Muta2,Process中, BAMIC-avgH算法優(yōu)于BAMIC-minH算法和BAMIC-maxH算法的AC值; 在數(shù)據(jù)集Muta1,Compon中, BAMIC-maxH算法優(yōu)于BAMIC-minH算法和BAMIC-avgH算法的AC指標; 在數(shù)據(jù)集Elephant,Web2,Musk1,Function中, BAMIC-minH算法的性能最優(yōu). BAMIC算法的其他指標也出現(xiàn)了相同結果. 因此, BAMIC算法很難從3種距離中得出最佳距離.

表2 不同算法9個數(shù)值型數(shù)據(jù)集的比較結果

續(xù)表2

續(xù)表2

續(xù)表2

表3 5類實驗中上述算法的平均排序值

(21)

圖1為8種算法對5個評估指標進行Bonferroni-Dunn實驗的結果, 其中圓圈表示算法的平均排序, 線段表示臨界差CD.由圖1可見,k-Mnv-Rep算法與CAN,PCAN,CLR-L1,CLR-L2四種算法的所有指標均差異較大, 與BAMIC-minH,BAMIC-maxH,BAMIC-avgH三種算法則差異較小. 而BAMIC-minH,BAMIC-maxH,BAMIC-avgH三種算法的指標幾乎無差異, CAN,PCAN,CLR-L1,CLR-L2四種算法的指標幾乎無差異. 從平均排序結果可見,k-Mnv-Rep算法性能最佳. 綜上, 因為k-Mnv-Rep算法的排序較高、 差異值較大, 所以k-Mnv-Rep算法優(yōu)于其他對比算法.

圖1 8種算法在Bonferroni-Dunn實驗中的5個指標Fig.1 Five indexes of eight algorithms in Bonferroni-Dunn experiment

2.3 混合矩陣對象數(shù)據(jù)實驗

下面進行混合數(shù)值矩陣對象實驗, 評估k-Mv-Rep算法的有效性. 已知有真實混合矩陣對象數(shù)據(jù)集, 并已知k-Mv-Rep算法和k型算法的比較結果.

2.3.1 真實混合數(shù)據(jù)集

由于缺少公開混合矩陣對象, 因此本文實驗中使用真實混合數(shù)據(jù)集評估k-Mnv-Rep算法的有效性. 為評估上述算法, 應對上述數(shù)據(jù)集進行結構預處理. 本文用多維尺度法對數(shù)據(jù)進行可視化處理. 由式(12)可得出n_by_n型距離矩陣, 用多維尺度法主要是為了將該矩陣轉(zhuǎn)移到MATLAB生成的mdscale方程中, 從而獲得P維度中n個點的構型.n點間的歐氏距離與n_by_n型距離矩陣中相應相異點的單調(diào)變換大致相同, 因此, 可通過將n點可視化顯示數(shù)據(jù)的分布情況.設P=2, 對數(shù)據(jù)進行可視化.在大多數(shù)實驗案例中, 真實數(shù)據(jù)集的分布通常是無序的.利用可視化, 可通過刪除部分點獲得相對清晰的數(shù)據(jù)結構.

首先從數(shù)據(jù)集Author中選出相應系統(tǒng)內(nèi)符合范圍x<0.55且y>0.16或x<0.55且y<-0.16的目標, 進行可視化后成為一個新數(shù)據(jù)集, 然后對如圖2所示的新數(shù)據(jù)集進行可視化. 利用可視化可推斷出聚類的數(shù)量和每個矩陣對象的標簽信息, 數(shù)據(jù)集Author信息列于表4.

圖2 數(shù)據(jù)集Author的分布Fig.2 Distribution of data set Author

表4 數(shù)據(jù)集Author信息

2.3.2 對比結果分析

已知部分聚類算法無法直接處理混合矩陣目標, 所以應在該子部分內(nèi)應用k型算法. 由于矩陣對象本質(zhì)上是矩陣而非向量, 因此需要將矩陣對象轉(zhuǎn)換為能使用k型算法的形式. 混合矩陣對象范疇屬性的屬性值由模式表示, 數(shù)值屬性的屬性值由中值表示. 這樣即可將混合矩陣對象變形為向量, 從而可以使用k型算法處理矩陣對象數(shù)據(jù)集.

分別運行k型算法和k-Mv-Rep算法50次, 取實驗結果的中值作為最終結果. 設k-Mv-Rep算法的參數(shù)ε=0.2,k型算法γ的參數(shù)值為文獻[16]中所有數(shù)值屬性的標準差, 表5列出了數(shù)據(jù)集Author中k型算法和k-Mv-Rep兩種算法的比較結果. 由表5可見,k-Mv-Rep算法的5個評估指標值均優(yōu)于k型算法, 并且k-Mv-Rep算法比k型算法的精確度約高13%. 因此,k-Mv-Rep算法優(yōu)于k型算法.

表5 兩種算法在數(shù)據(jù)集Author中的實驗結果對比

2.4 參數(shù)ε對算法的影響

k型算法和k-Mv-Rep算法的參數(shù)ε已知, 并作為終止程序的控制條件. 當目標方程的變換小于ε時, 程序終止. 因此, 不同參數(shù)大小可能會產(chǎn)生不同的聚類結果, 如何確定該參數(shù)十分重要. 分別在相應數(shù)據(jù)集內(nèi)按照不同公式運行k型算法和k-Mv-Rep算法各30次, 公式大小變化以0.05為梯度, 由0.05增加至0.35, 并記錄AC的中值和迭代次數(shù), 結果分別如圖3和圖4所示.

圖3 不同ε在10個數(shù)據(jù)集內(nèi)的準確率Fig.3 Accuracy of differnt ε in ten data sets

圖4 不同ε在10個數(shù)據(jù)集內(nèi)的迭代次數(shù)Fig.4 Iterations of differnt ε in ten data sets

由圖3可見, 隨著ε增大, AC在10個數(shù)據(jù)集內(nèi)均有輕微浮動, 但總體穩(wěn)定. 由圖4可見, 隨著ε增大, 迭代次數(shù)在10個數(shù)據(jù)集內(nèi)呈總體下降趨勢, 一般當ε>0.2時, 迭代次數(shù)下降趨勢較緩. 在上述兩種算法中, 綜合AC結果和迭代結果, 令ε=0.2.

2.5 聚合性檢驗

因為本文提出的用于更新聚類中心的k-Mv-Rep算法和k-Mnv-Rep算法均屬于啟發(fā)式算法, 所以要對這兩種算法進行聚合性檢驗, 以保證其合理性. 在所有實驗中, 記錄目標方程值和所有迭代次數(shù). 圖5為目標方程值變化與k-Mv-Rep算法迭代的比值. 由圖5可見, 隨著迭代次數(shù)增加, 目標方程值呈下降趨勢. 在10個數(shù)據(jù)集內(nèi)的聚合性檢驗結果也同樣證明了該結論.

圖5 目標方程值變化與k-Mv-Rep算法迭代的比值Fig.5 Ratio of value change of objective equation to iteration of k-Mv-Rep algorithm

綜上所述, 為解決數(shù)據(jù)的稀疏性和高維問題, 并有效反映聚類中心與聚類內(nèi)矩陣對象的分布, 本文提出了一種基于k多數(shù)值表示的混合矩陣對象數(shù)據(jù)聚類方法. 由真實數(shù)據(jù)集與合成數(shù)據(jù)集的實驗結果可得如下結論：

1) 本文聚類算法對于稀疏數(shù)據(jù)集和高維數(shù)據(jù)集均能保證良好的聚類效果, 證明該方法能解決數(shù)據(jù)集的稀疏和高維問題；

2) 本文算法對于不同的數(shù)據(jù)集均實現(xiàn)了精度較高的聚類, 證明該算法的泛化能力較強, 能有效反映聚類中心與聚類內(nèi)矩陣對象的分布；

3) 本文算法的聚類準確度對于參數(shù)具有良好的魯棒性, 并且聚合性檢驗證明了算法的合理性.