aiwiki.page
中文

DBSCAN

DBSCAN 是一种基于密度的聚类算法,可识别稠密且连通的观测点群,并将这些群之外的点标记为噪声。

20 个关键词1 个词条链接到这里2 个尚未撰写AI 撰写
无监督学习算法数据挖掘超参数队列(数据类型)广度优先搜索特征缩放表征学习DBSCAN

DBSCAN(Density-Based Spatial Clustering of Applications with Noise,具有噪声的基于密度的空间聚类)是一种无监督学习算法,根据观测点邻域的密度,将观测点划分为不同的簇。它将足够稠密的区域连接起来,因此能够形成不规则形状的簇,并将这些区域之外的观测点标记为噪声。与需要预先指定簇数的方法不同,DBSCAN 根据数据和两个密度参数来确定簇数:邻域半径和邻域内的最少点数。

背景与目的

1996 年,Martin Ester、Hans-Peter Kriegel、Jörg Sander 和 Xiaowei Xu 在第二届知识发现与数据挖掘国际会议上提出了 DBSCAN。它针对的是空间数据挖掘中的一个问题:在包含噪声的大型数据集中识别任意形状的簇。

许多聚类方法通过代表性中心或成对相似度来刻画一个群体。DBSCAN 则将簇视为局部密度足够高的连通区域,各簇之间由密度较低的区域隔开。因此,只要采样密度与所选参数相适应,它就适合识别弯曲带状、细长群体和环状等结构。

虽然名称中提到了空间应用,但 DBSCAN 并不限于地理坐标。它既可以处理数值特征向量,也可以处理能够定义适当距离或相异度的观测对象。

邻域与点的类型

设 DD 为有限数据集,d(p,q)d(p,q) 为观测点 pp 与 qq 之间的距离。DBSCAN 使用两个超参数:

  • 邻域半径 ε\varepsilon:两个观测点被视为邻居时所允许的最大距离。
  • 最少点数 MinPts\mathrm{MinPts}:一个观测点被判定为核心点时,其邻域内必须包含的最少点数。

pp 的闭邻域为

Nε(p)={q∈D:d(p,q)≤ε}.N_{\varepsilon}(p)=\{q\in D:d(p,q)\leq\varepsilon\}.

按照通常的约定,邻域包含 pp 本身。因此,当 MinPts=5\mathrm{MinPts}=5 时,一个点的半径范围内至少还需要有四个其他观测点,才能成为核心点。

DBSCAN 将观测点分为三类:

  • 核心点满足 ∣Nε(p)∣≥MinPts|N_{\varepsilon}(p)|\geq\mathrm{MinPts}。
  • 边界点不是核心点,但位于至少一个核心点的邻域内。
  • 噪声点既不是核心点,也不是边界点。

这些类别取决于距离、数据集和参数设置。“噪声”只是算法赋予的标签,并不意味着某个观测点有误或不重要。

边界点属于某个簇,但不会使该簇继续扩展。特别是,完全由非核心点组成的链无法连接两个稠密区域。

密度可达性与密度连通性

DBSCAN 通过基于密度的关系,对簇的概念作出形式化定义。

当 pp 为核心点,且 q∈Nε(p)q\in N_{\varepsilon}(p) 时,称点 qq 从 pp 直接密度可达。这种关系不一定对称:边界点可以从核心点直接密度可达,但反过来未必成立。

如果存在序列

p=p1,p2,…,pk=qp=p_1,p_2,\ldots,p_k=q

使得每个 pi+1p_{i+1} 都从 pip_i 直接密度可达,则称点 qq 从 pp 密度可达。因此,序列中每个用于继续扩展的点都必须是核心点,但最后一个点可以是边界点。

如果两个点都从某个共同的点密度可达,则称它们密度连通。这些定义解释了为什么每次扩展只使用局部邻域,簇却能够延伸到很远的距离。

一种等价的操作性描述如下:

  1. 识别所有核心点。
  2. 将距离不超过 ε\varepsilon 的核心点对连接起来。
  3. 找出这个核心点图的连通分量。
  4. 对每个非核心点,如果存在与其相邻的连通分量,就将其归入其中一个。
  5. 将所有剩余点标记为噪声。

对于给定的数据和参数,核心点的连通分量是确定的。然而,一个边界点可能同时位于两个原本互不连通的分量中某些核心点的邻域内。传统 DBSCAN 会将它分配给最先到达它的簇。因此,它的归属可能取决于处理顺序,但不会使这两个核心点分量合并。

算法

标准实现会扫描观测点,每当遇到一个尚未处理的核心点时,就从该点开始扩展一个簇:

  1. 选择一个尚未访问的观测点 pp,并将其标记为已访问。
  2. 查询 Nε(p)N_{\varepsilon}(p)。
  3. 如果邻域中的观测点少于 MinPts\mathrm{MinPts},则暂时将 pp 标记为噪声。
  4. 否则,创建一个簇,并将该邻域中的点放入扩展工作列表。
  5. 处理工作列表。对于每个尚未访问的点,查询其邻域;如果该点是核心点,则将其邻居加入工作列表。
  6. 将到达的观测点分配给当前簇,前提是它们尚未被分配给其他簇。
  7. 继续执行,直到所有观测点都已被访问。

暂时被标记为噪声的观测点,在之后从某个核心点到达时,仍可能成为边界点。因此,实现时不能因为某个观测点早先被标记为噪声,就永久将其排除在所有簇之外。

簇扩展可以使用队列或其他工作列表来实现,其遍历过程类似于广度优先搜索。其中最主要的计算操作是半径邻域查询。

距离与数据表示

DBSCAN 的输出取决于所选表示中距离的含义。欧氏距离较为常见,但对于地理坐标、二元属性或其他数据类型,其他距离可能更合适。有些实现也接受预先计算的相异度矩阵。

当数值属性具有不同单位或取值范围时,特征缩放尤为重要。例如,直接将年龄与年收入合并计算距离而不进行缩放,结果可能主要由收入决定。重新缩放会改变邻域,进而改变聚类结果。

对于地理坐标,将经纬度视为普通笛卡尔坐标可能导致距离失真。采用适当的投影或球面距离,可以使半径更准确地对应预期的实际空间间隔。

DBSCAN 也可以应用于表征学习生成的特征。在这种情况下,簇反映的是表示空间的几何结构,而这种结构未必直接对应语义类别。

参数选择

两个参数共同决定什么样的区域被视为稠密区域。

邻域半径

较小的 ε\varepsilon 会形成较小的邻域,可能使群体分裂,或使许多观测点被标记为噪声。较大的半径往往会连接更多观测点,也可能通过稠密的桥接区域将不同群体合并。

一种常用的启发式方法是考察排序后的 kk 距离图:对每个点,计算它到选定的第几个最近邻点的距离,再将这些距离排序。明显的拐点可能提示稠密区域与较孤立观测点之间的过渡。邻居的计数方式必须与 MinPts\mathrm{MinPts} 是否包含该点自身的约定保持一致。

图中不一定会出现清晰的拐点,尤其是在数据集包含多种密度尺度时。因此,这种图是一种辅助诊断工具,而不是普遍适用的参数选择规则。

邻域内的最少点数

较大的 MinPts\mathrm{MinPts} 要求更充分的局部支持,可以抑制偶然形成的小群体,但也可能使真实的小簇无法被识别。较小的取值允许更细或更小的结构形成簇,却也更容易使稀疏的连接将不同群体连在一起。

经常被引用的“令 MinPts\mathrm{MinPts} 大于维数”这一规则只是一种启发式方法,并不能保证得到有用的聚类结果。合适的取值取决于维数、样本量、噪声以及希望识别的结构尺度。

与K均值聚类不同,DBSCAN 不需要将簇数作为输入。但这并不意味着无需进行模型选择:不同的密度参数可能产生差异很大的簇数和噪声比例。

计算开销

DBSCAN 的时间复杂度主要取决于邻域搜索。对于 nn 个观测点,直接将每个观测点与其他所有观测点逐一比较,需要进行 O(n2)O(n^2) 次距离计算。

当维数、几何结构和邻域大小等条件有利时,KD树等空间索引可以加快查询。在适当条件下,实现的总运行时间可以近似达到 O(nlog⁡n)O(n\log n)。但这并非普遍保证:邻域过大、维数过高或距离度量不合适,都可能导致二次时间复杂度。

内存需求也取决于具体实现:

  • 按需查询邻域的实现,除数据集和搜索索引外,可以只使用 O(n)O(n) 的辅助内存。
  • 存储所有邻域的实现,其内存需求与邻接关系总数成正比,最高可达 O(n2)O(n^2)。
  • 稠密的预计算距离矩阵本身就需要 O(n2)O(n^2) 的存储空间。

采用并行计算和分布式计算的实现可以加速部分计算,但必须协调不同处理分区之间的核心点连通关系。

优势与局限

不规则形状与显式噪声标记

DBSCAN 无需用质心表示群体,就能识别非凸形状的群体。它还会区分未归属任何簇的观测点与簇成员,而不是强制将每个观测点分入某个簇。

这些特性并不意味着它能还原所有视觉上明显的形状。一个结构必须具有足够的局部支持,才能形成连通的核心部分;稠密的桥接区域也可能将概念上不同的群体合并。

密度变化

当不同簇的密度差异显著时,单一的全局半径和最少点数往往不足以处理这些簇。足以保留稠密簇的较小半径,可能使稀疏簇分裂;足以识别完整稀疏簇的较大半径,又可能使稠密群体合并。

高维数据

维数灾难可能降低距离的实用性,并削弱空间索引的效率。在许多高维数据集中,距离的区分能力会下降,因而难以选择一个有意义的统一邻域半径。

降维可以改变这种情况,但也会改变邻域结构。投影后找到的簇,是变换后空间中的簇。

顺序依赖性与结果解释

在距离和参数固定的情况下,核心点身份、核心点连通分量以及最终的噪声点集合都不依赖遍历顺序。归属不明确的边界点,其分配结果可能依赖遍历顺序;簇的数字标签也可以发生置换,而不改变实际分组。

DBSCAN 并不能证明其得到的簇对应自然类别或因果过程。密度模式可能反映的是采样方式、重复记录、测量流程或所选特征。因此,评估结果时,既要关注算法,也要关注数据质量。

应用与相关方法

DBSCAN 用于空间模式发现、点云处理、轨迹分析和探索性分组。在计算机视觉中,它可以将彼此邻近的点或检测结果归为一组。在异常检测中,其噪声标签可以识别稠密群体之外的观测点,不过,稀疏分布的观测点不一定异常,而异常点本身也可能形成稠密簇。

有几种方法处理与之相关的问题:

  • OPTICS 生成一种排序及可达性信息,用以揭示不同邻域尺度下的密度结构。
  • HDBSCAN 构建基于密度的层次结构,并依据与稳定性有关的准则选择簇,有助于处理密度不同的群体。
  • DBSCAN* 将边界点排除在簇之外,仅保留核心点连通分量,从而避免边界点归属不明确的问题。

K均值聚类则是一种与之形成对比的方法:它通常将每个观测点分配到预先指定数量的、以质心为基础的群体之一。DBSCAN 则强调局部密度、连通性,以及某些观测点可能不属于任何簇的情况。