使用欧几里德距离与曼哈顿距离实施 k-means？

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 不会最小化距离。

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

如果您按欧氏距离将点分配到最近的簇，它仍然会最小化平方和，而不是欧氏距离。特别是，欧氏距离之和可能增加。

最小化欧氏距离是韦伯问题。 mean 不是最优的。您需要一个复杂的几何中位数来最小化欧氏距离。

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

我想我前段时间在 SO 或 stats.SE 上发布了一个 k 均值最小化欧几里德距离的反例。因此，您的代码和分析甚至可能没问题 - 有缺陷的是作业。

使用欧几里德距离与曼哈顿距离实施 k-means？

Implementing k-means with Euclidean distance vs Manhattan distance?

python

cluster-analysis

k-means

euclidean-distance