欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

关于DBSCAN聚类算法

程序员文章站 2022-07-03 11:47:10
...

基本概念

DBSCAN(Density-Based Spatial Clustering of Application with Noiso):具有噪声的基于密度的聚类方法。从名字中就可以看出来,簇划分是根据样本密度来决定的。在了解算法具体过程之前,需要先了解一下相关的基本概念:

ϵ-邻域:样本x以ϵ为半径的范围内包含的所有样本的集合

核心对象:样本x的ϵ-领域内样本数大于阈值MinPts,则x为核心对象

直接密度可达:若某点p在点q的ϵ-邻域内,且q是核心点,则p由q直接密度可达。

关于DBSCAN聚类算法

密度相连:若从某核心点p出发,点q和点k都是密度可达的 ,则称点q和点k是密度相连的。

DBSCAN的基本思想:由密度可达导出的最大密度相连的集合作为一个簇。

算法流程

(1)将所有的样本标记为未访问状态

(2)随机选择一个未访问对象P,将其标记为已访问

(3)如果p为核心对象,创建一个新簇C,将q添加到C中

(4)对于C中的每一个样本q,如果q为核心对象,遍历其ϵ-邻域内的所有样本x:

a.如果x未被访问,则标记为已访问,将x添加到C中

b.如果x已被访问但是不属于任何一个簇,将x添加到C中

c.对C中的每个元素重复步骤a、b

(5)重复(2)到(4),直到没有未被访问的样本

(6)输出所有簇划分

DBSCAN类重要参数

    DBSCAN类的重要参数也分为两类,一类是DBSCAN算法本身的参数,一类是最近邻度量的参数,下面我们对这些参数做一个总结。

    1)eps DBSCAN算法参数,即我们的ϵϵ-邻域的距离阈值,和样本距离超过ϵϵ的样本点不在ϵϵ-邻域内。默认值是0.5.一般需要通过在多组值里面选择一个合适的阈值。eps过大,则更多的点会落在核心对象的ϵϵ-邻域,此时我们的类别数可能会减少, 本来不应该是一类的样本也会被划为一类。反之则类别数可能会增大,本来是一类的样本却被划分开。

    2)min_samples DBSCAN算法参数,即样本点要成为核心对象所需要的ϵϵ-邻域的样本数阈值。默认值是5. 一般需要通过在多组值里面选择一个合适的阈值。通常和eps一起调参。在eps一定的情况下,min_samples过大,则核心对象会过少,此时簇内部分本来是一类的样本可能会被标为噪音点,类别数也会变多。反之min_samples过小的话,则会产生大量的核心对象,可能会导致类别数过少。

    3)metric最近邻距离度量参数。可以使用的距离度量较多,一般来说DBSCAN使用默认的欧式距离(即p=2的闵可夫斯基距离)就可以满足我们的需求。可以使用的距离度量参数有:

    a) 欧式距离 “euclidean”:

关于DBSCAN聚类算法

    b) 曼哈顿距离 “manhattan”:

关于DBSCAN聚类算法

    c) 切比雪夫距离“chebyshev”: 

关于DBSCAN聚类算法

    d) 闵可夫斯基距离 “minkowski”: 

关于DBSCAN聚类算法

    e) 带权重闵可夫斯基距离 “wminkowski”:

关于DBSCAN聚类算法

    f) 标准化欧式距离 “seuclidean”: 即对于各特征维度做了归一化以后的欧式距离。此时各样本特征维度的均值为0,方差为1.

    g) 马氏距离“mahalanobis”:

关于DBSCAN聚类算法

其中,S的-1次方为样本协方差矩阵的逆矩阵。当样本分布独立时, S为单位矩阵,此时马氏距离等同于欧式距离。

    4)algorithm最近邻搜索算法参数,算法一共有三种,第一种是蛮力实现,第二种是KD树实现,第三种是球树实现。这三种方法在K近邻法(KNN)原理小结中都有讲述,如果不熟悉可以去复习下。对于这个参数,一共有4种可选输入,‘brute’对应第一种蛮力实现,‘kd_tree’对应第二种KD树实现,‘ball_tree’对应第三种的球树实现, ‘auto’则会在上面三种算法中做权衡,选择一个拟合最好的最优算法。需要注意的是,如果输入样本特征是稀疏的时候,无论我们选择哪种算法,最后scikit-learn都会去用蛮力实现‘brute’。个人的经验,一般情况使用默认的 ‘auto’就够了。 如果数据量很大或者特征也很多,用"auto"建树时间可能会很长,效率不高,建议选择KD树实现‘kd_tree’,此时如果发现‘kd_tree’速度比较慢或者已经知道样本分布不是很均匀时,可以尝试用‘ball_tree’。而如果输入样本是稀疏的,无论你选择哪个算法最后实际运行的都是‘brute’。

    5)leaf_size:最近邻搜索算法参数,为使用KD树或者球树时, 停止建子树的叶子节点数量的阈值。这个值越小,则生成的KD树或者球树就越大,层数越深,建树时间越长,反之,则生成的KD树或者球树会小,层数较浅,建树时间较短。默认是30. 因为这个值一般只影响算法的运行速度和使用内存大小,因此一般情况下可以不管它。

    6) p: 最近邻距离度量参数。只用于闵可夫斯基距离和带权重闵可夫斯基距离中p值的选择,p=1为曼哈顿距离, p=2为欧式距离。如果使用默认的欧式距离不需要管这个参数。

    以上就是DBSCAN类的主要参数介绍,其实需要调参的就是两个参数eps和min_samples,这两个值的组合对最终的聚类效果有很大的影响。

可直接使用sklearn库进行调用:

from sklearn.cluster import DBSCAN

db = DBSCAN(eps=0.5, min_samples=5)

'''默认相关参数:
(class) DBSCAN(eps=0.5, *, min_samples=5, metric='euclidean', metric_params=None, algorithm='auto', leaf_size=30, p=None, n_jobs=None)'''

参考

用scikit-learn学习DBSCAN聚类 - 刘建平Pinard - 博客园

DBSCAN聚类原理和sklearn实现-知乎