三角不等式对于kmeans聚类算法是否必要？

Question

我想知道在kmeans中使用的距离度量是否需要三角不等式。

- Masood_mj

Answer 1

k-means算法是为欧几里得距离设计的，它恰好满足三角不等式。

使用其他距离函数是有风险的，因为可能会导致算法无法收敛。然而，原因并不是三角不等式，而是平均值可能不能最小化距离函数（算术平均值只能最小化平方和，而不能最小化任意距离！）。

对于k-means算法，有一些更快的方法利用三角不等式来避免重新计算。但如果你坚持使用经典的MacQueen或Lloyd k-means算法，那么你就不需要使用三角不等式。

只要小心使用其他距离函数，以免陷入无限循环。你需要证明平均值最小化了到聚类中心的距离。如果你无法证明这一点，它可能无法收敛，因为目标函数不再单调递减！所以你真的应该尝试证明你的距离函数的收敛性！

- Has QUIT--Anony-Mousse

---

我的目标是创建具有所有成员中最少数量的1位的聚类（我需要为每个1位提供存储空间）。我将中心定义为所有成员的Or()，并使用|Or(x,y)|作为距离函数。目前，我使用链接算法创建分层聚类，而不是使用kmeans，这非常有效。 - Masood_mj

@Anony-Mousse：您是否有关于平均值必须是最小方差估计量的要求的参考资料？我已经阅读了相当多的机器学习教材（例如Bishop 2007、Alpaydin 2009），但我从未见过这样的要求。 - stackoverflowuser2010

@stackoverflowuser2010，均值是位置的最小二乘估计量，这是高斯在1800年左右证明的事实，而不是要求。需要在两个步骤中使用一致的标准来保证收敛证明。但是，这些教科书中是否讨论了收敛性呢？（我已经改进了上面的措辞，以便更容易理解。） - Has QUIT--Anony-Mousse

不幸的是，机器学习教材在非监督方法方面往往非常浅显。 - Has QUIT--Anony-Mousse

Answer 2

经典的kmeans是在欧几里得空间中定义的，使用L2距离，因此您可以自动获得三角不等式（三角不等式是距离/度量如何定义的一部分）。如果您使用的是非欧几里得度量，则需要定义“平均值”的含义以及其他事项。

如果没有三角不等式，则意味着两个点之间可能相距很远，但两者都可以接近第三个点。您需要考虑如何解释这种情况。

话虽如此，过去我已经使用了平均链接层次聚类和一种距离度量，该距离度量未实现三角不等式等功能，但它非常适合我的需求。

- Bitwise

---

谢谢。我正在处理二进制数据，并将点的位数的Or()定义为簇中点的平均值。我想使用d(A,B)=|Xor(A,B)|/|And(A,B)|来显示将点添加到簇中的成本与收益之比。然而，它不满足该属性。我最初考虑了Jaccord距离，但其含义不同。 - Masood_mj

我不确定你的度量标准想要实现什么，但是kmeans确实是针对L2（欧几里得）距离定义的 - 其他方法如UPGMA更自然地允许不同的度量标准。关于度量标准，它真的取决于你的目标，但汉明距离怎么样？它满足三角不等式。 - Bitwise

Answer 3

就像维数是向量空间中线性独立向量的最大数量一样，在线性代数中有4个主要子空间（行空间、列空间、零空间和左零空间）-你可以使用曼哈顿距离（不需要三角化）或欧几里得距离（需要三角化）来计算表格数据的距离。但无论如何，在笛卡尔坐标系（也称为2D [行-列]）中，考虑到点之间的向量之间的cos()（在使用三角化时 - 通常使用K-means进行操作）。

正如cos(90˚C)=0（ref“越接近0 - 两个向量越接近正交”）- 因此，是的，需要三角不等式。如果您的点在一个轴上相似[cos=0]（它们之间没有角度），那么距离就是它们在一个空间中的纯距离，并且在另一个空间中为0，这是由于cos(90˚C)=0。因此，要创建特征的投影矩阵，最好考虑三角不等式（就像K-Means使用欧几里得距离而不是曼哈顿距离所做的那样）。

p.s. cos(90˚C)=0 导致维度诅咒，指向此处

P.P.S. 小心：欧氏距离（在K-means中）提供误导性信息有关异常值（k-medians似乎更好使用，k-medoids似乎有争议）

P.P.P.S 对于分类任务，你可以不关心距离[点击链接]（只关心最佳交叉验证结果），仅对于聚类任务关心你选择的距离和算法

- JeeyCi