数据挖掘，DBSCAN算法的介绍
DBSCAN算法
- 密度聚类方法的指导思想是,只要一个区域中的点的密度大于某个阈值就把它加到与之相近的聚类中去.
- 密度聚类方法的优点：可以克服基于距离的算法只能发现“类圆形”聚类的缺点,可以发现任意形状的聚类,它还对噪声数据不敏感。与传统的k-means相比，DBSCAN算法不需要输入划分的聚类个数;聚类簇的形状没有偏差;可以在需要时，输入过滤噪声的参数.还可以处理任意形状和大小的簇．
- 密度聚类方法的缺点：计算密度单元的计算复杂度大,需要建立空间索引来降低计算量,对数据维数的伸缩性比较差.
- 密度聚类的代表算法有DBSCAN算法,OPTICS算法,DENCLUE算法.
- 今天我们先介绍DBSCAN算法.
- -
DBSCAN算法设计思想：从数据中抽取一个未处理过的点,然后如果抽取的点是核心点,那么找出所有从该点密度可达的对象，形成一个簇;如果抽取的点是边缘点，那么跳出本次循环，寻找下一个对象.终止的条件,就是所有的点都被处理过.
下面，我举个例子来讲解DBSCAN算法
样本事物数据库
| 序号 | 属性1 | 属性2 |
|---|---|---|
| 1 | 1 | 0 |
| 2 | 4 | 0 |
| 3 | 0 | 1 |
| 4 | 1 | 1 |
| 5 | 2 | 1 |
| 6 | 3 | 1 |
| 7 | 4 | 1 |
| 8 | 5 | 1 |
| 9 | 0 | 2 |
| 10 | 1 | 2 |
| 11 | 4 | 2 |
| 12 | 1 | 3 |
其中n=12,用户半径输入e=1,MinPts=4
DBSCAN算法步骤如下：
第一步：在数据库中选择序号１,由于在以它为圆心的，以１为半径的圆内包含２个点（１,４）,由于２个点小于４，所以序号１不是核心点，选择下一个点.
第二步：在数据库中选择序号２,由于在以它为圆心的，以１为半径的圆内包含２个点（４,７）,由于２个点小于４，所以序号２不是核心点，选择下一个点.
第三步：在数据库中选择序号3,由于在以它为圆心的，以１为半径的圆内包含3个点（3,4,9）,由于２个点小于４，所以序号3不是核心点，选择下一个点.
第四步：在数据库中选择序号４,由于在以它为圆心的，以１为半径的圆内包含５个点（１,３,4,5,）,由于5个点大于４，所以序号５是核心点,寻找从它出发可达的点，聚出的新类为c1={1,3,4,5,9,10,12},然后选择下一个点.
第五步：在数据库中选择序号５，由于已经在簇c1中,选择下一个点.
第六步：在数据库中选择序号６,由于在以它为圆心的，以１为半径的圆内包含３个点（５,６,７）,由于3个点小于４，所以序号6不是核心点，选择下一个点.
第七步：在数据库中选择序号７,由于在以它为圆心的，以１为半径的圆内包含5个点（2,6,７,8 ,11),所以序号7是核心点，寻找从它出发可达的点，聚类出的新类c2={2,6,7,8,11}.然后选择下一个点.
第八步：在数据库中选择序号８,已经在簇c2中,选择下一个点.
第九步：在数据库中选择序号９,已经在簇c1中，选择下一个点.
第十步：在数据库中选择序号１０,已经在簇c1中,选择下一个点.
第十一步：在数据库中选择序号１１,已经在簇c２中,选择下一个点.
第十二步:在数据库中选择序号12,已经在簇c1中,由于所有点的都遍历过一边了,所以DBSCAN算法结束.
聚类的结果为{1,3,4,5,9,10,12}和{2,6,7,8,11}
用途：
DBSCAN算法可以将具有足够高密度的图像点划分为簇,它能找到图像样本比较密集的部分,概括出图像样本相对比较集中的类,并且可以在带有噪声的图像中进行聚类,完成对图像分割.