データの距離尺度 -マンハッタン距離の紹介-

2点間のデータの距離を測る尺度として、マンハッタン距離(市街地距離,$L1-$距離)があります。

以下にマンハッタン距離の計算方法を紹介し、著名な距離尺度であるユークリッド距離との違いや、マンハッタン距離を計算するMATLABのコードを紹介します。

マンハッタン距離の計算方法

ユークリッド距離と異なる2点間の距離尺度として著名なのがマンハッタン距離(Manhattan distance)です。マンハッタン距離は$L1-$距離や市街地距離(City-block distance)と呼ばれることもあります。

$N$次元ベクトル$\mathbf{x}={x_i}$と$\mathbf{y}={y_i}$のマンハッタン距離$D_c$は以下の式で表されます。

$$D_c(\mathbf{x},\mathbf{y})=\sum_{i=1}^{N}|x_i-y_i|$$

例えば2次元の2点$A(1,2)$と$B(4,6)$のマンハッタン距離は,$|4-1|+|6-2|=7$となります。

また、例えば3次元の2点$C(1,2,3)$と$D(4,6,8)$のマンハッタン距離は,$|4-1|+|6-2|+|8-3|=12$と計算されます。

このようにマンハッタン距離は,距離計算を行う対象の2サンプルのみの情報から計算されます。

ユークリッド距離とマンハッタン距離の違い

よく使われる著名な距離尺度として「ユークリッド距離」があります。ユークリッド距離の計算法については以下の記事にまとめていますので、知りたい方は是非参照してください。

2点間のデータの距離を測る尺度として、最も著名と思われるものにユークリッド距離があります。 以下にユークリッド距離の計算方法を紹介し...

ここでは図を使って、シンプルにユークリッド距離とマンハッタン距離の違いを示します。

以下の図は、2点$A(1,2)$と$B(4,6)$の距離を図示しています。

このときに赤線の長さがユークリッド距離を表しており、これは2点の直線距離を示します。

一方、青線の長さの総和がマンハッタン距離を示しており、これは例えば網目上に道路が張り巡らされた都市(斜めに進める道路は存在せず、縦横のみに移動できる)で、ある場所からある場所に移動する場合の距離を示します。

マンハッタン距離を計算するソースコード(MATLAB)

以下のMATLABのコードで、上記の点Aと点B及び点Cと点Dのマンハッタン距離(を計算することができます。

計算部分は「Dist1_Cityblock = pdist2(A,B,’cityblock’);」の箇所のみです。

ユークリッド距離も計算し、ユークリッド距離の計算結果も同時に出力します。

A = [1,2]; B = [4,6];
C = [1,2,3]; D = [4,6,8];
Dist1_Euclidean = pdist2(A,B,'euclidean');
Dist2_Euclidean = pdist2(C,D,'euclidean');
Dist1_Cityblock = pdist2(A,B,'cityblock');
Dist2_Cityblock = pdist2(C,D,'cityblock');
fprintf('Distance between A and B, Euclidean: %f, Cityblock: %f\n' ,Dist1_Euclidean, Dist1_Cityblock);
fprintf('Distance between C and D, Euclidean: %f, Cityblock: %f\n' ,Dist2_Euclidean, Dist2_Cityblock);
plot([A(1) B(1)],[A(2) A(2)],'-ob','MarkerSize',1, 'MarkerFaceColor','red')
hold on
plot([B(1) B(1)],[A(2) B(2)],'-ob','MarkerSize',1, 'MarkerFaceColor','red')
plot([A(1) B(1)],[A(2) B(2)],'-or','MarkerSize',10, 'MarkerFaceColor','red')
hold off
xlim([0 10])
ylim([0 10])

実行結果は以下の通りです。

スポンサーリンク

シェアする

フォローする