張春英，高瑞艷，范雨祥，王龍飛，裴天帥，馮曉澤，任 靜

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

1 引 言

數(shù)據(jù)聚類[1]是將相似的樣本分配到同一類簇，將不同的樣本分配到不同的類簇.聚類技術(shù)可以發(fā)現(xiàn)潛在的數(shù)據(jù)結(jié)構(gòu)，其發(fā)現(xiàn)的聚類有助于解釋數(shù)據(jù)集的隱藏特征，目前已廣泛應(yīng)用于模式識別、圖像對象提取、和數(shù)據(jù)壓縮等多個領(lǐng)域.現(xiàn)有的聚類算法根據(jù)聚類策略粗略地劃分成劃分聚類[2]、密度聚類[3]、層次聚類[4,5]幾種類型，本文將著重對層次聚類算法進(jìn)行研究與討論.

聚類是一種重要的數(shù)據(jù)分析方法，在數(shù)據(jù)集中往往會出現(xiàn)不完整的數(shù)據(jù)，不適當(dāng)?shù)靥幚聿煌暾臄?shù)據(jù)會顯著降低聚類性能.目前關(guān)于不完備數(shù)據(jù)的聚類研究，已提出了一些有意義的成果.Aydilek[6]等提出了一種支持向量機(jī)和遺傳算法的混合方法來估計FCM算法中的缺失值并對參數(shù)進(jìn)行優(yōu)化.Zhang[7]等利用預(yù)先分類的聚類結(jié)果設(shè)計了一種改進(jìn)的區(qū)間構(gòu)造方法，并通過粒子群優(yōu)化尋找最優(yōu)聚類.Lu[8]等采用改進(jìn)的親和傳播(AP)算法，在不完備數(shù)據(jù)被填充后進(jìn)行聚類分析，得到了較好的聚類結(jié)果.在不完備數(shù)據(jù)聚類中，針對缺失值的處理，主要分為兩種方式:1)將含有缺失值的樣本進(jìn)行刪除，雖然計算簡單，但是若存在大量缺失樣本，則會導(dǎo)致部分有效信息的丟失；2)利用樣本之間的相似性和樣本本身特征，來有效的恢復(fù)和填充缺失的屬性值，例如可以采用區(qū)間值的形式來估計缺失屬性值[9]，或者根據(jù)其最近鄰的均值來估計缺失屬性值[10].

另外，在大多數(shù)聚類算法中，對于每個類簇通過單一的集合表示，如果樣本在類簇中，則屬于這個類簇，否則不屬于這個類簇.實(shí)際上，樣本與類簇之間存在3種關(guān)系：一定屬于、可能屬于和不屬于.姚[11,12]提出了一種作為復(fù)雜問題解決的新的研究領(lǐng)域-三支決策，通過添加延遲決策來擴(kuò)展常用的二支決策模型，對信息充足的對象進(jìn)行決策，等待新的信息來對信息不充分的對象做出進(jìn)一步的決策.在三支決策的啟發(fā)下，Yu[13]將其應(yīng)用于聚類，提出了三支聚類的概念，很好地解釋樣本與類簇之間的三種關(guān)系.最近，Wang等[14]針對數(shù)學(xué)形態(tài)學(xué)的腐蝕和膨脹，提出了三支聚類(CE3)的總體框架.Zhang[15]根據(jù)三支權(quán)重和三支分配，將粗糙k-means(RKM)進(jìn)行擴(kuò)展，提出了一種三支c-means聚類算法.Yu[16]等提出了一種基于改進(jìn)的DBSCAN的三支聚類，對樣本間相似性計算進(jìn)行了改進(jìn)，并用一對嵌套集來表示一個類簇.RKM算法其時間復(fù)雜度較低但聚類效果依賴于聚類中心的初始化；DBSCAN算法雖然可以對異常點(diǎn)進(jìn)行處理，但其對于密度不均勻的類簇，得到的聚類效果不佳；并且以上聚類算法，雖然考慮了樣本間的不確定關(guān)系，但主要針對完備數(shù)據(jù)集，對于不完備數(shù)據(jù)集并不適用.

CURE[4]算法通過代表點(diǎn)的收縮可以有效的控制異常點(diǎn)的影響，而且能夠識別非球形和尺寸變化的類簇，對于數(shù)據(jù)輸入順序也不敏感，其是一種處理完備數(shù)據(jù)集的有效方法，但對于存在缺失值的數(shù)據(jù)，不能做到對所有數(shù)據(jù)綜合考慮.缺失的數(shù)據(jù)值自身具有不確定性，對于不確定性問題的處理，集對論[17，18]展現(xiàn)了良好的優(yōu)勢，其從確定-不確定系統(tǒng)角度出發(fā)，通過關(guān)聯(lián)度對事物進(jìn)行統(tǒng)一刻畫，可以很好地對不確定信息進(jìn)行表示.Zhang等[19]基于集對論提出了集成正同、負(fù)反和差異三維粒度的集對信息粒，并用集對信息粒的方法，對三支決策的思想進(jìn)行了闡述，提出了基于集對信息?？臻g的三支決策模型.本文將集對信息粒的思想引入到CURE算法中，提出了一種面向不完備數(shù)據(jù)的集對粒層次聚類算法-SPGCURE，通過UCI數(shù)據(jù)庫中的數(shù)據(jù)集，將算法SPGCURE涉及的參數(shù)通過實(shí)驗(yàn)進(jìn)行了討論，并與其他7種算法進(jìn)行實(shí)驗(yàn)對比分析，結(jié)果表明該算法具有不錯的聚類性能.所提SPGCURE算法創(chuàng)新之處體現(xiàn)在以下幾方面：1) 缺失屬性本身具有不確定性，將缺失屬性刪除或者填充，都不能很好表達(dá)數(shù)據(jù)中的原有信息，本文采用集對信息粒的知識對缺失值進(jìn)行處理，用集對聯(lián)系度中的差異度來表示缺失屬性值，進(jìn)而可以提高缺失屬性估計的魯棒性.2) 與現(xiàn)有距離度量方法不同，本文根據(jù)集對信息粒的相關(guān)理論提出的是一種集對信息距離度量方法，可以用于處理不完備數(shù)據(jù)集.3) 基于改進(jìn)后的距離度量，給出了各個類簇的類內(nèi)平均距離的定義，形成以正同域Cs(樣本一定屬于類簇)，邊界域Cu(樣本可能屬于類簇)，負(fù)反域Co(樣本不屬于類簇)表示的集對粒層次聚類.

本文結(jié)構(gòu)如下：第2節(jié)對基礎(chǔ)知識進(jìn)行簡要介紹；第3節(jié)給出了所提算法SPGCURE，包括運(yùn)用集對信息粒知識提出的集對信息距離度量、集對粒層次聚類的處理與結(jié)果表示；第4節(jié)，選用5個經(jīng)典數(shù)據(jù)集，與常用的經(jīng)典及改進(jìn)聚類算法進(jìn)行實(shí)驗(yàn)評價，并報告了實(shí)驗(yàn)評價SPGCURE的結(jié)果；第5節(jié)是本文的結(jié)論。

2 基本理論

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

信息系統(tǒng)S是由四元組S=(U，A，V，f)表示，式中U={X1，X2，…，Xi，…，Xn}是有限非空的樣本集合，n為樣本的個數(shù)；A={A1，A2，…，Am}是非空有限的屬性集，其中，m為屬性的個數(shù)；V={V1，V2，…，Vm}是U關(guān)于屬性A的值域集合，Vs是屬性As的值域；f是信息函數(shù)，f：vis=f(Xi，As)∈VS，表示樣本Xi在屬性As上的取值為vis.

Xi是論域中第i個樣本，其具有|m|個屬性值，當(dāng)樣本Xi的某些屬性值vis(1≤s≤m)未知時，信息系統(tǒng)S成為一個不完備信息系統(tǒng).

2.2 集對信息粒

集對分析是一種新的研究確定性與不確定性系統(tǒng)的理論，將兩個事物所具有的特性作同異反分析，得出的同異反聯(lián)系度表達(dá)式為：

ρ=a+bi+cj

式中，a表示正同度，b表示差異度，c表示負(fù)反度，其中，i∈[-1，1]，j=-1分別稱為差異度和負(fù)反度標(biāo)記符號，用以識別分類信息的方向和不確定程度.

τ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. (集對聯(lián)系度矩陣)設(shè)待聚類信息系統(tǒng)為W=(U，A，R)，A為屬性集，在關(guān)系R下，任取W中的樣本Xp和Xq(p≠q;p，q=1，2，…，n)，令Xp與Xq建立集對聯(lián)系度，用矩陣A表示為：

式中apq，bpq，cpq滿足apq+bpq+cpq=1，其中，apq是正同度，bpq是差異度，cpq是負(fù)反度.

2.3 CURE聚類算法

層次聚類算法是從不相交的聚類集合開始，將每個輸入樣本放在一個單獨(dú)的類簇中，然后，對各個類簇進(jìn)行連續(xù)合并，直到類簇的數(shù)量減少到k.在每一步中，合并的對簇都是距離最小的簇，簇間距離的常用度量方式如下：

dmean(Ci，Cj)=‖mi-mj‖

式中，Xi，Xj是類簇中任取的樣本，mi和mj分別是類簇Ci和Cj的中心點(diǎn)，|Ci|是類簇Ci中的樣本個數(shù)，|Cj|是類簇Cj中的樣本個數(shù).

CURE算法的簇間距離度量方式與以往常用度量方法不同，采用多個代表點(diǎn)來表示類簇，代表點(diǎn)是從類簇中選擇的足夠分散的點(diǎn).通過收縮因子，使得分散的點(diǎn)向中心聚攏，可以消除異常點(diǎn)的干擾；針對大型數(shù)據(jù)集，選擇隨機(jī)抽樣和分割的方式，去減少輸入集的樣本數(shù)目；對于異常點(diǎn)的處理，分為兩個階段:1)在層次聚類中刪除增長速度慢的類簇;2)當(dāng)類簇總數(shù)減少到大約為k時，刪除簇中樣本個數(shù)較少的集合.CURE算法中代表點(diǎn)，中心點(diǎn)和距離度量方法的定義如下：

定義4[4].設(shè)樣本集為U={X1，X2，…，Xn}，n為樣本個數(shù)，將擁有最小距離的兩個類簇Ci，Cj進(jìn)行合并，合并后的新類簇記為Cw，Cw的中心點(diǎn)計算方法如下：

(1)

Cw的代表點(diǎn)集為Cw.rep，計算方法如下：

式中，Xp∈U，Xp={Xp1，Xp2，…，XpR}，α是收縮因子，R表示代表點(diǎn)數(shù)目.

定義5[4].將任意兩個類簇Ci，Cj之間的距離定義為：

式中，Ci.rep和Cj.rep分別是類簇Ci和Cj的代表點(diǎn)集，m為樣本屬性數(shù)目，vis和vjs分別為樣本Xi和Xj的第s維的屬性值.

3 算法描述與分析

3.1 集對信息距離度量

聚類分析通過對一組樣本進(jìn)行分組任務(wù)，使得同一組中的樣本比其它組中的樣本更相似.樣本間距離的度量是影響聚類效果的關(guān)鍵之處，然而由于缺失值的存在，一些常用的計算相似度的方法不能直接用于計算不完備數(shù)據(jù)之間的相似度，為此，本文基于集對信息粒理論，提出了基于集對聯(lián)系度的距離公式，將原本聚類過程中不同樣本之間的距離擴(kuò)展成包含正同度、差異度和負(fù)反度3個維度的距離定義，能有效處理含有缺失值的不完備數(shù)據(jù)集.

定義6(集對聯(lián)系度).任意給定兩個樣本Xi和Xj，每個樣本Xi={vi1，vi2，…，vim}由m個屬性A1，A2，…，Am描述，設(shè)定閾值ε1，ε2(ε2>ε1)，將樣本Xi和Xj建立集對聯(lián)系度，令滿足|vis-vjs|≤ε1(1≤s≤m)的記為正同信息粒S，滿足|vis-vjs|≥ε2的記為負(fù)反信息粒P，滿足ε1<|vis-vjs|<ε2以及缺失的屬性值均記為差異信息粒F，則建立的集對聯(lián)系度公式為：

(2)

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

式(2)也可以簡化為：

ρij=a+bi+cj

(3)

定義7(勢函數(shù)).對于一個三元聯(lián)系數(shù)ρ=a+bi+cj，其勢函數(shù)記為：

(4)

定義8(樣本間集對距離度量).兩個樣本Xi和Xj之間建立的三元集對聯(lián)系度為ρij=a+bi+cj，為了衡量兩個樣本之間的距離大小，將以集對聯(lián)系度中的正同度a以及聯(lián)系數(shù)的勢函數(shù)Shi(ρij)來反映兩個樣本之間的距離大小，其公式為：

(5)

式中，d(Xi，Xj)越小說明兩樣本之間的距離越小.a用來衡量樣本間確定性距離的大小，a越大表示確定性距離越小，Shi(ρij)用來衡量兩樣本之間的距離變化趨勢，Shi(ρij)越大表示距離變大的趨勢越小.

式中，maxv.j，minv.j表示第j個屬性的最大值，最小值.特別注意的是，進(jìn)行距離度量時所需的數(shù)據(jù)為標(biāo)準(zhǔn)化之后的數(shù)據(jù).

定義10(類簇間距離度量). 將類簇Ci和Cj合并后的類簇記為Cw=Ci∪Cj，類簇Cw中的第一個代表點(diǎn)記為p1，其選取公式為：

p1=max{Xd(Cw.mean，X)(X∈Ci.rep∪Cj.rep)}

(6)

剩余R-1個代表點(diǎn)的選取，按照公式：

(7)

將取出的R個點(diǎn)記為新類簇的代表點(diǎn)集Cw.rep，再將選取的代表點(diǎn)根據(jù)收縮因子α進(jìn)行收縮，收縮后的代表點(diǎn)集記為Cw.zoom_rep，其公式為：

Cw.zoom_rep=p+α*(Cw.mean-p)(p∈Cw.rep)

(8)

任意兩個類簇Ci和Cj之間的距離結(jié)合式(5)定義為：

(9)

式中，R代表選取的固定代表點(diǎn)的個數(shù)，p為類簇中選取的將要收縮的代表點(diǎn)，Ci.zoom_rep，Cj.zoom_rep，Cw.zoom_rep代表收縮后的代表點(diǎn)集.需要注意的是，選取新類簇代表點(diǎn)集Cw.rep時，待選取的點(diǎn)是類簇Ci和Cj中未收縮的代表點(diǎn)集Ci.rep和Cj.rep中的點(diǎn)，進(jìn)行類簇間距離計算時，需要將代表點(diǎn)進(jìn)行收縮，選取收縮后的代表點(diǎn)間的最小距離作為類簇間的距離.

表1 類簇Cw的部分距離信息Table 1 Partial distance information for cluster Cw

例：對類簇Ci和Cj進(jìn)行合并，合并后的類簇記為Cw，假設(shè)類簇Ci和Cj的代表點(diǎn)個數(shù)為3，其中代表點(diǎn)為X1，X2，X5∈Ci.rep，X3，X4，X6∈Cj.rep，表1給出的是類簇Cw的部分距離信息，包含樣本點(diǎn)Cw.mean，X1，X2，X3，X4，X5，X6中任意兩者之間的距離，選取代表點(diǎn)的過程如圖1所示，最后得到的類簇Cw的代表點(diǎn)為X3，X5，X6.

圖1 代表點(diǎn)選取過程Fig.1 Represents the point selection process

定義11(類內(nèi)平均距離).根據(jù)建立的集對距離度量方式，對各個類中樣本Xi∈Cj(1≤i≤n，1≤j≤k)與該類簇中心點(diǎn)Cj.mean進(jìn)行距離計算，得到n個距離值，d(X1，Cj.mean)，d(X2，Cj.mean)，…，d(Xn，Cj.mean)，由此定義類內(nèi)距離的平均值為：

(10)

3.2 集對粒聚類結(jié)果表示

在集對信息?？臻g中，定義了3種信息粒集：正同粒集、差異粒集和負(fù)反粒集，正同粒集和負(fù)反粒集屬于確定信息粒，差異粒集屬于不確定信息粒，這3種信息粒集與聚類中存在的3種關(guān)系相一致，因此將集對信息粒的思想引入到CURE聚類中，形成基于集對信息粒的聚類結(jié)果.從集對信息粒中的3種信息粒集的概念出發(fā)，提出了以正同域Cs，邊界域Cu和負(fù)反域Co組成的集對粒層次聚類，其中正同域中的樣本一定屬于這個類簇，邊界域中的樣本可能屬于這個類簇，負(fù)反域中的樣本不屬于這個類簇，其具有如下性質(zhì)：

i)Cs(Ci)≠?

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

性質(zhì)(i)表明每個類簇的正同域不是空集且至少有一個樣本；性質(zhì)(ii)表明每個樣本都必須進(jìn)行聚類分析；性質(zhì)(iii)表明任意兩個類簇的正同域相交為空集.

3.3 算法描述

1)算法思想

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

其中，Cs(Ck)是類Ck的正同域，Cu(Ck)是類Ck的邊界域，正同域和邊界域共同構(gòu)成一個類簇，圖2展示的是一個類簇的聚類結(jié)果.

圖2 SPGCURE聚類示意圖Fig.2 SPGCURE clustering diagram

2)數(shù)據(jù)結(jié)構(gòu)

U={X1，X2，…，Xn}：輸入數(shù)據(jù)集，n為樣本點(diǎn)的個數(shù)；

Xi={vi1，vi2，…，vim}：樣本點(diǎn)，通過m個屬性A1，A2，…，Am進(jìn)行描述；

Ci：儲存每個類簇中的樣本點(diǎn)；

Ci.mean：儲存類簇的中心點(diǎn)；

Ci.rep：儲存類簇的代表點(diǎn)；

Ci.zoom_rep：儲存類簇收縮后的代表點(diǎn)；

Ci.losest：用來跟蹤距離每個類簇Ci最近的簇；

d{Xi，Xj}：表示兩個樣本點(diǎn)之間的距離；

d{Ci，Cj}：表示兩個類簇之間的距離；

Heap結(jié)構(gòu)：將各個類簇根據(jù)與其最近簇之間的距離，按照遞增順序布置在堆中；

k-d tree結(jié)構(gòu)：用來存儲每個類簇的代表點(diǎn)的數(shù)據(jù)結(jié)構(gòu).

3)算法流程

算法.SPGCURE clustering

輸入：從原數(shù)據(jù)集中抽取的隨機(jī)樣本，記為樣本集U={X1，X2，…，Xn}，聚類數(shù)目k，代表點(diǎn)個數(shù)R，收縮因子α

輸出：集對粒層次聚類結(jié)果：C={{Cs(C1)∪Cu(C1)}，{Cs(C2)∪Cu(C2)}，…{Cs(Ck)∪Cu(Ck)}}

1.T：=構(gòu)建kd_tree(U)；

2.Q：=構(gòu)建heap(U)；

3.whilesize(Q)>kdo

4. 提取Q中頂部元素Ci，尋找Ci的最近簇Ci.closest=Cj，并從Q中刪除Cj；

5. 將Ci與Ci.closest=Cj合并為Cw=Ci∪Cj，公式(6)-公式(7)計算得到Cw的代表點(diǎn)集Cw.rep；

6. 將Cw的代表點(diǎn)插入到T中，并從T中刪除Ci和Cj的代表點(diǎn)；

7. 尋找并設(shè)置Cw的最近簇Cw.closest；

8. forQ中的任意一個類簇Cqdo

9. ifCiorCj是Cq的最近簇或Cw成為Cq的最近簇

10. 重新計算Cq的最近簇，并在Q中重新定位Cq；

11. end if

12. end for

13. 將Cw插入到Q中；

14.當(dāng)類簇總數(shù)減少到k時，刪除異常點(diǎn)；

16.fori=1，2，…，ndo

17. 計算各個樣本Xi與其所在類簇Cj.mean(1≤j≤k)的距離：d{Xi，Cj，mean}；

20. 將樣本Xi劃分到正同域Cs(Cj)；

21. else

22. 將樣本Xi劃分到邊界域Cu(Cj)；

23. end if

24.end for

26.fori=1，2，…，n′ do

30. 將樣本劃分到Cj的正同域；

31. else

32. 將樣本劃分到Cj的邊界域；

33. end if

34.end for

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

4)聚類分析

第1階段(步驟1-步驟14)：步驟1-步驟2是對數(shù)據(jù)結(jié)構(gòu)進(jìn)行初始化，將所有輸入樣本點(diǎn)作為代表點(diǎn)插入到k-d tree中，Heap的構(gòu)建是通過距離公式(9)確定任意兩個簇之間的距離，由此得到每個輸入點(diǎn)的最近簇Ci.closest，然后按照距離遞增的順序?qū)⒚總€類簇插入到heap中.步驟3-步驟13是層次聚類迭代的過程，根據(jù)迭代的次數(shù)不同，可以獲得不同層次的聚類結(jié)果，其中步驟5是計算新合并的類簇Cw的代表點(diǎn)，要注意的是若類簇中樣本點(diǎn)的個數(shù)少于固定代表點(diǎn)個數(shù)，則將所有點(diǎn)記為代表點(diǎn).

SPGCURE聚類算法的流程框圖如圖3所示.

圖3 SPGCURE聚類算法流程框圖Fig.3 SPGCURE flow block of clustering algorithm

5)時空復(fù)雜度

時間復(fù)雜度：設(shè)數(shù)據(jù)集的樣本點(diǎn)個數(shù)為n，在第1階段，算法的計算量主要由while循環(huán)產(chǎn)生.在while循環(huán)內(nèi)，計算量最大的是for循環(huán)，產(chǎn)生的復(fù)雜度為O(nmlogn)[4]，m是計算最近簇過程中參數(shù)調(diào)用的次數(shù)，另外步驟5中合并兩個類簇產(chǎn)生的復(fù)雜度由原CURE算法中的O(n)減少為O(1).由于while循環(huán)的主體被執(zhí)行O(n)，且在其每一次迭代中有for循環(huán)的O(n)次迭代，故第1階段的時間復(fù)雜度為O(n2mlogn).在第2階段，計算量主要由for循環(huán)產(chǎn)生，k為類簇數(shù)目，n為樣本點(diǎn)數(shù)目，產(chǎn)生的時間復(fù)雜度為O(kn).第3階段是將未抽取的樣本進(jìn)行劃分，產(chǎn)生的時間復(fù)雜度為O(kn′)，n′是未抽取的樣本個數(shù).所以本文的時間復(fù)雜度為O(n2mlogn+kn+kn′)，即為O(n2mlogn).根據(jù)文獻(xiàn)[20]可得，m的取值通常比n小很多，因此當(dāng)數(shù)據(jù)點(diǎn)的維數(shù)較小時，聚類算法的時間復(fù)雜度為O(n2logn)，雖然增加了以正同域、差異域和負(fù)反域的劃分，但仍與原CURE算法的時間復(fù)雜度保持一致.

空間復(fù)雜度：算法用到的heap和k-d tree兩種數(shù)據(jù)結(jié)構(gòu)，其二者都需要線性空間，則聚類算法的空間復(fù)雜度為O(n).

4 模型驗(yàn)證

為了驗(yàn)證所提出的SPGCURE算法的性能，在實(shí)驗(yàn)部分選取了5個數(shù)據(jù)集進(jìn)行測試，主要進(jìn)行了3方面實(shí)驗(yàn):1)對自身算法進(jìn)行性能分析；2)以不完備數(shù)據(jù)集為實(shí)驗(yàn)數(shù)據(jù)，將本文算法SPGCURE與兩種可以處理不完備數(shù)據(jù)的算法進(jìn)行對比分析，分別是Su等基于q近鄰提出的不完備三支聚類TWD-QNN[21]以及Yang等基于密度峰值提出的不完備三支聚類算法，依照原文將其記為Adopted methods[22]；3)以完備數(shù)據(jù)集為實(shí)驗(yàn)數(shù)據(jù)，選取了經(jīng)典聚類算法k-means[23]和CURE[4]，以及近幾年提出的三支聚類算法CE3-k-means[14]、TCM[15]和3W-DBSCAN[16]進(jìn)行對比分析.

本文所提算法和對比算法是在一臺MBP(macOS Catalina 10.15.3，Quad-Core Intel Core i5 CPU@ 2.3 GHz，8 GB 2133 MHz LPDDR3)上使用Anaconda 2019.10環(huán)境實(shí)現(xiàn)的.

4.1 數(shù)據(jù)集

所選數(shù)據(jù)集的樣本個數(shù)最小為150，最大為5473；數(shù)據(jù)集的屬性個數(shù)最小為4，最大為34，實(shí)驗(yàn)中涉及的這5個數(shù)據(jù)集都是來自UCI數(shù)據(jù)庫，數(shù)據(jù)集的詳細(xì)信息如表2所示.

表2 實(shí)驗(yàn)數(shù)據(jù)集信息Table 2 Information on experimental data sets

4.2 評價標(biāo)準(zhǔn)

聚類評估是評估學(xué)習(xí)方法在確定相關(guān)集群方面的性能的關(guān)鍵過程.良好的聚類質(zhì)量測量將有助于比較幾種聚類算法的優(yōu)劣，以下評價指標(biāo)通常用于評估聚類算法的性能.

1)準(zhǔn)確率(Accuracy)

式中，n為樣本的總數(shù)，θk為簇Ck中正確劃分的樣本數(shù)目.

2)F-measure同時兼顧精確率和召回率，是其二者的調(diào)和平均數(shù)，公式為：

式中：

式中TP表示真實(shí)為正，預(yù)測也為正的個數(shù)，F(xiàn)P表示真實(shí)為負(fù)，預(yù)測為正的個數(shù)，F(xiàn)N表示真實(shí)為正，預(yù)測為負(fù)的個數(shù).

3)調(diào)整蘭德系數(shù)(ARI)

4)標(biāo)準(zhǔn)互信息(NMI)

4.3 實(shí)驗(yàn)結(jié)果與分析

4.3.1 SPGCURE算法性能分析

算法中涉及到了4個參數(shù)：ε1，ε2，k和α.為了使得聚類效果最佳，以Iris數(shù)據(jù)集為例對這4個參數(shù)討論的結(jié)果進(jìn)行展示.由Guha的研究得知[4]，代表點(diǎn)的個數(shù)k一般選取大于10的值，對于收縮因子α的值，一般選取0.2-0.7中的值，故這兩個參數(shù)在此范圍內(nèi)進(jìn)行實(shí)驗(yàn)討論.本文的研究對象包括完備數(shù)據(jù)集和不完備數(shù)據(jù)集，為了模擬含有缺失值的不完備數(shù)據(jù)集，則將數(shù)據(jù)集中樣本的屬性值按照5%、10%、15%和20%的比例進(jìn)行缺失化處理.對隨機(jī)生成的不完備數(shù)據(jù)集，根據(jù)評價指標(biāo)ARI和NMI對不同閾值下的聚類結(jié)果進(jìn)行評價.

圖4 數(shù)據(jù)集Iris的閾值變化曲線Fig.4 Threshold variation curve of the dataset Iris

表3 算法性能分析Table 3 Algorithm performance analysis

圖4給出的是在缺失率10%下，兩個評價指標(biāo)隨著閾值ε1，ε2的改變的波動情況.從圖4中可以看出在ε1=0.1，ε2=0.11的情況下，ARI和NMI的值達(dá)到最大，使得聚類結(jié)果最優(yōu).表3中給出的是在最優(yōu)閾值ε1=0.1，ε2=0.11下，對應(yīng)不同缺失率下的聚類結(jié)果，通過評價指標(biāo)ARI和NMI可以分析出，隨著數(shù)據(jù)中缺失率的增加，聚類的性能會有所下降，導(dǎo)致下降的原因是缺失數(shù)據(jù)越多，具有的不確定性越高，相應(yīng)做出錯誤分類的可能性就越高.

表4 數(shù)據(jù)集Iris在不同收縮因子下的聚類結(jié)果Table 4 Clustering results of Iris under different shrinkage factors

同樣，為了算法的聚類效果最佳，對收縮因子α和代表點(diǎn)的個數(shù)k也進(jìn)行了實(shí)驗(yàn)討論.表4中給出的是Iris數(shù)據(jù)集在收縮因子為0.2-0.7之間的聚類結(jié)果，實(shí)驗(yàn)結(jié)果顯示在α=0.6時達(dá)到的最優(yōu)聚類，ARI的值為0.835，NMI的值為0.851.表5是針對Iris數(shù)據(jù)集，選擇對代表點(diǎn)的個數(shù)最少為5，最多為25，步長為5的聚類結(jié)果進(jìn)行了展示，在實(shí)驗(yàn)過程中，發(fā)現(xiàn)當(dāng)k的值超過20對聚類結(jié)果產(chǎn)生的影響不大，故本文選擇最佳代表點(diǎn)個數(shù)為20.對于其他4個數(shù)據(jù)集通過實(shí)驗(yàn)的方式，也得出了最佳參數(shù)的值，具體結(jié)果如表6所示.

表5 數(shù)據(jù)集Iris在不同代表點(diǎn)下的聚類結(jié)果Table 5 Clustering results of the dataset Iris under different representative points

表6 5個數(shù)據(jù)集的最優(yōu)參數(shù)情況Table 6 Optimal parameters for the five datasets

圖5 數(shù)據(jù)集Iris的集對粒層次聚類結(jié)果Fig.5 Set pair granule hierarchical clustering results of Iris data set

在最優(yōu)參數(shù)下，對數(shù)據(jù)集Iris的集對粒層次聚類結(jié)果進(jìn)行了可視化，如圖5所示，數(shù)據(jù)集聚成了3個類簇，分別用圓圈，菱形和方塊區(qū)分，另外針對每個類簇的正同域和邊界域，是以同符號的實(shí)心和空心進(jìn)行區(qū)分.從圖5中可以看出正同域中的樣本位于類簇的中心區(qū)域，與該類簇具有較強(qiáng)關(guān)系，邊界域中的樣本位于類簇的邊緣區(qū)域，與該類簇具有較弱的關(guān)系.

4.3.2 與其它算法對比分析—不完備數(shù)據(jù)集

本文所提算法既可以用于處理不完備數(shù)據(jù)集，也可以處理完備數(shù)據(jù)集，運(yùn)用隨機(jī)生成的不完備數(shù)據(jù)集將本文算法SPGCURE與其它兩個聚類算法TWD-QNN、Adopted methods進(jìn)行對比，通過評價指標(biāo)Accuracy得到的聚類結(jié)果見表7.

表7 不完備數(shù)據(jù)集的聚類結(jié)果對比Table 7 Comparison of clustering results of incomplete data sets

在表7中可以看到，在Iris和Page-blocks數(shù)據(jù)集中，所提出的SPGCURE算法的準(zhǔn)確性高于比較算法.在Ionosphere數(shù)據(jù)集中，即使它不是最好的算法，但準(zhǔn)確性確實(shí)接近最好的比較算法.此外，這3種聚類算法表明，隨著缺失率的增加，算法的聚類效果會降低，這也與實(shí)際一致，缺失的屬性值越多，原始信息的保留越少.本文所提算法還實(shí)現(xiàn)了即使缺失率增加，精度也不會大幅下降.

4.3.3 與其它算法對比分析—完備數(shù)據(jù)集

本文所提的集對粒層次聚類算法，不僅是在CURE基礎(chǔ)上改進(jìn)得到了3個域表示的聚類結(jié)果，而且涉及到了劃分的思想，故對于完備數(shù)據(jù)集，選擇k-means、CURE、CE3-k-means、TCM和3W-DBSCAN算法進(jìn)行對比分析.對于本文算法SPGCURE，CE3-k-means和3W-DBSCAN分別使用下界(所有簇的正區(qū)域Cs)和上界(所有簇的正區(qū)域和邊界區(qū)域Cs∪Cu)來計算評價指標(biāo)F-measure.由于原TCM算法中只計算了一個聚類結(jié)果，故k-means、CURE和TCM的聚類結(jié)果被認(rèn)為是上界的性能.通過評價指標(biāo)F-measure得到的聚類結(jié)果見表8.

如表8所示，CE3-k-means、3W-DBSCAN以及本文所提算法SPGCURE，對于幾乎所有數(shù)據(jù)集，評價指標(biāo)均在下界給出了較低的值，在上界給出了較高的值，歸因于這兩個集合是通過對二支聚類的收縮或擴(kuò)展一些樣本得到的，上界的性能優(yōu)于下界是合理的.為了更清楚地比較不同算法的性能，針對上界(Cs∪Cu)的聚類結(jié)果，生成了如圖6所示的曲線圖；針對下界(Cs)的聚類結(jié)果，生成了圖7所示的柱狀圖.可以清楚的看到，在Seeds，Contraceptive和Page-blocks數(shù)據(jù)集中，SPGCURE算法在評價指標(biāo)F-measure下得到的聚類結(jié)果均優(yōu)于比較算法，最優(yōu)的結(jié)果已用加粗標(biāo)記，對于Ionosphere數(shù)據(jù)集，最優(yōu)的算法雖是3W-DBSCAN，F(xiàn)-measure值達(dá)到0.831，但其在Ionosphere數(shù)據(jù)集的下界中得到的結(jié)果卻是最差的，僅為0.391.從圖7分析得出，單獨(dú)考慮在下界(Cs)中得到的結(jié)果，算法SPGCURE在Seeds，Ionosphere和Page-blocks這3個數(shù)據(jù)集中，均得到了最優(yōu)聚類結(jié)果.總體來說，SPGCURE算法不僅實(shí)現(xiàn)了可以處理不完備數(shù)據(jù)集聚類問題，而且得到了較好的聚類效果.

表8 完備數(shù)據(jù)集的聚類結(jié)果對比Table 8 Comparison of clustering results of complete data sets

圖6 F-measure下不同數(shù)據(jù)集的方法差異Fig.6 Differences in methods on different datasets under F-measure

圖7 F-measure下針對下界(Cs)不同方法的比較Fig.7 Comparison of different methods for lower bounds (Cs) under F-measure

5 結(jié) 論

在聚類的實(shí)際應(yīng)用中，樣本與類簇之間實(shí)際上存在3種關(guān)系，并且由于數(shù)據(jù)遺漏、讀取限制等原因存在大量不完備數(shù)據(jù)集，為此，本文提出了一種面向不完備數(shù)據(jù)的集對粒層次聚類算法-SPGCURE.對于缺失的屬性值，采用集對信息粒的相關(guān)理論進(jìn)行處理，將原本聚類過程中不同樣本之間的距離擴(kuò)展成包含正同度、差異度和負(fù)反度3個維度的距離定義，可以更加全面的對不完備數(shù)據(jù)集進(jìn)行距離度量.另外，為了更好地表示樣本與類簇之間的關(guān)系，基于改進(jìn)后的距離度量，給出了各個類簇的類內(nèi)平均距離的定義，提出了以正同域Cs，邊界域Cu和負(fù)反域Co表示的集對粒層次聚類.通過對5個數(shù)據(jù)集在指標(biāo)ARI，NMI，Accuracy和F-measure上的值對聚類性能進(jìn)行評價，并且選取了7個算法進(jìn)行對比分析，實(shí)驗(yàn)結(jié)果表明，SPGCURE具有較好的性能.然而，閾值ε1，ε2的變化會對聚類結(jié)果產(chǎn)生較大的影響，如何確定參數(shù)也是下一步的工作，其將會對聚類性能的提高有重要影響.