当前位置:   article > 正文

从零实现机器学习算法(十二)DBSCAN_accord.machinelearning.cluseter.dbscanclusterer

accord.machinelearning.cluseter.dbscanclusterer

目录

1. DBSCAN简介

2. DBSCAN模型

2.1 相关名词

2.2聚类算法

2.3 参数选择

3. 总结与分析


1. DBSCAN简介

DBSCAN(Density-based spatial clustering of applications with noise)是一种基于密度的聚类算法。与划分和层次聚类方法不同,它将簇定义为密度相连的点的最大集合,能够把具有足够高密度的区域划分为簇。KMeans对于非球状的数据聚类效果不好,但DBSCAN可在噪声的空间数据库中发现任意形状的聚类。

2. DBSCAN模型

2.1 相关名词

首先介绍几个概念:

\varepsilon -邻域:对于某一对象点来说,在其半径为 \varepsilon的区域为\varepsilon -邻域。

核心对象:对于给定的数目 m ,如果一个对象的\varepsilon -邻域内至少包含 m 个对象,那么称该对象为核心对象。

直接密度可达:给定一个集合 D ,如果 P 是在 Q 的\varepsilon -邻域内而且 Q 是一个核心对象,那么对象 Q 从对象 P 出发是直接密度可达( P 可以是核心对象也可以不是)

密度可达:如果存在一个对象链 P_{1}P_{2}...P_{n} , P=P_{1} , Q=P_{n} 。如果 P_{i} 从 P_{i-1} 直接密度可达,那么对象 Q 从对象 P 出发是直接密度可达(直接密度可达就是对象 P 在 Q 的邻域内,而密度可达对象 P 不在 Q 的邻域内)

密度相联:存在样本集合 D 中的一点 O ,如果对象 O 到对象 P 和对象 Q 都是密度可达的,那么 P 和Q 密度相联。

噪声:与任何点都不可达的对象称为噪声

举个例子, 如图所示, 其中 m=4 ,圆形范围为\varepsilon -邻域。由于图中红色的点的\varepsilon -邻域内都存在至少四个点,因此它们都是核心对象, 并且它们都是密度可达。 B,C 由于邻域内的点少于四个因此它们不是核心对象。图中青色圈中的点是直接密度可达的。图中褐色的圈中的点是密度相联。由于 N 与任何点都不可达,因此它是噪声点。

 

2.2聚类算法

首先我们通过计算所有样本的\varepsilon -邻域内样本数目找出数据集中所有的核心对象,剩余的样本点暂时记为噪声点。这里的距离可以使用欧式距离也可以使用其他距离,本文采用的是欧式距离。

  1. def getCenters(self, train_data):
  2. neighbor = {}
  3. for i in range(len(train_data)):
  4. distance = self.calculateDistance(train_data[i], train_data)
  5. index = np.where(distance <= self.eps)[0]
  6. if len(index) > self.m:
  7. neighbor[i] = index
  8. return neighbor

然后我们任一选取一个未被访问的核心对象 P ,开始合并与它密度相联的所有其他的点。即依次访问被选择核心对象邻域内的点 Q ,首先判断 Q 点是否为核心对象,如果 Q 是核心对象,则将该点领域中的点划为 P 所属的簇,然后对 Q 进行相同的操作(有点像深度优先遍历)。如果该点不是核心对象,那么访问下一个点,示意图如下。

  •  选取核心对象A点,找出其邻域内的所有样本,都属于簇A,依次访问领域内的点

 

  • 访问A邻域内的点B,点B是核心对象,访问B邻域内的点

 

  • 访问B领域内的点C,C属于簇A,C不是核心对象,访问B领域的其他点

 

  • 访问B领域内另一个样本点D,D是核心对象,访问D领域内的点

  • 访问E,E不是核心对象,此时没有其他点与簇A密度可达,停止簇A聚类。

  1. k = 0
  2. unvisited = list(range(sample_num)) # samples which are not visited
  3. while len(centers) > 0:
  4. visited = []
  5. visited.extend(unvisited)
  6. cores = list(centers.keys())
  7. # choose a random cluster center
  8. randNum = np.random.randint(0, len(cores))
  9. core = cores[randNum]
  10. core_neighbor = [] # samples in core's neighbor
  11. core_neighbor.append(core)
  12. unvisited.remove(core)
  13. # merege the samples density-connectivity
  14. while len(core_neighbor) > 0:
  15. Q = core_neighbor[0]
  16. del core_neighbor[0]
  17. if Q in initial_centers.keys():
  18. diff = [sample for sample in initial_centers[Q] if sample in unvisited]
  19. core_neighbor.extend(diff)
  20. unvisited = [sample for sample in unvisited if sample not in diff]
  21. k += 1
  22. label[k] = [val for val in visited if val not in unvisited]
  23. for index in label[k]:
  24. if index in centers.keys():
  25. del centers[index]

2.3 参数选择

DBSCAN包括两种参数一种是领域大小\varepsilon它决定了样本点簇之间的距离,另一个参数是 m 它决定了每个簇应该包含多少个样本。对于 \varepsilon ,我们计算每个样本到同一个领域内最近样本点的距离,并画出直方图。我们可以看到在大多数样本满足距离小于22这一条件,因此 \varepsilon=22

Distribution of distances to the nearest neighbor of each point

类似的,对于 m 我们计算有多少个点在给定点的 \varepsilon 领域中,画出直方图。从图中可以看出,129是第一个波谷,后面呈持续上升到776回落,因此 m=129

Distribution of distances to the number of neighbors

3. 总结与分析

DBSCAN对于非球类的样本也有很好的聚类效果,但是不能很好的反映高维数据并且如果样本集的密度不均匀、聚类间距差相差很大时,聚类质量较差。最后看下聚类的效果。

  •  KMeans聚类效果

  • 本文DBSCAN聚类效果

  • Sklearn DBSCAN聚类效果 

根据上图可以看出,KMeans的聚类结果明显呈带状,而DBSCAN聚类结果呈环状。

本文相关代码和数据集:https://github.com/DandelionLau/MachineLearning

 

[1] Wikipedia, DBSCAN

[2] Choosing parameters of DBSCAN algorithm

本文内容由网友自发贡献,转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号