概念
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)
