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

（1.華北理工大學(xué)理學(xué)院，唐山，063210；2.華北理工大學(xué)遷安學(xué)院，唐山，063210；3.河北省數(shù)據(jù)科學(xué)與應(yīng)用重點(diǎn)實(shí)驗(yàn)室，唐山，063210）

引 言

作為一種強(qiáng)大的數(shù)據(jù)分析工具，聚類在數(shù)據(jù)挖掘中起著重要作用，廣泛應(yīng)用于異常數(shù)據(jù)檢測(cè)[1-2]、生物信息學(xué)[3]和網(wǎng)絡(luò)結(jié)構(gòu)分析[4]等領(lǐng)域。聚類的目的是將相似的樣本分組到同一簇中，將不同的樣本分組到不同的簇中，從而可以從數(shù)據(jù)集中找到潛在的相似模式。

目前現(xiàn)有的大多數(shù)聚類方法是假設(shè)每個(gè)樣本必須精確地分配給一個(gè)類簇，即一個(gè)樣本只屬于一個(gè)類簇。然而在實(shí)際應(yīng)用中，一個(gè)樣本可以同時(shí)分配給兩個(gè)或多個(gè)類簇，其在信息不完整或不準(zhǔn)確的情況下，很難給出清晰的劃分結(jié)果。三支決策[5-6]理論認(rèn)為，人們通常根據(jù)現(xiàn)有的信息和證據(jù)作決策，然而，如果信息不足或薄弱，則無法做出接受或拒絕的決策，因此，人們可以選擇延遲決策來解決這一問題，待獲取更多信息后，再給予進(jìn)一步的決策。于洪[7]將其應(yīng)用于聚類，并提出了三支聚類的概念，認(rèn)為一個(gè)聚類不再由單一的具有清晰邊界的集合表示，而是通過一對(duì)集合來表示類簇。隨后學(xué)者們又對(duì)三支聚類的概念進(jìn)行了進(jìn)一步的研究。Wang 等[8]采用重疊聚類來獲得聚類的支持，再利用擾動(dòng)分析將核心區(qū)域從聚類的支持中分離開來，形成對(duì)聚類的三支解釋。隨后，Wang 等[9]又基于數(shù)學(xué)形態(tài)學(xué)的腐蝕和膨脹，提出了三支聚類（CE3）的總體框架。Yu 等[10]提出了一種基于改進(jìn)的DBSCAN（Density-based spatial clustering of application with noise）的三支聚類，對(duì)樣本間相似性計(jì)算進(jìn)行了改進(jìn)，并用一對(duì)嵌套集來表示一個(gè)類簇。以上聚類算法，雖然考慮了樣本間的不確定關(guān)系，但主要是針對(duì)完備數(shù)據(jù)集，其對(duì)不完備數(shù)據(jù)集可能并不完全適用。

當(dāng)聚類算法應(yīng)用于實(shí)際數(shù)據(jù)集，會(huì)出現(xiàn)一個(gè)不可避免的問題，就是樣本中部分屬性值缺失，然而傳統(tǒng)的聚類算法不能直接用于不完備的數(shù)據(jù)集，其只能應(yīng)用于完備的數(shù)據(jù)集。為了解決不完備數(shù)據(jù)聚類問題，國內(nèi)外學(xué)者基于模糊C 均值算法（Fuzzy C-means, FCM）算法提出了一系列改進(jìn)方法。Aydilek等[11]提出了一種支持向量機(jī)和遺傳算法的混合方法來估計(jì)FCM 算法中的缺失值并對(duì)參數(shù)進(jìn)行優(yōu)化；Li等[12]為區(qū)間數(shù)據(jù)定義了新的距離函數(shù)，并擴(kuò)展經(jīng)典FCM 以處理缺失數(shù)據(jù)；Zhang 等[13]利用預(yù)先分類的聚類結(jié)果設(shè)計(jì)了一種改進(jìn)的區(qū)間構(gòu)造方法，并通過粒子群優(yōu)化尋找最優(yōu)聚類。

目前，對(duì)于不完備數(shù)據(jù)聚類的研究，大多數(shù)方法采取了對(duì)缺失值進(jìn)行填充，然而，缺失值本身就具有不確定性，刪除或者填充都會(huì)造成一定的誤差，進(jìn)而影響聚類效果。為了有效解決不完備數(shù)據(jù)聚類問題以及更好地表示樣本與類簇的關(guān)系，本文提出了一種面向不完備信息系統(tǒng)的集對(duì)k-means（Set pair k-means, SPKM）聚類算法。SPKM 算法的主要貢獻(xiàn)體現(xiàn)在以下幾方面：（1）對(duì)于缺失值的處理給出了相應(yīng)方法，運(yùn)用集對(duì)信息粒的?；磉_(dá)方法，將缺失值對(duì)應(yīng)的粒度記為差異度，使得原本聚類過程中不同樣本之間距離擴(kuò)展成包含正同度、差異度和負(fù)反度3 個(gè)維度的距離定義，可全面地反映聚類效果的正同度、差異度和負(fù)反度，比從單一角度衡量更具有系統(tǒng)性。由此根據(jù)提出的集對(duì)距離度量，獲得距離各個(gè)樣本最近的聚類中心，進(jìn)而得到初步聚類結(jié)果；（2）針對(duì)一個(gè)樣本可能不止和一個(gè)類有關(guān)系的情況，也給出了相應(yīng)的聚類方法。對(duì)于同時(shí)屬于多個(gè)類的樣本，將其分配到相應(yīng)類的邊界域；對(duì)于只屬于一個(gè)類的樣本，根據(jù)建立的集對(duì)聯(lián)系度公式，將其劃分到相應(yīng)類的正同域或邊界域，進(jìn)而形成由正同域，邊界域和負(fù)反域表示的集對(duì)聚類結(jié)果；（3）通過6 個(gè)UCI 數(shù)據(jù)集與其他4 種有代表性的算法進(jìn)行了實(shí)驗(yàn)對(duì)比分析，結(jié)果表明，該算法可以有效處理具有缺失值的不完備數(shù)據(jù)集，并且得到較好的聚類效果。

1 基本理論

1.1 不完備信息系統(tǒng)

信息系統(tǒng)又稱為知識(shí)表達(dá)系統(tǒng)，是一個(gè)四元組S=(U,A,V,f)，其中U={x1,x2,…,xi,…,xn}是非空有限樣本集，稱為論域，n為論域中數(shù)據(jù)樣本的個(gè)數(shù)；A={a1,a2,…,am}是非空有限屬性集，m為屬性值的個(gè)數(shù)；V={V1,V2,…,Vm}是U關(guān)于A的屬性的值域集合，Vs是屬性as(1≤s≤m)的值域；f是信息函數(shù)，f：vis=f(xi,as)∈Vs，表示樣本xi在屬性as上的取值為vis。

xi是論域中的第i個(gè)樣本，其具有A=|m|個(gè)屬性值，當(dāng)存在缺失屬性值時(shí)，信息系統(tǒng)S是不完備的，本文的研究對(duì)象是具有缺失值的不完備信息系統(tǒng)。

1.2 集對(duì)分析

集對(duì)分析是以同、異、反來描述事物的一種理論，通過建立兩個(gè)事物之間的集對(duì)聯(lián)系度以期來描述確定-不確定性，集對(duì)聯(lián)系度表達(dá)式為

式中：S代表屬性值相同的數(shù)目，P代表屬性值相反的數(shù)目，F(xiàn)代表屬性值既不相同又不對(duì)立的數(shù)目，N表示屬性值的總個(gè)數(shù)。

式中：a表示正同度，b表示差異度，c表示負(fù)反度。其中i∈[-1,1]和j=-1 分別稱為差異度和負(fù)反度標(biāo)記符號(hào)。

定義1[14]（確定粒集、不確定粒集、確定度和不確定度）設(shè)W=(U,A,V)，W0=(U0,A0,V0)，A0?A，V0?V，R?A0，定義W上一對(duì)子集，確定粒集和不確定粒集（差異粒集），則對(duì)于信息x∈W0，存在一對(duì)映射

式中：aR+bR和cR分別稱為x關(guān)于XC，XU的確定度和不確定度為確定信息粒；為不確定信息粒（差異信息粒）。

定義2[14]（正同粒集、負(fù)反粒集、正同度和負(fù)反度）基于確定信息粒XC，R?A0，定義XC上一對(duì)子集，正同信息粒集和負(fù)反信息粒集則對(duì)于信息x∈XC，存在一對(duì)映射

式 中 ：aR和cR分 別 稱 為x關(guān) 于XCs，XCo的 正 同 度 和 負(fù) 反 度為 正 同 信 息 粒 ；為負(fù)反信息粒。

圖1 數(shù)據(jù)集示意圖Fig.1 Schematic diagram of dataset

圖2 傳統(tǒng)聚類結(jié)果示意圖Fig.2 Schematic diagram of traditional clustering results

1.3 傳統(tǒng)聚類結(jié)果表示

針對(duì)圖1 給出的數(shù)據(jù)集，由傳統(tǒng)聚類算法得到的結(jié)果如圖2所示。圖2 中每個(gè)樣本點(diǎn)被明確地劃分到一個(gè)類簇，實(shí)際上位于中間部分的樣本點(diǎn)x1,x2,x3存在不確定信息，不論是將其劃分到哪一類，都不能很好地體現(xiàn)聚類結(jié)構(gòu)，導(dǎo)致得到的聚類結(jié)果存在誤差。

2 基于集對(duì)的k-means 的聚類算法

2.1 集對(duì)距離度量

衡量樣本點(diǎn)之間的距離是聚類過程中非常關(guān)鍵的一步，然而由于缺失值的存在，一些傳統(tǒng)的距離計(jì)算方法不能直接用于計(jì)算不完備數(shù)據(jù)之間的距離。為此，本文基于集對(duì)分析的相關(guān)理論，提出了集對(duì)距離度量方法，將原本聚類過程中不同樣本之間的距離擴(kuò)展成包含正同度、差異度和負(fù)反度3 個(gè)維度的距離定義，能有效地處理含有缺失值的不完備數(shù)據(jù)集。

定義3（集對(duì)聯(lián)系度）假定樣本集為U={x1,x2,…,xn}，任意兩個(gè)樣本xp,xq∈U，每個(gè)樣本xp={vp1,vp2,…,vpm}由m個(gè)屬性描述，設(shè)定閾值為ε1,ε2(ε2＞ε1)，通過標(biāo)準(zhǔn)化后的數(shù)據(jù)，將樣本xp和樣本xq建立集對(duì)聯(lián)系度，令滿足|vps-vqs| ≤ε1(1≤s≤m)的記為正同信息粒S；滿足|vps-vqs|≥ε2的記為負(fù)反信息粒P；由于缺失屬性值本身就具有不確定性，刪除或者填充都會(huì)造成一定的誤差，然而差異信息?？梢员硎灸：?、不確定的信息，故將滿足ε1＜|vps-vqs| ＜ε2以及缺失的屬性值均記為差異信息粒F，則樣本xp和xq之間建立的集對(duì)聯(lián)系度為

式中：N代表屬性值的總數(shù)目；S代表屬性值數(shù)據(jù)差的絕對(duì)值小于等于ε1的數(shù)目；P代表屬性值數(shù)據(jù)差的絕對(duì)值大于等于ε2的數(shù)目；F代表其他屬性值數(shù)目，其包括缺失的屬性值。

式（7）也可以簡(jiǎn)化為

定義4（集對(duì)聯(lián)系度矩陣）設(shè)待聚類樣本集為U，A為屬性集，在關(guān)系R下，任取U中的樣本xp和xq(p≠q;p,q=1,2,…,n)，令xp與xq建立集對(duì)聯(lián)系度，從而獲得集對(duì)聯(lián)系度矩陣T為

式中：apq，bpq和cpq(1≤p≤n,1≤q≤n)滿足apq+bpq+cpq=1，其中apq為正同度，bpq為差異度，cpq為負(fù)反度。

定義5（集對(duì)距離度量）任意兩個(gè)樣本xp,xq(1≤p,q≤n)之間的集對(duì)聯(lián)系度ρpq=a+bi+cj可以通過式（8）得到。根據(jù)集對(duì)聯(lián)系度定義了一種集對(duì)距離度量方法，可通過正同度a和負(fù)反度c的大小來確定與每個(gè)樣本xp距離最近的樣本，即

對(duì)任意樣本xp，根據(jù)式（10）得到與之建立的集對(duì)聯(lián)系度中正同度最大的樣本，如果滿足條件的只有一個(gè)樣本，則將其確定為距離樣本xp最近的樣本，如果滿足條件的不止一個(gè)樣本，則根據(jù)條件更為嚴(yán)格的式（11），選取與之建立的集對(duì)聯(lián)系度同時(shí)滿足正同度最大、負(fù)反度最小的樣本，將其確定為距離樣本xp最近的樣本。需要注意的是，對(duì)于每個(gè)樣本xp，找到距離其最近的樣本，可能為一個(gè)，也可能為多個(gè)。

2.2 集對(duì)k-means 聚類結(jié)果表示

本文將集對(duì)信息粒的相關(guān)理論引入k-means 聚類中，基于集對(duì)信息粒中的正同粒集，差異粒集和負(fù)反粒集的定義，提出用正同域Cs，邊界域Cu和負(fù)反域Co三個(gè)域來表示聚類結(jié)果。其中，正同域表示屬于這個(gè)類，邊界域表示可能屬于這個(gè)類，負(fù)反域表示不屬于這個(gè)類。聚類結(jié)果如圖3 所示，設(shè)定了一個(gè)邊界線用于更好地顯示正同域和邊界域。

聚類的目的是將相似程度高的樣本劃分到正同域，使其位于類的中心，將相似程度較低的樣本劃分到邊界域，用這兩個(gè)域可以更好地表示一個(gè)類。這3 個(gè)域滿足如下性質(zhì)

（1）Cs(Ci)≠?

（2）(Cs(Ci)∪Cu(Ci))=U

（3）Cs(Ci)∩Cs(Cj)=?,i≠j

式中：Cs(Ci)表示類簇Ci的正同域，Cu(Ci)表示類簇Ci的邊界域。性質(zhì)（1）說明，每個(gè)類的正同域不能為空；性質(zhì)（2）說明U中的任何一個(gè)樣本必須屬于一個(gè)正同域或者至少屬于一個(gè)邊界域；性質(zhì)（3）說明任何一個(gè)樣本最多只能屬于一個(gè)類的正同域。

圖3 聚類的可視化Fig.3 Visualization of clustering

2.3 算法描述與分析

集對(duì)k-means 聚類算法可以用于處理存在缺失值的不完備數(shù)據(jù)集。缺失值處理的主要思想是將樣本的缺失屬性值在進(jìn)行集對(duì)分析時(shí)，將其粒度記為相應(yīng)的差異度。另外，其是用正同域、邊界域共同來表示一個(gè)聚類，而不是一個(gè)單一的集合。然而傳統(tǒng)k-means 聚類算法是用具有清晰邊界的集合來表示一個(gè)聚類，其思想是先初始化k個(gè)聚類中心，作為k個(gè)初始類簇，然后將每個(gè)樣本依次分配到各個(gè)類簇。但在聚類過程中只考慮了兩種關(guān)系，會(huì)降低對(duì)不確定點(diǎn)劃分的準(zhǔn)確性，而樣本與類簇之間存在屬于、可能屬于、不屬于這3 種關(guān)系。針對(duì)這3 種關(guān)系的劃分，本文實(shí)驗(yàn)中的聚類任務(wù)分為兩階段，第1 階段構(gòu)造包含正同域和邊界域的集合，第2 階段使正同域和邊界域分離。

第 1 階段：假定樣本集為U={x1,x2,…,xn}，選取的k個(gè)初始聚類中心為{μ1,μ2,…,μk}。將樣本集數(shù)據(jù)先進(jìn)行標(biāo)準(zhǔn)化處理，再通過式（8）依次將樣本xp(1≤p≤n)與各聚類中心μj(1≤j≤k)建立集對(duì)聯(lián)系度。根據(jù)集對(duì)距離式（10)和(11）得到距離每個(gè)樣本最近的聚類中心，將樣本xp分配到與之距離最近的類簇Cλq=Cλq∪{xp}，由此確定每個(gè)樣本的簇標(biāo)記λq。在迭代過程中，新聚類中心的計(jì)算公式為

式中：x∈Cj，x={v?1,v?2,…,v?m}，j=1,2,…,k，|Cj|表示類簇Cj的元素個(gè)數(shù)。

上述過程得到了聚類的初步結(jié)果，將類中樣本分為兩種類型，即

第2 階段：對(duì)初步聚類結(jié)果進(jìn)行細(xì)分，使得正同域和邊界域進(jìn)行分離。第1 種類型的樣本{xi∈Ci|?j=1,2,…,k,j≠i,xi∈Cj}，顯然，其與多個(gè)類簇存在關(guān)系，則將其同時(shí)分配到類簇Ci的邊界域Cu(Ci)和類簇Cj的邊界域Cu(Cj)。對(duì)于第 2 種類型的樣本其只屬于一個(gè)類簇Ci中，不再屬于其他任何類簇Cj(j≠i)，只需判斷其位于正同域還是邊界域。計(jì)算方法如下：設(shè)定正同度閾值為α，負(fù)反度閾值為β，計(jì)算該樣本與所在類的聚類中心的集對(duì)聯(lián)系度，比較其正同度、負(fù)反度與閾值之間的大小關(guān)系，將類中樣本依次分配到相應(yīng)類簇的正同域Cs或邊界域Cu，公式為

基于以上討論，集對(duì)k-means 聚類的結(jié)果可表示為

式中：Cj={Cs(Cj)∪Cu(Cj)}(1≤j≤k)表示一個(gè)類簇的聚類結(jié)果。對(duì)于圖1 中的樣本點(diǎn)，本文所提SPKM 算法得到的聚類結(jié)果如圖4 所示。

圖4 集對(duì)k-means 聚類示意圖Fig.4 Schematic diagram of set pair k-means clustering

2.4 算法流程

算法步驟如下：

輸入：樣本集U={x1,x2,…,xn}，類簇?cái)?shù)目k，參數(shù)ε1,ε2,α,β

輸出：聚類結(jié)果C={{Cs(C1)∪Cu(C1)},{Cs(C2)∪Cu(C2)},…,{Cs(Ck)∪Cu(Ck)}}

（1）隨機(jī)選取k個(gè)樣本作為初始聚類中心{μ1,μ2,…,μk}

（2）Repeat

（3）令Cj=? (j=1,2,…,k)

（4）Forp=1,2,…,ndo

（5） 對(duì)于每個(gè)樣本xp(1≤p≤n)，根據(jù)式（10）和（11）計(jì)算得到與之距離最近的聚類中心μj

（6） 令λj為簇標(biāo)記如果滿足 max {apj}的樣本不唯一，則增加條件min {cpj}，選擇

（7） 將樣本xp分配到類簇Cλj=Cλj∪{xp}中

（9）End for

（10）直到|μ′j-μj| ＜δ或者達(dá)到最大迭代次數(shù)

（11）Forj=1,2,…,kdo

（12） 對(duì)于類簇Cj中的每個(gè)樣本x，依次計(jì)算H={x：x∈Cj,?i,i≠j,x∈Ci}；

（13） IfH≠? then

（14） 將樣本x同時(shí)分配到類簇Ci和類簇Cj的邊界域Cu

（15） Else

（16） 根據(jù)公式Cs={a≥αorc＜β}，Cu={0 ＜a＜αandc≥β}，將樣本分配到類簇Cj的正同域Cs(Cj)或者邊界域Cu(Cj)

（17） End if

（18）End for

（19）輸出C={{Cs(C1)∪Cu(C1)},{Cs(C2)∪Cu(C2)},…,{Cs(Ck)∪Cu(Ck)}}

上述算法主要分為兩個(gè)階段：第1 階段（步驟(1)～(10)）是構(gòu)造包含正同域和邊界域的集合。在步驟(5)～(7)中，是對(duì)存在缺失值的樣本，根據(jù)本文提出的集對(duì)距離度量方法，計(jì)算得到距離每個(gè)樣本最近的聚類中心，由此將每個(gè)樣本分配到距離最近的類簇中。為了減少初始聚類中心對(duì)聚類結(jié)果的影響，在每次分配一個(gè)樣本后，根據(jù)步驟（8）對(duì)聚類中心進(jìn)行更新，進(jìn)而將所有樣本分配到k個(gè)類簇中，得到初步聚類結(jié)果。第2 階段（步驟（11）～（18）)是將正同域和邊界域分離，在步驟(12)中判斷每個(gè)樣本是否只存在一個(gè)類中，將樣本分為只屬于一個(gè)類和屬于多個(gè)類兩種情況，分別對(duì)其采取不同劃分方法。步驟（13）～（14）處理的是屬于多個(gè)類的樣本，將其同時(shí)分配到這些類簇的邊界域，步驟(16)處理的是只屬于一個(gè)類的樣本，根據(jù)式（13）進(jìn)行計(jì)算，進(jìn)而將其分配到類簇的正同域或者邊界域，由此得到兩個(gè)域共同表示的集對(duì)k-means 聚類結(jié)果。算法流程圖如圖5 所示。

2.5 算法復(fù)雜度分析

針對(duì)時(shí)間復(fù)雜度，設(shè)論域中的樣本數(shù)目為n，聚類數(shù)目為k，屬性數(shù)目為m。SPKM 算法的時(shí)間復(fù)雜度主要由預(yù)處理過程中的數(shù)據(jù)標(biāo)準(zhǔn)化、步驟（5）中依次對(duì)每個(gè)樣本計(jì)算距離和步驟（12）～（16）中將樣本劃分到相應(yīng)類簇的正同域或邊界域產(chǎn)生。數(shù)據(jù)標(biāo)準(zhǔn)化過程中，需要對(duì)每個(gè)樣本都進(jìn)行處理，每個(gè)樣本有m個(gè)屬性，故產(chǎn)生的時(shí)間復(fù)雜度為O(mn)；每次迭代計(jì)算各個(gè)樣本與聚類中心的距離產(chǎn)生的時(shí)間復(fù)雜度為knm，設(shè)迭代次數(shù)為I，則這部分的時(shí)間復(fù)雜度為O(knmI)；對(duì)于每個(gè)樣本劃分到相應(yīng)類簇的正同域或邊界域，須對(duì)類中每個(gè)元素xp(p=1,2,…,n)與所在類簇Cj(j=1,2,…,k)的聚類中心依次進(jìn)行計(jì)算，這部分產(chǎn)生的時(shí)間復(fù)雜度為O(knm)。所以，SPKM 算法的時(shí)間復(fù)雜度為O(n)=O(mn)+O(knmI)+O(knm)。本文算法在沒有增加時(shí)間復(fù)雜度的前提下，解決了存在缺失值的數(shù)據(jù)空白問題，提高了聚類效果。

圖5 集對(duì)k-means 聚類算法流程圖Fig.5 Flow chart of set pair k-means clustering algorithm

針對(duì)空間復(fù)雜度，SPKM 算法處理的樣本數(shù)目是n，初始聚類中心的數(shù)目是k個(gè)，樣本的屬性值的維數(shù)是m，故SPKM 算法的空間復(fù)雜度為O((k+n)m)。

3 模型驗(yàn)證

為了評(píng)估所提出的SPKM 算法的性能，進(jìn)行了一系列實(shí)驗(yàn)，主要分為兩方面：一是對(duì)算法參數(shù)進(jìn)行分析，二是選取了4 種具有代表性的算法進(jìn)行對(duì)比分析。本文所提算法和對(duì)比算法是在一臺(tái)DELL（Windows 10，Intel（R）Core（TM）i5-8300H，CPU@ 2.30 GHz 2.30 GHz）計(jì)算機(jī)上使用Python3.7 環(huán)境實(shí)現(xiàn)的。

3.1 數(shù)據(jù)集選取與評(píng)價(jià)

聚類的評(píng)價(jià)，又被稱為聚類有效性，是評(píng)估學(xué)習(xí)方法在聚類方面表現(xiàn)的關(guān)鍵過程，度量方法將影響到幾種聚類方法的性能比較。為了驗(yàn)證本文算法的性能，選取了UCI 中的6 個(gè)數(shù)據(jù)集Iris，Wine，Seeds，Liver disorders，Wave form 以及Page blocks，表1 給出了這些數(shù)據(jù)集的大小、屬性個(gè)數(shù)和類簇個(gè)數(shù)。

對(duì)于數(shù)據(jù)集：U={x1,x2,…,xn}，假定通過聚類得到的聚類結(jié)果為C={C1,C2,…,Ck}，數(shù)據(jù)集的真實(shí)聚類結(jié)果為令λ和λ?分別表示C和C?對(duì)應(yīng)的簇標(biāo)記，將樣本兩兩配對(duì)考慮，定義

表1 實(shí)驗(yàn)數(shù)據(jù)集的描述Table 1 Description of lab datasets

本文選取幾種常見的聚類性能度量指標(biāo)。

（1）MacroF（1宏平均）

作為一個(gè)多標(biāo)簽任務(wù)的衡量指標(biāo)，MacroF1可表達(dá)為

式中

式中：TPCi表示Ci中樣本被正確聚為該類的數(shù)量；FPCi表示非Ci中樣本被錯(cuò)誤聚為該類的數(shù)量；FNCi表示Ci中樣本被錯(cuò)誤聚為其他類的數(shù)量。MacroF1性能度量的結(jié)果在區(qū)間[0,1]。

（2）Accuracy（準(zhǔn)確率）

式中：φk為簇Ck中正確劃分的樣本數(shù)目，n為樣本的總數(shù)。準(zhǔn)確率越高，聚類結(jié)果越好。

（3）JC（Jaccard 系數(shù)）

（4）FMI（FM 指數(shù)）

（5）ARI（蘭德指數(shù)）

式中：|Ci|為類簇Ci的樣本數(shù)目；||為真實(shí)類簇的樣本數(shù)目表示類簇Ci和真實(shí)類簇共同擁有的樣本數(shù)目。

3.2 SPKM 算法參數(shù)分析

以Iris 數(shù)據(jù)集為例，對(duì)算法在不同參數(shù)下的性能進(jìn)行了詳細(xì)分析。由于數(shù)據(jù)集是經(jīng)典完備數(shù)據(jù)集，需要對(duì)其進(jìn)行處理，隨機(jī)生成帶有缺失值的不完備數(shù)據(jù)集，本文選取的缺失率為5%，10%，15%和20%，通過使用評(píng)價(jià)指標(biāo)JC，F(xiàn)MI 和ARI 對(duì)該聚類算法的性能進(jìn)行評(píng)價(jià)。圖6 給出了3 個(gè)評(píng)價(jià)指標(biāo)平均值隨著4 個(gè)參數(shù)變化的波動(dòng)情況。表2 給出了Iris 數(shù)據(jù)集在最優(yōu)參數(shù)下的聚類結(jié)果。由于本文提出SP-KM 算法是以正同域和邊界域來表示聚類結(jié)果，所以在每個(gè)指標(biāo)下都分別給出了單獨(dú)的正同域Cs以及正同域和邊界域Cs∪Cu這兩個(gè)評(píng)價(jià)結(jié)果。

圖6 數(shù)據(jù)集Iris 的參數(shù)變化結(jié)果Fig.6 Result of parameter changes in Iris dataset

首先討論的是參數(shù)ε1，ε2，以運(yùn)行100 次的均值作為一次實(shí)驗(yàn)值，進(jìn)行大量實(shí)驗(yàn)，圖6（a2）是相對(duì)圖6（a1）的一個(gè)局部圖，是通過縮小步長(zhǎng)進(jìn)行的更為精細(xì)的處理，得到最佳參數(shù)為ε1=0.16,ε2=0.79，其對(duì)應(yīng)的100 次均值的最大實(shí)驗(yàn)值達(dá)到0.87（正同和邊界域），最優(yōu)值在圖中已用紅色三角進(jìn)行區(qū)分。然后保持ε1=0.16,ε2=0.79 不變，討論參數(shù)α和β。用同樣的方法得到的最佳參數(shù)為α=0.6,β=0.09，其對(duì)應(yīng)的100 次均值的最大實(shí)驗(yàn)值達(dá)到0.922（正同域），0.923（正同和邊界域）。從圖6 可知數(shù)據(jù)集Iris 的最優(yōu)參數(shù)為ε1=0.16,ε2=0.79,α=0.6,β=0.09。對(duì)于其他5 個(gè)數(shù)據(jù)集也通過實(shí)驗(yàn)方式得出了最優(yōu)參數(shù)，具體結(jié)果如表3 所示。

表2 Iris 數(shù)據(jù)集在最優(yōu)參數(shù)下的性能分析Table 2 Performance analysis of Iris dataset under optimal parameters

表2 給出的是數(shù)據(jù)集Iris 在最優(yōu)參數(shù)下的聚類結(jié)果，可以看出在指標(biāo)JC，F(xiàn)MI 和ARI 下均得到了較好的聚類效果。其中，針對(duì)正同域和邊界域Cs∪Cu，在缺失率為5%的情況下得到的JC 指數(shù)為0.993，F(xiàn)MI 為 0.987，ARI 為 0.980；在缺失率為 10% 的情況下達(dá)到了 JC 為 0.973，F(xiàn)MI 為 0.947，ARI 為0.921。同時(shí)，從表中也可以看到，針對(duì)正同域Cs，得到的評(píng)價(jià)指標(biāo)的值均低于在Cs∪Cu下的。這是因?yàn)檫@兩個(gè)集合是通過對(duì)二支聚類的收縮或擴(kuò)展得到的，所以Cs∪Cu的性能優(yōu)于Cs是合理的。通過這3個(gè)指標(biāo)的實(shí)驗(yàn)結(jié)果可以分析出，隨著缺失率的增加，聚類質(zhì)量下降，究其原因是缺失率越大，不確定信息越多，其對(duì)樣本劃分產(chǎn)生的影響越大。

在最優(yōu)參數(shù)下，對(duì)Iris 數(shù)據(jù)集的集對(duì)k-means 聚類結(jié)果進(jìn)行了可視化，結(jié)果如圖7 所示。從圖7 可知，數(shù)據(jù)集被聚成了3個(gè)類簇，每個(gè)類簇通過正同域和邊界域兩個(gè)域共同表示。從圖7 可以看出，同時(shí)屬于多個(gè)類簇的樣本位于多個(gè)類簇的交界處，將其分配到邊界域是合理的；對(duì)于只屬于一個(gè)類，但其位于類簇的邊緣區(qū)域的樣本，將其分配到邊界域也是合理的。

3.3 SPKM 算法的實(shí)驗(yàn)對(duì)比分析

為了識(shí)別SPKM 算法的聚類質(zhì)量，通過評(píng)價(jià)指標(biāo)Accuracy，MacroF1，JC，F(xiàn)MI 和 ARI 與選取的 4 種算法進(jìn)行了對(duì)比分析。第1 種是Wang 等基于數(shù)學(xué)形態(tài)學(xué)的腐蝕和膨脹提出的三支聚類框架（CE3-k-means）[9]；第 2 種是 Yu 等基于改進(jìn)的 DBSCAN 提出的三支聚類算法（3W-DBSCAN）[10]；第3 種是Zhang 基于三支權(quán)重和三支分配，提出的一種三支c-means 聚類算法[15]，依照原文將其記為TCM；第4 種是Yang 等基于密度峰值提出的不完備三支聚類算法，依照原文將其記為Adopted methods[16]。

表3 6 個(gè)數(shù)據(jù)集的最優(yōu)參數(shù)Table 3 Optimal parameters for six datasets

圖7 Iris 數(shù)據(jù)集最優(yōu)參數(shù)下聚類結(jié)果Fig.7 Clustering result under optimal parameters of Iris dataset

將對(duì)所有正同域和邊界域形成的聚類結(jié)果進(jìn)行實(shí)驗(yàn)評(píng)價(jià)。由于本文的研究對(duì)象是不完備數(shù)據(jù)集，故將選取的6 個(gè)數(shù)據(jù)集按照5%，10%，15%，20%的比例作隨機(jī)缺失處理。本文所提算法和4 種對(duì)比算法在5 個(gè)評(píng)價(jià)指標(biāo)下的聚類結(jié)果如表4—8 所示。在不同算法之間的最優(yōu)結(jié)果用粗體進(jìn)行標(biāo)記。

表4 5 種算法在指標(biāo)Accuracy 下的對(duì)比結(jié)果Table 4 Comparison results of five algorithms under index Accuracy

表5 5 種算法在指標(biāo)Macro F1下的對(duì)比結(jié)果Table 5 Comparison results of five algorithms under index Macro F1

續(xù)表

表6 5 種算法在指標(biāo)JC 下的對(duì)比結(jié)果Table 6 Comparison results of five algorithms under index JC

續(xù)表

表7 5 種算法在指標(biāo)FMI 下的對(duì)比結(jié)果Table 7 Comparison results of five algorithms under index FMI

表8 5 種算法在指標(biāo)ARI 下的對(duì)比結(jié)果Table 8 Comparison results of five algorithms under index ARI

續(xù)表

從表4 中的實(shí)驗(yàn)結(jié)果可知，SPKM 算法在評(píng)價(jià)指標(biāo)Accuracy 上得到的聚類結(jié)果要優(yōu)于對(duì)比算法，特別是在數(shù)據(jù)集Iris，Liver disorders 和Wave form，該算法的準(zhǔn)確率均高于對(duì)比算法。對(duì)于數(shù)據(jù)集Wine 和Seeds，本文算法在4 個(gè)缺失率下，都能達(dá)到在3 個(gè)缺失率下優(yōu)于對(duì)比算法，其中Wine 在缺失率為20%時(shí)，比最優(yōu)算法低了0.045，Seeds 在缺失率為15%時(shí)，能做到優(yōu)于3 個(gè)對(duì)比算法。針對(duì)數(shù)據(jù)集Page blocks，在缺失率為5%和20%時(shí)，準(zhǔn)確率仍高于所有對(duì)比算法，但在缺失率為10%，15%時(shí)，與最優(yōu)對(duì)比算法Adopted methods 相比分別下降了0.019，0.002，但仍比其他3 個(gè)對(duì)比算法的效果要優(yōu)。

從表5 的實(shí)驗(yàn)結(jié)果可以看出，對(duì)于數(shù)據(jù)集Iris，Wine，Liver disorders 和Wave form，用評(píng)價(jià)指標(biāo)MacroF1得到的聚類結(jié)果要明顯高于對(duì)比算法，也體現(xiàn)出了SPKM 算法的優(yōu)越性。對(duì)于其他兩個(gè)數(shù)據(jù)集也得到了不錯(cuò)的聚類結(jié)果，比如數(shù)據(jù)集Seeds，在缺失率為15%的情況下，即使它不是最好的算法，但在缺失率為5%，10%和20%時(shí)，MacroF1值要高于其他4 個(gè)對(duì)比算法。從表6 中的實(shí)驗(yàn)結(jié)果可以看出，對(duì)于數(shù)據(jù)集Iris，Wine 和Wave form，用評(píng)價(jià)指標(biāo)JC 得到的聚類結(jié)果均優(yōu)于對(duì)比算法。從表7 中的實(shí)驗(yàn)結(jié)果可知，在4 個(gè)缺失率下數(shù)據(jù)集Liver disorders 和Wave form 得到的聚類結(jié)果均優(yōu)于對(duì)比算法。從表8 的實(shí)驗(yàn)結(jié)果可知，對(duì)于數(shù)據(jù)集Iris 和Wine，用評(píng)價(jià)指標(biāo)ARI 得到的聚類結(jié)果要明顯高于對(duì)比算法。綜上所述，本文提出的聚類算法可以有效處理含有缺失值的不完備數(shù)據(jù)集，而且具有良好的聚類性能。

4 結(jié)束語

針對(duì)不完備數(shù)據(jù)的聚類問題以及為了更好地表示樣本與類簇的關(guān)系，本文將集對(duì)分析的相關(guān)理論引入到k-means 聚類中，提出了一種面向不完備信息系統(tǒng)的集對(duì)k-means 聚類算法，將聚類結(jié)果劃分為3 部分，用正同域Cs，邊界域Cu，負(fù)反域Co表示。本文提出的集對(duì)k-means 聚類算法，將原本聚類過程中不同樣本之間距離擴(kuò)展成包含正同度、差異度和負(fù)反度3 個(gè)維度的距離定義，有效解決了不完備數(shù)據(jù)集的距離度量問題，并基于這個(gè)定義擴(kuò)展了k-means 聚類算法，很好地表示了樣本與類之間的3 種關(guān)系。同時(shí)，對(duì)于樣本可能和多個(gè)類有關(guān)系的情況，也給出了相應(yīng)的聚類方法，將其劃分到相應(yīng)類的邊界域。實(shí)現(xiàn)了對(duì)聚類結(jié)果結(jié)構(gòu)的改進(jìn)以及聚類準(zhǔn)確率的提高。通過對(duì)6 個(gè)UCI 數(shù)據(jù)集進(jìn)行對(duì)比實(shí)驗(yàn)，結(jié)果表明該算法可以有效解決具有缺失值的不完備數(shù)據(jù)集，并且改善了聚類結(jié)構(gòu)。然而，參數(shù)的變化對(duì)聚類結(jié)果的影響較大，如何獲取更為合適的參數(shù)也是下一步的工作，其將對(duì)提高聚類質(zhì)量有重要影響。