一種優化初始點與自適應半徑的密度聚類算法

王治和，曹旭琰，杜 輝

（西北師范大學計算機科學與工程學院，蘭州 730070）

0 概述

數據挖掘是從大量數據中提取有價值信息的過程，將其轉化成人們需要的且有組織的知識信息［1-2］，已在許多領域取得重要成果。聚類分析是數據挖掘的重要技術之一，可以作為一種獨立的工具深入了解數據集的分布情況。其主要任務是將數據集中的每一個數據樣本劃分到相應的簇中，使簇內的樣本彼此相似，而簇間的樣本彼此不相似［3-4］。目前，聚類分析已經廣泛地應用于圖像分析［5］、模式識別［6］、生物信息學［7］、知識發現［8］、醫學［9-10］和農業［11］等領域?；诿芏鹊木垲愃惴ㄊ蔷垲惙治龅闹匾夹g之一，其中經典算法有DBSCAN 算法［12］、OPTICS算法［13］、DENCLUE 算法［14］等。

文獻［12］提出的DBSCAN 算法，聚類初始點是從數據集中任意取出一個樣本，判斷其為核心點后開始聚類，增加了算法的時間開銷。該算法中的Eps和MinPts 是全局參數，在聚類過程中不能改變，所以不能正確聚類密度不均勻的數據集。因此，如何恰當地選擇聚類的初始點和Eps 值是提高聚類準確度的關鍵因素，很多學者對此做了大量研究和改進。文獻［13］提出OPTICS 算法，該算法并不產生數據集聚類，而是輸出一個表示數據的基于密度的聚類結構的簇排序，克服了使用一組全局參數的缺點。但這種總是朝高密度區域擴張的策略，使那些無法連向下一個高密度區域的低密度點往往被累積在結果序列的末尾，導致這些低密度點與高密度點的相鄰關系在映射時被分離［15］。文 獻［16］提出的OSDBSCAN 算法優化了初始點的選擇，并結合數據集的特點自適應計算Eps 和MinPts 值，但是引入了聚類個數k、密度參數α、倍率參數β3 個參數，不僅沒有減少人為干預，而且帶來更大的復雜性。文獻［17］提出VDBSCAN 算法，該算法能夠聚類密度不同的數據集，求每個數據樣本的第k個近鄰，利用k-dist 圖選取不同密度層次相應的Eps 值，但是選取過程需要人為干預，存在很大的不確定性。文獻［18］提出RNN-DBSCAN 算法，使用反向最近鄰（RNN）的思想來定義密度和核心樣本，但整體的聚類效果不佳且運行時間較長。文獻［19］提出ADBSCAN 算法，利用最近鄰圖（NNG）固有的性質來識別局部高密度樣本，運用密度估計對噪聲樣本進行濾波，但在某些情況下，該算法有時無法識別正確的簇數，而且需要對多個參數組合進行測試。

通過上述研究發現，RNN 算法對獲取全局密度最大的數據樣本起到重要作用，解決了DBSCAN 算法隨機取初始點的問題。本文提出一種新的OIRDBSCAN 算法，借鑒OPTICS 算法中核心距離和可達距離的思路，通過調整核心距離和可達距離的值得到適合該簇的半徑r，以解決DBSCAN 算法中Eps是全局參數的問題。

1 相關工作

1.1 DBSCAN 算法

DBSCAN 算法可以發現任意形狀的簇，并識別噪點，不需要設定具體的簇數，聚類效果穩定。在Eps 鄰域、MinPts 密度閾值、核心點、直接密度可達、密度可達的基礎上設定了密度相連［20］概念。

DBSCAN 算法從任意一個點p出發，先判斷其是否是核心點，若是，尋找Eps 鄰域內與p直接密度可達的點，將這些點放入集合U中，然后遍歷集合U中的所有核心點，尋找與它們密度可達的點，迭代上述步驟，直到集合U中沒有可擴展的核心點，此時形成了一個完整的簇；若不是，暫時將其標注為噪點。聚類完成其中的一個簇后，對未遍歷的數據點重復上述過程，進行其他簇的擴展，直至所有的點被遍歷。其中既不是核心點也不是邊界點的被稱為噪點。

1.2 點x 的k 近鄰和反向最近鄰

假設X是d維空間中的數據點集，用n表示X的大小，n=|X|。?x∈X，x∈Rd。對于X中的任意兩個點x和y，用表示兩點之間的距離，其中k的取值范圍為1≤k≤n-1。

定義1點x的k近鄰用Nk(x)=N表示，其中N滿足以下條件：

定義2點x的反向最近鄰用Rk(x)=R表示，其中R滿足以下條件：

1）R?X/{x}。

2）?y∈R：x∈Nk(y)。

下文用具體的示例對上述定義做出解釋，該數據集共有5 個點，如圖1 所示。

圖1 二維空間5 個數據點的最近鄰圖Fig.1 Nearest neighbor graph of five data points in two-dimensional space

從圖1可以看出：a點的最近鄰是b，b點和c點互為最近鄰，d點的最近鄰是c，以此類推。在k近鄰中，k取1 時為最近鄰點，k取2 時為第二近鄰點，k取n（n為正整數）時為第n個近鄰點。圖1 的最近鄰表如表1 所示，取k=1。對于反向最近鄰，需要滿足定義2 的2 個條件，具體分析如表2 所示。

表1 二維空間5 個數據點的最近鄰表Table 1 Nearest neighbor table of five data points in two-dimensional space

表2 二維空間5 個數據點的反向最近鄰表Table 2 Reverse nearest neighbor table of five data points in two-dimensional space

反向最近鄰表如表2 所示，其中以點b為例進行分析。點c滿足?x∈X：dist(b，c)≤dist(c，x)，所以c是b的反向最近鄰點，a同理，滿足?x∈X：dist(b，a)≤dist(a，x)，所以a也是b的反向最近鄰點。其他點的分析方法類似。

2 OIR-DBSCAN 算法

2.1 設計方法

首先尋找數據集中全局密度最大的數據樣本，將該樣本作為聚類初始點，然后用自適應半徑的方法計算出該初始點所在簇相應的r值。以該樣本為初始點，r值為半徑開始聚類。當一個簇聚類完成后，再從剩余的數據樣本中選出新的聚類初始點，迭代上述過程，直至所有數據樣本被劃分類別或有部分數據樣本被當作噪聲處理，聚類結束。

2.2 初始點優化

在K-means 算法中初始點的優化對算法的改進尤為重要。盡管DBSCAN 算法中初始點的優化對聚類結果的影響不太明顯，但從算法的角度考慮，如果初始點選擇的是全局密度最大的點，那么該點一定是核心點，可以省去判斷某個點是否是核心點的時間。本文從文獻［16，18］中得到啟發，改進的算法能夠找到數據集中全局密度最大的點。

在初始點優化思路中，運用到1.2 節中提到的k近鄰算法和反向最近鄰。從表2 可以看出，a點和e點無反向最近鄰，b點的反向最近鄰是a和c，c點的反向最近鄰是b和d。也可以理解為：a和e沒有出現在任何點的好友圈中，而b出現在a和c的好友圈中，c出現在b和d的好友圈中，d出現在e的好友圈中?？梢钥闯鯾和c在好友圈的活躍程度最高，在一定程度上證明其周圍數據點的密度較高。

首先根據反向最近鄰表計算出每個點反向最近鄰的個數m，m越大，意味著該點的活躍度越高，越有可能成為初始點。但是要計算出最終的聚類初始點，不能只根據m值，需要考慮下面這種情況，如圖2 所示（設k=1）。

圖2 52 個數據樣本考慮m 值的示意圖Fig.2 Fifty-two data samples only consider the schematic diagram of m value

觀察箭頭所指的兩個點，通過計算得出它們的反向最近鄰個數m均等于4。那么如果只考慮m，則兩者大小一樣。但圖2 中右下角箭頭所指的點所在簇的密度顯然大于左上角中箭頭所指的點所在簇的密度。因此，不能只考慮m的取值，還應該考慮該點與k個鄰近距離和的大小，記為dist。dist 越大，密度越小；反之dist 越小，密度越大。

設數據集的相似度矩陣為MMatrix，相似度矩陣用歐式距離表示，每行按從小到大排序后，去除第一列的零元素，記為KNNMatrix。每個數據樣本對應的m值記為minit。VValue(init)的大小決定該init 點是否可以作為聚類初始點，值越小，表明該點越適合作為聚類初始點；反之，不適合。因此，聚類初始點的判別公式如式（1）所示：

將當前最小的VValue(init)值對應的init 作為聚類初始點。當一個簇聚類完成后，將已經有聚類標簽的點從候選init 隊列中刪除，方便重新選出下一次聚類的初始點。

初始點的選擇如圖3 所示，數據集的初始點依次為三角形、六邊形和五角星所在的點。

圖3 52 個數據樣本初始點示意圖Fig.3 Schematic diagram of initial points of fifty-two data samples

初始點的優化算法如算法1 所示。

算法1初始點優化

輸入k（k=4）

輸出init

步驟1求出各個樣本之間的相似度矩陣MMatrix，用歐式距離表示。

步驟2對Matrix 按行升序排序，去掉第一列的0 元素，得到矩陣KNNMatrix。

步驟3計算每個樣本的反向最近鄰個數m。

步驟4計算每個樣本的k個近鄰的距離和dist。將該樣本的序號、步驟4 計算出的dist 值和步驟3 計算出的m放入列表RNNDist 中。

步驟5計算RNNDist列表中每個對象的VValue(init)值，參考式（1），按升序排列，得到列表SortRnnDist。

步驟6取SortRnnDist 列表的第一個值對應的init 為聚類初始點。

步驟7從第一個初始點開始的聚類結束后，將已經有標簽的樣本從SortRnnDist 列表中刪除，重復步驟6，選取下一次的聚類初始點，重復步驟7，迭代直至聚類結束。

2.3 自適應半徑r

在傳統的DBSCAN 算法中，Eps 在聚類過程中不能改變。如果Eps 取值太小，將會導致數據集被分割成多個簇；如果Eps 取值太大，將會出現多個簇被合并的現象。無論哪種情況，都不能對有密度變化的數據集進行正確聚類。為克服上述困難，引入以下3 個概念：

1）核心距離。對象p的核心距離ε'是使得p的ε'-領域內至少有k個對象，即ε'是使得p成為核心對象的最小半徑閾值。對于數據集中的任意一個對象，每個對象p的ε'都不同。如圖3 所示，五角星點的ε'=0.5；六邊形點的ε'=1；三角形點的ε'=1.25。

2）ε距離。ε的取值是一個全局的參數，由用戶設定，如圖4 所示，取ε=1。

圖4 核距比之間的關系Fig.4 Relationship of kernel’s distance radio

3）核距比。表示核心距離ε'與ε距離的比值，核距比在一定程度上可以反映數據點分布的疏密情況。

在圖4 中，圖4（a）和圖4（b）的核距比均小于1，其中圖4（a）的核距比最小，得出數據之間的密度分布緊湊；圖4（b）的核距比幾乎為1，數據之間的密度分布適中；圖4（c）的核距比大于1，明顯數據較分散。但是對于核距比大于1 的數據點，存在是噪點的可能性，需要做進一步的判斷。

設置一個參數α用來與核距比作比較，α設定的大小可以對自適應半徑r的調節起到伸縮作用。α越小，半徑r可調整的伸縮性越大；反之，伸縮性越小。自適應半徑r的判斷如圖5 所示。

圖5 自適應半徑流程Fig.5 Procedure of self-adapting radius

從圖5 可以看出，r的選擇有如下3 種情況：

1）數據對象的密度緊密，當核距比遠小于α時，如果直接取r=ε'，那么半徑r取值太小，會導致本屬于同一個簇的數據點被分割成多個簇。所以，采用圖5 中適當增大ε'的方法重新計算核距比，使得α落在規定區間，此時取r=ε'。

2）數據對象的密度適中，當核距比正好落在α規定區間時，直接取r=ε。因為此時ε和ε'的大小相差甚微，所以選取值較大的ε，加快聚類速度。

3）數據對象的密度稀疏，當核距比遠大于α時，如果直接判斷為噪點，那么可能會忽略如圖2 所示的左邊簇的情況。所以，判斷該數據對象的ε'鄰域中的每個點是否有大于等于k個未被標識的對象，若有，則說明該點附近只是密度稀疏，并不是噪點，取r=ε'；反之，則為噪點。

2.4 算法描述

通過上述初始值的選取和半徑的判定，得到init和r值，然后采用密度聚類的方法進行聚類。第一次聚類結束之后，從剩余未被標記的數據樣本中選出第二次聚類的初始點init′和半徑r′，進行第二次聚類、迭代，直至所有數據樣本被劃分類別或有部分數據做噪聲處理。

對于數據集X中的每個樣本x，標簽用cluster表示，聚類過的樣本添加到visited 列表中，未被聚類的樣本存放在unvisited 列表中，將聚類結果存放在數組assign中。OIR-DBSCAN 算法的流程如算法2 所示。

算法2OIR-DBSCAN 算法

輸入數據集dataset

輸出assign

步驟1對數據集作歸一化處理。

步驟2根據算法1 計算出初始點init。

步驟3根據圖5 的流程圖計算出自適應半徑r。

步驟4通過DBSCAN 算法，將和初始點init 屬于同一類的數據樣本劃分出來，cluster 加1。

步驟5執行步驟2、步驟3。

步驟6用步驟4 的方法對剩余點聚類。

步驟7迭代，直至所有數據被聚類或部分數據被當作噪聲處理。

2.5 參數選擇

算法中k值是固定參數，取值為4，k主要用來控制核心距離ε'，進而影響半徑r。參數ε人為設定。α的大小可以對自適應半徑r的調節起到伸縮作用，經大量實驗測試，α的取值范圍是0.25～0.8。參數MinPts 和DBSCAN 算法中的MinPts 一樣，用來控制核心點的判斷。雖然該參數也是人為設定的參數，但經過大量實驗論證，取值范圍一般為3～15，且為正整數。

3 實驗結果與分析

為對本文算法性能進行評估，檢測其有效性，本文進行以下對比實驗。對比算法包括DBSCAN 算法、OPTICS 算法和RNN-DBSCAN 算法。數據集采用人工數據集和真實數據集，人工數據集包括Compound、Pathbased、Jain、Aggregation、grid.orig；真實數據集包括iris、WBC、Thyroid、Ecoli、Pima、Vote、Vowel 等。其中人工數據集如表3 所示。

表3 人工數據集Table 3 Artificial datasets

實驗環境為Inter?CoreTMi7-1065G7 CPU@1.30 GHz 1.50 GHz，內存為16 GB，編程環境為python3.8，編譯器為Jupter Notebook、PyCharm。

聚類的評價指標選用調整蘭德指數（ARI）［21］、歸一化交互信息（NMI）［22］、同質性指標（homogeneity）、完整性指標（completeness）和同質性與完整性的調和平均（V-measure）［23］。

ARI 是調整的RI，相對RI 來說有更高的區分度。ARI 的取值范圍是［-1，1］，數值越接近1 代表聚類結果越好，越接近0 代表聚類結果越差，計算公式如式（2）所示：

其中：max 表示取最大值；E表示期望。

ARI 計算公式如式（3）所示：

其中：i、j分別表示為真實簇類和預測簇類；nij表示聚類正確的樣本個數；max（RI）表示如果聚類結果完全正確時的值；E[RI]表示求RI 的期望值。

NMI 是一個外部指標，通過將聚類結果與“真實”的類標簽對比衡量聚類效果，如式（4）所示：

其中：k（C）是聚類結果的簇數；k（T）是真實聚類結果的簇數；ni是簇i的樣本個數；nj是簇j的樣本個數；ni，j是聚類結果C中屬于簇i的樣本與真實聚類結果T中屬于簇j的樣本之間的樣本個數；n是數據集的樣本總數。

同質性h表示每個簇只包含單一類別成員的程度；完整性c表示一個給定類的所有成員分配到單一簇的程度；V-measure 表示兩者的調和平均。其中同質性和完整性如式（5）和式（6）所示：

其中：H(C|K)是給定簇。

類的條件熵如式（7）所示：

H(C)是類的熵，計算公式如式（8）所示：

其中：n表示數據集的樣本總數；nc和nk分別表示屬于簇c和簇k的樣本數；nc，k為類c中的樣本分配給簇k的數量。

V-measure 的表達式如式（9）所示：

3.1 人工數據集

本組實驗用上述提及的5 個人工數據集進行測試，聚類結果如圖6～圖10 所示。Compound 數據集中有若干個密度不同的簇，圖6 的實驗結果表明，只有本文提出的OIR-DBSCAN 算法能得到正確的聚類結果，而DBSCAN 算法中由于Eps 參數的局限性，誤將左上角的簇當作噪點處理，OPTICS 算法和RNN-DBSCAN 算法的聚類結果差強人意；在圖7中，數據集的分布較為松散且密度分布無規律，DBSCAN 算法、OPTICS 算法和RNN-DBSCAN 算法在聚類內部簇的過程中都會將最外層的數據樣本聚類進來，導致一個簇中出現了很多本不屬于該簇的數據樣本，而OIR-DBSCAN 算法通過對核心距離和ε距離的調整計算出合適的半徑r，從而進一步得到較好的聚類結果；在圖8 中，上下兩個簇有較大的密度差異，DBSCAN 算法中若Eps 取值小，則上面的簇會被分割成幾部分，如圖8（a）所示，RNN-DBSCAN算法和OPTICS 算法在聚類過程中將一個簇分成兩個，聚類效果較差，只有OIR-DBSCAN 算法能得到正確的聚類結果；在圖9 中，數據樣本的密度分布相對均勻，部分簇之間相連，經過聚類結果分析發現4 種算法都有不錯的聚類效果，其中OIR-DBSCAN聚類結果最好，RNN-DBSCAN 算法次之，OPTICS 算法相對最差；在圖10 中，簇內樣本分布均勻，但兩個簇的密度差異大且簇間距離很近，這種數據集最能充分體現出OIR-DBSCAN 算法的優越性，該算法針對不同密度的簇自適應地計算出不同的半徑r進行聚類，得到了較好的聚類結果，而DBSCAN 算法和OPTICS 算法在聚類右下角的簇時，將離該簇最近但本屬于左簇的部分數據樣本聚類進來，得到了錯誤的聚類結果，RNN-DBSCAN 算法的聚類結果最差。

圖6 4 種算法在Compound 數據集上的聚類結果Fig.6 Clustering results of four algorithms on Compound dataset

圖7 4 種算法在Pathbased 數據集上的聚類結果Fig.7 Clustering results of four algorithms on Pathbased dataset

圖8 4 種算法在Jain 數據集上的聚類結果Fig.8 Clustering results of four algorithms on Jain dataset

圖9 4 種算法在Aggregation 數據集上的聚類結果Fig.9 Clustering results of four algorithms on Aggregation dataset

圖10 4 種算法在grid.orig 數據集上的聚類結果Fig.10 Clustering results of four algorithms on grid.orig dataset

通過圖6～圖10 所示的可視化對比實驗分析可以得到，在Aggregation 等數據集上，其中一部分算法也可以達到較好的聚類效果。但總體來說，無論是密度不均勻的數據集還是普通數據集，OIRDBSCAN 算法都能夠得到很好的聚類結果。4 個聚類算法在人工數據集上性能的對比如表4 所示（粗體為最優值）。4 種算法在聚類過程中達到最優效果的具體參數取值如表5 所示。

表5 4 種算法在人工數據集上的參數值Table 5 Parameter values of four algorithms on artificial datasets

3.2 真實數據集

在人工數據集上，OIR-DBSCAN 算法表現出較好的聚類結果。為進一步驗證其聚類性能，還需要在真實數據集上進行驗證，UCI 數據集如表6所示。

表6 UCI 數據集Table 6 UCI datasets

在UCI 數據集中，因為高維數據集可視化難度較大，所以通過聚類評價指標ARI、NMI、homogeneity、completeness 和V-measure 進行對比，聚類評價指標的對比結果如表7 所示（粗體為最優值）。在Pima 數據集中，DBSCAN 算法的NMI 值高于OIR-DBSCAN算法0.006 9，在Vote 數據集中，DBSCAN 算法的NMI 值高于OIR-DBSCAN算法0.013 9，但從整體對比結果來看，OIR-DBSCAN 算法的ARI、NMI 等評價指標都明顯高于其他聚類算法。通過比較發現，OIR-DBSCAN 算法的聚類效果最好，DBSCAN 算法和OPTICS 算法次之，RNN-DBSCAN 算法效果相對最不理想。

表7 4 種算法在UCI 數據集上的評價指標對比Table 7 Comparison of evaluation index of four algorithms on UCI dataset

4 結束語

本文提出一種優化初始點與自適應半徑的密度聚類算法。將反向最近鄰和相似度矩陣相結合，迭代選取每次聚類開始的初始點，該初始點即為全局密度最大的樣本。優化DBSCAN 算法中Eps 全局參數，調整核心距離ε'和ε距離之間的核距比與參數α得出最終半徑值r，使得密度稀疏的簇和密度稠密的簇分別對應各自適合的r值，該參數具有較好的靈活性。實驗結果證明，OIR-DBSCAN 算法可以正確聚類密度不均勻的數據集，而且對高維甚至簇間有重疊的數據集也有較好的聚類能力。本文算法在聚類大規模數據集時會出現聚類時間較長的現象，下一步將從改進算法性能和提高聚類速度方向入手，以使算法的聚類效果達到最優。