快捷導(dǎo)航

詳解DBSCAN算法原理及其Python實(shí)現(xiàn)

更新時間：2023年12月08日 09:13:12 作者：微小冷

DBSCAN,即Density-Based Spatial Clustering of Applications with Noise,基于密度的噪聲應(yīng)用空間聚類,本文將詳細(xì)介紹DBSCAN算法的原理及其Python實(shí)現(xiàn),需要的可以參考下

原理

DBSCAN，即Density-Based Spatial Clustering of Applications with Noise，基于密度的噪聲應(yīng)用空間聚類。

在DBSCAN算法中，將數(shù)據(jù)點(diǎn)分為三類：

1.核心點(diǎn)：若樣本xi的ε鄰域內(nèi)至少包含了M個點(diǎn)，則為核心點(diǎn)

2.邊界點(diǎn)：若樣本xi的ε鄰域內(nèi)包含的點(diǎn)數(shù)小于M，但在其他核心點(diǎn)的ε鄰域內(nèi)，則為邊界點(diǎn)

3.噪聲：既非核心點(diǎn)也非邊界點(diǎn)則為噪聲

那么，在實(shí)際實(shí)現(xiàn)DBSCAN算法時，對這三種點(diǎn)理應(yīng)采取不同的操作

1.若一個點(diǎn)是核心點(diǎn)，那么應(yīng)該窮盡所有與其相連接的邊界點(diǎn)，再得到與邊界點(diǎn)相連接的所有點(diǎn)，知道遍歷完整個點(diǎn)集。

2.若一個點(diǎn)是邊界點(diǎn)，若這個點(diǎn)尚未歸類；若已經(jīng)歸類，則如1中所說，繼續(xù)搜索與其相連的點(diǎn)。

3.若為噪聲，則直接跳過。

可見，DBSCAN算法需要兩個參數(shù)，分別是鄰域半徑ε和點(diǎn)數(shù)M。

Python實(shí)現(xiàn)

為了衡量兩點(diǎn)之間的距離，計(jì)算一個距離矩陣以備調(diào)用，可以降低計(jì)算次數(shù)。對于一組點(diǎn)集data，其歐氏距離矩陣的求解方法如下

# 距離矩陣
def disMat(data):
    arr = np.array(data)
    dMat = lambda arr : arr.reshape(1,-1) - arr.reshape(-1,1)
    # 此為單個軸的距離矩陣
    mats = [dMat(arr[:,i]) for i in range(arr.shape[1])]
    return np.linalg.norm(mats, axis=0)

其中，dMat用于求解一維向量的距離矩陣。

下面則是基于距離矩陣的DBSCAN算法。

import numpy as np

class DBSCAN(object):
    # e 最小距離, minPts 最少樣本數(shù)量
    def __init__(self, e, minPts):
        self.e = e
        self.minPts = minPts

    # 獲取點(diǎn)id的臨近點(diǎn)
    def nearby(self, id):
        return np.where(self.mat[id] <= self.e)[0]

    def searchNearbyPts(self, points, group):
        for id in points:
            if id not in self.data:
                continue

            group.append(id)
            self.data.remove(id)

            # 查看id點(diǎn)的臨近點(diǎn)
            nearbyPts = self.nearby(id)
            if len(nearbyPts) >= self.minPts:
                self.searchNearbyPts(nearbyPts, group)

    def fit(self, mat):
        self.mat = mat
        groups = list()

        keys = range(mat.shape[0])
        self.data = list(keys)

        for id in keys:
            if id not in self.data:
                continue

            # id點(diǎn)的臨近點(diǎn)
            nearbyPts = self.nearby(id)
            if len(nearbyPts) < self.minPts:
                continue

            group = [id]
            self.data.remove(id)
            self.searchNearbyPts(nearbyPts, group)
            groups.append(group)

        # 加入飛點(diǎn)
        groups += self.data
        return groups

在上面的DBSCAN類中，fit相當(dāng)于執(zhí)行聚類的開關(guān)，其輸入?yún)?shù)mat是點(diǎn)集的距離矩陣。

self.data是點(diǎn)的序號的列表。其中的for循環(huán)是DBSCAN算法的核心部分，其基本邏輯是，如果一個點(diǎn)已經(jīng)被歸類了，那么就從self.data中刪除；如果這個點(diǎn)恰好又是核心點(diǎn)，那么就要搜尋其所有的鄰近點(diǎn)。

函數(shù)nearby用于查找序號為id的點(diǎn)的所有臨近點(diǎn)，searchNearbyPts則將某點(diǎn)的所有臨近點(diǎn)進(jìn)行歸類。

驗(yàn)證

其數(shù)據(jù)生成、繪圖代碼如下所示

# 初始化數(shù)據(jù)
def initData(num, min, max):
    return [np.random.randint(min, max, size=2) for _ in range(num)]

def drawRes(data, groups):
    for gp in groups:
        xy = np.array([data[i] for i in gp])
        plt.scatter(xy[:,0], xy[:,1])
    plt.title(u'DBSCAN')
    plt.grid()
    plt.tight_layout()
    plt.show()

if __name__ == '__main__':
    np.random.seed(42)
    ds1 = initData(20, 0, 30)
    ds2 = initData(20, 40, 60)
    ds3 = initData(20, 70, 100)
    ds = ds1 + ds2 + ds3

    score_mat = disMat(ds)

    groups = DBSCAN(20, 3).fit(score_mat)
    drawRes(ds, groups)

聚類結(jié)果為