DBSCAN - 维基百科，自由的百科全书

机器学习与数据挖掘
范式 监督学习 無監督學習 線上機器學習 元学习（英语：Meta-learning (computer science)） 半监督学习 自监督学习 强化学习 基于规则的机器学习（英语：Rule-based machine learning） 量子機器學習
问题 统计分类 生成模型 迴歸分析 聚类分析 降维 密度估计（英语：density estimation） 异常检测 数据清洗 自动机器学习 关联规则学习 語意分析 结构预测（英语：Structured prediction） 特征工程 表征学习 排序学习（英语：Learning to rank） 语法归纳（英语：Grammar induction） 本体学习（英语：Ontology learning） 多模态学习（英语：Multimodal learning）
监督学习 (分类 · 回归) 学徒学习（英语：Apprenticeship learning） 决策树学习 集成学习 Bagging 提升方法 随机森林 k-NN 線性回歸 朴素贝叶斯 人工神经网络 邏輯斯諦迴歸 感知器 相关向量机（RVM） 支持向量机（SVM） 迁移学习 微调
聚类分析 BIRCH CURE算法（英语：CURE algorithm） 层次 k-平均 Fuzzy 期望最大化（EM） DBSCAN OPTICS 均值飘移（英语：Mean shift）
降维 因素分析 CCA ICA LDA NMF（英语：Non-negative matrix factorization） PCA PGD（英语：Proper generalized decomposition） t-SNE（英语：t-distributed stochastic neighbor embedding） SDL
结构预测（英语：Structured prediction） 圖模式 貝氏網路 條件隨機域 隐马尔可夫模型
异常检测 RANSAC k-NN 局部异常因子（英语：Local outlier factor） 孤立森林（英语：Isolation forest）
人工神经网络 自编码器 認知計算 深度学习 DeepDream（英语：DeepDream） 多层感知器 RNN LSTM GRU（英语：Gated recurrent unit） ESN（英语：Echo state network） 储备池计算（英语：reservoir computing） 受限玻尔兹曼机 GAN SOM CNN U-Net Transformer Vision transformer（英语：Vision transformer） 脉冲神经网络（英语：Spiking neural network） Memtransistor（英语：Memtransistor） 电化学RAM（英语：Electrochemical RAM）（ECRAM）
强化学习 Q学习 SARSA 时序差分（TD） 多智能体（英语：Multi-agent reinforcement learning） Self-play（英语：Self-play (reinforcement learning technique)） RLHF
与人类学习 主动学习（英语：Active learning (machine learning)） 众包 Human-in-the-loop（英语：Human-in-the-loop）
模型诊断 学习曲线（英语：Learning curve (machine learning)）
数学基础 内核机器（英语：Kernel machines） 偏差–方差困境（英语：Bias–variance tradeoff） 计算学习理论（英语：Computational learning theory） 经验风险最小化 奥卡姆学习（英语：Occam learning） PAC学习（英语：Probably approximately correct learning） 统计学习 VC理论
大会与出版物 NeurIPS ICML（英语：International Conference on Machine Learning） ICLR ML（英语：Machine Learning (journal)） JMLR（英语：Journal of Machine Learning Research）
相关条目 人工智能术语（英语：Glossary of artificial intelligence） 机器学习研究数据集列表（英语：List of datasets for machine-learning research） 机器学习概要（英语：Outline of machine learning）
查 论 编

DBSCAN（英語：Density-based spatial clustering of applications with noise），是1996年由馬丁·愛胥特（英语：Martin Ester）、漢斯-彼得·克里戈爾、約爾格·桑德（Jörg Sander）及Xiaowei Xu提出的聚類分析算法， 這個算法是以密度為本的：給定某空間裡的一個點集合，這算法能把附近的點分成一組（有很多相鄰點的點），並標記出位於低密度區域的局外點（最接近它的點也十分遠），DBSCAN是其中一個最常用的聚類分析算法，也是其中一個科學文章中最常引用的。

在2014年，這個算法在領頭數據挖掘會議KDD上獲頒發了Test of Time award，該獎項是頒發給一些於理論及實際層面均獲得持續性的關注的算法。

考慮在某空間裡將被聚類的點集合，為了進行 DBSCAN 聚類，所有的點被分為核心點、(密度)可達點及局外點，詳請如下：

• 如果一個點 p 在距離 ε 範圍內有至少 minPts 個點(包括自己)，則這個點被稱為核心點，那些 ε 範圍內的則被稱為由 p 直接可達的。根據定義，沒有任何點是由非核心點直接可達的。
• 如果存在一條道路 p₁, ..., p_n ，有 p₁ = p和p_n = q， 且每個 p_i+1 都是由 p_i 直接可達的(道路上除了 q 以外所有點都一定是核心點)，則稱 q 是由 p 可達的。
• 所有不由任何點可達的點都被稱為局外點。

如果 p 是核心點，則它與所有由它可達的點(包括核心點和非核心點)形成一個聚類，每個聚類擁有最少一個核心點，非核心點也可以是聚類的一部分，但它是在聚類的「邊緣」位置，因為它不能達至更多的點。

「可達性」（英文：Reachability ）不是一個對稱關係，因為根據定義，沒有點是由非核心點可達的，但非核心點可以是由其他點可達的。所以為了正式地界定 DBSCAN 找出的聚類，進一步定義兩點之間的「連結性」（英文：Connectedness） ：如果存在一個點 o 使得點 p 和點 q 都是由 o 可達的，則點 p 和點 q 被稱為(密度)連結的，而連結性是一個對稱關係。

定義了連結性之後，每個聚類都符合兩個性質：

1. 一個聚類裡的每兩個點都是互相連結的；
2. 如果一個點 p 是由一個在聚類裡的點 q 可達的，那麼 p 也在 q 所屬的聚類裡。

DBSCAN 需要兩個參數：ε (eps) 和形成高密度區域所需要的最少點數 (minPts)，它由一個任意未被訪問的點開始，然後探索這個點的 ε-鄰域，如果 ε-鄰域裡有足夠的點，則建立一個新的聚類，否則這個點被標籤為雜音。注意這個點之後可能被發現在其它點的 ε-鄰域裡，而該 ε-鄰域可能有足夠的點，屆時這個點會被加入該聚類中。

如果一個點位於一個聚類的密集區域裡，它的 ε-鄰域裡的點也屬於該聚類，當這些新的點被加進聚類後，如果它(們)也在密集區域裡，它(們)的 ε-鄰域裡的點也會被加進聚類裡。這個過程將一直重覆，直至不能再加進更多的點為止，這樣，一個密度連結的聚類被完整地找出來。然後，一個未曾被訪問的點將被探索，從而發現一個新的聚類或雜音。

算法可以以下偽代碼表達，當中變數根據原本刊登時的命名：

DBSCAN(D, eps, MinPts) {    C = 0    for each point P in dataset D {       if P is visited          continue next point       mark P as visited       NeighborPts = regionQuery(P, eps)       if sizeof(NeighborPts) < MinPts          mark P as NOISE       else {          C = next cluster          expandCluster(P, NeighborPts, C, eps, MinPts)       }    } }  expandCluster(P, NeighborPts, C, eps, MinPts) {    add P to cluster C    for each point P' in NeighborPts {        if P' is not visited {          mark P' as visited          NeighborPts' = regionQuery(P', eps)          if sizeof(NeighborPts') >= MinPts             NeighborPts = NeighborPts joined with NeighborPts'       }       if P' is not yet member of any cluster          add P' to cluster C    } }  regionQuery(P, eps)    return all points within P's eps-neighborhood (including P) 

注意這個算法可以以下方式簡化：其一，"has been visited" 和 "belongs to cluster C" 可被結合起來，另外 "expandCluster" 副程式不必被抽出來，因為它只在一個位置被调用。以上算法沒有以簡化方式呈現，以反映原本出版的版本。另外，regionQuery 是否包含 P 並不重要，它等價於改變 MinPts 的值。

DBSCAN對資料庫裡的每一點進行訪問，可能多於一次（例如作為不同聚類的候選者），但在現實的考慮中，時間複雜度主要受regionQuery的调用次數影響，DBSCAN對每點都進行剛好一次调用，且如果使用了特別的編號結構，則總平均時間複雜度為${\displaystyle O(n\log {n})}$，最差時間複雜度則為${\displaystyle O(n^{2})}$。可以使用${\displaystyle O(n^{2})}$空間複雜度的距離矩陣以避免重複計算距離，但若不使用距離矩陣，DBSCAN的空間複雜度為${\displaystyle O(n)}$。

1. 相比 K-平均算法，DBSCAN 不需要預先聲明聚類數量。
2. DBSCAN 可以找出任何形狀的聚類，甚至能找出一個聚類，它包圍但不連接另一個聚類，另外，由於 MinPts 參數，single-link effect （不同聚類以一點或極幼的線相連而被當成一個聚類）能有效地被避免。
3. DBSCAN 能分辨噪音（局外點）。
4. DBSCAN 只需兩個參數，且對資料庫內的點的次序幾乎不敏感（兩個聚類之間邊緣的點有機會受次序的影響被分到不同的聚類，另外聚類的次序會受點的次序的影響）。
5. DBSCAN 被設計成能配合可加速範圍訪問的資料庫結構，例如 R*樹。
6. 如果對資料有足夠的了解，可以選擇適當的參數以獲得最佳的分類。

1. DBSCAN 并不完全是确定性的：从多个簇可到达的边界点可以是任一簇的一部分，具体取决于数据处理的顺序。对于大多数数据集和领域来说，这种情况并不经常出现，并且对聚类结果影响很小：因为核心点和噪声点都是确定性的。 DBSCAN* 是一种将边界点视为噪声的变体算法，这种方式实现了完全确定性的结果以及密度连通分量的更一致的统计解释。
2. DBSCAN 的质量取决于区域查询函数 regionQuery(P,ε) 中使用的距离度量。最常用的距离度量是欧氏距离。但是对于高维数据，由于维数灾难(Curse of dimensionality)，这个度量几乎没有用武之地，很难找到一个合适的邻域范围ε。
3. DBSCAN 无法很好地对密度差异较大的数据集进行聚类，因为此时无法为所有聚类选择合适的 minPts-ε 组合。
4. 如果对数据和规模不了解，可能很难选择合适的邻域范围ε。

• OPTICS算法：一個DBSCAN的一般化，有效地以「最大搜尋半徑」代替ε參數。
• Connected component
• 並查集

• Arlia, Domenica; Coppola, Massimo. "Experiments in Parallel Clustering with DBSCAN". Euro-Par 2001: Parallel Processing: 7th International Euro-Par Conference Manchester, UK August 28–31, 2001, Proceedings. Springer Berlin. 
• Kriegel, Hans-Peter; Kröger, Peer; Sander, Jörg; Zimek, Arthur (2011). "Density-based Clustering"（页面存档备份，存于互联网档案馆）. WIREs Data Mining and Knowledge Discovery. 1 (3): 231–240. doi:10.1002/widm.30.