距離を求めるプログラムを書こう（１）
こんにちは。前回は距離の考え方がいろいろあるということを確認しました。今回は、それらをプログラムで書いてみようというテーマです。
ミンコフスキー距離
プログラムを紹介する前に、ミンコフスキー距離について説明します。前回取り上げた距離のうち、ユークリッド距離・マンハッタン距離・チェビシェフ距離は一般化すると、ミンコフスキー距離という一つの距離にまとめることができます。ミンコフスキー距離は次の式で定義されます。
２つの\(n\)次元ベクトル\( \boldsymbol{ X } = ( x_1, x_2, \ldots, x_n ) \)，\( \boldsymbol{ Y } = ( y_1, y_2, \ldots, y_n ) \)に対して、
\[ d_{xy} = \left( \displaystyle \sum_{ i = 1 }^{ n } \vert x_i – y_i \vert^p \right)^\frac{1}{p} \]
と定義されます。
ここで、\(p=1\)の場合について、\(\sum\)記号を使わないで書くと
\[ d_{xy} = \displaystyle \sum_{ i = 1 }^{ n } \vert x_i – y_i \vert = \vert x_1 – y_1 \vert + \vert x_2 – y_2 \vert + \cdots +\vert x_n – y_n \vert \]
となって、マンハッタン距離になります。
次に、\(p=2\)の場合について、\(\sum\)記号を使わないで書くと
\[ d_{xy} = \left( \displaystyle \sum_{ i = 1 }^{ n } \vert x_i – y_i \vert^2 \right)^\frac{1}{2} = \sqrt{ \vert x_1 – y_1 \vert^2 + \vert x_2 – y_2 \vert^2 + \cdots +\vert x_n – y_n \vert^2 } \]
となって、ユークリッド距離になります。
なお、\(p=\infty\)とするとチェビシェフ距離になるそうです。
ユークリッド距離を求めるプログラム
scipyという有名なライブラリを使ってしまいましょう。
pip install scipyそうすると次のようなプログラムでユークリッド距離を求めることができます。上に書いたようにユークリッド距離は、ミンコフスキー距離で\(p=2\)の場合なので、第３引数に２をを入れています。第３引数を省略した場合のデフォルトも2になっています。
from scipy.spatial.distance import minkowski
a = [ 5, 9, 6, 3 ] #ごくろうさん
b = [ 4, 6, 4, 9 ] #よろしく
c = [ 1, 1, 2, 9 ] #いい肉
print( minkowski( a, b, 2 ) )
print( minkowski( b, c, 2 ) )
print( minkowski( c, a, 2 ) )
実行結果は次のとおりです。
7.0710678118654755
6.164414002968976
11.489125293076057
マンハッタン距離を求めるプログラム
これもscipyを使います。上に書いたようにマンハッタン距離は、ミンコフスキー距離で\(p=1\)の場合なので、第３引数に1をを入れています。
from scipy.spatial.distance import minkowski
a = [ 5, 9, 6, 3 ] #ごくろうさん
b = [ 4, 6, 4, 9 ] #よろしく
c = [ 1, 1, 2, 9 ] #いい肉
print( minkowski( a, b, 1 ) )
print( minkowski( b, c, 1 ) )
print( minkowski( c, a, 1 ) )
実行結果は次のとおりです。
12.0
10.0
22.0
チェビシェフ距離を求めるプログラム
これもscipyを使います。1行目のimport以降がユークリッド距離・マンハッタン距離の場合と異なっているので気をつけてください。ちなみにミンコフスキー距離で\(p=\infty\)の場合になります。
from scipy.spatial.distance import chebyshev
a = [ 5, 9, 6, 3 ] #ごくろうさん
b = [ 4, 6, 4, 9 ] #よろしく
c = [ 1, 1, 2, 9 ] #いい肉
print( chebyshev( a, b ) )
print( chebyshev( b, c ) )
print( chebyshev( c, a ) )
実行結果は次のとおりです。
6
5
8
レーベンシュタイン距離を求めるプログラム
python-Levenshteinというライブラリを使ってしまいましょう。
pip install python-Levenshteinそうすると
from Levenshtein import distance
a = "ぐんま"
b = "とちぎ"
c = "いばらき"
d = "とうきょう"
print( distance( a, d ) )
print( distance( b, d ) )
print( distance( c, d ) )
実行結果は次のとおりです。
5
4
5
単なる例です。他意はありません。
ジャッカード距離・ジャッカード係数を求めるプログラム
自然言語処理でよく使われているというnltkというライブラリを使ってしまいましょう。
pip install nltkそうすると次のようなプログラムでジャッカード距離を求めることができます。なお、ジャッカード距離＋ジャッカード係数＝１になる関係を使えば、ジャッカード係数も求められます。
from nltk.metrics import jaccard_distance
sato = { "高橋", "田中", "伊藤", "渡辺" }
suzuki = { "高橋", "田中", "伊藤", "山本" }
print( jaccard_distance( sato, suzuki ) )
print( 1 - jaccard_distance( sato, suzuki ) )
実行結果は次のとおりです。
0.4
0.6
ハミング距離を求めるプログラム
jellyfishというライブラリを使ってしまいましょう。
pip install jellyfishそうすると次のようなプログラムでハミング距離を求めることができます。
from jellyfish import hamming_distance
a = '5963' #ごくろうさん
b = '4949' #よろしく
c = '1129' #いい肉
print( hamming_distance( a, b ) )
print( hamming_distance( b, c ) )
print( hamming_distance( c, a ) )
実行結果は次のとおりです。
3
3
4
コサイン類似度を求めるプログラム
これもscipyを使います。1行目のimport以降がcosineになっているので気をつけてください。
from scipy.spatial.distance import cosine
a = [ 5, 9, 6, 3 ] #ごくろうさん
b = [ 4, 6, 4, 9 ] #よろしく
c = [ 1, 1, 2, 9 ] #いい肉
print( 1 - cosine( a, b ) )
print( 1 - cosine( b, c ) )
print( 1 - cosine( c, a ) )
実行結果は次のとおりです。
0.8333518524691587
0.8695257228184263
0.46241058789809175
よろしく・いい肉の類似度が高く、いい肉・ごくろうさんの類似度は低いようです。（語呂合わせの数字での類似度ですが・・・）また、ここで求まった値はコサイン(cos)の値です。高校数学の定番、サイン・コサイン・タンジェントのコサインです。角度に相当するものを求めたければアークコサインを使いましょう。
from scipy.spatial.distance import cosine
import math
a = [ 5, 9, 6, 3 ] #ごくろうさん
b = [ 4, 6, 4, 9 ] #よろしく
theta = math.acos( 1 - cosine( a, b ) )
print( math.degrees(theta) )
変数thetaは弧度法での角度です。printする際に度数法に変換しています。実行結果は次のとおりです。
33.55539016862236
ごくろうさん・よろしくのなす角は約33.6°です。そこそこ同じ方向性でしょうか。
まとめ
全部「ライブラリをインポートして求めているんじゃないか！」って批判があると思います。ライブラリをインポートしてしまえば、距離や類似度のように簡単に実装できてしまいます。今回、ライブラリを使うだけのプログラムを書いたのは、今後機械学習などを学ぶ際のポイントを整理したいという思いがあります。Pythonで機械学習を簡単にできるといわれており、本当に実装のハードルは低くなっていると思います。
ここでの主張は、概念がわからないまま実装を進めても、実装したものの精度を評価したり改善したりしたときに行き詰まってしまうので、機械学習をやってみようと思ったときには、ちゃんと概念を理解しておくことが重要になると考えていることです。
とはいえ、さすがに距離のプログラムを紹介する内容というには手抜き過ぎるような気がするので、数式に従ってちゃんと実装してみようと思います。それではまた。