DBSCAN

DBSCAN"/>

DBSCAN

DBSCAN

• DBSCAN算法
• • 算法概念
  • • DBSCAN中的几个定义
    • • Ε邻域
      • 核心对象
      • 直接密度可达
      • 密度可达
      • 密度相连
    • 参数选择
    • • MinPts
      • Eps
  • 背景介绍
  • 算法步骤
  • 数据集
  • • 数据集介绍
  • 算法优缺点
  • • 优点
    • 缺点
  • 训练
  • 运行结果
  • 总结
  • 参考文献

DBSCAN算法

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个比较有代表性的基于密度的聚类算法。在这一章里，你将使用有效的数据集对dbscan聚类算法进行分析，并了解到数据挖掘中的若干重要概念。

算法概念

与划分和层次聚类方法不同，DBSCAN将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在噪声的空间数据库中发现任意形状的聚类。DBSCAN算法与k均值相反，k均值将聚类建模为靠近其中心的点集，而基于密度的方法（如DBSCAN模型聚类）则是高密度的点集。

DBSCAN中的几个定义

Ε邻域

给定对象半径为Ε内的区域称为该对象的Ε邻域，对于xj∈D，其ϵ-邻域包含样本集D中与xj的距离不大于ϵ的子样本集。即对于xj∈D，其ϵ-邻域包含样本集D中与xj的距离不大于ϵ的子样本集，即Nϵ(xj)={xi∈D|distance(xi,xj)≤ϵ}, 这个子样本集的个数记为|Nϵ(xj)|

核心对象

如果给定对象Ε邻域内的样本点数大于等于MinPts，则称该对象为核心对象。即对于任一样本xj∈D，如果其ϵ-邻域对应的Nϵ(xj)至少包含MinPts个样本，即如果|Nϵ(xj)|≥MinPts，则xj是核心对象。

直接密度可达

对于样本集合D，如果样本点q在p的Ε邻域内，并且p为核心对象，那么对象q从对象p直接密度可达。如果xi位于xj的ϵ-邻域中，且xj是核心对象，则称xi由xj密度直达。注意反之不一定成立，即此时不能说xj由xi密度直达, 除非且xi也是核心对象。

密度可达

对于样本集合D，给定一串样本点p1,p2….pn，p= p1,q= pn,假如对象pi从pi-1直接密度可达，那么对象q从对象p密度可达。对于xi和xj,如果存在样本样本序列p1,p2,…,pT,满足p1=xi,pT=xj, 且pt+1由pt密度直达，则称xj由xi密度可达。也就是说，密度可达满足传递性。此时序列中的传递样本p1,p2,…,pT−1均为核心对象，因为只有核心对象才能使其他样本密度直达。注意密度可达也不满足对称性，这个可以由密度直达的不对称性得出

密度相连

存在样本集合D中的一点o，如果对象o到对象p和对象q都是密度可达的，那么p和q密度相联。对于xi和xj,如果存在核心对象样本xk，使xi和xj均由xk密度可达，则称xi和xj密度相连。注意密度相连关系是满足对称性的。

参数选择

MinPts

这个参数不做具体要求，建议根据所选的数据量及具体的业务进行自行设定。

Eps

《Python机器学习算法》这本书上给出了一个计算公式。input:data(mat)：训练数据；MinPts(int):半径内的数据点的个数；output: eps(float):半径

def epsilon(data, MinPts):

m, n = np.shape(data)
xMax = np.max(data, 0)
xMin = np.min(data, 0)
eps = ((np.prod(xMax - xMin) * MinPts * math.gamma(0.5 * n + 1)) / (m * math.sqrt(math.pi ** n))) ** (1.0 / n)
return eps

背景介绍

首先我们选择两个参数，正数epsilon和自然数minPoints。然后，我们从数据集中选择任意点开始。如果距epsilon的距离内的minPoints个点以上（包括原始点本身），则我们将所有这些点视为“群集”的一部分。然后，我们通过检查所有新点并查看它们在epsilon距离内是否也有超过minPoints个点来扩展该群集，如果是，则以递归方式扩展该群集。
最终，我们用完了要添加到群集中的点。然后，我们选择一个新的任意点并重复该过程。现在，完全有可能我们选择的一个点在其epsilon球中少于minPoints，并且也不属于任何其他群集。如果是这种情况，则将其视为不属于任何群集的“噪声点”。
国外有一个非常有意思的网站

它可以把我们DBSCAN的迭代过程动态图画出来。其中，设置好参数，点击GO！就开始聚类了。聚类的过程会通过动态的效果展示出来，如果直接跳到最后看一下dbscan的聚类效果，就会看到一个笑脸。

算法步骤

1.DBScan需要二个参数： 扫描半径 (eps)和最小包含点数(minPts)。 任选一个未被访问(unvisited)的点开始，找出与其距离在eps之内(包括eps)的所有附近点。

2.如果 附近点的数量 ≥ minPts，则当前点与其附近点形成一个簇，并且出发点被标记为已访问(visited)。 然后递归，以相同的方法处理该簇内所有未被标记为已访问(visited)的点，从而对簇进行扩展。

3.如果 附近点的数量 < minPts，则该点暂时被标记作为噪声点。

4.如果簇充分地被扩展，即簇内的所有点被标记为已访问，然后用同样的算法去处理未被访问的点。

数据集

数据集介绍

要想训练一个好的dbscan算法，一个良好的数据集是必不可少的，本文中的数据集来源于网络。它是由788个点构成的。这个数据集能很好的训练DBSCAN算法。

此处只截取了前15行数据，详细数据集在这里

在此数据集的基础上，通过在python中导入matplotlib包，就能把算法的聚类效果通过图像的形式展示出来。

算法优缺点

优点

1.相比K-Means而言，DBSCAN算法不需要预先声明聚类数量。

2.DBSCAN算法可以对任意形状的稠密数据集进行聚类，而K-Means聚类算法一般只适用于凸数据集。

3.DBSCAN算法对数据集中的异常点不敏感，可以在聚类的同时发现异常点。

4.DBSCAN算法聚类结果相对没有偏倚，而K-Means聚类算法初始值对聚类结果有很大影响。

缺点

1.当数据的密度不均匀、间距差相差很大时，聚类质量较差，这种情况下参数MinPts和Eps的选择都很困难。

2.如果数据样本集较大时，DBSCAN算法的聚类收敛时间会相对较长。

3.DBSCAN算法把交界点视为噪音，达到完全决定性的结果。

4.调参复杂，主要需要对距离阈值eps，邻域样本数阈值MinPts联合调参，不同的参数组合对最后的聚类效果有较大影响。

训练

1、导入我们需要的库

#导入我们需要的库
import numpy as np
import math
import matplotlib.pyplot as plt

2、导入数据

#根据路径file_path找到文件所在位置，并打开数据文件
#将数据文件中存储的文本信息转换为向量然后传出。
def load_data(file_path):f = open(file_path)data = []for line in f.readlines():tmp = []lines = line.strip().split(",")for k in lines:tmp.append(float(k.strip()))data.append(tmp)f.close()return np.mat(data)

3、计算半径

#参数 data: 数据文件中的样本数据
#参数 MinPts: 半径内的所有数据点的个数总和
#return: r: r定义为半径
def radius(data, MinPts):m, n = np.shape(data)#m:样本个数；n:特征的维度Mymax_data = np.max(data, 0)#找到最大与最小的样本Mymin_data = np.min(data, 0)r = ((np.prod(Mymax_data - Mymin_data) * MinPts * math.gamma(0.5 * n + 1)) / (m * math.sqrt(math.pi ** n))) ** (1.0 / n)return r

4、距离计算

#函数计算数据文件中每个点之间的距离，并返回Mydist。用来判断这个点是属于核心点、边界点还是噪音点
def distance(data):m, n = np.shape(data)Mydist = np.mat(np.zeros((m, m)))for a in range(m):for z in range(a, m):# 计算a和z之间的欧式距离tmp = 0for k in range(n):tmp += (data[a, k] - data[z, k]) * (data[a, k] - data[z, k])Mydist[a, z] = np.sqrt(tmp)Mydist[z, a] = Mydist[a, z]return Mydist

5、找到距离小于或等于r的样本的下标

#参数 distance: 存储了所有数据样本点之间距离的向量
#参数 Myradius: 定义的样本半径
#return: X:存储符合半径范围内的样本下标的向量
def find_in_radius(distance, Myradius):X = []n = np.shape(distance)[1]for j in range(n):if distance[0, j] <= Myradius:X.append(j)return X

6、DBSCAN算法

#在DBSCAN算法中，从核心对象出发，找到与该核心对象密度可达的所有样本形成“簇”。DBSCAN算法的流程为：#1.根据给定的eps和MinPts确定所有的核心对象，eps是定义密度时的邻域半径，MinPts是定义核心点时的阈值。在 DBSCAN 算法中将数据点分为3类。#（1）核心点：在其半径eps内含有超过MinPts数目的点为核心点；（2）边界点：在其半径eps内含有点的数量小于MinPts，但是落在核心点的邻域内，则为边界点。（3）噪音点：一个对点既不是核心点也不是边界点，则为噪音点。#2.对每一个核心对象，选择一个没有处理过的核心对象，找到由其密度可达的的样本生成聚类“簇”#3.重复以上过程，直到所有的点都被处理。
def dbscan(data, eps, MinPts):m = np.shape(data)[0]#m为样本个数# 区分核心点1，边界点0和噪音点-1types = np.mat(np.zeros((1, m)))#初始化，每个点的类型sub_class = np.mat(np.zeros((1, m)))#初始化，每个点所属类别# 判断该点是否处理过，0表示未处理过did = np.mat(np.zeros((m, 1)))# 计算每个数据点之间的距离dis = distance(data)# 用于标记类别number = 1# 对每一个点进行处理for i in range(m):# 找到未处理的点if did[i, 0] == 0:# 找到第i个点到其他所有点的距离D = dis[i, ]# 找到半径r内的所有点X = find_in_radius(D, eps)#X[]只存了下标# 区分点的类型# 边界点if len(X) > 1 and len(X) < MinPts + 1:types[0, i] = 0sub_class[0, i] = 0#类别为0，表示尚未处理过的# 噪音点if len(X) == 1:types[0, i] = -1sub_class[0, i] = -1did[i, 0] = 1# 核心点if len(X) >= MinPts + 1:types[0, i] = 1for x in X:sub_class[0, x] = number# 判断核心点是否密度可达while len(X) > 0:# 循环去找eps范围内的点（每个点下标都为X[0],因为处理完就会删除，相当于队列），标注相同的所属类别# 延伸出去，找到的点X[0]半径范围内的点（下标存在ind_1中）：# 全部标为相同类别# 若之前未被处理，则标为已经处理过；再加入X列表中，参与循环延伸did[X[0], 0] = 1D = dis[X[0], ]tmp = X[0]del X[0]ind_1 = find_in_radius(D, eps)if len(ind_1) > 1:  # 处理非噪音点for x1 in ind_1:sub_class[0, x1] = numberfor j in range(len(ind_1)):if did[ind_1[j], 0] == 0:did[ind_1[j], 0] = 1X.append(ind_1[j])sub_class[0, ind_1[j]] = numbernumber += 1# 最后处理所有未分类的点为噪音点X_2 = ((sub_class == 0).nonzero())[1]for x in X_2:sub_class[0, x] = -1types[0, x] = -1return types, sub_class

7、保存数据结果

#1.保存每个点的类型，其中，核心点为1，边界点为0，噪音点为-1，在主函数中生成types文件#2.保存每个点所属类别，在主函数中生成sub_class文件
def save_data(file_name, source):f = open(file_name, "w")n = np.shape(source)[1]tmp = []for i in range(n):tmp.append(str(source[0, i]))f.write("\n".join(tmp))f.close()

8、画图

#根据sub_class文件中生成的数据1.0,2.0,3.0,4.0,5.0，共计五个类别，对每个点的所属类别进行绘图，其中每种类别分别用不同的颜色来表示，便于图像观察与分析
def draw(point_data, subclass):Myfig = plt.figure()axes = Myfig.add_subplot(111)length = len(point_data)for j in range(length):if subclass[0,j] == 1:axes.scatter(point_data[j, 0], point_data[j, 1], color='c', alpha=0.4)if subclass[0,j] == 2:axes.scatter(point_data[j, 0], point_data[j, 1], color='g', alpha=0.4)if subclass[0,j] == 3:axes.scatter(point_data[j, 0], point_data[j, 1], color='m', alpha=0.4)if subclass[0,j] == 4:axes.scatter(point_data[j, 0], point_data[j, 1], color='y', alpha=0.4)if subclass[0,j] == 5:axes.scatter(point_data[j, 0], point_data[j, 1], color='r', alpha=0.4)plt.xlabel('X')plt.ylabel('Y')plt.title('dbscan-JYZ')plt.show()

9、主函数

if __name__ == "__main__":print("第一步：导入样本数据")sample_data = load_data("788points.txt")print("第二步：计算半径为")MinPts = 5eps = radius(sample_data, MinPts)print("第三步：DBSCAN算法")types, sub_class = dbscan(sample_data, eps, MinPts)print("第四步：保存每个点的类型（核心点为1，边界点为0，噪音点为-1）")save_data("types", types)print("第五步：保存每个点所属类别")save_data("sub_class", sub_class)#画图draw(sample_data,sub_class)

运行结果

总结

在这里，我们借助788个样本点的数据集，介绍了DBSCAN的概念，以及利用python实现算法聚类分析以及可视化的过程，并分析了dbscan算法的优缺点。主要思想就是把空间中密度较大，每个点之间有多个邻近点的部分聚为一类，而把密度较低的部分作为离群值对待，因此弄清算法思想非常重要。

参考文献

1.

2.

3.Hocine Chebi, Dalila Acheli, Mohamed Kesraoui. Dynamic detection of abnormalities in video analysis of crowd behavior with DBSCAN and neural networks. 2016, 1(5):56-63.

4.Pavel V. Skribtsov, Sergey O. Surikov, Michael A. Yakovlev. Background Image Estimation with MRF and DBSCAN Algorithms. 2015, 8(S10)

5.Xu Shou-kun, Wang Chao, Zhuang Li-hua, et al. DBSCAN Clustering Algorithm for the Detection of Nearby Open Clusters Based on Gaia-DR2two. 2019, 43(2):225-236.