一種啟發式確定聚類數方法

盧建云，朱慶生，吳全旺

1(重慶大學 計算機學院，重慶 400044)2(重慶大學 軟件理論與技術重慶市重點實驗室，重慶 400044)3(重慶電子工程職業學院 軟件學院，重慶 401331)

1 引 言

聚類分析是數據挖掘、模式識別領域的最重要任務之一，具有非常廣泛的應用，例如，圖像聚類，社交網絡，信息檢索，文本聚類等.聚類就是將數據集劃分成若干個類簇，同一類簇中的數據點具有高度的相似度，不同類簇中的數據點具有極低的相似度.層次聚類可以將數據集表示成樹型結構圖，根據需求對樹型結構圖的某一層次進行劃分，從而得到相應的聚類.聚類在實際應用中遇到很多的挑戰，比如噪聲點干擾、類內密度變化、復雜形狀、高維數據、不均衡數據等.這些挑戰對聚類數目的選擇造成了很大的困難，同時聚類結果表現也達不到要求.聚類數目是聚類研究的基礎問題之一，大多數聚類算法需要輸入聚類數目，在沒有更多的先驗知識的情況下，確定最佳聚類數目顯得尤為困難.

針對復雜數據集確定最佳聚類數目問題，本文提出了一種啟發式的最佳聚類數目確定方法.K-最近鄰鏈間距啟發規則能夠通過半徑擴展的方式識別出球凸形狀類間的變化，K-最近鄰鏈最近鄰間距啟發規則能夠識別出不規則形狀類間的變化.啟發式規則能夠清楚地識別出類間的變化情況，通過決策圖確定出最佳聚類數目和聚類代表點.在數據集上的實驗結果表明，我們提出的聚類方法可以有效地找到正確的聚類個數，與流行的聚類算法相比取得了較好的聚類結果.

2 相關工作

目前聚類還沒有一個統一的定義.通常把聚類定義為：同一個類簇內的對象具有很高的相似度，不同類簇間的對象具有很低的相似度；類簇是一個密度相對較高的空間點的集合，類簇之間被相對密度較低的區域分離[1].在聚類分析中，聚類數目往往預先是不知道的，需要對數據集進行分析得到預估的聚類數目.當面對具有復雜結構的數據集時，設置最佳聚類數目就顯得很困難[2].

陳黎飛等人[3]提出了一種基于層次劃分的最佳聚類數目確定方法，該方法首先統計數據集的聚類特征值，增量構建不同層次劃分聚類的質量曲線，曲線上的極值點所對應的劃分即是最佳聚類數目.周世兵等人[4]認為決定聚類質量的關鍵是確定最佳聚類數目，并提出了一種基于近鄰傳播算法的最佳聚類數目確定方法，該方法通過計算樣本聚類距離和樣本聚類離差距離來確定最佳聚類數目.劉娜等人[5]針對譜聚類通常缺少聚類數目問題，提出了一種自動確定最佳聚類數目的文檔譜聚類方法.該方法利用形態學對矩陣進行轉換、過濾，通過特征間隙確定最佳聚類數目.針對傳統k-means算法對初始聚類中心敏感，并且無法事先確定聚類數目，王勇等人[6]提出了一種高效的k-means最佳聚類數算法，該方法通過樣本數據分層技術得到聚類數目的上界，利用設計的聚類有效性評價指標在聚類數目搜索范圍內得到最佳聚類.同樣是選取k-means初始聚類中心，何云斌等人[7]提出了通過標準差確定有效密度半徑，并從高密度區域中選取具有代表性的樣本點作為初始聚類中心，選取距離全局中心最遠的點集作為最優的初始中心點集合.馮柳偉等人[8]提出了最近鄰一致性和最遠鄰相異性的準則，利用最近最遠得分評價指標來自動確定類別數的聚類算法.

DBSCAN算法[9]通過調整參數ε和MinPts來自適應地學習最佳聚類數目，并且能夠找到具有不同形狀和大小的類簇.Dp算法[10]提出了一種搜索密度峰值的聚類算法，它使用臨界值核函數或高斯核函數來計算每個數據點的局部密度，基于這些數據點的局部密度使用δ距離函數來評估這些數據點之間的距離.Dp算法選擇具有更高局部密度和δ距離的數據點作為聚類的中心，根據決策圖能夠找到正確的聚類數目.近來，受到PageRank算法的啟發，Liu等人提出了基于PageRank的聚類算法[11，12].PageRank算法的優勢體現在快速收斂，與數據集的大小和數據點的維度無關等.在文獻[11]中，K-PRSCAN算法與數據點的重要性順序密切相關，并且跨度參數對聚類的輸出數目有著很大的影響.文獻[12]中，作者提出了一種影響力聚類算法，簡稱為CSIP.CSIP算法采用升序方式對所有數據點的影響力進行排序，并從具有最低影響力的數據點開始進行聚類.具有較低影響力的數據點幾乎都是邊界點，它們描述了每個類簇的輪廓.

3 數據點重要性度量

3.1 隨機游走模型

在數據集上查找重要數據點的過程可以被看作在該數據集構建的有向圖上的隨機游走過程[13].它始發于一個隨機數據點，然后隨機選擇一個能夠跳到另一個數據點的外部鏈接，選中的數據點具有漸近的概率作為數據中心，能夠以迭代方式計算出每個數據點作為數據中心的全局值.全局值較高的數據點能夠描述聚類結構和特征.隨機游走模型相關定義如下.

定義1. (數據點p的k最近鄰距離)在一個數據集D中，數據點p的k最近鄰距離表示為k_dist(p)，它是指數據點p和o之間的距離d(p，o)，具體性質描述如下：

1)至少有k個對象q∈D/{p}，那么，d(p，q)<=d(p，o)；

2)至多有(k-1)個對象q∈D/{p}，那么，d(p，q)

定義2. (數據集的k-最近鄰有向圖G)給出一個數據集D，數據點p，q∈D，p≠q.如果d(p，q)<=k_dist(p)，那么，在G中有一條有向邊從頂點p到q.

定義3. (有向圖G的鄰接矩陣)給出一個n個頂點的有向圖G，它的鄰接矩陣A是一個n×n矩陣.在該矩陣中，如果從頂點i到頂點j存在有向邊，A中元素aij的值等于1；反之，aij=0.

鄰接矩陣用于存儲數據集k-最近鄰有向圖中數據點的鏈接關系.在鄰接矩陣A中，第i行元素的總和表示從數據點i到其他數據點的內部鏈接數，第j列元素的總和表示從其他數據點到數據點j的外部鏈接數，分別用ri和cj(1<=i，j<=n)表示.假設S為隨機游走模型的轉移概率矩陣，則S可以用公式(1)表示如下.S中的元素都嚴格介于0和1之間，并且每列元素的總和都等于1.

(1)

在實際應用中，k-最近鄰有向圖可能包含完整的子圖，這些子圖不會鏈接到任何外部數據點.這就意味著，游走者可能走進某個子圖，并隨機漫步在這個封閉的區域內.因此，它只能發現局部聚類中心，而非全局聚類中心.為了避免這種現象，我們將具有小概率的阻尼因子α添加到隨機矩陣S中，改進后的S如公式(2)所示.

(2)

目前S是一個列不可約隨機矩陣.根據Perron-Frobenius理論[14]，S取1為最大特征值，其對應的特征向量取值為0和1之間的非負數.數據點的重要性可以轉化為計算S的特征值1所對應的特征向量問題.描述如下：

Sx=x

(3)

通常查找給定矩陣特征值的特征向量是一個復雜而耗時的問題.文獻[14]給出了幾種計算特征向量的方法.本文選擇Power方法，其具有存儲少、計算時間短和復雜度低等優點.在Power方法中，如果阻尼因子α的值太小，則矩陣S將很難描述數據點的真正鏈接關系；如果阻尼因子α的值接近1，則算法收斂很慢.在實驗中，為了反映數據點的鏈接關系，我們將α值設為0.95.

3.2 重要性排序算法

本節給出了基于隨機游走模型迭代計算每個數據點的全局重要性的算法，具體描述如算法1所示.該算法包含三個參數k，α和ε.其中，k是查找最近鄰居個數，α是防止算法陷入局部最優的阻尼因子，ε用來控制算法的收斂速度.在實驗中，設置參數k取值為離散區間[5，30]，α= 0.95，ε= 10-6.

算法1.數據點重要性排序

輸入：包含n個數據點的數據集D，參數k，α和ε.

輸出：包含每個數據點的全局重要性的向量dpir.

1.初始化參數k，α和ε.

2.在數據集D中查找每個數據點的k-最近鄰.

3.根據k-最近鄰有向圖構造鄰接矩陣A.

4.根據公式(2)計算列不可約隨機矩陣S.

5.根據公式(3)，使用Power方法計算矩陣S特征值1對應的特征向量.

6.返回特征向量dpir.

4 啟發聚類算法

4.1 k最近鄰鏈啟發規則

通常聚類中心是數據密集區域或中心區域.具有較高的重要性的數據點通常位于數據集的密集區或中心區域，而位于稀疏區或邊界區的噪聲和邊界點通常具有較低的重要性.本節我們提出了基于k-最近鄰鏈的啟發規則來確定最佳聚類個數，相關定義如下.

定義4. (k-最近鄰鏈)給定一個具有n個數據點的數據集D，kNN(p)表示數據點p的k-最近鄰集合，t=|kNN(p)|，t≤n-1.存在數據點p的一個k-最近鄰鏈p，q1，q2，…，qi，qi+1，…，qt，其中qi表示p的第i個近鄰，qi≠qi+1，d(p，qi)≤d(p，qi+1)，1≤i

啟發規則1. (k-最近鄰鏈間距)給出數據點p的一條k-最近鄰鏈，用kNNC(p)表示，t= |kNNC(p)|表示kNNC(p)中包含數據點的個數，k-最近鄰鏈間距定義為Δg(qi) =d(p，qi)-d(p，qi-1)，qi是p的第i個最近鄰，qi-1是p的第i-1個最近鄰，1

我們注意到，Δg能夠描述類簇之間的距離變化.當k-最近鄰鏈中包含的數據點屬于不同的類簇時，繪制出的Δg曲線將包含比較明顯的峰值，而不是平滑的曲線.啟發規則1對于檢測球凸形狀的類簇非常有效.對于具有不規則形狀的類簇或一個類簇嵌入到另一個類簇中，我們引入另一種啟發規則來找到正確的聚類數.下面給出k-最近鄰鏈最近鄰間距的定義.

啟發規則2. (k-最近鄰鏈最近鄰間距)給出數據點p的一條k-最近鄰鏈kNNC(p)，t= |kNNC(p)| 表示kNNC(p)中包含數據點的個數.kNNC(p)中第i個點qi的最近鄰間距定義為Δnng(qi) =d(qi，qj) 1≤i≤t，1≤j

k-最近鄰鏈最近鄰間距揭示了類簇內的密度變化.一旦Δnng曲線包含比較明顯的峰值，我們便認為出現了新的類簇.如果數據點qi具有較大的Δg(qi)值，則Δnng(qi)值也較大.反之，則不一定成立.

4.2 算法步驟

聚類過程分兩個階段，第一階段我們利用k_dist距離圖譜來確定截取的重要數據點的個數，然后對截取的數據點構建k-最近鄰鏈，計算鏈中每個點的Δg和Δnng值并繪制二維決策圖，得到最佳聚類數目和聚類代表點.第二階段利用最近距離傳播進行聚類.我們提出的啟發聚類算法如下所示.

算法2.啟發聚類算法(Heuristic Clustering，HC)

輸入：數據集D.

輸出：聚類標簽C.

1.計算數據集k_dist距離.

2.確定截取重要數據點個數Nimp，形成新的數據集Dimp.

3.為新數據集Dimp構建歐氏距離矩陣E.

4.在矩陣E中找到具有最大值的數據點p.

5.構建一鏈(Nimp-1)NNC(p)鏈.

6.計算Δheu(qi)=Δg(qi)+Δnng(qi)，qi∈(Nimp-1)NNC(p).

7.對Δheu進行降序排序.

8.從決策圖中確定聚類數目c，并從(Nimp-1)NNC(p)中得到對應的聚類代表點q1，q2，…，qc.

9.初始化聚類C={C1={q1}，C2={q2}，…，Cc={qc}}，D=D-{q1，q2，…，qc}.

10.for 每個數據點p∈D

11.dist[p]=min(p，C).

12.end

13.[pi，Cj]=min(dist) .

14.Cj=Cj∪{pi}.

15.D=D-{pi}.

16.重復步驟9-14，直至D=?.

17.返回聚類標簽C.

5 實驗與結果

在本節中，在數據集DataGroup上對本文提出的確定最佳聚類數和聚類效果進行驗證.DataGroup包含了10個2維的人工數據集，數據集中包含了噪聲和不同形狀、不同密度、不同程度連接的類簇，其中前5個數據集用來驗證最佳聚類數方法，后5個數據集用來驗證聚類方法，DataGroup具體描述信息如表1所示.

表1 DataGroup的基本信息Table 1 Details of DataGroup

5.1 聚類有效性評價指標

我們采用Silhouette評價指標對最佳聚類數進行驗證.Silhouette的定義如下：

(4)

在公式(4)中，db(i)表示數據點i與其它類最低平均不相似度，da(i)表示數據點i與它所在類的平均不相似度，s(i)的值介于-1到1之間，值越大，聚類效果越好.數據點x= (x1，x2，…，xn)和數據點y= (y1，y2，…，yn)之間的距離定義如公式(5)所示：

(5)

我們采用準確率(Accuracy)和標準互信息(Normalization Mutual Information，NMI)兩個評價指標對聚類結果進行評價.準確率定義如下：

(6)

在公式(6)中，TP表示正確聚類的樣本個數，Total表示總體樣本個數.標準互信息定義如下：

(7)

在公式(7)中，si和sj分別表示第i個聚類和第j個聚類的樣本個數，si，j表示第i個聚類和第j個聚類相同的樣本個數，t表示總體樣本個數.Acc和NMI的值越大，表示聚類的效果越好.

5.2 最佳聚類數分析

本節對DataGroup前5個數據集上確定最佳聚類數進行了實驗.圖1 給出了每個數據集的形態與分布(A1～E1)，以及對應的k_dist距離圖譜(A2～E2)和聚類數目決策圖(A3～E3).

在計算距離圖譜時，我們取k=7，11，15.隨著k值的增大，k_dist距離也越來越大，距離圖譜曲線變的越來越陡峭，曲線當中的拐點也越來越不明顯，不利于觀察數據集密度的變化情況.分析和觀察距離圖譜的拐點，可以選擇多個多個數據，最后確定最佳的重要數據點的數目.

聚類數目決策圖顯示了峰值的分布情況，橫坐標表示Δg值，縱坐標表示Δnng值，被框起來的點表示選取的峰值.假設一條k最近鄰鏈出現了n個峰值，通過峰值進行劃分，則k最近鄰鏈被劃分成了n+1個部分.因此，峰值數目和聚類數目的關系是：聚類數目=峰值數目+1.

對于B1，D1，E1數據集，本文方法很好地識別出類簇中的密集區域，并且密集區域間距明顯，所以聚類數目決策圖B3，D3和E3中的峰值同時具有較大的Δg值和Δnng值.對于A1數據集，存在著一個嵌套的類簇，在聚類數目決策圖A3中有一個峰值具有較大的Δnng值，而Δg值很小.C1數據集中有兩個類簇形成一個環狀，并且密集區域離的非常近，所以在C3中有一個峰值不是很明顯.

圖2給出了聚類結果對應的輪廓(Silhouette)圖.從圖中可以看出，數據集data-c-cv-nu-n、data-link2、dataX取得了比較好的聚類效果，只有少部分Silhouette的值是負數.數據集data-c-cc-nu-n中存在一個環狀嵌套的類簇，所以輪廓圖中第2個聚類有一部分Silhouette的值是負數表明與被嵌套的聚類相似度大于與本類的相似度.數據集data-uc-cc-nu-n中第1個聚類的尾部與第3個聚類的頭部的相似度要大于與本類的相似度，所以第1個聚類有一部分Silhouette值是負數.

圖2 DataGroup中前5個數據集的聚類輪廓圖Fig.2 Silhouette results of the first 5 datasets in DataGroup

5.3 聚類算法對比分析

在本節中，我們對DataGroup后5個數據集進行了2個實驗來驗證本文聚類算法的有效性.

表2 本文聚類方法與其他方法在DataGroup后5個數據集上的Acc(%)對比結果Table 2 Acc (%) results of our method and other popular methods on the last 5 datasets in DataGroup

第1個實驗，將HC算法與流行的K-means算法[15]、譜聚類算法SC[16]、密度峰值Dp算法[10]和基于影響的排序CSIP算法[12]就聚類準確率和NMI值進行了比較.表2和表3分別給出了5個聚類算法在DataGroup后5個數據集上的Acc值和NMI值.從表2和表3中可以看出，HC算法在Flame、Compound、Pathbased數據集上取得了最高的準確率和NMI值.對于Flame和Spirial兩個數據集，HC取得了100%準確率，同時NMI的值為1.在Aggregation數據集上，HC算法取得了第3好95.94%的準確率，NMI值為0.95.這是因為Aggregation數據集中有兩個類簇之間存在橋接鏈，橋接鏈上面的點很密集，距離很近，所以在采用最近距離聚類時會把橋接鏈上面的點劃分在一起，甚至會延伸到另外一個類簇.

表3 本文聚類方法與其他方法在DataGroup后5個數據集上的NMI對比結果Table 3 NMI results of our method and other popular methods on the last 5 datasets in DataGroup

第2個實驗，在Win7操作系統，6G內存，2.4GHz雙核CPU上，我們將5個算法在DataGroup2數據集上的運行時間進行了比較，結果如表4所示.從表4中可知，K-means算法在運行時間上取得了最好的性能，Dp算法僅次于K-means算法，兩個算法的運行時間在Aggregation數據集上均小于0.03秒，在其他數據集上更是少于0.01秒.HC算法的運行時間性能優于CSIP和SC算法.HC算法在Aggregation數據集上運行時間少于0.2秒，在其他數據集上的運行時間不足0.05秒.SC算法在每個數據集上的運行時間相對穩定，在0.3秒到0.4秒之間.相對其他算法，CSIP算法在Aggregation數據集上運行時間最長為0.6秒.

表4 本文聚類方法與其他方法在DataGroup后5個數據集上的運行時間(s)對比結果Table 4 Runtime(s) results of our method and other popular methods on the last 5 datasets in DataGroup

6 總 結

確定最佳聚類數目是聚類分析研究的一個基礎問題.針對復雜結構數據集，本文提出了一種啟發式確定最佳聚類數的方法.其中，k-最近鄰鏈間距曲線能夠描述類間的距離變化，k-最近鄰鏈最近鄰間距曲線能夠反映類內的聚類變化.理論分析和實驗結果表明，本文方法對具有密集區域并且被稀疏區域分離的數據，對流行、不規則形狀分布的數據比較有效，能夠快速準確地找到最佳聚類個數.與目前流行的聚類算法相比，本文聚類算法取得了較好的結果，在處理速度方面也具有明顯的優勢.