dbscan算法_聚类算法之DBSCAN算法(基于密度)

英文全称：Density—Based Spatial Clustering of Application with Noise，是一种基于密度的聚类方法，和k-means不同的是，它不需要预先确定多少类别，而是基于数据推测出类的数目，并且可以发掘任意形状的聚类数据，同时可以有效过滤噪声数据。

概念：

ε邻域：半径为 ε的邻近区域；

minPts：邻近区域中的样本数，一般建议为>=特征数+1；

核心点：如果给定邻域内的样本数大于等于minPts，则那些样本都称为核心点；

边缘点：如果给定邻域内的样本数小于minPts，则那些样本都称为边缘点；

离群点：既不是核心点，也不是边缘点的样本；

直接密度可达：假设有样本集D，若p点在s的 ε邻域内，而且s为核心点，那么p点到s点称为直接密度可达；

密度可达（或者称间接密度可达）：假设有样本集D，若p到p1直接密度可达，p1到p2直接密度可达，那么称p到p2密度可达的。（传递性）

密度相连：假设有样本集D，s到p是密度可达的，s到q也是密度可达的，那么称p到q是密度相连的。

流程：

(1) 自定义邻域半径ε和minPts的值，并在数据集中任意选择一个样本数据p；

(2) 计算样本p到其他样本点的距离，再根据ε和minPts，找出p密度可达的其他样本，形成一个簇；

(3) 若p是一个边缘点，则选其他未被选择的样本；

(4) 重复(2)(3) 知道所有点都被选取过；

例子：

假设有样本集合D，如下：

二维坐标系形象表示：

第1步：

(1) 我们设定ε=3，minPts=3， 选择样本集中的d1作为第一点，计算d1到其他样本点的距离，例如：distance(d1->d2)=sqrt((1-2)∧2+(2-1)∧2) = sqrt(2)；

(2) 根据ε=3，将(1)中得到距离中大于等于ε的样本，分配到d1邻域内，那么可以得到d1邻域中的样本有：{d1, d2, d3, d13}，又因为minPts=3，即邻域中的样本数大于3，则d1是一个核心点，因此建立簇C1；

(3) 为了找出d1所有密度可达的点，遍历d1邻域中的点，找出d2, d3, d13的邻域样本；

(4) 按照d1找邻域的点，我们可以发现d2领域中的样本有：{d1, d2, d3, d4, d13} , 而d4是可以由间接密度可达归类到d1邻域中的，那么d1的簇C1中有：{d1, d2, d3, d4, d13}；

(5) d3满足核心点条件，且d3领域中的样本有：{d1, d2, d3, d4, d13}，但以上的样本在C1中已存在；

(6) d4满足核心点条件，且d3领域中的样本有：{d3, d4, d13}，但以上的样本在C1中已存在；

(7) d13满足核心点条件，且d13领域中的样本有：{d1, d2, d3, d4, d13}，但以上的样本在C1中已存在；

(8) 最终我们得到d1的簇C1={d1, d2, d3, d4, d13}。

第2步：

(1) 由于d2,d3,d4已处理过，接下来处理d5，根据第一步中的(2) 步，得到d5是一个核心点，其邻域中样本有：{d5, d6, d7, d8}，建立簇C2，再根据第一步(3)中的方法，遍历d5域中的样本，此处省略，最终可以得到簇C2={d5, d6, d7, d8}；

第4步：：

(1) 选取未处理的d9，由于d9满足条件的领域中只有{d9}，个数小于minPts，因此不是核心点，直接结束；

第四步：

(1) 选取未处理的d10，由于d9满足条件的领域中只有{d10, d11}，个数小于minPts，因此不是核心点，直接结束；

第5步：

(1) 选取未处理的d11，由于d11满足条件的领域中有{d10, d11, d12}，个数等于minPts，因此d11是核心点，建立簇C3，遍历d11域中的样本，此处省略，最终可以得到簇C3={d10, d11,d12}；

第6步： 所有点都已经被处理过，算法结束。

最终我们得到3个簇，即C1={d1, d2, d3, d4, d13}, C2={d5, d6, d7, d8}, C3={d10, d11,d12}，因此可以认为有3个类别，d9被认为是噪声样本，忽略掉。如下图：

优点：

(1) 预先无需知道簇的数量；

(2) 能够识别出噪声样本，对噪音数据不敏感；

(3) 可发现任意形状簇类；

缺点：

(1) 若样本间距差很大，即密度差异大，聚类效果较差；

(2) 在特征数特别多的情况，即维数灾难，半径ε很难选取；