基本概念

• 核心點：若某個點的密度達到算法設定的閾值，即ε-鄰域內點的數量（包括自己）不小于minPts，則該點為核心點。

• 邊界點：在ε-鄰域內點的數量小于minPts，但是落在核心點鄰域內的點。

• 噪聲點：不屬于任何一個簇的點，從任何一個核心點出發都是密度不可達的。

• ε-鄰域：設定的半徑r。

• 直接密度可達：若某點p在點q的r鄰域內，且q是核心點，則稱p從q出發是直接密度可達的。

• 密度可達：若有一個點的序列q0、q1...qk，對任意q0-qi-qk是直接密度可達的，則稱從q0到qk密度可達，這實際上是直接密度可達的傳播。

• 密度相連：若從某核心點p出發，點q和點k都是密度可達的，則稱點q和點k是密度相連的。

如果p是核心點，則它與所有由它可達的點（包括核心點和邊界點）形成一個簇，每個簇擁有最少一個核心點，邊界點也可以是簇的一部分，但它在簇的邊緣位置，因為它不能到達更多的點。在DBSCAN里，簇可以理解為被低密度區域分隔開的稠密對象區域，DBSCAN將具有足夠高密度的區域劃分為簇，并在具有噪聲的空間數據中發現任意形狀的簇。

執行過程

DBSCAN通過檢查空間數據中每點的鄰域來搜索簇。

如果點p的鄰域包含的點多于minPts，則創建一個以p為核心點的新簇，然后，DBSCAN迭代地聚集從這些核心點密度可達的對象，這個過程可能涉及一些密度可達簇的合并，當沒有新的點可以添加到任何簇時，該過程結束。

具體步驟

• 根據?尋找每個點的鄰域，找出核心點；
• 對于每一個核心點，如果這個核心點未被分配到某一個簇時，創建一個新的簇；
• 尋找這個核心點所有鄰域點，并循環尋找這些鄰域點相應的鄰域點，將所有這些點分配到同一個簇；
• 重復以上三步，直到左右核心點都被分配。對于不屬于任何簇的點即為噪聲點。

參數選擇

半徑r：根據k距離來設定。

首先選中一個點，計算它和所有其它點的距離，從小到大排序為d1、d2、d3...，假如d3和d4之間的差異很大，就可以認為d1到d3之間的距離是合適的，將其設為半徑。

minPts：一般可通過多次嘗試設置。

優缺點

優點

• 不需要指定簇個數；

• 可以發現任意形狀的簇；

• 擅長找到離群點（檢測任務）；

• 僅需兩個參數。

缺點

• 不適用于高維數據；

• 參數對結果影響非常大；

• sklearn中效率很慢（可以應用數據削減策略）。

算法可視化演示

DBSCAN的可視化演示