使用欧几里得距离与曼哈顿距离实现 k 均值？

Question

我正在 python 和 Spark 上从头开始实现 kmeans 算法。事实上，这是我的作业。问题是用不同的初始化方法实现具有预定义质心的kmeans，其中一种是随机初始化（c1），另一种是kmeans++（c2）。此外，还需要使用不同的距离度量、欧几里得距离和曼哈顿距离。两者的公式介绍如下：

每个部分中的第二个公式用于相应的成本函数，该函数将被最小化。我已经实现了这两个，但我认为有一个问题。这是使用不同设置的 kmeans 每次迭代的成本函数图：

第一个图看起来不错，但第二个图似乎有问题，因为就我而言，每次迭代后 kmeans 的成本必须减少。那么，问题是什么？这是我的代码或公式吗？

这些是我计算距离和成本的函数：

def Euclidean_distance(point1, point2):
    return np.sqrt(np.sum((point1 - point2) ** 2))

def Manhattan_distance(point1, point2):
    return np.sum(np.absolute(point1 - point2))

def cost_per_point(point, center, cost_type = 'E'):
    if cost_type =='E':
        return Euclidean_distance(point, center)**2
    else:
        return Manhattan_distance(point, center)

这是我在 GitHub 上的完整代码： https://github.com/mrasoolmirzaei/My-Data-Science-Projects/blob/master/Implementing%20Kmeans%20With%20Spark.ipynb

Answer 1

K-means 不会最小化距离。

它最小化平方和（这不是度量）。

如果通过欧几里德距离将点分配给最近的簇，它仍然会最小化平方和，而不是欧几里德距离。特别地，欧氏距离的总和可能会增加。

最小化欧几里得距离是韦伯问题。平均值不是最优的。您需要一个复杂的几何中位数来最小化欧几里德距离。

如果您用曼哈顿距离分配点，则不清楚什么被最小化......您有两个相互竞争的目标。虽然我假设它仍然会收敛，但这可能很难证明。因为使用平均值可能会增加曼哈顿距离的总和。

我想我不久前在 SO 或 stats.SE 上发布了一个 k 均值最小化欧几里得距离的反例。所以你的代码和分析甚至可能没问题——只是作业有缺陷。