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

邱保志，辛 杭

鄭州大學(xué) 信息工程學(xué)院，鄭州 450001

1 引言

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

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

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

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

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

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

2 相關(guān)定義

D表示數(shù)據(jù)集，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距離越小，表明對象周圍近鄰分布的就越密集，對象就越有可能分布在稠密區(qū)域，反之則越有可能分布在稀疏區(qū)域。

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

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

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

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

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

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

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

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

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

3 算法描述

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

SNNA算法

Input：D,k//D表示原始數(shù)據(jù)集，k表示近鄰數(shù)

Output：Result//Result表示最終的聚類結(jié)果

2.for each x∈D do

3. Find Nk(x)

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

14.Assign the rest objects to their nearest CoreCluster

15.Result←CoreCluster

4 實驗結(jié)果與分析

實驗環(huán)境為：Intel Core i3-2130 CPU 3.4 GHz，內(nèi)存4 GB，操作系統(tǒng)Microsoft Windows 7，算法編寫環(huán)境為MATLAB R2014a。

4.1 實驗數(shù)據(jù)

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

表1 數(shù)據(jù)集基本信息

4.2 參數(shù)設(shè)置與時間復(fù)雜度

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

圖1 SNNA算法中，k值與準(zhǔn)確率的關(guān)系

4.3 聚類結(jié)果分析

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

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

圖2 二維數(shù)據(jù)集的聚類結(jié)果

表2 各算法在各數(shù)據(jù)集的聚類結(jié)果

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

5 結(jié)論

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