概念

DBSCAN（Density-Based Spatial Clustering of Applications with Noise），有噪声的基于密度聚类算法。

• 将簇定义为具有足够高密度的区域；
• 可以在有噪声的空间数据中发现任意形状的聚类。

关于DBSCAN的一些定义：

• E邻域：对于给定对象，半径为Ε内的区域。
• 核心对象：E邻域内样本点数大于等于MinPts的给定对象。
• 直接密度可达：对于样本集合D，如果样本点q在p的Ε邻域内，并且p为核心对象，那么对象q从对象p直接密度可达。
• 密度可达：对于样本集合D，给定一串样本点p_1,p_2,…,p_n，p=p_1，q=p_n，假如对象p_i从p_{i-1}直接密度可达，那么对象q从对象p密度可达。
• 密度相连：存在样本集合D中的一点o，如果对象o到对象p和对象q都是密度可达的，那么p和q密度相联。

DBSCAN目的是找到密度相连对象的最大集合。

算法

伪代码

REPEAT:
    选取未处理的一个点P进行处理
    IF P是核心点
        THEN 找出P的所有密度相连的点，形成簇
    ELSE P是非核心点
        标记P为噪声
        CONTINUE
UNTIL所有点都被处理

Python代码实现

import numpy as np


def dist2D(p1, p2):
    d = np.sqrt(sum([np.power(p1[i] - p2[i], 2) for i in range(len(p1))]))
    return d


def dbscan(D, Eps, MinPts, dist):
    c = 0  # 初始化簇的个数为0
    n = len(D)  # 点的个数
    visited = np.zeros(n, dtype=int)  # 访问列表
    C = np.zeros(n, dtype=int)  # 簇号列表
    while 0 in visited:  # 当还有点未被访问到
        p = np.random.choice(np.where(visited == 0)[0].tolist())  # 随机选取未被访问到的点
        visited[p] = 1  # 标记该点被访问
        N = np.empty(0, dtype=int)  # 邻域点集
        for i in range(n):
            if dist(D[p], D[i]) <= Eps:
                N = np.append(N, i)  # 计算E邻域的点
        if len(N) < MinPts:
            C[p] = -1  # 如果E邻域的点数小于MinPts，则为非核心点（噪声）
        else:  # 否则，为核心店
            c += 1  # 新建簇号
            '''找到所有该点的密度相连的点，标记簇号'''
            C[p] = c
            while 0 in visited[N]:
                _p = np.random.choice(np.intersect1d(N, np.where(visited == 0)[0]))
                visited[_p] = 1
                _N = np.empty(0, dtype=int)
                for i in range(n):
                    if dist(D[_p], D[i]) <= Eps:
                        _N = np.append(_N, i)
                if len(_N) >= MinPts:
                    N = np.append(N, _N)
                if C[_p] == 0:
                    C[_p] = c
    return C

测试

'''
导入dbscan算法
'''
import matplotlib.pyplot as plt

data = np.loadtxt("788points.txt", dtype="float32", delimiter=",")
data_c = dbscan(data, 2, 14, dist2D)

plt.scatter([a[0] for a in data], [a[1] for a in data], c=data_c)

参考

基于密度的聚类算法DBSCAN原理与实现 - 知乎 (zhihu.com)

DBSCAN_百度百科 (baidu.com)