【机器学习】24. 聚类-层次式 Hierarchical Clustering
1. 优势和缺点
优点：
- 无需提前指定集群的数量
通过对树状图进行不同层次的切割，可以得到所需数量的簇。 - 树状图提供了一个有用的可视化-集群过程的可解释的描述
- 树状图可能揭示一个有意义的分类
缺点：
- 计算复杂度较大, 限制了其在大规模数据集上的应用，空间复杂度n^2 , 时间复杂度 n^3
- not incremental 没有增量, 假设所有数据都存在
- 噪声和离群点会对聚类结果产生较大影响
2. 两种方法
聚合式 agglomerative(bottom-up) and 分裂式divisive(top-down)
3. 三种Link
- Single link(min)
- Complete link(max)
- Average link
4. 聚合式agglomerative(bottom-up) 实现
- 计算邻近矩阵
- 将每个数据点都视为一个簇
- 重复过程:
- 合并两个最近的簇
- 更新邻近矩阵
- 结束条件: 直到只有一个剩余的簇
5. 分裂式divisive(top-down)实现
- 首先, 将数据点的距离关系表示为一个邻近图, 生成MST
- 重复过程:
- 通过切断MST中的最长边来创建新簇
- 结束条件: 直到所有的点都被分割为单独的簇
