目录
1. DBSCAN简介
2. DBSCAN模型
2.1 相关名词
2.2聚类算法
2.3 参数选择
3. 总结与分析
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然后我们任一选取一个未被访问的核心对象 ，开始合并与它密度相联的所有其他的点。即依次访问被选择核心对象邻域内的点 ，首先判断 点是否为核心对象，如果 是核心对象，则将该点领域中的点划为 所属的簇，然后对 进行相同的操作（有点像深度优先遍历）。如果该点不是核心对象，那么访问下一个点，示意图如下。
选取核心对象A点，找出其邻域内的所有样本，都属于簇A，依次访问领域内的点访问A邻域内的点B，点B是核心对象，访问B邻域内的点
访问B领域内的点C，C属于簇A，C不是核心对象，访问B领域的其他点
访问B领域内另一个样本点D，D是核心对象，访问D领域内的点 访问E，E不是核心对象，此时没有其他点与簇A密度可达，停止簇A聚类。 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聚类效果 Sklearn DBSCAN聚类效果根据上图可以看出，KMeans的聚类结果明显呈带状，而DBSCAN聚类结果呈环状。
本文相关代码和数据集：https://github.com/DandelionLau/MachineLearning
[1] Wikipedia, DBSCAN
[2] Choosing parameters of DBSCAN algorithm
