我想知道kmeans中使用的距离度量是否需要三角不等式。
问问题
2530 次
2 回答
3
好吧，经典的 kmeans 是在具有 L2 距离的欧几里得空间上定义的，所以你会自动得到三角不等式（三角不等式是定义距离/度量的一部分）。如果您使用的是非欧几里德度量，则需要定义“均值”的含义等。
如果你没有三角不等式，这意味着两点可能相距很远，但都可能靠近第三点。您需要考虑如何解释这个案例。
说了这么多，我过去曾使用平均链接层次聚类和距离度量，但不能满足三角不等式等要求，它非常适合我的需求。
于 2012-07-16T17:46:50.980 回答
3
k-means 是为欧几里得距离设计的，恰好满足三角不等式。
使用其他距离函数是有风险的，因为它可能会停止收敛。然而，原因不是三角不等式，而是平均值可能不会最小化距离函数。（算术平均值最小化平方和，而不是任意距离！）
有更快的 k-means 方法利用三角不等式来避免重新计算。但是如果你坚持经典的 MacQueen 或 Lloyd k-means，那么你就不需要三角不等式。
请注意使用其他距离函数，以免陷入无限循环。您需要证明均值可以最小化您到聚类中心的距离。如果你不能证明这一点，它可能无法收敛，因为目标函数不再单调递减！所以你真的应该尝试证明你的距离函数的收敛性！
于 2012-07-18T05:37:43.247 回答