iPAS AI 應用規劃師 中級　科目一

DBSCAN 跑百萬筆資料慢到爆，怎麼加速？

原題 48

某數據工程師使用 DBSCAN 演算法對一份數百萬筆的高維顧客資料進行聚類分析，但發現程式執行速度極慢，甚至出現記憶體不足的情況。若要在不改變演算法核心邏輯的前提下，最有效提升其運算效率的作法為何？

白話

一位資料工程師用「DBSCAN」這個聚類演算法（也叫密度聚類，Density-Based Spatial Clustering）分析幾百萬筆顧客資料，但程式跑得極慢、記憶體還不夠用。

題目要求：不能改變演算法的核心邏輯（也就是還是用 DBSCAN 本人），但要讓它跑得更快。

問你：在這個限制下，最有效的加速方法是什麼？

點選你的答案。

← 回 50 題列表 回 iPAS 備考總覽
01　總結

一句話總結

DBSCAN 慢的根本原因是每個點都要搜尋全部鄰居；用 KD-Tree 或 Ball Tree 這類距離索引結構（Distance Index Structure），把鄰居搜尋從暴力掃描（O(n²)）降到近似對數複雜度，是在不改核心邏輯前提下最有效的加速方法。答案是 B。

02　情境

先感受問題：找鄰居要翻遍整棟大樓

「全台通」電商平台的資料工程師林小明，要用 DBSCAN 分析 300 萬筆顧客行為資料，找出高價值顧客群集。

DBSCAN 的核心動作是：對每個顧客，找出「距離在 ε 以內的所有顧客」，看看這個人附近夠不夠密集，決定要不要把他劃進一個群集。

暴力做法：找顧客 A 的鄰居，就把 A 和所有其他 299 萬 9,999 個人逐一比距離。
300 萬個人，每個人都這樣搜索一遍：大約 9 兆次比較。

這就像你住在一棟 300 萬人的大廈，要找離你 5 公尺內的鄰居，卻要從 1 樓開始逐戶敲門比距離。

DBSCAN 需要的不是換掉這個「找鄰居」的邏輯，而是要一本更好的「住戶地圖」，讓它能直接跳到附近樓層找人。

03　對照

DBSCAN 暴力搜尋的五個痛點

沒有索引結構的 DBSCAN 有以下問題：

  1. 時間複雜度 O(n²)：n 筆資料，每筆都要和其他 n-1 筆比距離。n = 300 萬時，比較次數約 4.5 × 10¹²，根本跑不完。
  2. 記憶體炸掉：如果預先計算所有點對點的距離矩陣，需要 n × n 的記憶體。300 萬筆高維資料的距離矩陣遠超伺服器 RAM 上限。
  3. 高維資料更慢：每次計算兩點距離，維度越高，計算量越大。高維顧客資料（幾十個特徵）讓每次距離計算都很耗時。
  4. 沒辦法平行化暴力搜尋：傳統暴力搜尋的鄰居查詢互相依賴，平行化效益有限。
  5. 改 ε 救不了根本問題：把 ε 縮小確實會讓每個點的鄰居變少，但搜尋範圍判斷本身仍需要掃遍全部資料，時間不會大幅改善。
04　解法

KD-Tree 和 Ball Tree：給 DBSCAN 一本更好的地圖

回到林小明的問題。解法是在跑 DBSCAN 之前，先把 300 萬筆顧客資料建成一個「空間索引」。

以 KD-Tree（K維樹）為例：把所有點按座標遞迴切割成樹狀結構，就像把大廈劃分成區域、樓層、房間。

找顧客 A 的 ε 鄰居時：
1. 先問樹：「哪些區域的最近距離比 ε 小？」
2. 只進入那些區域細查，其他區域整塊跳過。
3. 搜尋複雜度從 O(n) 降到接近 O(log n)。

Ball Tree 是 KD-Tree 的改良版：把空間劃成球形邊界而非矩形邊界，在高維度資料（超過 20 維）時比 KD-Tree 更有效率。

重點是：DBSCAN 的核心邏輯（密度判斷、連通性擴展）完全沒變，只是「找鄰居這個步驟」用了更聰明的資料結構，整體速度可以提升幾個數量級。

這就是選項 B 講的：採用高效率的距離索引結構（Distance Index Structure），例如 KD-Tree 或 Ball Tree。

技術版：KD-Tree 的構建原理與 DBSCAN 整合方式

中級考試大概率會考程式碼跟公式，所以這部分你還是要學。但如果現在學起來很痛苦，可以先跳過，等讀完其他題目回頭再來。

scikit-learn 的 DBSCAN 預設就支援 KD-Tree 和 Ball Tree，只需要指定 algorithm 參數：

from sklearn.cluster import DBSCAN
import numpy as np

# 暴力搜尋（預設，慢）
dbscan_brute = DBSCAN(eps=0.5, min_samples=5, algorithm='brute')

# 用 Ball Tree（高維資料推薦，快很多）
dbscan_ball = DBSCAN(eps=0.5, min_samples=5, algorithm='ball_tree')

# 用 KD-Tree（低維資料推薦，維度 < 20）
dbscan_kd = DBSCAN(eps=0.5, min_samples=5, algorithm='kd_tree')

X = np.random.randn(100000, 10)  # 10 萬筆，10 維
labels = dbscan_ball.fit_predict(X)

KD-Tree 的構建過程：

步驟說明
選分割軸選方差最大的那個維度
找中位數點把這個維度上的中位數點當根節點
遞迴切割左子樹放小於中位數的點，右子樹放大於的點
重複對左右子樹分別重複上述步驟，直到節點只有少量點

查詢時為什麼能跳過大量點：

查詢「顧客 A 的 ε 鄰居」時，KD-Tree 會計算查詢點到每個子樹的「最短可能距離」。如果一個子樹的最短可能距離已經 > ε，這整棵子樹裡沒有任何點在 ε 以內，直接跳過，不用逐一比較。

KD-Tree vs Ball Tree 適用情境：

# 維度 < 20：KD-Tree 快
# 維度 >= 20 或資料有非均勻分佈：Ball Tree 更好
# 極高維（> 50）：兩者都退化，考慮先用 PCA 降維

# 實際使用可以設 algorithm='auto'，sklearn 自動選擇
dbscan = DBSCAN(eps=0.5, min_samples=5, algorithm='auto')
05　陷阱

為什麼其他選項是錯的

A改用以平均連結（Average Linkage）為基礎的階層式群集法（Hierarchical Clustering）

字面在說什麼

換一個完全不同的聚類演算法，用階層式群集法（Hierarchical Clustering）來代替 DBSCAN。

為什麼不對

題目明確要求「不改變演算法核心邏輯」，換成階層式群集法就是完全換掉演算法，違反了題目條件。而且，Average Linkage 階層式群集法在大資料集上的時間複雜度是 O(n² log n)，比 DBSCAN 的暴力版 O(n²) 還慢，記憶體需求也更高（需要存整棵合併樹），完全不是加速的解決方案。

誰會選錯

知道 DBSCAN 有效能問題，想到「換個方法」就解決了。但忘記看題目的限制條件：「不改變演算法核心邏輯」。

C將 ε（Epsilon）參數調得極小，以減少鄰近點的數量

字面在說什麼

把 ε（鄰近半徑）縮到很小，這樣每個點的鄰居就很少，計算量就小了。

為什麼不對

ε 變小確實能讓每個點找到的鄰居少，但 DBSCAN 在「判斷哪些點在 ε 內」這個步驟，在暴力模式下仍然需要掃遍所有資料，沒有根本改善時間複雜度。更嚴重的是：ε 太小會讓大量點變成「雜訊點（Noise）」或讓群集碎裂，聚類結果失去意義，這是改變了分析品質，不是優化效率。

誰會選錯

直覺「鄰居少 = 計算少 = 速度快」，但忽略了「找鄰居的過程本身」才是瓶頸，而不是「找到多少鄰居」。而且調參數改變了聚類結果，不是單純的效率優化。

D在資料前處理時增加標準化後的特徵維度數

字面在說什麼

在跑 DBSCAN 之前，先把資料的特徵維度增加（例如加入更多衍生特徵），然後做標準化。

為什麼不對

維度增加只會讓問題更嚴重。DBSCAN 的效能問題本來就部分來自「高維度詛咒（Curse of Dimensionality）」：維度越高，距離計算越耗時，KD-Tree 的效率也越差。增加維度完全是反向操作。標準化（正規化特徵尺度）對 DBSCAN 的距離計算有幫助，但題目說的是「增加維度數」，這是讓速度更慢，不是加速。

誰會選錯

知道「標準化對距離類演算法很重要」，看到「標準化」兩個字就覺得有道理。但沒注意題目說的是「增加」維度數，而非降維或正規化尺度。

06　變形

同個考點下次怎麼變形

變形 1　邊界

KD-Tree 在維度很高時（例如 100 維）還有用嗎？

直覺

KD-Tree 應該在任何維度都比暴力搜尋快？

答案

不是。KD-Tree 在高維度（通常 > 20 維）會遇到「高維詛咒（Curse of Dimensionality）」：所有點的距離越來越相近，KD-Tree 無法有效剪枝（幾乎每個子樹都要查），效率退化到接近暴力搜尋。這時候 Ball Tree 稍微好一點，但根本解法是先用 PCA 降維再跑 DBSCAN。

變形 2　反例

什麼情況下暴力搜尋（Brute Force）反而比 KD-Tree 快？

直覺

KD-Tree 構建有額外開銷，資料量很小時可能划不來？

答案

正確。資料量很小（幾千筆以內），或維度極高時，KD-Tree 的構建時間和記憶體開銷可能超過它省下的查詢時間。scikit-learn 的 algorithm='auto' 在資料量小時會自動選擇暴力搜尋。

變形 3　升級版

百億筆資料規模的 DBSCAN，還有其他加速方法嗎？

直覺

KD-Tree 解決了單機問題，但百億筆根本放不進一台機器？

答案

分散式 DBSCAN（如 DBSCAN on Spark）：把資料分區，各分區先各自跑 DBSCAN，再合併邊界上的群集。另一個方向是近似 DBSCAN：用 LSH（Locality-Sensitive Hashing，局部敏感雜湊）快速找近似鄰居，犧牲少量精確度換取大幅速度提升。

變形 4　跨領域

KD-Tree 在電腦視覺裡有什麼應用？

直覺

KD-Tree 不只是聚類用的資料結構，應該在很多地方都用到？

答案

是的。在電腦視覺裡，最近鄰特徵匹配（如 SIFT 特徵配對）大量使用 KD-Tree。兩張圖片各提取幾千個特徵點，要找每個特徵的「最相似對應點」，暴力搜尋太慢，KD-Tree 可以把配對速度提升幾十倍。FLANN（Fast Library for Approximate Nearest Neighbors）就是建在 KD-Tree 之上的標準工具。

變形 5　評估指標

怎麼評估 DBSCAN 聚類結果的品質？

直覺

DBSCAN 不需要事先指定群集數，評估方法應該和 K-Means 不同？

答案

常用輪廓係數（Silhouette Score）：衡量每個點到自己群集的平均距離，和到最近其他群集的平均距離之比，值越接近 1 越好。另一個是 DBCV（Density-Based Clustering Validation）：專為密度聚類設計，考慮群集內密度均勻性，適合評估 DBSCAN 找出的非球形群集。

07　延伸

想再往下看，這 5 個

出處

iPAS 經濟部產業人才能力鑑定 ・ 114 年第二次　iPAS AI 應用規劃師 中級　科目一　第 48 題

查看官方原文 PDF

© 經濟部產業發展署。AITerms.tw 僅作教學解析使用。