今回はプログラミングにおける
距離の測り方をまとめてみました。

解説動画はこちら




さて今回はプログラミングなどで用いられる
距離の測り方についてです。

wikipediaでは
距離(きょり、distance)
ある2点間に対して測定した長さの量をいう
ということになっていますが
距離と言っても結構たくさんの距離が存在します。


今回扱う距離は次のようなものです。

1.数学的な距離
 ユークリッド距離
 マンハッタン距離
 チェビシェフ距離
 ミンコフスキー距離
 マハラノビス距離

2.文字列の類似度
 ハミング距離
 レーベンシュタイン距離
 ジャロ・ウィンクラー距離

3.数学/統計学/機械学習における類似度
 コサイン類似度
 ピアソンの相関係数

4.集合同士の類似度
 ジャッカード係数
 ダイス係数
 シンプソン係数



それでは一つ一つの距離の測り方を
見ていくこととしましょう。

Python言語では
scipy.spatial ライブラリの distanceを用いると
簡単に距離を求める事ができるようになっています。

始めにライブラリを読み込みしておきましょう。
from scipy.spatial import distance
import numpy as np

import matplotlib.pyplot as plt
%matplotlib inline




1.数学的な距離

・ユークリッド距離

まずはじめは一般的に距離と言うと
思い浮かばれるのかこれだと思います。

2次元では、2点間の直線距離のことで
各データの差の二乗の合計値のルート
が距離になります。

スクリーンショット 2022-04-02 17.27.59
直角三角形の斜辺を求めるやり方と一緒ですね。
図表を作図して2点を表示してみましょう。

import matplotlib.pyplot as plt
%matplotlib inline

plt.plot(0,0,marker='o',c='blue')
plt.plot(4,3,marker='o',c='red')
plt.plot([0,4],[0,3],linestyle='dashed',c='green')
plt.title('Euclid Distance')
plt.axis('square')
plt.xlim(-5,5)
plt.ylim(-5,5)
plt.show()
download-4

これがユークリッド距離になります。

これを求めるには次のコードで
求めることができます。
from scipy.spatial import distance

a = [0,0]
b = [4,3]

# ユークリッド距離を求める
euclid_distance = distance.euclidean(a, b)
print(euclid_distance)
5.0



3次元の場合は数値を増やすことで対応できます。
from scipy.spatial import distance

a = [0,0,0]
b = [1,1,1]

# ユークリッド距離を求める
euclid_distance = distance.euclidean(a, b)
print(euclid_distance)
1.7320508075688772



・マンハッタン距離

マンハッタンや京都のような
碁盤の目のような街を移動する時の距離です。

それぞれの次元の差の合計値ですね
スクリーンショット 2022-04-02 17.28.07

作図はこんな感じです。
import matplotlib.pyplot as plt
%matplotlib inline

plt.plot(0,0,marker='o',c='blue')
plt.plot(4,3,marker='o',c='red')
plt.plot([0,4],[0,0],linestyle='dashed',c='green')
plt.plot([4,4],[0,3],linestyle='dashed',c='green')
plt.title('Manhattan Distance')
plt.axis('square')
plt.xlim(-5,5)
plt.ylim(-5,5)
plt.show()
download-3

次のコードで距離を求めることができます。
import numpy as np

a = np.array([0, 0])
b = np.array([4, 3])

# マンハッタン距離を求める
manhattan_distance = np.linalg.norm(a - b , ord=1)
print(manhattan_distance)
7.0


次元が増えても対応できます。
import numpy as np

a = np.array([0, 0, 0])
b = np.array([4, 4, 4])

# マンハッタン距離を求める
manhattan_distance = np.linalg.norm(a - b , ord=1)
print(manhattan_distance)
12.0




・チェビシェフ距離

次元の差の絶対値の最大値のことで
座標次元ごとで求めた差の中で
一番大きいものになります。

スクリーンショット 2022-04-02 17.28.13

作図はこんな感じですが
マンハッタン距離と同じです。
import matplotlib.pyplot as plt
%matplotlib inline

plt.plot(0,0,marker='o',c='blue')
plt.plot(4,3,marker='o',c='red')
plt.plot([0,4],[0,0],linestyle='dashed',c='green')
plt.plot([4,4],[0,3],linestyle='dashed',c='green')
plt.title('Chebyshev Distance')
plt.axis('square')
plt.xlim(-5,5)
plt.ylim(-5,5)
plt.show()
download-2

距離は次のコードで求めることができます。
from scipy.spatial import distance

a = [0 , 0]
b = [4 , 3]

# チェビシェフ距離を求める
chebyshev_distance = distance.chebyshev(a , b)
print(chebyshev_distance)
4

次元が増えても対応できます。
from scipy.spatial import distance

a = np.array([0, 0, 0])
b = np.array([1, 2, 4])

# チェビシェフ距離を求める
chebyshev_distance = distance.chebyshev(a , b)
print(chebyshev_distance)
4


・ミンコフスキー距離

ユークリッド、マンハッタン、チェビシェフ距離を
一般化したようなもので、pによって取りうる値が変わります。

p=1にするとマンハッタン距離
p=2にするとユークリッド距
p=∞にするとチェビシェフ距離
になります。


コードはこんな感じです。
from scipy.spatial import distance

a = [0 , 0]
b = [4 , 3]

# ミンコフスキー距離を求める p=1
minkowski_distance = distance.minkowski(a,b,p=1)
print(minkowski_distance)

# ミンコフスキー距離を求める p=2
minkowski_distance = distance.minkowski(a,b,p=2)
print(minkowski_distance)

# ミンコフスキー距離を求める p=99
minkowski_distance = distance.minkowski(a,b,p=99)
print(minkowski_distance)

pの値を変えることで距離が変化します。



・マハラノビス距離

一般的にあまりなじみのない距離の名前かと思いますが
多変数間の相関関係を取り入れて
既知のサンプルとの関係を明らかにする距離です

データ群の平均や共分散行列を用いる方法で
異常検知などに使われるケースが多いようです。

サンプルデータを作図してみましょう。

# サンプルデータの可視化
import numpy as np
import matplotlib.pyplot as plt

x1 = np.array([(x, x + np.random.normal()) for x in np.arange(-5, 5, 0.1)])
x2 = np.array([(x, 12 + x + np.random.normal()) for x in np.arange(-10, 0, 0.1)])

plt.plot(x1[:,0], x1[:,1] , '.' , c='blue')
plt.plot(x2[:,0], x2[:,1] , '.' , c='orange')
plt.plot(0 , 0 , marker='o' , c='red',markersize=10)
plt.title('Mahalanobis Distance')
plt.axis('square')
plt.ylim(-20, 20)
plt.xlim(-20, 20)
plt.show()
download

青いデータが正常なもの
オレンジが異常データだと仮定します。

これにユークリッド距離で
等高線を描いてみましょう。
# ユークリッド距離で見てみる
import numpy as np
from scipy.spatial import distance
import matplotlib.pyplot as plt

# サンプルデータ作成
x1 = np.array([(x, x + np.random.normal()) for x in np.arange(-5, 5, 0.1)])
x2 = np.array([(x, 12 + x + np.random.normal()) for x in np.arange(-10, 0, 0.1)])

# ユークリッド距離を計算する
m = x1[:,0].mean(), x1[:,1].mean()
y = np.linspace(-20, 20, 100)
z = np.array([[(i, j, distance.euclidean([i, j], m)) for i in y] for j in y])

# 等高線を表示する
z1,z2,z3 = z.transpose()[0],z.transpose()[1], z.transpose()[2]
cont = plt.contour(z1,z2,z3, levels=[5,10,15], colors=['k'])
cont.clabel(fmt=' d=%1s', fontsize=12)

plt.plot(x1[:,0], x1[:,1] , '.' , c='blue')
plt.plot(x2[:,0], x2[:,1] , '.' , c='orange')
plt.plot(0 , 0 , marker='o' , c='red',markersize=10)
plt.title('Mahalanobis Distance')
plt.axis('square')
plt.ylim(-20, 20)
plt.xlim(-20, 20)
plt.show()
download-1

正常な青いデータを囲もうとすると
ユークリッド距離だとなかなかうまくいきません。

今度は青いデータを用いて
マハラビノス距離を考えてみましょう。

次のコードは簡単なデータでの
マハラビノス距離の計算です。
import numpy as np
from scipy.spatial import distance

# サンプルを用意
x = np.array([[0, 0], [1, 1], [2, 2]])

# サンプルの分散共分散行列の逆行列を計算する
vcm = np.linalg.pinv(np.cov(x.T))

#  [0 , 0]と[3 , 3]のマハラノビス距離を計算する
mahalanobis_distance = distance.mahalanobis([0, 0] , [3, 3], vcm)
print(mahalanobis_distance)
2.9999999999999996

マハラビノス距離は2点のデータと
分散共分散行列のデータが必要になります。


先ほどのサンプルデータに
マハラビノス距離で等高線を描いてみましょう。

# マハラノビス距離で見てみる
import numpy as np
from scipy.spatial import distance
import matplotlib.pyplot as plt

# サンプルデータ作成
x1 = np.array([(x, x + np.random.normal()) for x in np.arange(-5, 5, 0.1)])
x2 = np.array([(x, 12 + x + np.random.normal()) for x in np.arange(-10, 0, 0.1)])

# マハラノビス距離を計算する
m = x1[:,0].mean(), x1[:,1].mean()
vcm = np.linalg.pinv(np.cov(x1.T))
y = np.linspace(-20, 20, 100)
z = np.array([[(i, j, distance.mahalanobis([i, j], m,vcm)) for i in y] for j in y])

# 等高線を表示する
z1,z2,z3 = z.transpose()[0],z.transpose()[1], z.transpose()[2]
cont = plt.contour(z1,z2,z3, levels=[5,10,15], colors=['k'])
cont.clabel(fmt=' d=%1s', fontsize=12)

plt.plot(x1[:,0], x1[:,1] , '.' , c='blue')
plt.plot(x2[:,0], x2[:,1] , '.' , c='orange')
plt.plot(0 , 0 , marker='o' , c='red',markersize=10)
plt.title('Mahalanobis Distance')
plt.axis('square')
plt.ylim(-20, 20)
plt.xlim(-20, 20)
plt.show()
download-1

今度は青いデータとオレンジのデータを
マハラビノス距離でうまく分離することができます。

こんな感じで距離を計算すれば
異常検知などに使えますね。



2.文字列の類似度

・ハミング距離

同じ文字数の二つの文字列を比較したとき
同じ位置にある異なる文字の個数になります。

二つの文字列を同じくするために
必要な文字の置換の回数(0回 - MAXは文字数分)

ABCDE と ABDFC なら3回(割合は0.6)
割合のMAXは1.0になります。
from scipy.spatial import distance

# 文字列をリストとして格納
s1 = list('abcde')
s2 = list('abdfc')

# ハミング距離を計算する(同じ長さであること)
hamming_distance = distance.hamming(s1,s2)
print(hamming_distance)

hamming_num = hamming_distance * len(s1)
print(hamming_num)
0.6
3.0



・レーベンシュタイン距離

二つの文字列がどの程度異なっているかを示す
距離の一種です。

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

編集距離とも呼ばれ、文字列の類似度が分かります。


例:kitten と sitting
sitten(「k」を「s」に置換)
sittin(「e」を「i」に置換)
sitting(「g」を挿入して終了)

3回の手順が必要なので
レーベンシュタイン距離は3

Pythonでは専用のライブラリが有るので
インストールしておきましょう。
!pip install python-Levenshtein

距離の計算は次のようになります。
import Levenshtein

s1 = 'abcde'
s2 = 'abdfcee'

# レーベンシュタイン距離を算出する
levenshtein_distance = Levenshtein.distance(s1, s2)
print(levenshtein_distance)
3



・ジャロ・ウィンクラー距離

ある文字列と別の文字列で一致する文字数と
置換の要不要から計算する距離になります。

距離の取りうる値が0~1で
距離の数値が大きいほど
文字列間の類似度が高くなります。


import Levenshtein

s1 = 'abcde'
s2 = 'abdfc'

# ジャロ・ウィンクラー距離を算出する
jaro_winkler_distance = Levenshtein.jaro_winkler(s1, s2)
print(jaro_winkler_distance)
0.8266666666666667

これらの距離を使い分けることで
単語の類似度などに
応用することができます。



3.数学/統計学/機械学習における類似度

・コサイン類似度

2つのベクトルが「どのくらい似ているか」という
類似性を表す尺度のことで
2つのベクトルがなす角のコサイン値になります。

1なら完全に似ている
0なら無関係
-1なら完全に似ていない
ということになります。

作図するとこんな感じです。
import matplotlib.pyplot as plt
from matplotlib import patches

# 2つのベクトルを指定
a = np.array([5.0, 5.0])
b = np.array([3.0, 9.0])

# 作図
fig, ax = plt.subplots()
plt.quiver(0, 0, a[0], a[1], angles='xy', scale_units='xy', scale=1, color='c', label='a')
plt.quiver(0, 0, b[0], b[1], angles='xy', scale_units='xy', scale=1, color='orange', label='b')
c = patches.Arc(xy=(0.9, 1.5), width=0.5, height=0.3, angle=-60, 
                theta1=0, theta2=180, linewidth=3, color="r")
ax.add_patch(c)
plt.title('Cosine Similarity')
plt.axis('square')
plt.xlim(-2,10)
plt.ylim(-2,10)
plt.legend()
plt.grid()
plt.show()
download

計算は次のコードでできます。
from scipy.spatial import distance

a = [2, 48, 9, 11]
b = [3, 51, 13, 19]

cosine_dos = 1 - distance.cosine(a , b)
print(cosine_dos)
0.9902460327205821

真逆の方向を向くベクトルで計算してみましょう。
from scipy.spatial import distance

a = [1 , 1]
b = [-1 , -1]

cosine_dos = 1 - distance.cosine(a , b)
print(cosine_dos)
-1.0




・ピアソンの相関係数

2つの変数間の関係の強さと方向性を表す
-1 ~ 1の範囲の数値になります。

1(強い正の相関)では、2つの変数が強く同方向に連動
-1(強い負の相関)では強く逆方向に連動

データ群を用意して計算してみましょう。
from scipy.spatial import distance

a = [2,3,4,5]
b = [2,3,5,6]

correlation_coefficient =  1 - distance.correlation(a , b)
print(correlation_coefficient)
0.9899494936611665

from scipy.spatial import distance

a = [2,3,4,5]
b = [5,4,3,1]

correlation_coefficient =  1 - distance.correlation(a , b)
print(correlation_coefficient)
-0.9827076298239907

相関係数は様々なライブラリで
求めることができるので
好きな方法を使うのが良いと思います。



4.集合同士の類似度

・ジャッカード係数

集合の類似度を表す指標でテキストマイニングでは
文章と文章の類似度=距離を表す指標になります。

2つの集合に含まれている要素のうち
共通要素が占める割合です。

0から1の間の値となり値が大きいほど
2つの集合の類似度は高い(似ている)ことになります。
スクリーンショット 2022-04-02 18.03.38

集合の計算方法で係数を求めることができます。

import numpy as np

# ジャッカード係数を算出する
def jaccard_coefficient(x,y):
    # 積集合を求める
    intersection = len(set.intersection(set(x), set(y)))    
    # 和集合を求める
    union = len(set.union(set(x), set(y)))                
    return intersection / union

a = np.array([1, 2, 3, 5])
b = np.array([1, 2, 3, 4, 6])

jaccard_index = jaccard_coefficient(a,b)
print(jaccard_index)
0.5



・ダイス係数

2つの集合の平均要素数と
共通要素数での割合になります。

スクリーンショット 2022-04-02 18.03.43


import numpy as np

# ダイス係数を算出する
def dice_coefficient(x,y):
    num = len(set.intersection(set(x), set(y)))
    if num!=0:
        return (2.0 * num) / (len(x) + len(y))
    else:
        return 0.0
    
a = np.array([1, 2, 3, 5])
b = np.array([1, 2, 3, 4, 6])

dice_index = dice_coefficient(a,b)
print(dice_index)
0.6666666666666666


・シンプソン係数

ダイス係数の定義式の分母を「2集合の平均要素数」から
「少ない方の要素数」にしたものです。

ダイス係数よりも差集合の要素数による影響を下げ
相対的に共通要素数を重視した類似度計算です。


スクリーンショット 2022-04-02 18.03.48

# Simpson係数
def simpson_coefficient(x,y):
    num = len(set.intersection(set(x), set(y)))
    if num!=0:
        return num / min([len(x),len(y)])
    else:
        return 0.0

a = np.array([1, 2, 3, 5])
b = np.array([1, 2, 3, 4, 6])

simpson_index = simpson_coefficient(a,b)
print(simpson_index)
0.75

集合の一部が共通要素の場合は
Jaccard係数 < Dice係数 < Simpson係数となります。

これらの係数は
 文書同士の類似度計算
 トピック同士の関連推定
 文字列同士の共起推定
など類似性や距離を測るのに用いられます。



まとめ

プログラミングでは文字列や集合
ベクトルの類似度など
距離を測るのにたくさんの方法があるので
目的に応じて使い分けられるようになると
すごく捗るでしょう。

今回はこれまでです
それでは。