DBSCAN 聚类算法
 
 
DBSCAN 算法是一种基于密度的聚类算法，它能够发现任意形状的类别 (database 2)，而 $k$-means 只能发现凸 (convex) 的形状 (database 1)，同时 DBSCAN 还有很强的抗噪性 (database 3)，在具有噪声的数据中发现任意形状的聚类。DBSCAN 只需扫描一遍数据集即可完成聚类，不需迭代执行。
 
 
DBSCAN 是一种基于密度的聚类算法，密度聚类算法一般假定类别可以通过样本分布的紧密程度决定。同一类别的样本，他们之间是紧密相连的。在该类别任意样本周围不远处一定有同类别的样本存在。通过将紧密相连的样本划为一类，得到一个聚类类别。通过将所有各组紧密相连的样本划为各个不同的类别，得到了最终的所有聚类类别结果。
 
DBSCAN 是基于一组邻域来描述样本集的紧密程度的，参数 (Eps, MinPts) 用来描述邻域的样本分布紧密程度。其中，Eps 描述了某一样本的邻域距离阈值，MinPts 描述了某一样本的距离为 Eps 的邻域中样本个数的阈值。
 
DBSCAN 既可以适用于凸样本集，也可以适用于非凸样本集。
 
DBSCAN 只需扫描一遍数据库。在扫描的过程中判断当前数据 $q$ 是否是核心数据点，如果是的话，那么就发现了一个新的类别，并且在添加新的数据点时将它们标记为这个类别。首先将 $q$ 还没有标记类别或者标记 noise 的 Eps 近邻都添加进去。如果新添加的近邻也是核心数据点的话，就再添加其没有标记类别或者标记 noise 的 Eps 近邻，直至不能再添加新的结点。如果不是的话，就将 $q$ 标记为 noise 并跳到下一个数据点。扫描之后，标记为 noise 的数据点就是噪声数据。
 
density-reachability and density-connectivity
 
 
 
$m$, $p$, $o$, $r$ 都是核心对象
 
对象 $q$ 是由 $m$ 直接密度可达的。对象 $m$ 由 $p$ 直接密度可达的。
对象 $q$ 是由 $p$ (间接) 密度可达的，因为 $q$ 由 $m$ 直接密度可达，$m$ 由 $p$ 直接密度可达。
$r$ 和 $s$ 是由 $o$ 密度可达的，而 $o$ 是由 $r$ 密度可达的。
 
只有核心对象才能使其他样本密度直达。注意密度可达也不满足对称性，由密度直达的不对称性得出。密度相连关系是满足对称性的。
 
 
MinPts=5，红色的点都是核心对象，因为其 Eps-邻域至少有 5 个样本。黑色的样本是非核心对象。所有核心对象密度直达的样本在以红色核心对象为中心的超球体内。如果不在超球体内，则不能密度直达。图中用绿色箭头连起来的核心对象组成了密度可达的样本序列。在这些密度可达的样本序列的 Eps-邻域内所有的样本相互都是密度相连的。
 
DBSCAN 需从数据库中寻找到一个指定数据的 Eps 近邻，而这需要扫描全部数据库。通过 R* trees 可以优化这种区域查找。
 
A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise 中提出一种启发式的方法来选择最稀疏类别的参数。首先计算出所有数据点的第 $k$ 个近邻与它的距离，降序排序并绘制二维图。然后选择出第一个抖动大的数据的值。
 
 
convex ['kɒnveks]：adj. 凸面的，凸圆的 n. 凸面体，凸状
 
DBSCAN 算法需要选择一种距离度量，对于待聚类的数据集中，任意两个点之间的距离，反映了点之间的密度。DBSCAN 算法对高维数据定义密度很困难，对于二维空间中的点，可以使用 Euclidean distance 来进行度量。
DBSCAN 算法需要用户输入 2 个参数：一个参数是半径 (Eps)，表示以给定点 $P$ 为中心的圆形邻域的范围；另一个参数是以点 $P$ 为中心的邻域内最少点的数量 (MinPts)。如果满足以点 $P$ 为中心、半径为 Eps 的邻域内的点的个数不少于 MinPts，则称点 $P$ 为核心点。
DBSCAN 聚类使用 $k$-距离的概念。$k$-距离是指：给定数据集 $P=p(i);i=0,1,\dots n$，对于任意点 $P(i)$，计算点 $P(i)$ 到集合 $D$ 的子集 $S=p(1),p(2),\dots ,p(i-1),p(i+1),\dots ,p(n)$ 中所有点之间的距离，距离按照从小到大的顺序排序。假设排序后的距离集合为 $D=d(1),d(2),\dots ,d(k-1),d(k),d(k+1),\dots ,d(n)$，则 $d(k)$ 就被称为 $k$-距离。$k$-距离是点 $p(i)$ 到所有点 (除了 $p(i)$ 点) 之间距离第 $k$ 近的距离。对待聚类集合中每个点 $p(i)$ 都计算 $k$-距离，最后得到所有点的 k-距离集合 $E=e(1),e(2),\dots ,e(n)$。
根据经验计算半径 Eps：根据得到的所有点的 $k$-距离集合 $E$，对集合 $E$ 进行升序排序后得到 $k$-距离集合 $E’$，需要拟合一条排序后的 $E’$ 集合中 $k$-距离的变化曲线图，然后绘出曲线，通过观察，将急剧发生变化的位置所对应的 $k$-距离的值，确定为半径 Eps 的值。
根据经验计算最少点的数量 MinPts：确定 MinPts 的大小，实际上也是确定 $k$-距离中 $k$ 的值，DBSCAN 算法取 $k=4$，则 $MinPts=4$。
 如果觉得经验值聚类的结果不满意，可以适当调整 Eps 和 MinPts 的值，经过多次迭代计算对比，选择最合适的参数值。
 如果 MinPts 不变，Eps 取得值过大，会导致大多数点都聚到同一个 cluster 中，Eps 过小，会导致一个 cluster 的分裂；如果 Eps 不变，MinPts 的值取得过大，会导致同一个 cluster 中点被标记为离群点，MinPts 过小，会导致发现大量的核心点。
 
DBSCAN 聚类由密度可达关系导出的最大密度相连的样本集合，形成最终聚类的一个类别或簇。
 
DBSCAN 的簇里面可以有一个或者多个核心对象。如果只有一个核心对象，则簇里其他的非核心对象样本都在这个核心对象的 Eps-邻域里。如果有多个核心对象，则簇里的任意一个核心对象的 Eps-邻域中一定有一个其他的核心对象，否则这两个核心对象无法密度可达。这些核心对象的 Eps-邻域里所有的样本的集合组成的一个 DBSCAN 聚类簇。
 
DBSCAN 使用的方法很简单，它任意选择一个没有类别的核心对象作为种子，然后找到所有这个核心对象能够密度可达的样本集合，即为一个聚类簇。接着继续选择另一个没有类别的核心对象去寻找密度可达的样本集合，这样就得到另一个聚类簇。一直运行到所有核心对象都有类别为止。
 
一些异常样本点或者说少量游离于簇外的样本点，这些点不在任何一个核心对象周围，在 DBSCAN 中，我们一般将这些样本点标记为噪声点。
在 DBSCAN 中，一般采用最近邻思想，采用某一种距离度量来衡量样本距离，例如欧式距离。这和 KNN 分类算法的最近邻思想完全相同。对应少量的样本，寻找最近邻可以直接去计算所有样本的距离。如果样本量较大，则一般采用 kd_tree 或者 ball_tree 来快速的搜索最近邻。最近邻的思想参考 KNN。
某些样本可能到两个核心对象的距离都小于 Eps，但是这两个核心对象由于不是密度直达，不属于同一个聚类簇。一般来说，此时 DBSCAN 采用先来后到，先进行聚类的类别簇会标记这个样本为它的类别。DBSCAN 的算法不是完全稳定的算法。
 
DBSCAN 算法，需要输入 2 个参数，这两个参数的计算都来自经验知识。可以理解为以某个样本点为中心，以 Eps 为半径的球形范围内都是邻域范围。
 能够有效处理噪声点和发现任意形状的空间聚类。直接对整个数据库进行操作且进行聚类时使用了一个全局性的表征密度的参数，具有比较明显的弱点。
 
当数据量增大时，要求较大的内存支持，I/O 消耗也很大。
当空间聚类的密度不均匀、聚类间距差相差很大时，聚类质量较差。
参数敏感。聚类结果与用户输入的邻域半径及密度域值密切相关，可能由于用户对数据特点不了解而输入不合适的参数，进而得出不准确的结论。
算法过滤噪声点，同时也是其缺点，造成了其不适用于某些领域 (例如网络安全领域中恶意攻击的判断)。
 
DBSCAN 不需要输入类别数 $k$，可以发现任意形状的聚类簇。在聚类的同时可以找出异常点，和 BIRCH (balanced iterative reducing and clustering using hierarchies，利用层次方法的平衡迭代规约和聚类) 算法类似。$K$-means 一般适用于凸的样本集聚类。一般来说，如果数据集是稠密的，并且数据集不是凸的，使用 DBSCAN 会比 $K$-means 聚类效果好。
 
DBSCAN 主要优点：
 
(1) 可以对任意形状的稠密数据集进行聚类，$K$-means 聚类算法一般只适用于凸数据集。
 
(2) 可以在聚类的同时发现异常点，对数据集中的异常点不敏感。
 
(3) 聚类结果没有偏倚。$K$-means 聚类算法初始值对聚类结果有很大影响。
 
DBSCAN 主要缺点：
 
(1) 如果样本集的密度不均匀、聚类间距差相差很大时，聚类质量较差，DBSCAN 聚类一般不适合。
 
(2) 如果样本集较大时，聚类收敛时间较长，此时可以对搜索最近邻时建立的 kd_tree 或者 ball_tree 进行规模限制来改进。
 
(3) 调参相对于传统的 $K$-means 聚类算法稍复杂，主要需要对距离阈值 Eps，邻域样本数阈值 MinPts 联合调参，不同的参数组合对最后的聚类效果有较大影响。
 
凸优化 / 凸最优化 / 凸最小化的文献里面会包含凸集的概念。
 
References
 
SCAN: A Structural Clustering Algorithm for Networks
 A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise

 
DBSCAN聚类算法
 
 本文转自：
 https://blog.csdn.net/huacha__/article/details/81094891

 
一、前言
 
二、DBSCAN聚类算法
 
三、参数选择
 
四、DBSCAN算法迭代可视化展示
 
五、常用的评估方法：轮廓系数
 
六、用Python实现DBSCAN聚类算法
 
一、前言
 
去年学聚类算法的R语言的时候，有层次聚类、系统聚类、K-means聚类、K中心聚类，最后呢，被DBSCAN聚类算法迷上了，为什么呢，首先它可以发现任何形状的簇，其次我认为它的理论也是比较简单易懂的。今年在python这门语言上我打算好好弄弄DBSCAN。下面贴上它的官方解释：
 
DBSCAN（Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法）是一种基于密度的空间聚类算法。 该算法将具有足够密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇，它将簇定义为密度相连的点的最大集合。
 
二、DBSCAN聚类算法
 
文字看不懂看下面这个图。下面这些点是分布在样本空间的众多样本，现在我们的目标是把这些在样本空间中距离相近的聚成一类。我们发现A点附近的点密度较大，红色的圆圈根据一定的规则在这里滚啊滚，最终收纳了A附近的5个点，标记为红色也就是定为同一个簇。其它没有被收纳的根据一样的规则成簇。（形象来说，我们可以认为这是系统在众多样本点中随机选中一个，围绕这个被选中的样本点画一个圆，规定这个圆的半径以及圆内最少包含的样本点，如果在指定半径内有足够多的样本点在内，那么这个圆圈的圆心就转移到这个内部样本点，继续去圈附近其它的样本点，类似传销一样，继续去发展下线。等到这个滚来滚去的圈发现所圈住的样本点数量少于预先指定的值，就停止了。那么我们称最开始那个点为核心点，如A，停下来的那个点为边界点，如B、C，没得滚的那个点为离群点，如N）。
 
 
基于密度这点有什么好处呢，我们知道kmeans聚类算法只能处理球形的簇，也就是一个聚成实心的团（这是因为算法本身计算平均距离的局限）。但往往现实中还会有各种形状，比如下面两张图，环形和不规则形，这个时候，那些传统的聚类算法显然就悲剧了。于是就思考，样本密度大的成一类呗。呐这就是DBSCAN聚类算法。
 
 
三、参数选择
 
上面提到了红色圆圈滚啊滚的过程，这个过程就包括了DBSCAN算法的两个参数，这两个参数比较难指定，公认的指定方法简单说一下：
 
半径：半径是最难指定的 ，大了，圈住的就多了，簇的个数就少了；反之，簇的个数就多了，这对我们最后的结果是有影响的。我们这个时候K距离可以帮助我们来设定半径r，也就是要找到突变点，比如：
 
以上虽然是一个可取的方式，但是有时候比较麻烦 ，大部分还是都试一试进行观察，用k距离需要做大量实验来观察，很难一次性把这些值都选准。 
 
MinPts:这个参数就是圈住的点的个数，也相当于是一个密度，一般这个值都是偏小一些，然后进行多次尝试
 
 
四、DBSCAN算法迭代可视化展示
 
国外有一个特别有意思的网站：https://www.naftaliharris.com/blog/visualizing-dbscan-clustering/
 
 
它可以把我们DBSCAN的迭代过程动态图画出来
 
 
设置好参数，点击GO! 就开始聚类了！
 
 
直接跳到最后看一下DBSCAN的聚类结果，如下：
 
 
如果minPoints参数设置再大一点，那么这个笑脸可能会更好看。没有颜色标注的就是圈不到的样本点，也就是离群点，DBSCAN聚类算法在检测离群点的任务上也有较好的效果。如果是传统的Kmeans聚类，我们也来看一下效果：
 
 
是不是好丑，这完美的体现出来DBSCAN算法基于密度聚类的优势了啊.
 
 
 
五、常用的评估方法：轮廓系数
 
这里提一下聚类算法中最常用的评估方法——轮廓系数（Silhouette Coefficient）：
 
ji
 
计算样本i到同簇其它样本到平均距离ai。ai越小，说明样本i越应该被聚类到该簇（将ai称为样本i到簇内不相似度）。
计算样本i到其它某簇Cj的所有样本的平均距离bij，称为样本i与簇Cj的不相似度。定义为样本i的簇间不相似度：bi=min(bi1,bi2,...,bik2)
si接近1，则说明样本i聚类合理
si接近-1，则说明样本i更应该分类到另外的簇
若si近似为0，则说明样本i在两个簇的边界上
 
 
六、用Python实现DBSCAN聚类算法
 
import pandas as pd
# 导入数据
beer = pd.read_csv('data.txt', sep=' ')
print(beer)
 
输出结果：
 
 
from sklearn.cluster import DBSCAN

X = beer[["calories","sodium","alcohol","cost"]]
# 设置半径为10，最小样本量为2，建模
db = DBSCAN(eps=10, min_samples=2).fit(X)

labels = db.labels_ 
beer['cluster_db'] = labels  # 在数据集最后一列加上经过DBSCAN聚类后的结果
beer.sort_values('cluster_db')

# 注：cluster列是kmeans聚成3类的结果；cluster2列是kmeans聚类成2类的结果；scaled_cluster列是kmeans聚类成3类的结果（经过了数据标准化）
 
 
# 查看根据DBSCAN聚类后的分组统计结果（均值）
print(beer.groupby('cluster_db').mean())
 
 
# 画出在不同两个指标下样本的分布情况
print(pd.scatter_matrix(X, c=colors[beer.cluster_db], figsize=(10,10), s=100))
 
 
# 我们可以从上面这个图里观察聚类效果的好坏，但是当数据量很大，或者指标很多的时候，观察起来就会非常麻烦。
from sklearn import metrics  
# 就是下面这个函数可以计算轮廓系数（sklearn真是一个强大的包）
score = metrics.silhouette_score(X,beer.cluster_db) 
print(score)
 
 

一、前言
 
二、DBSCAN聚类算法
 
三、参数选择
 
四、DBSCAN算法迭代可视化展示
 
五、常用的评估方法：轮廓系数
 
六、用Python实现DBSCAN聚类算法
 
一、前言
 
去年学聚类算法的R语言的时候，有层次聚类、系统聚类、K-means聚类、K中心聚类，最后呢，被DBSCAN聚类算法迷上了，为什么呢，首先它可以发现任何形状的簇，其次我认为它的理论也是比较简单易懂的。今年在python这门语言上我打算好好弄弄DBSCAN。下面贴上它的官方解释：
 
DBSCAN（Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法）是一种基于密度的空间聚类算法。 该算法将具有足够密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇，它将簇定义为密度相连的点的最大集合。
 
二、DBSCAN聚类算法
 
文字看不懂看下面这个图。下面这些点是分布在样本空间的众多样本，现在我们的目标是把这些在样本空间中距离相近的聚成一类。我们发现A点附近的点密度较大，红色的圆圈根据一定的规则在这里滚啊滚，最终收纳了A附近的5个点，标记为红色也就是定为同一个簇。其它没有被收纳的根据一样的规则成簇。（形象来说，我们可以认为这是系统在众多样本点中随机选中一个，围绕这个被选中的样本点画一个圆，规定这个圆的半径以及圆内最少包含的样本点，如果在指定半径内有足够多的样本点在内，那么这个圆圈的圆心就转移到这个内部样本点，继续去圈附近其它的样本点，类似传销一样，继续去发展下线。等到这个滚来滚去的圈发现所圈住的样本点数量少于预先指定的值，就停止了。那么我们称最开始那个点为核心点，如A，停下来的那个点为边界点，如B、C，没得滚的那个点为离群点，如N）。
 
 
基于密度这点有什么好处呢，我们知道kmeans聚类算法只能处理球形的簇，也就是一个聚成实心的团（这是因为算法本身计算平均距离的局限）。但往往现实中还会有各种形状，比如下面两张图，环形和不规则形，这个时候，那些传统的聚类算法显然就悲剧了。于是就思考，样本密度大的成一类呗。呐这就是DBSCAN聚类算法。
 
 
三、参数选择
 
上面提到了红色圆圈滚啊滚的过程，这个过程就包括了DBSCAN算法的两个参数，这两个参数比较难指定，公认的指定方法简单说一下：
 
半径：半径是最难指定的 ，大了，圈住的就多了，簇的个数就少了；反之，簇的个数就多了，这对我们最后的结果是有影响的。我们这个时候K距离可以帮助我们来设定半径r，也就是要找到突变点，比如：
 
以上虽然是一个可取的方式，但是有时候比较麻烦 ，大部分还是都试一试进行观察，用k距离需要做大量实验来观察，很难一次性把这些值都选准。 
 
MinPts:这个参数就是圈住的点的个数，也相当于是一个密度，一般这个值都是偏小一些，然后进行多次尝试
 
 
四、DBSCAN算法迭代可视化展示
 
国外有一个特别有意思的网站：https://www.naftaliharris.com/blog/visualizing-dbscan-clustering/
 
 
它可以把我们DBSCAN的迭代过程动态图画出来
 
 
设置好参数，点击GO! 就开始聚类了！
 
 
直接跳到最后看一下DBSCAN的聚类结果，如下：
 
 
如果minPoints参数设置再大一点，那么这个笑脸可能会更好看。没有颜色标注的就是圈不到的样本点，也就是离群点，DBSCAN聚类算法在检测离群点的任务上也有较好的效果。如果是传统的Kmeans聚类，我们也来看一下效果：
 
 
是不是好丑，这完美的体现出来DBSCAN算法基于密度聚类的优势了啊.
 
 
 
五、常用的评估方法：轮廓系数
 
这里提一下聚类算法中最常用的评估方法——轮廓系数（Silhouette Coefficient）：
 
ji
 
计算样本i到同簇其它样本到平均距离ai。ai越小，说明样本i越应该被聚类到该簇（将ai称为样本i到簇内不相似度）。
计算样本i到其它某簇Cj的所有样本的平均距离bij，称为样本i与簇Cj的不相似度。定义为样本i的簇间不相似度：bi=min(bi1,bi2,...,bik2)
si接近1，则说明样本i聚类合理
si接近-1，则说明样本i更应该分类到另外的簇
若si近似为0，则说明样本i在两个簇的边界上
 
 
六、用Python实现DBSCAN聚类算法
 
import pandas as pd
# 导入数据
beer = pd.read_csv('data.txt', sep=' ')
print(beer)
 
输出结果：
 
 
from sklearn.cluster import DBSCAN

X = beer[["calories","sodium","alcohol","cost"]]
# 设置半径为10，最小样本量为2，建模
db = DBSCAN(eps=10, min_samples=2).fit(X)

labels = db.labels_ 
beer['cluster_db'] = labels  # 在数据集最后一列加上经过DBSCAN聚类后的结果
beer.sort_values('cluster_db')

# 注：cluster列是kmeans聚成3类的结果；cluster2列是kmeans聚类成2类的结果；scaled_cluster列是kmeans聚类成3类的结果（经过了数据标准化）
 
 
# 查看根据DBSCAN聚类后的分组统计结果（均值）
print(beer.groupby('cluster_db').mean())
 
 
# 画出在不同两个指标下样本的分布情况
print(pd.scatter_matrix(X, c=colors[beer.cluster_db], figsize=(10,10), s=100))
 
 
# 我们可以从上面这个图里观察聚类效果的好坏，但是当数据量很大，或者指标很多的时候，观察起来就会非常麻烦。
from sklearn import metrics  
# 就是下面这个函数可以计算轮廓系数（sklearn真是一个强大的包）
score = metrics.silhouette_score(X,beer.cluster_db) 
print(score)