机器学习笔记（3）——聚类之DBSCAN算法

 一、算法介绍

DBSCAN，具有噪声的基于密度的聚类方法，是一种很典型的密度聚类算法，和K-Means，DBSCAN既可以适用于凸样本集，也可以适用于非凸样本集。DBSCAN算法的显著优点是聚类速度快且能够有效处理噪声点和发现任意形状的空间聚类。

DBSCAN是基于一组邻域来描述样本集的紧密程度的，参数(ϵϵ, MinPts)用来描述邻域的样本分布紧密程度。其中，ϵϵ描述了某一样本的邻域距离阈值，MinPts描述了某一样本的距离为ϵϵ的邻域中样本个数的阈值。

补充概念：

假设我的样本集是D=(x1,x2,...,xm)(x1,x2,...,xm),则DBSCAN具体的密度描述定义如下：

1） ϵϵ-邻域：对于xj∈Dxj∈D，其ϵϵ-邻域包含样本集D中与xjxj的距离不大于ϵϵ的子样本集，即Nϵ(xj)={xi∈D|distance(xi,xj)≤ϵ}Nϵ(xj)={xi∈D|distance(xi,xj)≤ϵ}, 这个子样本集的个数记为|Nϵ(xj)||Nϵ(xj)|　

2) 核心对象：对于任一样本xj∈Dxj∈D，如果其ϵϵ-邻域对应的Nϵ(xj)Nϵ(xj)至少包含MinPts个样本，即如果|Nϵ(xj)|≥MinPts|Nϵ(xj)|≥MinPts，则xjxj是核心对象。　

3）密度直达：如果xixi位于xjxj的ϵϵ-邻域中，且xjxj是核心对象，则称xixi由xjxj密度直达。注意反之不一定成立，即此时不能说xjxj由xixi密度直达, 除非且xixi也是核心对象。

4）密度可达：对于xixi和xjxj,如果存在样本样本序列p1,p2,...,pTp1,p2,...,pT,满足p1=xi,pT=xjp1=xi,pT=xj, 且pt+1pt+1由ptpt密度直达，则称xjxj由xixi密度可达。也就是说，密度可达满足传递性。此时序列中的传递样本p1,p2,...,pT−1p1,p2,...,pT−1均为核心对象，因为只有核心对象才能使其他样本密度直达。注意密度可达也不满足对称性，这个可以由密度直达的不对称性得出。

5）密度相连：对于xixi和xjxj,如果存在核心对象样本xkxk，使xixi和xjxj均由xkxk密度可达，则称xixi和xjxj密度相连。注意密度相连关系是满足对称性的。

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

二、算法步骤

需要两个参数：ε (eps) 和形成高密度区域所需要的最少点数 (minPts)

它由一个任意未被访问的点开始，然后探索这个点的 ε-邻域，如果 ε-邻域里有足够的点，则建立一个新的聚类，否则这个点被标签为杂音。注意这个点之后可能被发现在其它点的 ε-邻域里，而该 ε-邻域可能有足够的点，届时这个点会被加入该聚类中。

三、学习资料

学习视频：https://www.bilibili.com/video/av29441170?from=search&seid=13770901324831569072

（是B站的视频，up主讲得深入浅出，有需要的boy可以自己去看一下，这个算法很简单）

动画演示网站：https://www.naftaliharris.com/blog/visualizing-dbscan-clustering/

（上面包括DBSCAN、kmeans等算法的演示）

四、算法优缺点

DBSCAN的主要优点有：

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

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

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

DBSCAN的主要缺点有：

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

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

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

五、算法Python实现

Python内置鸢尾花数据集实现DBSCAN算法

import matplotlib.pyplot as plt 
import numpy as np 
from sklearn.cluster import KMeans
from sklearn import datasets 
from sklearn.cluster import DBSCAN
  
iris = datasets.load_iris() 
X = iris.data[:, :4] # #表示我们只取特征空间中的4个维度
print(X.shape)

# 绘制数据分布图
plt.scatter(X[:, 0], X[:, 1], c="red", marker='o', label='see') 
plt.xlabel('sepal length') 
plt.ylabel('sepal width') 
plt.legend(loc=2) 
plt.show() 
  

(150, 4)

#核心代码
dbscan = DBSCAN(eps=0.4, min_samples=9)
dbscan.fit(X) 
label_pred = dbscan.labels_

# 绘制DBSCANs结果
x0 = X[label_pred == 0]
x1 = X[label_pred == 1]
x2 = X[label_pred == 2]
plt.scatter(x0[:, 0], x0[:, 1], c="red", marker='o', label='label0') 
plt.scatter(x1[:, 0], x1[:, 1], c="green", marker='*', label='label1') 
plt.scatter(x2[:, 0], x2[:, 1], c="blue", marker='+', label='label2') 
plt.xlabel('sepal length') 
plt.ylabel('sepal width') 
plt.legend(loc=2) 
plt.show()

改变参数之后：

 dbscan = DBSCAN(eps=0.6, min_samples=5)

dbscan = DBSCAN(eps=0.2, min_samples=6)

也可以是使用上一篇中的数据2Ddata.txt：https://pan.baidu.com/s/15r58ohVWUcywdXB2uEDv2w

#替换的代码部分
#iris = datasets.load_iris() 
#X = iris.data[:, :4] # #表示我们只取特征空间中的4个维度
#print(X.shape)

X = np.loadtxt('2Ddata.txt')
print(X)

我设置的参数是 dbscan = DBSCAN(eps=1, min_samples=3)

原始图为：

聚类后为：

做K-means聚类算法代码：

#数据和绘图代码同DBSCAN算法的相同
import matplotlib.pyplot as plt 
import numpy as np 
from sklearn.cluster import KMeans
from sklearn import datasets 
  
iris = datasets.load_iris() 
X = iris.data[:, :4] # #表示我们取特征空间中的4个维度
print(X.shape)
  
# 绘制数据分布图
plt.scatter(X[:, 0], X[:, 1], c="red", marker='o', label='see') 
plt.xlabel('sepal length') 
plt.ylabel('sepal width') 
plt.legend(loc=2) 
plt.show() 
  
#核心代码
estimator = KMeans(n_clusters=3) # 构造聚类器
estimator.fit(X) # 聚类
label_pred = estimator.labels_ # 获取聚类标签

# 绘制k-means结果
x0 = X[label_pred == 0]
x1 = X[label_pred == 1]
x2 = X[label_pred == 2]
plt.scatter(x0[:, 0], x0[:, 1], c="red", marker='o', label='label0') 
plt.scatter(x1[:, 0], x1[:, 1], c="green", marker='*', label='label1') 
plt.scatter(x2[:, 0], x2[:, 1], c="blue", marker='+', label='label2') 
plt.xlabel('sepal length') 
plt.ylabel('sepal width') 
plt.legend(loc=2) 
plt.show()