一種面向不完備數(shù)據(jù)的集對(duì)粒層次聚類算法

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

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í)別、圖像對(duì)象提取、和數(shù)據(jù)壓縮等多個(gè)領(lǐng)域.現(xiàn)有的聚類算法根據(jù)聚類策略粗略地劃分成劃分聚類[2]、密度聚類[3]、層次聚類[4,5]幾種類型，本文將著重對(duì)層次聚類算法進(jìn)行研究與討論.

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

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

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

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

2 基本理論

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

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

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

2.2 集對(duì)信息粒

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

ρ=a+bi+cj

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

τX(jué)C：W0→[0，1]，x→τX(jué)C(x)=aR+cR

τX(jué)U：W0→[0，1]，x→τX(jué)U(x)=bR

τX(jué)Cs：XC→[0，1]，x→τX(jué)Cs(x)=aR

τX(jué)Co：XC→[0，1]，x→τX(jué)Co(x)=cR

定義3. (集對(duì)聯(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建立集對(duì)聯(lián)系度，用矩陣A表示為：

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

2.3 CURE聚類算法

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

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

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

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

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

(1)

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

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

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

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

3 算法描述與分析

3.1 集對(duì)信息距離度量

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

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

(2)

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

式(2)也可以簡(jiǎn)化為：

ρij=a+bi+cj

(3)

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

(4)

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

(5)

式中，d(Xi，Xj)越小說(shuō)明兩樣本之間的距離越小.a用來(lái)衡量樣本間確定性距離的大小，a越大表示確定性距離越小，Shi(ρij)用來(lái)衡量?jī)蓸颖局g的距離變化趨勢(shì)，Shi(ρij)越大表示距離變大的趨勢(shì)越小.

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

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

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

(6)

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

(7)

將取出的R個(gè)點(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)

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

(9)

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

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

例：對(duì)類簇Ci和Cj進(jìn)行合并，合并后的類簇記為Cw，假設(shè)類簇Ci和Cj的代表點(diǎn)個(gè)數(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)的過(guò)程如圖1所示，最后得到的類簇Cw的代表點(diǎn)為X3，X5，X6.

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

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

(10)

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

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

i)Cs(Ci)≠?

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

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

3.3 算法描述

1)算法思想

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

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

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

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

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

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

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

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

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

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

Ci.losest：用來(lái)跟蹤距離每個(gè)類簇Ci最近的簇；

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

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

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

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

3)算法流程

算法.SPGCURE clustering

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

輸出：集對(duì)粒層次聚類結(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)計(jì)算得到Cw的代表點(diǎn)集Cw.rep；

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

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

8. forQ中的任意一個(gè)類簇Cqdo

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

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

11. end if

12. end for

13. 將Cw插入到Q中；

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

16.fori=1，2，…，ndo

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

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

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

5)時(shí)空復(fù)雜度

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

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

4 模型驗(yàn)證

為了驗(yàn)證所提出的SPGCURE算法的性能，在實(shí)驗(yàn)部分選取了5個(gè)數(shù)據(jù)集進(jìn)行測(cè)試，主要進(jìn)行了3方面實(shí)驗(yàn):1)對(duì)自身算法進(jìn)行性能分析；2)以不完備數(shù)據(jù)集為實(shí)驗(yàn)數(shù)據(jù)，將本文算法SPGCURE與兩種可以處理不完備數(shù)據(jù)的算法進(jìn)行對(duì)比分析，分別是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)行對(duì)比分析.

本文所提算法和對(duì)比算法是在一臺(tái)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ù)集的樣本個(gè)數(shù)最小為150，最大為5473；數(shù)據(jù)集的屬性個(gè)數(shù)最小為4，最大為34，實(shí)驗(yàn)中涉及的這5個(gè)數(shù)據(jù)集都是來(lái)自UCI數(shù)據(jù)庫(kù)，數(shù)據(jù)集的詳細(xì)信息如表2所示.

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

4.2 評(píng)價(jià)標(biāo)準(zhǔn)

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

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

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

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

式中：

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

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

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

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

4.3.1 SPGCURE算法性能分析

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

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

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

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

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

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

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

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

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

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

表7 不完備數(shù)據(jù)集的聚類結(jié)果對(duì)比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種聚類算法表明，隨著缺失率的增加，算法的聚類效果會(huì)降低，這也與實(shí)際一致，缺失的屬性值越多，原始信息的保留越少.本文所提算法還實(shí)現(xiàn)了即使缺失率增加，精度也不會(huì)大幅下降.

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

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

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

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