Scipy Ward层次聚类的linkage结果是否依赖节点顺序？

核心原因 #

当数据存在0距离对时，Ward聚类的合并顺序会受数据行排列的影响，最终导致树结构和聚类标签差异。这是因为：

• Ward算法采用贪心策略，每次选择能最小化类内方差增量的样本对合并。当多组样本对的方差增量相同时，scipy.cluster.hierarchy.linkage会按输入数据的原始顺序优先合并先遇到的样本对。
• 重排数据后，相同方差增量的候选合并对出现的顺序改变，合并路径随之变化，最终树结构和cut_tree结果自然不同。

是否属于预期行为？ #

这是Ward聚类在存在重复/近重复样本时的非确定性表现，并非Scipy的bug，但也不符合“数据重排后结果一致”的常规预期。这类基于贪心逻辑的聚类算法在遇到等价合并选项时，都可能出现类似情况。

确保可复现性的方法 #

1. 预处理去重：移除完全重复的样本，或用均值、中位数等方式合并重复样本，消除等价合并的候选。
2. 自定义合并规则：如果必须保留重复样本，可以实现自定义Ward合并逻辑，当遇到方差增量相同时，用固定规则（比如选择索引更小的样本对）确定合并顺序，不受数据排列影响。
3. 验证距离矩阵输入：确认np.triu_indices_from(dist, k=1)提取的压缩距离矩阵，与重排后的数据行/列顺序完全对应——比如重排后的DataFrame行索引变化，是否同步更新了距离矩阵的行和列顺序。

额外验证步骤 #

• 对比两棵树的聚类有效性指标（如轮廓系数），若指标相近，说明两种聚类的实际效果差异不大，仅合并路径不同；若指标差异明显，可能是距离矩阵构建或传入过程出错。
• 尝试直接将原始数据和重排数据传入linkage(method='ward')（不手动传预计算的距离矩阵），若结果一致，说明问题出在手动构建压缩距离矩阵的步骤中。

内容的提问来源于stack exchange，提问作者Nikolay Markov