KMeans聚类中的距离计算：从欧氏距离到曼哈顿距离的全面解析
KMeans聚类中的距离计算：从欧氏距离到曼哈顿距离的全面解析
在机器学习领域，聚类算法扮演着无监督学习的重要角色，而KMeans作为其中最经典和广泛应用的算法之一，其核心思想简单却强大。但你是否曾思考过，为什么同样的数据集使用KMeans会得到不同的聚类结果？答案很可能隐藏在距离度量的选择中。本文将带你深入探索KMeans中距离计算的奥秘，从数学原理到代码实现，全面解析不同距离度量如何影响聚类效果。
1. 距离度量的基础概念
距离度量是KMeans算法中决定样本归属的核心标准。想象一下，当你在城市中规划多个便利店的位置时，如何确定每个居民区应该归属于哪个便利店？这个决策过程本质上就是距离计算的问题。
常见的距离度量包括：
欧氏距离(Euclidean Distance)：这是最直观的距离概念，源自我们日常的几何空间认知。在二维空间中，两点之间的欧氏距离就是它们之间的直线距离。数学表达式为：
def euclidean_distance(x, y): return np.sqrt(np.sum((x - y)**2))曼哈顿距离(Manhattan Distance)：又称城市街区距离，得名于曼哈顿整齐的街区布局。它计算的是两点在各坐标轴上的投影距离总和。在二维空间中，相当于只能沿着街道行走的最短路径。
def manhattan_distance(x, y): return np.sum(np.abs(x - y))
有趣的是，这两种距离实际上是更广义的闵可夫斯基距离(Minkowski Distance)的特例。闵可夫斯基距离的公式为：
$$ D(x,y) = \left( \sum_{i=1}^n |x_i - y_i|^p \right)^{1/p} $$
当p=1时，就是曼哈顿距离；p=2时，就是欧氏距离。
提示：在实际应用中，选择哪种距离度量取决于数据的特性和业务需求。欧氏距离对异常值更敏感，而曼哈顿距离在高维数据中往往表现更稳定。
2. 距离度量在KMeans中的角色
KMeans算法的核心步骤可以概括为：
- 随机初始化K个质心
- 将每个样本分配到最近的质心所在的簇
- 重新计算每个簇的质心
- 重复步骤2-3直到收敛
其中，"最近"的定义完全依赖于我们选择的距离度量。这就像用不同的尺子测量同一物体，得到的结果自然不同。
不同距离度量对聚类结果的影响：
| 特性 | 欧氏距离 | 曼哈顿距离 |
|---|---|---|
| 形状偏好 | 倾向于形成球形簇 | 形成轴对齐的矩形簇 |
| 对异常值的敏感性 | 高 | 相对较低 |
| 计算复杂度 | 中等 | 较低 |
| 适用场景 | 低维空间、各向同性数据 | 高维数据、稀疏数据 |
在sklearn的KMeans实现中，默认使用欧氏距离，但我们可以通过自定义距离函数来改变这一行为。下面是一个比较两种距离下聚类效果的示例：
from sklearn.cluster import KMeans import numpy as np # 生成样本数据 X = np.array([[1, 2], [1, 4], [1, 0], [10, 2], [10, 4], [10, 0]]) # 欧氏距离下的KMeans kmeans_euclidean = KMeans(n_clusters=2, random_state=42).fit(X) # 曼哈顿距离下的KMeans（通过precomputed实现） from sklearn.metrics import pairwise_distances manhattan_dist = pairwise_distances(X, metric='manhattan') kmeans_manhattan = KMeans(n_clusters=2, random_state=42).fit(manhattan_dist)3. 质心计算的数学原理
质心是KMeans算法中另一个关键概念，它代表了一个簇的中心位置。有趣的是，质心的定义其实隐含了距离度量的选择。
对于欧氏距离，质心就是簇中所有样本的算术平均值。这是因为均值最小化了簇内样本的平方欧氏距离和（即Inertia）：
$$ \arg\min_c \sum_{x \in C} ||x - c||^2 $$
而对于曼哈顿距离，最优的质心应该是簇中样本的中位数。这是因为中位数最小化的是绝对偏差和：
$$ \arg\min_c \sum_{x \in C} |x - c| $$
计算质心的Python实现对比：
import numpy as np # 欧氏距离下的质心（均值） def centroid_euclidean(cluster): return np.mean(cluster, axis=0) # 曼哈顿距离下的质心（中位数） def centroid_manhattan(cluster): return np.median(cluster, axis=0) # 示例 cluster_data = np.array([[1, 2], [2, 3], [3, 4], [100, 100]]) # 含有一个离群点 print("欧氏质心:", centroid_euclidean(cluster_data)) # 受离群点影响大 print("曼哈顿质心:", centroid_manhattan(cluster_data)) # 对离群点更鲁棒在实际应用中，sklearn的KMeans实现总是使用均值作为质心，即使你使用其他距离度量。这意味着如果你真正想要曼哈顿距离下的最优聚类，可能需要自己实现KMeans算法。
4. 距离度量的高级应用与优化
理解了基础的距离度量后，我们可以进一步探讨如何针对特定场景优化距离计算。
4.1 特征缩放的重要性
不同特征可能有不同的量纲，这会严重影响距离计算。例如，一个特征范围是0-1，另一个是0-10000，后者将主导距离计算。常见的解决方法包括：
- 标准化（Standardization）：
(x - mean) / std - 归一化（Normalization）：
(x - min) / (max - min)
from sklearn.preprocessing import StandardScaler scaler = StandardScaler() X_scaled = scaler.fit_transform(X) kmeans = KMeans(n_clusters=2).fit(X_scaled)4.2 自定义距离度量
在某些场景下，标准的欧氏或曼哈顿距离可能不够适用。sklearn允许我们通过传递可调用对象作为metric参数来定义自己的距离函数：
def custom_distance(x, y): # 例如，给不同特征赋予不同权重 weights = np.array([0.7, 0.3]) # 第一个特征更重要 return np.sqrt(np.sum(weights * (x - y)**2)) # 使用pairwise_distances计算自定义距离矩阵 custom_dist = pairwise_distances(X, metric=custom_distance) kmeans_custom = KMeans(n_clusters=2).fit(custom_dist)4.3 大规模数据下的距离计算优化
当数据量很大时，距离计算可能成为性能瓶颈。几种优化策略包括：
- 使用稀疏矩阵表示
- 采用近似算法或采样
- 利用并行计算
from sklearn.cluster import MiniBatchKMeans # 适用于大数据集的近似算法 mbkmeans = MiniBatchKMeans(n_clusters=2, random_state=42) mbkmeans.fit(X_large)5. 实战案例：不同距离度量的可视化比较
为了直观展示不同距离度量的影响，我们创建一个简单的二维数据集并进行聚类实验。
5.1 数据准备
import matplotlib.pyplot as plt from sklearn.datasets import make_blobs # 生成三个明显分离的簇 X, y = make_blobs(n_samples=300, centers=3, cluster_std=0.6, random_state=42) # 添加一些噪声点 np.random.seed(42) noise = np.random.uniform(low=-10, high=10, size=(20, 2)) X = np.vstack([X, noise])5.2 欧氏距离聚类
kmeans_euclidean = KMeans(n_clusters=3, random_state=42) y_pred_euclidean = kmeans_euclidean.fit_predict(X) plt.scatter(X[:, 0], X[:, 1], c=y_pred_euclidean, cmap='viridis') plt.scatter(kmeans_euclidean.cluster_centers_[:, 0], kmeans_euclidean.cluster_centers_[:, 1], s=200, c='red', marker='X') plt.title("KMeans with Euclidean Distance") plt.show()5.3 曼哈顿距离聚类
# 计算曼哈顿距离矩阵 manhattan_dist = pairwise_distances(X, metric='manhattan') kmeans_manhattan = KMeans(n_clusters=3, random_state=42) y_pred_manhattan = kmeans_manhattan.fit_predict(manhattan_dist) plt.scatter(X[:, 0], X[:, 1], c=y_pred_manhattan, cmap='viridis') plt.title("KMeans with Manhattan Distance") plt.show()从可视化结果中可以观察到，欧氏距离形成的簇边界更圆滑，而曼哈顿距离形成的簇边界更倾向于形成与坐标轴对齐的矩形。对于噪声点，曼哈顿距离通常表现出更好的鲁棒性。
6. 距离度量选择的实用建议
在实际项目中如何选择适合的距离度量？以下是一些经验法则：
数据维度：
- 低维数据（<10维）：欧氏距离通常表现良好
- 高维数据：曼哈顿距离或余弦相似度可能更合适（"维度诅咒"问题）
数据分布：
- 各向同性分布（各个方向方差相似）：欧氏距离
- 轴对齐分布或稀疏数据：曼哈顿距离
异常值处理：
- 数据中有显著异常值：曼哈顿距离更鲁棒
- 数据较干净：欧氏距离可提供更精确的相似度度量
计算效率：
- 曼哈顿距离计算通常更快，尤其在高维情况下
业务需求：
- 如果需要考虑实际路径（如城市导航），曼哈顿距离更合适
- 如果关注绝对差异（如物理测量），欧氏距离更合适
# 评估不同距离度量下的聚类效果 from sklearn.metrics import silhouette_score # 欧氏距离 euclidean_score = silhouette_score(X, y_pred_euclidean) print(f"欧氏距离轮廓系数: {euclidean_score:.3f}") # 曼哈顿距离 manhattan_score = silhouette_score(manhattan_dist, y_pred_manhattan, metric="precomputed") print(f"曼哈顿距离轮廓系数: {manhattan_score:.3f}")在最近的一个客户细分项目中，我们尝试了两种距离度量。原始数据包含用户的多维行为特征，使用欧氏距离时，聚类结果对少数极端用户非常敏感，导致质心偏移。改用曼哈顿距离后，聚类结果更加稳定，业务人员也反馈分群结果更符合他们的直觉。