DBSCAN原理及实现

项目地址：https://github.com/Daya-Jin/ML_for_learner/blob/master/cluster/DBSCAN.ipynb
原博客：https://daya-jin.github.io/2018/08/06/DBSCAN/

模型概述

DBSCAN是一种聚类算法，首先明确几个概念：

  • \epsilon-邻域：对任一样本点x^{(i)}，数据集D中与该样本点的距离不大于\epsilon的其余样本点构成的集合，该集合内的样本数为该点的密度，即dense_i=N_{\epsilon}(x^{(i)})=\{x^{(j)}\in{D}\|dist(x^{(i)},x^{(j)})\le\epsilon\}
  • 核心对象(core object)：若某一样本的密度不小于一个阈值，即dense_i\geMin_pts，则该样本是一个核心对象
  • 边界对象：若某一样本的密度小于Min_pts，则该样本成为边界对象；特别地，密度为1的样本被称为噪声样本
  • 密度直达：核心对象直达其邻域内的样本点，直达方向由核心对象指向其邻域内的样本点
  • 密度可达：对两个样本点x^{(i)}与x^{(j)}，若存在一条密度直达链x^{(i)}\rightarrow...{\rightarrow}x^{(j)}，则称x^{(i)}可达x^{(j)}，方向由x^{(i)}指向x^{(j)}，前者必须为核心对象，后者不作要求
  • 密度相连：同一个核心对象可达的两样本点称为密度相连，即同时存在两条直达链：x^{(i)}\rightarrow...{\rightarrow}x^{(j)}与x^{(i)}\rightarrow...{\rightarrow}x^{(k)}，x^{(j)}与x^{(k)}密度相连

DBSCAN算法将所有密度相连的样本聚成一类。换个角度来说，DBSCAN会尽量多的寻找密度相连的核心对象（容易推出密度相连在核心对象上满足交换律），然后将这些核心对象及其邻域样本都归为一类。

实现指导

完整代码

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

  • DBSCAN算法原理
    1. 密度聚类原理 DBSCAN是一种基于密度的聚类算法，这类密度聚类算法一般假定类别可以通过样本分布的紧密程度...
    程序猿小小白阅读 9,724评论 0赞 3
  • 机器学习-DBSCAN
    积跬步以致千里,积怠惰以致深渊 主要内容 DBSCAN（Density-Based Spatial Cluster...
    指尖上的魔术师阅读 4,626评论 0赞 2
  • DBSCAN之所以然
    基于密度的方法(Density-based methods) 基本思想 基于密度的方法：k-means解决不了不规...
    偲偲爸阅读 4,798评论 0赞 1
  • DBSCAN聚类算法
    一、算法描述 DBSCAN(Density-Based Spatial Clustering of Applic...
    owolf阅读 19,790评论 2赞 8
  • DBSCAN 聚类
    以下使用Out[数字]:的方式表示代码输出结果 DBSCAN 密度聚类算法 密度聚类是一类常用并且有效的聚类方法，...
    魏允臣阅读 9,191评论 0赞 8

友情链接更多精彩内容