简单一文助你理解DBSCAN是什么

2019-09-02 08:49

Python进阶学习交流

关注

一般说到聚类算法，大多数人会想到k－means算法，但k－means算法一般只适用于凸样本集，且需要预先设定k值，而DBSCAN聚类既可以用于凸样本集，也可以用于非凸样本集，也不需要提前设定簇族数。关于凸样本集的解释如下图所示。

关于DBSCAN聚类，它是基于密度的聚类，一般通过样本间的紧密程度来进行聚类，将紧密相连的一类样本化为一类，直至遍历所有样本点。

而DBSCAN聚类有下面几个定义。

1．ε－邻域：有一个样本点x1，以x1为圆心，半径为ε的一个范围

2．min＿sample（最小样本点数）：在样本点x1的ε－邻域内的所有样本点总数n；如果n＞＝min＿sample，样本点成为核心点，否则为非核心点。而非核心又分为边界点和噪声点。他们的区别在于其ε－邻域内是否存在核心点，如果存在则为边界点，否则为噪声点。

3．密度直达：有样本点x1位于x2的ε－邻域内，且x2为核心点，则称x1由x2密度直达。

4．密度可达：有样本点x1位于x2的ε－邻域内，且x1和x2均为核心点，则称x1和x2密度可达。

5．密度相连：有非核心点x1和x2均在核心点x3的ε－邻域内，则称x1和x2密度相连。所有密度相连的样本点组成一个集合。

上图中的红色点为核心点，黑色点为非核心点（包括边界点和噪音点）。一共有两组密度可达，第一组（左边）有七个核心点，其集合包括七个核心点以及各个ε－邻域内的所有边界点。第二组（右边）有五个核心点，其集合包括五个核心点以及各个ε－邻域内的所有边界点。当所有非噪声点均在不同集合内时，聚类结束。

因此，可以将DBSCAN聚类的流程定义如下：

有数据集X＝｛x1，x2，．．．，xn｝，设置好min＿sample和邻域半径值。

1．遍历数据集，将各个样本点间的距离保存到一个矩阵中；

2．遍历数据集，将所有的核心点，以及各个核心点邻域内的样本点找出；

3．如果核心点间的距离小于半径值，则将两个核心点连接到一起；最终会形成若干簇族；

4．将所有边界点分配到离他最近的核心点；

5．直至所有非噪音点完成分配，算法结束。

python实现

用的是sklearn库自带的数据集－－－make＿circles。散点图如下。

根据上面定义的流程，开始写代码啦。

首先要得到各个样本点间的距离：

def dis（self，va，vb）： s＝（va－vb） f＝sqrt（s＊s．T） return f［0，0］
def get＿distance（self，dataset）： m，n＝shape（dataset）［0］，shape（dataset）［1］ dataset＝mat（dataset） dis＝mat（zeros（（m，m））） for i in range（m）： for j in range（i，m）： dis［i，j］＝self．dis（dataset［i，］，dataset［j，］） dis［j，i］＝dis［i，j］ return dis

然后找到所有的核心点，以及各个核心点邻域内的所有样本点集合。

def find＿core＿point（self，dismatrix）： core＿point＝［］ core＿point＿dict＝｛｝ m＝shape（dismatrix）［0］ for i in range（m）： ind＝［］ for j in range（m）： if dismatrix［i，j］＜self．eps： ind．append（j） if len（ind）＞＝self．min＿sample： core＿point．append（i） core＿point＿dict［str（i）］＝ind core＿point＿core＝｛｝ for key，value in core＿point＿dict．items（）： o＝［］ for i in value： if i in core＿point： o．append（i） core＿point＿core［key］＝o return core＿point，core＿point＿dict，core＿point＿core其中core＿point是一个列表，存储所有的核心点core＿point＿dict是一个字典，key为核心点，value为该核心点邻域内的所有样本点集合core＿point＿core是一个字典，key为核心点，value为该核心点邻域内所有核心点集合

接下来就是找出密度直达点集合，也就是在邻域内的核心点集合

def join＿core＿point（self，core＿point，core＿point＿dict，core＿point＿core）： labels＝array（zeros（（1，len（core＿point）））） num＝1 result＝｛｝ result［str（num）］＝core＿point＿core［str（core＿point［0］）］ for i in range（1，len（core＿point））： q＝［］ for key，value in result．items（）： r＝self．get＿same（core＿point＿core［str（core＿point［i］）］，value） if r： q．append（key） if q： n＝result［q［0］］．copy（） n．extend（core＿point＿core［str（core＿point［i］）］） for i in range（1，len（q））： n．extend（result［q［i］］） del result［q［i］］ result［q［0］］＝list（set（n）） else： num＝num＋1 result［str（num）］＝core＿point＿core［str（core＿point［i］）］ return result

再将所有边界点划分到其最近的核心点一簇并画出。

def ddbscan（self，data， label）： m＝shape（data）［0］ dismatrix＝self．get＿distance（data） types＝array（zeros（（1，m））） number＝1 core＿point， core＿point＿dict，core＿point＿core＝self．find＿core＿point（dismatrix） if len（core＿point）： core＿result＝self．join＿core＿point（core＿point，core＿point＿dict，core＿point＿core） for key，value in core＿result．items（）： k＝int（key） for i in value： types［0，i］＝k for j in core＿point＿dict［str（i）］： types［0， j］＝ k print（types） newlabel＝types．tolist（）［0］ data＝array（data） q＝list（set（newlabel）） print（q） colors ＝［＇r＇，＇b＇，＇g＇，＇y＇，＇c＇，＇m＇，＇orange＇］ for ii in q： i＝int（ii） xy＝data［types［0，：］＝＝i，：］ plt．plot（xy［：， 0］， xy［：， 1］，＇o＇， markerfacecolor＝colors［q．index（ii）］， markeredgecolor＝＇w＇， markersize＝5） plt．title（＇DBSCAN＇） plt．show（）

最后的结果图如下：

虽然效果不错，但自己写的就是比较辣鸡，一共用了10．445904秒；如果真的要用这个算法的话，不推荐大家用自己写的，事实上sklearn库就有DBSCAN这个函数，只需要0．0284941秒。

效果如上所示。而且代码也只有几行。代码复制于（http：／／itindex．net／detail／58485－％E8％81％9A％E7％B1％BB－％E7％AE％97％E6％B3％95－dbscan）

def skdbscan（self，data，label）： data ＝ array（data） db ＝ DBSCAN（eps＝self．eps， min＿samples＝self．min＿sample， metric＝＇euclidean＇）．fit（data） core＿samples＿mask ＝ zeros＿like（db．labels＿， dtype＝bool） core＿samples＿mask［db．core＿sample＿indices＿］＝ True labels ＝ db．labels＿ n＿clusters＿＝ len（set（labels））－（1 if －1 in labels else 0） unique＿labels ＝ set（labels） colors ＝［＇r＇，＇b＇，＇g＇，＇y＇，＇c＇，＇m＇，＇orange＇］ for k， col in zip（unique＿labels， colors）： if k ＝＝－1： col ＝＇k＇ class＿member＿mask ＝（labels ＝＝ k） xy ＝ data［class＿member＿mask ＆ core＿samples＿mask］ plt．plot（xy［：， 0］， xy［：， 1］，＇o＇， markerfacecolor＝col， markeredgecolor＝＇w＇， markersize＝10） plt．title（＇Estimated number of clusters：％d＇％ n＿clusters＿） plt．show（）

关于DBSCAN这个函数有几个要注意的地方：

DBSCAN（eps＝0．1， min＿samples＝5， metric＝＇euclidean＇，

algorithm＝＇auto＇， leaf＿size＝30， p＝None， n＿jobs＝1）

核心参数：

eps： float－邻域的距离阈值

min＿samples ：int，样本点要成为核心对象所需要的？－邻域的样本数阈值

其他参数：

metric ：度量方式，默认为欧式距离，可以使用的距离度量参数有：

欧式距离 “euclidean”

曼哈顿距离 “manhattan”

切比雪夫距离“chebyshev”

闵可夫斯基距离 “minkowski”