简介
K-Means算法、K-Means++算法和Mean Shift算法都是基于距离的聚类算法，基于距离的聚类算法的聚类结果是球状的簇，当数据集中的聚类结果是非球状结构时，基于距离的聚类算法的聚类效果并不好，然而，基于密度的聚类算法能够较好地处理非球状结构的数据。与基于距离的聚类算法不同的是，基于密度的聚类算法可以发现任意形状的聚类。
在基于密度的聚类算法中，通过在数据集中寻找被低密度区域分离的高密度区域，将分离出的高密度区域作为一个独立的类别。DBSCAN（Density-Based Spatial Clustering of Application with Noise）是一种典型的基于密度的聚类算法。
基于距离的聚类算法存在的问题
K-Means算法，K-Means++算法和Mean Shift算法都是基于距离的聚类算法，当数据集中的聚类结果是球状结构时，基于距离的聚类算法能够得到比较好的结果，球状结构的聚类结果下图所示。
其中，Sh指的是一个半径为h的高维球区域，如图中所示圆形区域。Sh的定义为：
利用K-Means++聚类算法对图2中的数据进行聚类， 设置聚类中心的个数为2， 得到如图3所示的聚类结果。
在图2中，“+”表示的是最终的两个聚类中心，由图2可知，对于图中的非球状结构的聚类数据，基于距离的KMeans++算法并不能得到正确的聚类结果。
利用Mean Shift聚类算法对图2中的数据进行聚类，设置高斯核函数中的h=1时，得到如图4所示的聚类结果。
在图4中，“+”表示最终的聚类中心，与K-Means++算法类似，基于距离的Mean Shift算法对图中的非球状聚类结构的数据也不能得到正确的聚类结果。
基于密度的聚类
从图2中，我们可以看出，数据点在图中呈现上下两个弧形，同时，分别在两个弧形中，数据点之间较为密集， 而两个弧形彼此之间较为稀疏。由这样的现象，我们猜测是否存在一种方法能够利用样本之间的紧密程度对数据进行聚类？基于密度的聚类（Density-Based Clustering）便是这样一种利用数据之间的紧密程度来对样本进行聚类的算法。
1、DBSCAN算法相关的基本概念
DBSCAN（Density-Based Spatial Clustering of Application with Noise）是一种典型的基于密度的聚类算法，在DBSCAN算法中，有两个最基本的邻域参数，分别为ε邻域和MinPts。其中ε邻域表示的是在数据集D中与样本点xi的距离不大于ε的样本，即：
样本点xi的ε邻域如图5所示:
在图5中，样本点x不在样本点xi的ε邻域内。xi的密度可由xi的ε邻域内的点的数量来估计。MinPts表示的是在样本点xi的ε邻域内的最少样本点的数目。基于邻域参数ε邻域和MinPts，在DBSCAN算法中将数据点分为以下三类：
• 核心点（Core Points）：若样本xi的ε邻域内至少包含了MinPts个样本，即则称样本点xi为核心点。
• 边界点（Border Points）：若样本xi的ε邻域内包含的样本数目小于MinPts，但是它在其他核心点的邻域内，则称样本点xi为边界点。
• 噪音点（Noise）：指的是既不是核心点也不是边界点的点。
核心点、边界点和噪音点如图6所示：
在图6中，设置MinPts的值为9，对应的样本点x1的ε邻域内包含11个样本点，大于MinPts，则样本点x1为核心点。样本点的x2在样本点x1的ε邻域内，且样本点x2的ε邻域内只包含8个样本点，小于MinPts，则样本点x2为边界点。样本点x3为噪音点。
在DBSCAN算法中，还定义了如下的一些概念：
• 直接密度可达（directly density-reachable）：若样本点xj在核心点xi的ε邻域内，则称样本点xj从样本点xi直接密度可达。
• 密度可达（density-reachable）：若在样本点xi，1和样本点xi，n之间存在序列xi，2，…，xi，n-1，且xi，j+1从xi，j直接密度可达，则称xi，n 从xi，1密度可达。由密度可达的定义可知，样本点xi，1，xi，2，…，xi，n-1均为核心点，直接密度可达是密度可达的特殊情况。
• 密度连接（density-connected）：对于样本点xi和样本点xj，若存在样本点xk，使得xi和x j都从xk密度可达，则称xi和xj密度相连。
直接密度可达、 密度可达如图7所示：
在图7中，设置MinPts的值为9，则样本点x1和样本点x2为核心点，样本点x3为边界点。样本点x2在核心点x1的ε邻域内，则样本点x2从样本点x1直接密度可达；样本点x3在核心点x2的ε邻域内，则样本点x3从核心点x2直接密度可达；在样本点x1和x3之间存在样本点x2，且样本点x2从样本点x1直接密度可达，则样本点x3从样本点x1密度可达。
2、DBSCAN算法原理
基于密度的聚类算法通过寻找被低密度区域分离的高密度区域，并将高密度区域作为一个聚类“簇”。在DBSCAN算法中，聚类“簇”定义为：由密度可达关系导出的最大的密度连接样本的集合。
若x为核心对象，由x密度可达的所有样本组成的集合记为：
则X满足连接性和最大性的簇。
DBSCAN算法流程
在DBSCAN算法中，由核心对象出发，找到与该核心对象密度可达的所有样本形成一个聚类“簇”。DBSCAN算法的算法流程为：
• 根据给定的邻域参数ε和MinPts确定所有的核心对象；
• 对每一个核心对象；
• 选择一个未处理过的核心对象，找到由其密度可达的样本生成聚类“簇”；
• 重复以上过程。
SKlearn的DBSCAN算法的实践
子函数
主函数
执行结果：
文章转载于:集智书童
作者: ChaucerG
推荐阅读
- Bag of Tricks for Neural Architecture Search
- ARM-CPU150FPS | PicoDet助力移动端达到超实时检测（强烈建议工程人员学习）
- 【从零开始学深度学习编译器】十三，如何在MLIR里面写Pass？
更多嵌入式AI技术相关内容请关注嵌入式AI专栏。
