深圳网站建设公司简介,广告网站策划方案,网站下载免费,万网域名查询接口在前面的文章中#xff0c;我们分别介绍了《K-means原理和实践》和《Birch和层次聚类》两种聚类算法#xff0c;本文我们继续介绍另一种常用的聚类算法DBSCAN。相对于前两种算法#xff0c;DBSCAN的原理要简单的多#xff0c;但是这并不意味着它的效果就会差#xff0c;在…在前面的文章中我们分别介绍了《K-means原理和实践》和《Birch和层次聚类》两种聚类算法本文我们继续介绍另一种常用的聚类算法DBSCAN。相对于前两种算法DBSCAN的原理要简单的多但是这并不意味着它的效果就会差在很多算法表现不好的非凸数据集上凸数据集可以简单理解为数据集中的任意两点连线上的点都在数据集内DBSCAN往往能取得较好的效果见下图这也是DBSCAN最大的优势而且DBSCAN还可以作为异常检测算法发现噪声点离群点。另外本文讲解原理篇多引用了文献[1]的内容有时间的话建议也看看原文。 一、原理
DBSCANDensity-Based Spatial Clustering of Applications with Noise具有噪声的基于密度的聚类方法是一种基于密度的空间聚类算法。 该算法将具有足够密度的区域划分为簇并在具有噪声的空间数据库中发现任意形状的簇它将簇定义为密度相连的点的最大集合。关于什么是密度相连我们下面解释。
1.1 密度定义
DBSCAN是基于一组邻域来描述样本集的紧密程度的参数(eps, min_samples)用来描述邻域的样本分布紧密程度。其中eps描述了某一样本的邻域距离阈值min_samples描述了某一样本的距离为eps的邻域中样本个数的阈值[1]。
假设已知样本集 则DBSCAN具体的密度描述定义如下
eps-邻域对于 其eps-邻域包含样本集D中与 的距离不大于eps的子样本集这个子样本集的个数记为 这里需要注意距离并不一定是欧氏距离具体在API章节会再详细介绍。核心对象核心对象又叫核心点。对于任一样本 如果其eps-邻域对应的 不小于 min_samples即如果 ≥ min_samples则 是核心对象。密度直达如果 位于 的eps-邻域中且 是核心对象则称 由 密度直达。注意反之不一定成立即此时不能说 由 密度直达, 除非且 也是核心对象。密度可达对于 和 ,如果存在样本序列 , 满足 且 由 密度直达则称 由 密度可达。也就是说密度可达满足传递性。此时序列中的传递样本 均为核心对象因为只有核心对象才能使其他样本密度直达。注意密度可达也不满足对称性这个可以由密度直达的不对称性得出。密度相连对于 和 ,如果存在核心对象样本 使 和 均由 密度可达则称 和 密度相连。注意密度相连关系是满足对称性的。这一点由密度可达的定义可以很容易得出。
上面的定义理解起来会有点抽象看下面这个图就比较容易理解了图中min_samples5红色点都是核心对象。位于每一个核心对象圆圈内eps-邻域的点都可以由对应的核心对象密度直达图中绿色箭头连接起来的核心对象都是密度可达的样本序列在这些密度可达的样本序列的eps-邻域黑色圆圈内的点内所有的样本相互都是密度相连的。 1.2 聚类原理
有了密度定义DBSCAN的聚类原理就很简单了由密度可达关系导出的最大密度相连的样本集合即为我们最终聚类的一个类别或者说一个簇。所以任意一个DBSACN簇都至少有一个核心对象如果有多于一个核心对象则这些核心对象必然可以组成密度可达序列。
那么怎么才能找到这样的簇样本集合呢DBSCAN使用的方法很简单它任意选择一个没有类别的核心对象作为种子然后找到所有这个核心对象能够密度可达的样本集合即为一个聚类簇。接着继续选择另一个没有类别的核心对象去寻找密度可达的样本集合这样就得到另一个聚类簇。一直运行到所有核心对象都有类别为止。参考上图的两个绿色箭头路径聚类的两个簇。
聚类完成后样本集中的点一般可以分为三类核心点边界点和离群点异常点。边界点是簇中的非核心点离群点就是样本集中不属于任意簇的样本点。此外在簇中还有一类特殊的样本点该类样本点可以由两个核心对象密度直达但是这两个核心对象又不能密度可达属于两个簇该类样本的最终划分簇一般由算法执行顺序决定即先被划分到哪个簇就属于哪个簇也就是说DBSCAN的算法不是完全稳定的算法。这也意味着DBSCAN是并行算法对于两个并行运算结果簇如果两个簇中存在两个核心对象密度可达则两个簇聚为一个簇。
根据上面介绍的原理可知DBSCAN的主要计算量仍然是在距离上这里同样可以借鉴 elkan K-means 和 KNN KD树/球树的原理进行优化减少计算量。
1.3 调参
DBSCAN有两个关键参数eps,和min_samples一般可通过网格搜索加无监督聚类指标的方法调参具体指标可参考kmeans篇也可以结合特征的方差、均值分布来调参。对于特定场景的业务如果已知某些先验参数例如簇数则可以通过该指标对网格参数结果进行筛选然后再从剩下的聚类结果中选择合适的结果。如果是有监督聚类建模还可以在聚类之前通过 NCA 等方法对特征进行变换一般对于 DBSCAN 这种基于密度聚类的算法可以得到一个更好的结果。
1.4 优缺点
1优点
不需要预先指定聚类数量可以对任意形状的稠密数据集进行聚类相对的K-Means之类的聚类算法一般只适用于凸数据集。可以在聚类的同时发现异常点对数据集中的异常点不敏感。聚类结果没有偏倚相对的K-Means之类的聚类算法初始值对聚类结果有很大影响。
2缺点
如果样本集的密度不均匀、聚类间距差相差很大时聚类质量较差这时用DBSCAN聚类一般不适合。如果样本集较大时聚类收敛时间较长此时可以对搜索最近邻时建立的KD树或者球树进行规模限制来改进。调参相对于传统的K-Means之类的聚类算法稍复杂主要需要对距离阈值eps邻域样本数阈值min_samples联合调参不同的参数组合对最后的聚类效果有较大影响。eps越大得到的簇数也就越少得到的簇就越大离群点就越少min_samples越大离群点就越多得到的簇越小。
最后再给一个聚类算法的可视化测试网址有兴趣的可以去玩玩对于理解聚类的过程非常友好
https://www.naftaliharris.com/blog/visualizing-dbscan-clustering/
二、实践
本节我们同样通过 sklearn 来学习 DBSCAN的使用。
2.1 API
sklearn.cluster.DBSCAN(
eps0.5,
*,
min_samples5, ## min_samples参数计算的时候注意是包括样本点自身的
metriceuclidean, ## 距离度量方式默认是欧氏距离具体选择可参考KNN篇选择precomputed表示自己计算距离fit时X传入距离矩阵即可
metric_paramsNone, ## metric的辅助参数根据metric的值决定
algorithmauto, ## 近邻点的查找方法可选‘auto’, ‘ball_tree’, ‘kd_tree’, ‘brute’。默认auto会根据样本数量自动选择具体可参考前面KNN的文章
leaf_size30, ## BallTree or cKDTree参数
pNone, ## 闵可夫斯基距离的p默认None就是2表示欧式距离
n_jobsNone)
labels_ 属性可以返回聚类结果-1表示是离群点。
另外提一下关于 DBSCAN 预测的问题可以发现在 sklearn 中 DBSCAN 是没有 predict 方法的因为很多聚类算法和 kmeans 原理不同不能根据训练样本的簇中心点来预测新的样本所属簇。不过我们可以自己根据原理来实现预测过程第一种就是像 kmeans 一样得到簇结果以后计算出簇的中心点根据新样本距离所有簇中心的远近判断所属的簇但是这种方法对于 DBSCAN 不适合。第二种是基于聚类结果再运行 KNN 算法找到距离新样本点最近的一个或者多个样本点所属的簇就是新样本点所属的簇。
2.2 实践
使用sklearn先对特征进行归一化再聚类。
import numpy as npfrom sklearn.cluster import DBSCAN
from sklearn import metrics
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler# #############################################################################
# Generate sample data
centers [[1, 1], [-1, -1], [1, -1]]
X, labels_true make_blobs(n_samples750, centerscenters, cluster_std0.4,random_state0)X StandardScaler().fit_transform(X)# #############################################################################
# Compute DBSCAN
db DBSCAN(eps0.3, min_samples10).fit(X)
core_samples_mask np.zeros_like(db.labels_, dtypebool)
core_samples_mask[db.core_sample_indices_] True
labels db.labels_# Number of clusters in labels, ignoring noise if present.
n_clusters_ len(set(labels)) - (1 if -1 in labels else 0)
n_noise_ list(labels).count(-1)print(Estimated number of clusters: %d % n_clusters_)
print(Estimated number of noise points: %d % n_noise_)
print(Homogeneity: %0.3f % metrics.homogeneity_score(labels_true, labels))
print(Completeness: %0.3f % metrics.completeness_score(labels_true, labels))
print(V-measure: %0.3f % metrics.v_measure_score(labels_true, labels))
print(Adjusted Rand Index: %0.3f% metrics.adjusted_rand_score(labels_true, labels))
print(Adjusted Mutual Information: %0.3f% metrics.adjusted_mutual_info_score(labels_true, labels))
print(Silhouette Coefficient: %0.3f% metrics.silhouette_score(X, labels))# #############################################################################
# Plot result
import matplotlib.pyplot as plt# Black removed and is used for noise instead.
unique_labels set(labels)
colors [plt.cm.Spectral(each)for each in np.linspace(0, 1, len(unique_labels))]
for k, col in zip(unique_labels, colors):if k -1:# Black used for noise.col [0, 0, 0, 1]class_member_mask (labels k)xy X[class_member_mask core_samples_mask]plt.plot(xy[:, 0], xy[:, 1], o, markerfacecolortuple(col),markeredgecolork, markersize14)xy X[class_member_mask ~core_samples_mask]plt.plot(xy[:, 0], xy[:, 1], o, markerfacecolortuple(col),markeredgecolork, markersize6)plt.title(Estimated number of clusters: %d % n_clusters_)
plt.show()#######################运行结果################################Estimated number of clusters: 3
Estimated number of noise points: 18
Homogeneity: 0.953
Completeness: 0.883
V-measure: 0.917
Adjusted Rand Index: 0.952
Adjusted Mutual Information: 0.916
Silhouette Coefficient: 0.626 参考文献
[1] https://www.cnblogs.com/pinard/p/6208966.html
[2] https://blog.csdn.net/u012848304/article/details/108710864
