今回はプログラミングにおける
距離の測り方をまとめてみました。
解説動画はこちら
さて今回はプログラミングなどで用いられる
距離の測り方についてです。
wikipediaでは
今回扱う距離は次のようなものです。
2.文字列の類似度
3.数学/統計学/機械学習における類似度
4.集合同士の類似度
それでは一つ一つの距離の測り方を
見ていくこととしましょう。
・ユークリッド距離
まずはじめは一般的に距離と言うと
思い浮かばれるのかこれだと思います。
2次元では、2点間の直線距離のことで
各データの差の二乗の合計値のルート
が距離になります。
直角三角形の斜辺を求めるやり方と一緒ですね。
図表を作図して2点を表示してみましょう。
これがユークリッド距離になります。
これを求めるには次のコードで
求めることができます。
3次元の場合は数値を増やすことで対応できます。
一般的にあまりなじみのない距離の名前かと思いますが
2.文字列の類似度
・ハミング距離
・レーベンシュタイン距離
1文字の挿入・削除・置換によって
一方の文字列をもう一方の文字列に変形するのに
必要な手順の最小回数になります。
編集距離とも呼ばれ、文字列の類似度が分かります。
例:kitten と sitting
3回の手順が必要なので
レーベンシュタイン距離は3
距離の計算は次のようになります。
・ジャロ・ウィンクラー距離
これらの距離を使い分けることで
単語の類似度などに
応用することができます。
3.数学/統計学/機械学習における類似度
・コサイン類似度
作図するとこんな感じです。
計算は次のコードでできます。
真逆の方向を向くベクトルで計算してみましょう。
・ピアソンの相関係数
相関係数は様々なライブラリで
求めることができるので
好きな方法を使うのが良いと思います。
4.集合同士の類似度
・ジャッカード係数
・ダイス係数
2つの集合の平均要素数と
共通要素数での割合になります。
・シンプソン係数
これらの係数は
距離の測り方をまとめてみました。
解説動画はこちら
さて今回はプログラミングなどで用いられる
距離の測り方についてです。
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点間の直線距離のことで
各データの差の二乗の合計値のルート
が距離になります。
直角三角形の斜辺を求めるやり方と一緒ですね。
図表を作図して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()
これがユークリッド距離になります。
これを求めるには次のコードで
求めることができます。
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
・マンハッタン距離
マンハッタンや京都のような
碁盤の目のような街を移動する時の距離です。
それぞれの次元の差の合計値ですね
作図はこんな感じです。
次のコードで距離を求めることができます。
次元が増えても対応できます。
マンハッタンや京都のような
碁盤の目のような街を移動する時の距離です。
それぞれの次元の差の合計値ですね
作図はこんな感じです。
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()
次のコードで距離を求めることができます。
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
・チェビシェフ距離
作図はこんな感じですが
マンハッタン距離と同じです。
距離は次のコードで求めることができます。
次元が増えても対応できます。
次元の差の絶対値の最大値のことで
座標次元ごとで求めた差の中で
一番大きいものになります。
一番大きいものになります。
作図はこんな感じですが
マンハッタン距離と同じです。
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()
距離は次のコードで求めることができます。
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=∞にするとチェビシェフ距離
になります。
コードはこんな感じです。
pの値を変えることで距離が変化します。
ユークリッド、マンハッタン、チェビシェフ距離を
一般化したようなもので、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の値を変えることで距離が変化します。
・マハラノビス距離
一般的にあまりなじみのない距離の名前かと思いますが
多変数間の相関関係を取り入れて
既知のサンプルとの関係を明らかにする距離です
既知のサンプルとの関係を明らかにする距離です
データ群の平均や共分散行列を用いる方法で
異常検知などに使われるケースが多いようです。
サンプルデータを作図してみましょう。
青いデータが正常なもの
オレンジが異常データだと仮定します。
これにユークリッド距離で
等高線を描いてみましょう。
正常な青いデータを囲もうとすると
ユークリッド距離だとなかなかうまくいきません。
今度は青いデータを用いて
マハラビノス距離を考えてみましょう。
次のコードは簡単なデータでの
マハラビノス距離の計算です。
マハラビノス距離は2点のデータと
分散共分散行列のデータが必要になります。
先ほどのサンプルデータに
マハラビノス距離で等高線を描いてみましょう。
今度は青いデータとオレンジのデータを
マハラビノス距離でうまく分離することができます。
こんな感じで距離を計算すれば
異常検知などに使えますね。
異常検知などに使われるケースが多いようです。
サンプルデータを作図してみましょう。
# サンプルデータの可視化 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()
青いデータが正常なもの
オレンジが異常データだと仮定します。
これにユークリッド距離で
等高線を描いてみましょう。
# ユークリッド距離で見てみる 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()
正常な青いデータを囲もうとすると
ユークリッド距離だとなかなかうまくいきません。
今度は青いデータを用いて
マハラビノス距離を考えてみましょう。
次のコードは簡単なデータでの
マハラビノス距離の計算です。
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()
今度は青いデータとオレンジのデータを
マハラビノス距離でうまく分離することができます。
こんな感じで距離を計算すれば
異常検知などに使えますね。
2.文字列の類似度
・ハミング距離
同じ文字数の二つの文字列を比較したとき
同じ位置にある異なる文字の個数になります。
同じ位置にある異なる文字の個数になります。
二つの文字列を同じくするために
必要な文字の置換の回数(0回 - MAXは文字数分)
必要な文字の置換の回数(0回 - MAXは文字数分)
ABCDE と ABDFC なら3回(割合は0.6)
割合のMAXは1.0になります。
3.0
割合の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()
計算は次のコードでできます。
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 ~ 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つの集合の類似度は高い(似ている)ことになります。
集合の計算方法で係数を求めることができます。
2つの集合の類似度は高い(似ている)ことになります。
集合の計算方法で係数を求めることができます。
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つの集合の平均要素数と
共通要素数での割合になります。
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集合の平均要素数」から
「少ない方の要素数」にしたものです。
「少ない方の要素数」にしたものです。
ダイス係数よりも差集合の要素数による影響を下げ
相対的に共通要素数を重視した類似度計算です。
相対的に共通要素数を重視した類似度計算です。
# 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係数となります。
Jaccard係数 < Dice係数 < Simpson係数となります。
これらの係数は
文書同士の類似度計算
トピック同士の関連推定
文字列同士の共起推定
など類似性や距離を測るのに用いられます。
まとめ
プログラミングでは文字列や集合
ベクトルの類似度など
ベクトルの類似度など
距離を測るのにたくさんの方法があるので
目的に応じて使い分けられるようになると
すごく捗るでしょう。
今回はこれまでです
それでは。
すごく捗るでしょう。
今回はこれまでです
それでは。
コメントする