本文,就像本系列的其他文章一样。旨在通过阅读原论文+手写代码的方式,自己先把算法搞明白,然后再教其他人。手写代码除了可以验证自己是否搞明白以外,我会对中间过程做图。这样,我可以通过图直观的验证算法是否正确。而这些图,又成为写文章时候的很好的素材。
什么是 DBSCAN
DBSCAN,全称是 Density-Based Scan。 故名思意,就是通过密度扫描。DBSCAN是一种聚类算法,和KMeans相比,他不需要指定cluster的数量。他的主要参数有两个,半径和邻居的数量。Scikit-Learn中,半径用ϵ \epsilon ϵ(epsilon)表示,邻居的数量用min-samples表示。我们这里也借用sklearn的表示方式。这样大家使用sklearn的时候不会搞混。
当然,除了sklearn,在weka,R,elki等库里,也有DBSCAN的实现。他在教科书里也经常被提及,并有很多成功的实际运用。许多基于密度的聚类算法,也都受了DBSCAN的启发。实践证明改算法是有效的,并在2014年获得了SIGKDD的test-of-time大奖。
和KMeans比较
为什么有了KMeans,还要有DBSCAN,肯定是KMeans有解决不了的问题。
比如,我们画两个月亮。
```python
import numpy as np
from matplotlib import pyplot as plt
from matplotlib.patches import Circle
from sklearn.cluster import DBSCAN, KMeans
from sklearn.datasets import make_moons