這里介紹的幾種常用基于密度聚類算法包括：DBSCAN、OPTICS、DENCLUE。
1. DBSCAN
DBSCAN (Density Based Spatial Clustering of Application with Noise)[1] 算法的核心思想是，對(duì)于一個(gè)簇(cluster)內(nèi)的點(diǎn)，要求在給定半徑 ε 的鄰域包含的點(diǎn)數(shù)——也稱為基數(shù)(cardinality)——必須不小于一個(gè)最小值MInPts，這些滿足要求點(diǎn)成為“核心點(diǎn)”(core points)。所以這里一個(gè)點(diǎn)的密度就是以其關(guān)于 ε 和 MInPts 的基數(shù)來代表的。而為了讓每個(gè)簇中的那些“邊緣點(diǎn)”(border points)——不滿足最小值要求但在核心點(diǎn)的鄰域范圍內(nèi)的點(diǎn)——不被忽略掉，算法遞進(jìn)地給出了"密度直達(dá)"(directly density-reachable)、“密度可達(dá)”(density-reachable)、“密度相連”(density-connected)的概念，所有彼此之間關(guān)于給定參數(shù) ε 和 MInPts 密度相連的數(shù)據(jù)點(diǎn)組成一個(gè)簇，沒有包含在任何一個(gè)簇內(nèi)的點(diǎn)就屬于噪聲(noise)。其實(shí)在具體實(shí)現(xiàn)時(shí)時(shí)不必在意所謂“密度相連”的概念的，只需要迭代地將“核心點(diǎn)”鄰域中的所有點(diǎn)——即密度直達(dá)的點(diǎn)——包含進(jìn)來即可，這樣最終形成的簇其內(nèi)的所有點(diǎn)必定是密度相連的。
對(duì)于DBSCAN中的兩個(gè)全局參數(shù) ε 和 MInPts，可以通過一個(gè)參數(shù) K 來啟發(fā)式地得到它們。數(shù)據(jù)集中一個(gè)點(diǎn)的第 K 鄰近點(diǎn)與它的距離稱為 k_dist，當(dāng)我們畫出所有點(diǎn)排序后的 k_dist 圖之后，可以確定一個(gè)”界限“(threshold)。在界限之下的所有點(diǎn)就是核心點(diǎn)，界限值就是所需的 ε 值，K 值就是 MInPts 值。界限一般在 k_dist 突然變化的地方，或者根據(jù)先驗(yàn)知識(shí)確定(事先知道數(shù)據(jù)集中噪聲的比例)。
Tips
使用統(tǒng)計(jì)的方法，通過統(tǒng)計(jì) k_dist 變化率 Δk_dist 可以形成一種自動(dòng)找出 k_dist 突變處的方法。
2. OPTICS
OPTICS (Ordering Points To Identify the Clustering Structure)[2] 不直接提供數(shù)據(jù)集的聚類結(jié)果，而是產(chǎn)生一個(gè)關(guān)于數(shù)據(jù)集的“増廣排序”(augmented ordering)，它反映了數(shù)據(jù)基于密度的聚類結(jié)構(gòu)。原文中介紹說道OPTICS的工作原理就像是一種擴(kuò)展的DBSCAN算法。在算法過程中會(huì)考慮在“生成距離”(generating distance) ε 之下的任何距離參數(shù) ε_i，但這個(gè)過程不會(huì)生成點(diǎn)的所屬簇，而是保存對(duì)象的處理順序和重要信息。重要的信息包括兩個(gè)：核心距離(core-distance)和可達(dá)距離(reachability-distance)。核心距離 core_distance_{ε,MinPts}(p) 就是，數(shù)據(jù)點(diǎn) p 在給定的生成距離 ε 范圍與一個(gè)臨近點(diǎn)的距離，且是能讓 p 成為核心點(diǎn)的最短距離 ε'（若 ε' 超過了 ε，p 不能稱為核心點(diǎn)，那么 p 的核心距離就失去意義）。可達(dá)距離ReachDist_ε_MinPts(p,o) 是關(guān)于核心點(diǎn)來說的，數(shù)據(jù)點(diǎn) p 在 ε 范圍內(nèi)與某一核心點(diǎn) o 之間的距離，且它不能小于 o 的核心距離（若點(diǎn) p 的 ε 范圍沒有核心點(diǎn)，則它不存在關(guān)于任何點(diǎn)的可達(dá)距離）。
在生成了數(shù)據(jù)集相對(duì)于 ε 和 MInPts 的增廣聚類排序之后，我們可以從中提取關(guān)于 ε'<ε 和 MInPts 的任何基于密度的聚類結(jié)果，只需要根據(jù)核心距離和可達(dá)距離通過簡(jiǎn)單的“掃描”得到的排序序列來標(biāo)記數(shù)據(jù)點(diǎn)的所屬簇即可。
Tips
生成增廣的聚類排序會(huì)保存兩種信息——核心距離和可達(dá)距離。但對(duì)于從中提取類似 DBSCAN 的結(jié)果而言，通過對(duì)提取程序的一些調(diào)整，我們只需要可達(dá)距離這一種信息即可實(shí)現(xiàn)目的。
3. DENCLUE
DENCLUE (DENsity based CLUstEring)[3] 引入影響函數(shù)和密度函數(shù)(influence and density function)的概念用以進(jìn)行基于密度的聚類。空間中的任一點(diǎn)密度是所有數(shù)據(jù)點(diǎn)在此點(diǎn)產(chǎn)生影響的疊加，一般采用高斯影響函數(shù)進(jìn)行計(jì)算，這里需要給定算法的第一個(gè)參數(shù) σ，一般稱為平滑參數(shù)(smoothing parameter)。算法又定義了密度吸引點(diǎn)(density attractor)的概念用以進(jìn)行聚類操作。密度吸引點(diǎn)就是密度函數(shù)中的那些局部最大值點(diǎn)，在算法中可以通過梯度爬山法(climb hill)來得到它們的近似位置，這里需要給定算法的第二個(gè)參數(shù)，步進(jìn)長度 δ，也稱為收斂速率(controlling convergence speed)。由這些吸引點(diǎn)可以給出從“中心限定簇”(center-defined cluster)到“任意形狀簇”(arbitrary-shape cluster)的定義。中心限定簇針對(duì)每個(gè)吸引中心而言，指的是某吸引中心 x* 的密度大于給定的密度閾值 ξ，那么由 x* 所吸引的所有數(shù)據(jù)點(diǎn)構(gòu)成一個(gè)中心限定簇。任意形狀簇在前者的基礎(chǔ)上延伸得到，只要兩個(gè)吸引 x1* 、x2* 中心之間存在一條路徑，該路徑上的密度也大于 ξ，那么由x1* 、x2* 所定義的中心限定簇合并在同一簇內(nèi)，這樣構(gòu)成的簇就可以任意形狀的。這里的閾值 ξ 就是算法需要的第三個(gè)參數(shù)，也稱為噪聲閾值(noise threshold)。
算法實(shí)現(xiàn)過程中需要一些處理技巧。首先是計(jì)算密度函數(shù)，顯然全局密度函數(shù)的計(jì)算量隨著數(shù)據(jù)量的增加是巨大的(O(n^2))，所以我們可以根據(jù)高斯函數(shù)的 3σ 原則來計(jì)算局部密度函數(shù)值(local density function)，即數(shù)據(jù)空間中某點(diǎn)的局部密度等于它的 3σ 范圍內(nèi)數(shù)據(jù)點(diǎn)的影響疊加。然后為了提高搜索效率，我們可以對(duì)數(shù)據(jù)空間分塊并建立索引，如B+樹、R樹等。
在缺少先驗(yàn)知識(shí)的情況下，設(shè)置算法的三個(gè)參數(shù)(σ/δ/ξ)是一件困難的事情，而且三個(gè)參數(shù)之間是互相牽制的，這無疑增大的參數(shù)調(diào)整的復(fù)雜度。另一個(gè)問題在于數(shù)據(jù)過濾操作，這一操作是DENCLUE算法中多出的一步操作。由于密度閾值 ξ 只針對(duì)密度吸引點(diǎn)，那么在原始數(shù)據(jù)集上的產(chǎn)生的聚類中不能避免地會(huì)包含噪聲，這回造成聚類結(jié)果噪聲率較低的假象，所以需要對(duì)數(shù)據(jù)提前過濾，去除明顯的噪聲數(shù)據(jù)。過濾實(shí)在數(shù)據(jù)分塊的基礎(chǔ)上進(jìn)行的，設(shè)定一個(gè)過濾閾值 ξ_c ，視分塊中數(shù)據(jù)量小于 ξ_c 的數(shù)據(jù)點(diǎn)為噪聲，過濾即讓該數(shù)據(jù)分塊為空，之后使用過濾后的數(shù)據(jù)進(jìn)行聚類。這里的ξ_c原文里的建議值是 ξ/2/ndims ， ndims 為數(shù)據(jù)維度。但是在實(shí)驗(yàn)中發(fā)現(xiàn)該建議值并不一定合適，實(shí)際上這里又產(chǎn)生了一個(gè)參數(shù)，需要我們針對(duì)數(shù)據(jù)集的特點(diǎn)進(jìn)行設(shè)定。
DENCLUE在t7_10k.dat上的聚類結(jié)果如下，
有過濾操作
無有過濾操作
DENCLUE2.0 改進(jìn)的地方在爬山法的方式。它不在采用原始的定步長爬山，而是給出了一種自適應(yīng)的變步長爬山方式，可以更快的接近吸引點(diǎn)即山頂?shù)奈恢茫⑶以诶碚摽梢陨蠠o限接近吸引點(diǎn)。正因?yàn)槠鋾?huì)無限度地接近吸引點(diǎn)，所以我們需要給定其停止的條件。直白地說就是，當(dāng)爬上過程中密度上升不十分明顯時(shí)，可以停止繼續(xù)爬山，表達(dá)式為 (f(x)l-f(x){l-1})/f(x)_l<=γ， γ 不需給太小，這樣反而會(huì)讓迭代步驟增加，加大計(jì)算量，同時(shí)也使爬山終點(diǎn)太過集中于各吸引點(diǎn)附近，不利于簇的合并，容易形成更多分離的簇，本次試驗(yàn)中的參數(shù)為 h=0.01985, γ=0.01, ξ=38, ξ_c=6，無過濾操作對(duì)應(yīng) ξ_c=0。
DENCLUE2.0在t7_10k.dat上的聚類結(jié)果如下，
有過濾操作(聚類數(shù)=9，噪聲占比=7.410%)
無有過濾操作(聚類數(shù)=12,噪聲占比=2.070%)
Tips
通過觀察DENLCUE2.0中爬山終點(diǎn)的聚集過程得到啟發(fā)，也許可以直接利用爬山終點(diǎn)提取聚類結(jié)果，由此節(jié)省許多時(shí)間與空間成本。
數(shù)據(jù)
實(shí)驗(yàn)數(shù)據(jù) 7_10k.dat 為 Chameleon 論文[5]中所給的DS3數(shù)據(jù)，數(shù)據(jù)密度分布圖如下（h=0.01985）：
參考
-
Ester M, Kriegel H-P, Sander J, Xu X. A density based algorithm for discovering clusters in large spatial databases with noise[C]. Proceedings of the 2nd ACM In ternational Conference on Knowledge Discovery and Data Mining (KDD), 1996:226-231. https://dl.acm.org/doi/10.5555/3001460.3001507
-
Ankerst M, Breunig MM, Kriegel H-P, Sander J. OPTICS: ordering points to identify the clustering structure[C]. Proceedings of the ACM International Conference on Management of Data (SIGMOD), 1999:49–60. DOI:https://doi.org/10.1145/304181.304187
-
Hinneburg A, Keim DA. An efficient approach to clustering in large multimedia databases with noise[C]. Proceedings of the 4th ACM International Conference on Knowledge Discovery and Data Mining (KDD), 1998:58-65. https://dl.acm.org/doi/10.5555/3000292.3000302
-
Campello, RJGB, Kröger, P, Sander, J, Zimek, A. Density‐based clustering[J]. WIREs Data Mining Knowl Discov. 2020, 10(2):e1343. DOI:https://doi.org/10.1002/widm.1343
-
George Karypis, Eui-Hong (Sam) Han, and Vipin Kumar. 1999. Chameleon: Hierarchical Clustering Using Dynamic Modeling[J]. Computer, 1999, 32(8):68–75. DOI:https://doi.org/10.1109/2.781637
