基于鄰域樣本穩(wěn)定性的三支聚類方法

李洪梅，姜冬勤，王平心

(1.江蘇科技大學(xué) 計算機學(xué)院,江蘇 鎮(zhèn)江 212003;2.江蘇科技大學(xué) 理學(xué)院,江蘇 鎮(zhèn)江 212003)

0 引言

聚類分析是數(shù)據(jù)挖掘與機器學(xué)習(xí)領(lǐng)域中的重要技術(shù)之一[1-2],已經(jīng)廣泛地應(yīng)用于多個領(lǐng)域,包括信息?；痆3-4]、圖像處理[5]、生物信息學(xué)[6]、安全保障[7]、網(wǎng)頁搜索[8]等。所謂聚類就是將數(shù)據(jù)集中的樣本劃分到不同的類簇中,使得相同類簇中的樣本相似度高,而不同類簇中的樣本相似度低。聚類作為一種無監(jiān)督學(xué)習(xí)技術(shù),在識別無標(biāo)簽數(shù)據(jù)結(jié)構(gòu)方面發(fā)揮了極大的作用。針對不同的情況,可以將聚類方法粗略地分為兩大類:層次聚類方法和劃分聚類方法[9]。

傳統(tǒng)的聚類方法大多屬于硬聚類,即對象要么屬于一個類,要么不屬于一個類,聚類的結(jié)果必須具有清晰的邊界。但是在處理不確定性信息時,考慮到當(dāng)前獲取到的信息還不夠充分,強制將其中的元素劃分到一個類中,往往容易帶來較高的錯誤率或決策風(fēng)險。為了解決傳統(tǒng)聚類方法存在的問題,許多新的聚類策略被提出。Hoppner等人[10]將模糊數(shù)學(xué)引入到了聚類分析中,用模糊集表示聚類結(jié)果。Lingras[11-12]提出了粗糙聚類方法,將聚類結(jié)果由粗糙集的正域,邊界域和負(fù)域來表示。以上方法都是對傳統(tǒng)硬聚類的一種改進(jìn)。而三支決策聚類方法[13],是將三支決策[14]思想引入到了聚類分析中,將確定的元素放入核心域中,將不確定的元素放入邊界域中延遲決策,有效地降低了決策風(fēng)險。三支聚類不僅可使聚類的結(jié)果具有更好的結(jié)構(gòu)特征和可解釋性,還可以避免二支決策引起的不必要代價。因此研究基于三支決策的聚類分析具有非常廣泛的科研價值和實際應(yīng)用價值。

自從三支聚類方法提出以來,很多學(xué)者在這個理論框架下發(fā)展了多種三支聚類算法, Afridi等人[15]提出了一種使用博弈論粗糙集模型處理缺失數(shù)據(jù)的三支聚類方法;Wang和Yao[16]提出了一種基于收縮和膨脹的三支聚類框架,稱為CE3,該框架來自數(shù)學(xué)形態(tài)學(xué)的腐蝕和膨脹的思想;Yu等人[17]研究通過低秩矩陣實現(xiàn)主動三支聚類方法。王等人[18]利用動態(tài)鄰域給出了一種基于鄰域的三支聚類算法。以上的研究成果均豐富了三支聚類理論和模型,擴(kuò)大了其應(yīng)用范圍和領(lǐng)域。

2019年,Li和Qian等[19]研究了聚類集成的樣本穩(wěn)定性的概念并用來發(fā)現(xiàn)穩(wěn)定關(guān)系的樣本集并建立基于樣本穩(wěn)定性的集成聚類算法。該方法基于一組聚類結(jié)果,計算任意兩個樣本被劃分在同一類的頻率,即樣本的共現(xiàn)概率。當(dāng)兩樣本的共現(xiàn)概率為1時,說明這兩個樣本始終在同一類;當(dāng)兩樣本的共現(xiàn)概率為0時,說明這兩個樣本始終不在同一類;無論共現(xiàn)概率為1還是為0,都說明兩樣本之間具有較高的穩(wěn)定關(guān)系。而共現(xiàn)概率介于0和1之間的樣本說明在某些聚類結(jié)果是聚在一類,在另外的聚類結(jié)果沒有聚在一類,他們之間的關(guān)系具有一定的不確定性。為了定量的刻畫樣本的穩(wěn)定性,文獻(xiàn)[19]提出了確定性函數(shù)的概念來刻畫兩樣本的確定度并將一個樣本與其他樣本的平均確定度定義為樣本的穩(wěn)定性。穩(wěn)定性比較高的樣本在聚類過程中有著較好類屬關(guān)系,而穩(wěn)定性較低的樣本在聚類過程中類屬關(guān)系較為不確定?；跇颖痉€(wěn)定的理論,最近李等[20]給出了一種基于信息熵的樣本穩(wěn)定性度量函數(shù)。

樣本的穩(wěn)定性理論為研究樣本間關(guān)系的不確定性提供了新思路,同時也為三支聚類中核心樣本和邊界樣本的判別提供了一個新依據(jù)。將穩(wěn)定性的概念和三支聚類方法結(jié)合起來,可以提供一種有效的尋找三支聚類核心域和邊界域的方法。本文利用樣本穩(wěn)定性理論給出一種新的三支聚類方法,其主要思想是將任意兩個樣本的鄰域中的公共元素個數(shù)定義兩個樣本的共現(xiàn)概率,并在此基礎(chǔ)上定義每個樣本的穩(wěn)定性。然后基于閾值將這些樣本元素分為穩(wěn)定樣本集和不穩(wěn)定樣本集。對穩(wěn)定集中的樣本,我們采用傳統(tǒng)方法挖掘其團(tuán)簇結(jié)構(gòu)。對于不穩(wěn)定集中的樣本,我們通過比較樣本到穩(wěn)定集中聚類中心的距離將它們分到相應(yīng)類的邊界域中。通過以上策略,我們得到了三支聚類的核心域和邊界域。

0.1 三支聚類

三支聚類方法是對二支聚類即硬聚類方法的拓展,對于二支聚類分析的基本概念可以總結(jié)為:假設(shè)給定數(shù)據(jù)集U={x1,x2,…,xn}中包含n個樣本對象,數(shù)據(jù)集的聚類數(shù)為k,獲得聚類結(jié)果是C={C1,C2,…,Ck}。則聚類結(jié)果中任意類簇需要滿足以下三個條件:

(1)Ci≠?,i=1,…,k;

(3)Ci∩Cj=?,i≠j。

條件(1)要求任意類簇不為空。條件(2)和條件(3)要求任意樣本對象x∈U有且僅屬于一個類簇。在這種情況下,任意類簇之間有著清晰的界限且每個類簇Ci只是數(shù)據(jù)集U中的一個分區(qū)。

受到三支決策理論的啟發(fā),Yu等人[17]提出了三支聚類分析理論。三支聚類結(jié)果與硬聚類結(jié)果的區(qū)別是:使用一對集合來表示一個類簇即Ci=(Co(Ci),Fr(Ci))。硬聚類結(jié)果中每個樣本對象至多屬于某個類簇,而將那些可能屬于多個類簇的樣本即不確定類簇的樣本強制劃分到某個類簇中可能降低聚類精度。但是三支聚類結(jié)果考慮了那些不確定類簇歸屬的樣本,顯然,樣本對象和類簇之間存在三種關(guān)系即:確定屬于該類簇、不屬于該類簇、可能屬于該類簇。對比可以看出,使用三個域來表示一個類簇更合適,即核心域、邊界域以及瑣碎域。其中Co(Ci)?U、Fr(Ci)?U、Tr(Ci)=U-(Co(Ci)∪Fr(Ci)),這三個集合分別表示類簇的核心域、邊界域以及瑣碎域。這三個子集需要滿足以下幾個條件:

(1)Tr(Ci)∪Co(Ci)∪Fr(Ci)=U,

(2)Co(Ci)∩Fr(Ci)=?,

(3)Co(Ci)∩Tr(Ci)=?,

(4)Fr(Ci)∩Tr(Ci)=?。

如果Fr(Ci)=?,則類簇Ci=Co(Ci)且Tr(Ci)=U-Co(Ci),此時該聚類結(jié)果是一個硬聚類結(jié)果。通過單個集合(邊界域中無樣本對象時)來表示一個聚類結(jié)果是三支聚類結(jié)果的一個特殊情況。

聚類結(jié)果中的核心域和邊界域需要滿足不同的要求,在本文中,我們要求核心域和邊界域滿足以下三個條件:

(1)Co(Ci)≠?,

(3)Co(Ci)∩Co(Cj)=?,i≠j。

條件(1)要求任意類簇不能為空。條件(2)要求數(shù)據(jù)集U中的任意樣本對象至少屬于某個類簇中的核心域或者邊界域,可能存在某個樣本元素x∈U屬于多個類簇的情況。條件(3)要求不同類簇之間的核心域是沒有交集的?；谏鲜鲇懻?得出三支聚類結(jié)果表達(dá)方式,

C={(Co(C1),Fr(C1)),

(Co(C2),Fr(C2)),…,

(Co(Ck),Fr(Ck))}。

數(shù)據(jù)集中的每個樣本至多屬于一個類簇中的核心域而至少屬于一個類簇中的邊界域。

0.2 穩(wěn)定性

文獻(xiàn)[19]利用樣本的共現(xiàn)概率和確定性函數(shù),給出了樣本穩(wěn)定性的定義。其中樣本的共現(xiàn)概率是基于一組聚類結(jié)果,利用兩個樣本劃分在同一類的頻率得到的。 共現(xiàn)概率為1 的樣本表明樣本始終被分在一類,具有較高的穩(wěn)定性。同理共現(xiàn)概率為0 的樣本表明樣本始終沒有被分在一類,兩樣本之間具有較高的穩(wěn)定性,而共現(xiàn)概率介于0和1之間的樣本說明在某些聚類結(jié)果是聚在一類,在另外的聚類結(jié)果沒有聚在一類。為此,文獻(xiàn)[19]給出了確定函數(shù)的概念來評價樣本關(guān)系的確定度,并用一個樣本與其他樣本的平均確定度來定義樣本的穩(wěn)定性。

定義1[19](確定性函數(shù))設(shè)t為區(qū)間[0,1]的一個常數(shù)。樣本的確定性函數(shù)為關(guān)于變量p的函數(shù)f,其中p∈[0,1],,定義如下:

(1) 如果pt,f′(p)>0，

(1)

定義2[19](樣本穩(wěn)定性)假定一個數(shù)據(jù)集X={x1,x2,x3,…,xn}含有n個樣本,pij表示樣本xi與xj的共現(xiàn)概率,基于確定性函數(shù)f,對于每一個點xi,我們可以定義樣本穩(wěn)定性s(xi)如式(2)。

(2)

特別的,針對線性函數(shù)fl(p),樣本點xi的穩(wěn)定性記為sl(xi),其計算方法見式(3)。

(3)

1 基于鄰域樣本穩(wěn)定性的三支聚類

1.1 基于鄰域樣本穩(wěn)定性的定義

在樣本穩(wěn)定性的定義中,樣本的共現(xiàn)概率pij起著關(guān)鍵的作業(yè),如何定義樣本的共現(xiàn)概率pij是一個非常重要的問題。文獻(xiàn)[20]采用兩樣本K近鄰中共同元素的個數(shù)與K的比值作為它們的共現(xiàn)概率。對數(shù)據(jù)集X={x1,x2,x3,…,xn},記樣本xi的K近鄰為KNN(xi),則KNN(xi)滿足:

1)KNN(xi)?X;

2) |KNN(xi)|=K;

3) ?xj∈KNN(xi),xk∈X-KNN(xi),有

dist(xi,xj)≤dist(xi,xk)。

對于樣本xi與xj,基于K近鄰的共現(xiàn)概率pij定義為公式(4)。

(4)

下面我們用一個例子來說明樣本共現(xiàn)概率的計算。設(shè)X={x1,x2,x3,…,x6},它們之間的距離關(guān)系用如表1所示。

表1 X樣本間的距離關(guān)系

利用基于K近鄰的共現(xiàn)概率的定義,設(shè)K=3,我們可以得到樣本間的共現(xiàn)概率如表2所示。

表2 樣本間的共現(xiàn)概率

共現(xiàn)概率為1的樣本表明樣本始終被分在一類,具有較高的穩(wěn)定性。同理共現(xiàn)概率為0的樣本表明樣本始終沒有被分在一類,兩樣本之間具有較高的穩(wěn)定性,而共現(xiàn)概率介于0和1之間的樣本說明在某些聚類結(jié)果是聚在一類,在另外的聚類結(jié)果沒有聚在一類。因此當(dāng)我們得到樣本間的共現(xiàn)概率以后,我們還需要學(xué)習(xí)閾值t,使得穩(wěn)定性函數(shù)在t的值最小。這里我們采用Otsu算法[21]來求t。

1.2 基于鄰域樣本穩(wěn)定性的三支聚類算法

(5)

(6)

其中集合O代表比較穩(wěn)定的數(shù)據(jù)樣本,H代表不穩(wěn)定的數(shù)據(jù)樣本。對穩(wěn)定的數(shù)據(jù)樣本集合我們采用傳統(tǒng)硬聚類kmeans算法得到聚類結(jié)果Ci作為三支聚類的核心域。而對于不穩(wěn)定的數(shù)據(jù)樣本集合,采用遍歷的形式,依次計算環(huán)中的每個數(shù)據(jù)到聚類中心的距離d,隨后我們先找出距離最小的值dmin,將此距離最小的所對應(yīng)的數(shù)據(jù)點劃分為此類的上界,然后計算此點到其他聚類中心的距離與dmin的差值dpoor,如果這個距離dpoor小于指定的閾值p,則把此數(shù)據(jù)點劃分為該類的上界,直至不穩(wěn)定的數(shù)據(jù)樣本集合中數(shù)據(jù)全部遍歷完成。最終得到三支聚類結(jié)果。算法步驟如算法1所示。

算法1:基于鄰域樣本穩(wěn)定性的三支聚類 輸入:數(shù)據(jù)集X={x1,x2,x3,…,xn},鄰域大小K,聚類數(shù)目k。輸出:C={(Co(C1),Fr(C1)),(Co(C2),Fr(C2)),…(Co(Ck),Fr(Ck))}Step1:利用公式(4)求得每兩點共現(xiàn)概率pij并通過Otsu算法來求t;Step2:利用公式(3)可以得到每個樣本的穩(wěn)定性,記SM={sM1,sM2,…,sMn};Step3:利用Otsu算法應(yīng)用到SM求得閾值ts;Step4:利用公式(6)和(7)求得穩(wěn)定的數(shù)據(jù)樣本集O和不穩(wěn)定的數(shù)據(jù)樣本H;Step5:對穩(wěn)定性的數(shù)據(jù)進(jìn)行kmeans聚類得聚類結(jié)果Ci,i=1,2,…,k。Step6:對不穩(wěn)定的數(shù)據(jù)H, for i=1,2,3,…,|H| do 計算不穩(wěn)定點hi到每一個聚類C的聚類中心的距離d={d1,d2,..,dk} 找出集合d中的最小值dmin=min(d), 將dmin對應(yīng)的數(shù)據(jù)hi劃分到其對應(yīng)類C的上界。 接著,計算集合d中其余點與dmin的差值dpoor if dpoor

2 聚類結(jié)果評價指標(biāo)

2.1 準(zhǔn)確率

準(zhǔn)確率(Accuracy)[22]是一種常見的評價聚類結(jié)果好壞的外部指標(biāo)。這個方法就是根據(jù)預(yù)測的結(jié)果與真實值做對比,當(dāng)此值越高說明聚類結(jié)果越好。

定義1[22](ACC)

其中N表示總樣本個數(shù),Ci表示正確劃分到類i的樣本個數(shù),k表示聚類數(shù)。本論文的三支聚類算法實驗所計算的ACC是使用核心域的對象來計算的。

2.2 Davies-Bouldin Index評價指標(biāo)

Davies-Bouldin Index,即DB-Index[23]。由Davide L.Davies和Donald W.Bouldin于1979年提出來的,是一種內(nèi)部聚類評價指標(biāo)。DBI的主要思想是度量每個簇類最大相似度的均值。

定義2[23](DBI)

3 實驗結(jié)果

為了驗證算法的有效性,本文采用5組UCI數(shù)據(jù)對算法進(jìn)行驗證,UCI數(shù)據(jù)集的純度高,噪音數(shù)據(jù)較少,被許多人所認(rèn)可。數(shù)據(jù)集如表3所示,本文將基于鄰域樣本穩(wěn)定性的三支聚類與傳統(tǒng)的聚類k-means和FCM進(jìn)行ACC與DBI聚類指標(biāo)的對比,實驗結(jié)果如表4所示,其中鄰域大小K取為樣本個數(shù)與類別數(shù)2倍比值的整數(shù)部分。

表3 實驗中使用的數(shù)據(jù)集

表4 UCI數(shù)據(jù)集上的實驗結(jié)果

通過比較表4的實驗結(jié)果不難發(fā)現(xiàn),除了在數(shù)據(jù)集Bank上,本文給出的基于樣本鄰域三支聚類ACC略低于k-means和FCM外,其他數(shù)據(jù)集合指標(biāo)上,本文給出的基于樣本鄰域穩(wěn)定性的三支聚類總體性能比k-means算法均有一定的提升: DBI變小,準(zhǔn)確率提高。因而,本文的基于鄰域樣本穩(wěn)定性的三支聚類可以提高聚類精度,改善聚類性能,能夠更好地顯示出聚類的結(jié)構(gòu)。

4 結(jié)論

本文利用樣本鄰域給出了一種基于樣本鄰域穩(wěn)定性的三支聚類算法。該算法使用任意兩個樣本的鄰域中的公共元素個數(shù)定義兩個樣本的共現(xiàn)概率,并在此基礎(chǔ)上定義每個樣本的穩(wěn)定性,然后基于閾值將這些樣本元素分為穩(wěn)定樣本集和不穩(wěn)定樣本集。對穩(wěn)定集中的樣本,我們采用傳統(tǒng)方法挖掘其團(tuán)簇結(jié)構(gòu)。對于不穩(wěn)定集中的樣本,我們通過比較樣本到穩(wěn)定集中聚類中心的距離將它們分到相應(yīng)類的邊界域中。實驗也表明此方法可以提高聚類的精度。

在本文的算法中,鄰域大小K是本算法中一個非常重要的參數(shù),如何設(shè)置參數(shù)K將是未來的研究內(nèi)容之一。