DBSCAN 原始碼解讀

語言: CN / TW / HK
時間 2021-11-02 11:16:35
主題:

DBSCAN 解讀

DBSCAN 全拼為:

A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise.

該演算法為基於密度聚類的抗噪聚類演算法.

演算法分為兩大步驟

第一大步驟:

尋找核心點形成臨時聚類簇

對應原始碼

neighbors_model = NearestNeighbors(
    radius=self.eps,
    algorithm=self.algorithm,
    leaf_size=self.leaf_size,
    metric=self.metric,
    metric_params=self.metric_params,
    p=self.p,
    n_jobs=self.n_jobs,
)

neighbors_model.fit(X)
# This has worst case O(n^2) memory complexity
neighborhoods = neighbors_model.radius_neighbors(X, return_distance=False)

解讀

掃描全部樣本點，如果某個樣本點eps半徑範圍內點數目>=min_samples，則將其納入核心點列表，並將其密度直達的點形成對應的臨時聚類簇.

第二大步驟: 合併臨時聚類簇得到聚類簇

core_samples = np.asarray(n_neighbors >= self.min_samples, dtype=np.uint8)
dbscan_inner(core_samples, neighborhoods, labels)

其中 dbscan_inner 在 _dbscan_inner.pyx (.pyx 檔案類似於 C 語言的 .c 原始碼檔案，.pyx 檔案中有 Cython 模組的原始碼 被編譯成 .c 檔案 後實現計算加速) dbscan_inner 函式計算是DBSCAN 演算法的核心 藉助【棧】 對簇的合併 深度優先搜尋從i開始,這與經典的連通計算演算法非常相似 元件，區別在於將非核心點標記為是簇的一部分，但不要擴充套件其鄰居。

while True:
    if labels[i] == -1:
        labels[i] = label_num
        if is_core[i]:
            neighb = neighborhoods[i]
            for i in range(neighb.shape[0]):
                v = neighb[i]
                if labels[v] == -1:
                    push(stack, v)

    if stack.size() == 0:
        break
    i = stack.back()
    stack.pop_back()

需要注意的問題:

  1. the parameter min_samples primarily controls how tolerant the algorithm is towards noise.the parameter eps is crucial to choose appropriately for the data set and distance function and usually cannot be left at the default value. 鄰域半徑eps和最少點數目min_samples。這兩個演算法引數控制了聚類的效果,不能用預設值.

2.the clusters to which non-core samples are assigned can differ depending on the data order. This would happen when a non-core sample has a distance lower than eps to two core samples in different clusters.

這是常被忽略的另一個問題.當以不同的順序提供資料時,聚類的結果可能不相同!詳見:http://github.com/irvingc/dbscan-on-spark/issues/19 邊界點問題:(比Kmeans 嚴重) 某樣本點到兩個核心物件的距離都小於eps,但是核心物件不是密度直達的,又不屬於同一個簇,此時應該如何確定?先進行聚類的類別會標記這個樣本成為它的類別

3.其他 metric,metric_params=None,algorithm="auto",leaf_size=30,p=2,著幾個引數決定了樣本點之間的距離計算方式,預設為歐式距離完全遍歷計算.sample_weight這個引數為對應到每個樣本的權重,預設為1,該值越大則越能促進成為核心樣本點,反之則能抑制成為核心樣本點.n_jobs 是否並行化計算.

http://blog.csdn.net/qq_35405379/article/details/103755803

http://zhuanlan.zhihu.com/p/336501183

「其他文章」
「」