webエンジニアの知らない’距離’の世界

この記事はニフティグループ Advent Calendar 2018の2/19日の記事です。
昨日はikaimanさんのVaporでセッションを利用した認証をつくる
でした。

何を書くか

距離についてまとめておこうと思います。
知らない人からすると何を言っているのか思われそうですが、実はこの世にはたくさんの距離尺度が存在します。

そもそも距離って何？

コトバンクによると「空間的な離れ方の大きさ」ですとか「へだたり」という風に書かれています。
まさにそのとおりで、学校でもその様に習うはずです。

ところで「離れ方の大きさ」が距離というのはすんなり理解できると思うのですが、「空間的な」というのはどういうことでしょう。
実は中高の数学で習う「距離」の「空間」とは何かと言うと、ユークリッド空間、あるいは幾何平面と呼ばれる空間を示しています。
なので、我々が普段使っている「距離」というのはユークリッド距離であり、「ユークリッド平面に存在する離れ方の大きさ」を表すのです。

そのため、ユークリッド空間以外の空間上での隔たりはいわゆるユークリッド距離では表せられませんし、
隔たりの大きさも定義の仕方によっては同じユークリッド空間上でもユークリッド距離以外の距離が存在します。

なぜ書くか

距離についてどんな距離があってどんなときに使われるのかまとまってるページが見つからなかったからです。

最近機械学習や統計を少し勉強しています。その中で距離の概念が非常に重要です。
実は学生時代にベクトルの高速検索アルゴリズムについて研究してたためそれらも勉強していたこともあり
懐かしい気持ちになったのでついでに調べてまとめておいたら何かの役に立つかと思いました。
自分なりのまとめになるので、間違っていたら指摘してください。

どんな距離があるか

ユークリッド距離 / L2norm

ユークリッド距離は誰もが習う二点間の距離です。
二次元空間の点の場合数式で表すと

\sqrt{x^2+y^2} 

となります。これはユークリッド空間上での最短直線距離がどのくらいか、という距離です。

マンハッタン距離 / L1norm

ユークリッド空間に定義された、ユークリッド距離とは別の距離尺度です。
こちらの式は以下となります。

|x|+|y|

これは何かと言うと座標の絶対値和を取ります。
ユークリッド空間を斜めに移動することができないとき、どれくらいの距離になるか、という風に考えると想像しやすいです。

ミンコフスキー距離

ユークリッド距離とマンハッタン距離ってすごく似ていると思いませんか？
これらを一般化したのがミンコフスキー距離です。

ユークリッド距離は2乗和を1/2乗したものです。
マンハッタン距離は1乗和を1/1乗したものです。

ミンコフスキー距離はつまり、各座標のp乗和を1/p乗したものとして定義されています。

こちらのサイトによれば
ミンコフスキー距離では、p が大きいほど「差が大きい成分を重視して、差が小さい成分は無視する」
傾向があるみたいです。

チェビシェフ距離

ミンコフスキー距離によって定義された、pが無限大のときの距離です。
これは差分の最も大きな成分だけを見る距離です。ユークリッド空間上の点で考えると

max (|x| |y|)

となります。

3つの距離の使い分け

上記引用のサイトから更に引用になりますが
・p=1 のマンハッタン距離は「どの成分も平等に見る」
・p=∞ のチェビシェフ距離は「差が一番大きい成分以外は完全無視する」
・p=2 のユークリッド距離はその中間くらい

というときに使うみたいです。

マハラノビス距離

定義をwikipediaから拝借すると以下です。

多変数間の相関に基づくものであり、多変量解析に用いられる。
新たな標本につき、類似性によって既知の標本との関係を明らかにするのに有用である。
データの相関を考慮し、また尺度水準によらないという点で、ユークリッド空間で定義される普通のユークリッド距離とは異なる。

標本点が複数あるときに、平均からの距離を分散に基づいて計測する距離で、主に異常検知などに使われるみたいです。
ユークリッド空間でイメージすると、例えば標本点が

(0, n), (0, -n)

で定義される複数の自然数nで構成された場合、y軸上に正負均等な集合になり、その平均の座標は
(0,0)
のはずです。
また、この集合の分散を計算するとy軸方向は非常に大きくなり、x軸の分散は０になることが想像できます。

このとき、ある点とこの集合のマハラノビス距離を計算した場合、y軸方向のユークリッド距離はどれだけ大きくてもマハラノビス距離に大きな影響はありませんが、x軸方向のユークリッド距離が大きくなればマハラノビス距離は大きくなります。

そのため、基準となる集合からどれだけ逸脱しているかがわかるみたいです。

ハミング距離

ここまでは座標を定義できる空間上での距離の話でしたがハミング距離は2つの単語や文章での距離を計算する距離の一つです。
詳細はwikipediaに譲りますが、かいつまんで説明します。
1001 と 1011
について距離（＝差分）を計算します。
もし、2進数とみなして距離を計算すると答えは10、10進数とみなしたときも10で、10進変換すると2ですね。
ここでハミング距離の定義をwikiから引用すると

等しい文字数を持つ二つの文字列の中で、対応する位置にある異なった文字の個数である。
別の言い方をすれば、ハミング距離は、ある文字列を別の文字列に変形する際に必要な置換回数を計測したものである。

ハミング距離はこの2つの文字列で差分がある項目数をとります。ですからここでは答えは1となります。
また、"toned" と "roses" の間のハミング距離は 3 となります。

レーベンシュタイン距離

ハミング距離は同じ文字数じゃないと比較できないという問題がありました。レーベンシュタイン距離はハミング距離をより洗練させたものです。
wikipediaから定義を引用します。

1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数

これによって文字数の違う2つの単語間でも文字の挿入、削除という手順をふむことで文字数の違いを吸収できるようになりました。

終わりに

多分自分が知らないだけで他にも距離はたくさんあると思うんですが、自分の知っている範囲ではこのくらいです。
一般化して理解することで超平面上での対応ができるようになったり、分散を考慮し空間を歪めることで重要な差分を見逃さないようにするなど
改めて調べると先達の工夫が見て取れて非常に興味深かったです。

さて、次回はmegmismさんがhackday2018で作ったものでも書こうかととのことです。お楽しみに！