一種基于共享近鄰親和度的聚類算法

邱保志，辛 杭

鄭州大學 信息工程學院，鄭州 450001

1 引言

聚類是將給定的數據集劃分成互不相交的非空子集，其中，每個子集代表一個類，同一類中的數據對象具有較高的相似性，而不同類中的數據對象高度不相似。目前人們已經提出了許多聚類算法，其中基于密度的聚類算法是通過尋找密度足夠大的連通區域形成聚類，這類算法具有發現任意形狀的聚類且對噪聲不敏感的特點，所以在模式識別、機器學習、信息處理等諸多領域都具有廣泛的應用。

基于密度的聚類算法以數據集在空間分布上的稠密程度為依據進行聚類，將簇看作是數據空間中被低密度區域分割開的高密度區域。DBSCAN[1]是一種經典的密度聚類算法，該算法將密度定義為給定半徑鄰域內對象的個數，密度大于給定閾值的對象被標識為核心點，然后對核心點進行密度可達聚類。然而隨著維度的增加，對象分布將變得非常稀疏，這時，基于鄰域度量密度的方式將失去度量意義。

基于密度的聚類算法DPC[2]中，密度被定義為與對象距離小于給定閾值的對象個數，據此將聚類的中心點定義為局部密度最高，且全局范圍內與密度更高的中心點的距離較大。在準確識別聚類中心點后，按照最近鄰分類完成對整個數據集的聚類。DPC算法在處理低維數據集時能夠準確地識別聚類中心并得到較好的聚類結果，但是對高維數據集聚類準確度不高。

CLUB[3]算法引入了k近鄰的概念，將對象的密度定義為與k個近鄰的平均距離的倒數，利用與近鄰對象的平均距離來度量局部分布特征，平均距離越小，表明對象局部分布的越緊密，對象就越有可能分布在稠密區域。該度量方式使得算法能夠較好地處理多密度和任意形狀的數據集，但是處理高維數據集時聚類準確度仍然不高。

共享近鄰[4-5]采用對象間共享近鄰的多少確定對象之間的相似性，對象間的共享近鄰越多，這兩個對象就越靠近，其相似性就越大，說明它們屬于同一類的可能性越大；反之，對象間的共享近鄰越少，這兩個對象分布就越稀疏，其屬于同一類的可能性就越小。

為了準確地度量對象的局部密度且使密度度量能適用于高維空間聚類[6-10]，本文引入k近鄰和共享近鄰技術，提出一種基于共享近鄰親和度的聚類算法。k近鄰可以準確反映空間中對象的局部分布特征，共享近鄰用于度量空間中對象間的相似度。利用k近鄰和共享近鄰定義共享近鄰親和度，以共享親和度作為密度度量方式提取核心點，然后使用廣度優先搜索算法對核心點進行密度可達聚類，最后將非核心點指派到距離最近的點所屬聚類中[11]，即完成整個數據集的聚類。

2 相關定義

D表示數據集，dist(x,y)表示對象x和y的歐式距離。

定義1（k近鄰空間）對 p∈D,p的k近鄰空間是距離 p最近的k個點的集合，記作Nk(p)：定義2（knn距離）對 p∈D,p的knn距離是與k個近鄰的距離的平均值，記作distknn(p)：

knn距離反映了對象的局部分布情況，knn距離越小，表明對象周圍近鄰分布的就越密集，對象就越有可能分布在稠密區域，反之則越有可能分布在稀疏區域。

對 p,q∈D,p與q的共享近鄰是指 p與q的k近鄰空間的交集元素，交集元素反映了對象間的相似程度，交集元素越多，表明兩個對象在空間中分布的越靠近，其相似性就越大。

定義3（共享近鄰數）對 p∈D,p的共享近鄰數是指 p與其k個近鄰的共享近鄰元素的總個數，記作Snn(p)：

定義4（Snn親和度）親和度表示一個對象與其他對象之間的親和程度，一個對象的共享近鄰親和度定義為該對象的共享近鄰數與knn距離的比值。記作Affinitysnn(p)：

對象的共享近鄰數越多，knn距離越小，Snn親和度就越大，表明對象與近鄰的親和程度就越大，對象局部空間分布就越緊湊，即反映該對象的局部密度就越大。反之，局部密度就越小。

定義5（核心點）對 p∈D，若 p為核心點，則其需要滿足以下條件：

即核心點的Snn親和度不小于k個近鄰點的Snn親和度的平均值。

定義6（密度直接可達）若為核心點，如果兩個對象滿足：，即兩個核心對象的k近鄰空間存在交集元素，則稱核心對象 p和q是密度直接可達的。

選取親和度足夠大的點作為核心點，核心點分布在數據空間的稠密區域，通過對核心點進行密度直接可達聚類，將數據空間中高密度區域連接起來形成聚類的骨架，然后將非核心點劃歸到距離最近的高密度點所屬聚類中，即完成整個數據集的聚類。

k近鄰方法選取空間中距離對象最近的k個近鄰來反映其局部分布特征，適用于描述高維空間中對象的分布特征，共享近鄰適用于任意維度空間對象的相似性度量[12-15]，因此本文基于k近鄰和共享近鄰定義親和度作為新的密度度量方式，同樣也適用于高維空間的聚類處理。

3 算法描述

算法首先尋找每個對象的k近鄰集，據此計算對象的knn距離和共享近鄰數，然后計算共享近鄰親和度并提取核心點，利用廣度優先搜索算法將滿足密度直接可達的核心點進行聚類，最后對剩余點進行指派即完成整個數據集的聚類。算法偽代碼如下：

SNNA算法

Input：D,k//D表示原始數據集，k表示近鄰數

Output：Result//Result表示最終的聚類結果

2.for each x∈D do

3. Find Nk(x)

13.CoreClust←BFS(Core,Nk(x))//使用廣度優先搜索算法對核心點進行聚類

14.Assign the rest objects to their nearest CoreCluster

15.Result←CoreCluster

4 實驗結果與分析

實驗環境為：Intel Core i3-2130 CPU 3.4 GHz，內存4 GB，操作系統Microsoft Windows 7，算法編寫環境為MATLAB R2014a。

4.1 實驗數據

實驗選取了10個數據集來驗證本文算法對于聚類任務的有效性，數據集的維度從二維到萬維不等，這些數據集可廣泛代表數據的各種分布。數據集詳細信息如表1所示。二維數據集含有多種不同的分布，Flame數據集包含兩個形狀不規則的聚類，且兩個聚類間呈現半包圍的環繞分布，用以測試算法能否準確的識別距離較近的兩個聚類；Compound數據集共有6個密度分布不均勻的聚類，且聚類之間存在嵌套分布，用以測試算法能否準確識別多密度聚類和嵌套的聚類；R15數據集共包含15個大小、形狀均不相同的聚類，用以測試算法能否準確識別多個聚類；Aggregation數據集共包含7個大小形狀均不相同的聚類，且聚類之間存在干擾的橋接線，用以測試算法能否準確識別多密度聚類和存在橋接干擾線的聚類；其他6個數據集為高維分類數據集，用來測試算法能否在高維空間中準確聚類。

表1 數據集基本信息

4.2 參數設置與時間復雜度

本算法只需設置一個參數，即近鄰數k。算法在處理二維數據集時準確率與參數k的關系如圖1所示，從圖中發現當k在[5，15]取值時通常能得到較好的聚類結果。相比DBSCAN算法和DPC算法，本文算法的參數易于確定。SNNA算法需要根據k近鄰和共享近鄰來計算親和度，算法的時間消耗主要在于計算k近鄰集合，時間復雜度為O(k?n2)，若采用R*-tree空間索引進行優化，時間復雜度可降低為O(k?n?lbn)。

圖1 SNNA算法中，k值與準確率的關系

4.3 聚類結果分析

本算法在各二維數據集上的核心點提取和聚類結果如圖2所示，從圖中可以看出，算法在二維數據集上總能正確識別聚類的個數并得到較好的聚類結果，從而驗證了算法在二維數據集上的有效性。

各算法在實驗數據集上的參數設置和聚類結果如表2所示，采用準確率（Accuracy）和調整蘭德系數（ARI）來評價各聚類算法的執行結果，具體描述如下。其中，準確率為正確分類的對象數與識別出的對象總數的比值，其值在[0，1]區間，值越大意味著正確分類的對象越多；調整蘭德系數（ARI）是蘭德系數（RI）的改進形式，ARI的值在[-1,1]區間，值越大意味著聚類結果與真實情況越吻合。

圖2 二維數據集的聚類結果

表2 各算法在各數據集的聚類結果

從表2中可以看出，與其他算法相比，SNNA算法在處理二維數據集時可以得到更高或相近的準確率和ARI值。對于Compound數據集，由于該數據集右側呈現嵌套分布，數據分布稀疏，參數k的取值范圍較小，因此未能對此簇完全聚類，從而導致本算法在處理該數據集時準確率要稍低于CLUB算法，但是仍然能夠準確識別出聚類個數，且準確率高于DBSCAN和DPC算法。對于高維度數據集，SNNA算法同樣能夠得到較好的聚類結果，與其他三個算法相比，SNNA算法在各數據集均能得到較高的聚類準確率，并且在Sonar和Facedata數據集上得到了遠高于其他算法的準確率，同時本算法也取得了較高或相近的ARI值，從而驗證了本算法在處理高維數據集時的有效性和準確性。

5 結論

本文引入k近鄰和共享近鄰，提出了一種基于共享近鄰親和度的聚類算法，定義共享近鄰親和度作為密度度量，算法保留了密度聚類算法在處理多密度數據集時的優點，同時適用于高維空間的聚類，從而更好地處理高維度數據集。該算法簡單、易于理解，僅需要輸入一個近鄰參數k，能夠很好地處理多密度數據集和高維度數據集。然而算法在處理大數據集時會面臨運行時間過長的問題，如何進一步提高算法的執行效率以及處理高維度大數據集將是下一步的研究方向。