层次聚类

一、层次聚类

  层次聚类(Hierarchical Clustering)通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中，不同类别的原始数据点是树的最低层，树的顶层是一个聚类的根节点。创建聚类树有自下而上合并和自上而下分裂两种方法

二、合并算法 2.1、算法流程

• (1) 将每个对象看作一类，计算两两之间的距离；
  • MIN度量
  • MAX度量
  • Group Average（平均距离度量）
  • Distance Between Centroids（质心度量）
  • Other methods driven by an objective function
    • Ward’s Method uses squared error
• (2) 将距离最相近的两个类合并成一个新类；
• (3) 重新计算新类与所有类之间的距离；
• (4) 重复(2)、(3)，直到所有类最后合并成一类。

不同的度量方式，层次的划分也不一样

2.2、优缺点 2.2.1、优点：

• 1，距离和规则的相似度容易定义，限制少
• 2，不需要预先制定聚类数
• 3，可以发现类的层次关系
• 4，可以聚类成其它形状

2.2.2、缺点：

• 1，计算复杂度太高
• 2，奇异值也能产生很大影响
• 3，算法很可能聚类成链状
• 3，合并策略是最终的，一旦合并不可撤销

Reference

• 09 聚类算法 - 层次聚类 - CF-Tree、BIRCH、CURE
• http://bluewhale.cc/2016-04-19/hierarchical-clustering.html
• scipy实现树状图