DBSCAN基于密度的聚类算法

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个比较有代表性的基于密度的聚类算法。与划分和层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在噪声的空间数据库中发现任意形状的聚类。

关键概念
1.与基于距离的聚类算法不同的是，基于距离的聚类算法的聚类结果是球状的簇，而基于密度的聚类算法可以发现任意形状的聚类，这对于带有噪音点的数据起着重要的作用。
2.所有的数据被分为三类点：
核心点。在半径eps内含有超过min_samples数目的点。
边界点。在半径eps内点的数量小于min_samples，但是落在核心点的邻域内，也就是说该点不是核心点，但是与其他核心点的距离小于eps。
噪音点。既不是核心点也不是边界点的点，该类点的周围数据点非常少。

步骤：

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

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

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

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

 

好处：

1. 与K-means方法相比，DBSCAN不需要事先知道要形成的簇类的数量。

2. 与K-means方法相比，DBSCAN可以发现任意形状的簇类。

3. 同时，DBSCAN能够识别出噪声点。

4.DBSCAN对于数据库中样本的顺序不敏感，即Pattern的输入顺序对结果的影响不大。但是，对于处于簇类之间边界样本，可能会根据哪个簇类优先被探测到而其归属有所摆动。

 

应用场景和限制：
是非监督的聚类算法。
对噪声点的容忍性非常好；而去簇的形状随意，不受线性方程的限制。

 

缺点：

1. DBScan不能很好反映高维数据。

2. DBScan不能很好反映数据集以变化的密度

 

参数：

class sklearn.cluster.DBSCAN(eps=0.5, min_samples=5, metric='euclidean', algorithm='auto', leaf_size=30, p=None, random_state=None)

eps：点之间的间距，大于这个间距的就不算一个簇了。
min_samples：可以算作核心点的高密度区域的最少点个数。
metric：距离公式，可以用默认的欧式距离，还可以自己定义距离函数。
algorithm：发现近邻的方法，是暴力brute，二维空间的距离树kd_tree还是球状树形结构ball_tree。这个参数主要是为了降低计算复杂度的，可以从O(N^2)降到O(n*log(n))。换句话说，无论哪种算法都会达到最后的结果，影响的只是性能。
leaf_size：配合两种_tree算法的。
random_state：不用。

结果展开说：

labels_：所有点的分类结果。无论核心点还是边界点，只要是同一个簇的都被赋予同样的label，噪声点为-1.
core_sample_indices_：核心点的索引，因为labels_不能区分核心点还是边界点，所以需要用这个索引确定核心点。

# 不是很懂，做个笔记，日后用到详细添加内容