聚类分析 -- 层次聚类

层次聚类算法，分为两个方向，自顶向下（分裂的）或自底向上（凝聚的），通过定义簇的临近性概念来逐步进行聚类。

关键性问题：临近性度量

• 单链，两个簇中任意两点之间的最短距离（最大相似度），擅于处理非椭圆形的簇，但对噪声和离群点敏感
• 全链，两个簇中任意两点之间的最长距离（最小相似度），对噪声和离群点不敏感，但是可能使大的簇破裂，偏好球形。
• 组平均，不同簇的所有点对临近度的平均值
• ward 方法，两个簇合并时导致的平方误差的增量，目标函数与 K 均值相同，并且可以证明：当两个点之间的临近度取距离的平方时，Ward 方法与组平均类似 （推荐）

缺点：

• 缺乏全局目标函数，每一步都是局部最优，但是不能保证全局最优
• 时空间复杂度高，空间复杂度为 o(n^2)，时间复杂度 o(n^2 logn)

应用：使用 SciPy 的层次聚类包进行层次聚类，别人写的非常好 使用 SciPy 层次聚类包