机器学习方法篇(20)层次聚类法

● 每周一言

如果有人相信你，给你机会，你就有义务加倍努力。

导语

前面介绍了划分聚类法，在划分聚类中，通常需要指定聚类个数，这样指定的个数往往不是最优个数。本节要讲的层次聚类法，更关心的是同类别样本之间的相似性，而非聚类个数。那么，层次聚类的原理思想是什么？又有哪些常用算法？

层次聚类

层次聚类顾名思义，按层次对样本进行聚类。层次聚类法按照层次分解顺序可以分成自底向上和自顶而下两种方式。自底向上的方式我们称为凝聚层次法，而自顶而下叫做分裂层次法。

对于凝聚层次法，一开始的每个样本都是一个类，然后根据相似性度量法寻找同类样本，自下而上一层一层形成类别。

分裂层次法则相反，一开始所有的样本都属于同一个大类，然后根据相似性度量法拆分样本，最后越拆越小，直到每一个样本都成为一个小类。

由于大部分的层次聚类法都属于凝聚层次法，本文将重点讲一下凝聚层次法的算法流程。

凝聚层次法类似于哈夫曼树的构建。哈夫曼树就是每次选择权值最小的节点组成一棵新树，直到所有节点合并成一棵权值路径和最小的树。同理，凝聚层次法根据样本之间的最小距离来合并成类，具体算法流程如下：

1> 起初，每个样本独自为一类，计算两两类之间的最小距离；
2> 合并距离最小的两个类为一个新类；
3> 重新计算产生的新类与剩余所有类之间的距离；
4> 重复上述两步，直到只剩下一个类，或类间距离大于某一阈值。

上述类间距离的计算方法可以是最小距离法、平均法等。其中最小距离法指的是类之间最近样本的距离；而平均法是最常用的方法，即两两计算类间样本的距离后取平均值作为类间距离。

层次聚类优点：
1. 无需预先指定聚类个数；
2. 可以发现类的层次关系；
3. 能够聚出各种形状的类。

层次聚类缺点：
1. 计算复杂度高；
2. 可能聚成链状类。

以上便是层次聚类的讲解，敬请期待下节内容。

结语

感谢各位的耐心阅读，后续文章于每周日奉上，敬请期待。欢迎大家关注小斗公众号 对半独白！