复习DBSCAN算法

复习DBSCAN算法

这个blog主要回顾一下DBSCAN算法,发现上课学的全部还给老师了,惭愧! 不过学过一次还是有很多好处的,比如看到里面的图就回忆起来了主要的内容,所以还是要多学东西.

DBSCAN是基于密度聚类的代表,全称叫作”Density-Based Spatial Clustering of Applications with Noise”.其实这个算法和拓扑里的有些概念十分相似,以致于我都怀疑是不是从那里面来源的想法。在拓扑学里面这一节的内容叫连通,里面有概念,比如连通分支,就和这里的非常相似,而且我还想起来了“有限覆盖定理”,和PDE里的“Harnack’s inequality”,都可以用这种方法来证明。

定义

  • $\epsilon$-领域, $N_{\epsilon}(x_j)$就是以$x_j$为“圆心”以$\epsilon$为半径的一个”闭球”,这里加”“号的原因是距离并不一定是欧氏距离。

  • 核心对象, 如果$N_{\epsilon}(x_j)$ 中的基数是大于MinPts的话,就称$x_j$是一个核心对象(core object).

  • 密度直达, 若$x_j$位于一核心对象$x_i$的$\epsilon$领域中,就称$x_j$由$x_i$密度直达.

  • 密度可达, 若 $p1=x_i, …, pn=x_j$, 且 $p_{i+1}$ 是由 $p_i$ 密度直达,则称 $x_j$ 由 $x_i$ 密度可达.

  • 密度相连, 若$x_i$与$x_j$同时可由$x_k$密度可达,则称$x_i$与$x_j$密度相连。

是不是有“有限覆盖”的感觉?

在上面的基础之上DBSCAN将”簇”定义为:满足连接性和最大性的一个非空子集。用拓扑中的语言说就是极大元。实际上,假设$x$为核心对象,那么由$x$所有密度可达的样本组成的集合就是簇。

所以DBSCAN算法的核心思想就是以”核心对象”为种子,再由此出发确定相应的聚类簇。

一个有趣的例子

自己想了一个例子,以中国象棋棋盘为例,每一个棋子代表一个点,假设所有的格子的长都是1,现在如果取$\epsilon=2, MinPts=3$的话,按照DBSCAN的算法走下去的话,最终得到的就会是红棋为一个簇,黑棋为一个簇。

优缺点以及和k-means的比较

  • 与K-Means算法

与k-means 相比,DBSCAN最大的不同就是不需要输入簇的个数k,当然它最大的优势是可以发现任意形状的聚类簇,而不是像K-Means一般仅仅使用于凸的样本集聚类。 并且DBSCAN算法可以在聚类的同时还可以找出异常点。

  • 什么时候需要用DBSCAN来聚类?

一般来说,如果数据集是稠密的,并且数据集不是凸的,那么用DBSCAN会比K-Means聚类效果好很多。如果数据集不是稠密的,则不推荐用DBSCAN来聚类。

  • 优缺点

    DBSCAN的主要优点有:

    1) 可以对任意形状的稠密数据集进行聚类,相对的,K-Means之类的聚类算法一般只适用于凸数据集。

    2) 可以在聚类的同时发现异常点,对数据集中的异常点不敏感。

    3) 聚类结果没有偏倚,相对的,K-Means之类的聚类算法初始值对聚类结果有很大影响。

    DBSCAN的主要缺点有:

    1)如果样本集的密度不均匀、聚类间距差相差很大时,聚类质量较差,这时用DBSCAN聚类一般不适合。

    2) 如果样本集较大时,聚类收敛时间较长,此时可以对搜索最近邻时建立的KD树或者球树进行规模限制来改进。

    3) 调参相对于传统的K-Means之类的聚类算法稍复杂,主要需要对距离阈值ϵ,邻域样本数阈值MinPts联合调参,不同的参数组合对最后的聚类效果有较大影响。

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦