使用反转距离的K均值聚类

Question

首先，我想弄清楚如何应用这个算法来解决作业项目。所以，我不是在寻找作业解决方案，只是帮助完成我的算法来解决问题。

我想使用K均值聚类来聚集大集（2^6）数组。这些数组是序列[0,1,2 ... 31]的唯一排列。但是，我不需要使用欧式距离，而需要使用反演距离。

我在k-means中的第一步是从数据集中选择k = 10个随机点。然后我计算数据集中每个值到每个随机k点的反转距离。这给出了最初的聚类。

现在，我不知道如何将下一步从欧氏距离转换为反转距离。我怎样才能找到每个群集的中心（就反演距离而言），所以我可以重复聚类步骤？

作为一个伴侣问题，欧氏距离是一个很好的近似（或等效）反演距离吗？我不相信它，但我不知道如何去证明它。

感谢所有提前。

Answer 1

一般来说，你的不能使用k-means与非欧几里德距离。您可以尝试使用它们来运行算法，但算法终止时收敛的含义很少。

正如您在the Wikipedia entry中看到的那样，欧几里得距离是算法固有的。它通过在E和M类型的步骤之间交替进行工作（如在the EM algorithm中），并且对于欧几里得距离，可以显示两个步骤都使相同的目标函数最小化。对于其他距离，尽管代码看起来相同，但它通常不成立。请参阅this question in Cross Validated。

如果您有不同的距离，您应该使用其他的东西，例如hierarchical clustering或k-medoids。