DBSCAN

2020-04-20 本文已影响0人 dingtom

DBSCAN(Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法)是一种很典型的密度聚类算法，和K-Means，BIRCH这些一般只适用于凸样本集的聚类相比，DBSCAN既可以适用于凸样本集，也可以适用于非凸样本集。

1.原理：

$\epsilon$ 两个样本的最小距离，它的含义为：如果两个样本的距离小于或等于值 $\epsilon$ 那么这两个样本互为邻域。

MinPts：形成簇类所需的最小样本个数，比如MinPts等于5，形成簇类的前提是至少有一个样本的 $\epsilon$ -邻域大于等于5。

如果 $\epsilon$ 值取的太小，部分样本误认为是噪声点（白色）； $\epsilon$ 值取的多大，大部分的样本会合并为同一簇类。同样的，若MinPts值过小，则所有样本都可能为核心样本；MinPts值过大时，部分样本误认为是噪声点（白色）

minPts必须大于等于3，因此一般认为minPts=2*dim，若数据集越大，则minPts的值选择的亦越大。
$\epsilon$ 值常常用k-距离曲线（k-distance graph）得到，计算每个样本与所有样本的距离，选择k个最近邻的距离并从大到小排序，得到k-距离曲线，曲线拐点对应的距离设置为 $\epsilon$ 如下图：

一般选择 $\epsilon$ 值等于第（minPts-1）的距离，计算样本间的距离前需要对数据进行归一化，使所有特征值处于同一尺度范围
如果(k+1)-距离曲线和k-距离曲线没有明显差异，那么minPts设置为k值。

首先确定半径 $\epsilon$ 和minPoints. 从一个没有被访问过的任意数据点开始，以这个点为中心， $\epsilon$ 为半径的圆内包含的点的数量是否大于或等于minPoints，如果大于或等于minPoints则改点被标记为central point,反之则会被标记为noise point。
重复1的步骤，如果一个noise point存在于某个central point为半径的圆内，则这个点被标记为边缘点，反之仍为noise point。重复步骤1，直到所有的点都被访问过。

2.总结

优点：

1）DBSCAN不需要指定簇类的数量；
2）DBSCAN可以处理任意形状的簇类；
3）DBSCAN可以检测数据集的噪声，且对数据集中的异常点不敏感；
4）DBSCAN结果对数据集样本的随机抽样顺序不敏感（样本的顺序不一样，结果也可能不一样，如非核心点处于两个聚类的边界，若核心点抽样顺序不同，非核心点归于不同的簇类）；

缺点：

1）DBSCAN最常用的距离度量为欧式距离，对于高维数据集，会带来维度灾难，导致选择合适的 $\epsilon$ 值很难；
2）若不同簇类的样本集密度相差很大，则DBSCAN的聚类效果很差，因为这类数据集导致选择合适的minPts和 $\epsilon$ 值非常难，很难适用于所有簇类。

sklearn

*class *`sklearn.cluster.``DBSCAN`(*eps=0.5*, *min_samples=5*, *metric='euclidean'*, *metric_params=None*, *algorithm='auto'*, *leaf_size=30*, *p=None*, *n_jobs=None*)

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler

# 生成随机簇类数据
X, y = make_blobs(random_state=170,n_samples=600,centers=5)
# 绘制延伸图
plt.scatter(X[:,0],X[:,1])
plt.xlabel("Feature 0")
plt.ylabel("Feature 1")
plt.show()
# dbscan聚类算法 按照经验MinPts=2*ndims，因此我们设置MinPts=4。
dbscan = DBSCAN(eps=1, min_samples=4)
clusters = dbscan.fit_predict(X)
# 绘制dbscan聚类结果
plt.scatter(X[:,0],X[:,1],c=clusters,cmap="plasma")
plt.xlabel("Feature 0")
plt.ylabel("Feature 1")
plt.title("eps=0.5,minPts=4")
plt.show()
# 性能评价指标ARI
from sklearn.metrics.cluster import adjusted_rand_score
# ARI指数  ARI= 0.99为了较少算法的计算量，我们尝试减小MinPts的值。
print("ARI=",round(adjusted_rand_score(y,clusters),2))

DBSCAN

1.原理：

2.总结

sklearn

猜你喜欢

热点阅读