DBSCAN算法(python代码实现)

DBSCAN

上次学了kmeans基于划分的方法,这次学一个基于密度的聚类算法:DBSCAN(Density-Based Spatial Clustering of Applications with Noise)

一个例子

想象有一个很大的广场,上面种了很多的鲜花和绿草。快要到国庆节了,园丁要把上面的鲜花和绿草打造成四个字:欢度国庆。于是园丁开始动手,用绿草作为背景去填补空白的区域,用红色的鲜花摆成文字的形状,鲜花和绿草之间都要留下至少一米的空隙,让文字看起来更加醒目。

国庆节过后,园丁让他的大侄子把这些花和草收起来运回仓库,可是大侄子是红绿色盲,不能通过颜色来判断,这些绿草和鲜花的面积又非常大,没有办法画出一个区域来告知大侄子。这可怎么办呢?

想来想去,园丁一拍脑袋跟大侄子说:”你就从一个位置开始收,只要跟它连着的距离在一米以内的,你就摞在一起;如果是一米以外的,你就再重新放一堆。” 大侄子得令,开开心心地去收拾花盆了。最后呢,大侄子一共整理了三堆花盆:所有的绿草盆都摞在一起,”国” 字用的红花摞在一起,”庆” 字用的红花摞在了一起。这就是一个关于密度聚类的例子了。

DBSCAN算法(python代码实现)

; DBSCAN算法将数据点分为三类:

  • 核心点:在半径Eps内含有不少于MinPts数目的点
  • 界点:在半径Eps内点的数量小于MinPts,但是落在核心点的邻域内
  • 噪音点:既不是核心点也不是边界点的点

DBSCAN算法(python代码实现)

在这幅图里,MinPts = 4,点 A 和其他红色点是核心点,因为它们的 ε-邻域(图中红色
圆圈)里包含最少 4 个点(包括自己),由于它们之间相互相可达,它们形成了一个聚类。
点 B 和点 C 不是核心点,但它们可由 A 经其他核心点可达,所以也和A属于同一个聚类。点 N 是局外点,它既不是核心点,又不由其他点可达。

算法原理

上面的例子看起来比较简单,但是在算法的处理上我们首先有个问题要处理,那就是如何去衡量密度。在 DBSCAN 中,衡量密度主要使用两个指标,即半径和最少样本量。

对于一个已知的点,以它为中心,以给定的半径画一个圆,落在这个圆内的就是与当前点比较紧密的点;而如果在这个圆内的点达到一定的数量,即达到最少样本量,就可以认为这个区域是比较稠密的。

在算法的开始,要给出半径和最少样本量,然后对所有的数据进行初始化,如果一个样本符合在它的半径区域内存在大于最少样本量的样本,那么这个样本就被标记为核心对象。

这里我画了一幅图,假设我们的最小样本量为 6,那么这里面的 A、 B、 C 为三个核心对象。

DBSCAN算法(python代码实现)

对于在整个样本空间中的样本,可以存在下面几种关系:

  • 直接密度可达: 如果一个点在核心对象的半径区域内,那么这个点和核心对象称为直接密度可达,比如上图中的 A 和 B 、 B 和 C 等。
  • 密度可达: 如果有一系列的点,都满足上一个点到这个点是密度直达,那么这个系列中不相邻的点就称为密度可达,比如 A 和 D。
  • 密度相连: 如果通过一个核心对象出发,得到两个密度可达的点,那么这两个点称为密度相连,比如这里的 E 和 F 点就是密度相连。

; DBSCAN 处理步骤

经过了初始化之后,再从整个样本集中去抽取样本点,如果这个样本点是核心对象,那么从这个点出发,找到所有密度可达的对象,构成一个簇。

如果这个样本点不是核心对象,那么再重新寻找下一个点。
不断地重复这个过程,直到所有的点都被处理过。

这个时候,我们的样本点就会连成一片,也就变成一个一个的连通区域,其中的每一个区域就是我们所获得的一个聚类结果。

当然,在结果中也有可能存在像 G 一样的点,游离于其他的簇,这样的点称为异常点。

算法优缺点

优点

  • 不需要划分个数。 跟 K-means 比起来, DBSCAN 不需要人为地制定划分的类别个数,而可以通过计算过程自动分出。
  • 可以处理噪声点。 经过 DBSCAN 的计算,那些距离较远的数据不会被记入到任何一个簇中,从而成为噪声点,这个特色也可以用来寻找异常点。
  • 可以处理任意形状的空间聚类问题。 从我们的例子就可以看出来,与 K-means 不同, DBSCAN 可以处理各种奇怪的形状,只要这些数据够稠密就可以了。

缺点

  • 需要指定最小样本量和半径两个参数。 这对于开发人员极其困难,要对数据非常了解并进行很好的数据分析。而且根据整个算法的过程可以看出, DBSCAN 对这两个参数十分敏感,如果这两个参数设定得不准确,最终的效果也会受到很大的影响。
  • 数据量大时开销也很大。 在计算过程中,需要对每个簇的关系进行管理。所以当数据量大的话,内存的消耗也非常严重。
  • 如果样本集的密度不均匀、聚类间距差相差很大时,聚类质量较差。

在使用的过程中十分要注意的就是最小样本量和半径这两个参数,最好预先对数据进行一些分析,来加强我们的判断

python 代码实现

今天我们使用的数据集不再是鸢尾花数据集,我们要使用 datasets 的另外一个生成数据的功能。

在下面的代码中可以看到,我调用了 make_moons 这个方法,在 sklearn 的官网上,我们可以看到关于这个方法的介绍:生成两个交错的半圆环,从下面的生成图像我们也能够看到,这里生成的数据结果,是两个绿色的半圆形。

我们今天调用的聚类方法是 sklearn.cluster 中的 dbscan。

from sklearn import datasets
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.cluster import dbscan #今天使用的新算法包
import numpy as np
X,_=datasets.make_moons(500,noise=0.1,random_state=1) #单单用x=。。。的话最后面还会有一个类别的数组
df = pd.DataFrame(X,columns=['x','y'])
df.plot.scatter('x','y',s=200,alpha=0.5,c='green')

接下来我们就用dbscan算法来进行聚类计算
eps为邻域半径, min_samples为最少样本量
core_samples,cluster_ids=dbscan(X,eps=0.2,min_samples=20)
cluster_ids中 -1表示对应的点为噪声
df= pd.DataFrame(np.c_[X,cluster_ids],columns=['x','y','cluster_id'])
np.c 中的c 是 column(列)的缩写,就是按列叠加两个矩阵,就是把两个矩阵左右组合,要求行数相等。
df['cluster_id']=df['cluster_id'].astype('i2') #变整数

df.plot.scatter('x','y',s=200,c=list(df['cluster_id']),cmap='Reds',colorbar=False,alpha=0.6,title='DBSCAN')

最后,我们使用不同的颜色来标识聚类的结果,从图上可以看出有两个大类,也就是两个月亮的形状被聚类算法算了出来。

但是眼尖的同学可能看到,在月亮两头的区域有一些非常浅色的点,跟两个类别的颜色都不一样,这里就是最后产生的噪声点,根据我们设置的参数计算,这些点不属于任何一个类别。

Original: https://blog.csdn.net/abc1234564546/article/details/126135022
Author: ybhybh666
Title: DBSCAN算法(python代码实现)

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/549736/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

亲爱的 Coder【最近整理,可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球