本站原创文章，转载请说明来自《老饼讲解-机器学习》www.bbbdata.com
DBSCAN聚类是一种抗噪声的基于密度的空间聚类方法，它的特点是不会被样本的形态所影响
本文讲解DBSCAN聚类的思想原理和具体算法流程，并展示一个DBSCAN聚类的具体实现代码
通过本文可以快速了解DBSCAN聚类是什么，以及如何使用DBSCAN对不规则形态的样本进行聚类
本节介绍DBSCAN聚类算法的思想以及相关概念
什么是DBSCAN聚类
DBSCAN(Density-Based Scan)聚类是一种基于密度扫描的聚类方法
通俗来说，DBSCAN就是从一个样本出发，依靠近邻找近邻，不断把附近的点纳入同一类别
如图所示，DBSCAN从样本A出发，近邻找近邻，直到找到C时，C密度不足，则停止搜索
由于DBSCAN是依靠近邻扫描式进行聚类，因此它不受样本的形状约束，并具有极强的抗噪性
DBSCAN具体算法流程与机制
为了更专业地描述DBSCAN聚类，下面先介绍一些定义
DBSCAN有两个参数：半径 和 最小样本数，以及下述样本类型和关系：
一、样本点的类型
核心样本点：如果样本的半径内的样本个数最小样本数，则称为核心点
核心样本点代表密度足够，核心样本点允许扩散，继续搜索它的近邻点
边界样本点：不是核心样本点，但在其它核心样本点的半径内
边界样本点可以被核心样本点搜索到，但不会进一步搜索它的近邻点
噪声样本点：既不是核心样本点，又不在其它核心样本点的半径内
噪声点不会被核心样本点搜索到，是较为孤立的点
二、样本点的关系
密度直达 ：p是核心点，q在p的范围内，则称p到q是密度直达的
密度直达代表可以通过p直接找到q
密度可达 ：如果p到q可通过一连串的密度直达连接，则称p到q是密度可达的
密度可达代表可以通过p可以找到q
密度相连 ：如果o到p,q都是密度可达的，则称p,q密度相连
密度相连代表p,q能同时被某个点o找到
DBSCAN聚类流程
DBSCAN的聚类机制描述如下：
DBSCAN聚类从一个样本点p出发(p必须是核心点，边界、噪声点根本出发不了)
通过密度直达不断传播，直到边界点样本点为止，本次找到的所有样本归为一个类别
可知，所有与p密度可达的样本都会被找到，样本之间的允许的最大跨度是"密度相连"
DBSCAN的算法流程如下：
一、初始化所有样本均未被访问过
二、对所有样本点进行历遍：
1. 如果样本已被访问过：
继续下一个样本
2. 如果不是核心样本点：
将样本标为噪声，并标记样本已被访问，继续下一个样本
3. 如果是核心样本点：
创建一个类别
标记该样本已被访问
将样本的密度直达样本放到搜索队列
历遍搜索队列样本 :
样本还没有类别，则标上当前类别
如果样本被访问过，继续下一个样本
标记样本被访问
如果是核心点，将样本的密度直达样本放到搜索队列，并去重
（备注：后期会有许多样本已被访问，因此在放上队列前可先作筛选）
三、输出最终每个样本的分类
本节讲解如何使用代码实现一个DBSCAN聚类方法对样本进行聚类
DBSCAN聚类-代码实现
在sklearn中，可以使用DBSCAN函数来实现一个DBSCAN聚类算法
具体代码如下：
import numpy as np
import matplotlib.pyplot as plt
from sklearn import cluster
from sklearn import datasets
# -------------成生数据 -----------------------
X1, y1=datasets.make_circles(n_samples=500, factor=.5,noise=.05)
X2, y2 = datasets.make_blobs(n_samples=100
,n_features=2
,centers=[[2,2]]
,cluster_std=[[.1]]
,random_state=0)
X = np.concatenate((X1, X2))
# ----------对样本进行聚类----------------------
clf = cluster.DBSCAN(eps = 0.2, min_samples = 12) # 初始化DBSCAN聚类模型
y_pred = clf.fit_predict(X) # 对样本进行聚类
plt.scatter(X[:, 0], X[:, 1], c=y_pred) # 绘画结果
plt.show() # 展示画布运行结果如下：
可以看到，样本已经很好地进行聚类，这体现了DBSCAN并不受形状的影响
备注L：DBSCAN是很受min_samples 和eps 两个参数的影响的，需要尝试与调整
End