面向不完備分類型矩陣數據的集對k-modes聚類算法

張春英，高瑞艷，王佳昊，陳 松，劉鳳春，任 靜，馮曉澤

1(華北理工大學 理學院，河北 唐山 063210) 2(華北理工大學 遷安學院，河北 唐山 063210) 3(河北省數據科學與應用重點實驗室，河北 唐山 063210)

1 引 言

聚類是一個基礎研究領域，在數據分析中起著重要的作用.在原型聚類中，k-means聚類算法[1，2]對于處理大型數據集非常有效，但其僅適用于數值型數據集，并不適用于處理分類型數據集.為此，Huang提出了k-modes算法[3]，通過分類樣本的簡單匹配來計算兩個樣本之間的距離，解決了分類型數據的聚類問題.此后，學者們在更好的初始化技術或更有效的距離度量方面，對k-modes算法進行了許多改進[4-7]，但其處理的都是由一組屬性特征描述的樣本，而在實際數據庫中，存在由多組屬性特征描述的矩陣樣本數據[8].例如，用戶的購物記錄，每個用戶是一個樣本，然而每個用戶都會購買多個商品，而且購買的商品種類和數量也不相同，因此，就會產生分類型矩陣樣本數據.傳統的簡單匹配計算兩個樣本之間距離的方式不能直接用于處理這類數據集.另外，由于數據遺漏、不完整、讀取限制等現象，會導致大量缺失值存在.例如，用戶的購物記錄，由于數據存儲過程不當和出于保護用戶隱私的目的，就會存在某些記錄值缺失的情況，因此，有必要研究不完備矩陣數據集的聚類問題.

傳統聚類算法的結果，是用具有清晰邊界的集合表示，其只能表示樣本與類簇之間的兩種關系，即樣本在集合中則屬于類簇，否則不屬于，而在許多應用中，樣本與類簇之間存在3種類型的關系：屬于、可能屬于和不屬于，是因為目前所收集的信息具有局限性，對于有些樣本和類簇之間的關系無法進行準確判斷，則給出第3種關系：可能屬于.為此，Yu在傳統聚類的基礎上，引入三支決策[9，10]的思想并提出了三支聚類的框架[11]，其聚類結果通過兩個集合表示，分別是典型對象集合和邊緣對象集合.然而，考慮樣本和類簇之間3種關系的聚類算法大多是針對數值數據設計的，對分類數據的研究較少.

在分類型數據聚類的研究中，傳統距離度量方法一般只能使用一個特征向量來表示具有多組屬性特征描述的矩陣數據，然而這樣會導致丟失大量原始信息，不能做到對所有的數據進行綜合考慮.另外，通常面臨的數據帶有缺失值，是一種不完備矩陣數據.為了解決上述具有不完備、分類型矩陣數據集的聚類問題，同時考慮樣本和類簇間的不確定關系，提出了一種面向不完備分類型矩陣數據的集對k-modes聚類算法(MD-SPKM).

1)為了解決矩陣數據集不完備、不確定性的問題，將集對信息粒[12](set pair information granule)的相關理論引入到k-modes聚類算法中，對傳統k-modes算法的距離公式進行改進，提出了矩陣樣本間的集對距離度量公式；

2)考慮樣本和類簇間的不確定關系，給出了類內平均距離的定義，用于將肯定屬于類簇的樣本與可能屬于類簇的樣本進行區分.此外，針對樣本可能與多個類簇存在關系的情況，給出了判斷樣本是否屬于多個類簇的閾值計算公式；

3)提出了面向不完備分類型矩陣數據的集對k-modes聚類算法，形成了由正同域、邊界域和負反域組成的集對聚類結果，正同域中的樣本肯定屬于這個類簇，邊界域中的樣本可能屬于這個類簇，負反域中的樣本不屬于這個類簇；

4)與現有4種代表性算法進行實驗對比分析，結果表明該算法可以有效處理不完備分類型矩陣數據集.

2 相關工作

在聚類算法中，樣本間距離度量是很關鍵的一步，針對分類型數據，學者們提出了多種距離度量方法.比如，Huang等[13]提出的基于相互依存冗余度量的計算方法，不僅考慮了兩個樣本之間屬性值本身的差異性，而且考慮了屬性之間的相互影響；Zhou等[14]提出了一種針對k-modes聚類算法的全局關系差異度量方法，其不僅考慮了樣本與所有聚類modes之間的關系，而且考慮了各種屬性的差異，而不是簡單的匹配.然而，這些距離度量方法針對的是只有一個特征向量表示的樣本，可以得到較好的聚類結果，但是對具有多組屬性特征描述的矩陣樣本，在對其進行距離度量時，只能選擇其中的一組特征來進行距離計算，不能做到對所有數據進行考慮.因此，Cao等提出了處理集值樣本的Set-Valued k-modes算法[15]和fuzzy SV-k-modes算法[16]，為具有集值特征的兩個樣本之間定義了距離函數，并提出了聚類中心的集值模式表示.另外，Li等提出了一種用于分類型矩陣數據的MD fuzzy k-modes算法[17]，并給出了聚類中心的啟發式更新算法.上述算法雖然解決了矩陣數據的聚類問題，然而其算法主要針對完備數據集.對于樣本中存在的缺失值不能給予恰當的處理，因為缺失的屬性值本身就具有不確定性，無論是將其刪除或者填充，都會造成一定的誤差.集對信息粒理論是對現有粒計算模型的拓展，將粒空間劃分成正同粒、差異粒和負反粒，可以從多個角度對問題域的相同程度、對立程度以及不確定程度進行全面刻畫.因此，本文將集對信息粒的知識引入到聚類分析中，對不完備矩陣數據集的聚類問題進行研究.

由于樣本與類簇之間存在3種關系，學者們為了更好的刻畫這種關系提出了多種三支聚類算法，如Wang等[18]基于數學形態學的腐蝕和膨脹提出的三支聚類框架；Zhang[19]根據三支權重和三支分配方法，將粗糙k-means(RKM)進行擴展，得到一種三支c-means聚類算法等.然而，上述算法的研究對象是數值型數據，關于分類型數據的研究較少，此外，目前還沒有發現針對不完備分類型矩陣數據在樣本和類簇之間不確定關系方面的研究工作，因此，本文將基于集對信息粒理論，提出一種面向不完備分類型矩陣數據的集對k-modes聚類算法，可以很好的對樣本和類簇之間的關系進行表示.

3 相關理論

為了更好的度量不完備矩陣樣本之間的距離，本文將集對信息粒理論引入到聚類分析中，對傳統距離度量方式進行改進，涉及的相關定義如下：

3.1 不完備的矩陣樣本

3.2 集對信息粒

集對分析[20]是以同、異、反來描述事物的一種理論.將兩個事物所具有的特性作同異反分析，得出兩個事物的同異反聯系度表達式：ρ=a+bi+cj.a表示正同度，b表示差異度，c表示負反度，其中，i∈[-1，1]，j=-1分別稱為差異度和負反度標記符號，用以識別分類信息的方向和不確定程度.

τXC：W0→[0，1]，x→τXC(x)=aR+cR

τXU：W0→[0，1]，x→τXU(x)=bR

τXCs：XC→[0，1]，x→τXCs(x)=aR

τXCo：XC→[0，1]，x→τXCo(x)=cR

定義3[21].設n個聯系數，ρ1=a1+b1i+c1j，ρ2=a2+b2i+c2j，…，ρn=an+bni+cnj，n個聯系數之和仍是一個聯系數：

ρ=ρ1+ρ2+…+ρn=a+bi+cj

(1)

式(1)中，a=(a1+a2+…+an)，b=(b1+b2+…+bn)，c=(c1+c2+…+cn).

3.3 傳統k-modes算法

k-modes算法[3]是對k-means算法的擴展，擴展后的k-modes具有以下特征：

1)使用簡單匹配的距離度量方式；

2)采用modes替代means來更新聚類中心；

3)采用頻率相關策略對modes進行更新.

這些擴展排除了k-means算法中的數值限制，使得聚類能夠應用到分類型數據集中.

設U={X1，X2，…，Xn}是一組分類型數據的集合，每個樣本Xi={Xi1，Xi2，…，Xim}(1≤i≤n)由m個屬性A1，A2，…，Am描述.集合Qj(1≤j≤k)是類簇Cj的modes，任意的Cj由ni個樣本組成，其中Cj={v1，v2，…，vni}，每個類簇的Qj取每個類別屬性中出現頻率最高的值.

給定任意兩個樣本Xi和Xj，距離度量公式為：

(2)

k-modes聚類算法的目標函數為：

(3)

wij∈{0，1}，1≤j≤k，1≤i≤n；

4 集對k-modes聚類算法

4.1 矩陣樣本間的集對距離度量

傳統k-modes的距離度量方式只能適用于只有一組屬性特征描述的樣本，對于具有多組屬性特征描述的矩陣型分類數據卻存在一定的局限性.為了解決不完備、矩陣樣本的距離度量問題，本文結合集對信息粒的相關理論，提出了基于集對聯系度的距離公式，是將原本聚類過程中不同樣本之間的距離擴展成包含正同度、差異度和負反度3個維度的距離定義.

定義4.(單一屬性下的集對聯系度)：給定矩陣樣本Xi和Xj，每個樣本由m個屬性A1，A2，…，Am描述.將矩陣樣本Xi，Xj在屬性As下建立集對聯系度，屬性值相同的作為正同信息粒S，缺失的作為差異信息粒Q，其他的作為負反信息粒F.具體是將兩樣本在屬性As下的記錄值進行同異反分析，若對某一記錄值，兩樣本中各有一條，則將這兩條記錄值都劃分為正同信息粒；若存在缺失記錄值，則將缺失的記錄值劃分為差異信息粒；將剩余的其他記錄值劃分為負反信息粒，則在單一屬性As下建立的集對聯系度公式為：

(4)

式(4)中，S的取值為相同記錄值的個數，Q的取值為缺失記錄值的個數，F的取值為其他記錄值的個數，N的取值為兩個樣本屬性記錄值個數之和.特別注意的是當數據集是完備數據集時，不存在缺失值，則差異信息粒的個數為0.

式(4)也可以簡化為：

(5)

在上述定義4中給出的是，只考慮兩個矩陣樣本的一組屬性特征建立的集對聯系度.為了能夠全面考慮多組屬性特征，在定義4的基礎上，在定義5中給出了考慮多組屬性特征的綜合集對聯系度的定義.

(6)

接下來，給出了一個計算兩個矩陣樣本X1，X2之間集對聯系度的例子：

表1所示是一個矩陣樣本數據集，其中X={X1，X2}，A={A1，A2，A3}，樣本X1，X2之間的集對聯系度計算如下：

表1 矩陣樣本數據集

樣本X1和X2在屬性A1下的集對聯系度為：

樣本X1和X2在屬性A2下的集對聯系度為：

樣本X1和X2在屬性A3下的集對聯系度為：

樣本X1和X2的綜合集對聯系度為：

定義6.(勢函數)：對于兩個矩陣樣本之間建立的三元集對聯系度ρ=a+bi+cj，其勢函數記為：

(7)

定義7.(集對距離度量)：兩個矩陣樣本Xi，Xj之間建立的三元集對聯系度為ρ=a+bi+cj，為了衡量兩個樣本之間的距離大小，并綜合考慮集對聯系度中的正同度、差異度和負反度，故根據集對聯系度中的正同度a以及勢函數Shi(ρ)來反映兩個樣本之間的距離大小，公式為：

d(Xi，Xj)=1/[a+Shi(ρ)]

(8)

式(8)中，a+Shi(ρ)表示兩個矩陣樣本之間的相似性，其中，a+Shi(ρ)的值越大，代表兩矩陣樣本之間的相似性越大.d(Xi，Xj)代表兩矩陣樣本之間的距離，其值越小表明兩個樣本之間距離越小.a用來衡量樣本間屬性值相同的程度，a越大表示兩樣本的相同程度越高，Shi(ρ)用來衡量兩個樣本之間相似性的變化趨勢，Shi(ρ)的值越大表示兩樣本之間的相似性越大.雖然集對距離度量公式中只有正同度a和負反度c，但由于a+b+c=1，即b=1-c-a，則間接考慮了差異度b.

4.2 集對k-modes聚類結果表示

在集對信息粒空間中，定義了3種信息粒集：正同粒集、差異粒集和負反粒集.正同粒集和負反粒集屬于確定信息粒，差異粒集屬于不確定信息粒，其3種信息粒集正好對應聚類中存在的3種關系，因此將集對信息粒的相關理論引入到k-modes聚類中，從3種信息粒集的概念出發，提出了以正同域Cs，邊界域Cu，負反域Co表示的集對聚類結果.正同域中的樣本一定屬于這個類簇，邊界域中的樣本可能屬于這個類簇，負反域中的樣本不屬于這個類簇，這3個域具有如下性質：

(i)Cs(Ci)≠?

(iii)Cs(Ci)∩Cs(Cj)=?，i≠j

性質(i)表明每個類簇的正同域不是空集，至少有一個樣本在正同域中；性質(ii)表明每個樣本都必須被劃分；性質(iii)表明任意兩個類簇的正同域相交為空集.

4.3 算法設計思想與實現

針對不完備、分類型矩陣樣本的特性，定義7中給出了基于集對信息粒的樣本間距離度量方法.將該集對距離度量方法應用到k-modes聚類中，提出一種面向不完備分類型矩陣數據的集對k-modes聚類算法.在傳統k-modes算法中，是用具有清晰邊界的集合表示一個聚類，只考慮了樣本與類簇之間的兩種關系：屬于和不屬于，然而將不確定的樣本分配到一個類簇會降低聚類結果的精確性.為此，本文在k-modes聚類算法的基礎上進行改進，提出的集對k-modes聚類算法考慮了樣本和類簇間的不確定關系，每個類簇由正同域Cs，邊界域Cu和負反域Co表示.本文算法中涉及的相關定義如下：

定義8.(類內平均距離)：假設類簇Cj(1≤j≤k)中的樣本數目為n，給定μj為類簇Cj的聚類中心，任意兩個樣本Xi，Xj間的距離為d(Xi，Xj)=1/[a+Shi(ρ)]，則類簇Cj內的平均距離為：

(9)

定義9.(閾值αj)：假設類簇Cj(1≤j≤k)的邊界域中有n個樣本，類簇Cj(1≤j≤k)的聚類中心記為μj，令樣本Xi與聚類中心μj的距離為dij，樣本Xi與其他類簇的聚類中心的距離中最小值為dih(1≤h≤k，h≠j)，則類簇Cj的閾值αj(1≤j≤k)為：

(10)

位于正同域中的樣本肯定屬于該類簇，且只屬于這一個類簇，然而，位于邊界域中的樣本，可能與多個類簇存在關系，因此需要對每個類簇邊界域中的樣本進行計算判斷.(dih-dij)表示樣本Xi與所在類簇中心之間的距離和與其他類簇中心之間的最小距離的差值，該差值越大代表該樣本距離其他類簇越遠，屬于其他類簇的可能性越小.

對于每個類簇，設定了一個閾值用于判斷樣本Xi是否與其他類簇存在關系，閾值αj的確定是根據(dih-dij)的均值，對于每個樣本，若計算得到的差值比閾值小，說明該樣本與其他類簇存在一定的關系，故將該樣本也分配到其他類簇Ch的邊界域中，使其同時位于兩個類簇.

本文MD-SPKM算法將聚類過程主要分成以下幾部分：

1)初始樣本的劃分

假設U={X1，X2，…，Xn}是一組n個矩陣樣本的集合，從樣本集U中隨機選取k個矩陣樣本作為初始聚類中心{μ1，μ2，…，μk}.根據公式(5)和公式(6)，將樣本集中的每個樣本Xi(1≤i≤n)與各聚類中心μj建立集對聯系度.再根據集對距離公式(8)，得到每個樣本與各個聚類中心的距離d(Xi，μj)，選擇距離最近的聚類中心確定Xi的類簇標記λi=argminj∈{1，2，…，k}d(Xi，μj)，將樣本Xi劃入相應的類簇：Cλi=Cλi∪{Xi}.

2)聚類中心更新

3)集對聚類結果生成

C={{Cs(C1)∪Cu(C1)}，{Cs(C2)∪Cu(C2)}，…,{Cs(Ck)∪Cu(Ck)}}

其中，Cs(Ck)是類Ck的正同域，Cu(Ck)是類Ck的邊界域，正同域和邊界域共同構成一個類簇，聚類結果的示意圖如圖1所示.

圖1 集對k-modes聚類示意圖

算法具體實現流程如下：

算法.MD-SPKM

輸入:樣本集U={X1，X2，…，Xn}，類簇數目k

輸出：集對聚類結果為：C={{Cs(C1)∪Cu(C1)}，

{Cs(C2)∪Cu(C2)}，…，{Cs(Ck)∪Cu(Ck)}}

1.從樣本集U中隨機選取k個樣本，作為初始聚類中心{μ1，μ2，…，μk}；

2.令Cj=?(1≤j≤k)

3.fori=1，2，…，ndo

4. 根據公式(8)計算每個樣本Xi與聚類中心μj的距離d(Xi，μj)，

令λi為簇標記；

5.λi=arg minj∈{1，2，…，k}d(Xi，μj)，將樣本Xi劃入相應的類簇：

Cλi=Cλi∪{Xi}；

7.Q是更新后的聚類中心；

8.end for

9.repeat

10.fori=1，2，…，ndo

11. 重新計算每個樣本與當前類簇聚類中心的距離；

12. if存在樣本與另一個類簇的距離更近then；

13. 將樣本重新分配到該類簇，并更新這兩個類簇的聚類中心；

14. else

15. 保持當前分配狀態不變；

16. end if

17.end for

18.until沒有樣本改變類簇；

d(Xi，μj)進行比較；

22. 將樣本劃分到類簇Cj的正同域Cs；

23.else

24. 將樣本劃分到類簇Cj的邊界域Cu；

25.end if

26.計算得到邊界域中每個樣本的(dij-dih)值，再根據公式(10)

獲得閾值αj(1≤j≤k)；

27.if(dij-dih)<αjthen

28. 將樣本Xi同時分配到類簇Cj和Ch的邊界域中

29.else

30. 保持樣本Xi當前分配狀態

31.end if

32.returnC={{Cs(C1)∪Cu(C1)}，{Cs(C2)∪Cu(C2)}，…，

{Cs(Ck)∪Cu(Ck)}}

在上述算法中，步驟1-步聚5是根據本文在定義7中提出的集對距離度量方法，得到每個樣本與各個聚類中心的距離，從而將樣本分配到距離最近的類簇中；步驟6是在每次分配一個樣本后，對聚類中心進行更新，使得目標函數最小化；步驟10-步驟17是將所有樣本分配到類簇后，重新計算樣本與各個類簇之間的距離，并將其優化為每個樣本與所在類簇的距離是最近的.接下來，是對初步聚類結果進行細分，主要任務是構造正同域和邊界域.在步驟19-步驟25中，根據定義8中給出的類內平均距離的定義，對各個類簇依次進行處理，將類簇中的樣本劃分到正同域和邊界域；由于邊界域中的樣本有可能屬于多個類簇，因此，在步驟26-步驟31中，根據定義9中的閾值計算公式，對邊界域中的樣本進行判斷，若樣本與多個類簇存在關系，將其同時分配到這些類簇的邊界域；最后，輸出包含正同域和邊界域的集對聚類結果.

4.4 算法復雜度分析

由于在當下大多數實際應用場景下，數據具有大量的屬性，會對算法的效率具有一定的影響，故令論域中樣本數目為n，屬性數目為m，類簇數目為k.本文算法的復雜度主要由兩部分產生，第1部分是計算樣本與各個聚類中心的距離產生的復雜度為O(kmn)，令迭代次數為t，則產生的時間復雜度為O(tkmn).第2部分是由對初步聚類結果細化，將每個樣本劃分到相應類簇的正同域或邊界域產生，其時間復雜度為O(kmn).所以，整個MD-SPKM算法產生的時間復雜度為O(tkmn)+O(kmn).

5 實驗評價

在這一部分中進行了一系列的實驗，來評估所提算法MD-SPKM的聚類性能，通過選取4種代表性的算法進行了實驗對比.第1種是Huang提出的經典k-modes算法[3]，第2種是Cao等提出的基于矩陣樣本的k-mw-modes算法[8]，第3種是Li等提出的MD fuzzy k-modes 算法[17]，第4種是Saha等提出的基于粗糙集的Fuzzy k-modes算法[23]，將其記為RFKMd算法.

為了證明MD-SPKM算法的有效性，將從兩個方面進行實驗評價:1)以Microsoft Web數據集為例，對算法的性能進行分析；2)選擇不完備的矩陣數據集，在不同缺失率的條件下，通過4個聚類評價指標，將本文所提算法MD-SPKM與4個對比算法進行比較分析.

本文在一臺DELL計算機(Windows 10，Intel(R)Core(TM)i5-8300H，CPU@ 2.30 GHz 2.30 GHz)上實現了該算法和對比算法，編程平臺為Python3.7.

5.1 數據集與評價指標

在本實驗中，選擇了3個數據集來評估算法，分別是Musk、Microsoft Web和MovieLens.Musk從UCI數據庫下載，包含92個樣本的476條記錄值，每個樣本有167個屬性；Microsoft Web數據集也從UCI數據庫下載，包含32711個用戶對294個網站的165257條記錄值，每條記錄有用戶ID，網頁ID兩個屬性；MovieLens數據集在2018年創建，從MovieLens website下載，本文使用了其中的ratings數據，包含了6040名用戶對3900部電影的1000209個評級分值，其中每條記錄值有用戶ID，電影ID，評分等級和提交時間4個屬性.本文實驗選擇將不影響聚類結果的提交時間屬性刪除.由于具有標簽信息的矩陣樣本數據是比較少見的，因此，需要對給定的數據進行預處理，本文采用多維標度法對數據進行處理，預處理后的最終數據集如表2所示.

表2 矩陣數據集的描述

聚類的評價，也稱為聚類有效性，是評價聚類算法性能的關鍵過程.以下評價指標常用于評價聚類算法的性能.

C={{Cs(C1)∪Cu(C1)}，…，{Cs(Ck)∪Cu(Ck)}}

1)準確率(Accuracy)

(11)

式(11)中，n為樣本的總數，θk為簇Ck中正確劃分的樣本數目，包含正同域和邊界域中的樣本.

2)召回率(Recall)

(12)

式(12)中，TP表示真實為正，預測也為正的個數，FN表示真實為正，預測為負的個數.

3)調整蘭德系數(ARI)

(13)

4)標準化互信息(NMI)

(14)

5.2 實驗結果及分析

5.2.1 MD-SPKM算法性能分析

為了更好的展示本文所提算法MD-SPKM的聚類效果，以Microsoft Web數據集為例，給出了迭代過程中評價指標的變化情況.由于每個類簇都是由正同域和邊界域構成，所以在圖2(a)中給出了在4個評價指標下僅包含正同域Cs(Cj)的計算結果，在圖2(b)中給出了在4個評價指標下包含正同域和邊界域Cs(Cj)∪Cu(Cj)的計算結果.

圖2 Microsoft Web數據集的迭代聚類過程

MD-SPKM算法可以做到考慮樣本和類簇間的不確定關系，將肯定屬于該類簇的樣本劃分到正同域，將可能屬于該類簇的樣本劃分到邊界域.從圖2可以看到，隨著迭代次數的增加，4個指標的結果都在不斷上升.然而，在所有指標下，正同域和邊界域結合的結果均高于僅考慮正同域的，其原因是每個類簇被劃分為正同域和邊界域兩部分，這兩個集合是通過基于二支聚類的收縮或擴展得到的.在圖2(a)中得到的最優聚類結果是準確率0.9296、召回率0.9552、ARI 0.7383以及NMI 0.6405.在圖2(b)中雖然僅考慮正同域，但準確率依然達到了0.8981，ARI達到了0.7，NMI達到了0.5856，僅召回率下降幅度稍大，下降為0.5994，但總體仍得到了較好的聚類結果.

5.2.2 不同缺失率下的實驗對比分析

為了模擬含有缺失值的數據集，隨機選擇刪除了一些樣本的屬性值.在實驗中，選用5%、10%、15%和20%的缺失率隨機生成不完備矩陣數據集，為了消除缺失數據結構或分布的影響，在每個缺失率下，生成多個不同的數據集，然后取多次運行得到的實驗結果的平均值.本文選取了4種算法與所提算法MD-SPKM進行比較，這4種算法分別是k-modes[3]，k-mw-modes[8]，MD fuzzy k-modes[17]和RFKMd[23].通過4個評價指標對Musk、Microsoft Web和MovieLens數據集在不同缺失率下進行實驗評價，其結果如表3-表5所示，每個數據集在不同缺失率下的最佳性能已用黑體突出顯示.

表3 Musk數據集在4種缺失率下的聚類結果

從表3-表5中可以看到，在多數情況下，MD-SPKM算法比k-modes，k-mw-modes，MD fuzzy k-modes以及RFKMd算法具有更好的聚類性能，特別是在Microsoft Web數據集，在4種缺失率下實現了所有指標均高于對比算法，這也表明了MD-SPKM算法的優越性.表3中給出的是Musk數據集的實驗結果，MD-SPKM算法在缺失率為5%和10%的條件下，得到的聚類結果均優于對比算法，在缺失率為15%時，雖然它不是最好的算法，但準確性也接近最好的對比算法.表5中給出的是MovieLens數據集在不同缺失率下的實驗結果，可以看到在缺失率為5%、10%、15%和20%時，MD-SPKM算法在指標準確率、Recall和ARI下的結果均高于對比算法.另外，對于指標NMI，在缺失率為5%和10%的條件下，對比算法k-mw-modes達到了最好的效果，雖然MD-SPKM算法不是最優的，但也高于其他3個對比算法.

表4 Microsoft Web數據集在4種缺失率下的聚類結果

表5 MovieLens數據集在4種缺失率下的聚類結果

另外，從表3-表5中可分析出，在缺失率增加的情況下，本文算法和對比算法的準確性都呈現下降的趨勢，導致下降的原因是缺失率越高，數據中的確定性信息越少，不確定性信息越多，相應作出錯誤分類的可能性就越高，這也與實際一致.

本文實驗中選取的3個數據集都是不完備、矩陣數據集.由于對比算法k-mw-modes和MD fuzzy k-modes的研究對象都是完備矩陣數據集，未考慮缺失值對實驗結果的影響.另外，對比算法RFKMd和k-modes，都是用于處理僅一組屬性特征描述的數據集，不能充分考慮數據的所有信息.然而在本文中，根據集對信息粒理論，提出了一種可以處理不完備、矩陣數據集的距離度量方法，并對傳統k-modes算法進行改進，從而實現了較對比算法性能的提升.

6 結 論

本文對傳統k-modes算法進行改進，提出了一種面向不完備分類型矩陣數據的集對k-modes聚類算法.首先，對數據集中的缺失值給出了處理方法，采用集對信息粒的相關理論，對樣本進行粒化處理，劃分成正同粒、差異粒、負反粒，提出了矩陣樣本間的集對距離度量方法.將聚類過程中不同樣本之間的距離擴展成包含正同度、差異度和負反度3個維度的距離定義，由此將樣本劃分到各個類簇，形成初步的聚類結果.其次，考慮樣本和類簇間的不確定關系，給出了類內平均距離的定義，用于將肯定屬于類簇的樣本與可能屬于類簇的樣本進行區分.另外，給出了判斷樣本是否屬于多個類簇的閾值計算公式，對初步的聚類結果進行細分，形成包含正同域，邊界域和負反域的集對聚類結果.最后，利用選取的3個數據集與四個對比算法進行實驗評價，結果表明，本文所提MD-SPKM算法可以有效處理不完備矩陣數據集，并在多項評價指標下優于對比算法.