前書き

重み付きユークリッド距離をscikit-learnで実現したかったのですが、なかなか情報がなかったのでまとめました。

検証環境としてDocker Hubで提供されているjupyter/datascience-notebookイメージを使用します。

下記コマンドを実行し、ブラウザからlocalhost:9292にアクセスし、ログイン画面が表示されたら成功です。
パスワードはお好みで大丈夫です、今回はnhHce4PGOv0d0z4kにします。

$ password="nhHce4PGOv0d0z4k"
$ hash=$(docker run --rm -it jupyter/datascience-notebook python -c "from notebook.auth import passwd; print(passwd('${password}'))")
$ docker run --rm -it -p 9292:9292 \
             jupyter/datascience-notebook \
             jupyter notebook \
             --ip=0.0.0.0 \
             --port=9292 \
             --NotebookApp.password="${hash}"

ログインが出来たら新規Notebookを開きます、言語はPython 3を利用します。

ユークリッド距離における重みとは

ユークリッド距離における重みとは、任意な軸に対して重要度を与える配列を指します。

つまり重みを利用することで、距離を算出する際に当該次元の重要度を上げることが出来ます。

例えば年齢、身長、体重からなる集合から最近傍を抽出する際に、身長軸に対して重みを与えることで、身長の類似性が反映され、身長が似たものが優先的に抽出されます。

重み付きユークリッド距離は下記の様な表現ができると思っています。

D(x,y) = \sqrt{\sum_i^nw_i(x_i - y_i)^2}

重みについての解釈に当たって、下記のリンクを参考にさせて頂きました。

重み付きユークリッド距離モデル
重み付きユークリッド距離モデルのためのパラメータ推定法
クラスター分析の原理
複数の非類似度を自由に重みづけできる単一のグラフ索引を用いた最近傍探索手法

データセットの作成

今回は自前で3次元のデータセットを用意します。

なぜかというと、kneighborsメソッドの返り値を利用して逆引きした時に、重みづけが正しく反映されているか確認したいからです。

各特徴量の桁を3桁, 4桁, 5桁とすることで重みがかかっているか否かが分かりやすく判別出来ます。

import numpy as np
from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as plt
%matplotlib inline
from sklearn.neighbors import NearestNeighbors

row = 1500

def generate_train_data(row):
    X = np.random.randint(100, 1000, (row))
    X = np.column_stack((X, np.random.randint(1000, 10000, (row))))
    X = np.column_stack((X, np.random.randint(10000, 100000, (row))))
    
    return X

def generate_sample_data():
    return [
        np.random.randint(100, 1000),
        np.random.randint(1000, 10000),
        np.random.randint(10000, 100000),
    ]

X = generate_train_data(row)

ax = Axes3D(plt.figure())
ax.plot(X[:, 0], X[:, 1], X[:, 2], marker="o", linestyle='None')

散布図を見ると、データが全体的に散らばっているのが確認できます。

今回はNearestNeighborsの最近傍数をデフォルトの5で検証するので、散布図を見る限り
母集合に属す入力データであれば、分かりやすい5個の最近傍点は取れそうです。

重みをつけない場合

まずは重みをつけないパターンで実践してみます、今回は特徴量の標準化を行うために標準化ユークリッド距離を使用します。

ググったところ、標準化ユークリッド距離は特徴を標準偏差で割ると知られているそうです。
sklearn.neighbors.SEuclideanDistanceを確認すると、確かにそれらしい実装になっています。

D(x, y) = \sqrt{ \sum_i \frac{ (x_i - y_i) ^ 2}{V_i} }

v = X.std(axis=0)
sextractor = NearestNeighbors(metric='seuclidean',
                              metric_params={'V': v},
                              algorithm='auto')
sextractor.fit(X)

distances, indexes = sextractor.kneighbors([sample_data])

print(sample_data)
print(X[indexes[0]])
print(distances[0])

出力

学習データがランダム生成なために散らばりは見えますが、各特徴が類似したデータを抽出できていることが確認できると思います。

以降では重みをつけた最近傍点の抽出を行いますが、その際の比較としてのデータと認識頂ければと思います。

[943, 3209, 57925]
[[  912  3755 58469]
 [  796  2920 59772]
 [  675  3051 56917]
 [  985  3231 60983]
 [  940  4276 59186]]
[11.33139547 15.67520701 18.05811462 19.08931958 22.22105314]

重みをつけた場合

次に自作の重み付きユークリッド距離とsklearn.neighbors.WMinkowskiDistanceにp=2、wなる重みを与えた、いわばscikit-learnで提供されている重み付きユークリッド距離の二通りを試してみます。

自作重み付きユークリッド距離

実装には重み付きユークリッド距離モデルのためのパラメータ推定法を参考にさせて頂きました。

ここではまず、データセット、モデルの入力データの標準化を行います。
次に重み配列を生成し、最近傍点の抽出を行い、重みがかかっていることを確認します。

def genarate_weightlist(weightdict, n):
    return [weightdict[key] if key in weightdict else 1 for key in range(n)]
    

def weuclidean(q, p, **kwargs):
    w = np.array(kwargs["weight"]) ** 2
    
    return np.linalg.norm(w * (q - p))


X_ = X.copy()
sample_data_ = sample_data.copy()

mean = X_.mean(axis=0)
std = X_.std(axis=0)

X_ = (X_ - mean) / std
sample_data_ = (sample_data_ - mean) / std

weight = genarate_weightlist({1: 3}, 3)

wextractor = NearestNeighbors(metric=weuclidean,
                              metric_params={"weight": weight})

wextractor.fit(X_)
distances, indexes = wextractor.kneighbors([sample_data_])

print(sample_data)
print(X[indexes[0]])
print(distances[0])

出力

2列目に対して重み3を与えたことで、3209の近似値を持つベクトルが優先的に抽出されていることが確認できます。

またその代償として3列目の精度が高くないことが伺えます、重みを使った場合の要件や、重みの強さには注意が必要です。

[943, 3209, 57925]
[[  985  3231 60983]
 [  930  3232 69253]
 [  832  3228 65068]
 [  989  3152 72432]
 [  950  3098 71369]]
[0.21380456 0.44290195 0.51286854 0.61409306 0.63958892]

補足

特徴をスケールしています、出来ればsklearn.neighbors.SEuclideanDistanceと同様に(x - y) / stdとしたかったのですが、実力不足のため、厳密に再現できませんでした。

しかし目的なスケールなので、いったんはz-scoreによる標準化を行いました。

X_ = X.copy()
sample_data_ = sample_data.copy()

mean = X_.mean(axis=0)
std = X_.std(axis=0)

X_ = (X_ - mean) / std
sample_data_ = (sample_data_ - mean) / std

重み配列の生成を行っています、公理に従うとw_iなので重みは配列であることが伺えます。
genarate_weightlistの引数weightdictは{軸: 重み値}となっており、今回は{1: 3}なので2列目に重み3をかけています。

また引数nは配列長です、w_i * (x_i - y_i)^2なので次元数を揃える必要があります、今回は3です。

ここで重要なのは公理中でw_i * (x_i - y_i)^2なので重みを0を指定するともちろん演算結果も0になります。

よって指定がない場合はweightdict[key] if key in weightdict else 1としてデフォルト1を返すようにしています。

weight = genarate_weightlist({1: 3}, 3)

scikit-learnで提供されている重み付きユークリッド距離

最後にsklearn.neighbors.WMinkowskiDistanceを試してみます。

ミンコフスキー距離はパラメータpに応じてユークリッド距離、マンハッタン距離、チェビシェフ距離として扱える一般化された尺度です。

{D_p(x, y) = \left( \sum_{i}^n \left| x_i - y_i \right|^p \right)^{\frac 1 p}
}

p=2とすることで、ベクトルの差を2乗し、総和を1/2乗するので、確かにユークリッド距離となると思います。

D_2(x,y) = \left(\sum_{i}^n|x_i - y_i |^2 \right)^{\frac 12}

合っているかわかりませんが、下記計算式で出力が同一であることが確認できました。

import numpy as np

a = np.array([300, 500])
b = np.array([200, 300])

print(np.linalg.norm(a - b))
print(np.sqrt(((a - b) ** 2).sum()))

出力

223.60679774997897
223.60679774997897

以下では、重み付きユークリッド距離を使用した抽出器を使って最近傍点の抽出を行います。

自作時に生成したデータを利用し、重みがかかっていることを確認します。

DistanceMetricのコンストラクタのpに2が指定されているため、Warningが出ますが、今回は明示的に指定しているので、気にしなくて大丈夫です。

wmextractor = NearestNeighbors(metric='wminkowski',
                              metric_params={
                                  "w": weight,
                                  "p": 2
                              })
wmextractor.fit(X_)
distances, indexes = wmextractor.kneighbors([sample_data_])

print(sample_data)
print(X[indexes[0]])
print(distances[0])

出力

こちらでもやはり重みが効いていることが確認できます。
自作の場合と比べて若干出力が異なってきているのが見て取れます。
時間がある時にソースを追って追記してみたいとは思います。

[943, 3209, 57925]
[[  985  3231 60983]
 [  975  3025 63169]
 [  930  3232 69253]
 [  853  3439 54236]
 [  976  3048 68596]]
[0.20167393 0.31551838 0.43663889 0.45812962 0.46513838]

最後に

今回は重み付きユークリッド距離の実装を行いました。

自作した場合と比べて、sklearn.neighbors.WMinkowskiDistanceを利用することで簡単に実装できることが分かりました。

最近傍点を利用した検索機能を実装する場合、プライオリティ、優先度、重要度の様なものを重みを利用して実現できるのでとても便利ですね。