DBSCAN

DBSCAN的全部英文是Density-Based Spatial Clustering of Applications with Noise，中文是“基于密度的带有噪声的空间聚类”。DBSCAN是一个比较有代表性的基于密度的聚类算法，与划分和层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在噪声的空间数据库中发现任意形状的聚类。

该算法利用基于密度的聚类的概念，即要求聚类空间中的一定区域内（用Eps定义出的半径）所包含对象（点或其他空间对象）的数目不小于某一给定阈值（用MinPts定义的聚类点数）。

DBSCAN算法的显著优点是聚类能够有效处理噪声点和发现任意形状的空间聚类。但是由于它直接对整个数据库进行操作且进行聚类时使用了一个全局性的表征密度的参数，因 此也具有两个比较明显的弱点：

  • 对于高维问题， 基于Eps和MinPts密度定义是个很大问题
  • 当簇的密度变化太大时，聚类结果较差
  • 当数据量增大时，要求较大的内存支持，I/0消耗也很大

DBSCAN算法的目是基于密度寻找被低密度区域分离的高密度，以此来实现不同样本点的聚类。跟传统聚类算法如K-Means相比，它具有以下优点：

  • 原始数据集的分布没有明显要求，因此数据集适用性更广，尤其是非凸装、圆环形等异形簇分布的识别较好；
  • 与K-Means相比，无需指定聚类数量，对结果的先验要求不高；
  • 由于DBSCAN可区分核心对象、边界点和噪音点，因此对噪声的过滤效果好。

基于密度的定义，可将所有样本点分为三类：

  • 稠密区域内部的点（核心点）：在半径Eps内含有超过MinPts数目的点。
  • 稠密区域边缘上的点（边界点）：在半径Eps内点的数量小于MinPts（即不是核心点），但是其邻域内包含至少一个核心点。
  • 稀疏区域中的点（噪声或背景点）： 任何不是核心点或边界点的点。

用图形表示如下图：

DBSCAN11

 
DBSCAN应用

以下使用Python机器学习库SKlearn中的DBSCAN来进行演示演示，目标是对随机生成的数据集进行聚类。
 

  1. #coding:utf-8   
  2.   
  3. import numpy as np   
  4. from sklearn.cluster import DBSCAN   
  5. from sklearn import metrics   
  6. from sklearn.datasets.samples_generator import make_blobs   
  7. from sklearn.preprocessing import StandardScaler   
  8. import matplotlib.pyplot as plt   
  9.   
  10. # 生成训练数据   
  11. centers = [[1, 1], [-1, -1], [1, -1]]   
  12. X, labels_true = make_blobs(n_samples=750, centers=centers, cluster_std=0.4, random_state=0)   
  13.   
  14. X = StandardScaler().fit_transform(X)   
  15.   
  16. # 训练DBSCAN   
  17. db = DBSCAN(eps=0.3, min_samples=10).fit(X)   
  18. core_samples_mask = np.zeros_like(db.labels_, dtype=bool)   
  19. core_samples_mask[db.core_sample_indices_] = True  
  20. labels = db.labels_   
  21. new_X = np.column_stack((X, labels))   
  22.   
  23. # 如果存在噪音则去除   
  24. n_clusters_ = len(set(labels)) - (1 if -1 in labels else 0)   
  25.   
  26. print('Estimated number of clusters: %d' % n_clusters_)   
  27. print("Homogeneity: %0.3f" % metrics.homogeneity_score(labels_true, labels))   
  28. print("Completeness: %0.3f" % metrics.completeness_score(labels_true, labels))   
  29. print("V-measure: %0.3f" % metrics.v_measure_score(labels_true, labels))   
  30. print("Adjusted Rand Index: %0.3f"   
  31.       % metrics.adjusted_rand_score(labels_true, labels))   
  32. print("Adjusted Mutual Information: %0.3f"   
  33.       % metrics.adjusted_mutual_info_score(labels_true, labels))   
  34. print("Silhouette Coefficient: %0.3f"   
  35.       % metrics.silhouette_score(X, labels))   
  36. print("Top 10 samples:",new_X[:10])   
  37.   
  38. # 图形展示   
  39. unique_labels = set(labels)   
  40. colors = plt.cm.Spectral(np.linspace(0, 1, len(unique_labels)))   
  41. for k, col in zip(unique_labels, colors):   
  42.     if k == -1:   
  43.         # 噪音显示为黑色.   
  44.         col = 'k'   
  45.   
  46.     class_member_mask = (labels == k)   
  47.   
  48.     xy = X[class_member_mask & core_samples_mask]   
  49.     plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=col,   
  50.              markeredgecolor='k', markersize=14)   
  51.   
  52.     xy = X[class_member_mask & ~core_samples_mask]   
  53.     plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=col,   
  54.              markeredgecolor='k', markersize=6)   
  55.   
  56. plt.title('Estimated number of clusters: %d' % n_clusters_)   
  57. plt.show()   

运行结果如下：

  1. Estimated number of clusters: 3   
  2. Homogeneity: 0.953   
  3. Completeness: 0.883   
  4. V-measure: 0.917   
  5. Adjusted Rand Index: 0.952   
  6. Adjusted Mutual Information: 0.883   
  7. Silhouette Coefficient: 0.626   
  8. ('Top 10 samples:', array(   
  9.       [[ 0.49426097,  1.45106697,  1.        ],   
  10.        [-1.42808099, -0.83706377,  0.        ],   
  11.        [ 0.33855918,  1.03875871,  1.        ],   
  12.        [ 0.11900101, -1.05397553,  2.        ],   
  13.        [ 1.1224246 ,  1.77493654,  1.        ],   
  14.        [-1.2615699 ,  0.27188135,  0.        ],   
  15.        [-1.30154775, -0.76206203,  0.        ],   
  16.        [ 0.58569865, -0.33910463,  2.        ],   
  17.        [ 1.08247212,  0.8868554 ,  1.        ],   
  18.        [ 1.01416668,  1.34114022,  1.        ]]))   


dbscan_result11
DBSCAN可配置的参数如下，重点是半径eps和密度min_samples的定义：

  1. class sklearn.cluster.DBSCAN(eps=0.5, min_samples=5, metric='euclidean', algorithm='auto', leaf_size=30, p=None, random_state=None)  


 
DBSCAN应用场景：

  • 数据集聚类，如会员聚类；
  • 图像切割；

 

尾巴

DBSCAN的最大优势是它对于原始数据集的分布几乎没有要求，并且对噪音不敏感，因此，它的模型适应性和鲁棒性相对较强；但是，它对于大数据集的处理速度只能算是一般，以下是分别针对100，1000，10000，100000，1000000样本量进行聚类（类别数为三，二维），得到三类算法KMeans、MiniBatchKMeans和DBSCAN的聚类用时。由于三者计算用时差异比较大，因此取对数进行图形对比。从结果可以看出，MiniBatchKMeans由于是KMeans的优化版本，因此用时少是毫无疑问的，重点是KMeans和DBSCAN的对比发现，DBSCAN在对100万数据聚类时用时竟然达到40多分钟。
dbscan_time11

  1. ('DBSCAN Time:', [[100, 0.015000104904174805], [1000, 0.2969999313354492], [10000, 3.9000000953674316], [100000, 69.59299993515015], [1000000,2854.7410000000]])   
  2. ('MiniBatchKMeans Time:', [[100, 0.016000032424926758], [1000, 0.016000032424926758], [10000, 0.031000137329101562], [100000, 0.20300006866455078], [1000000, 1.748000144958496]])   
  3. ('KMeans Time:', [[100, 0.014999866485595703], [1000, 0.015000104904174805], [10000, 0.07799983024597168], [100000, 0.7639999389648438], [1000000, 6.769999980926514]])   


====================【好书推荐，我为自己代言】====================

《Python数据分析与数据化运营》第二版上市啦！

50+数据流工作知识点
14个数据分析与挖掘主题
8个综合性运营分析案例
涵盖会员、商品、流量、内容4大主题
360°把脉运营问题并贴合数据场景落地


本书主要基于Python实现，其中主要用到的计算库是numpy、pandas和sklearn，其他相关库还包括：
  • 标准库：re、time、datetime、json、 base64、os、sys、cPickle、tarfile
  • Python调用R的rpy2
  • 统计分析：Statsmodels
  • 中文处理：结巴分词
  • 文本挖掘：Gensim
  • 数据挖掘和算法：XGboost、gplearn、TPOT
  • 爬虫和解析：requests、Beautiful Soup、xml
  • 图像处理：OpenCV和PIL/Pollow
  • 数据读取：xlrd、pymongo、pymysql
  • 数据预处理：imblearn
  • 展示美化类：Matplotlib、pyecharts、graphviz、prettytable、wordcloud、mpl_toolkits、pydotplus
如果你对以下内容感兴趣，那么本书将值得一看：
  • KMeans聚类的自动K均值的确立方法
  • 基于软方法的多分类模型组合评估模型的应用
  • 基于自动下探（下钻、细分）的应用
  • 基于增量学习的多项式贝叶斯分类
  • pipeline管道技术的应用
  • 基于超参数的自动参数值的优化方法
  • 特征自动选择
  • 文本分类、文本主题挖掘
  • 基于自动时间序列ARIMA的P、D、Q的调整
  • python决策树规则输出
  • 基于自定义图像的文本标签云
  • 非结构化数据，例如图像、音频、文本等处理
  • 对象持久化处理
  • 如何使用Python调用R实现数据挖掘
  • 自动化学习：增加了对于自动化数据挖掘与机器学习的理论、流程、知识和应用库介绍，并基于TPOT做自动化回归和分类学习案例演示
有关这本书的写作感受、详细内容介绍、附件（含数据和代）下载、关键知识和方法以及完整书稿目录，请访问《Python数据分析与数据化运营》第二版出版了！要购买此书，可以去京东、当当和天猫等查看。

发表评论

电子邮件地址不会被公开。 必填项已用*标注