基于自然近鄰的自適應關聯融合聚類算法

李 萍,龔曉峰,雒瑞森

(四川大學 電氣信息學院,成都 610065)

0 概述

聚類分析是數據挖掘領域的一個重要分支,其可在無任何先驗知識的條件下,用于探索數據之間的內部結構和內在聯系從而獲取有價值的信息。聚類的過程是通過迭代將數據集劃分為多個類簇,并且使類間聯系盡可能小、類內聯系盡可能大[1]。如今,聚類分析已廣泛應用于人工智能、圖像處理、模式識別等任務中。

聚類算法一般可分為基于劃分的聚類、基于網格的聚類、基于密度的聚類等算法[2-3]。K均值聚類(K-means)算法[4-5]是基于劃分聚類的經典算法,通過多次迭代找到最佳數據均值點作為聚類中心,因此異常點和噪聲點對聚類中心的影響很大。基于此,文獻[6-7]相繼提出K-medoids聚類和K-modes聚類算法來尋找最佳聚類中心,改善異常點和噪聲點對聚類中心的影響,但其都需要設定初始聚類個數。STING算法[8]是基于網格聚類的代表算法,將數據每個屬性的可能值劃分成多個相鄰區間,從而創建網格單元集合進行聚類,但其也需提前設定聚類個數。基于密度的空間聚類(Density-Based Spatial Clustering of Applications with Noise,DBSCAN)算法[9]是基于密度聚類的經典算法,該算法能夠識別異常點和噪聲點,然而需要人工設定兩個鄰域信息參數(Eps和Minpts),并且對于數據集的密度比較敏感。為解決以上問題,文獻[10]提出改進的DBSCAN算法對不同密度層次的數據進行分層聚類,但需要確定近鄰數K。文獻[11]提出一種新的密度峰值聚類(Density Peaks Clustering,DPC)算法,該算法只需要指定一個截斷距離來計算數據集的局部密度,但是聚類中心的選取需要利用決策圖進行判斷,缺乏可靠性。近些年來,基于圖論的譜聚類算法[12]廣泛應用于聚類任務中。譜聚類主要通過求解圖的最優劃分得到最優結果,但是該算法的準確性依賴于其鄰接矩陣,基于此,文獻[13-14]相繼提出改進的譜聚類算法,雖然通過改進鄰接矩陣能有效改善聚類效果,但是需要指定聚類數并且無法識別出異常點和噪聲點。

由于多數聚類算法需要指定聚類參數,導致聚類結果的準確性受到影響,而自然近鄰[15-16]是一種無尺度的最近鄰概念,其利用數據集自身的特性進行自然鄰居的搜索,通過每個數據點的自然鄰居個數來判斷其周圍的數據分布情況,因此無需人為指定聚類參數。本文利用自然近鄰的特性篩選出密度較高的數據作為代表核點進行聚類,從而排除邊界點和噪聲點對聚類的影響,通過建立簇間的關聯度矩陣來尋找具有關聯度的簇,并根據簇間融合的有效性評估自適應合并關聯度較高的簇,最終得到理想的聚類結果。

1 相關工作

1.1 自然近鄰

自然近鄰是一種新型的最近鄰概念,其屬于無尺度最近鄰方法的范疇,自然鄰居的搜索過程中不需要進行人工的參數設置,而是通過不斷擴大自然鄰居的搜索范圍,使得數據集比較密集的地方自然鄰居較多,數據集比較稀疏的地方自然鄰居較少。對于一些離群點和噪聲點而言,其自然鄰居個數相對較少甚至幾乎為0。假設存在數據集X,p∈X,q∈X且p≠q,則存在如下定義[17]:

定義1(逆K近鄰) 若q在p的K近鄰內,則稱p屬于q的逆K近鄰,記為p∈RNNk(q)。

定義2(自然穩定狀態) 在自然鄰居的搜索過程中,若每個數據點都有逆近鄰或者當所有逆鄰個數為0的數據不變時,自然鄰居搜索達到自然穩定狀態。

定義3(自然特征值) 當自然鄰居的搜索達到自然穩定狀態時,自然鄰居的搜索次數稱為自然特征值,記作supk。

定義4(自然近鄰) 當自然鄰居的搜索達到自然穩定狀態時,若?p是q的supk逆近鄰,則稱p是q的自然鄰居,同理,若q是p的supk逆近鄰,則稱q是p的自然鄰居。

自然近鄰搜索算法的具體步驟如下:

步驟1初始化搜索次數r=1,自然近鄰數nb=?,逆近鄰數RNN=?。

步驟2計算每個樣本p的r近鄰、nb(p)及RNN(p)。

步驟3r=r+1。

步驟4當?q使得RNN(q)≠?或所有RNN=?的q值不再變化時,supk=r-1,輸出supk、nb和RNN,否則跳轉至步驟2。

1.2 自適應關聯融合聚類算法

本文通過自然近鄰思想尋找數據集中的相對稀疏點和密集點。為去除稀疏的邊界點和噪聲點信息,本文提出代表核點的概念,即代表核點周圍的自然鄰居數較多并且其周圍分布的自然鄰居也多數為代表核點。因此,由代表核點組成的代表核點集能反映數據的集中分布情況,從而體現原數據集的主要數據結構信息。以R15人工數據集為例,通過計算代表核點并去除干擾點,得到如圖1所示的主要簇信息,最后將代表核點進行聚類得到初始聚類信息和聚類數。

圖1 R15人工數據集原始分布及其代表核點

定義5(代表核點) 當自然鄰居的搜索達到自然穩定狀態時,?p滿足其自然鄰居個數nb(p)大于等于自然特征值supk,并且在p的supk范圍內滿足此條件的數據個數大于不滿足該條件的數據個數,則稱該點為代表核點。

代表核點的選取雖然能有效移除邊界點和噪聲點,從而使得邊界點和噪聲點不會影響數據的聚類,但是由于同簇數據間會存在一些相對稀疏的非邊界點數據,該算法可能會將這些相對稀疏的非邊界點移除,使得同簇的數據最終聚為兩個不同的簇。因此,本文提出關聯度矩陣(ccomatrix)的概念。關聯度矩陣表示簇間的關聯程度,簇間關聯度越大,則關聯程度越高,當簇間關聯度為0時,即不存在關聯關系,其數學表達式如下:

(1)

其中,cco_num為簇間數據點的關聯個數矩陣,co_dist為簇間代表核點的最短距離,ds為簇間最短距離之和,ns為簇間關聯個數之和。

為尋找最佳的關聯簇進行融合,本文引入一種幾何方法[18]計算簇間的融合信息。簇間的融合度量體現了簇間融合的有效性,本文通過聚類簇的數據特征軸和聚類簇間的距離來評估聚類結果對于簇間分離或融合的有效性。當聚類數據簇間的融合度量(GI)達到最優值時(GI達到最小),此時的聚類數為最佳聚類數。簇間的融合度量可表示為:

(2)

其中,λ表示聚類簇的協方差矩陣的特征根,d表示聚類數據維度,c表示聚類個數,k表示第k類簇,q表示第q類簇,mk表示第k類簇的中心點,mq表示第q類簇的中心點。

圖2 樣本分布示意圖

本文算法步驟具體如下:

步驟1將數據進行歸一化處理,利用自然近鄰搜索算法計算自然特征值supk,逆近鄰數RNN,自然近鄰數nb。

步驟2通過定義5選擇代表核點,將互為最大逆鄰范圍內的代表核點歸為一類。

步驟3將最大逆鄰范圍內包含代表核點的未歸類點歸為離其最近的代表核點類。

步驟4對于最大逆鄰范圍內未包含代表核點的未歸類點,若在其逆鄰范圍內包含具有類簇信息的數據點,則將該點歸為該類簇,否則判斷其為異常點。

步驟5通過式(1)計算簇間的關聯度矩陣ccomatrix,選擇關聯度大于0的值從高到低排序作為數據融合閾值。

步驟6通過式(2)計算從高到低閾值下數據融合的最小GI值,選擇最小GI值所對應的聚類數作為最佳聚類數,得到最終的聚類結果。

1.3 算法分析

本文算法主要分為初步聚類和聚類有效性評估兩個部分:

第一部分主要是對數據集進行初步聚類,首先利用自然近鄰篩選代表核點,再對代表核點集進行初步聚類,最后將一些邊界點進行歸類,其主要優點如下:

1)在代表核點的篩選過程中,由于自然近鄰能尋找每個數據點的自然鄰居,其自然鄰居數越多,該數據點的位置就越集中,因此可以將自然鄰居數少的邊界點和噪聲點排除,避免代表核點集聚類時將噪聲點和具有邊界相連的數據簇融合。

2)由于自然近鄰算法的自然鄰居尋找是通過數據點附近的數據分布特點進行搜索,因此對于不同密度簇的數據集而言,代表核點的篩選不會將整體密度較小的數據簇作為噪聲點或邊界點排除,只要密度較小的數據簇分布集中,也能篩選出該簇的主要簇信息。

3)對于代表核點的聚類,考慮數據點間的密度分布情況,本文通過對代表核點間的互逆近鄰關系進行聚類從而達到一個理想效果,對于非代表核點的分類,主要分為兩種情況,即其逆鄰范圍內存在代表核點和不存在代表核點,將存在代表核點的數據歸為最近核點類,而不存在代表核點類的數據,若逆鄰范圍內無類簇信息,則可證明其遠離信息簇,其可能為異常點或噪聲點。

第二部分主要是對第一部分的初步聚類效果進行有效性評估。由于初步聚類過程中可能存在同簇間數據連接較稀疏,使得代表核點的篩選過程中將同簇分離,因此本文需要對聚類結果進行評估。該部分首先求出類簇間的關聯度,其中關聯度越小,類簇間融合的可能性越小,當簇間關聯度為0時,說明該簇組無關聯,無需考慮融合。為尋找最佳的關聯簇進行融合,本文結合關聯度信息與簇間融合度量的方法,將關聯度以從高到低的類簇進行依次融合并計算其對應的GI值,當GI值達到最小時停止融合。此時的聚類結果可作為最佳聚類結果,可見本文算法在無需設定聚類數的情況下仍能尋找出合適的類簇個數。

2 實驗設置與結果分析

2.1 實驗參數設置

為驗證本文聚類算法的有效性,將其與DBSCAN密度聚類、K-means聚類算法分別在D31、Aggregation、Five_Clusters人工數據集上進行對比驗證,其中,K-means聚類算法的聚類個數K選取原始數據集的類簇個數,DBSCAN算法的參數Eps和Minpits選取接近于原始類簇聚類效果的最佳值。

2.2 結果分析

實驗最終聚類結果如圖3～圖5所示,其中的實心圓點為噪聲點或異常點。通過原始數據特征可以看出,3種類型的數據集都存在邊界值相連的情況并且部分數據簇存在密度分布不均的問題。對于K-means聚類結果而言,由于K-means算法聚類中心選取不當,導致數據集中同簇數據分離成為異簇,異簇數據合并成為同簇。對于DBSCAN聚類結果而言,由于DBSCAN算法參數選取容易將邊界相連的兩類數據合并為同一簇,大部分邊界點和密度較稀疏的點判斷為噪聲點。本文算法考慮到較稀疏的邊界值和噪聲點對數據聚類結果的影響,首先使用自然近鄰搜索算法在保證密度層次較低的數據簇不被當作邊界點或噪聲點排除的情況下選取代表核點進行初步聚類,再將一些與類簇有關聯的邊界點進行歸類,而無關聯的數據點判定為異常點或孤立點,最后對已聚類的類簇間進行關聯度計算排序,按照關聯度大小依次計算融合后數據集的GI值,通過尋找最小的GI值使得數據集中本為同簇的類簇合并為一簇,從而找到合適的聚類數。因此,對比K-means算法和DBSCAN算法的聚類結果,本文算法在無需指定聚類個數的條件下,對邊界互連和密度層次不同的類簇仍具有比較理想的聚類效果,并且能識別出偏離類簇較遠的異常點或噪聲點。

圖3 D31人工數據集原始分布及聚類算法效果對比

圖5 Five_Clusters人工數據集原始分布及聚類算法效果對比

為驗證算法的有效性,本文采用準確率[19]和輪廓系數[20]兩組指標對這3種聚類算法的聚類結果進行評價。準確率是聚類結果的外部評價指標,其原理是將聚類得到的類標簽與原數據的類標簽進行對比,并計算出正確分類的樣本個數占總樣本的比值,準確率的比值越大,則表示聚類的質量越高,準確率的數學表達式如式(3)所示:

(3)

其中,xi表示第i個樣本的正確類標號,yi表示聚類計算后得到的第i個樣本的類標號,當xi=yi時,δ(xi,yi)=1,否則δ(xi,yi)=0。

輪廓系數是聚類結果的內部評價指標,其衡量了每個樣本與其同簇樣本間的緊密程度和異簇樣本間的分離程度,取值范圍為[-1,1],輪廓系數的數學表達式如式(4)所示:

(4)

其中:a(i)表示第i個樣本與同簇樣本間的平均歐式距離;b(i)表示第i個樣本與所有異簇樣本間的最小平均歐式距離;S(i)越接近于1,表示第i個樣本聚類越具合理性,本文取所有樣本的平均輪廓系數作為評價指標。

如表1和表2所示,本文實驗分別記錄了K-means算法、DBSCAN算法和本文算法在D31、Aggregation、Five_Clusters人工數據集下的聚類準確率和輪廓系數值。對于K-means算法,本文對每個數據集進行100次獨立的K-means算法實驗,實驗的準確率和輪廓系數值取100次重復實驗的平均結果。通過對比可知,本文算法的聚類準確率和輪廓系數值在不同數據集上均明顯高于K-means算法和DBSCAN算法,驗證了本文算法的可靠性。

表1 聚類算法準確率比較

表2 聚類算法輪廓系數比較

3 結束語

本文提出基于自然近鄰的自適應關聯融合聚類算法,在自然近鄰的基礎上尋找代表簇結構的核點進行初步聚類,并通過簇間融合度量尋找關聯度矩陣中的最優關聯度類簇進行融合。實驗結果表明,本文算法無需人工設定聚類參數,可以有效處理密度層次不同和簇間相互靠近的類簇,同時能排除異常點和噪聲點的干擾。但由于本文算法在多維數據集中的聚類效果不明顯,因此后續將對多維數據集的最佳聚類個數確定問題進行研究,進一步提升算法聚類準確率。