基于k多數值代表的混合矩陣對象數據聚類

趙 健

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

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

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

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

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

1 矩陣對象數據的聚合

1.1 問題描述

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

(1)

1.2 算法設計

1.2.1 兩個數值矩陣對象間的相異度

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

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

(2)

其中

(3)

定義2[6]已知由m屬性{A1,A2,…,Am}定義的數值矩陣對象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 啟發式聚類中心更新方法

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

(6)

已知矩陣對象Xi(Xi∈X), 由式(2)可知,n_fi(v)為屬性值v在Xis內相鄰值的個數,n_fi(v)/ri為屬性值v在Xis內的重要程度.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啟發式聚類中心更新算法.

輸入：m屬性描述的n數值矩陣對象集X, 用于計算相鄰值的參數集ε={ε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)內的數值矩陣對象集X={X1,X2,…,Xn}, 使用k-Mnv-Rep算法對下列目標函數最小化：

(7)

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

對目標函數的最小化為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數值矩陣對象集X, 需聚合的聚類個數k, 閾值o;

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

步驟1) 生成隨機數k, 通過指數取得初始中心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內兩個數值矩陣對象間相異度的復雜性可表示為O(|Vs|), 屬性m內兩個數值矩陣對象間相異度的計算復雜性可表示為O(m|V′|), 其中|V′|=max{|Vs|, 1≤s≤m}.

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

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

1.3 用于處理混合矩陣對象數據的算法

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

(8)

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

(9)

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

(10)

其中

(11)

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

(12)

其中

(13)

1.3.2 屬性值的權重更新方法

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

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

(14)

1.3.3k-Mv-Rep算法

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

(15)

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

算法3k-Mv-Rep算法.

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

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

步驟1) 生成k個隨機數, 通過指數取得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}. 因此, 該算法的計算時間復雜性與矩陣對象數量、 屬性數量、 聚類數量和屬性值數量呈線性正相關.

2 實驗與分析

2.1 評估指標

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

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

2.2 數值矩陣對象數據實驗

2.2.1 真實數據集

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

表1 數據集信息

2.2.2 比較結果

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

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

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

表2 不同算法9個數值型數據集的比較結果

續表2

續表2

續表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算法優于其他對比算法.

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

2.3 混合矩陣對象數據實驗

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

2.3.1 真實混合數據集

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

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

圖2 數據集Author的分布Fig.2 Distribution of data set Author

表4 數據集Author信息

2.3.2 對比結果分析

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

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

表5 兩種算法在數據集Author中的實驗結果對比

2.4 參數ε對算法的影響

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

圖3 不同ε在10個數據集內的準確率Fig.3 Accuracy of differnt ε in ten data sets

圖4 不同ε在10個數據集內的迭代次數Fig.4 Iterations of differnt ε in ten data sets

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

2.5 聚合性檢驗

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

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

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

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

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

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