scikit-learnで重み付きユークリッド距離を実装する

### 前書き

重み付きユークリッド距離を[scikit-learn](https://scikit-learn.org/stable/)で実現したかったのですが、なかなか情報がなかったのでまとめました。

検証環境として[Docker Hub](https://hub.docker.com/)で提供されている[jupyter/datascience-notebook](https://hub.docker.com/r/jupyter/datascience-notebook)イメージを使用します。

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

```sh
$ 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`を利用します。

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

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

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

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

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

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

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

- [重み付きユークリッド距離モデル](http://www.it.is.tohoku.ac.jp/~kato/patman/sld027.htm)
- [重み付きユークリッド距離モデルのためのパラメータ推定法](https://www.jstage.jst.go.jp/article/sicetr1965/23/4/23_4_394/_pdf)
- [クラスター分析の原理](http://www.snap-tck.com/room04/c01/stat/stat20/stat2001.html)<br>
- [複数の非類似度を自由に重みづけできる単一のグラフ索引を用いた最近傍探索手法](https://library.naist.jp/mylimedio/dllimedio/showpdf2.cgi/DLPDFR012627_P1_72)<br>


### データセットの作成

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

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

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

```py
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個の最近傍点は取れそうです。

![output_0_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/156292/4c13b064-a4d5-a5b1-b206-6db547b62a04.png)
### 重みをつけない場合

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

ググったところ、[標準化ユークリッド距離は特徴を標準偏差で割ると知られているそうです](https://www.albert2005.co.jp/knowledge/data_mining/cluster/cluster_summary)。
[sklearn.neighbors.SEuclideanDistance](https://github.com/scikit-learn/scikit-learn/blob/14f5302b7000e9096de93beef37dcdb08f55f128/sklearn/neighbors/dist_metrics.pyx#L435-L477)を確認すると、確かにそれらしい実装になっています。


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

```py
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`で提供されている重み付きユークリッド距離の二通りを試してみます。

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

実装には[重み付きユークリッド距離モデルのためのパラメータ推定法](https://www.jstage.jst.go.jp/article/sicetr1965/23/4/23_4_394/_pdf)を参考にさせて頂きました。

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

```py
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`による標準化を行いました。


```py
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`を返すようにしています。

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

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

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

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

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

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

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

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

```py
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](https://github.com/scikit-learn/scikit-learn/blob/14f5302b7000e9096de93beef37dcdb08f55f128/sklearn/neighbors/dist_metrics.pyx#L211-L217)に`2`が指定されているため、`Warning`が出ますが、今回は明示的に指定しているので、気にしなくて大丈夫です。

```py
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`を利用することで簡単に実装できることが分かりました。

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