戰(zhàn)：從原理到調(diào)參的完整指南)
1. 為什么DBSCAN至今仍是聚類算法里的“萬金油”做數(shù)據(jù)分析和挖掘的朋友大概率都經(jīng)歷過這樣的場景手里攥著一份用戶行為數(shù)據(jù)或者傳感器采集數(shù)據(jù)想按相似度把樣本分成幾堆結(jié)果用K-Means跑出來的結(jié)果怎么看怎么別扭——有的簇被硬生生劈成兩半有的明顯該分開的樣本又被強(qiáng)行捏在一起更頭疼的是那些孤零零的離群點(diǎn)全被塞進(jìn)了某個簇里把整個簇的中心都帶偏了。這時(shí)候DBSCAN就該登場了。它的全稱是Density-Based Spatial Clustering of Applications with Noise翻譯過來就是“基于密度的帶噪聲應(yīng)用空間聚類”。名字聽著唬人但核心思想特別樸素一堆挨得近的點(diǎn)算一個簇孤零零沒鄰居的點(diǎn)就是噪聲。就這么簡單一個邏輯卻解決了K-Means搞不定的三大難題——不用提前指定簇的數(shù)量、能發(fā)現(xiàn)任意形狀的簇、能自動識別并剔除噪聲點(diǎn)。我第一次在生產(chǎn)環(huán)境里用DBSCAN是處理一批GPS軌跡點(diǎn)。那批數(shù)據(jù)里混著大量定位漂移產(chǎn)生的“飛點(diǎn)”用K-Means跑完飛點(diǎn)把好幾個簇的質(zhì)心拽得偏離了真實(shí)路徑。換成DBSCAN之后飛點(diǎn)直接被標(biāo)記為噪聲剩下的軌跡點(diǎn)自動聚成了幾條清晰的路線效果立竿見影。從那以后凡是遇到“簇形狀不規(guī)則”或者“噪聲多”的場景我第一個想到的就是它。這篇文章面向的讀者很明確如果你已經(jīng)了解聚類的基本概念用過或者聽說過K-Means但還沒真正把DBSCAN跑起來或者跑起來了但參數(shù)調(diào)不明白、結(jié)果時(shí)好時(shí)壞那接下來的內(nèi)容就是為你準(zhǔn)備的。我會從算法原理講起把每個參數(shù)掰開揉碎然后給出一份可以直接復(fù)制運(yùn)行的源碼最后分享我在實(shí)際項(xiàng)目里踩過的坑和總結(jié)出來的調(diào)參經(jīng)驗(yàn)。全程不拽公式用生活化的類比把事兒說清楚。2. DBSCAN的核心概念拆解三個參數(shù)撐起整個算法2.1 從“串門”理解鄰域與密度要搞懂DBSCAN先得理解它怎么定義“密度”。你可以把數(shù)據(jù)集里的每個點(diǎn)想象成住在一個小區(qū)里的住戶每個住戶都有一個“串門半徑”也就是參數(shù)Epsε。以某個住戶為中心畫一個半徑為Eps的圓圓里住著的其他住戶就是它的“鄰居”。鄰居的數(shù)量就是參數(shù)MinPts要管的事兒。如果某個住戶的鄰居數(shù)量大于等于MinPts那這個住戶就是“核心住戶”它所在的區(qū)域就算“高密度區(qū)”。核心住戶的鄰居里如果也有核心住戶那它們就手拉手連成一片形成一個簇。那些鄰居數(shù)量不夠、但恰好住在核心住戶的圈里的叫“邊界住戶”它們被拉進(jìn)簇里但不擴(kuò)大簇的范圍。至于那些既不是核心、也不在任何核心住戶圈里的就是“噪聲住戶”直接被踢出局。這個類比里有個關(guān)鍵點(diǎn)密度是相對的由Eps和MinPts共同決定。Eps放大一點(diǎn)原來不是鄰居的點(diǎn)可能就變成鄰居了MinPts調(diào)小一點(diǎn)原來不夠格的住戶可能就成核心了。所以這兩個參數(shù)不是獨(dú)立的它們得配合著調(diào)。2.2 直接密度可達(dá)、密度可達(dá)與密度相連DBSCAN的簇?cái)U(kuò)展過程靠的是三個“可達(dá)”概念聽著像繞口令但用串門的邏輯一解釋就通了。直接密度可達(dá)住戶A是核心住戶住戶B住在A的Eps圈里那B就是直接密度可達(dá)于A的。注意方向性——A能直接到達(dá)B但B不一定能直接到達(dá)A因?yàn)锽可能不是核心住戶它的圈里沒那么多鄰居。密度可達(dá)A直接密度可達(dá)BB直接密度可達(dá)CC直接密度可達(dá)D……這樣一條鏈傳下去A就能密度可達(dá)D。這就像串門接力A認(rèn)識BB認(rèn)識CC認(rèn)識D雖然A和D住得不近但通過中間人也能扯上關(guān)系。密度相連如果存在一個住戶O使得A和B都密度可達(dá)于O那A和B就是密度相連的。這是簇的“連通性”保證——同一個簇里的任意兩個點(diǎn)都能通過某個核心點(diǎn)串起來。理解了這三個概念DBSCAN的算法流程就一句話從任意一個未訪問的核心點(diǎn)出發(fā)沿著密度可達(dá)的方向不斷擴(kuò)展把所有密度相連的點(diǎn)拉進(jìn)同一個簇直到?jīng)]有新點(diǎn)可加然后換下一個未訪問的核心點(diǎn)重復(fù)這個過程。剩下的沒被拉進(jìn)任何簇的點(diǎn)就是噪聲。2.3 為什么DBSCAN能發(fā)現(xiàn)任意形狀的簇K-Means的簇是球形的因?yàn)樗镁嚯x質(zhì)心的遠(yuǎn)近來判斷歸屬質(zhì)心一固定簇的形狀就定死了。DBSCAN不一樣它不看質(zhì)心只看密度連通性。只要一條“高密度通道”能把兩片區(qū)域連起來哪怕這個通道彎彎曲曲像條蛇DBSCAN也能把它們歸成一個簇。我做過一個實(shí)驗(yàn)生成兩個月牙形交錯的數(shù)據(jù)集K-Means跑出來直接把兩個月牙從中間切開分成了上下兩半完全錯了。DBSCAN跑出來兩個月牙各自成簇邊界清清楚楚。這就是密度連通性的威力——它不關(guān)心簇長什么樣只關(guān)心點(diǎn)與點(diǎn)之間有沒有“路”連著。3. 源碼逐行解析從零實(shí)現(xiàn)一個可用的DBSCAN3.1 數(shù)據(jù)準(zhǔn)備與距離矩陣計(jì)算先上代碼后面逐段解釋。這份實(shí)現(xiàn)不依賴任何機(jī)器學(xué)習(xí)庫只用NumPy方便你理解每一步在干什么。import numpy as np from collections import deque def dbscan(X, eps, min_pts): X: 輸入數(shù)據(jù)shape(n_samples, n_features) eps: 鄰域半徑 min_pts: 核心點(diǎn)所需的最小鄰居數(shù)含自身 返回: labels-1表示噪聲其余為簇編號 n X.shape[0] labels np.full(n, -1) # 初始化全部為噪聲 visited np.zeros(n, dtypebool) cluster_id 0 # 預(yù)計(jì)算距離矩陣歐氏距離 diff X[:, np.newaxis, :] - X[np.newaxis, :, :] dist_matrix np.sqrt((diff ** 2).sum(axis-1)) for i in range(n): if visited[i]: continue visited[i] True # 找i的鄰居 neighbors np.where(dist_matrix[i] eps)[0] if len(neighbors) min_pts: # i不是核心點(diǎn)暫時(shí)標(biāo)記為噪聲后續(xù)可能被其他核心點(diǎn)拉進(jìn)簇 labels[i] -1 else: # i是核心點(diǎn)開始擴(kuò)展簇 labels[i] cluster_id seeds deque(neighbors) # 從seeds中移除i自身 seeds deque([s for s in seeds if s ! i]) while seeds: q seeds.popleft() if not visited[q]: visited[q] True q_neighbors np.where(dist_matrix[q] eps)[0] if len(q_neighbors) min_pts: # q也是核心點(diǎn)把它的鄰居加入種子隊(duì)列 for nb in q_neighbors: if nb not in seeds: seeds.append(nb) if labels[q] -1: # q還沒被歸入任何簇拉進(jìn)來 labels[q] cluster_id cluster_id 1 return labels這段代碼的核心邏輯分三步預(yù)計(jì)算距離矩陣、遍歷每個點(diǎn)判斷核心點(diǎn)、從核心點(diǎn)出發(fā)做廣度優(yōu)先擴(kuò)展。距離矩陣用廣播機(jī)制一次性算完比循環(huán)調(diào)用距離函數(shù)快得多數(shù)據(jù)量在幾千到幾萬級別時(shí)完全夠用。3.2 核心點(diǎn)判斷與簇?cái)U(kuò)展的細(xì)節(jié)代碼里有個容易忽略的細(xì)節(jié)min_pts是包含自身的。也就是說如果一個點(diǎn)的Eps鄰域內(nèi)只有它自己那它的鄰居數(shù)就是1。如果min_pts3那它就不是核心點(diǎn)。這個設(shè)定和sklearn的DBSCAN實(shí)現(xiàn)是一致的但很多教程里會寫成“不含自身”導(dǎo)致參數(shù)對不上。我建議統(tǒng)一按“含自身”來理解調(diào)參時(shí)心里有數(shù)。簇?cái)U(kuò)展用的是廣度優(yōu)先搜索BFS用雙端隊(duì)列deque來管理種子點(diǎn)。為什么用BFS而不是DFS因?yàn)锽FS能保證同一個簇的點(diǎn)被連續(xù)處理內(nèi)存訪問更友好而且不會因?yàn)檫f歸深度過大導(dǎo)致棧溢出。數(shù)據(jù)量大的時(shí)候DFS遞歸版本很容易崩BFS是更穩(wěn)妥的選擇。還有一個邊界情況一個點(diǎn)可能先被標(biāo)記為噪聲labels[i] -1后來又被某個核心點(diǎn)的擴(kuò)展過程拉進(jìn)簇里。代碼里用if labels[q] -1來判斷只有還沒歸簇的點(diǎn)才會被重新賦值。這個邏輯保證了噪聲點(diǎn)有機(jī)會“平反”但已經(jīng)被歸入其他簇的點(diǎn)不會被搶走。3.3 參數(shù)Eps和MinPts的確定方法Eps和MinPts怎么定是DBSCAN最讓人頭疼的地方。我試過幾種方法最實(shí)用的是k-距離曲線法。具體操作對每個點(diǎn)計(jì)算它到第k個最近鄰居的距離k通常取MinPts的值然后把這些距離從小到大排序畫成曲線。曲線拐點(diǎn)最明顯的地方對應(yīng)的距離值就是比較合適的Eps。原理很簡單如果Eps選在拐點(diǎn)附近那么大部分核心點(diǎn)的鄰居數(shù)剛好夠MinPts既不會把太多噪聲拉進(jìn)來也不會把本該成簇的點(diǎn)拆散。MinPts的選取有個經(jīng)驗(yàn)法則MinPts 維度數(shù) 1。比如二維數(shù)據(jù)MinPts至少取3十維數(shù)據(jù)MinPts至少取11。維度越高M(jìn)inPts要相應(yīng)調(diào)大否則密度估計(jì)會不穩(wěn)定。另一個經(jīng)驗(yàn)是如果數(shù)據(jù)量在幾千到幾萬MinPts取4到10之間通常比較穩(wěn)。數(shù)據(jù)量特別大幾十萬以上可以適當(dāng)調(diào)大到10到20。我一般會先用k-距離曲線定一個Eps的大致范圍然后在這個范圍里取幾個值分別跑一遍看簇的數(shù)量和噪聲比例。如果噪聲比例超過30%說明Eps太小或者M(jìn)inPts太大如果所有點(diǎn)都被歸成一個簇說明Eps太大或者M(jìn)inPts太小。目標(biāo)是把噪聲比例控制在5%到15%之間簇的數(shù)量符合業(yè)務(wù)預(yù)期。4. 完整實(shí)操流程從數(shù)據(jù)加載到結(jié)果可視化4.1 生成測試數(shù)據(jù)并跑通第一個DBSCAN光看代碼不夠得跑起來才有感覺。下面這段腳本生成一組包含噪聲的月牙形數(shù)據(jù)然后調(diào)用上面的DBSCAN函數(shù)最后用Matplotlib畫出來。import numpy as np import matplotlib.pyplot as plt from sklearn.datasets import make_moons # 生成月牙形數(shù)據(jù)加一點(diǎn)噪聲 X, y_true make_moons(n_samples500, noise0.08, random_state42) # 手動添加一些離群點(diǎn) rng np.random.RandomState(42) outliers rng.uniform(low-1.5, high2.5, size(30, 2)) X np.vstack([X, outliers]) # 跑DBSCAN labels dbscan(X, eps0.25, min_pts5) # 可視化 plt.figure(figsize(10, 5)) plt.subplot(1, 2, 1) plt.scatter(X[:, 0], X[:, 1], cy_true, cmapviridis, s20) plt.title(原始數(shù)據(jù)含噪聲) plt.subplot(1, 2, 2) unique_labels set(labels) colors plt.cm.viridis(np.linspace(0, 1, len(unique_labels))) for label, color in zip(unique_labels, colors): if label -1: color red # 噪聲用紅色標(biāo)出 marker x else: marker o mask labels label plt.scatter(X[mask, 0], X[mask, 1], c[color], markermarker, s20, labelf簇{label} if label ! -1 else 噪聲) plt.title(DBSCAN聚類結(jié)果) plt.legend() plt.tight_layout() plt.show()跑完這段代碼你會看到左邊是原始數(shù)據(jù)兩個月牙交錯在一起周圍散落著一些噪聲點(diǎn)。右邊是DBSCAN的結(jié)果兩個月牙被正確分開噪聲點(diǎn)被標(biāo)成紅色叉號。如果Eps調(diào)到0.15月牙可能會被拆成更多小簇調(diào)到0.4兩個月牙可能被合并成一個簇。你可以自己動手改改參數(shù)感受一下變化。4.2 用sklearn的DBSCAN做對比驗(yàn)證自己實(shí)現(xiàn)的版本適合理解原理但生產(chǎn)環(huán)境里我一般直接用sklearn的DBSCAN因?yàn)樗隽撕芏鄡?yōu)化速度更快而且接口統(tǒng)一。下面是對比驗(yàn)證的代碼from sklearn.cluster import DBSCAN from sklearn.metrics import silhouette_score # sklearn版本 db DBSCAN(eps0.25, min_samples5) labels_sklearn db.fit_predict(X) # 對比兩個版本的結(jié)果一致性 print(f自實(shí)現(xiàn)版本簇?cái)?shù)量: {len(set(labels)) - (1 if -1 in labels else 0)}) print(fsklearn版本簇?cái)?shù)量: {len(set(labels_sklearn)) - (1 if -1 in labels_sklearn else 0)}) print(f噪聲點(diǎn)數(shù)量自實(shí)現(xiàn): {np.sum(labels -1)}) print(f噪聲點(diǎn)數(shù)量sklearn: {np.sum(labels_sklearn -1)}) # 計(jì)算輪廓系數(shù)排除噪聲點(diǎn) mask labels_sklearn ! -1 if len(set(labels_sklearn[mask])) 1: score silhouette_score(X[mask], labels_sklearn[mask]) print(f輪廓系數(shù)排除噪聲: {score:.3f})注意sklearn的DBSCAN里參數(shù)叫min_samples含義和我們的min_pts一樣都是含自身的。跑完對比你會發(fā)現(xiàn)兩個版本的簇?cái)?shù)量和噪聲點(diǎn)數(shù)量基本一致差異主要來自距離計(jì)算的浮點(diǎn)精度。輪廓系數(shù)能幫你判斷聚類質(zhì)量但DBSCAN的輪廓系數(shù)通常不會特別高因?yàn)榇氐男螤畈灰?guī)則輪廓系數(shù)的球形假設(shè)不成立。所以別太糾結(jié)這個指標(biāo)重點(diǎn)看業(yè)務(wù)上是否合理。4.3 高維數(shù)據(jù)下的降維與可視化DBSCAN在低維數(shù)據(jù)上表現(xiàn)很好但維度一高距離度量就失效了——所有點(diǎn)之間的距離都差不多大“密度”的概念就模糊了。我處理高維數(shù)據(jù)時(shí)一般先用PCA或者t-SNE降到2維或3維再跑DBSCAN。from sklearn.decomposition import PCA from sklearn.manifold import TSNE # 假設(shè)X_high是原始高維數(shù)據(jù) pca PCA(n_components2) X_pca pca.fit_transform(X_high) # 或者用t-SNE更慢但可視化效果更好 tsne TSNE(n_components2, perplexity30, random_state42) X_tsne tsne.fit_transform(X_high) # 在降維后的數(shù)據(jù)上跑DBSCAN labels_pca DBSCAN(eps0.5, min_samples5).fit_predict(X_pca)這里有個坑降維會丟失信息降維后的密度分布和原始空間可能不一樣。所以降維后的Eps不能直接套用原始空間的Eps得重新用k-距離曲線調(diào)。我的做法是降維只用于可視化真正的聚類還是在原始空間做或者至少在一個保留較多主成分的中間空間做比如PCA保留95%方差。5. 常見問題與排查技巧實(shí)錄5.1 參數(shù)調(diào)不對導(dǎo)致聚類失敗這是DBSCAN最常見的問題沒有之一。我整理了一個速查表覆蓋了大部分參數(shù)異常的情況現(xiàn)象可能原因排查方法調(diào)整方向所有點(diǎn)都是噪聲Eps太小或MinPts太大打印k-距離曲線看拐點(diǎn)位置增大Eps或減小MinPts所有點(diǎn)歸為一個簇Eps太大或MinPts太小檢查Eps是否大于數(shù)據(jù)整體范圍減小Eps或增大MinPts簇?cái)?shù)量過多且碎片化Eps偏小看噪聲比例是否過高適當(dāng)增大Eps噪聲比例超過30%Eps太小或MinPts太大統(tǒng)計(jì)噪聲點(diǎn)占比增大Eps或減小MinPts簇的形狀明顯被切斷Eps不夠大密度通道斷了可視化觀察簇的連通性增大Eps或減小MinPts我踩過最坑的一次是拿一份歸一化后的數(shù)據(jù)跑DBSCANEps設(shè)了0.5結(jié)果所有點(diǎn)歸成一簇。后來發(fā)現(xiàn)數(shù)據(jù)歸一化后每個維度的范圍都是0到1點(diǎn)與點(diǎn)之間的最大距離也就1.7左右Eps0.5相當(dāng)于把半個空間都圈進(jìn)去了。改成0.1之后才正常。所以跑DBSCAN之前一定要看數(shù)據(jù)的尺度該歸一化就歸一化但歸一化之后Eps要重新調(diào)。5.2 數(shù)據(jù)尺度不一致引發(fā)的密度誤判DBSCAN用距離來衡量密度如果不同維度的尺度差異很大距離計(jì)算就會被大尺度維度主導(dǎo)。比如一個維度是年齡0到100另一個維度是收入0到100000歐氏距離里收入的影響會完全蓋過年齡。這時(shí)候跑DBSCAN聚類結(jié)果基本只反映收入差異年齡信息被淹沒了。解決辦法是標(biāo)準(zhǔn)化。我一般用StandardScaler把每個維度變成均值0、方差1這樣各維度權(quán)重一致。但標(biāo)準(zhǔn)化之后Eps的物理含義就變了不能再按原始尺度的經(jīng)驗(yàn)來設(shè)。我的做法是標(biāo)準(zhǔn)化后重新畫k-距離曲線按曲線拐點(diǎn)定Eps。還有一種情況是數(shù)據(jù)里混了類別型特征。DBSCAN本身只支持?jǐn)?shù)值型距離類別型特征得先做獨(dú)熱編碼或者用其他方式轉(zhuǎn)成數(shù)值。但獨(dú)熱編碼會引入稀疏性讓距離計(jì)算變得很奇怪。我一般會把類別型特征單獨(dú)處理或者用Gower距離這類能混合處理數(shù)值和類別的方法但那就得自己改距離矩陣的計(jì)算邏輯了。5.3 大數(shù)據(jù)量下的性能瓶頸與優(yōu)化DBSCAN的時(shí)間復(fù)雜度在最壞情況下是O(n2)因?yàn)橐?jì)算所有點(diǎn)對的距離。數(shù)據(jù)量上萬之后自實(shí)現(xiàn)的版本會明顯變慢。我做過測試n10000時(shí)自實(shí)現(xiàn)版本跑一次要十幾秒sklearn版本用KD樹優(yōu)化后只要一兩秒。優(yōu)化手段有幾個用KD樹或球樹加速鄰居查詢sklearn的DBSCAN默認(rèn)就用了對數(shù)據(jù)進(jìn)行采樣先用小樣本調(diào)好參數(shù)再在全量數(shù)據(jù)上跑用MiniBatchDBSCAN這是sklearn提供的一個變體每次只用一小批數(shù)據(jù)更新簇速度更快但結(jié)果略有近似。如果數(shù)據(jù)量實(shí)在太大幾十萬以上我會考慮先用K-Means做粗聚類把數(shù)據(jù)分成若干小塊然后在每個小塊里跑DBSCAN。這樣雖然損失了全局密度信息但速度能提升一個數(shù)量級對于很多業(yè)務(wù)場景來說夠用了。5.4 噪聲點(diǎn)處理與后續(xù)分析銜接DBSCAN把噪聲點(diǎn)標(biāo)為-1這些點(diǎn)不是“沒用”而是“需要單獨(dú)分析”。我在做用戶分群時(shí)噪聲點(diǎn)往往對應(yīng)著行為異常的用戶比如刷單賬號、機(jī)器人流量。把這些點(diǎn)單獨(dú)拎出來做異常檢測經(jīng)常能挖出有價(jià)值的信息。但要注意噪聲點(diǎn)的比例不能太高。如果超過30%說明參數(shù)沒調(diào)好或者數(shù)據(jù)本身就不適合DBSCAN。這時(shí)候要么重新調(diào)參要么換算法。我一般會把噪聲比例控制在5%到15%之間這個區(qū)間里噪聲點(diǎn)既有分析價(jià)值又不會影響主要簇的質(zhì)量。還有一個銜接問題DBSCAN的簇編號是隨機(jī)的每次跑可能不一樣。如果要把聚類結(jié)果和業(yè)務(wù)標(biāo)簽做對比得先做簇匹配。我一般用簇的質(zhì)心或者主要特征來做匹配或者用匈牙利算法做最優(yōu)分配。這個步驟在報(bào)告里經(jīng)常被忽略但實(shí)際做分析時(shí)很重要。6. 幾個實(shí)戰(zhàn)場景下的參數(shù)配置參考6.1 地理坐標(biāo)數(shù)據(jù)的Eps選取處理GPS軌跡點(diǎn)時(shí)Eps的單位是“度”但度在不同緯度對應(yīng)的實(shí)際距離不一樣。我一般先把經(jīng)緯度轉(zhuǎn)成平面坐標(biāo)比如UTM投影然后用“米”作為Eps的單位。城市道路場景下Eps取50到100米比較合適對應(yīng)一個路口的范圍。MinPts取5到10對應(yīng)一個路口至少有幾輛車經(jīng)過。如果數(shù)據(jù)是稀疏的鄉(xiāng)村道路Eps要適當(dāng)放大到200到500米MinPts可以降到3到5。這個沒有固定公式得結(jié)合業(yè)務(wù)場景試。我的經(jīng)驗(yàn)是先在地圖上可視化幾個簇看看簇的覆蓋范圍是否符合預(yù)期然后反推Eps。6.2 用戶行為數(shù)據(jù)的MinPts經(jīng)驗(yàn)值用戶行為數(shù)據(jù)通常是高維的而且噪聲多。我一般先做特征選擇挑出區(qū)分度最高的幾個維度降到5維以內(nèi)再跑DBSCAN。MinPts取10到15因?yàn)橛脩粜袨閿?shù)據(jù)里“正常用戶”的密度比較高M(jìn)inPts太小會把偶然行為也當(dāng)成核心點(diǎn)。Eps的選取用k-距離曲線k取MinPts的值。如果曲線拐點(diǎn)不明顯說明數(shù)據(jù)密度分布比較均勻DBSCAN可能不太適合得考慮其他算法。我遇到過幾次這種情況最后換成了HDBSCAN它不需要指定Eps能自動適應(yīng)不同密度的簇。6.3 圖像分割中的DBSCAN變體應(yīng)用圖像分割里用DBSCAN通常是把像素的顏色、位置、紋理等特征拼成一個向量然后對像素做聚類。但像素?cái)?shù)量太大一張圖幾十萬像素直接跑DBSCAN不現(xiàn)實(shí)。我一般先用超像素分割把圖像切成幾百個小塊每個小塊提取一個特征向量再對超像素跑DBSCAN。這種場景下Eps的選取和特征尺度強(qiáng)相關(guān)。顏色特征歸一化到0到1位置特征歸一化到0到1Eps取0.1到0.2比較合適。MinPts取3到5因?yàn)槌袼乇旧硪呀?jīng)是聚合過的密度比原始像素高。7. 我踩過的坑和總結(jié)出的調(diào)參心得7.1 不要迷信k-距離曲線的拐點(diǎn)k-距離曲線是個好工具但拐點(diǎn)不一定總是明顯。我遇到過好幾次曲線平滑得像條直線根本找不到拐點(diǎn)。這時(shí)候硬找拐點(diǎn)就是自欺欺人。我的做法是如果曲線沒有明顯拐點(diǎn)就取距離分布的中位數(shù)或者70分位數(shù)作為Eps的初始值然后在這個值附近取幾個點(diǎn)試跑看哪個效果最好。還有一個坑是k-距離曲線對MinPts的取值敏感。MinPts取3和取10畫出來的曲線可能完全不一樣。我一般會畫多條曲線MinPts分別取3、5、10對比著看。如果多條曲線的拐點(diǎn)位置差不多那這個Eps就比較可靠。7.2 簇的數(shù)量不是越多越好剛開始用DBSCAN時(shí)我總想著把簇分得越細(xì)越好覺得這樣信息量更大。后來發(fā)現(xiàn)簇太多會導(dǎo)致每個簇的樣本量太小統(tǒng)計(jì)上不可靠業(yè)務(wù)上也沒法解讀。我現(xiàn)在的原則是每個簇至少要有30個樣本低于這個數(shù)的簇要么合并要么當(dāng)噪聲處理。如果跑出來的簇很多但每個都很小說明Eps太小了。適當(dāng)增大Eps讓密度通道更寬小簇會自然合并成大簇。但也不能太大否則所有點(diǎn)歸成一簇就失去了聚類的意義。這個平衡點(diǎn)得靠業(yè)務(wù)經(jīng)驗(yàn)來找。7.3 結(jié)果不穩(wěn)定時(shí)的排查思路DBSCAN的結(jié)果有時(shí)候會不穩(wěn)定——同樣的參數(shù)換一批數(shù)據(jù)或者換個隨機(jī)種子結(jié)果差異很大。這種情況通常有三個原因數(shù)據(jù)本身密度不均勻、Eps處于臨界值附近、MinPts太小導(dǎo)致核心點(diǎn)判定不穩(wěn)定。排查方法先固定MinPts把Eps在臨界值附近微調(diào)看結(jié)果變化是否劇烈。如果變化很大說明Eps選在了敏感區(qū)間得換一個更穩(wěn)的值。然后固定Eps調(diào)MinPts看核心點(diǎn)數(shù)量變化。如果MinPts加1就導(dǎo)致大量核心點(diǎn)消失說明MinPts太小了得調(diào)大。我一般會把Eps和MinPts的組合跑一個網(wǎng)格記錄每個組合下的簇?cái)?shù)量和噪聲比例然后選一個“簇?cái)?shù)量合理、噪聲比例適中、參數(shù)鄰域內(nèi)結(jié)果穩(wěn)定”的組合。這個過程有點(diǎn)繁瑣但比拍腦袋定參數(shù)靠譜得多。7.4 與業(yè)務(wù)方溝通聚類結(jié)果的技巧DBSCAN跑出來的簇業(yè)務(wù)方往往看不懂。他們習(xí)慣的是“高價(jià)值用戶”“流失用戶”這種標(biāo)簽而不是“簇0”“簇1”。所以聚類之后一定要做簇的特征分析給每個簇起個業(yè)務(wù)名字。我一般會計(jì)算每個簇在各個特征上的均值和全局均值對比找出這個簇最突出的特征。比如某個簇在“最近登錄天數(shù)”上顯著低于全局均值那就可以叫“沉默用戶”。另一個簇在“月消費(fèi)金額”上顯著高于全局均值就叫“高消費(fèi)用戶”。這樣業(yè)務(wù)方才能理解聚類結(jié)果的價(jià)值。還有一個技巧是把噪聲點(diǎn)單獨(dú)拿出來做分析往往能發(fā)現(xiàn)一些業(yè)務(wù)方之前沒注意到的異常模式。我有一次在噪聲點(diǎn)里發(fā)現(xiàn)了一批注冊后從未活躍的賬號后來查出來是批量注冊的垃圾賬號。這個發(fā)現(xiàn)比聚類本身更有價(jià)值。8. 從DBSCAN到HDBSCAN什么時(shí)候該換算法DBSCAN有個硬傷全局Eps固定無法處理密度差異很大的數(shù)據(jù)。比如一份數(shù)據(jù)里有的簇很緊密有的簇很稀疏用一個Eps去套要么緊密的簇被拆散要么稀疏的簇被合并。我遇到過好幾次這種情況調(diào)參調(diào)到懷疑人生。后來我換成了HDBSCANHierarchical DBSCAN它不需要指定Eps而是通過構(gòu)建層次化的密度樹自動找出不同密度的簇。HDBSCAN只有一個主要參數(shù)min_cluster_size控制最小簇的大小比DBSCAN好調(diào)得多。而且它能給出每個點(diǎn)的“簇成員概率”對于邊界點(diǎn)的歸屬更靈活。但HDBSCAN也不是萬能的。它的計(jì)算復(fù)雜度比DBSCAN高數(shù)據(jù)量大的時(shí)候跑得慢。而且它的結(jié)果解釋起來比DBSCAN復(fù)雜業(yè)務(wù)方接受度低一些。我的選擇策略是數(shù)據(jù)密度均勻、追求速度用DBSCAN數(shù)據(jù)密度差異大、追求效果用HDBSCAN。兩者不是替代關(guān)系而是互補(bǔ)關(guān)系。如果你還沒用過HDBSCAN我建議先從DBSCAN入手把密度聚類的核心思想吃透然后再過渡到HDBSCAN。DBSCAN的源碼實(shí)現(xiàn)能幫你理解密度可達(dá)、核心點(diǎn)、噪聲這些基礎(chǔ)概念這些概念在HDBSCAN里同樣適用。直接上HDBSCAN容易知其然不知其所以然。最后分享一個我常用的調(diào)試技巧把DBSCAN的中間結(jié)果打印出來包括每個點(diǎn)的鄰居數(shù)量、核心點(diǎn)標(biāo)記、簇?cái)U(kuò)展過程。這些信息在sklearn的接口里拿不到但自己實(shí)現(xiàn)的版本可以隨便加打印。我調(diào)試參數(shù)時(shí)會先在小樣本比如100個點(diǎn)上跑把每個點(diǎn)的處理過程都看一遍確認(rèn)邏輯沒問題了再上全量數(shù)據(jù)。這個習(xí)慣幫我省了很多時(shí)間也讓我對算法的理解更深了一層。 DBSCAN聚類算法實(shí)戰(zhàn)：從原理到調(diào)參的完整指南
1. 為什么DBSCAN至今仍是聚類算法里的“萬金油”做數(shù)據(jù)分析和挖掘的朋友大概率都經(jīng)歷過這樣的場景手里攥著一份用戶行為數(shù)據(jù)或者傳感器采集數(shù)據(jù)想按相似度把樣本分成幾堆結(jié)果用K-Means跑出來的結(jié)果怎么看怎么別扭——有的簇被硬生生劈成兩半有的明顯該分開的樣本又被強(qiáng)行捏在一起更頭疼的是那些孤零零的離群點(diǎn)全被塞進(jìn)了某個簇里把整個簇的中心都帶偏了。這時(shí)候DBSCAN就該登場了。它的全稱是Density-Based Spatial Clustering of Applications with Noise翻譯過來就是“基于密度的帶噪聲應(yīng)用空間聚類”。名字聽著唬人但核心思想特別樸素一堆挨得近的點(diǎn)算一個簇孤零零沒鄰居的點(diǎn)就是噪聲。就這么簡單一個邏輯卻解決了K-Means搞不定的三大難題——不用提前指定簇的數(shù)量、能發(fā)現(xiàn)任意形狀的簇、能自動識別并剔除噪聲點(diǎn)。我第一次在生產(chǎn)環(huán)境里用DBSCAN是處理一批GPS軌跡點(diǎn)。那批數(shù)據(jù)里混著大量定位漂移產(chǎn)生的“飛點(diǎn)”用K-Means跑完飛點(diǎn)把好幾個簇的質(zhì)心拽得偏離了真實(shí)路徑。換成DBSCAN之后飛點(diǎn)直接被標(biāo)記為噪聲剩下的軌跡點(diǎn)自動聚成了幾條清晰的路線效果立竿見影。從那以后凡是遇到“簇形狀不規(guī)則”或者“噪聲多”的場景我第一個想到的就是它。這篇文章面向的讀者很明確如果你已經(jīng)了解聚類的基本概念用過或者聽說過K-Means但還沒真正把DBSCAN跑起來或者跑起來了但參數(shù)調(diào)不明白、結(jié)果時(shí)好時(shí)壞那接下來的內(nèi)容就是為你準(zhǔn)備的。我會從算法原理講起把每個參數(shù)掰開揉碎然后給出一份可以直接復(fù)制運(yùn)行的源碼最后分享我在實(shí)際項(xiàng)目里踩過的坑和總結(jié)出來的調(diào)參經(jīng)驗(yàn)。全程不拽公式用生活化的類比把事兒說清楚。2. DBSCAN的核心概念拆解三個參數(shù)撐起整個算法2.1 從“串門”理解鄰域與密度要搞懂DBSCAN先得理解它怎么定義“密度”。你可以把數(shù)據(jù)集里的每個點(diǎn)想象成住在一個小區(qū)里的住戶每個住戶都有一個“串門半徑”也就是參數(shù)Epsε。以某個住戶為中心畫一個半徑為Eps的圓圓里住著的其他住戶就是它的“鄰居”。鄰居的數(shù)量就是參數(shù)MinPts要管的事兒。如果某個住戶的鄰居數(shù)量大于等于MinPts那這個住戶就是“核心住戶”它所在的區(qū)域就算“高密度區(qū)”。核心住戶的鄰居里如果也有核心住戶那它們就手拉手連成一片形成一個簇。那些鄰居數(shù)量不夠、但恰好住在核心住戶的圈里的叫“邊界住戶”它們被拉進(jìn)簇里但不擴(kuò)大簇的范圍。至于那些既不是核心、也不在任何核心住戶圈里的就是“噪聲住戶”直接被踢出局。這個類比里有個關(guān)鍵點(diǎn)密度是相對的由Eps和MinPts共同決定。Eps放大一點(diǎn)原來不是鄰居的點(diǎn)可能就變成鄰居了MinPts調(diào)小一點(diǎn)原來不夠格的住戶可能就成核心了。所以這兩個參數(shù)不是獨(dú)立的它們得配合著調(diào)。2.2 直接密度可達(dá)、密度可達(dá)與密度相連DBSCAN的簇?cái)U(kuò)展過程靠的是三個“可達(dá)”概念聽著像繞口令但用串門的邏輯一解釋就通了。直接密度可達(dá)住戶A是核心住戶住戶B住在A的Eps圈里那B就是直接密度可達(dá)于A的。注意方向性——A能直接到達(dá)B但B不一定能直接到達(dá)A因?yàn)锽可能不是核心住戶它的圈里沒那么多鄰居。密度可達(dá)A直接密度可達(dá)BB直接密度可達(dá)CC直接密度可達(dá)D……這樣一條鏈傳下去A就能密度可達(dá)D。這就像串門接力A認(rèn)識BB認(rèn)識CC認(rèn)識D雖然A和D住得不近但通過中間人也能扯上關(guān)系。密度相連如果存在一個住戶O使得A和B都密度可達(dá)于O那A和B就是密度相連的。這是簇的“連通性”保證——同一個簇里的任意兩個點(diǎn)都能通過某個核心點(diǎn)串起來。理解了這三個概念DBSCAN的算法流程就一句話從任意一個未訪問的核心點(diǎn)出發(fā)沿著密度可達(dá)的方向不斷擴(kuò)展把所有密度相連的點(diǎn)拉進(jìn)同一個簇直到?jīng)]有新點(diǎn)可加然后換下一個未訪問的核心點(diǎn)重復(fù)這個過程。剩下的沒被拉進(jìn)任何簇的點(diǎn)就是噪聲。2.3 為什么DBSCAN能發(fā)現(xiàn)任意形狀的簇K-Means的簇是球形的因?yàn)樗镁嚯x質(zhì)心的遠(yuǎn)近來判斷歸屬質(zhì)心一固定簇的形狀就定死了。DBSCAN不一樣它不看質(zhì)心只看密度連通性。只要一條“高密度通道”能把兩片區(qū)域連起來哪怕這個通道彎彎曲曲像條蛇DBSCAN也能把它們歸成一個簇。我做過一個實(shí)驗(yàn)生成兩個月牙形交錯的數(shù)據(jù)集K-Means跑出來直接把兩個月牙從中間切開分成了上下兩半完全錯了。DBSCAN跑出來兩個月牙各自成簇邊界清清楚楚。這就是密度連通性的威力——它不關(guān)心簇長什么樣只關(guān)心點(diǎn)與點(diǎn)之間有沒有“路”連著。3. 源碼逐行解析從零實(shí)現(xiàn)一個可用的DBSCAN3.1 數(shù)據(jù)準(zhǔn)備與距離矩陣計(jì)算先上代碼后面逐段解釋。這份實(shí)現(xiàn)不依賴任何機(jī)器學(xué)習(xí)庫只用NumPy方便你理解每一步在干什么。import numpy as np from collections import deque def dbscan(X, eps, min_pts): X: 輸入數(shù)據(jù)shape(n_samples, n_features) eps: 鄰域半徑 min_pts: 核心點(diǎn)所需的最小鄰居數(shù)含自身 返回: labels-1表示噪聲其余為簇編號 n X.shape[0] labels np.full(n, -1) # 初始化全部為噪聲 visited np.zeros(n, dtypebool) cluster_id 0 # 預(yù)計(jì)算距離矩陣歐氏距離 diff X[:, np.newaxis, :] - X[np.newaxis, :, :] dist_matrix np.sqrt((diff ** 2).sum(axis-1)) for i in range(n): if visited[i]: continue visited[i] True # 找i的鄰居 neighbors np.where(dist_matrix[i] eps)[0] if len(neighbors) min_pts: # i不是核心點(diǎn)暫時(shí)標(biāo)記為噪聲后續(xù)可能被其他核心點(diǎn)拉進(jìn)簇 labels[i] -1 else: # i是核心點(diǎn)開始擴(kuò)展簇 labels[i] cluster_id seeds deque(neighbors) # 從seeds中移除i自身 seeds deque([s for s in seeds if s ! i]) while seeds: q seeds.popleft() if not visited[q]: visited[q] True q_neighbors np.where(dist_matrix[q] eps)[0] if len(q_neighbors) min_pts: # q也是核心點(diǎn)把它的鄰居加入種子隊(duì)列 for nb in q_neighbors: if nb not in seeds: seeds.append(nb) if labels[q] -1: # q還沒被歸入任何簇拉進(jìn)來 labels[q] cluster_id cluster_id 1 return labels這段代碼的核心邏輯分三步預(yù)計(jì)算距離矩陣、遍歷每個點(diǎn)判斷核心點(diǎn)、從核心點(diǎn)出發(fā)做廣度優(yōu)先擴(kuò)展。距離矩陣用廣播機(jī)制一次性算完比循環(huán)調(diào)用距離函數(shù)快得多數(shù)據(jù)量在幾千到幾萬級別時(shí)完全夠用。3.2 核心點(diǎn)判斷與簇?cái)U(kuò)展的細(xì)節(jié)代碼里有個容易忽略的細(xì)節(jié)min_pts是包含自身的。也就是說如果一個點(diǎn)的Eps鄰域內(nèi)只有它自己那它的鄰居數(shù)就是1。如果min_pts3那它就不是核心點(diǎn)。這個設(shè)定和sklearn的DBSCAN實(shí)現(xiàn)是一致的但很多教程里會寫成“不含自身”導(dǎo)致參數(shù)對不上。我建議統(tǒng)一按“含自身”來理解調(diào)參時(shí)心里有數(shù)。簇?cái)U(kuò)展用的是廣度優(yōu)先搜索BFS用雙端隊(duì)列deque來管理種子點(diǎn)。為什么用BFS而不是DFS因?yàn)锽FS能保證同一個簇的點(diǎn)被連續(xù)處理內(nèi)存訪問更友好而且不會因?yàn)檫f歸深度過大導(dǎo)致棧溢出。數(shù)據(jù)量大的時(shí)候DFS遞歸版本很容易崩BFS是更穩(wěn)妥的選擇。還有一個邊界情況一個點(diǎn)可能先被標(biāo)記為噪聲labels[i] -1后來又被某個核心點(diǎn)的擴(kuò)展過程拉進(jìn)簇里。代碼里用if labels[q] -1來判斷只有還沒歸簇的點(diǎn)才會被重新賦值。這個邏輯保證了噪聲點(diǎn)有機(jī)會“平反”但已經(jīng)被歸入其他簇的點(diǎn)不會被搶走。3.3 參數(shù)Eps和MinPts的確定方法Eps和MinPts怎么定是DBSCAN最讓人頭疼的地方。我試過幾種方法最實(shí)用的是k-距離曲線法。具體操作對每個點(diǎn)計(jì)算它到第k個最近鄰居的距離k通常取MinPts的值然后把這些距離從小到大排序畫成曲線。曲線拐點(diǎn)最明顯的地方對應(yīng)的距離值就是比較合適的Eps。原理很簡單如果Eps選在拐點(diǎn)附近那么大部分核心點(diǎn)的鄰居數(shù)剛好夠MinPts既不會把太多噪聲拉進(jìn)來也不會把本該成簇的點(diǎn)拆散。MinPts的選取有個經(jīng)驗(yàn)法則MinPts 維度數(shù) 1。比如二維數(shù)據(jù)MinPts至少取3十維數(shù)據(jù)MinPts至少取11。維度越高M(jìn)inPts要相應(yīng)調(diào)大否則密度估計(jì)會不穩(wěn)定。另一個經(jīng)驗(yàn)是如果數(shù)據(jù)量在幾千到幾萬MinPts取4到10之間通常比較穩(wěn)。數(shù)據(jù)量特別大幾十萬以上可以適當(dāng)調(diào)大到10到20。我一般會先用k-距離曲線定一個Eps的大致范圍然后在這個范圍里取幾個值分別跑一遍看簇的數(shù)量和噪聲比例。如果噪聲比例超過30%說明Eps太小或者M(jìn)inPts太大如果所有點(diǎn)都被歸成一個簇說明Eps太大或者M(jìn)inPts太小。目標(biāo)是把噪聲比例控制在5%到15%之間簇的數(shù)量符合業(yè)務(wù)預(yù)期。4. 完整實(shí)操流程從數(shù)據(jù)加載到結(jié)果可視化4.1 生成測試數(shù)據(jù)并跑通第一個DBSCAN光看代碼不夠得跑起來才有感覺。下面這段腳本生成一組包含噪聲的月牙形數(shù)據(jù)然后調(diào)用上面的DBSCAN函數(shù)最后用Matplotlib畫出來。import numpy as np import matplotlib.pyplot as plt from sklearn.datasets import make_moons # 生成月牙形數(shù)據(jù)加一點(diǎn)噪聲 X, y_true make_moons(n_samples500, noise0.08, random_state42) # 手動添加一些離群點(diǎn) rng np.random.RandomState(42) outliers rng.uniform(low-1.5, high2.5, size(30, 2)) X np.vstack([X, outliers]) # 跑DBSCAN labels dbscan(X, eps0.25, min_pts5) # 可視化 plt.figure(figsize(10, 5)) plt.subplot(1, 2, 1) plt.scatter(X[:, 0], X[:, 1], cy_true, cmapviridis, s20) plt.title(原始數(shù)據(jù)含噪聲) plt.subplot(1, 2, 2) unique_labels set(labels) colors plt.cm.viridis(np.linspace(0, 1, len(unique_labels))) for label, color in zip(unique_labels, colors): if label -1: color red # 噪聲用紅色標(biāo)出 marker x else: marker o mask labels label plt.scatter(X[mask, 0], X[mask, 1], c[color], markermarker, s20, labelf簇{label} if label ! -1 else 噪聲) plt.title(DBSCAN聚類結(jié)果) plt.legend() plt.tight_layout() plt.show()跑完這段代碼你會看到左邊是原始數(shù)據(jù)兩個月牙交錯在一起周圍散落著一些噪聲點(diǎn)。右邊是DBSCAN的結(jié)果兩個月牙被正確分開噪聲點(diǎn)被標(biāo)成紅色叉號。如果Eps調(diào)到0.15月牙可能會被拆成更多小簇調(diào)到0.4兩個月牙可能被合并成一個簇。你可以自己動手改改參數(shù)感受一下變化。4.2 用sklearn的DBSCAN做對比驗(yàn)證自己實(shí)現(xiàn)的版本適合理解原理但生產(chǎn)環(huán)境里我一般直接用sklearn的DBSCAN因?yàn)樗隽撕芏鄡?yōu)化速度更快而且接口統(tǒng)一。下面是對比驗(yàn)證的代碼from sklearn.cluster import DBSCAN from sklearn.metrics import silhouette_score # sklearn版本 db DBSCAN(eps0.25, min_samples5) labels_sklearn db.fit_predict(X) # 對比兩個版本的結(jié)果一致性 print(f自實(shí)現(xiàn)版本簇?cái)?shù)量: {len(set(labels)) - (1 if -1 in labels else 0)}) print(fsklearn版本簇?cái)?shù)量: {len(set(labels_sklearn)) - (1 if -1 in labels_sklearn else 0)}) print(f噪聲點(diǎn)數(shù)量自實(shí)現(xiàn): {np.sum(labels -1)}) print(f噪聲點(diǎn)數(shù)量sklearn: {np.sum(labels_sklearn -1)}) # 計(jì)算輪廓系數(shù)排除噪聲點(diǎn) mask labels_sklearn ! -1 if len(set(labels_sklearn[mask])) 1: score silhouette_score(X[mask], labels_sklearn[mask]) print(f輪廓系數(shù)排除噪聲: {score:.3f})注意sklearn的DBSCAN里參數(shù)叫min_samples含義和我們的min_pts一樣都是含自身的。跑完對比你會發(fā)現(xiàn)兩個版本的簇?cái)?shù)量和噪聲點(diǎn)數(shù)量基本一致差異主要來自距離計(jì)算的浮點(diǎn)精度。輪廓系數(shù)能幫你判斷聚類質(zhì)量但DBSCAN的輪廓系數(shù)通常不會特別高因?yàn)榇氐男螤畈灰?guī)則輪廓系數(shù)的球形假設(shè)不成立。所以別太糾結(jié)這個指標(biāo)重點(diǎn)看業(yè)務(wù)上是否合理。4.3 高維數(shù)據(jù)下的降維與可視化DBSCAN在低維數(shù)據(jù)上表現(xiàn)很好但維度一高距離度量就失效了——所有點(diǎn)之間的距離都差不多大“密度”的概念就模糊了。我處理高維數(shù)據(jù)時(shí)一般先用PCA或者t-SNE降到2維或3維再跑DBSCAN。from sklearn.decomposition import PCA from sklearn.manifold import TSNE # 假設(shè)X_high是原始高維數(shù)據(jù) pca PCA(n_components2) X_pca pca.fit_transform(X_high) # 或者用t-SNE更慢但可視化效果更好 tsne TSNE(n_components2, perplexity30, random_state42) X_tsne tsne.fit_transform(X_high) # 在降維后的數(shù)據(jù)上跑DBSCAN labels_pca DBSCAN(eps0.5, min_samples5).fit_predict(X_pca)這里有個坑降維會丟失信息降維后的密度分布和原始空間可能不一樣。所以降維后的Eps不能直接套用原始空間的Eps得重新用k-距離曲線調(diào)。我的做法是降維只用于可視化真正的聚類還是在原始空間做或者至少在一個保留較多主成分的中間空間做比如PCA保留95%方差。5. 常見問題與排查技巧實(shí)錄5.1 參數(shù)調(diào)不對導(dǎo)致聚類失敗這是DBSCAN最常見的問題沒有之一。我整理了一個速查表覆蓋了大部分參數(shù)異常的情況現(xiàn)象可能原因排查方法調(diào)整方向所有點(diǎn)都是噪聲Eps太小或MinPts太大打印k-距離曲線看拐點(diǎn)位置增大Eps或減小MinPts所有點(diǎn)歸為一個簇Eps太大或MinPts太小檢查Eps是否大于數(shù)據(jù)整體范圍減小Eps或增大MinPts簇?cái)?shù)量過多且碎片化Eps偏小看噪聲比例是否過高適當(dāng)增大Eps噪聲比例超過30%Eps太小或MinPts太大統(tǒng)計(jì)噪聲點(diǎn)占比增大Eps或減小MinPts簇的形狀明顯被切斷Eps不夠大密度通道斷了可視化觀察簇的連通性增大Eps或減小MinPts我踩過最坑的一次是拿一份歸一化后的數(shù)據(jù)跑DBSCANEps設(shè)了0.5結(jié)果所有點(diǎn)歸成一簇。后來發(fā)現(xiàn)數(shù)據(jù)歸一化后每個維度的范圍都是0到1點(diǎn)與點(diǎn)之間的最大距離也就1.7左右Eps0.5相當(dāng)于把半個空間都圈進(jìn)去了。改成0.1之后才正常。所以跑DBSCAN之前一定要看數(shù)據(jù)的尺度該歸一化就歸一化但歸一化之后Eps要重新調(diào)。5.2 數(shù)據(jù)尺度不一致引發(fā)的密度誤判DBSCAN用距離來衡量密度如果不同維度的尺度差異很大距離計(jì)算就會被大尺度維度主導(dǎo)。比如一個維度是年齡0到100另一個維度是收入0到100000歐氏距離里收入的影響會完全蓋過年齡。這時(shí)候跑DBSCAN聚類結(jié)果基本只反映收入差異年齡信息被淹沒了。解決辦法是標(biāo)準(zhǔn)化。我一般用StandardScaler把每個維度變成均值0、方差1這樣各維度權(quán)重一致。但標(biāo)準(zhǔn)化之后Eps的物理含義就變了不能再按原始尺度的經(jīng)驗(yàn)來設(shè)。我的做法是標(biāo)準(zhǔn)化后重新畫k-距離曲線按曲線拐點(diǎn)定Eps。還有一種情況是數(shù)據(jù)里混了類別型特征。DBSCAN本身只支持?jǐn)?shù)值型距離類別型特征得先做獨(dú)熱編碼或者用其他方式轉(zhuǎn)成數(shù)值。但獨(dú)熱編碼會引入稀疏性讓距離計(jì)算變得很奇怪。我一般會把類別型特征單獨(dú)處理或者用Gower距離這類能混合處理數(shù)值和類別的方法但那就得自己改距離矩陣的計(jì)算邏輯了。5.3 大數(shù)據(jù)量下的性能瓶頸與優(yōu)化DBSCAN的時(shí)間復(fù)雜度在最壞情況下是O(n2)因?yàn)橐?jì)算所有點(diǎn)對的距離。數(shù)據(jù)量上萬之后自實(shí)現(xiàn)的版本會明顯變慢。我做過測試n10000時(shí)自實(shí)現(xiàn)版本跑一次要十幾秒sklearn版本用KD樹優(yōu)化后只要一兩秒。優(yōu)化手段有幾個用KD樹或球樹加速鄰居查詢sklearn的DBSCAN默認(rèn)就用了對數(shù)據(jù)進(jìn)行采樣先用小樣本調(diào)好參數(shù)再在全量數(shù)據(jù)上跑用MiniBatchDBSCAN這是sklearn提供的一個變體每次只用一小批數(shù)據(jù)更新簇速度更快但結(jié)果略有近似。如果數(shù)據(jù)量實(shí)在太大幾十萬以上我會考慮先用K-Means做粗聚類把數(shù)據(jù)分成若干小塊然后在每個小塊里跑DBSCAN。這樣雖然損失了全局密度信息但速度能提升一個數(shù)量級對于很多業(yè)務(wù)場景來說夠用了。5.4 噪聲點(diǎn)處理與后續(xù)分析銜接DBSCAN把噪聲點(diǎn)標(biāo)為-1這些點(diǎn)不是“沒用”而是“需要單獨(dú)分析”。我在做用戶分群時(shí)噪聲點(diǎn)往往對應(yīng)著行為異常的用戶比如刷單賬號、機(jī)器人流量。把這些點(diǎn)單獨(dú)拎出來做異常檢測經(jīng)常能挖出有價(jià)值的信息。但要注意噪聲點(diǎn)的比例不能太高。如果超過30%說明參數(shù)沒調(diào)好或者數(shù)據(jù)本身就不適合DBSCAN。這時(shí)候要么重新調(diào)參要么換算法。我一般會把噪聲比例控制在5%到15%之間這個區(qū)間里噪聲點(diǎn)既有分析價(jià)值又不會影響主要簇的質(zhì)量。還有一個銜接問題DBSCAN的簇編號是隨機(jī)的每次跑可能不一樣。如果要把聚類結(jié)果和業(yè)務(wù)標(biāo)簽做對比得先做簇匹配。我一般用簇的質(zhì)心或者主要特征來做匹配或者用匈牙利算法做最優(yōu)分配。這個步驟在報(bào)告里經(jīng)常被忽略但實(shí)際做分析時(shí)很重要。6. 幾個實(shí)戰(zhàn)場景下的參數(shù)配置參考6.1 地理坐標(biāo)數(shù)據(jù)的Eps選取處理GPS軌跡點(diǎn)時(shí)Eps的單位是“度”但度在不同緯度對應(yīng)的實(shí)際距離不一樣。我一般先把經(jīng)緯度轉(zhuǎn)成平面坐標(biāo)比如UTM投影然后用“米”作為Eps的單位。城市道路場景下Eps取50到100米比較合適對應(yīng)一個路口的范圍。MinPts取5到10對應(yīng)一個路口至少有幾輛車經(jīng)過。如果數(shù)據(jù)是稀疏的鄉(xiāng)村道路Eps要適當(dāng)放大到200到500米MinPts可以降到3到5。這個沒有固定公式得結(jié)合業(yè)務(wù)場景試。我的經(jīng)驗(yàn)是先在地圖上可視化幾個簇看看簇的覆蓋范圍是否符合預(yù)期然后反推Eps。6.2 用戶行為數(shù)據(jù)的MinPts經(jīng)驗(yàn)值用戶行為數(shù)據(jù)通常是高維的而且噪聲多。我一般先做特征選擇挑出區(qū)分度最高的幾個維度降到5維以內(nèi)再跑DBSCAN。MinPts取10到15因?yàn)橛脩粜袨閿?shù)據(jù)里“正常用戶”的密度比較高M(jìn)inPts太小會把偶然行為也當(dāng)成核心點(diǎn)。Eps的選取用k-距離曲線k取MinPts的值。如果曲線拐點(diǎn)不明顯說明數(shù)據(jù)密度分布比較均勻DBSCAN可能不太適合得考慮其他算法。我遇到過幾次這種情況最后換成了HDBSCAN它不需要指定Eps能自動適應(yīng)不同密度的簇。6.3 圖像分割中的DBSCAN變體應(yīng)用圖像分割里用DBSCAN通常是把像素的顏色、位置、紋理等特征拼成一個向量然后對像素做聚類。但像素?cái)?shù)量太大一張圖幾十萬像素直接跑DBSCAN不現(xiàn)實(shí)。我一般先用超像素分割把圖像切成幾百個小塊每個小塊提取一個特征向量再對超像素跑DBSCAN。這種場景下Eps的選取和特征尺度強(qiáng)相關(guān)。顏色特征歸一化到0到1位置特征歸一化到0到1Eps取0.1到0.2比較合適。MinPts取3到5因?yàn)槌袼乇旧硪呀?jīng)是聚合過的密度比原始像素高。7. 我踩過的坑和總結(jié)出的調(diào)參心得7.1 不要迷信k-距離曲線的拐點(diǎn)k-距離曲線是個好工具但拐點(diǎn)不一定總是明顯。我遇到過好幾次曲線平滑得像條直線根本找不到拐點(diǎn)。這時(shí)候硬找拐點(diǎn)就是自欺欺人。我的做法是如果曲線沒有明顯拐點(diǎn)就取距離分布的中位數(shù)或者70分位數(shù)作為Eps的初始值然后在這個值附近取幾個點(diǎn)試跑看哪個效果最好。還有一個坑是k-距離曲線對MinPts的取值敏感。MinPts取3和取10畫出來的曲線可能完全不一樣。我一般會畫多條曲線MinPts分別取3、5、10對比著看。如果多條曲線的拐點(diǎn)位置差不多那這個Eps就比較可靠。7.2 簇的數(shù)量不是越多越好剛開始用DBSCAN時(shí)我總想著把簇分得越細(xì)越好覺得這樣信息量更大。后來發(fā)現(xiàn)簇太多會導(dǎo)致每個簇的樣本量太小統(tǒng)計(jì)上不可靠業(yè)務(wù)上也沒法解讀。我現(xiàn)在的原則是每個簇至少要有30個樣本低于這個數(shù)的簇要么合并要么當(dāng)噪聲處理。如果跑出來的簇很多但每個都很小說明Eps太小了。適當(dāng)增大Eps讓密度通道更寬小簇會自然合并成大簇。但也不能太大否則所有點(diǎn)歸成一簇就失去了聚類的意義。這個平衡點(diǎn)得靠業(yè)務(wù)經(jīng)驗(yàn)來找。7.3 結(jié)果不穩(wěn)定時(shí)的排查思路DBSCAN的結(jié)果有時(shí)候會不穩(wěn)定——同樣的參數(shù)換一批數(shù)據(jù)或者換個隨機(jī)種子結(jié)果差異很大。這種情況通常有三個原因數(shù)據(jù)本身密度不均勻、Eps處于臨界值附近、MinPts太小導(dǎo)致核心點(diǎn)判定不穩(wěn)定。排查方法先固定MinPts把Eps在臨界值附近微調(diào)看結(jié)果變化是否劇烈。如果變化很大說明Eps選在了敏感區(qū)間得換一個更穩(wěn)的值。然后固定Eps調(diào)MinPts看核心點(diǎn)數(shù)量變化。如果MinPts加1就導(dǎo)致大量核心點(diǎn)消失說明MinPts太小了得調(diào)大。我一般會把Eps和MinPts的組合跑一個網(wǎng)格記錄每個組合下的簇?cái)?shù)量和噪聲比例然后選一個“簇?cái)?shù)量合理、噪聲比例適中、參數(shù)鄰域內(nèi)結(jié)果穩(wěn)定”的組合。這個過程有點(diǎn)繁瑣但比拍腦袋定參數(shù)靠譜得多。7.4 與業(yè)務(wù)方溝通聚類結(jié)果的技巧DBSCAN跑出來的簇業(yè)務(wù)方往往看不懂。他們習(xí)慣的是“高價(jià)值用戶”“流失用戶”這種標(biāo)簽而不是“簇0”“簇1”。所以聚類之后一定要做簇的特征分析給每個簇起個業(yè)務(wù)名字。我一般會計(jì)算每個簇在各個特征上的均值和全局均值對比找出這個簇最突出的特征。比如某個簇在“最近登錄天數(shù)”上顯著低于全局均值那就可以叫“沉默用戶”。另一個簇在“月消費(fèi)金額”上顯著高于全局均值就叫“高消費(fèi)用戶”。這樣業(yè)務(wù)方才能理解聚類結(jié)果的價(jià)值。還有一個技巧是把噪聲點(diǎn)單獨(dú)拿出來做分析往往能發(fā)現(xiàn)一些業(yè)務(wù)方之前沒注意到的異常模式。我有一次在噪聲點(diǎn)里發(fā)現(xiàn)了一批注冊后從未活躍的賬號后來查出來是批量注冊的垃圾賬號。這個發(fā)現(xiàn)比聚類本身更有價(jià)值。8. 從DBSCAN到HDBSCAN什么時(shí)候該換算法DBSCAN有個硬傷全局Eps固定無法處理密度差異很大的數(shù)據(jù)。比如一份數(shù)據(jù)里有的簇很緊密有的簇很稀疏用一個Eps去套要么緊密的簇被拆散要么稀疏的簇被合并。我遇到過好幾次這種情況調(diào)參調(diào)到懷疑人生。后來我換成了HDBSCANHierarchical DBSCAN它不需要指定Eps而是通過構(gòu)建層次化的密度樹自動找出不同密度的簇。HDBSCAN只有一個主要參數(shù)min_cluster_size控制最小簇的大小比DBSCAN好調(diào)得多。而且它能給出每個點(diǎn)的“簇成員概率”對于邊界點(diǎn)的歸屬更靈活。但HDBSCAN也不是萬能的。它的計(jì)算復(fù)雜度比DBSCAN高數(shù)據(jù)量大的時(shí)候跑得慢。而且它的結(jié)果解釋起來比DBSCAN復(fù)雜業(yè)務(wù)方接受度低一些。我的選擇策略是數(shù)據(jù)密度均勻、追求速度用DBSCAN數(shù)據(jù)密度差異大、追求效果用HDBSCAN。兩者不是替代關(guān)系而是互補(bǔ)關(guān)系。如果你還沒用過HDBSCAN我建議先從DBSCAN入手把密度聚類的核心思想吃透然后再過渡到HDBSCAN。DBSCAN的源碼實(shí)現(xiàn)能幫你理解密度可達(dá)、核心點(diǎn)、噪聲這些基礎(chǔ)概念這些概念在HDBSCAN里同樣適用。直接上HDBSCAN容易知其然不知其所以然。最后分享一個我常用的調(diào)試技巧把DBSCAN的中間結(jié)果打印出來包括每個點(diǎn)的鄰居數(shù)量、核心點(diǎn)標(biāo)記、簇?cái)U(kuò)展過程。這些信息在sklearn的接口里拿不到但自己實(shí)現(xiàn)的版本可以隨便加打印。我調(diào)試參數(shù)時(shí)會先在小樣本比如100個點(diǎn)上跑把每個點(diǎn)的處理過程都看一遍確認(rèn)邏輯沒問題了再上全量數(shù)據(jù)。這個習(xí)慣幫我省了很多時(shí)間也讓我對算法的理解更深了一層。