python实现dbscan

python实现dbscan

原理

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个比较有代表性的基于密度的聚类算法。它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在噪声的空间数据库中发现任意形状的聚类。

DBSCAN中的几个定义：

1. Ε邻域：给定对象半径为Ε内的区域称为该对象的Ε邻域；
2. 核心对象：如果给定对象Ε邻域内的样本点数大于等于MinPts，则称该对象为核心对象；

DBSCAN 算法步骤

1. 初始化：
   从数据集中任意选择一个点 p，判断它是否为核心点（即 ε 邻域内是否包含至少 minPts 个点）。
2. 扩展簇：
   如果 p 是核心点，则开始一个新簇，将 p 及其邻域中的点加入簇中，并不断对新的核心点的邻域进行扩展。
3. 处理噪声点：
   如果一个点既不在任何簇中，也不满足成为核心点的条件，则将其标记为噪声点。
4. 重复处理：
   继续检查所有未访问的点，直到所有点都被访问为止。

python实现

从大神哪里复制过来的代码
https://github.com/lansinuote/Machine-Learning-In-Numpy/blob/master/%E6%97%A0%E7%9B%91%E7%9D%A3%E7%AF%87/5.DBSCAN/1.DBSCAN.ipynb

from sklearn.datasets import make_moons
from matplotlib import pyplot as pltimport numpy as np#加载数据
x, y = make_moons(n_samples=300, noise=0.05, random_state=42)
print(type(x))print(x)
x[0,0] = 2
x[0,1] = 2def my_dbscan(x, eps, minpts):#被访问过的放这里visited = []#被分组过的放这里grouped = []#分组结果groups = []#求一个点周围的邻居def get_neighbors(xi):diff = x - xidiff = diff**2diff = diff.sum(axis=1)diff = diff**0.5#这里的eps是超参数，是画圆的半径index = diff <= epsreturn np.where(index)[0]#获取一个没有访问过的x索引def get_unvisited_idx():for i in range(len(x)):if i not in visited:return ireturn None#从一个中心点开始扩散成一个组def build_group(i, group):#如果一个点已经被访问过，则不进行任何计算if i in visited:return#标记这个点已经被访问过了visited.append(i)#获取这个点所有的邻居neighbors = get_neighbors(x[i])#如果邻居数小于minpts，说明不是中心点，不进行任何计算if len(neighbors) < minpts:return#如果是中心点，把它加入到组中if i not in grouped:group.append(i)grouped.append(i)#遍历中心点的所有邻居，如果在它的邻居中也有中心点，则扩散for j in neighbors:#如果邻居还没有被分过组，则归入中心点的组if j not in grouped:group.append(j)grouped.append(j)build_group(j, group)#遍历直到所有点被访问while True:i = get_unvisited_idx()if i == None:break#每次重新开始扩散，是一个新的组group = []build_group(i, group)if group:groups.append(group)#结果画图predict = -1 * np.ones(len(x)) # 没有分簇的都是-1分类for i in range(len(groups)):predict[groups[i]] = ireturn predictpredict = my_dbscan(x, 0.25, 5)print(predict)
plt.scatter(x[:, 0], x[:, 1], c=predict)
plt.show()