程序员经验分享-hwhale

DBSCAN聚类算法

2023-05-16

DBSCAN是一种非常著名的基于密度的聚类算法。其英文全称是 Density-Based Spatial Clustering of Applications with Noise，意即：一种基于密度，对噪声鲁棒的空间聚类算法。直观效果上看，DBSCAN算法可以找到样本点的全部密集区域，并把这些密集区域当做一个一个的聚类簇。

DBSCAN算法具有以下特点：

  • 基于密度，对远离密度核心的噪声点鲁棒
  • 无需知道聚类簇的数量
  • 可以发现任意形状的聚类簇

1. 基本概念

1.1. 核心思想

核心思想是基于密度。直观效果上看，DBSCAN算法可以找到样本点的全部密集区域，并把这些密集区域当做一个一个的聚类簇。

1.2. 算法参数

邻域半径R和最少点数目MinPoints。这两个算法参数实际可以刻画什么叫密集：当邻域半径R内的点的个数大于最少点数目MinPoints时，就是密集。

1.3. 3种点的类别

核心点，边界点和噪声点。邻域半径R内样本点的数量大于等于minpoints的点叫做核心点。不属于核心点但在某个核心点的邻域内的点叫做边界点。既不是核心点也不是边界点的是噪声点。

1.4. 4种点的关系

密度直达，密度可达，密度相连，非密度相连。

如果P为核心点，Q在P的R邻域内，那么称P到Q密度直达。任何核心点到其自身密度直达，密度直达不具有对称性，如果P到Q密度可达，那么Q到P不一定密度可达。

如果存在核心点P2，P3，……，Pn，且P1到P2密度直达，P2到P3密度直达，……，P(n-1)到Pn密度直达，Pn到Q密度直达，则P1到Q密度可达。密度可达也不具有对称性。

如果存在核心点S，使得S到P和Q都密度可达，则P和Q密度相连。密度相连具有对称性，如果P和Q密度相连，那么Q和P也一定密度相连。密度相连的两个点属于同一个聚类簇。

如果两个点不属于密度相连关系，则两个点非密度相连。非密度相连的两个点属于不同的聚类簇，或者其中存在噪声点。

2. 算法步骤

上面这些点是分布在样本空间的众多样本，现在我们的目标是把这些在样本空间中距离相近的聚成一类。

我们发现A点附近的点密度较大，红色的圆圈根据一定的规则在这里滚啊滚，最终收纳了A附近的5个点，标记为红色也就是定为同一个簇。

其它没有被收纳的根据一样的规则成簇。

形象来说，我们可以认为这是系统在众多样本点中随机选中一个，围绕这个被选中的样本点画一个圆，规定这个圆的半径以及圆内最少包含的样本点，如果在指定半径内有足够多的样本点在内，那么这个圆圈的圆心就转移到这个内部样本点，继续去圈附近其它的样本点，类似传销一样，继续去发展下线。

等到这个滚来滚去的圈发现所圈住的样本点数量少于预先指定的值，就停止了。那么我们称最开始那个点为核心点，如A，停下来的那个点为边界点，如B、C，没得滚的那个点为离群点，如N）。

基于密度这点有什么好处呢？

我们知道kmeans聚类算法只能处理球形的簇，也就是一个聚成实心的团（这是因为算法本身计算平均距离的局限）。但往往现实中还会有各种形状，比如下面两张图，环形和不规则形，这个时候，那些传统的聚类算法显然就悲剧了。

于是就思考，样本密度大的成一类呗，这就是DBSCAN聚类算法。

2.1. 寻找核心点形成临时聚类簇

扫描全部样本点，如果某个样本点R半径范围内点数目>=MinPoints，则将其纳入核心点列表，并将其密度直达的点形成对应的临时聚类簇。

2.2. 合并临时聚类簇得到聚类簇

对于每一个临时聚类簇，检查其中的点是否为核心点，如果是，将该点对应的临时聚类簇和当前临时聚类簇合并，得到新的临时聚类簇。

重复此操作，直到当前临时聚类簇中的每一个点要么不在核心点列表，要么其密度直达的点都已经在该临时聚类簇，该临时聚类簇升级成为聚类簇。

继续对剩余的临时聚类簇进行相同的合并操作，直到全部临时聚类簇被处理。

3. DBSCAN算法迭代可视化展示

国外有一个特别有意思的网站，它可以把我们DBSCAN的迭代过程动态图画出来。

网址：Visualizing DBSCAN Clustering

设置好参数，点击GO! 就开始聚类了！

还有其他的聚类实例：

聚类1

聚类2

4. 常用评估方法：轮廓系数

这里提一下聚类算法中最常用的评估方法——轮廓系数（Silhouette Coefficient）：

  • 计算样本i到同簇其它样本到平均距离ai，ai越小，说明样本i越应该被聚类到该簇（将ai称为样本i到簇内不相似度）；

  • 计算样本i到其它某簇Cj的所有样本的平均距离bij，称为样本i与簇Cj的不相似度。定义为样本i的簇间不相似度：bi=min(bi1,bi2,...,bik2)；

说明：

  • si接近1，则说明样本i聚类合理；

  • si接近-1，则说明样本i更应该分类到另外的簇；

  • 若si近似为0，则说明样本i在两个簇的边界上；

5. sklearn调用范例

5.1. 生成样本点

# matplotlib inline
# config InlineBackend.figure_format = 'svg'
import numpy as np
import pandas as pd
from sklearn import datasets


X,_ = datasets.make_moons(500,noise = 0.1,random_state=1)
df = pd.DataFrame(X,columns = ['feature1','feature2'])

df.plot.scatter('feature1','feature2', s = 100,alpha = 0.6, title = 'dataset by make_moon');

5.2. 调用dbscan方法完成聚类

# matplotlib inline
# config InlineBackend.figure_format = 'svg'

from sklearn.cluster import dbscan

# eps为邻域半径，min_samples为最少点数目
core_samples,cluster_ids = dbscan(X, eps = 0.2, min_samples=20) 
# cluster_ids中-1表示对应的点为噪声点

df = pd.DataFrame(np.c_[X,cluster_ids],columns = ['feature1','feature2','cluster_id'])
df['cluster_id'] = df['cluster_id'].astype('i2')

df.plot.scatter('feature1','feature2', s = 100,
    c = list(df['cluster_id']),cmap = 'rainbow',colorbar = False,
    alpha = 0.6,title = 'sklearn DBSCAN cluster result');

参考文献

20分钟学会DBSCAN - 知乎

【他山之石】DBSCAN密度聚类算法（理论+图解+python代码） 

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

DBSCAN

聚类算法

DBSCAN聚类算法 的相关文章

  • Python学习2——DBSCAN聚类算法

    一 原理 参考博文 xff1a DBSCAN聚类算法Python实现 徐奕的专栏 CSDN博客 dbscan python https blog csdn net xyisv article details 88918448 DBSCAN是

  • python DBSCAN聚类算法

    文章目录 DBSCAN聚类算法基本思想基本概念工作流程参数选择DBSCAN的优劣势 代码分析 61 61 Matplotlib Pyplot 61 61 61 61 make blobs 61 61 61 61 StandardScaler

  • DBSCAN算法(python代码实现)

    DBSCAN 上次学了kmeans基于划分的方法 xff0c 这次学一个基于密度的聚类算法 xff1a DBSCAN xff08 Density Based Spatial Clustering of Applications with N

  • 【数据挖掘】DBSCAN聚类算法（python实现）

    一 python代码 39 39 39 Author Vici date 2020 5 14 39 39 39 import math 39 39 39 Point类 xff0c 记录坐标x xff0c y和点的名字id 39 39 39

  • K-means聚类算法

    K means 是我们最常用的基于欧式距离的聚类算法 xff0c 其认为两个目标的距离越近 xff0c 相似度越大 本文大致思路为 xff1a 先介绍经典的牧师 村名模型来引入 K means 算法 xff0c 然后介绍算法步骤和时间复杂度

  • DBSCAN聚类算法

    DBSCAN是一种非常著名的基于密度的聚类算法 其英文全称是 Density Based Spatial Clustering of Applications with Noise xff0c 意即 xff1a 一种基于密度 xff0c 对

  • DBSCAN算法，概念+示例，超详细！！

    DBSCAN xff08 Density Based Spatial Clustering of Applications with Noise xff09 与划分和层次聚类方法不同 xff0c 它将簇定义为密度相连的点的最大集合 xff0

  • K-means聚类算法 伪代码 python3代码

    K means 算法及其代码 K means算法介绍K means 伪代码K means python 代码 K means算法介绍 链接 模式识别 聚类分析 K means 伪代码 计算两个点之间的欧式距离 span class toke

  • 机器学习（二）：聚类算法1——K-means算法

    Kmeans是一种经典的聚类算法 xff0c 所谓聚类 xff0c 是指在没有给出目标的情况下 xff0c 将样本根据某种关系分为某几类 那在kmeans中 xff0c 是根据样本点间的距离 xff0c 将样本n分为k个类 K means实

  • DBSCAN聚类算法原理总结

    点击上方 小白学视觉 xff0c 选择加 34 星标 34 或 置顶 重磅干货 xff0c 第一时间送达 DBSCAN是基于密度空间的聚类算法 xff0c 在机器学习和数据挖掘领域有广泛的应用 xff0c 其聚类原理通俗点讲是每个簇类的密度

  • 【机器学习】DBSCAN密度聚类算法（理论 + 图解）

    文章目录 一 前言 二 DBSCAN聚类算法 三 DBSCAN算法步骤 四 算法的理解 五 常用评估方法 轮廓系数 一 前言 之前学聚类算法的时候 有层次聚类 系统聚类 K means聚类 K中心聚类 最后呢 被DBSCAN聚类算法迷上了

  • KMeans算法

    目录 一 基本概念 二 Centroid Initialization Methods 三 Mini Batch K Means 四 找寻最优的聚类数量 4 1 拐点 4 2 silhouette score 轮廓分数 五 Kmeans的优

  • Python机器学习之k-means聚类算法

    1 引言 所谓聚类 就是按照某个特定的标准将一个数据集划分成不同的多个类或者簇 使得同一个簇内的数据对象的相似性尽可能大 同时不再一个簇内的数据对象的差异性也尽可能大 聚类算法属于无监督学习算法的一种 k 均值聚类的目的是 把 n个点 可以

  • DBSCAN点云聚类

    1 DBSCAN算法原理 DBSCAN是一种基于密度的聚类方法 其将点分为核心点与非核心点 后续采用类似区域增长方式进行处理 下图为DBSCAN聚类结果 可见其可以对任意类别的数据进行聚类 无需定义类别数量 DBSCAN聚类说明 DBSCA

  • 八种点云聚类方法（一）— DBSCAN

    本文为博主原创文章 未经博主允许不得转载 本文为专栏 python三维点云从基础到深度学习 系列文章 地址为 https blog csdn net suiyingy article details 124017716 传统机器学习聚类的方

  • 层次聚类在MATLAB中实现

    层次聚类在MATLAB中实现 By Yang Liu 1 第一种方法 1 输入要聚类的数据 2 计算各个样本之间的欧氏距离 3 把距离化成矩阵 矩阵中的元素 X i j X ij Xij 表示第i个样本和第j个样

  • DBSCAN sklearn 非常慢

    我正在尝试对包含超过 100 万个数据点的数据集进行聚类 一列包含文本 另一列包含与其对应的数值 我面临的问题是它被卡住并且永远不会完成 我尝试过处理大约 100 000 个较小的数据集 它运行得相当快 但当我开始增加数据点时 它开始变慢

  • ELKI：在 Java 中的自定义对象上运行 DBSCAN

    我正在尝试在 JAVA 中使用 ELKI 来运行 DBSCAN 为了进行测试 我使用了 FileBasedDatabaseConnection 现在我想使用我的自定义对象作为参数来运行 DBSCAN 我的对象具有以下结构 public cl

  • 如何在Python中绘制k距离图

    如何在 DBSCAN 中绘制 在 python 中 给定最小点值的距离图 我正在寻找拐点和相应的 epsilon 值 在 sklearn 中 我没有看到任何返回此类距离的方法 我错过了什么吗 您可能想使用 numpy 提供的矩阵运算来加速距

  • 如何选择 eps 和 minPts（DBSCAN 算法的两个参数）以获得有效的结果？

    我应该使用什么例程或算法来为 DBSCAN 算法提供 eps 和 minPts 参数以获得有效的结果 DBSCAN 论文建议根据维度选择 minPts 根据 k 距离图中的肘部选择 eps 在最近的出版物中 舒伯特 E 桑德 J 埃斯特 M

随机推荐

  • 美团笔试题（2018.10.09）

    逻辑题20个要快点做 xff0c 然后30个选择考的东西比较多 编程两个 优惠券 有一个满x减的优惠券 xff0c 一共n个商品 xff0c 每个只能选择一次 xff0c 求能使用优惠券的最小价格 就是求n个数选任意几个加起来最接近x且大于

  • AndroidStudio gradle 编译发现阿里云镜像找不到对应jar包https://maven.aliyun.com/nexus/content/repositories/jcenter

    FAILURE Build completed with 4 failures 1 Task failed with an exception What went wrong Execution failed for task 39 app

  • 用PyQt5写了个音乐播放器

    首先先展示一下界面 xff08 不美观但好用 xff09 除了不能看歌词功能该有的都有 xff0c 作为本地播放器还挺好用的 xff0c 界面是用PyQt5做的 下面是源代码 xff1a span class token keyword i

  • Consul+Ocelot搭建微服务实践--IdentityServer集成

    文章目录 1 IdentityServer介绍2 建立IdentityServer2 1 安装IdentityServer42 2 定义配置中心2 2 1 定义Client2 2 2 定义ApiResource2 2 3定义Identity

  • 配置Linux内核版本在线或离线升级（回退）

    在线升级 一 查看系统内核 xff08 当前系统内核为3 10 xff09 uname r 二 确定当前主机能连外网 ping www baidu com 三 导入在线elrepo仓库公钥 rpm import https www elre

  • 深度学习相关网址

    深度学习教学网址 Unsupervised Feature Learning and Deep Learning Tutorial GitHub rasmusbergpalm DeepLearnToolbox Matlab Octave t

  • CentOS Docker安装并使用httpd镜像运行容器

    Docker 是一个开源的应用容器引擎 xff0c 基于 Go 语言 并遵从 Apache2 0 协议开源 CentOS Docker 安装 先卸载旧版本 xff0c 较旧的 Docker 版本称为 docker 或 docker engi

  • 基于神经辐射场NeRF的SLAM方法

    随着2020年NeRF 1 的横空出世 xff0c 神经辐射场方法 xff08 Neural Radiance Fields xff09 如雨后春笋般铺天盖地卷来 NeRF最初用来进行图像渲染 xff0c 即给定相机视角 xff0c 渲染出

  • 有限视角重叠和不准确外参标定下的多相机SLAM的鲁棒初始化

    1 摘要 本文提出了一种当相机只有有限的公共视野和不准确的外参标定情形下的用于多相机视觉SLAM系统的鲁棒初始化方法 有限的共同视野导致只有一些特征可以在相机之间匹配上 离线标定后 xff0c 由于振动或相机错误放置而导致的不准确的外部位姿

  • Unifying Flow, Stereo and Depth Estimation论文阅读

    1 序言 上篇文章中我们提到了一种在线标定光学防抖主摄和ToF方法 其中使用RAFT作为光流估计网络来进行密集匹配 xff0c 本文我们来介绍一种更新的光流估计算法GMFlow xff0c 其被CVPR2022接收为Oral 同时也将介绍其

  • BARF: Bundle-Adjusting Neural Radiance Fields论文阅读

    摘要 神经辐射场 NeRF 可以合成真实世界场景的全新视角的照片 xff0c 其性能优异 xff0c 因此在计算机视觉领域引起较大的兴趣 NeRF的一个限制条件是需要准确相机位姿 本文提出了集束调整神经辐射场 BARF xff0c 可以用不

  • 自动驾驶高精定位

    定位是高等级自动驾驶的基础 xff0c 但在高速NOA和城区NOA等场景中 xff0c 如何能够稳定地在各种工况下实现高精度定位将是个难题 一个常见的问题是 xff1a 高速NOA 城区NOA功能需要实现多高精度的定位 xff1f 需要多高

  • 高精度组合导航里的松耦合、紧耦合、深耦合

    高精度定位 xff0c 是自动驾驶车辆一切丰满理想实现的前提 它用于判断自动驾驶功能是否处于可激活的设计运行条件内 xff1b 它用于支撑自动驾驶车辆的全局路径规划 xff1b 它用于辅助自动驾驶车辆的变道 避障策略 不同的场景特点 不同的

  • 超像素分割

    1 超像素 超像素是把一张图片中具有相似特征的像素进行聚类 xff0c 形成一个更具有代表性的大 像素 这个新的像素可以作为其他图像处理算法的基本单位 xff0c 可以减低图像的维度和异常像素点 目前常用的超像素分割算法有SLIC SEED

  • Numpy使用问题汇总

    1 批量操作 1 1 现象 import numpy as np vec 61 np zeros 10 int indices 61 np array 0 0 vec indices 43 61 1 print vec 上面代码的输出不是

  • K-means聚类算法

    K means 是我们最常用的基于欧式距离的聚类算法 xff0c 其认为两个目标的距离越近 xff0c 相似度越大 本文大致思路为 xff1a 先介绍经典的牧师 村名模型来引入 K means 算法 xff0c 然后介绍算法步骤和时间复杂度

  • 自组织映射(Self-organizing map, SOM)

    1 算法原理 自组织映射 Self organizing map SOM 通过学习输入空间中的数据 xff0c 生成一个低维 离散的映射 Map xff0c 从某种程度上也可看成一种降维算法 SOM是一种无监督的人工神经网络 不同于一般神经

  • 怎么将数据存入session

    怎么将数据存入session 默认数据都是存入request 需要自己设置存入session 1 方式1 原生session代码 64 RequestMapping 34 selectUser 34 public String select

  • Octree(八叉树)

    1 算法原理 八叉树 xff08 Octree xff09 是一种用于描述三维空间的树状数据结构 八叉树的每个节点表示一个正方体的体积元素 xff0c 每个节点有八个子节点 xff0c 将八个子节点所表示的体积元素加在一起就等于父节点的体积

  • DBSCAN聚类算法

    DBSCAN是一种非常著名的基于密度的聚类算法 其英文全称是 Density Based Spatial Clustering of Applications with Noise xff0c 意即 xff1a 一种基于密度 xff0c 对

热门标签