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

DBSCAN聚类

一、概述

  DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一种基于密度的聚类算法,簇集的划定完全由样本的聚集程度决定。聚集程度不足以构成簇落的那些样本视为噪声点,因此DBSCAN聚类的方式也可以用于异常点的检测。

二、算法原理

1.基本原理

  算法的关键在于样本的‘聚集程度’,这个程度的刻画可以由聚集半径和最小聚集数两个参数来描述。如果一个样本聚集半径领域内的样本数达到了最小聚集数,那么它所在区域就是密集的,就可以围绕该样本生成簇落,这样的样本被称为核心点。如果一个样本在某个核心点的聚集半径领域内,但其本身又不是核心点,则被称为边界点;既不是核心点也不是边界点的样本即为噪声点。其中,最小聚集数通常由经验指定,一般是数据维数+1或者数据维数的2倍。

  通俗地讲,核心点就是构成一个簇落的核心成员;边界点就是构成一个簇落的非核心成员,它们分布于簇落的边界区域;噪声点是无法归属在任何一个簇集的游离的异常样本。如图所示。
在这里插入图片描述
  对于聚成的簇集,这里有三个相关的概念:密度直达,密度可达,密度相连。

密度直达: 对一个核心点p,它的聚集半径领域内的有点q,那么称p到q密度直达。密度直达不具有对称性。

密度可达: 有核心点p1,p2,…,pn,非核心点q,如果pi到pi+1(i=1,2,…,n-1)是密度直达的,pn到q是密度直达的,那么称核心点pi(i=1,2,…,n)到其他的点是密度可达的。密度可达不具有对称性。

密度相连: 如果有核心点P,到两个点A和B都密度可达,那么称A和B密度相连。密度相连具有对称性。

  简单地讲,核心点到其半径邻域内的点是密度直达的;核心点到其同簇集内的点是密度可达的;同一个簇集里的成员间是密度相连的。

在这里插入图片描述
  由定义易知,密度直达一定密度可达,密度可达一定密度相连。密度相连就是对聚成的一个簇集最直接的描述。

2.算法描述

输入: 样本集D,聚集半径r,最小聚集数MinPts;
输出: 簇集C1,C2,…,Cn,噪声集O.
根据样本聚集程度,传播式地划定聚类簇,并将不属于任何一个簇的样本划入噪声集合。

(1)随机搜寻一个核心点p,

S1.从样本集D中随机选择一个未归入任何集合的且未被标记的样本对象p
S2.计算p的r邻域大小 ∣ N r ( p ) ∣ \left| N_r(p) \right| Nr(p)
∣ N r ( p ) ∣ ≥ M i n P t s \left| N_r(p) \right|\geq MinPts Nr(p)MinPts ,则标记为核心点;否则,标记为非核心点,并选择其他的点进行判别.
S3.重复上面的步骤,直至找到一个核心点;若未找到,将未归集的样本划入噪声集O.

(2)在核心点p处建立簇C,将r邻域内所有的点加入簇C.

(3)对邻域内所有未被标记的点迭代式进行考察,扩展簇集.

若一个邻域点q为核心点,则将它领域内未归入集合的点加入簇C中.

(4)重复以上步骤,直至所有样本划入了指定集合;

(5)输出簇集C1,C2,…,Cn和噪声集合O。

3.优缺点

优势:
  1.可以发现任意形状的簇,适用于非凸数据集;
  2.可以进行异常检测;
  3.不需要指定簇数,根据样本的密集程度适应性地聚集。

不足:
  1.当样本集密度不均匀,不同簇中的平均密度相差较大时,效果较差;
  2.聚集半径和最小聚集数两个参数需人工指定。

三、示例

  假设二维空间中有下列样本,坐标为

(1,2),(1,3),(3,1),(2,2),(9,8),(8,9),(9,9),(18,18)

  由DBSCAN算法完成聚类操作。

过程演算:
  由经验指定参数聚集半径r=2,最小聚集数MinPts=3。

(1)随机搜寻一个核心点,若不存在,返回噪声集合。
  考察点(1,2),它到各点的距离分别为
在这里插入图片描述
  在它的r邻域内,包括了自身在内的共三个样本点,达到了MinPts数,因此(1,2)为核心点。

(2)在核心点(1,2)处建立簇C1,原始簇成员为r邻域内样本:(1,2)、(1,3)、(2,2)。

(3)对簇落C1成员迭代式进行考察,扩展簇集。
  先考察(1,3),它到各点的距离分别为
在这里插入图片描述
  在它的r邻域内,包括了自身在内的共三个样本点,达到了MinPts数,因此(1,3)为核心点,它邻域内的样本均已在簇C1中,无需进行操作。
  再考察(2,2),它到各点的距离分别为
在这里插入图片描述
  在它的r邻域内,包括了自身在内的共四个样本点,达到了MinPts数,因此(2,2)为核心点,将它领域内尚未归入任何一个簇落的点(3,1)加入簇C1。

  再考察(3,1),它到各点的距离分别为
在这里插入图片描述
  在它的r邻域内,包括了自身在内的共两个样本点,因此(3,1)是非核心点。

  考察结束,簇集C1扩展完毕。

(4)在其余未归簇的样本点中搜寻一个核心点,若不存在,返回噪声集合。
  考察点(9,8),它到各点的距离分别为
在这里插入图片描述
  在它的r邻域内,包括了自身在内的共三个样本点,达到了MinPts数,因此(9,8)为核心点。

(5)在核心点(9,8)处建立簇C2,原始簇成员为r邻域内样本:(9,8)、(8,9)、(9,9)。

(6)对簇落C2成员迭代式进行考察,扩展簇集。
  先考察(8,9),它到各点的距离分别为
在这里插入图片描述
  在它的r邻域内,包括了自身在内的共三个样本点,达到了MinPts数,因此(8,9)为核心点,它邻域内的样本均已在簇C2中,无需进行操作。
再考察(9,9),它到各点的距离分别为
在这里插入图片描述
  在它的r邻域内,包括了自身在内的共三个样本点,达到了MinPts数,因此(9,9)为核心点。它邻域内的样本均已在簇C2中,无需进行操作。
考察结束,簇集C2扩展完毕。

(7)在其余未归簇的样本点中搜寻一个核心点,若不存在,返回噪声集合。
  其余未归簇的样本点集合为{(18,18)},考察(18,18),它到各点的距离分别为
在这里插入图片描述
  在它的r邻域内,包括了自身在内的共一个样本点,未达到MinPts数,因此(18,18)为非核心点。其余未归簇的样本中不存在核心点,因此归入噪声集O={(18,18)}。

(8)输出聚类结果
  簇类C1:{(1,2),(1,3),(3,1),(2,2)}
  簇类C2:{(9,8),(8,9),(9,9)}
  噪声集O:{(18,18)}

四、Python实现

示例的Python实现。

'''
功能:用python实现DBSCAN聚类算法。
'''
from sklearn.cluster import DBSCAN
import numpy as np
import matplotlib.pyplot as plt# 初始化数据
data = np.array([(1,2),(1,3),(3,1),(2,2),(9,8),(8,9),(9,9),(18,18)])# 定义DBSCAN模型
dbscan = DBSCAN(eps=2,min_samples=3)# 计算数据,获取标签
labels = dbscan.fit_predict(data)# 定义颜色列表
colors = ['b','r','c']
T = [colors[i] for i in labels]# 输出簇类
print('\n 聚类结果: \n')
ue = np.unique(labels)
for i in range(ue.size):CLS = []for k in range(labels.size):if labels[k] == ue[i]:CLS.append(tuple(data[k]))print('簇类{}:'.format(ue[i]),CLS)# 结果可视化
plt.figure()
plt.scatter(data[:,0],data[:,1],c=T,alpha=0.5)  # 绘制数据点
plt.show()

运行结果:
在这里插入图片描述
在这里插入图片描述


End.


资源打包下载:
https://download.csdn.net/download/Albert201605/88152784?spm=1001.2014.3001.5503

相关文章:

DBSCAN聚类

一、概述 DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一种基于密度的聚类算法,簇集的划定完全由样本的聚集程度决定。聚集程度不足以构成簇落的那些样本视为噪声点,因此DBSCAN聚类的方式也可以用于异常点的检测。 二、算法…...

java+ssm美食推荐交流系统 7jsw7

随着社会的发展,美食推荐系统的管理形势越来越严峻。越来越多的用户利用互联网获得信息,但美食推荐信息鱼龙混杂,真假难以辨别。为了方便用户更好的获得美食推荐信息,因此,设计一款安全高效的美食推荐系统极为重要。 为…...

基于php雪花算法工具类Snowflake -来自chatGPT

<?phpclass Snowflake {// 定义Snowflake算法的各个参数private $workerIdBits 5;private $datacenterIdBits 5;private $sequenceBits 12;private $workerIdShift;private $datacenterIdShift;private $timestampLeftShift;private $maxWorkerId;private $maxDatacente…...

怎么加密文件夹才更安全?安全文件夹加密软件推荐

文件夹加密可以让其中数据更加安全&#xff0c;但并非所有加密方式都能够提高极高的安全强度。那么&#xff0c;怎么加密文件夹才更安全呢&#xff1f;下面我们就来了解一下那些安全的文件夹加密软件。 文件夹加密超级大师 如果要评选最安全的文件夹加密软件&#xff0c;那么文…...

知识分享和Tomcat简单部署press应用

一、简述静态网页和动态网页的区别。 静态网页: 静态网页是指运行于客户端的程序、网页、组件、纯粹HTML格式的网页; 如果有涉及网页内容的修改&#xff0c;就要修改源文件&#xff0c;重新上传到服务器。而且当网站信息量很大的时候&#xff0c;网页制作和维护都非常困…...

回归预测 | MATLAB实现SO-CNN-BiGRU蛇群算法优化卷积双向门控循环单元多输入单输出回归预测

回归预测 | MATLAB实现SO-CNN-BiGRU蛇群算法优化卷积双向门控循环单元多输入单输出回归预测 目录 回归预测 | MATLAB实现SO-CNN-BiGRU蛇群算法优化卷积双向门控循环单元多输入单输出回归预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 MATLAB实现SO-CNN-BiGRU蛇群算法…...

步入React前厅 - 组件和JSX

目录 扩展学习资料 购物车应用 编写React元素 /src/index.js 创建组件 /src/components/listItem.jsx /src/App.js 理解JSX【JavaScriptXML】 JSX是什么 JSX规则 /src/components/listItem.jsx 使用Fragments /src/App.js 为何要使用Fragments 表格中使用Fragme…...

SpringBoot整合Sfl4j+logback的实践

一、概述 对于一个web项目来说&#xff0c;日志框架是必不可少的&#xff0c;日志的记录可以帮助我们在开发以及维护过程中快速的定位错误。slf4j,log4j,logback,JDK Logging等这些日志框架都是我们常见的日志框架&#xff0c;本文主要介绍这些常见的日志框架关系和SpringBoot…...

IT 基础架构自动化

什么是 IT 基础架构自动化 IT 基础架构自动化是通过使用技术来控制和管理构成 IT 基础架构的软件、硬件、存储和其他网络组件来减少人为干预的过程&#xff0c;目标是构建高效、可靠的 IT 环境。 为什么要自动化 IT 基础架构 为客户和员工提供无缝的数字体验已成为企业的当务…...

Docker入门——保姆级

Docker概述 ​ —— Notes from WAX through KuangShen 准确来说&#xff0c;这是一篇学习笔记&#xff01;&#xff01;&#xff01; Docker为什么出现 一款产品&#xff1a;开发—上线 两套环境&#xff01;应用环境如何铜鼓&#xff1f; 开发 – 运维。避免“在我的电脑…...

MONGODB ---- Austindatabases 历年文章合集

开头还是介绍一下群&#xff0c;如果感兴趣polardb ,mongodb ,mysql ,postgresql ,redis 等有问题&#xff0c;有需求都可以加群群内有各大数据库行业大咖&#xff0c;CTO&#xff0c;可以解决你的问题。加群请联系 liuaustin3 &#xff0c;在新加的朋友会分到2群&#xff08;共…...

菠萝头 pinia和vuex对比 pinia比vuex更香 Pinia数据持久化及数据加密

前言 毕竟尤大佬都推荐使用pinia&#xff0c;支持vue2和vue3&#xff01; 如果熟悉vuex&#xff0c;花个把小时把pinia看一下&#xff0c;就不想用vuex了 支持选项式api和组合式api写法pinia没有mutations&#xff0c;只有&#xff1a;state、getters、actionspinia分模块不…...

机器学习笔记 - 关于GPT-4的一些问题清单

一、简述 据报道,GPT-4 的系统由八个模型组成,每个模型都有 2200 亿个参数。GPT-4 的参数总数估计约为 1.76 万亿个。 近年来,得益于 GPT-4 等高级语言模型的发展,自然语言处理(NLP) 取得了长足的进步。凭借其前所未有的规模和能力,GPT-4为语言 AI​​设立了新标准,并为机…...

sql 参数自动替换

需求&#xff1a;看日志时&#xff0c;有的sql 非常的长&#xff0c;参数比较多&#xff0c;无法直接在sql 客户端工具执行&#xff0c;如果一个一个的把问号占位符替换为参数太麻烦&#xff0c;因此写个html 小工具&#xff0c;批量替换&#xff1a; 代码&#xff1a; <!…...

Linux——设备树

目录 一、Linux 设备树的由来 二、Linux设备树的目的 1.平台识别 2.实时配置 3.设备植入 三、Linux 设备树的使用 1.基本数据格式 2.设备树实例解析 四、使用设备树的LED 驱动 五、习题 一、Linux 设备树的由来 在 Linux 内核源码的ARM 体系结构引入设备树之前&#x…...

网络:从socket编程的角度说明UDP和TCP的关系,http和tcp的区别

尝试从编程的角度解释各种网络协议。 UDP和TCP的关系 从Python的socket编程角度出发&#xff0c;UDP&#xff08;User Datagram Protocol&#xff09;和TCP&#xff08;Transmission Control Protocol&#xff09;是两种不同的传输协议。 TCP是一种面向连接的协议&#xff0c…...

大数据技术之Hadoop:HDFS集群安装篇(三)

目录 分布式文件系统HDFS安装篇 一、为什么海量数据需要分布式存储 二、 分布式的基础架构分析 三、 HDFS的基础架构 四 HDFS集群环境部署 4.1 下载安装包 4.2 集群规划 4.3 上传解压 4.4 配置HDFS集群 4.5 准备数据目录 4.6 分发hadoop到其他服务器 4.7 配置环境变…...

移动开发最佳实践:为 Android 和 iOS 构建成功应用的策略

您可以将本文作为指南&#xff0c;确保您的应用程序符合可行的最重要标准。请注意&#xff0c;这份清单远非详尽无遗&#xff1b;您可以加以利用&#xff0c;并添加一些自己的见解。 了解您的目标受众 要制作一个成功的应用程序&#xff0c;你需要了解你是为谁制作的。从创建…...

2023年第二届网络安全国际会议(CSW 2023)

会议简介 Brief Introduction 2023年第二届网络安全国际会议(CSW 2023) 会议时间&#xff1a;2023年10月13日-15日 召开地点&#xff1a;中国杭州 大会官网&#xff1a;www.cybersecurityworkshop.org 2023年第二届网络安全国际会议(CSW 2023)由杭州电子科技大学&#xff0c;国…...

【100天精通python】Day23:正则表达式,基本语法与re模块详解示例

目录 专栏导读 1 正则表达式概述 2 正则表达式语法 2.1 正则表达式语法元素 2.2 正则表达式的分组操作 3 re 模块详解与示例 4 正则表达式修饰符 专栏导读 专栏订阅地址&#xff1a;https://blog.csdn.net/qq_35831906/category_12375510.html 1 正则表达式概述 python 的…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...