查看“︁DBSCAN”︁的源代码

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

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

== 基礎知識 ==
考慮在某空間裡將被集群的點集合，為了進行 DBSCAN 集群，所有的點被分為''核心點''、''(密度)可達點''及''局外點''，詳請如下：
* 如果一個點 ''p'' 在距離 ''ε'' 範圍內有至少 minPts 個點(包括自己)，則這個點被稱為''核心點''，那些 ''ε'' 範圍內的則被稱為''由 p 直接可達的。''根據定義，沒有任何點是由非核心點直接可達的。
* 如果存在一條[[道路 (图论)|道路]] {{math|''p''<sub>1</sub>, ..., ''p<sub>n</sub>''}} ，有 {{math|''p''<sub>1</sub> {{=}} ''p''}}和{{math|''p<sub>n</sub>'' {{=}} ''q''}}， 且每個 {{math|''p''<sub>''i''+1</sub>}} 都是由 {{mvar|p<sub>i</sub>}} 直接可達的(道路上除了 q 以外所有點都一定是核心點)，則稱 q 是''由 p 可達的''。
* 所有不由任何點可達的點都被稱為局外點。
如果 p 是核心點，則它與所有由它可達的點(包括核心點和非核心點)形成一個集群，每個集群擁有最少一個核心點，非核心點也可以是集群的一部分，但它是在集群的「邊緣」位置，因為它不能達至更多的點。
[[File:DBSCAN-Illustration.svg|居中|缩略图|400x400像素|在這幅圖裡，minPts = 4，點 A 和其他紅色點是核心點，因為它們的 ε-鄰域（圖中紅色圓圈）裡包含最少 4 個點（包括自己），由於它們之間相互相可達，它們形成了一個集群。點 B 和點 C 不是核心點，但它們可由 A 經其他核心點可達，所以也屬於同一個集群。點 N 是局外點，它既不是核心點，又不由其他點可達。]]
「可達性」（英文：Reachability ）不是一個對稱[[关系 (数学)|關係]]，因為根據定義，沒有點是由非核心點可達的，但非核心點可以是由其他點可達的。所以為了正式地界定 DBSCAN 找出的集群，進一步定義兩點之間的「連結性」（英文：Connectedness） ：如果存在一個點 ''o'' 使得點 ''p'' 和點 ''q'' 都是由 ''o'' 可達的，則點 ''p'' 和點 ''q'' 被稱為(密度)連結的，而連結性是一個對稱關係。

定義了連結性之後，每個集群都符合兩個性質：
# 一個集群裡的每兩個點都是互相連結的；
# 如果一個點 ''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對每點都進行剛好一次调用，且如果使用了特別的編號結構，則總平均時間複雜度為<math>O(n\log{n})</math>，最差時間複雜度則為<math>O(n^2)</math>。可以使用<math>O(n^2)</math>空間複雜度的距離矩陣以避免重複計算距離，但若不使用距離矩陣，DBSCAN的空間複雜度為<math>O(n)</math>。
[[File:DBSCAN-density-data.svg|缩略图|上圖展示 DBSCAN 分辨非線性可分集群的能力，上圖所示的資料點不能被 [[K-平均算法]] 或 [[Gaussian Mixture EM clustering]] 正確或足夠好地分類。]]

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

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

== 有關文章 ==
* [[OPTICS算法]]：一個DBSCAN的一般化，有效地以「最大搜尋半徑」代替ε參數。
* [[Connected component (graph theory)|Connected component]]
* [[并查集|並查集]]

== 注意 ==
<div class="reflist" style=" list-style-type: lower-alpha;">
<references group="lower-alpha" /></div>

== 參考文獻 ==

=== 延伸閱讀 ===
* <cite class="citation conference">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''. </cite><cite class="citation conference">Springer Berlin.</cite><span class="Z3988" title="ctx_ver=Z39.88-2004&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADBSCAN&rft.atitle=Experiments+in+Parallel+Clustering+with+DBSCAN&rft.au=Coppola%2C+Massimo&rft.aufirst=Domenica&rft.aulast=Arlia&rft.btitle=Euro-Par+2001%3A+Parallel+Processing%3A+7th+International+Euro-Par+Conference+Manchester%2C+UK+August+28%9331%2C+2001%2C+Proceedings&rft.genre=conference&rft.pub=Springer+Berlin&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook">&nbsp;</span>
* <cite class="citation journal">Kriegel, Hans-Peter; Kröger, Peer; Sander, Jörg; Zimek, Arthur (2011). [http://wires.wiley.com/WileyCDA/WiresArticle/wisId-WIDM30.html "Density-based Clustering"]{{Wayback|url=http://wires.wiley.com/WileyCDA/WiresArticle/wisId-WIDM30.html |date=20161117070919 }}. </cite><cite class="citation journal">''WIREs Data Mining and Knowledge Discovery''. '''1''' (3): 231–240. [[DOI|doi]]:[[doi:10.1002/widm.30|10.1002/widm.30]].</cite><span class="Z3988" title="ctx_ver=Z39.88-2004&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADBSCAN&rft.atitle=Density-based+Clustering&rft.aufirst=Hans-Peter&rft.au=Kr%C3%B6ger%2C+Peer&rft.aulast=Kriegel&rft.au=Sander%2C+J%C3%B6rg&rft.au=Zimek%2C+Arthur&rft.date=2011&rft.genre=article&rft_id=http%3A%2F%2Fwires.wiley.com%2FWileyCDA%2FWiresArticle%2FwisId-WIDM30.html&rft_id=info%3Adoi%2F10.1002%2Fwidm.30&rft.issue=3&rft.jtitle=WIREs+Data+Mining+and+Knowledge+Discovery&rft.pages=231-240&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.volume=1">&nbsp;</span>
[[Category:数据挖掘]]