マンハッタン距離とは？定義・性質・幾何・応用とL1/L2の違いを徹底解説
エバープレイ編集部マンハッタン距離とは
マンハッタン距離（マンハッタンきょり、Manhattan distance）は、ベクトル空間における2点間の距離の一種で、各座標ごとの差の絶対値を合計したものです。数学的にはL1ノルム（p=1のLpノルム）として表現され、別名「タクシー距離（taxicab distance）」「シティブロック距離（city-block distance）」とも呼ばれます。名前の由来は、マンハッタンの碁盤目状の道路網における移動距離にたとえられたことによります。
定義と式
n次元ユークリッド空間R^nにおいて、2点 x = (x1, x2, ..., xn) と y = (y1, y2, ..., yn) のマンハッタン距離 d1(x, y) は次で定義されます。
d1(x, y) = Σ_{i=1}^{n} |xi − yi|
2次元の例を挙げると、x = (1, 2)、y = (4, 6) のとき、マンハッタン距離は |1−4| + |2−6| = 3 + 4 = 7 になります。ユークリッド距離（通常の直線距離）は sqrt(3^2 + 4^2) = 5 であり、2つは異なる測度になります。
性質（メトリックとしての条件）
- 非負性: d1(x, y) ≥ 0 であり、等号は x = y のときのみ成立する。
- 対称性: d1(x, y) = d1(y, x)。
- 三角不等式: d1(x, z) ≤ d1(x, y) + d1(y, z)。これは各座標ごとの絶対値についての三角不等式 |xi − zi| ≤ |xi − yi| + |yi − zi| を合計することで容易に示せます。
したがってマンハッタン距離は数学的に正しい「距離（メトリック）」です。
幾何学的な見た目
2次元でマンハッタン距離が一定となる点の集合は、ユークリッド円とは異なり菱形（45度傾いた正方形）の形になります。これは「等距離集合」が軸方向の合計差で決まるためです。一般にL1の等高線は多面体的な形状を取り、L2（ユークリッド）は円、L∞は正方形（軸平行）になります。
応用例と実務での使いどころ
- 経路探索（グリッド上）: マンハッタン距離は碁盤状のグリッドで上下左右（4近傍）のみ移動を許す場合の最短距離を表します。A*アルゴリズムなどでヒューリスティックに使われます（ヒューリスティックは実際の移動コストを過小評価しないことが重要）。
- 機械学習: k-NN（k近傍法）やクラスタリングで距離指標として用いられます。特徴空間の特性によってL1が好まれることがあります（外れ値へのロバスト性、スパース性を生みやすい性質など）。
- 画像処理・コンピュータビジョン: ピクセルごとの差の総和として用いられる場面があります。例えば2つのバイナリベクトルのマンハッタン距離はハミング距離と一致します（各要素が0/1の場合）。
- 統計・最適化: 最小絶対偏差（L1誤差）に基づく回帰（ラッソ回帰や最小絶対偏差回帰）は係数のスパース化や外れ値へのロバスト性で知られています。
- データベース/インデックス: 高次元空間での近傍探索では距離計算のコストや探索構造の選択が問題になります。マンハッタン距離用の近似近傍探索法（例えばp-安定分布を用いたローカリティセンシティブハッシングなど）が存在します。
L1 と L2 の違い、選び方の指針
- 外れ値への感度: L2（ユークリッド）の場合、差分を二乗するため大きな差がより大きく影響します。L1は差の絶対値を合計するため大きな差の影響が相対的に小さく、外れ値に対してロバストです。
- スパース性: 最適化問題でL1正則化は係数をゼロにする性質があり、変数選択に有利です（Lasso）。
- 計算と実装: マンハッタン距離は計算上も単純で、座標ごとの差の絶対値を足すだけなので実装が容易で高速です。ただし次元数が増えると計算量はO(n)であるため大規模データでは工夫が必要です。
- 問題の幾何: 移動が格子上でかつ斜め移動が不可であればマンハッタン距離が自然な選択です。一方で直線距離が意味を持つ物理的距離の問題ならユークリッド距離を使います。
計算上の留意点と高次元での振る舞い
特徴量のスケーリングはマンハッタン距離にも重要です。特徴ごとにスケールが異なると、スケールの大きい特徴が距離を支配してしまいます。標準化（平均0、分散1）や正規化（最小最大スケーリング）を事前に行うのが通例です。
高次元空間では「次元の呪い（curse of dimensionality）」により距離の分布が集中しやすく、どの距離尺度を使っても近傍識別が難しくなることがあります。L1とL2のどちらが良いかはデータの分布次第ですが、スパースなデータやカテゴリカルに近い特徴を含む場合はL1が有利になることがあります。
アルゴリズム的な補足
- 索引構造: KD-tree や Ball-tree はL2を想定している場合が多いですが、L1でも基本的には利用可能です。ただし次元が高くなるとこれらの構造は効率が落ちます。
- 近似近傍探索: 大規模・高次元データではローカリティセンシティブハッシング（LSH）などの近似手法が使われます。L1距離に対しては1安定分布（コーシー分布など）を用いる手法が理論的に対応します。
- ヒューリスティック: A*アルゴリズムでマンハッタン距離をヒューリスティックに使うと、グリッド上での最短経路探索（4方向移動）に対して一貫でかつ許容的（admissible）なヒューリスティックを与えます。
実例：離散空間での応用（簡単なケース）
物流倉庫のピッキングルートやロボットの格子移動で、斜め移動ができない場合にマンハッタン距離は最短移動回数そのものを表します。例えば商品の棚が格子状に並ぶ環境で、ピッカーがある棚から別の棚へ移動するコストの推定に使いやすいです。
まとめ（選び方のチェックリスト）
- 移動が格子状で斜め不可 → マンハッタン距離を第一候補とする。
- 外れ値やスパース性を重視 → L1系（マンハッタン／L1ノルム）が有利。
- 物理的な直線距離や角度が重要 → L2（ユークリッド距離）を検討。
- 高次元で効率良く近傍探索が必要 → 近似手法（LSHなど）や次元削減を検討。
- バイナリデータ（0/1） → マンハッタン距離はハミング距離と同値。
参考文献
- ウィキペディア: マンハッタン距離（日本語）
- Wikipedia: Taxicab geometry (English)
- Wikipedia: Lp space (English)
- Wikipedia: A* search algorithm — Heuristics (Manhattan distance の利用例)
- Wikipedia: Lasso (statistics) — L1正則化に関する説明
- Wikipedia: Curse of dimensionality
- Wikipedia: Stable distribution — p-安定分布と近似近傍探索（LSH）に関する基礎
投稿者プロフィール
