经典的凝聚层次聚类方法基于贪心算法。这意味着他们（其中许多人）倾向于给出次优解决方案而不是全局最优结果，尤其是在集聚的后续步骤中。上对合并哪两个集群做出最佳选择，该选择使步骤上的碰撞系数最小化（使值） ；然而，如果算法在之前的一些步骤中选择的不是最好的而是更差的选择，那么它就能够最小化步骤的系数，这并非不可能。$q$$\delta_q$$\delta$$q$值小于的单调增长。上的全局最优解对应于绝对最小的这种方式可实现的值，并保留的限制。$\delta_q$$\delta$$q$$\delta_q$$\delta_q \ge \delta_{q-1} \ge \delta_{q-2} \cdots$

次优风​​险是通常不建议对大量对象（例如，超过数百个）进行层次聚类的主要原因：研究人员通常需要很少的聚类，因此会考虑后面的步骤，但如果后面的步骤是，比如说，第 1000 步，在第 1000 步可能偏离全局最优分区比在第 100 步可能偏离全局最优分区的第 100 步更可疑。这看起来是一个格言问题。

我的问题是你认为在著名的聚集方法中哪一个 - 单一链接，完全链接，平均链接（组内），平均链接（组间），质心，中位数，沃德平方和 - 我是提到SPSS中的那些，但还有其他类似的变体 -更多，更不容易出现次优缺陷随着步数的增长。直觉告诉我，单个或完整的链接根本不存在，并且总是给出它们全局最佳的解决方案，因为这些方法不参与计算从原始距离（例如质心）衍生的任何统计数据。我可能是对的，也可能不是。其余的方法是什么？这里有人可以尝试分析上述具体贪心算法的局部最优风险的（相对）程度吗？

插图。幸运的是，对于Ward方法，我们有线索可以观察到次优性如何随着的增长而累积。因为有一种众所周知的迭代方法试图优化与Ward这是K-means聚类：两者都试图最小化合并的聚类内平方和。我们可以进行 Ward 聚类，并在每一步保存聚类中心，并将其用作 K-means 程序中的初始中心。K-means 会在平方和方面改进 Ward 的解决方案吗？$q$$\delta$ $^1$

[脚注：Ward 最小化其台阶上平方和的增加。另一种不太为人所知的分层方法，方差方法 MNVAR（参见 Podany，J.，1989 年的各种分层方法）可最大限度地减少聚类内的均方值。这两种方法都可以被认为是 K-Means 的一种，Ward 在最终 SSwithin 的最小化方面比 MNVAR 更好（我自己的模拟研究）。]$^1$

笔记。这个插图测试了 Ward 观察到的值，而不是针对它自己的全局最优值，这是我们无法知道的，因为我们无法为每一步尝试所有先前步骤的无数替代重建，以找出可能的最小；它针对K-means最优性进行测试（这几乎是它的全局性，因为 Ward 提供的初始中心可以被认为是迭代的合理良好开端）。$\delta_q$$\delta_q$

这是一些数据（5 个没有很好分离的集群，183 个点）。如所述，数据经历了 Ward 聚类会话和 K-means 聚类会话。

集群 50 到 2 的结果（的值）如下所示。虽然 2 条曲线彼此接近，但 K-means 的值要好一些。也就是说，K-means 比 Ward 更优。$\delta$

最后一张图片绘制。趋势很明显：随着集群数量的减少（即，Ward 的步长增加），Ward 相对于 K-means 趋向于变得不太理想。$\delta^{Ward}/\delta^{Kmeans}$$q$

一个诱人的问题是，如果我以相同的方式分析 1830 年的数据，Ward 的相对次优性（的值）在这最新的 49 个聚集步骤上是否会更高点而不是只有 183。$\delta^{Ward}/\delta^{Kmeans}$