当前位置: 首页 > news >正文

DBSCAN聚类算法

目录

  • 背景
  • DBSCAN算法
  • DBSCAN算法原理
  • DBSCAN算法基本步骤
  • DBSCAN算法调优
  • DBSCAN算法优缺点
  • 参考文献

背景

如果有车队在某一片区域经常规律性作业,现在要让你来绘制这一片的路网,你会选择让一辆车从头到尾把所有路网跑一遍还是基于历史轨迹点通过技术手段构建出路网出来?

前者就像我们的智能穿戴设备记录你晨跑的轨迹,可能绘制出来的路网更加干净,但是、需要另行安排车辆跑路会影响工程进度,如果是自有车辆还好,如果是无车承运人,车子就不受控,在具体跑路的时候为了避免相同路段不重复记录还需要及时插拔车载设备;后者更多像文科生利用已有的素材来做事,更符合数学科学家的身份和做事风格,可能会用到DBScan算法,下面重点介绍一下DBSCAN算法。

DBSCAN算法

DBSCAN是Density-Based Spatial Clustering of Applications with Noise的简称,从名字来看其是专门用来处理空间数据的,并且能够处理噪声点,与k-means算法不同,DBSCAN算法可以处理任意形状分布的数据。DBSCAN算法依赖下面的基本概念

  • eps

样本点辐射半径(epsilon,一下简称eps),如果样本点的相互距离小于或等于指定的eps,那么它们在同一邻域。

  • MinPts

样本点辐射半径里包含其他样本点的最小数目(MinPts);

  • 核心点

以该点为圆心,如果给定半径eps内含有不少于MinPts数目的点,那么该点就是核心点。

  • 边界点

以该点为圆心,如果给定半径eps内含有不超过MinPts数目的点,并且落在核心点的eps半径内。

  • 噪声点

不是核心点也不是边界点的点。

  • 密度直达

如果P为核心点,Q在P的邻域内,那么称P到Q密度直达。反之不一定成立,即此时不能说Q到P密度直达,除非Q也是核心点,即密度直达不满足对称性。

  • 密度可达

如果存在核心点P1,P2,P3,…,Pn,并且P到P密度直达,P1到P2密度直达,…,Pn-1到Pn密度直达,Pn到Q密度直达,则P到Q密度可达。密度可达也不具备对称性。

  • 密度相连

如果存在核心点S,使得S到P和Q都密度可达,则P和Q密度相连。密度相连具有对称性,如果P和Q密度相连,那么Q和P也一定密度相连。

DBSCAN算法原理

DBSCAN聚类是将所有样本点分为核心点,边界点和噪声点三类,然后从核心点出发通过密度可达的方式按广度优先(BFS)去索引非噪声点,这定义了一个密度可达的关系,我们知道在数学里的线性空间定义一个关系就可以找一个划分,现在就可以把所有样本点进行划分了,有这种密度可达的关系划分为一簇,这样就聚好类了。

DBSCAN算法基本步骤

1,指定一个半径eps和最小样本点数MinPts,遍历所有数据点,确定其是核心点,边界点还是噪声点;
2,从核心点出发按照密度可达的关系(广度优先搜索(BFS))去搜索,标记所有半径范围内的样本点;
3,对所有核心点循环执行上述操作;

DBSCAN算法调优

  • 半径eps和最小样本点数MinPts

作为DBSCAN两个超参,可以结合业务来定,这里给出初始值的确定逻辑,比如在厂内其实不容许跑60km/h的,按这个速度计算一秒钟的路程d,以这个d作为超参半径eps,在计算边长为d的正方形与所有样本点分布的平面四至范围S对比按下面公式来估算超参MinPts,也就是按比例计算这么小方格平均会散落多少个样本点

d 2 : S = M i n P t s : N d^2: S = MinPts:N d2:S=MinPts:N

其中, d 2 d^2 d2为边长为d的正方形面积,S表示所有样本点分布的平面四至范围大小,N为所有样本点数。

确定了初始值之后,以轮廓系数silhouette_score为目标进行gridSearch。

  • 轮廓系数

轮廓系数silhouette_score它结合簇内聚集度和簇间的分离度两种因素。对于样本点i来说,

计算 a(i) = average(样本i到所有它属于的簇中其它点的距离)

计算 b(i) = min (样本i到某一不包含它的其他簇最小距离)

那么样本 i 轮廓系数就为:

S ( i ) = b ( i ) − a ( i ) m a x { b ( i ) , a ( i ) } S(i) = \frac{b(i) - a(i)}{max\{b(i) , a(i)\}} S(i)=max{b(i),a(i)}b(i)a(i)

可见轮廓系数的值是介于 [-1,1] ,越趋近于1代表内聚度和分离度都相对较优。将所有点的轮廓系数求平均,就是该聚类结果总的轮廓系数。

DBSCAN算法优缺点

  • 优点

(1)聚类速度快且能够有效处理噪声点和发现任意形状的空间聚类;

(2)与K-means比较起来,不需要输入要划分的聚类个数,且不要求样本凸分布;

  • 缺点

(1)当数据量增大时,要求较大的内存支持I/O消耗也很大;

(2)当空间聚类的密度不均匀、聚类间距差相差很大时,聚类质量较差

(3)算法聚类效果依赖与距离公式选取,实际应用中常用欧式距离,对于高维数据,存在“维数灾难”。

参考文献

1,DBSCAN的sklearn官网
https://scikit-learn.org/stable/modules/clustering.html#dbscan

2,认识DBSCAN
https://www.cnblogs.com/sbb-first-blog/p/16514003.html

3,基于DBACAN的道路轨迹点聚类
https://blog.csdn.net/zengbowengood/article/details/131180609

4,DBSCAN聚类算法原理总结
https://mp.weixin.qq.com/s?__biz=MzU1MjY4MTA1MQ==&mid=2247615480&idx=4&sn=a7789b16571c3fbab240b5c1fa5898cf&chksm=fbfd28cccc8aa1da4d4064be011563c5f82f885083b9fbecd97144c245e06ac1b1b495764ef5&scene=27

相关文章:

DBSCAN聚类算法

目录 背景DBSCAN算法DBSCAN算法原理DBSCAN算法基本步骤DBSCAN算法调优DBSCAN算法优缺点参考文献 背景 如果有车队在某一片区域经常规律性作业,现在要让你来绘制这一片的路网,你会选择让一辆车从头到尾把所有路网跑一遍还是基于历史轨迹点通过技术手段构…...

【tauri】安装

https://blog.csdn.net/freewebsys/article/details/136092092 1 安装nodejs curl -sL https://deb.nodesource.com/setup_18.x -o nodesource_setup.sh sudo bash nodesource_setup.sh sudo apt install nodejs # 查看版本 node -v2 安装webkit2 sudo apt update sudo apt i…...

(Java)心得:LeetCode——19.删除链表的倒数第 N 个节点

一、原题 给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 示例 1: 输入:head [1,2,3,4,5], n 2 输出:[1,2,3,5]示例 2: 输入:head [1], n 1 输出:[]示例 3&…...

树莓派安装opencv

安装opencv 上述步骤完成后,输入以下代码(基于python3) sudo apt-get install python3-opencv -y不行的话,试试换源,然后 sudo apt-get update成功! 测试opencv是否安装成功 输入 python3 然后再输入 import cv2 没有报错就…...

bert 的MLM框架任务-梯度累积

参考:BEHRT/task/MLM.ipynb at ca0163faf5ec09e5b31b064b20085f6608c2b6d1 deepmedicine/BEHRT GitHub class BertConfig(Bert.modeling.BertConfig):def __init__(self, config):super(BertConfig, self).__init__(vocab_size_or_config_json_fileconfig.get(vo…...

Nginx配置/.well-known/pki-validation/

当你需要在Nginx上配置.well-known/pki-validation/时,这通常是为了支持SSL证书的自动续订或其他验证目的。以下是配置步骤: 创建目录结构: 在你的网站根目录下创建一个名为.well-known的目录(SSL证书申请之如何创建/.well-known/…...

iOS LQG开发框架(持续更新)

基本规则 开发便利性为前提,妥协性能可维护性为前提可读性MVC各部分职责一定要清晰,controll类里面功能尽量抽离成helper,功能一定要清晰,这个非常重要,对代码可读性提升非常高方法内部尽量使用局部变量,最…...

Python 自动化脚本系列:第3集

21. 使用 cryptography 自动化文件加密 Python 的 cryptography 库提供了一种安全的方式,使用对称加密算法对文件进行加密和解密。你可以自动化加密和解密文件的过程来保护敏感数据。 示例:文件加密和解密 假设你想使用对称加密算法加密一个文件&…...

Matlab-粒子群优化算法实现

文章目录 一、粒子群优化算法二、相关概念和流程图三、例题实现结果 一、粒子群优化算法 粒子群优化算法起源于鸟类觅食的经验,也就是一群鸟在一个大空间内随机寻找食物,目标是找到食物最多的地方。以下是几个条件: (1) 所有的鸟都会共享自己的位置以及…...

python 新特性

文章目录 formatted字符串字面值formatted字符串支持 字符串新方法变量类型标注二进制表示中数字为1的数量统计字典的三个方法新增mapping属性函数zip()新增strict参数dataclass字典合并match 语法 formatted字符串字面值 formatted字符串是带有’f’字符前缀的字符串&#xf…...

十一、Redis持久化-RDB、AOF

Redis提供了两种持久化数据的方式。一种是RDB快照,另一种是AOF日志。RDB快照是一次全量备份,AOF日志是连续的增量备份。RDB快照是以二进制的方式存放Redis中的数据,在存储上比较紧凑;AOF日志记录的是对内存数据修改的指令文本记录…...

Oracle闪回数据库【Oracle闪回技术】(二)

理解Oracle闪回级别【Oracle闪回技术】(一)-CSDN博客 Oracle默认是不开启闪回数据库的。如果开启闪回数据库的前提条件是,开启Oracle归档模式并启用闪回恢复区。 因为闪回日志文件存放在闪回恢复区中,如果在RAC环境下,必须将闪回恢复区存储在集群文件或者ASM文件中。 一…...

简单负载均衡

题目描述 某工程师为了解决服务器负载过高的问题,决定使用多个服务器来分担请求消息。 现给定 k 台服务器(编号从 1 到 k),以及一批请求消息的信息,格式为到达时刻 负载大小,消息说明: 每个时刻…...

Portforge:一款功能强大的轻量级端口混淆工具

关于Portforge Portforge是一款功能强大的轻量级端口混淆工具,该工具使用Crystal语言开发,可以帮助广大研究人员防止网络映射,这样一来,他人就无法查看到你设备正在运行(或没有运行)的服务和程序了。简而言…...

1.8. 离散时间鞅-无界停时定理与随机游走

无界停时定理与随机游走 无界停时定理与随机游走1. 无界停时定理1.1. 一致可积1.2. 非一致可积2. 应用于随机游动-鞅方法2.1. 随机游走构造的鞅2.2. 对称简单随机游走无界停时定理与随机游走 1. 无界停时定理 本节给出一致可积下鞅的无界停时定理,说明一致可积下鞅的停止过程…...

Google Pixel4手机刷机+Root+逆向环境详细教程

Google Pixel4手机刷机Root逆向环境配置详细教程 刷机工具下载 Windows10、Google Pixel4手机当前安卓10系统、adb工具、要刷的谷歌原生的Android11最新刷机包、安装google usb驱动、美版临时twrp-3.6.0_11-0-flame.img和美版永久twrp-installer-3.6.0_11-0-flame.zip、Magis…...

IT项目管理-小题计算【太原理工大学】

1.合同总价问题 问承包商的利润是? 实际利润目标利润(目标成本-实际成本)*卖方分担比例 解:10 000(100 000 - 90 000)* 0.2 12 000(元) 实际成本有时也写作最终成本,问承…...

ARP欺骗使局域网内设备断网

一、实验准备 kali系统:可使用虚拟机软件模拟 kali虚拟机镜像链接:https://www.kali.org/get-kali/#kali-virtual-machines 注意虚拟机网络适配器采用桥接模式 局域网内存在指定断网的设备 二、实验步骤 打开kali系统命令行:ctrlaltt可快…...

Android动画(四):PathMeasure实现路径动画

文章概览 1 PathMeasure概述2 实现路径加载动画3 实现箭头加载动画4 实现操作成功动画 本系列将介绍以下内容: Android动画 1 PathMeasure概述 PathMeasure是一个单独的类,其全部源码如下(请详细研读注释): package…...

HTTP 连接详解

概述 世界上几乎所有的 HTTP 通信都是由 TCP/IP 承载的,客户端可以打开一条TCP/IP连接,连接到任何地方的服务器。一旦连接建立,客户端和服务器之间交换的报文就永远不会丢失、受损或失序 TCP(Transmission Control Protocol&…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...

站群服务器的应用场景都有哪些?

站群服务器主要是为了多个网站的托管和管理所设计的,可以通过集中管理和高效资源的分配,来支持多个独立的网站同时运行,让每一个网站都可以分配到独立的IP地址,避免出现IP关联的风险,用户还可以通过控制面板进行管理功…...

API网关Kong的鉴权与限流:高并发场景下的核心实践

🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中,API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关,Kong凭借其插件化架构…...