层次聚类

另一种思路

k-means 是“先定 k,再分”。层次聚类反过来:先全部分开,再一步步合并。

过程:

  1. 每个样本自己是一个簇(n 个簇)

  2. 找出最接近的两个簇,合并

  3. 重复,直到只剩一个簇

把合并过程画成树,叫树状图(dendrogram)。横轴是样本,纵轴是合并时的距离。

为什么要画树

树状图的好处是:你可以在任意高度横着切一刀,切出几个簇就是几个。

所以它不像 k-means 那样必须事先定 k——你可以先把树建出来,再决定切在哪。

看哪里

含义

哪两个先合并

它们最像

合并的高度

它们有多不像

很长的竖直分支

这里切最合适——说明这是天然的分界

“接近”的定义不止一种

两个簇之间的距离,有好几种算法:

方法

簇间距离怎么算

倾向

single(最近点)

两个簇里最近的一对点

容易产生长条形簇(链式效应)

complete(最远点)

两个簇里最远的一对点

倾向紧凑的球形簇

average

所有点对的平均距离

折中

Ward

合并后方差增加多少

最常用,倾向等大小的簇

选哪种会得到完全不同的结果

同一份数据,用 single 可能分出两个长条,用 complete 可能分成四个团。

这不是“哪个对”的问题——它们对应不同的“簇”定义。你先要决定“簇”是什么意思,再选方法。

代价

时间 O(n2log⁡n)O(n^2 \log n) 以上,空间 O(n2)O(n^2)(要存距离矩阵)。

几万样本就不行了。而 k-means 是 O(n⋅k⋅t)O(n \cdot k \cdot t),可以处理百万级。

什么时候用层次聚类

  • 样本量不大(几千以内)

  • 你想看数据的层次结构,不只是一个分组结果

  • 不知道该分几个簇,想先看看再决定

  • 需要可解释性:树状图能直接给业务方看

这一课解决了什么

层次聚类不用事先给 k,还能展示“不同粒度下数据长什么样”。代价是慢、吃内存。

但它和 k-means 有个共同的假设:簇是“凸”的,可以用某种距离度量聚在一起。 月牙形、环形这种形状,两个都会失败。下一课讲能处理这种情况的方法。