マンハッタン距離

マンハッタン距離(マンハッタンきょり、Manhattan distance)またはL1-距離、タクシーの幾何、 直線距離 、 L 1距離 、 L 1距離、ノルム ( L p spaceを参照)、 スネーク距離 、 シティブロック距離は、幾何学における距離概念のひとつ。各座標の差(の絶対値)の総和を2点間の距離とする。

マンハッタン距離とユークリッド距離の比較:マンハッタン距離では、赤、黄、青のパスの最短パス長はすべて同じ12である。 ユークリッド幾何学では、緑の線は長さを持っているユニークな最短経路である。

ユークリッド幾何学における通常の距離ユークリッド距離)に代わり、この距離概念を用いた幾何学はタクシーの幾何 (taxicab geometry) と呼ばれる。19世紀ヘルマン・ミンコフスキーによって考案された。

通常の距離関数またはユークリッド幾何学メトリックが、2点間の距離デカルト座標絶対差の合計である新しいメトリックで置き換えられる幾何学の形式である。 。 [1] マンハッタン距離の名前は、 マンハッタン島のほとんどの道路のグリッドレイアウトを暗示している 。これにより、車が自治区内の2つの交差点間を移動できる最短距離は、タクシージオメトリの交差点の距離と同じになる。

ジオメトリは18世紀から回帰分析で使用されており、今日ではしばしばLASSOと呼ばれている。 幾何学的解釈は、19世紀の非ユークリッド幾何学にさかのぼり、 ヘルマンミンコフスキーによるものである。

正式な定義編集

タクシー距離、   、2つのベクトル間  デカルト座標系が固定されたn次元の実数 ベクトル空間では、 座標軸への点間の線分の投影の長さの合計である。 より正式には、

 

 ベクトルである。

 

たとえば、 飛行機では、タクシーの距離 そして である 

より形式的には、2点間の距離を直交する座標軸に沿って測定することで一般の   次元空間においてマンハッタン距離   が定義される。

 

ただし、 ,   とおいた。例えば、平面上において座標   に置かれた点   と、座標   に置かれた点   間のマンハッタン距離は

 

となる。

プロパティ編集

タクシー距離は、座標系の回転に依存するが、座標軸に関するその反射またはその並進には依存しない。 全てのマンハッタン距離を満たすヒルベルトの公理 (の定式化ユークリッド幾何学を除く) 側角側公理 、等しく「長い」両側と、それらの間に同じ角度を有する2つの三角形は、典型的ではないとして合同上記側面はに起こる場合を除き平行になる。

サークル編集

 
離散および連続したタクシージオメトリの円

は、 中心と呼ばれる点から、 半径と呼ばれる固定距離の点のセットである。 タクシージオメトリでは、距離はユークリッドジオメトリとは異なるメトリックによって決定され、円の形状も変化する。 タクシーの円は、座標軸に対して45度の角度で側面が向けられた正方形である。 右の図は、これが真実である理由を示している。青で示されている、中心からの距離が固定されたすべてのポイントのセットを赤で示している。 街区のサイズが小さくなると、ポイントはより多くなり、連続したタクシージオメトリで回転した正方形になる。 両側に長さがあるが  ユークリッド計量を使用する 。rは円の半径で、タクシージオメトリの長さは2 rである。 したがって、円の円周は8 rである。 したがって、幾何学的なアナログの値は このジオメトリでは4である。 タクシージオメトリの単位円の式は次のとおりである。   デカルト座標

 

半径1の円(この距離を使用)は、その中心のフォンノイマン近傍である。

以下のための半径rの円チェビシェフ距離L∞メトリック平面上の)はチェビシェフ距離を平面タクシー距離に回転及びスケーリングによって同等とみなすことができるので、平面、また座標軸に辺の長さ2 r個の並列の正方形である。 ただし、L 1L∞メトリックの間のこの等価性は、より高い次元に一般化されない。

これらの円のコレクションの各ペアに空でない交差がある場合は常に、コレクション全体の交差ポイントが存在する。したがって、マンハッタン距離は単射距離空間を形成する 。

用途編集

チェスの距離の測定編集

チェスでは、 ルークチェス盤上の正方形間の距離は、タクシー距離で測定される。 女王チェビシェフ距離を使用し、 司教は45度回転したチェス盤の(同じ色の正方形の間の)タクシー距離、つまり対角線を座標軸として使用する。 ある正方形から別の正方形に到達するには、キングのみがそれぞれの距離に等しい移動数を必要とする。ルーク、クイーン、ビショップは1つか2つの移動が必要である(空のボード上で、ビショップの場合はまったく移動が可能であると想定している)。

圧縮センシング編集

劣決定の線形方程式系を解く場合、パラメーターベクトルの正則化項は、   -ベクトルのノルム(タクシージオメトリ)。 [2] このアプローチは、 圧縮センシングと呼ばれる信号回復フレームワークに現れる。

頻度分布の違い編集

タクシージオメトリは、離散度数分布の違いを評価するために使用できる。 たとえば、 RNAスプライシングでは、スプライスサイトの近くの各特定のヌクレオチドに各ヘキサマーが出現する確率をプロットするヘキサマーの位置分布をL1距離と比較できる。 各位置分布は、各エントリが特定のヌクレオチドで始まる六量体の可能性を表すベクトルとして表すことができる。 2つのベクトル間のL1距離が大きい場合は、分布の性質に大きな違いがあることを示し、距離が小さい場合は、同様の形状の分布を示する。 これは、各セグメントの面積がそのポイントでの2つの曲線の尤度の絶対差であるため、2つの分布曲線間の面積を測定することと同じである。 すべてのセグメントについて合計すると、L1距離と同じ測定値を提供する。 [3]

編集

マンハッタン距離は、都市ブロック距離(city block distance, 市街地距離)としても知られている。マンハッタン距離の名は、マンハッタンのような正方形のブロックに区分された都市で、自動車が運転される距離に由来する。ある角から東に 3 ブロック、北に 6 ブロックの位置にある角まで移動するには、いかなる経路を辿っても最低 9 ブロックを通過せねばならない。

チェスでは、ルークにとってのマス間の距離はマンハッタン距離によって測られる(キングクイーンビショップチェビシェフ距離を用いる)。

歴史編集

L 1メトリックは、 Roger Joseph Boscovichによって1757年に回帰分析で使用されました。 [4] 幾何学的解釈は19世紀後半にまでさかのぼり、 非ユークリッド幾何学の発展、特にヘルマンミンコウスキーとそのミンコフスキーの不等式によるものである。この幾何学は、特に数の幾何学で使用される特別なケースである(Minkowski 1910) 。 L p空間の形式化は(Riesz 1910) である。

関連項目編集

ノート編集

  1. ^ Black. “Manhattan distance”. Dictionary of Algorithms and Data Structures. 2019年10月6日閲覧。
  2. ^ Donoho, David L. (March 23, 2006). “For most large underdetermined systems of linear equations the minimal  -norm solution is also the sparsest solution”. Communications on Pure and Applied Mathematics 59 (6): 797–829. doi:10.1002/cpa.20132. 
  3. ^ Lim, Kian Huat; Ferraris, Luciana; Filloux, Madeleine E.; Raphael, Benjamin J.; Fairbrother, William G. (July 5, 2011). “Using positional distribution to identify splicing elements and predict pre-mRNA processing defects in human genes”. Proceedings of the National Academy of Sciences of the United States of America 108 (27): 11093–11098. Bibcode2011PNAS..10811093H. doi:10.1073/pnas.1101135108. PMC: 3131313. PMID 21685335. https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3131313/. 
  4. ^ Stigler, Stephen M. (1986). The History of Statistics: The Measurement of Uncertainty before 1900. Harvard University Press. ISBN 9780674403406. https://archive.org/details/historyofstatist00stig 2019年10月6日閲覧。 

参考文献編集

外部リンク編集