DBSCAN 最花時間的動作是反覆問「這個點 ε 半徑內有誰？」。樸素做法是 O(N²)，資料一大就卡死；空間索引能把它降到平均 O(N log N)，而且分群結果一模一樣。
先講清楚瓶頸——不是分群邏輯複雜，而是「找鄰居」這件事被做了太多次。
DBSCAN 每處理一個點，都要回答：「以我為圓心、半徑 ε，圈住了哪些點？」最直覺（也最笨）的做法是拿這個點跟其他所有點都量一次距離。N 個點、每個都這樣做 → 大約要算 N × N ＝ N² 次距離。
| 資料量 N | 暴力搜尋約需的距離計算次數（N²） |
|---|---|
| 1,000 | 1,000,000（一百萬） |
| 10,000 | 100,000,000（一億） |
| 1,000,000 | 1,000,000,000,000（一兆） |
核心想法：先記住「誰在哪一區」，查鄰居時只看附近幾區，其他直接略過。
畫布上有 600 個點。切換上方選項、然後點畫布任一處，找出該位置 ε 半徑內的鄰居，盯著中間「距離計算次數」。
| 結構 | 怎麼切 | 適合 | sklearn 對應 |
|---|---|---|---|
| 網格 Grid | 切成邊長 ≈ ε 的方格 | 低維、密度均勻、好實作 | —（常見於自製/空間資料庫） |
| KD-Tree | 沿座標軸遞迴二分 | 低～中維度（約 ≤ 20D） | algorithm='kd_tree' |
| Ball-Tree | 用超球體包覆點 | 較高維、非歐氏距離 | algorithm='ball_tree' |
DBSCAN(eps=..., min_samples=..., algorithm='auto') 會自動依資料挑索引；想固定可指定 'kd_tree'／'ball_tree'／'brute'。leaf_size 可微調樹的查詢/記憶體取捨。高維資料建議先用 PCA／UMAP 降維再分群。
| 方法 | 平均時間複雜度 | 備註 |
|---|---|---|
| 暴力搜尋 | O(N²) | 穩定但慢；資料大就崩 |
| 空間索引（低維） | O(N log N) | 快很多，DBSCAN 加速主力 |
| 空間索引（高維） | 退化 → 接近 O(N²) | 維度詛咒，索引幾乎失效 |
先想再點開。
每個點找鄰居時都跟所有其他點算距離，整體約 O(N²)，資料量一大就吃不消。
先依位置把點建索引（網格／KD-Tree／Ball-Tree），查鄰居時只檢查與 ε 範圍重疊的區塊/分支，其餘略過，平均降到 O(N log N)。
不會。索引只加速「找鄰居」，核心/邊界/雜訊判定與最終群數完全相同。
維度詛咒讓距離趨於一致，索引篩不掉點而退化回接近暴力；對策是先降維（PCA／UMAP）。
DBSCAN 樸素實作是 O(N²),靠空間索引(KD-Tree／Ball-Tree／網格)把「找鄰居」降到平均 O(N log N),是大資料分群的效能關鍵,iPAS 中級科目三可考。重點:索引只加速鄰居查詢、不改變分群結果(核心/邊界/雜訊判定相同)。易混點:高維時索引會退化回接近暴力(維度詛咒),需先降維;sklearn 以 algorithm='auto'/'kd_tree'/'ball_tree'/'brute' 選擇。情境:百萬筆資料分群效能調校。
想練情境題與詳解 → AI 學習與考證地圖
樸素做法每個點都要和所有點算距離來找 ε 鄰居，複雜度約 O(N²)；資料量一大就非常吃 CPU 與時間。
先依位置把點建索引(網格/KD-Tree/Ball-Tree)，查鄰居時只檢查與 ε 範圍重疊的區塊或分支，平均可降到 O(N log N)。
KD-Tree 沿座標軸切分、低維度快；Ball-Tree 用超球體切分，對較高維度與非歐氏距離較穩定。
不會。索引只加速「找鄰居」這個查詢，DBSCAN 的核心/邊界/雜訊判定與最終分群完全相同。
維度一高索引會退化回接近暴力(維度詛咒)，建議先用 PCA/UMAP 降維，或改用適合高維的距離與方法。