【漫话机器学习系列】115.曼哈顿距离（Manhattan Distance）

曼哈顿距离（Manhattan Distance）详解

1. 引言

在数据科学、机器学习和计算几何中，距离度量（Distance Metric） 是一个核心概念。距离度量帮助我们衡量点与点之间的相似性、分类数据、进行聚类分析等。其中，曼哈顿距离（Manhattan Distance） 是一种常见的距离度量方式，尤其适用于网格状结构（如城市街区或棋盘上的路径规划）。

本文将详细介绍曼哈顿距离的定义、数学公式、计算示例、应用场景以及与欧几里得距离的对比分析。

2. 曼哈顿距离的定义

曼哈顿距离，也称为 L1 距离（L1 Distance） 或 城市街区距离（City Block Distance），用于计算仅允许沿水平和垂直方向移动的两个点之间的距离。

该名称来源于美国纽约市曼哈顿区的街道布局：曼哈顿的街道呈网格状，行人和车辆只能沿着南北（纵向）或东西（横向）行走，而不能直接对角线行进。因此，在这个街区内，两个点之间的实际行走距离是沿水平和垂直方向的总步数，而不是欧几里得直线距离。

3. 数学公式

假设在 n 维空间中，点 $P = (p_1, p_2, ..., p_n)$ 和点 $Q = (q_1, q_2, ..., q_n)$ 之间的曼哈顿距离定义如下：

$d_{\text{Manhattan}}(P, Q) = \sum_{i=1}^{n} | p_i - q_i |$

其中：

P 和 Q 是两个 n 维向量（即 n 维坐标点）。
$| p_i - q_i |$ 表示第 i 个维度上两个点的绝对差值。
结果是两个点在各个维度上的坐标差值之和。

该公式的核心思想是：从点 P 到点 Q 的距离等于在每个维度上相差的绝对值的总和，类似于在网格地图上只能沿着横纵方向移动的步数。

4. 计算示例

示例 1：二维平面

假设我们有两个点：

P(1,2)
Q(4,5)

使用曼哈顿距离计算：

$d_{\text{Manhattan}}(P, Q) = |1 - 4| + |2 - 5|= 3 + 3 = 6$

解释：

从 (1,2) 到 (4,2) 需要水平移动 3 步。
从 (4,2) 到 (4,5) 需要垂直移动 3 步。
总步数 = 3 + 3 = 6。

示例 2：三维空间

设 P(2, 3, 5) 和 Q(6, 1, 8)，则：

$d_{\text{Manhattan}}(P, Q) = |2 - 6| + |3 - 1| + |5 - 8|= 4 + 2 + 3 = 9$

解释：

在 x 轴方向移动 4。
在 y 轴方向移动 2。
在 z 轴方向移动 3。
总步数 = 4 + 2 + 3 = 9。

5. 曼哈顿距离的应用

5.1 机器学习中的应用

特征空间中的相似度计算：
- 在 KNN（K-近邻）算法、K-Means 聚类等方法中，曼哈顿距离可用于衡量数据点之间的相似性，尤其是在高维稀疏数据中表现良好。
正则化技术：
- L1 正则化（Lasso 回归）使用曼哈顿距离来限制模型的参数，使得部分参数变为零，实现特征选择。

5.2 计算机视觉

图像处理：
- 在像素网格中，曼哈顿距离可用于测量像素间的距离，适用于某些模式识别算法。
路径规划：
- 在 A* 算法和 Dijkstra 算法中，曼哈顿距离用于计算网格地图上的启发式路径估计。

5.3 计算几何

在计算凸包、最短路径、最近邻搜索等问题中，曼哈顿距离是常见的度量方式之一。

5.4 机器人与游戏开发

机器人在网格地图上导航时，通常使用曼哈顿距离来计算移动步数。
游戏 AI 需要计算角色在离散网格上的最短路径，例如迷宫游戏中的路径规划。

6. 曼哈顿距离 vs 欧几里得距离

对比项	曼哈顿距离（L1 距离）	欧几里得距离（L2 距离）
定义	只能沿水平或垂直方向移动的总步数	直线距离（最短路径）
公式	$\sum_{i=1}^{n} \| p_i - q_i \|$	$\sqrt{\sum_{i=1}^{n} (p_i - q_i)^2}$
移动方式	只能水平或垂直	任意方向（包括对角线）
适用场景	离散网格、城市交通、L1 正则化	连续空间、物理运动、L2 正则化
计算复杂度	计算简单，适合高维稀疏数据	计算稍复杂，适合低维密集数据
特性	对离群点更鲁棒	对离群点更敏感