最近傍点について

### 前書き

最近傍点に関する理解の整理のために、現状の認識を纏めました。

本投稿ではまず最近傍点について確認し、その後尺度についても確認します。
次に最近傍点の抽出を行い、最後に最近傍法について補足をして終わります。

最近傍点抽出器には[sklearn.neighbors.NearestNeighbors](https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.NearestNeighbors.html)を、
最近傍分類器には[sklearn.neighbors.KNeighborsClassifier](https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsClassifier.html)を使用します。

また実行環境として[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`を利用します。

## 最近旁点について

最近旁点とは距離空間におけるある点から最も近い点です。

まず距離空間について説明します。
距離空間とは下記の図`distance1`の様な点と点の間の距離を測れる空間です。

各データをプロットすることで、距離空間を可視化し、点同士の距離における相関が確認できます。

図`distance1`において、点`1`、点`2`、点`3`が比較的近いこと、また点`0`が離れていることが分かります。

最近旁点とは最も近い点なので、例でいうと点`3`の最近傍点は点`1`です。

![output_0_0.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/156292/a4f05f20-ec4b-378a-4194-b404026fde90.png)

- ソースコード、集合`X`をプロット

```py
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline

# 集合を定義
X = np.array([[7.3, 4.1], [3.8, 3.7], [2.5, 3.8], [3.4, 3.3]])

# 散布図を初期化
plt.figure()
plt.title('distance1')
plt.xlabel('x axis')
plt.ylabel('y axis')

# データをプロット
for i in range(X.shape[0]):
    x = X[i][0]
    y = X[i][1]
    
    plt.plot(x, y, 'o')
    plt.annotate(i, xy=(x, y))
```

### 距離空間について

距離空間は実数値から成るN次元のデータであれば簡単に作り出せます。

例えば緯度と経度、支出と収入等、数値に変換できるものであれば可能です。

ただし不規則なハッシュ値や、0, 1しか取らない真偽値などの数値は、意味のある距離に出来ません。

### 距離空間における用語

集合`X`を例に距離空間における概念、用語を説明します。

```py
X = np.array([[7.3, 4.1], [3.8, 3.7], [2.5, 3.8], [3.4, 3.3]])
```

- `[7.3, 4.1]`の様な配列をベクトル、または点と呼びます。

- `X`を集合または、ベクトル集合と呼びます。

- ベクトル間(点と点の間)を距離と呼びます。

- 距離は非類似度と呼ぶことが出来ます。
   近ければ似ていて、遠ければ似てないことを意味します。

- 実数値を特徴と呼びます、`7.3`、`4.1`をそれぞれ特徴1、特徴2と呼ぶことが出来ます。


### 距離を測るには

距離を測るためには、尺度と呼ばれる距離関数を利用し、ベクトル間の距離を算出します。

ベクトル間の距離を測る尺度は多数あり、データの種類に応じて使い分けを行うことが出来ます。
[sklearn.neighbors.DistanceMetric](https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.DistanceMetric.html)で提供される距離を元に例を挙げてみます。

- [ユークリッド距離](https://github.com/scikit-learn/scikit-learn/blob/14f5302b7000e9096de93beef37dcdb08f55f128/sklearn/neighbors/dist_metrics.pyx#L405)
- [ミンコフスキー距離](https://github.com/scikit-learn/scikit-learn/blob/14f5302b7000e9096de93beef37dcdb08f55f128/sklearn/neighbors/dist_metrics.pyx#L524)
- [マハラノビス距離](https://github.com/scikit-learn/scikit-learn/blob/14f5302b7000e9096de93beef37dcdb08f55f128/sklearn/neighbors/dist_metrics.pyx#L630)
...etc

`NearesrNeighbors`のデフォルトの尺度はミンコフスキー距離ですが、以下では一般的な距離の尺度として利用されるユークリッド距離を例に距離の算出を行います。

### ユークリッド距離

ユークリッド距離とはざっくりいうと、ベクトルの差を2乗した物の総和をルートで割ったものになります。

ユークリッド距離はnumpy、scipy等で機能として提供されていますが、ブラックボックスにならないようにまずは自分で実装をしてみたいと思います。

- 二次元の場合

二次元の場合はとてもシンプルに書けます。
ベクトルの類似性が高いほど、距離が短くなることが分かります。

```py
import numpy as np

# 定義
def euclidean(v1, v2):
     return np.sqrt((v1[0] - v2[0]) ** 2 + (v1[1] - v2[1]) ** 2)

# テスト
v1 = [7.3, 4.1]
v2 = [3.8, 3.7]

print(euclidean(v1, v2))

v1 = [3.4, 3.3]
v2 = [3.8, 3.7]

print(euclidean(v1, v2))
```

- 実行結果

```
3.5227829907617076
0.5656854249492381
```

- N次元の場合

2次元とは若干アプローチが違いますが、やっていることは同じで
ベクトルの列の差を2乗したものを`sum_ `変数に足して総和を出します。

最後に総和をルートで割ります。

```py
import numpy as np

def euclidean(v1, v2):
    sum_ = 0
    
    for i in range(len(v1)):
        sum_ += (v1[i] - v2[i]) ** 2
    
    return np.sqrt(sum_)

# 2次元の場合と同じ距離が算出される
v1 = [3.4, 3.3]
v2 = [3.8, 3.7]

print(euclidean(v1, v2))

# 多次元の場合でも距離を算出できる
v1 = [3.9, 9.1, 7.1, 4.6, 8.8]
v2 = [7.1, 3.9, 9.5, 6.8, 1.8]

print(euclidean(v1, v2))

v1 = [3.9, 9.1, 7.1, 4.6, 8.8]
v2 = [4.1, 8.8, 6.9, 5.5, 8.8]

print(euclidean(v1, v2))
```

- 出力

```
0.5656854249492381
9.842763839491427
0.9899494936611662
```

- numpyを使用した場合

次にnumpyを利用してユークリッド距離を実装してみたいと思います。

numpyでは科学計算等で利用される様々な機能が提供されているので、計算に関する複雑な実装を自分でする必要がなく、かつ計算を高速に処理できます、内部的にPythonを拡張し高速化する実装が行われているそうです。

まず`np.array`を使うことで行列計算が楽になります。

```py
import numpy as np

v1 = np.array([3.4, 3.3])
v2 = np.array([3.8, 3.7])

# 恐らく演算子がオーバーライドされているため、配列間の演算が楽に行える。
print(v1 - v2)

# こういうことをしなくて済む
print([v1[i] - v2[i] for i in range(len(v2))])
```

- 出力、numpyでは丸め処理も行ってくれるそう

```
[-0.4 -0.4]
[-0.3999999999999999, -0.40000000000000036]
```

- numpyを使ったユークリッド距離の実装

次にユークリッド距離の実装を行いたいと思います。
ググったところ、numpyでのユークリッド距離の実装はいくつかありました。

- 方法１

norm関数を利用した場合

```py
import numpy as np

def euclidean(v1, v2):
    return np.linalg.norm(v1 - v2)
```

- 方法２

power関数、sqrt関数を利用した場合。やってることは冪乗して平方根で割っているだけ

```py
def euclidean(v1, v2):
    return np.sqrt(np.power(v1 - v2, 2).sum())
```

上記でユークリッド距離の実装が行えます、いずれも出力は同一です。

```py
import numpy as np

distances = []

v1 = [3.4, 3.3]
v2 = [3.8, 3.7]

def euclidean(v1, v2):
     return np.sqrt((v1[0] - v2[0]) ** 2 + (v1[1] - v2[1]) ** 2)

distances.append(euclidean(v1, v2))

def euclidean(v1, v2):
    sum_ = 0
    
    for i in range(len(v1)):
        sum_ += (v1[i] - v2[i]) ** 2
    
    return np.sqrt(sum_)

distances.append(euclidean(v1, v2))

def euclidean(v1, v2):
    return np.linalg.norm(v1 - v2)

v1 = np.array([3.4, 3.3])
v2 = np.array([3.8, 3.7])

distances.append(euclidean(v1, v2))

def euclidean(v1, v2):
    return np.sqrt(np.power(v1 - v2, 2).sum())

distances.append(euclidean(v1, v2))

print(distances)
print([distance == distances[0] for distance in distances])
```

- 出力

```
[0.5656854249492381, 0.5656854249492381, 0.5656854249492381, 0.5656854249492381]
[True, True, True, True]
```

また公式、公理に関して、[wikipedia](https://ja.wikipedia.org/wiki/%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E8%B7%9D%E9%9B%A2)を参照するとユークリッド距離の定義がされていますが、プログラムで考えるとさほど難しくないかと思います。

```math
d(q,p) = \sqrt{\sum_{i=i}^n(q_i - p_i)^2}
```

### 最近傍点の抽出

最近傍点、距離を踏まえた上で最近傍点の抽出を行います。

scikit-learnでは最近傍点の抽出を行う機能として、`NearestNeighbors`、`KNeighborsClassifier`が提供されています、今回は`NearestNeighbors`を使用します。

学習データには前述で登場した集合`X`を利用します。

```py
from sklearn.neighbors import NearestNeighbors

X = np.array([[7.3, 4.1], [3.8, 3.7], [2.5, 3.8], [3.4, 3.3]])

extractor = NearestNeighbors(metric='euclidean', n_neighbors=4)

extractor.fit(X)

test_data = [[3.8, 3.7]]

distances, indexes = extractor.kneighbors(test_data)

print('最近傍点\n')
for k, v in enumerate(indexes[0]):
    print(k, '--->',  X[v])

print('\n最近傍点の距離\n')
for k, v in enumerate(distances[0]):
    print(k, '--->',  v)
```

- 出力

出力から最近傍点が取り出せていることが確認できます。
また上から距離がどんどん離れていっていることが確認できます。

```
最近傍点

0 ---> [3.8 3.7]
1 ---> [3.4 3.3]
2 ---> [2.5 3.8]
3 ---> [7.3 4.1]

最近傍点の距離

0 ---> 0.0
1 ---> 0.5656854249492382
2 ---> 1.3038404810405282
3 ---> 3.522782990761708
```

- ソースについての補足

抽出器のインスタンスを生成します。

パラメータとして、尺度に`ユークリッド距離`、取り出す最近傍点に`4`を指定しています。

```py
extractor = NearestNeighbors(metric='euclidean', n_neighbors=4)
```

集合を与えて抽出器に学習させます。

余談ですが、`NearestNeighbors`ではただ学習するだけではなく、決定木を構築し
近傍取り出しの処理速度を高速化してくれる機能も付いてるらしいです。
今後ソースを読んで記事にしたいとは思っています。

```py
extractor.fit(X)
```

集合`X`の一部を切り取って変数`test_data`に抽出器の入力データとして定義しています。
また`kneighbors`メソッドで最近傍点の抽出を行っています。

返り値は`距離配列`、`学習時のデータのインデックス配列`となっており後者によって最近傍点の逆引きが行えます。
配列は最近傍点ということで`距離`が短いものから昇順になっています。

```py
test_data = [[3.8, 3.7]]

distances, indexes = extractor.kneighbors(test_data)
```

### 最近傍法について

最近傍法とはざっくりいうと、任意な`k`個の最近傍点を取り出し、`k`個の最近傍点が属す最も多いクラスに入力データを分類する機能を指します。

以下でざっくり説明します。

```py
from sklearn.neighbors import KNeighborsClassifier

X = np.array([[7.3, 4.1], [3.8, 3.7], [2.5, 3.8], [3.4, 3.3]])

y = np.array([1, 1, 2, 0])

classifier = KNeighborsClassifier(metric='euclidean', n_neighbors=4)
classifier.fit(X, y)

predict = classifier.predict([[3.8, 3.7]])
print(predict)

X = np.array([[7.3, 4.1], [3.8, 3.7], [2.5, 3.8], [3.4, 3.3]])
y = np.array([1, 2, 2, 0])

classifier.fit(X, y)

predict = classifier.predict([[3.8, 3.7]])
print(predict)
```

- 出力

```
[1]
[2]
```

- 補足

`NearestNeighbors`のケースとほとんど同じで、違うのは変数`y`の登場と学習モデルの出力だと思います。
変数`y`はラベルの集合です、ラベルはクラスとも呼ばれたりしますが指し示すものは同じです。

ラベルとはデータの識別子のようなもので、例として犬の画像のラベル、文字列`"犬"`が挙げられます。
しかし機械学習では文字列をデータを使った学習というのができないらしいので、予め数値に変換したりします。

上記ではそれぞれ点`0`、点`1`がクラス`1`に属し、点`2`がクラス`2`に属し、点`3`がクラス`0`に属すことを意味します。

分類器の最近傍点の数を`4`に指定しているので、4個の中の多数決、つまり入力データのクラスは`1`に分類されます。

ラベル付けの作業をミスると期待しないクラスに分類されるので注意です。

### 最後に

上記では最近傍点について説明を行いましたが、ある程度説明出来ていれば幸いです。

最近傍点の抽出を利用して類似データの検索や識別、逆にクレジットカードの不正利用などの異常値の識別に使われることもあるそうです。

弱点や向かないパターンも多々ありますが、実数値に起こせれば距離が測れるので、汎用性が高く魅力的だと思います。