当前位置:   article > 正文

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

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。 该参数越大,可能的噪声点会被聚类,同样的邻域半径越小,噪声点也会被分类。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家自动化/article/detail/694628
推荐阅读
相关标签
  

闽ICP备14008679号