DBSCAN 算法【python，机器学习，算法】

DBSCAN 即 Density of Based Spatial Clustering of Applications with Noise，带噪声的基于空间密度聚类算法。

算法步骤：

1. 初始化：
   • 首先，为每个数据点分配一个初始聚类标签，这里设为0，表示该点尚未被分配到一个聚类中。
   • 设置一个聚类ID（cluster_id），初始化为0，用于标识不同的聚类。
2. 遍历数据点：
   遍历数据集中的每个点。如果某点已经被标记（即不属于聚类0），则跳过该点。
3. 查找邻居点：
   对于每个尚未被标记的点，使用get_neighbors函数查找其ε-邻域内的所有邻居点。这通常是通过计算该点与数据集中其他点之间的欧氏距离，并比较距离与ε来实现的。
4. 处理邻居点数量：
   • 如果找到的邻居点数量小于min_pts（最小邻居数量），则将当前点标记为噪声点（标签设为-1）。
   • 如果邻居点数量大于或等于min_pts，则将该点标记为一个新的聚类（将cluster_id加1，并将该点标签设为新的cluster_id）。
5. 扩展聚类：
   • 对于每个新发现的聚类中的点（即刚被标记为当前cluster_id的点），执行expand_cluster函数以进一步扩展聚类。
   • 在expand_cluster函数中，遍历当前点的所有邻居点，并根据其标签进行处理：
     • 如果邻居点是噪声点（标签为-1），则将其标记为当前聚类（将标签改为cluster_id）。
     • 如果邻居点尚未被标记（标签为0），则将其标记为当前聚类，并递归地查找并标记其邻居点（如果其邻居点数量也满足min_pts）。
6. 返回结果：
   当所有点都被处理完毕后，算法返回每个数据点的最终聚类标签。

下面是代码实现：

from collections import Counter

import numpy as np
from sklearn.datasets import make_blobs


def dbscan(data, eps, min_pts):
	# 初始化每个数据点的聚类标签为 0
	labels = [0] * len(data)
	# 聚类 id
	cluster_id = 0

	for i in range(len(data)):
		if labels[i] != 0:
			# 如果数据点已经被标记过，则跳过该点，继续下一个点
			continue
		# 获取当前点的邻居点
		neighbors = get_neighbors(data, i, eps)

		# 如果邻居点的数量小于最小邻居数量，则将当前点标记为噪声点
		if len(neighbors) < min_pts:
			labels[i] = -1
		else:
			# 否则，增加聚类 id
			cluster_id += 1
			# 将当前点标记为当前聚类 id
			labels[i] = cluster_id
			# 扩展聚类
			expand_cluster(data, labels, neighbors, cluster_id, eps, min_pts)
	# 返回每个数据点的聚类标签
	return labels


def expand_cluster(data, labels, neighbors, cluster_id, eps, min_pts):
	# 遍历每个邻居点
	for neighbor in neighbors:
		# 如果邻居点的标签为 -1
		if labels[neighbor] == -1:
			# 将噪声点标记为当前聚类 id
			labels[neighbor] = cluster_id
		# 如果邻居点的标签为 0
		elif labels[neighbor] == 0:
			# 将邻居点标记为当前聚类 id
			labels[neighbor] = cluster_id
			# 获取邻居点的邻居点
			new_neighbors = get_neighbors(data, neighbor, eps)
			# 如果新的邻居点数量满足最小邻居数量要求，则将其加入邻居列表
			if len(new_neighbors) >= min_pts:
				neighbors += new_neighbors


def get_neighbors(data, point_idx, eps):
	# 邻居点列表
	neighbors = []
	for i in range(len(data)):
		# 计算当前点与目标点之间的欧氏距离，如果距离小于邻域半径 eps
		if np.linalg.norm(data[i] - data[point_idx]) < eps:
			# 将目标点的索引加入邻居点列表
			neighbors.append(i)
	# 返回邻居点列表
	return neighbors


np.random.seed(0)
# 生成样例数据
data, y = make_blobs(n_samples=200, centers=5, cluster_std=0.6)
print(Counter(y))

eps, min_pts = 0.6, 3
# 进行聚类
labels = dbscan(data, eps, min_pts)
print(Counter(labels))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

上述代码实现了一个简单的 DBSCAN 算法。注意，在实际应用中，你需要根据实际情况调整邻域半径参数和核心点周围最小数据点数。
一般情况下，最小数据点数取数据维度值的 2 倍数，最小取 3。 该参数越大，可能的噪声点会被聚类，同样的邻域半径越小，噪声点也会被分类。