李 萍,龔曉峰,雒瑞森

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

0 概述

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

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

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

1 相關(guān)工作

1.1 自然近鄰

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

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

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

定義3(自然特征值) 當自然鄰居的搜索達到自然穩(wěn)定狀態(tài)時,自然鄰居的搜索次數(shù)稱為自然特征值,記作supk。

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

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

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

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

步驟3r=r+1。

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

1.2 自適應關(guān)聯(lián)融合聚類算法

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

圖1 R15人工數(shù)據(jù)集原始分布及其代表核點

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

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

(1)

其中,cco_num為簇間數(shù)據(jù)點的關(guān)聯(lián)個數(shù)矩陣,co_dist為簇間代表核點的最短距離,ds為簇間最短距離之和,ns為簇間關(guān)聯(lián)個數(shù)之和。

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

(2)

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

圖2 樣本分布示意圖

本文算法步驟具體如下:

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

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

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

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

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

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

1.3 算法分析

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

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

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

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

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

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

2 實驗設置與結(jié)果分析

2.1 實驗參數(shù)設置

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

2.2 結(jié)果分析

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

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

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

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

(3)

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

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

(4)

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

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

表1 聚類算法準確率比較

表2 聚類算法輪廓系數(shù)比較

3 結(jié)束語

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