K-Means 过程——它是一种经常用作聚类方法的矢量量化方法——根本不明确使用 数据点之间的成对距离（与允许任意接近度度量的分层聚类和其他一些聚类相比）。这相当于重复将点分配给最近的质心，从而使用从数据点到质心的欧几里得距离。但是，K-Means隐含地基于数据点之间的成对欧几里得距离，因为与质心的偏差平方和等于成对的欧几里得距离平方和除以点数. 术语“质心”本身来自欧几里得几何。它是欧几里得空间中的多元均值。欧几里得空间大约是欧几里得距离。非欧几里得距离通常不会跨越欧几里得空间。这就是为什么 K-Means 仅适用于欧几里得距离。

但是两个数据点之间的欧几里得距离可以用多种替代方式表示。例如，它与点之间的余弦或标量积密切相关。如果您有余弦、协方差或相关性，您始终可以(1) 将其转换为（平方）欧几里得距离，然后 (2) 为该欧几里得距离矩阵创建数据（通过主坐标或其他形式的度量）多维缩放）到（3）将这些数据输入到 K-Means 聚类。因此，可以 使 K-Means “与”成对的余弦等“一起工作”；事实上，存在这样的 K-Means 聚类实现。也可以看看关于“距离矩阵的K-means”实现。

当然，可以对 K-means 进行编程，使其直接在成对欧几里德距离的方阵上进行计算。但它会运行缓慢，因此更有效的方法是为该距离矩阵创建数据（将距离转换为标量产品等 - 上一段中概述的通道） - 然后应用标准 K-means 程序到那个数据集。

请注意，我正在讨论数据点之间的欧几里得或非几里得差异是否与 K-means 兼容的主题。它与质心（广义上的中心或准质心）的非几里得偏差是否可以合并到 K-means 或修改的“K-means”中有关但不完全相同的问题。

请参阅相关问题K-means：为什么最小化 WCSS 是最大化集群之间的距离？.

另请参阅@ttnphns 答案，了解实际上涉及逐点欧几里德距离的 k 均值的解释。

k-means 的构建方式不是基于 distances。

K-means 最小化集群内方差。现在，如果您查看方差的定义，它与距中心的欧几里得距离平方和相同。（@ttnphns 答案指的是成对的欧几里得距离！）

k-means 的基本思想是最小化平方误差。这里不涉及“距离”。

为什么使用任意距离是不正确的：因为k-means 可能会停止与其他距离函数收敛。收敛的常见证明是这样的：分配步骤和平均更新步骤都优化了相同的标准。可能的分配数量是有限的。因此，它必须在有限数量的改进后收敛。要将此证明用于其他距离函数，您必须证明均值（注意：k- means）也可以最小化您的距离。

如果您正在寻找 k 均值的曼哈顿距离变体，则有 k 中位数。因为中位数是已知的最佳 L1 估计量。

如果您想要任意距离函数，请查看 k-medoids（又名：PAM，围绕 medoids 进行分区）。中心点最小化任意距离（因为它被定义为最小值），并且也只存在有限数量的可能中心点。不过，它比平均价格贵得多。

我在这里可能有点迂腐，但 K-means 是赋予特定算法的名称，该算法将标签分配给数据点，以使集群内的方差最小化，它不是“通用技术”的名称。

K-means 算法已经从多个领域独立提出，具有适用于该领域的强烈解释。事实证明，它也是到中心的欧几里得距离。有关 K-means 的简要历史，请阅读数据聚类：K-means 的 50 年

有许多其他聚类算法使用欧几里得以外的度量。我知道的最一般的情况是使用Bregman Divergences进行聚类，其中欧几里得是一个特例。

由于这显然现在是一个规范问题，因此此处尚未提及：

k-means 在 $\mathbb R^d$ 上使用标准欧几里得距离以外的距离度量的一种自然扩展是使用内核技巧。这是指将输入隐式映射到高维或无限维希尔伯特空间的想法，其中距离对应于我们想要使用的距离函数，并在那里运行算法。也就是说，让 $\varphi : \mathbb R^p \to \mathcal H$ 是一些特征图，使得所需的度量 $d$ 可以写成 $d(x, y) = \lVert \varphi(x) - \varphi(y) \rVert_{\mathcal H}$，我们在点 $\{ \varphi(x_i) \}$ 上运行 k-means。在许多情况下，我们无法显式计算映射 $\varphi$，但我们可以计算内核 $k(x, y) = \langle \varphi(x), \varphi(y) \rangle_{\mathcal H}$。并非所有距离度量都适合这个模型，但很多都适合，并且在字符串、图形、图像、概率分布等上定义了这样的函数......

在这种情况下，在标准 (Lloyd's) k-means 算法中，我们可以轻松地将点分配给它们的集群，但我们隐式地表示集群中心（作为希尔伯特空间中输入点的线性组合）。在输入空间中找到最佳表示需要找到一个Fréchet mean，这非常昂贵。因此，使用内核很容易获得集群分配，但更难获得手段。

以下论文讨论了该算法，并将其与谱聚类相关联：

I. Dhillon、Y. Guan 和 B. Kulis。内核 k 均值、光谱聚类和归一化切割。2005 年 KDD。