机器算法验证 - 可以在层次聚类中使用曼哈顿距离和 Ward 的集群间链接吗？ - 吾爱随笔录

可以在层次聚类中使用曼哈顿距离和 Ward 的集群间链接吗？

机器算法验证聚类距离函数病房

2022-01-24 11:30:50

我正在使用层次聚类来分析时间序列数据。我的代码是使用Mathematica函数实现的DirectAgglomerate[...]，它在给定以下输入的情况下生成层次集群：

距离矩阵 D
用于确定集群间链接的方法的名称。

我已经使用曼哈顿距离计算了距离矩阵 D：

d (x, y) = \sum_{i} | x_{i} - y_{i} |

$d(x,y) = \sum_i|x_i - y_i|$

其中和是我的时间序列中的数据点数。 $i = 1,\cdots, n$ $n \approx 150$

我的问题是，可以将 Ward 的集群间链接与曼哈顿距离矩阵一起使用吗？一些消息来源表明，沃德的联系只应与欧几里得距离一起使用。

请注意，DirectAgglomerate[...]仅使用距离矩阵而不是原始观测值来计算 Ward 的链接。不幸的是，我不确定Mathematica如何修改 Ward 的原始算法，该算法（根据我的理解）通过最小化观察值平方和的误差来工作，根据聚类平均值计算。例如，对于由单变量观测向量组成的集群，Ward 将误差平方和公式化为： $c$

(\sum_{j} | | c_{j} - m e a n (c) | |_{2})^{2}

$(\sum_j||c_j - mean(c)||_2)^2$

（其他软件工具，如 Matlab 和 R也仅使用距离矩阵实现 Ward 的聚类，因此问题不是 Mathematica 特有的。）

4个回答

Ward 聚类算法是一种层次聚类方法，可在每一步最小化“惯性”标准。这种惯性量化了减少信号和初始信号之间的残差平方和：它是 l2（欧几里得）传感器中误差方差的量度。实际上，您甚至在问题中提到了它。这就是为什么，我相信，将它应用于不是 l2 欧几里得距离的距离矩阵是没有意义的。

另一方面，平均链接或单个链接层次聚类将非常适合其他距离。

我想不出 Ward 应该支持任何指标的任何理由。Ward 的方法只是决定在聚集过程中接下来要融合哪些集群的另一种选择。这是通过找到融合将最小化某个误差的两个集群来实现的（公式的示例来源）。

因此，它依赖于两个概念：

向量的平均值（对于数值向量）通常通过分别对每个维度进行平均来计算。
距离度量本身，即该度量所表达的相似性概念。

所以：只要所选度量的属性（例如旋转、平移或尺度不变性）满足您的需求（并且度量适合计算集群平均值的方式），我认为没有任何理由不使用它.

我怀疑大多数人建议使用欧几里得度量，因为他们

想要增加聚类均值和单个观察向量之间差异的权重（通过四分法完成）
或者因为它是基于他们的数据的验证中的最佳指标
或者因为它被普遍使用。

考虑这一点的另一种方式，可能有助于适应是平均值的选择来自这样一个事实，即平均值是使平方欧几里得距离之和最小化的点。如果您使用来测量时间序列之间的距离，那么您应该使用最小化平方距离之和的中心。 $\ell_1$ $\ell_1$ $\ell_1$

尽管 Ward 旨在与欧几里德距离一起使用，但本文表明，使用 Ward 和非欧几里德距离的聚类结果与使用欧几里德距离的结果基本相同。

结果表明，Ward 方法对非正定和归一化相似度的结果与 Ward 方法对通过在对角元素上添加正常数从原始相似度获得的正定矩阵的另一个结果几乎相同.

S. Miyamoto、R. Abe、Y. Endo 和 J. Takeshita，“用于非欧几里得相似性度量的层次聚类的 Ward 方法”，2015 年第 7 届软计算和模式识别国际会议 (SoCPaR)，福冈，2015 年，pp。 60-63，doi：10.1109/SOCPAR.2015.7492784。

其它你可能感兴趣的问题

上一篇Scipy中的Beta分布拟合下一篇单边置信区间能否覆盖 95%