知识卡片

结构图卡 · 9833.i · 生成模型:DeepSeek-V4.1-Flash

DBSCAN 从种子长成簇

理解等级:中级

DBSCAN 的执行方式是”先找骨架,再从骨架往外长”,全程不需要预先给簇数:

  1. 按距离度量算出每个样本的 ε-邻域,邻域内样本数 ≥ MinPts 的进入核心对象集合 Ω。
  2. 若 Ω 为空就结束;否则从 Ω 里任取一个核心对象作种子。
  3. 从种子出发,把所有与它密度可达的样本收进同一个簇 C_k。
  4. 把 C_k 里包含的核心对象从 Ω 中剔除。
  5. 回到第 2 步,直到 Ω 为空。剩下的、从未被任何核心对象覆盖的点就是噪声。

这里有两个必须知道的实现细节。其一,若某个样本同时落在两个互不密度直达的核心对象的 ε-邻域内,算法按”先来后到”把它判给先聚出来的那个簇——所以 DBSCAN 不是完全稳定的算法,结果与核心对象的遍历顺序有关。其二,瓶颈在邻域搜索:样本量大时可用 KD 树加速,scikit-learn 的 algorithm 参数就是用来选暴力计算、KD 树还是球树的。

结构图:

flowchart TD
    A[计算各点 ε-邻域] --> B[得到核心对象集 Ω]
    B --> C{Ω 为空?}
    C -- 是 --> F[输出各簇与噪声]
    C -- 否 --> D[取一个核心对象作种子]
    D --> E[扩张所有密度可达点成簇]
    E --> G[从 Ω 剔除该簇的核心对象]
    G --> C
这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《机器学习基础:从入门到求职》第12章《第12章 聚类》(源文件:extracted/机器学习基础:从入门到求职/_epub-src/OEBPS/text00015.html) - 结论依据:原文给出 DBSCAN 五步流程(求核心对象集—判空—选种子扩张成簇—剔除已用核心对象—循环),并说明噪声标记、KD 树加速与"先来后到"导致的不稳定性。 - 原始内容:第3步:在集合Ω中,随机选择一个核心对象o作为种子,找到由它密度可达的所有样本构成一个聚类簇Ck 。