基于鄰域樣本穩定性的三支聚類方法

李洪梅，姜冬勤，王平心

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

0 引言

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

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

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

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

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

0.1 三支聚類

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

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

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

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

受到三支決策理論的啟發,Yu等人[17]提出了三支聚類分析理論。三支聚類結果與硬聚類結果的區別是:使用一對集合來表示一個類簇即Ci=(Co(Ci),Fr(Ci))。硬聚類結果中每個樣本對象至多屬于某個類簇,而將那些可能屬于多個類簇的樣本即不確定類簇的樣本強制劃分到某個類簇中可能降低聚類精度。但是三支聚類結果考慮了那些不確定類簇歸屬的樣本,顯然,樣本對象和類簇之間存在三種關系即:確定屬于該類簇、不屬于該類簇、可能屬于該類簇。對比可以看出,使用三個域來表示一個類簇更合適,即核心域、邊界域以及瑣碎域。其中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),此時該聚類結果是一個硬聚類結果。通過單個集合(邊界域中無樣本對象時)來表示一個聚類結果是三支聚類結果的一個特殊情況。

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

(1)Co(Ci)≠?,

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

條件(1)要求任意類簇不能為空。條件(2)要求數據集U中的任意樣本對象至少屬于某個類簇中的核心域或者邊界域,可能存在某個樣本元素x∈U屬于多個類簇的情況。條件(3)要求不同類簇之間的核心域是沒有交集的。基于上述討論,得出三支聚類結果表達方式,

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

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

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

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

0.2 穩定性

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

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

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

(1)

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

(2)

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

(3)

1 基于鄰域樣本穩定性的三支聚類

1.1 基于鄰域樣本穩定性的定義

在樣本穩定性的定義中,樣本的共現概率pij起著關鍵的作業,如何定義樣本的共現概率pij是一個非常重要的問題。文獻[20]采用兩樣本K近鄰中共同元素的個數與K的比值作為它們的共現概率。對數據集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近鄰的共現概率pij定義為公式(4)。

(4)

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

表1 X樣本間的距離關系

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

表2 樣本間的共現概率

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

1.2 基于鄰域樣本穩定性的三支聚類算法

(5)

(6)

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

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

2 聚類結果評價指標

2.1 準確率

準確率(Accuracy)[22]是一種常見的評價聚類結果好壞的外部指標。這個方法就是根據預測的結果與真實值做對比,當此值越高說明聚類結果越好。

定義1[22](ACC)

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

2.2 Davies-Bouldin Index評價指標

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

定義2[23](DBI)

3 實驗結果

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

表3 實驗中使用的數據集

表4 UCI數據集上的實驗結果

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

4 結論

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

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