当前位置：首页 > news >正文

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

news 来源：原创 2024/9/30 3:29:24

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

算法步骤：

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

下面是代码实现：

from collections import Counterimport numpy as np
from sklearn.datasets import make_blobsdef dbscan(data, eps, min_pts):# 初始化每个数据点的聚类标签为 0labels = [0] * len(data)# 聚类 idcluster_id = 0for i in range(len(data)):if labels[i] != 0:# 如果数据点已经被标记过，则跳过该点，继续下一个点continue# 获取当前点的邻居点neighbors = get_neighbors(data, i, eps)# 如果邻居点的数量小于最小邻居数量，则将当前点标记为噪声点if len(neighbors) < min_pts:labels[i] = -1else:# 否则，增加聚类 idcluster_id += 1# 将当前点标记为当前聚类 idlabels[i] = cluster_id# 扩展聚类expand_cluster(data, labels, neighbors, cluster_id, eps, min_pts)# 返回每个数据点的聚类标签return labelsdef expand_cluster(data, labels, neighbors, cluster_id, eps, min_pts):# 遍历每个邻居点for neighbor in neighbors:# 如果邻居点的标签为 -1if labels[neighbor] == -1:# 将噪声点标记为当前聚类 idlabels[neighbor] = cluster_id# 如果邻居点的标签为 0elif labels[neighbor] == 0:# 将邻居点标记为当前聚类 idlabels[neighbor] = cluster_id# 获取邻居点的邻居点new_neighbors = get_neighbors(data, neighbor, eps)# 如果新的邻居点数量满足最小邻居数量要求，则将其加入邻居列表if len(new_neighbors) >= min_pts:neighbors += new_neighborsdef get_neighbors(data, point_idx, eps):# 邻居点列表neighbors = []for i in range(len(data)):# 计算当前点与目标点之间的欧氏距离，如果距离小于邻域半径 epsif np.linalg.norm(data[i] - data[point_idx]) < eps:# 将目标点的索引加入邻居点列表neighbors.append(i)# 返回邻居点列表return neighborsnp.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))