赞
踩
目录
DBSCAN(Density-based spatial clustering of applications with noise)是一种基于密度的聚类算法。与划分和层次聚类方法不同,它将簇定义为密度相连的点的最大集合,能够把具有足够高密度的区域划分为簇。KMeans对于非球状的数据聚类效果不好,但DBSCAN可在噪声的空间数据库中发现任意形状的聚类。
首先介绍几个概念:
-邻域:对于某一对象点来说,在其半径为
的区域为
-邻域。
核心对象:对于给定的数目 ,如果一个对象的
-邻域内至少包含
个对象,那么称该对象为核心对象。
直接密度可达:给定一个集合 ,如果
是在
的
-邻域内而且
是一个核心对象,那么对象
从对象
出发是直接密度可达(
可以是核心对象也可以不是)
密度可达:如果存在一个对象链 ,
,
。如果
从
直接密度可达,那么对象
从对象
出发是直接密度可达(直接密度可达就是对象
在
的邻域内,而密度可达对象
不在
的邻域内)
密度相联:存在样本集合 中的一点
,如果对象
到对象
和对象
都是密度可达的,那么
和
密度相联。
噪声:与任何点都不可达的对象称为噪声
举个例子, 如图所示, 其中 ,圆形范围为
-邻域。由于图中红色的点的
-邻域内都存在至少四个点,因此它们都是核心对象, 并且它们都是密度可达。
由于邻域内的点少于四个因此它们不是核心对象。图中青色圈中的点是直接密度可达的。图中褐色的圈中的点是密度相联。由于
与任何点都不可达,因此它是噪声点。
首先我们通过计算所有样本的 -邻域内样本数目找出数据集中所有的核心对象,剩余的样本点暂时记为噪声点。这里的距离可以使用欧式距离也可以使用其他距离,本文采用的是欧式距离。
- def getCenters(self, train_data):
- neighbor = {}
- for i in range(len(train_data)):
- distance = self.calculateDistance(train_data[i], train_data)
- index = np.where(distance <= self.eps)[0]
- if len(index) > self.m:
- neighbor[i] = index
- return neighbor
然后我们任一选取一个未被访问的核心对象 ,开始合并与它密度相联的所有其他的点。即依次访问被选择核心对象邻域内的点
,首先判断
点是否为核心对象,如果
是核心对象,则将该点领域中的点划为
所属的簇,然后对
进行相同的操作(有点像深度优先遍历)。如果该点不是核心对象,那么访问下一个点,示意图如下。
- k = 0
- unvisited = list(range(sample_num)) # samples which are not visited
- while len(centers) > 0:
- visited = []
- visited.extend(unvisited)
- cores = list(centers.keys())
- # choose a random cluster center
- randNum = np.random.randint(0, len(cores))
- core = cores[randNum]
- core_neighbor = [] # samples in core's neighbor
- core_neighbor.append(core)
- unvisited.remove(core)
- # merege the samples density-connectivity
- while len(core_neighbor) > 0:
- Q = core_neighbor[0]
- del core_neighbor[0]
- if Q in initial_centers.keys():
- diff = [sample for sample in initial_centers[Q] if sample in unvisited]
- core_neighbor.extend(diff)
- unvisited = [sample for sample in unvisited if sample not in diff]
- k += 1
- label[k] = [val for val in visited if val not in unvisited]
- for index in label[k]:
- if index in centers.keys():
- del centers[index]

DBSCAN包括两种参数一种是领域大小它决定了样本点簇之间的距离,另一个参数是
它决定了每个簇应该包含多少个样本。对于
,我们计算每个样本到同一个领域内最近样本点的距离,并画出直方图。我们可以看到在大多数样本满足距离小于22这一条件,因此
类似的,对于 我们计算有多少个点在给定点的
领域中,画出直方图。从图中可以看出,129是第一个波谷,后面呈持续上升到776回落,因此
DBSCAN对于非球类的样本也有很好的聚类效果,但是不能很好的反映高维数据并且如果样本集的密度不均匀、聚类间距差相差很大时,聚类质量较差。最后看下聚类的效果。
根据上图可以看出,KMeans的聚类结果明显呈带状,而DBSCAN聚类结果呈环状。
本文相关代码和数据集:https://github.com/DandelionLau/MachineLearning
[1] Wikipedia, DBSCAN
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。