——————————非原创,来自知乎https://zhuanlan.zhihu.com/p/77043965————————————————————————————
1.定义
DBSCAN将簇定义为密度相连的点的最大集合,能够把具有足够高密度的区域划分为簇,并可在噪声的空间数据库中发现任意形状的聚类。
2.思想
由密度可达关系导出的最大密度相连的样本集合,即为我们最终聚类的一个类别,或者说一个簇。(注意是密度相连的集合),簇里面可以有一个或者多个核心对象。它任意选择一个没有类别的核心对象作为种子,然后找到所有这个核心对象能够密度可达的样本集合,即为一个聚类簇。接着继续选择另一个没有类别的核心对象去寻找密度可达的样本集合,这样就得到另一个聚类簇 (这样的得到都肯定是密度相连的)。一直运行到所有核心对象都有类别为止。
3.问题
- 异常点问题:一些异常样本点或者说少量游离于簇外的样本点,这些点不在任何一个核心对象在周围,在DBSCAN中,我们一般将这些样本点标记为噪音点。
- 距离度量问题:即如何计算某样本和核心对象样本的距离。在DBSCAN中,一般采用最近邻思想,采用某一种距离度量来衡量样本距离,比如欧式距离、曼哈顿距离等。
- 数据点优先级分配问题:例如某些样本可能到两个核心对象的距离都小于 ϵ ,但是这两个核心对象由于不是密度直达,又不属于同一个聚类簇,那么如果界定这个样本的类别呢?一般来说,此时 DBSCAN采用先来后到,先进行聚类的类别簇会标记这个样本为它的类别。也就是说DBSCAN的算法不是完全稳定的算法
4.使用`numpy`实现`DBSCAN`算法
import numpy as np import matplotlib.pyplot as plt from scipy.spatial.distance import pdist from scipy.spatial.distance import squareform import time # 计算距离矩阵 def compute_squared_EDM(X): return squareform(pdist(X,metric='euclidean')) # DBSCAN算法核心过程 def DBSCAN(data,eps,minPts): # 获得距离矩阵 disMat = compute_squared_EDM(data) # 获得数据的行和列(一共有n条数据) n, m = data.shape # 将矩阵的中小于minPts的数赋予1,大于minPts的数赋予零,然后1代表对每一行求和,然后求核心点坐标的索引 core_points_index = np.where(np.sum(np.where(disMat <= eps, 1, 0), axis=1) >= minPts)[0] # 初始化类别,-1代表未分类。 labels = np.full((n,), -1) clusterId = 0 # 遍历所有的核心点 for pointId in core_points_index: # 如果核心点未被分类,将其作为的种子点,开始寻找相应簇集 if (labels[pointId] == -1): # 首先将点pointId标记为当前类别(即标识为已操作) labels[pointId] = clusterId # 然后寻找种子点的eps邻域且没有被分类的点,将其放入种子集合 neighbour=np.where((disMat[:, pointId] <= eps) & (labels==-1))[0] seeds = set(neighbour) # 通过种子点,开始生长,寻找密度可达的数据点,一直到种子集合为空,一个簇集寻找完毕 while len(seeds) > 0: # 弹出一个新种子点 newPoint = seeds.pop() # 将newPoint标记为当前类 labels[newPoint] = clusterId # 寻找newPoint种子点eps邻域(包含自己) queryResults = np.where(disMat[:,newPoint]<=eps)[0] # 如果newPoint属于核心点,那么newPoint是可以扩展的,即密度是可以通过newPoint继续密度可达的 if len(queryResults) >= minPts: # 将邻域内且没有被分类的点压入种子集合 for resultPoint in queryResults: if labels[resultPoint] == -1: seeds.add(resultPoint) # 簇集生长完毕,寻找到一个类别 clusterId = clusterId + 1 return labels # 将分类后的数据可视化显示 def plotFeature(data, labels_): clusterNum=len(set(labels_)) fig = plt.figure() scatterColors = ['black', 'blue', 'green', 'yellow', 'red', 'purple', 'orange', 'brown'] ax = fig.add_subplot(111) for i in range(-1,clusterNum): colorSytle = scatterColors[i % len(scatterColors)] subCluster = data[np.where(labels_==i)] ax.scatter(subCluster[:,0], subCluster[:,1], c=colorSytle, s=12) plt.show() # 加载数据 data = np.loadtxt("./cluster2.csv", delimiter=",") start = time.clock() # DBSCAN聚类并返回标识;ϵ=2,且MinPts=15 labels=DBSCAN(data,3,30) end = time.clock() print('finish all in %s' % str(end - start)) plotFeature(data, labels)
使用scikit-learn调用DBSCAN算法
1 # -*- coding: utf-8 -*- 2 import numpy as np 3 from sklearn.cluster import DBSCAN 4 # 加载数据 5 data=np.loadtxt("788points.txt",delimiter=",") 6 # 构造一个ϵ=2,MinPts=15的聚类器,距离使用欧式距离 7 estimator=DBSCAN(eps=2,min_samples=15,metric='euclidean') 8 # 聚类数据 9 estimator.fit(data) 10 # 输出聚类都类别(-1代表异常点) 11 print(estimator.labels_)
5.优缺点
- 可以对任意形状的稠密数据集进行聚类,相对的,K-Means之类的聚类算法一般只适用于凸数据集。
- 可以在聚类的同时发现异常点,对数据集中的异常点不敏感。
- 聚类结果没有偏倚,相对的,K-Means之类的聚类算法初始值对聚类结果有很大影响。
- DBSCAN的主要缺点有:
- 如果样本集的密度不均匀、聚类间距差相差很大时,聚类质量较差,这时用DBSCAN聚类一般不适合。
- 如果样本集较大时,聚类收敛时间较长
- 调参相对于传统的K-Means之类的聚类算法稍复杂,主要需要对距离阈值ϵ,邻域样本数阈值MinPts联合调参,不同的参数组合对最后的聚类效果有较大影响。