基于兩階段搜索的密度聚類算法

汪 勇，李巧娜，艾學軼

(武漢科技大學 恒大管理學院，湖北 武漢 430081)

0 引 言

密度聚類是應用廣泛的一類機器學習方法。典型的密度聚類算法有DBSCAN[1]和DPC[2]。DBSCAN算法兩個參數憑經驗確定，易形成過度聚類或噪聲增多問題。另外，核心對象的隨機選擇影響聚類的穩定性。為此，Ankerst提出基于任何半徑和閥值的聚類方法OPTICS[3]，該方法生成一個簇排序可達圖，將參數隱含在圖形中，由應用者根據需要選擇聚類結果，這給應用者帶來極大不便。于是，一些改進的算法如基于動態近鄰的DN-DBSCAN算法[4]、高效處理簇密度的RNN-DBSCAN算法[5]、自適應鄰域的AA-DBSCAN算法[6]以及解決離群數據點聚類問題的VDBSCAN算法[7]等相繼被提出，在一定程度上提高了DBSCAN的聚類性能。基于對密度聚類方法思想的延伸，Rodriguez等在Science上發表論文提出密度峰聚類算法(DPC)。雖然DPC算法只有一個計算局部密度的截斷距離參數，但該參數值確定依然無據可依，基于距離的最近鄰劃分聚類策略易產生錯誤聚類。為此，研究者提出一些改進的密度計算方法，提高密度峰值的差異性，如采用鄰域數據點殘差計算局部密度的REDPC算法[8]。計算相對密度的RDCA聚類算法[9]、基于邏輯分布和引力的密度計算方法DPC-LG[10]和自適應密度峰聚類算法[11]等。針對連帶錯誤聚類問題，研究者提出一些改進的聚類策略，如模糊加權k近鄰算法[12]、指數樣條k近鄰算法[13]以及相互鄰近度劃分聚類算法[14]等，較好地解決了連帶錯誤聚類問題。

在上述密度聚類算法研究基礎上，本文提出一種基于兩階段搜索的密度聚類算法(density clustering algorithm based on two-stage search，DCATS)，進一步提高其聚類精度。

1 DCATS聚類思想

1.1 基本概念定義

給定數據集DS={x1,x2,…,xn}， 其中xi={xi1,xi2,xim}，i=1,2,…,n，n為數據數量，m為數據維度。設ε是一個正數，則開區間 (xi-ε,xi+ε) 為數據點xi的ε鄰域。

定義1 數據點xi的密度ρ(xi)是xi鄰域ε內的數據點數量，即

(1)

定義2 所有數據點按照密度由高到低排列，按式(2)計算相對密度差d(xi)，令具有最小相對密度差絕對值之和的密度為δ，則稱δ為密度閾值。當ρ(xi)≥δ時，xi為高密度數據點。否則，xi為低密度數據點

(2)

定義3 設xj在xi的ε鄰域內，且xi是高密度數據點，則稱xj是xi的直接密度可達點。設xj為高密度數據點，xk是xj的直接密度可達點，若xk是高密度數據點，則稱xk是xi關于鄰域ε和δ的密度可達點。否則，稱xk是xi的密度相連點。

dik-dij>0

(3)

1.2 兩階段搜索

DCATS由鄰域遞歸搜索和簇最近鄰搜索兩個階段組成。第一階段，鄰域遞歸搜索(recursive search in neighborhood，RSN)采用遞歸搜索方法，在高密度數據點鄰域內搜索未聚類的直接密度可達點、密度可達點和密度相連點，并將這些數據點歸為該高密度數據點所在的簇。直到搜索到的數據點均已聚類或均為低密度數據點為止。RSN搜索流程如圖1所示。

圖1 鄰域逆歸搜索階段

圖1中，條件1判斷密度排序數據集是否含有未聚類的高密度數據點。條件2判斷每次搜索的數據點中是否含有高密度數據點。

第一階段聚類完成時可能存在未聚類的低密度數據點，此時，啟動第二階段的簇最近鄰搜索算法(search the nearest neighbor in cluster，SNNC)，實現低密度數據點或離群數據點聚類。在已聚類數據簇中搜索距離未聚類的低密度數據點最近的數據點，即簇最近鄰點，根據簇最近鄰距離與鄰域關系以及當前已聚類簇數，確定該低密度數據點的歸屬。簇最近鄰搜索流程如圖2所示。

圖2 簇最近鄰搜索階段

圖2中，條件1判斷所有低密度數據點是否均已聚類。條件2判斷簇最近鄰距離是否小于等于鄰域。條件3判斷當前聚類是否只有一個簇。

2 DCATS算法設計

2.1 聚類策略

DCATS運用密度排序、簇最近鄰分配和自適應搜索方法設計算法的聚類策略。

(1)密度排序

對于DBSCAN，假設xi和xj為隨機排列的兩個核心點，且xi和xj分屬于不同簇，dij>ε。數據點xk為非核心點，dik≤ε，djk≤ε。若xi排列在xj之前，則xk屬于xi所在的簇，否則，xk屬于xj所在的簇。故xk的歸屬具有隨機性。DCATS將所有數據點按密度由高到低排序，構成密度序列，RSN從第一個高密度數據點創建類簇進行聚類，SNNC從第一個低密度數據點搜索簇最近鄰點。密度排序策略解決DBSCAN聚類的穩定性問題。

(2)簇最近鄰分配

對于給定的未聚類數據點，其簇最近鄰與最近鄰的區別是，簇最近鄰為已聚類數據點，而最近鄰可能是已聚類數據點，也可能是未聚類數據點。SNNC根據低密度數據點與其簇最近鄰點的距離以及鄰域關系確定該低密度數據點的歸屬。當低密度數據點與簇最近鄰之間距離小于等于鄰域時，將該低密度數據點歸類到其簇最近鄰所在的簇。當其距離大于鄰域時，分為兩種情形，若當前聚類簇數為空或只有一簇時，則以該數據點創建一個新的簇。否則將該數據點歸類到其簇最近鄰所在的簇。

(3)自適應搜索

自適應搜索是指DCATS根據鄰域和數據分布情形而自動選擇執行RSN和SNNC實現聚類。當數據點均勻分布時，根據設置的鄰域，所有數據點均為高密度數據點或低密度數據點，DCATS只啟動RSN或SNNC即可完成聚類。對于連續變密度數據，則同時啟動RSN和SNNC進行兩階段搜索聚類。

2.2 符號說明

DCATS算法涉及的符號見表1。

表1 符號說明

2.3 算法描述

2.3.1 RSN算法

采用密度排序和自適應搜索策略設計RSN算法，算法描述如下。

(1)給定數據集DS，設置鄰域eps。

(2)按式(4)計算DS兩數據點之間的距離d并按距離升序排列

(4)

(3)按式(1)計算數據點xi的密度DP(xi)，并按密度降序排列。

(4)按式(2)計算數據點xi的相對密度差絕對值之和，選擇最小值的數據點密度作為密度閾值DenThd。

(5)設置數據點編號SN、聚類輸出矩陣C和各簇數據點數累積值Q。SN為按密度排序的數據點編號。

(6)判斷SN的狀態，若SN不為空且DP(1)≥DenThd， 轉下一步，否則轉SNNC算法。

(7)以數據點SN(1)創建一個簇并將其存入C。令高密度數據點HDP初始值為SN(1)，刪除SN(1)。

(8)若HDP不為空，轉下一步，否則轉步驟(6)。

(9)查找HDP鄰域內不重復且未聚類的數據點Pts并將其存入C，刪除SN中數據點Pts。

(10)累積已聚類數據點數量并存入Q。

(11)按定義4查找Pts中的高密度數據點，生成新的HDP，轉步驟(8)。

2.3.2 SNNC算法

采用密度排序、簇最近鄰分配和自適應搜索策略設計SNNC算法，算法描述如下。

(1)判斷所有數據點是否為低密度數據點。若C為空，表示所有數據點為低密度數據點，即DenThd>DP(1,2)， 轉下一步。否則轉步驟(3)。

(2)將SN(1)添加至C，創建一個簇，刪除SN(1)。

(3)統計SN中余下的低密度數據點數量L，令i=1。

(4)若i≤L，轉下一步。否則聚類結束，輸出聚類數據C。

(5)從dist中提取與數據點SN(i)構成的點對A，統計A的點對數量S，令j=1。

(6)若j≤S，轉下一步。否則i=i+1，轉步驟(4)。

(7)在A中查找距離SN(i)最近的點對A(j,2)。

(8)若A(j,2)屬于C，由式(3)可知，A(j,2)是SN(i)的簇最近鄰，轉下一步。否則j=j+1， 轉步驟(6)。

(9)統計當前已聚類的簇數nc。

(10)若SN(i)與A(j,2)之間的距離A(j,3)≤eps， 轉下一步。否則，若nc=1，轉步驟(14)。否則轉下一步。

(11)查找A(j,2) 在類簇C中的位置并將SN(i) 插入到C的A(j,2) 之前的位置。

(12)查找A(j,2) 位置值在Q中的位置。

(13)更新C中各類簇數據點累積數。i=i+1， 轉步驟(4)。

(14)將SN(i)添加到C的尾部，構成新簇，轉步驟(13)。

2.4 時間復雜度

由RSN算法步驟可知，它由距離計算、密度計算和鄰域搜索過程組成。數據點距離計算次數為n(n-1)/2， 故時間復雜度為O(n2)。 顯然，密度計算的時間復雜度為O(n)。 鄰域搜索是一個遞歸過程，假設聚類為c簇，數據點數量分別為n1,n2,…,nc， 則時間復雜度為

O(logn1+logn2+…+lognc)

(5)

對于SNNC算法，最壞情況下，假設剩余的數據點有n個，因d是有序的，故只需n次搜索即可完成聚類，時間復雜度為O(n)。

由上述分析可知，距離計算是DCATS算法執行最耗時的過程，與DBSCAN和DPC算法一樣，DCATS時間復雜度為O(n2)。

3 算法性能分析

3.1 數據集選擇

為驗證DCATS聚類算法性能，選擇4個人工數據集和4個UCI真實數據集進行測試[14]。數據集描述見表2。

表2 數據集描述

將DCATS與DBSCAN、AA-DBSCAN[6]、DPC和RDCA[9]進行聚類效果對比。利用標準互信息(NMI)[15]、調整蘭德系數(ARI)[16]和Fowlkes-Mallows指數(FMI)[17]評價各算法的聚類效果。采用Matlab作為實驗平臺，經多次實驗選擇最優參數作為各算法的聚類參數。

3.2 人工數據集測試

5個算法在4個人工數據集上的聚類結果評價指標見表3。粗體數值表示對應的指標最優。

表3 人工數據集聚類評價

由表3可知，對于Flame、Jain和Square這3個數據集，DCATS這3個指標保持最優。對于Aggregation數據集，DCATS的NMI指標最優，AA-DBSCAN的ARI、FMI指標略優于DCATS。總的來看，AA-DBSCAN和DBSCAN聚類效果優于DPC和RDCA，AA-DBSCAN優于DBSCAN，RDCA優于DPC，DCATS算法聚類效果優于比較的4個算法。各算法在4個人工數據集上的聚類結果如圖3～圖7所示。

圖3 DCATS聚類結果

圖4 DBSCAN聚類結果

圖5 AA-DBSCAN聚類結果

圖6 DPC聚類結果

圖7 RDCA聚類結果

圖3(a)～圖7(a)是Flame數據集的聚類結果。5個算法均聚為2簇，DBSCAN和AA-DBSCAN存在少數噪聲點，且AA-DBSCAN噪聲點少于DBSCAN。DPC和RDCA出現明顯的連帶錯誤，聚類結果較差。只有DCATS聚類結果最理想。

圖3(b)～圖7(b)是Jain數據集的聚類結果。DCATS、DBSCAN和AA-DBSCAN聚為3簇，DBSCAN和AA-DBSCAN出現少量噪聲點。DPC和RDCA雖聚為2簇，但存在較多的錯誤聚類。總的來看，DCATS在Jain數據集上的聚類結果最好。

圖3(c)～圖7(c)是Aggregation數據集的聚類結果。5個算法均聚為7簇。AA-DBSCAN噪聲點少于DBSCAN。DPC和RDCA均有3簇出現錯誤聚類。總的來看，對于Aggregation數據集，前3個算法聚類結果相近，DCATS算法聚類結果更優。

圖3(d)～圖7(d)是Square數據集的聚類結果。DBSCAN和AA-DBSCAN出現較多的噪聲點，DPC和RDCA均存在簇間錯誤聚類。相對而言，DCATS在Square數據集上的聚類結果明顯優于另外4個算法。

3.3 真實數據集測試

真實數據集均為多維度數據。5個算法在4個真實數據集上的聚類結果評價指標見表4。粗體數值表示對應的指標最優。

由表4可知，對于Seeds數據集，DCATS、DPC和RDCA這3個指標相同，均為最優。對于Heart數據集，DCATS、DPC和RDCA的ARI和FMI指標相同，均為最優，DBSCAN的NMI指標最優。對于Lonosphere數據集，DCATS的ARI和FMI指標最優，AA-DBSCAN的NMI指標最優。對于Libras數據集，DCATS的NMI和ARI指標最優，DPC的FMI指標略優于DCATS。綜合來看，DCATS算法的聚類精度優于比較的密度聚類算法，表明其聚類策略是有效的。

表4 真實數據集聚類評價

4 結束語

DCATS對所有數據按密度進行排序，第一階段的鄰域遞歸搜索算法代替DBSCANs基于核心對象的鄰域搜索機制，避免DBSCANs核心對象的選擇順序造成數據點隨機聚類問題，實現數據的穩定聚類。同時，鄰域遞歸搜索算法自動確定類簇，避免DPCs聚類算法人工確定聚類中心帶來的主觀聚類問題。DCATS的簇最近鄰搜索算法實現低密度離群數據點的正確聚類，消除DBSCANs聚類產生的噪聲數據點。同時，簇最近鄰搜索算法解決了DPCs的最近鄰劃分策略產生的聚類連帶錯誤問題，提高了聚類精度。如何合理確定DCATS的鄰域參數值得進一步探討。