草稿
HDBSCAN
构建密度层级，并选择在多个密度层级中保持稳定的簇。
algorithm advanced machine-learningclusteringalgorithms
Hook problem：不同区域密度不同
DBSCAN 要求一个密度尺度。OPTICS 暴露多个可能尺度。HDBSCAN 进一步询问：哪些簇会随着密度要求变化而持续存在？
关键动作是：不再把每个切分都当成同等可信。
wide-density: p1, p2, p3, p4, p5, p6, p7, p8, p9 | stability 0.80
A: p1, p2, p3, p4 | stability 2.90
B: p5, p6, p7, p8 | stability 3.10
A-core: p1, p2, p3 | stability 1.40
B-core: p5, p6, p7 | stability 1.50
First naive idea：凭眼睛选最好看的密度切分
手动挑一个切分很脆弱。短命分支可能在某个尺度看起来真实，但到下一个尺度马上消失。
HDBSCAN 用跨层级稳定性来修补这个问题。
Core invention：压缩密度树
HDBSCAN 把距离转成互可达距离（mutual-reachability distance），建立层级，压缩太小的分支，再选择稳定簇。
直觉是：
短命分支会被视为噪声或子结构。
Interactive trace lab
聚类算法轨迹实验台
步骤 1/2: 密度要求变严格时，簇会分裂。
保留在多个密度层级中保持稳定的簇。
A, B
Implementation sketch
compute core distances;
build mutual-reachability graph;
build a minimum spanning tree;
condense the hierarchy by minimum cluster size;
select stable branches as clusters;Correctness intuition and cost
层级记录了密度要求变严格时簇如何分裂。稳定性避免某个簇只因为碰巧存在于一个阈值上就胜出。
实际实现很依赖最近邻和最小生成树例程。简单稠密实现可能接近 O(n^2)；在合适数据上，优化版本可以更快。
Common confusions
- HDBSCAN 不只是自动选
epsilon的 DBSCAN。 - 它可以把点标记为噪声。
- 它仍有最小簇大小等参数，并非完全无参数。
- 层级是模型的一部分，不只是画图技巧。
不断移动质心，直到平方距离簇基本稳定。
用真实样本点做中心，降低离群点的影响。
从高密度邻域扩张簇，并把孤立点留作噪声。
按密度可达性排序点，而不是只选一个固定半径。
保留在多个密度层级中保持稳定的簇。
在软成员概率估计和高斯参数更新之间交替。
Exercises
- 为什么跨密度层级持续存在有用？
- 什么样的分支应该被当作噪声？
- 为什么 HDBSCAN 仍需要最小簇大小选择？
图谱连接 : HDBSCAN