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

【机器学习】25. 聚类-DBSCAN(density base)

聚类-DBSCAN-density base

  • 1. 介绍
  • 2. 实现
    • 案例计算
  • 3. K-dist
  • 4. 变化密度
  • 5. 优缺点

1. 介绍

DBSCAN – Density-Based Spatial Clustering of Applications with Noise
与K-Means查找圆形簇相比,DBSCAN可以查找任意形状和复杂形状的簇,如S形、椭圆、半圆
适合处理带有噪声的复杂数据集. DBSCAN将高密度区域识别为一个簇, 并把低密度区域视为簇和簇之间的分割. 噪声点通常位于低密度区域, 被排除在簇之外.
在这里插入图片描述
不同于K-means只能找圆形的簇, DBSCAN能找任意复杂形状的簇, 如S形, 半圆形…

2. 实现

在给定的数据集中,根据每个数据点周围其他数据点的密度情况,将数据点分为核心点、边界点和噪声点。

  • 核心点 core point 是周围某个半径内有足够多其他数据点的数据点;
  • 边界点 border point 是不满足核心点要求,但在某个核心点的半径内的数据点;
  • 噪声点 noise point 则是不满足任何条件的点。

接着,从核心点开始,通过密度相连的数据点不断扩张,形成一个簇。
在这里插入图片描述
一个点的密度取决于半径Eps. 如果:
Eps太大: 所有的点都会有一个较大的密度m,m是数据集中所有的点的数量
Eps太小: 所有的点的密度都等于1, 即只有一个自身

具体实现步骤为

  1. 将数据点标注为核心点, 边界点, 噪声点
  2. 抛弃噪声点
  3. 将剩余的点根据如下方式聚类:
  • 任何两个核心点, 若各自在对方的Eps内, 则属于同一个簇
  • 任何的边界点都放在与其相关联的核心点所属的簇中. 若边界点同时和多个核心点相关联, 需要解决冲突

案例计算

在这里插入图片描述
Eps = 1
MinPts = 2

  1. 找每个点eps范围内的点
    A : AB
    B: AB
    C: C
    D: DE
    E: ED

2.根据MinPts找到core point, border point 和noise point
Core point: A,B,D,E
border point: 0
noise point: C
3. 找到类 AB,DE

3. K-dist

不同的Eps和MinPts可能会对结果产生很大影响.
可以使用k-距离, k-dist来选取适当的Eps和MinPts.
计算每个点到第k个最近邻居的距离,属于某个cluster的点,k-dist会比较小,对与不属于任何cluster的点,如噪声点,则k-dist比较大。在这个图中,拐点是比较合适的。
在这里插入图片描述
在 k-距离图(k-distance graph)中,X 轴和 Y 轴表示以下内容:

X 轴(点的索引):数据集中所有点按与其第 k 个最近邻的距离值从小到大排序后的索引。这些点可以按顺序编号,例如从 1 到数据集中点的总数。
Y 轴(k-距离):每个点与其第 k 个最近邻的距离,通常记为 k-距离值。这个值表示该点到数据集中第 k 近邻点的距离。Y 轴的值越大,表示点的密度越低,反之则表示密度较高。

4. 变化密度

DBSCAN无法很好处理密度不同的cluster

5. 优缺点

优点:

  • 可以形成任意形状和大小的簇
  • 不需要实现指定簇的数量
  • 对噪声具有鲁棒性

缺点:

  • 不适合密度差异较大的数据
  • 不适合高维数据
  • 对输入参数Eps和MinPts敏感
    -Eps和MinPts选择通常不是直观的, 需要通过一些启发方法

时间复杂度n^2
空间复杂度n


http://www.kler.cn/a/381166.html

相关文章:

  • Linux下编译安装Kokkos
  • Naive UI 多选框自定义tag和label
  • 【JetPack】Navigation知识点总结
  • GPU环境配置
  • 人工智能:人机交互和用户体验:相关学点、两者关系、未来趋势
  • 【专题】2024年悦己生活消费洞察报告汇总PDF洞察(附原数据表)
  • 云计算Openstack 虚拟机调度策略
  • Docker-- cgroups资源控制实战
  • 【C++刷题】力扣-#705-设计哈希集合
  • 「Mac畅玩鸿蒙与硬件27」UI互动应用篇4 - 猫与灯的互动应用
  • Flink-Kafka-Connector
  • 第五次作业
  • L1G3000 提示工程(Prompt Engineering)
  • 【Spring】Spring的简单创建和使用
  • 11.5日志
  • labview学习总结
  • Linux终端退出程序后,TCP地址仍被占用
  • 【前端】Fetch:数据请求
  • C++之数组和字符串
  • ffplay 实现视频流中音频的延迟
  • 手机ip地址怎么切换外省
  • 【大模型】海外生成式AI赛道的关键玩家:OpenAI、Anthropic之外还有谁?
  • 二、 问题发现(监控工具和方法)
  • 【Unity】Unity拖拽在Android设备有延迟和卡顿问题的解决
  • Qt 视口和窗口
  • 使用RestTemplate发送post请求,入参是多层嵌套的JSON