概念

「DBSCAN」（Density-Based Spatial Clustering of Applications with Noise，基于高密度连接区域的密度聚类方法）是一种著名的密度聚类算法。它基于一组「邻域函数」（）来刻画样本分布的紧密程度

与划分和层次聚类方法不同，DBSCAN 将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在有噪声的空间数据库中发现任意形状的聚类

邻域

对 ，其 -邻域包含样本集 中与 距离不大于 的样本构成「邻域」，即

核心对象

若 的 -邻域至少包含 个样本，即 ，则称 为「核心对象」（Core object）

直接密度可达

给定一个对象集合 ，如果 是在 的 邻域内，而 是一个核心对象，则对象 从对象 出发是「直接密度可达」的（Directly Density-Reachable）或「密度直达」

密度可达

若 与 ，存在样本序列 ，其中 ，且 由 密度直达，则称 由 密度可达。注意，这意味着路径上除了 之外的所有点必须是核心对象

密度相连

对 与 ，若存在 使得 与 均由 密度可达，则称 与 密度相连。

img-2024-05-02 18-24-26.png

如图，，虚线表示 -邻域，若以 为核心对象，则 由 密度直达， 由 密度可达， 与 密度相连

由密度可达关系到出的最大相连样本集合被定义为「簇」。给定邻域参数 ，簇 是满足一下性质的非空样本子集

  • 连接性（Connectivity）： 与 密度相连
  • 最大性（Maximality）： 由 密度可达
    若以 为核心对象，则 密度可达的所有样本的集合记为 由密度可达 ，则不难证明 即为满足连接性与最大性的簇。

算法

先任选数据集中的一个核心对象为「种子」，再由此出发确定相应的聚类簇。

以任一核心对象为出发点，找出由其密度可达的样本生成聚类簇，然后更新核心对象集合（在集合中去除生成的聚类簇中包含的核心对象），重复上述操作，直到所有核心对象均被访问过为止。

输入：样本集 ，邻域参数

输出：簇划分

过程：

  • 初始化核心对象集合
    • 确定样本 的 -邻域
      • 将样本 加入核心样本集合
    • end if
  • end for
  • 初始化聚类簇数
  • 初始化为访问样本集合
  • while do
    • 取出队列 Q 中首个样本
    • if then
      • 令
      • 将 中的样本加入队列
    • end if
    • ，生成聚类簇
  • end while

DBSCAN 将数据对象分为三类

  • 核心对象（Core Object）： 邻域内邻居数量大于
  • 边缘对象（Border Object）：非核心对象，但位于某个核心对象邻域内
  • 离群对象（Outlier）：亦称为噪声对象，非核心对象，亦非边缘对象

特点

优点：

  • 可以发现任意形状的聚类簇
  • 自动发现簇的数量
  • 有效处理数据集中的噪声数据
  • 对数据输入顺序不敏感

缺点：

  • 对输入参数 敏感，若选取不当，将造成聚类质量下降
  • 输入参数 是全局唯一的，当数据本身的密度不均匀，聚类间距离相差很大时，聚类质量较差
  • 只能发现密度相仿的簇
  • 计算复杂度 ，但可采用 R-树等空间索引技术来降低计算复杂度

例子

例 1

假设现在有 7 个点 ，令

解：

首先找出所有核心对象，为

已知 ，以 为出发点，其密度可达样本有 ，，因此第一个聚类为

此时剩下的核心对象为 以及剩下的样本点 。现在再次选取出发点进行聚类。比如选取 ，则其密度可达样本有 ，，因此第二个聚类为

此时 ，循环结束，剩下的 不属于任何聚类，被判定为离群点。

例 2

下面以西瓜数据集为例演示 DBSCAN 的过程，设置 。

  • DBSCAN 首先确定核心对象集合

然后随机选择一个核心对象作为种子。假设选择核心对象 为种子，则 DBSCAN 生成的第一个聚类簇为

然后 DBSCAN 将 中包含的核心对象从 去除

再从更新后的集合 中随机选择一个核心对象作为种子来生成下一个聚类簇，重复上述过程，直到 为空

Interactive Graph
Table Of Contents
概念

邻域

核心对象
直接密度可达
密度可达
密度相连
算法
特点
例子
例 1
例 2