机器学习›第 13 章 聚类›层次聚类
层次聚类
另一种思路
k-means 是“先定 k,再分”。层次聚类反过来:先全部分开,再一步步合并。
过程:
每个样本自己是一个簇(n 个簇)
找出最接近的两个簇,合并
重复,直到只剩一个簇
把合并过程画成树,叫树状图(dendrogram)。横轴是样本,纵轴是合并时的距离。
为什么要画树
树状图的好处是:你可以在任意高度横着切一刀,切出几个簇就是几个。
所以它不像 k-means 那样必须事先定 k——你可以先把树建出来,再决定切在哪。
看哪里 | 含义 |
|---|---|
哪两个先合并 | 它们最像 |
合并的高度 | 它们有多不像 |
很长的竖直分支 | 这里切最合适——说明这是天然的分界 |
“接近”的定义不止一种
两个簇之间的距离,有好几种算法:
方法 | 簇间距离怎么算 | 倾向 |
|---|---|---|
single(最近点) | 两个簇里最近的一对点 | 容易产生长条形簇(链式效应) |
complete(最远点) | 两个簇里最远的一对点 | 倾向紧凑的球形簇 |
average | 所有点对的平均距离 | 折中 |
Ward | 合并后方差增加多少 | 最常用,倾向等大小的簇 |
选哪种会得到完全不同的结果
同一份数据,用 single 可能分出两个长条,用 complete 可能分成四个团。
这不是“哪个对”的问题——它们对应不同的“簇”定义。你先要决定“簇”是什么意思,再选方法。
代价
时间 以上,空间 (要存距离矩阵)。
几万样本就不行了。而 k-means 是 ,可以处理百万级。
什么时候用层次聚类
样本量不大(几千以内)
你想看数据的层次结构,不只是一个分组结果
不知道该分几个簇,想先看看再决定
需要可解释性:树状图能直接给业务方看
这一课解决了什么
层次聚类不用事先给 k,还能展示“不同粒度下数据长什么样”。代价是慢、吃内存。
但它和 k-means 有个共同的假设:簇是“凸”的,可以用某种距离度量聚在一起。 月牙形、环形这种形状,两个都会失败。下一课讲能处理这种情况的方法。