知识卡片
DBSCAN 从种子长成簇
DBSCAN 的执行方式是”先找骨架,再从骨架往外长”,全程不需要预先给簇数:
- 按距离度量算出每个样本的 ε-邻域,邻域内样本数 ≥ MinPts 的进入核心对象集合 Ω。
- 若 Ω 为空就结束;否则从 Ω 里任取一个核心对象作种子。
- 从种子出发,把所有与它密度可达的样本收进同一个簇 C_k。
- 把 C_k 里包含的核心对象从 Ω 中剔除。
- 回到第 2 步,直到 Ω 为空。剩下的、从未被任何核心对象覆盖的点就是噪声。
这里有两个必须知道的实现细节。其一,若某个样本同时落在两个互不密度直达的核心对象的 ε-邻域内,算法按”先来后到”把它判给先聚出来的那个簇——所以 DBSCAN 不是完全稳定的算法,结果与核心对象的遍历顺序有关。其二,瓶颈在邻域搜索:样本量大时可用 KD 树加速,scikit-learn 的 algorithm 参数就是用来选暴力计算、KD 树还是球树的。
结构图:
flowchart TD
A[计算各点 ε-邻域] --> B[得到核心对象集 Ω]
B --> C{Ω 为空?}
C -- 是 --> F[输出各簇与噪声]
C -- 否 --> D[取一个核心对象作种子]
D --> E[扩张所有密度可达点成簇]
E --> G[从 Ω 剔除该簇的核心对象]
G --> C
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 第12章 聚类
原书出处 · 1 处
- 第12章 聚类 12.4.1 密度聚类过程和原理 · 查看原书依据
第3步:在集合Ω中,随机选择一个核心对象o作为种子,找到由它密度可达的所有样本构成一个聚类簇Ck 。
参考来源
- 位置:《机器学习基础:从入门到求职》第12章《第12章 聚类》(源文件:extracted/机器学习基础:从入门到求职/_epub-src/OEBPS/text00015.html)
- 结论依据:原文给出 DBSCAN 五步流程(求核心对象集—判空—选种子扩张成簇—剔除已用核心对象—循环),并说明噪声标记、KD 树加速与"先来后到"导致的不稳定性。
- 原始内容:第3步:在集合Ω中,随机选择一个核心对象o作为种子,找到由它密度可达的所有样本构成一个聚类簇Ck 。