反向近鄰構造連通圖的聚類算法

龍建武，王 強

重慶理工大學 計算機科學與工程學院，重慶 400054

聚類[1]，作為最常用的無監督學習方法，在數據挖掘與機器學習領域具有廣泛的研究和應用。聚類算法的目的是利用簇內數據具有較高的相似度，簇間數據相似度較低的特性將數據集按照某種方式劃分成不同的類別[2]。隨著人工智能時代的發展，聚類的應用場景越來越廣泛，包括數據挖掘[3]、人工智能[4]、文檔聚類[5]、模式識別[6]、社交網絡[7]和圖像分割[8]等領域。目前已經提出了許多應用廣泛的聚類算法，根據算法實現方式的不同可以分為：基于劃分的方法[9-11]、基于密度的方法[12-15]、基于分層的方法[16-17]、基于圖的方法[18-20]等。不同類型的算法各有其特點和應用場景。

K-means 算法[9,21-22]是最典型的基于劃分的聚類算法，該算法在初始化聚類中心后，多次迭代將點劃分到對應聚類中心所在的簇中。該算法思想簡單，但它無法擬合非凸數據以及對噪聲數據敏感。Kmeans算法屬于硬劃分算法，即對于數據集中的每個點，只能將其劃分到一個簇中。此外，還有一種軟劃分算法，如FCM（fuzzy C-means clustering algorithm）[23]，該算法認為數據集中的點相對于每個簇都有一個隸屬度，一個點屬于不同簇的隸屬度之和為1。FCM算法同樣具有劃分聚類算法的缺陷，即需要初始化聚類中心且無法擬合非凸數據集。

典型的基于密度的算法是DBSCAN（density based spatial clustering of applications with noise）算法[24]，它將數據定義為由稀疏區域分隔開的密集區域，通過設定兩個參數鄰域半徑Eps和密度閾值MinPts進行聚類。孫璐等人[25]提出融合網格劃分和DBSCAN的改進聚類算法，采用網格劃分技術劃分稀疏和密集區域，降低復雜度。Rodriguez等人[26]提出了DPC（clustering by fast search and find of density peaks）算法，通過構造決策圖初始化局部密度最大值的點作為聚類中心，再將其他點分配到距離其最近且密度比其更大的聚類中心所在的類中，但該算法無法擬合非凸形狀的簇。劉娟等人[15]提出了采用反向最近鄰計算出的局部密度和密度自適應距離構建決策圖進行聚類的密度峰值聚類算法。

譜聚類算法[19-20]是基于圖的聚類算法。該算法利用圖論的基礎將數據聚類問題轉化為圖劃分問題，其往往具有較高的時間復雜度。Huang等人[27]提出一種可伸縮譜聚類（ultra-scalable spectral clustering，USPEC）算法，通過混合代表選擇策略和k近鄰快速逼近的方式構造稀疏親和子矩陣，然后將稀疏子矩陣解釋成二部圖，對圖通過有效的分割進行聚類，但是其隨機選擇候選代表的方式使得算法穩定性較差。Li等人[28]提出基于圖的CutPC（cut point clustering algorithm）算法，通過對去噪后的數據構造自然鄰接圖進行聚類，但是該算法無法識別部分無噪數據。

針對上述聚類算法不能很好地擬合非凸數據集以及對噪聲敏感的缺陷，提出一種反向近鄰構造連通圖的聚類算法。首先，考慮到噪點對聚類的影響，利用自然鄰居搜索達到穩定狀態時的反向鄰居最大值設計一種密度公式計算點的密度，為有效去噪，利用密度均值和標準差函數設計一種動態的噪聲判別器，利用該判別器有效識別噪點，對數據進行去噪；其次，根據“距離越近的點具有越強的相關性”這一特點設計一種通過去噪后數據點的反向鄰居數作為限制條件構造反向近鄰連通圖進行聚類的方法得到初步聚類結果，并根據給定的聚類數合并初始簇得到無噪數據的聚類結果；最后，對噪點劃分聚類得到最終的聚類結果。

1 自然鄰居

自然鄰居的概念首次由Zhu 等人[29-30]提出，其目的是為了解決數據點最近鄰范圍內的參數選擇問題，其思想來源于現實社會中人類之間的友誼，自然社會中，一個人真正擁有多少朋友取決于有多少人把他當作朋友。自然鄰居的搜索過程是通過不斷地擴大搜索范圍尋找數據點反向鄰居的過程。基于自然鄰居的思想，數據點越密集的地方擁有的反向鄰居越多，越稀疏的地方擁有的反向鄰居越少。

定義1（k近鄰）對于數據集D中的一點a，若點b是其第k個最近鄰居，則點a的k近鄰定義為：

其中，dist(a,b)表示數據點a和b之間的歐式距離。

定義2（反向鄰居）對于數據集D中的一個點a，其反向鄰居定義如下：

其中，d是D中的一個點，點a是點d的k近鄰，點a的反向鄰居為D中一組點d的集合。

定義3（自然特征值λ）自然鄰居搜索過程是被動查找所有數據點反向鄰居的過程。當滿足以下兩個條件之一時，自然鄰居搜索達到穩定狀態：（1）自然鄰居搜索范圍由k=1 到n逐漸擴大的過程中，若在連續兩次迭代過程中，擁有反向鄰居的數據點的個數保持不變；（2）數據集D中的任意一個點都擁有反向鄰居。若滿足上述兩個條件中的任意一個，則自然鄰居搜索停止，此時的狀態定義為自然鄰居穩定狀態。自然鄰居搜索達到穩定狀態時的k值定義為自然特征值λ，具體如下：

其中，k初始化為1，后續逐漸遞增，直至自然鄰居搜索達到穩定狀態。nbk(xi)是數據集D中的點xi第k次迭代時的反向鄰居數量，函數f(x)用來統計D中擁有反向鄰居的點的個數，定義如下：

自然鄰居搜索過程的算法如算法1所示，自然鄰居搜索達到穩定狀態時的自然特征值能夠克服傳統的KNN 算法k值選取不合理的情況，在數據挖掘和聚類分析領域具有良好的性能。

算法1自然鄰居搜索過程

2 提出的方法

由于目前的許多聚類方法在非凸數據集上的聚類效果較差，而現有的基于圖的方法如譜聚類算法常常具有較高的時間復雜度，因而限制了其在聚類分析領域的應用。本文通過對自然鄰居思想的理解，發現自然鄰居搜索過程是不斷擴大搜索范圍尋找數據點反向鄰居的過程，考慮到核心區域的點擁有較多的反向鄰居，而邊緣區域的點擁有的反向鄰居較少或為0，提出一種反向近鄰構造連通圖的聚類算法。通過對去噪后數據構造反向近鄰連通圖來識別數據結構特征，進行聚類。構造反向近鄰連通圖進行聚類的方式只需考慮數據點與周圍一定范圍內的其他點之間的聯系，具有較高的計算效率。

算法分為三部分：首先，利用自然鄰居搜索達到穩定狀態時所有數據點的反向鄰居數最大值設計密度公式計算點的密度，并構建一種動態的噪聲判別器利用給定的噪聲參數計算出合適的噪聲閾值進行去噪。然后，提出一種反向近鄰構造連通圖進行聚類的方法，利用自然鄰居搜索達到穩定狀態時數據點的反向鄰居數作為限制條件構造反向近鄰連通圖，記錄構圖完成時的極大連通子圖個數，得到初步聚類結果，并通過給定的聚類數對得到的初步聚類結果按照簇間距離從小到大合并聚類。最后，對噪點劃分聚類，得到最終的聚類結果。

2.1 反向密度去噪

聚類數據中，大部分數據集都包含噪點，這也導致很多對噪點比較敏感的聚類方法如K-means 算法的聚類效果較差。為解決這個問題，必須采用合適的方法識別噪聲數據。

傳統的聚類算法如DPC 算法[26]采用的是ε近鄰的方式來計算密度，通常有兩種計算方式：第一種采用的是計算截斷距離dc范圍內數據點的個數作為點的密度，但這種計算方式得出的密度是離散值，通常無法取得較好的聚類效果，并且由于數據分布的多樣性，難以人為給出合理的截斷距離dc值。另一種方式采用高斯核函數計算密度，雖然能夠保證計算得到連續的密度值，但是這種密度計算方式仍然沒有解決截斷距離dc難以給定的缺陷。

由于稠密區域比稀疏區域點的密度更大，具有自適應性特點的k近鄰方式相比難以確定合適取值的ε近鄰更具優勢。基于上述觀點，使用數據點k近鄰方式相比ε近鄰計算密度的效果更好。傳統的k近鄰方式通常需要人為給定k值，而數據的復雜多樣性又導致往往難以給定合理的k取值，因此，使用一種能夠針對不同數據集自動確定k取值的方式計算密度就顯得尤為重要。

本文通過觀察，發現聚類數據具備以下特點：“位于稀疏區域的點具有較小的密度，位于稠密區域點的密度較大”。根據數據的這一特點利用自然鄰居搜索停止時的反向鄰居數設計密度公式計算點的密度信息，然后構建一種動態的噪聲識別器利用噪聲參數計算合適的噪聲閾值對數據集進行去噪。

定義4（反向密度）對于D中的點a，其反向密度計算方式定義如下：

其中，μ為自然鄰居搜索達到穩定狀態的反向鄰居數最大值，定義如下：

λ為該狀態下的自然特征值。nbλ(D)表示該狀態下所有點的反向鄰居數。

本文采取的密度計算方式，對自然鄰居搜索達到穩定狀態時的反向鄰居數最大值μ以及μ近鄰的歐式距離之和的比值取對數來計算數據的密度。由于不同數據集自然鄰居搜索達到穩定狀態時的反向鄰居數最大值并不相同，因此本文的密度計算方式能夠針對不同數據集得到不同的反向鄰居數最大值，從而避免人工選擇k值不合理的缺陷。

通過式（5）計算出數據的密度后，觀察噪點數據與非噪點數據之間的密度差異，利用密度均值和標準差構造一種動態的噪聲判別器，根據提供的噪聲參數計算出噪聲密度閾值，識別噪點，對數據集進行去噪。

定義5（噪聲判別器）對于D中的點a，若點a屬于噪點，則點a需要滿足的條件定義為：

其中，τ(β)是噪聲密度閾值，定義如下：

利用式（8），將數據集中所有密度小于τ(β)的點均識別為噪點。mean(ρ(D))表示數據集D的密度均值，Φ-1(?)表示標準正態分布的分位數函數，β表示噪聲參數，由人工根據數據集的含噪情況給定，β∈[0,1)，σ(?)表示標準差函數。數據集的噪點越多，識別噪點的噪聲閾值τ(β)就越大，因而需要給定較大的噪聲參數β。

由于不同數據集的噪點含量并不相同，有些數據集含噪較多，也有些數據集含噪點較少或者不包含噪點。基于這種情況，設計一種能夠根據數據集含噪程度調節噪聲參數控制去噪比例的噪聲識別器就顯得尤為重要。本文式（8）中的噪聲判別器，通過密度均值獲得數據點密度的總體分布，然后利用噪聲參數β來調節判別器識別出的噪點數量。上述條件使得噪聲判別器針對不同噪點含量的數據集都能達到較好的去噪效果，因此能夠適應于各種類型的含噪數據集，解決噪點對聚類過程的影響。

通過上述的噪聲判別器設置合適的噪聲參數對數據集進行去噪，去噪過程如算法2 所示，去噪后的數據集能很好地保留點之間的結構信息，便于后續進行聚類。例如對于圖1中的數據集，該數據集共有1 532 個樣本，利用式（8）設置噪聲參數為0.12，識別噪點，對數據集進行去噪。該圖中紅色點表示去噪后保留的數據，灰色點表示噪點，經過去噪后的數據集簇內與簇間的結構信息明顯地體現出來。接下來，將去噪后的數據利用2.2節中提出的方法進行聚類。

圖1 去噪后的數據可視化效果圖Fig.1 Data visualization after denoising

算法2反向密度去噪算法

2.2 反向鄰居構圖劃分聚類

對數據集去噪后，能夠得到比較干凈的數據。接下來，對得到的數據利用自然鄰居搜索過程尋找每個點的反向鄰居。由于點的密度各不相同，位于核心區域的點擁有較多的反向鄰居，位于邊緣的點擁有的反向鄰居數目較少，甚至沒有反向鄰居。例如對于圖2中的數據集，將自然鄰居搜索過程應用在該數據集上，得到每個點的反向鄰居。該數據集在自然鄰居搜索達到穩定狀態時的自然特征值λ=8，其中點p位于數據集的核心區域，自然鄰居搜索停止時該點擁有的反向鄰居數為13，而對于點q，由于其位于邊緣區域，自然鄰居搜索停止時該點僅擁有1個反向鄰居。接下來，利用點的反向鄰居數作為限制條件構造反向近鄰連通圖劃分聚類。

圖2 點p 和q 的反向鄰居（點p 和q 的反向鄰居數分別為13和1）Fig.2 Reverse neighbors of point p and q(The number of reverse neighbors of points p and q are 13 and 1,respectively)

定義6（反向近鄰連通圖）對于D*中的一個點d，通過自然鄰居搜索得到d的反向鄰居數目為nb[d]，將點d與其周圍nb[d]個近鄰的數據點進行連接構造的連通圖。

由于不同數據點的反向鄰居數各不相同，核心位置的點具有更多的反向鄰居，它與周圍點之間的聯系更密切，而邊緣位置的點具有的反向鄰居數較少，這也使得它只與自身周圍少部分點之間存在聯系。基于這種結論，設計一種反向近鄰構造連通圖的聚類算法，利用點的反向鄰居數作為限制條件構造連通圖。反向近鄰構圖與傳統的k近鄰構圖有著明顯的區別，傳統的k近鄰方式進行構圖，數據集中的每個點均需要與其最近的k個鄰居相連，而反向近鄰連通圖是對傳統k近鄰方式構圖的一種改進，它利用數據點的反向鄰居數作為構造k近鄰圖k取值的限制條件，也就是說，對于不同的點，在構造反向近鄰連通圖時所選擇的近鄰個數是不相同的。位于核心區域的數據點構造反向近鄰連通圖時選擇的近鄰個數較多，位于邊緣區域的數據點構造反向近鄰連通圖時選擇的近鄰個數較少甚至為0。傳統k近鄰方式構圖時對所有點取相同的k值容易導致將本不屬于同一個聚類的邊緣點進行連接，影響聚類效果，而利用反向鄰居數作為限制條件構造連通圖能夠有效避免k近鄰方式構圖的缺陷，聚類效果更好。對于去噪后數據集利用反向近鄰構圖劃分聚類的具體算法流程可描述如下：

（1）利用自然鄰居搜索的方式尋找去噪后數據集D*的反向鄰居數，記錄為nb[D*]。

（2）對D*中的每個數據點構造反向近鄰連通圖，具體方式為：對于D*中的一點d，利用KNN算法對k取值從1 開始，若點d的反向鄰居數目nb[d]大于等于k，就將點d與其周圍的k近鄰范圍內的點連接起來，若nb[d]小于k，則不進行連接，隨后對k進行加1操作。不斷重復該過程，直到k達到所有數據點反向鄰居數最大值max(nb[D*])時停止。

（3）統計（2）所得結果中的極大連通子圖的個數（number of maximal connected subgraphs，NMCS）得到初步的聚類結果。

（4）利用給定的聚類數將上述得到的簇合并成對應聚類數的聚類結果。

在構造反向近鄰連通圖時，針對不同數據點構圖時選取的近鄰個數不同。對于數據集D*中的一個點d，取其nb[d]個近鄰的數據點構造反向近鄰連通圖，其中nb[d]表示自然鄰居搜索達到穩定狀態時點d的反向鄰居個數。當所有數據點構造反向近鄰連通圖完成時算法停止，統計此時的極大連通子圖的個數，得到初步的聚類結果。例如對于圖2中的數據集，自然鄰居搜索達到穩定狀態時該數據集中所有數據點的反向鄰居數最大值為15，將每個數據點的反向鄰居數作為構造k近鄰連通圖對應該點k取值的限制條件，利用KNN算法對于k取[1,15]之間的所有整數時，不同k值得到的極大連通子圖的數量（NMCS）變化情況如圖3（a）～（g）所示。根據圖3（g）中的結果，得到反向近鄰構圖完成時的極大連通子圖數量為3，因此利用反向近鄰構圖劃分聚類得到初始聚類數為3。根據初步的聚類結果發現，利用反向近鄰連通圖進行聚類的過程已經識別出該無噪數據集的基本結構。

圖3 不同k 值的NMCS變化情況Fig.3 Change of NMCS for different values of k

利用反向近鄰構圖劃分聚類的過程中可能會產生部分小簇或者孤立點，針對這種情況，根據設定好的聚類數對初始聚類結果進行合并，依次選擇簇間距離最近的兩個簇合并，直到達到設定的聚類數為止。對于圖2中的數據集，其真實聚類數為2，通過構造反向近鄰連通圖得到的初始聚類結果包含3個簇，利用給定的聚類數依次合并簇間距離最近的簇后得到的聚類結果如圖3（h）所示。利用反向近鄰構造連通圖劃分聚類的具體算法如算法3所示。

算法3反向近鄰構造連通圖劃分聚類

2.3 噪點劃分聚類

通過構造反向近鄰連通圖劃分聚類得到去噪后數據的聚類結果后，將去掉的噪點劃分到對應的聚類中，在劃分噪點時，考慮到噪點分布在簇間的范圍比較廣，單純將其分配到距離最近的簇所在的類別中可能導致劃分不準確，影響聚類結果。因此，考慮數據的密度信息，將噪點分配規則定義如下：

噪點劃分規則（noise division rules，NDR）：針對噪點數據，將其劃分到距離其最近的非噪點所在的類別中，同時要求該非噪點的密度大于當前待分配的噪點。

通過將密度信息考慮到噪點劃分中，可使得噪點劃分的結果更準確，最終的聚類效果更好，噪點劃分聚類的原理如算法4所示。

算法4噪點劃分聚類

2.4 時間復雜度

對于提出算法，假設數據集有n個對象，經過構建KD 樹后自然鄰居搜索過程時間復雜度為O(nlgn)，去噪過程需要判斷每個點是否為噪點，時間復雜度為O(n)，構造反向近鄰連通圖時對每個點與其最近的nb[d]點進行連接，時間復雜度為O(nlgn)，噪點劃分聚類時需要尋找每個點周圍距離最近的高密度點，時間復雜度為O(nlgn)。因此，本文算法的時間復雜度為O(nlgn)。

3 實驗

為驗證提出方法的有效性，在9個合成數據集和5個真實數據集上進行實驗，并將本文方法與其他聚類算法在上述數據集上的聚類結果進行對比。合成數據集來自文獻[28]（https://github.com/lintao6/CutPC/tree/master/datasets），真實數據集來自UCI官網（https://archive.ics.uci.edu/ml/index.php）。實驗中將所有的數據集進行標準化處理，對比算法包括K-means算法[9]、DBSCAN 算 法[24]、DPC 算 法[26]、USPEC 算 法[27]以 及CutPC算法[28]。

聚類評價指標通常被用來衡量聚類結果的質量，一般來說，聚類評價指標分為兩種：內部評價指標和外部評價指標。內部評價指標利用簇的內部結構信息設計不同的內部評價標準對聚類結果的優劣進行評判，而外部評價指標通常需引入外部信息來評價聚類效果，如聚類的真實標簽。常用的外部評價指標有聚類精度（cluster accuracy，Acc）、標準化互信息（normalized mutual information，NMI）等，實驗中采用上述兩種外部評價指標對聚類結果進行評價，以評估提出方法的有效性。

3.1 外部評價指標

聚類精度（Acc）是最常用的聚類外部評價指標之一，它是利用映射后的預測標簽與真實聚類標簽的差異性對聚類效果進行評估。聚類精度能夠直觀地評價聚類結果的準確率，得到聚類結果正確數據的比例。具體計算方式定義如下：

其中，n為數據樣本個數，ti和pi分別代表真實的聚類標簽和預測的聚類標簽，map(?)是一個映射函數，作為預測標簽和真實標簽的映射，用來解決聚類過程中預測標簽和真實標簽不匹配的問題，采用匈牙利算法實現。δ(a,b)定義為：

Acc∈[0,1]，Acc的值越大，聚類效果越好。

另一個評價聚類效果的外部指標是標準化互信息（NMI），該指標是評估聚類算法優劣的一個常用的指標，計算方式定義為：

其中，X和Y分別代表真實聚類標簽和預測標簽的集合，I(X,Y)表示兩個隨機變量X和Y之間的互信息，H(?)表示隨機變量的熵，NMI 指標的取值范圍為[0,1]。NMI 指標利用信息論來量化聚類分區的差異，NMI的值越大，聚類的效果越好。

3.2 合成數據集實驗

實驗中選擇9 個合成數據集來驗證提出方法的有效性，9 個合成數據集均包含部分噪點。將5 種對比算法和本文方法應用在合成數據集上進行聚類，對比聚類結果。9個合成數據集的基本信息如表1所示。

表1 9個合成數據集的基本信息Table 1 Basic information of 9 synthetic datasets

由于9個合成數據集均包含部分噪點，需利用提出的去噪方式對數據集進行去噪，去噪后的數據能夠體現出簇的結構信息。對9 個合成數據集設置的噪聲參數如表2 所示。對于數據集D7，其包含噪點較多，故設置噪聲參數為0.18，其他8 個合成數據集設置噪聲參數為0.12。去噪前后的數據集可視化效果圖如圖4所示。觀察發現，去噪后的數據集接近理想數據集。為展示提出算法的有效性，實驗中與其他5 個算法的聚類效果進行對比，5 種對比算法在9個合成數據集上的參數如表2 所示。其中DBSCAN算法對參數非常敏感，調參過程比較復雜，為得到較好的聚類結果需要對參數精心選取。

表2 不同聚類算法在9個合成數據集上的參數Table 2 Parameters of different clustering algorithms on 9 synthetic datasets

圖4 9個合成數據集去噪后的數據可視化效果Fig.4 Data visualization after denoising of 9 synthetic datasets

對9個合成數據集去噪后，利用去噪后的數據構造反向近鄰連通圖進行聚類，通過反向近鄰連通圖得到初步聚類結果后，再根據輸入的聚類數將部分較小簇或者孤立點合并，得到去噪后數據對應于給定聚類數的聚類結果，最后對噪點數據劃分聚類，得到最終的聚類結果。本文方法在9 個合成數據集上應用后得到的聚類結果可視化效果圖如圖5 所示。通過觀察發現，本文方法在9個合成數據集上均能夠準確地區分出不同的簇，聚類效果較好。

圖5 數據集D1～D9的最終聚類結果Fig.5 Final clustering results of datasets D1 to D9

此外，將本文方法應用在上述9個合成數據集上的聚類效果和其他5種聚類方法進行對比，并采用Kmeans、DBSCAN、DPC、USPEC、CutPC 共5 種聚類算法作為對比方法進行實驗。其中K-means 算法是基于分區的聚類算法，該算法通常無法較好地劃分非凸數據集，并且對噪聲數據比較敏感。DBSCAN 算法是基于密度的算法，通過對鄰域半徑Eps和密度閾值MinPts的多次調參進行聚類，但是其往往會因為數據密度不均勻導致聚類效果較差。DPC算法通過計算數據點的密度以及到高密度點的最小距離構造決策圖尋找聚類中心進行聚類，但是其同K-means算法一樣對非凸數據集擬合較差。USPEC算法在選擇候選代表時使用了隨機選擇策略，因此會導致聚類效果具有隨機性，算法穩定性較差。CutPC算法是基于圖的方法，但是其只對于特定噪聲范圍內的數據集有效，無法識別部分無噪數據集。相比而言，本文方法能夠避免上述五種對比方法的缺陷，對9個合成數據集的聚類效果較好。

為了更直觀地描述本文方法相對其他幾種對比算法的優勢，實驗中采用了外部評價指標聚類精度（Acc）和標準化互信息（NMI）進行聚類效果的評判，6種算法應用在9個合成數據集上的Acc和NMI指標如表3所示。

表3 6種方法應用在9個合成數據集上的Acc和NMITable 3 Acc and NMI of 6 methods applied on 9 synthetic datasets

通過6 種聚類方法在合成數據集上的聚類效果對比，采用聚類精度（Acc）和標準化互信息（NMI）作為驗證指標進行聚類效果的驗證后發現，其他五種聚類算法由于各自存在的缺陷，無法達到較優的結果，而本文方法先對數據集去噪后，對不包含噪點的數據集進行聚類能夠準確識別非凸形狀數據集的內部結構信息，在9 個合成數據集上均具有較好的聚類效果。

表4展示了6種聚類算法在9個合成數據集上的運行時間。通過對比發現，本文算法在9個合成數據集上的運行時間相比K-means 算法以及DBSCAN 算法的運行時間稍長，在數據量較小的時候，本文算法的運行時間相比DPC 算法和USPEC 算法具有明顯的優勢，而在數據量較大的時候，例如對于數據集D9，本文算法的運行時間高于USPEC 算法，但依舊低于DPC算法。此外，不論數據量的大小，本文算法都遠低于CutPC算法的運行時間。綜上得出，本文方法不僅能在9 個合成數據集上具有比較好的聚類效果，同時還能擁有較快的計算速度。

表4 6種方法應用在9個合成數據集上的運行時間Table 4 Runtime of 6 methods applied on 9 synthetic datasets 單位：s

3.3 真實數據集實驗

另外，實驗中還將本文方法應用在真實數據上，利用UCI 提供的真實數據集進行本文方法的實驗。實驗過程中將6 種聚類算法應用在5 個真實數據集上的聚類效果進行對比，5個真實數據集分別為iris、cancer、seeds、banknote 和heart，5 個真實數據集的基本信息如表5所示。

表5 5個真實數據集的基本信息Table 5 Basic information of 5 real datasets

實驗中將本文方法和5 個對比算法應用在5 個真實數據集上，不同方法對應5種真實數據集的參數設置如表6所示。和合成數據集一樣，仍然采用聚類精度（Acc）和標準化互信息（NMI）兩種聚類評價指標進行聚類效果的評估。6 種算法應用在真實數據集上的Acc和NMI指標如表7所示。

表6 6種方法應用在5個真實數據集上的參數Table 6 Parameters of 6 methods applied on 5 real datasets

表7 6種方法應用在5個真實數據集上的Acc和NMITable 7 Acc and NMI of 6 methods applied on 5 real datasets

通過將本文方法與其他5 種對比算法在5 個真實數據集上進行實驗得到的聚類精度（Acc）和標準化互信息（NMI）指標結果表明，對于iris 數據集，USPEC算法在兩種聚類指標上優于其他5種方法，而對于cancer、seeds、banknote和heart數據集，本文方法的聚類精度（Acc）和標準化互信息（NMI）指標均優于其他5 種對比方法。另外對于iris 數據集，本文方法的聚類結果也接近于最優方法所得結果。綜上所述，本文方法在5個真實數據集上的聚類效果優于其他5種對比算法。

表8展示了6種算法在5個真實數據集上進行聚類消耗的時間。通過對比發現：當數據量較小時，本文算法進行聚類時所消耗的時間非常少，例如在對iris、seeds 和heart 數據集聚類時，消耗的時間是6 種聚類方法中最少的；當數據集較大時，比如在對banknote 數據集進行聚類時，所消耗的時間明顯增長，接近于DPC和USPEC算法，但仍然遠小于CutPC算法消耗的時間，這是由于數據量較大時，在尋找反向鄰居的過程、去噪的過程以及合并聚類時需要進行一系列的計算，因而會增加時間的消耗。總的來說，本文方法能夠在達到較好聚類效果的同時還能夠實現較少的計算時間。

表8 6種方法應用在5個真實數據集上的運行時間Table 8 Runtime of 6 methods applied on 5 real datasets 單位：s

3.4 參數魯棒性實驗

為驗證噪聲參數β的魯棒性，實驗中對9個合成數據集采用提出的方法在β從0.08～0.20范圍內每間隔0.02的取值做一次實驗，計算β每次變化時9個合成數據集的Acc和NMI指標的平均值來評價提出算法的參數魯棒性，噪聲參數β在上述范圍內改變時的Acc 和NMI 指標均值變化情況如圖6 所示。紅色折線代表9個合成數據集Acc指標均值的變化情況，藍色折線代表9 個合成數據集NMI 指標均值的變化情況。

圖6 合成數據集的Acc和NMI均值隨著β 的變化Fig.6 Changes of Acc and NMI mean values of synthetic datasets with β

觀察發現，當噪聲參數β在0.08～0.20 范圍內變化時，本文方法應用在9個合成數據集上進行聚類的Acc和NMI指標的均值僅在β較大時出現較小的變化。而β較大時聚類指標均值下降的主要原因在于數據集D4的外圍環狀簇的數據點個數相對于中間3個球形簇較少，噪聲參數較大時會去除環狀簇內部密度較小點，使得環狀簇斷開，從而影響聚類效果。總的來說，噪聲參數β在一定范圍內變化時本文算法依然具有較好的聚類效果。因此，本文方法在參數選擇上具有較強的魯棒性。

4 結束語

本文提出一種反向近鄰構造連通圖的聚類算法。該算法對去噪后的數據采用反向鄰居數作為限制條件構造反向近鄰連通圖進行初步聚類，然后利用給定的聚類數將初步聚類結果按照簇間距離從小到大合并成對應聚類數的結果，最后劃分噪點得到最終的聚類結果。通過構造反向近鄰連通圖能夠避免傳統k近鄰圖由于對每個點取相同的k值導致聚類劃分不準確的問題，能夠擬合非凸形狀等復雜結構的數據集。另外，實驗中將本文方法應用在9個合成數據集和5個真實數據集上，并利用兩種聚類外部指標進行評價，結果表明，本文方法在合成數據集和真實數據集上均能夠取得較好的聚類效果。

然而，當噪聲參數設置過小導致去噪不完全時，可能會導致本文方法無法得到較好的聚類結果。這是因為若噪聲參數設置過小則會導致構造反向近鄰連通圖時將不同簇的數據連接，導致簇劃分錯誤，影響最終的聚類結果。另外，需要人工給定聚類數也是本文方法的不足之處，這也是現有的大多數聚類方法存在的共性問題，后續將針對以上問題做進一步的研究。