最近傍点の抽出

### 初めに

[PythonによるAIプログラミング入門](https://www.amazon.co.jp/PythonによるAIプログラミング入門-―ディープラーニングを始める前に身につけておくべき15の基礎技術-Prateek-Joshi)という書籍で機械学習周りの技術を勉強しています。

この書籍での最近旁点の抽出に関する記述がとても分かりやすかったので、理解できたことをこの投稿に残します。

誤った解釈をしている可能性がありますので、何か誤りがございましたらコメント欄にてご指摘お願い致します。

### 最近旁法について

少し機械学習目線にはなりますが、最近旁法とは入力データの距離から最も近い最近旁点を取得するアルゴリズムです。

入力データに最も類似したデータを抽出するアルゴリズムともいえます。

ここで扱う距離とは、高校数学で扱われる距離を指します。

距離は、各データの特徴を元に算出されます。
距離を測るアルゴリズムの代表的なものとして[ユークリッド距離](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{(q_1 - p_1)^2 + (q_2 -p_2)^2 + ...+(q_n-p_n)^2}}
```

プログラマはcsv形式のほうが分かりやすいと思うので、csvで上記の公式で登場する要素を表現してみます。

`q`は一列目、`p`は二列目、`p1`は一行目の一列目のを表し、`n`はデータの最大行数を表します。
そして`特徴`は行列を表します。

```hoge.csv
q,p
2.1,1.3
1.3,3.2
2.9,2.5
```

本記事で登場する`各データ`とは一般的なプログラム言語で扱うような配列の各要素を指します。
また以降で登場する`k`も同様の位置づけとなります。

```ruby
File.open('hoge.csv').each_line.to_a.length # => n

File.open('hoge.csv').each_line { |line| 
    puts line.split(",").length # => 特徴数
    puts line    # => k
    puts line[0] # => q, 特徴
    puts line[1] # => p, 特徴
}
```

最近旁法では、まず学習データの距離を割り出します。
未知データを入力として渡されたときに、学習データの中から最も距離が近いデータを返します。

この__最も距離が近いデータ__を__最近旁点__と呼びます。

より深い理解を行うため、[距離について](https://qiita.com/shim0mura/items/64918dad83d162ef2ac2)や[近傍法について](https://qiita.com/NoriakiOshita/items/698056cb74819624461f#k%E8%BF%91%E5%82%8D%E6%B3%95%E3%81%AE%E6%95%B0%E5%AD%A6%E7%9A%84%E7%90%86%E8%A7%A3)分かりやすい記事がありますので、是非参照してみてください。

### kNN、k-nn、k最近傍法について

- 最近旁法

最近旁法について調べていくと、k最近傍法というワードが出てきますが、最近旁法とk最近傍法は別物です。

以降の[チュートリアルの実践](#チュートリアルの実践)にて説明しますが、scikit-learnで最近旁法を提供するものとしてNearestNeighborsがあります。

NearestNeighborsは`unsupervised.py`というファイルに定義されています。

Unsupervised（教師なし）なので、最近旁法自体のアルゴリズムは`教師なし学習`です。

[公式ドキュメント](https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.NearestNeighbors.html)でも以下の様な言及がされています。

> Unsupervised learner for implementing neighbor searches.

翻訳すると`近傍検索を実装するための教師なし学習器`です。

- k最近傍法

それに対して`k最近傍法`は分類を行う機能で、最近旁法を利用して`k`個の最近旁点を見つけ
その中で最も多いクラスに分類を行うものです。

調べるとkNN、k-nn、k最近傍法と様々な名称がありますが、いずれも同じものを指します。

scikit-learnでは`KNeighborsClassifier`として機能が提供され、`classification.py`というファイルに定義されています。

classification（分類）なので、k最近傍法は分類を行う機能です。

公式ドキュメントでは、`k最近傍法を実装する分類子`という言及がされています。

また、NearestNeighborsに対して、KNeighborsClassifierは教師あり学習となります。

- 教師あり学習、教師なし学習について

念のため、教師の有無について少し言及します。

教師あり学習では人間が正解データをモデルに与え、それを元にモデルが学習します。
モデルは未知データを与えられた際にそのデータが正解か否かを推論します。

犬と猫の画像分類では、人間があらかじめ犬猫に分類したデータをモデルに学習させます。

人間から予め正解を教えてもらうことで、画像が犬か猫か？という問題を解決させます。

それに対して、教師なし学習では与えられたデータが正解か否かではなく
データの類似性など潜在的な本質を抽出します。

教師なし学習では、類似したデータのグループ化などが行われることがあります。

### チュートリアルの実践

以降では、書籍に記載してあるチュートリアルを実践していこうと思います。

`scikit-learn`という機械学習ライブラリでは最近旁法として、[NearestNeighbors](https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/neighbors/unsupervised.py)が提供されています。

チュートリアルでは`NearestNeighbors`を利用して、最近旁点の抽出を行います。

チュートリアルを行う際の環境は書籍に倣って、jupyter notebookを使用しています。

- パッケージのインポート、グラフのインライン表示、学習データの定義

学習データは2個のカラムを持つ2次元データです、14個あります。

チュートリアルではNearestNeighborsの振る舞いを確認したいので、このデータが何を意味するかは重要ではありません。

```py
import numpy as np 
import matplotlib.pyplot as plt
%matplotlib inline
from sklearn.neighbors import NearestNeighbors 

X = np.array([[2.1, 1.3], [1.3, 3.2], [2.9, 2.5], [2.7, 5.4], [3.8, 0.9], 
              [7.3, 2.1], [4.2, 6.5], [3.8, 3.7], [2.5, 4.1], [3.4, 1.9], 
              [5.7, 3.5], [6.1, 4.3], [5.1, 2.2], [6.2, 1.1]]) 
```

- データの可視化

下記の様な図が表示されます、pltやXに関しては、`plt.figure`や`X[:,0]`などを自分の手で打っていくと理解しやすいかもしれません。

```py
plt.figure() 
plt.title('Input data') 
plt.scatter(X[:,0], X[:,1], marker='o', s=75, color='black') 
plt.show()
```

![ダウンロード.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/156292/79ebf273-928d-86cd-46e5-c5f0e32e3680.png)

- モデルの学習、最近旁点の抽出

ここは非常に重要です、それぞれの変数について説明します。

項目|説明
:--|:--
k|最近旁点の数です、ここでは5個の最近旁点を抽出します。
test_datapoint|未知データです、このデータを中心に最近旁点を抽出します。
knn_model|モデルです、最近傍点数とアルゴリズムを指定し、学習させています。
kneighbors|入力(未知データ)からみた最近旁点を抽出します、ここでは5つの最近旁点を抽出します。
distances|float型の最近旁点の距離です。
indices|最近旁点のインデックスです、このインデックスを使用することで、学習データとの紐づけが出来ます。

`indices`変数は2次元のリストなので、一階層掘ってから`[:k]`でリストの5番目より前のデータをスライスします。

`indices`はリストです、それを`enumerate`で項番が付いた辞書に変換して回します。

`indices`は左が最も距離が類似しているので`rank`は類似順ともいえます。
`index`は学習データの出現位置を示します。

なので、`X[index]`とすれば5つの類似データを参照できるわけです。

```py
k = 5 
test_datapoint = [4.3, 2.7] 

knn_model = NearestNeighbors(n_neighbors=k, algorithm='ball_tree').fit(X) 
distances, indices = knn_model.kneighbors([test_datapoint]) 

print("K Nearest Neighbors:") 
for rank, index in enumerate(indices[0][:k], start=1): 
    print(str(rank) + " ==>", X[index]) 
```

下記が出力されます。
上から`test_datapoint`に類似しているデータを参照しています。

```
K Nearest Neighbors:
1 ==> [5.1 2.2]
2 ==> [3.8 3.7]
3 ==> [3.4 1.9]
4 ==> [2.9 2.5]
5 ==> [5.7 3.5]
```

- 最近旁点の可視化

最後に最近旁点の可視化を行います。
最近旁点となる5つのデータは大円で囲まれます。

```py
plt.figure() 
plt.title('Nearest neighbors') 
plt.scatter(X[:, 0], X[:, 1], marker='o', s=75, color='k') 
plt.scatter(X[indices][0][:][:, 0], X[indices][0][:][:, 1], 
            marker='o', s=250, color='k', facecolors='none') 
plt.scatter(test_datapoint[0], test_datapoint[1], 
            marker='x', s=75, color='k') 
plt.show() 
```

![ダウンロード (1).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/156292/728c1913-f37d-d284-1651-4a6e07e4a0b4.png)

チュートリアルは以上となります。

### 最後に

機械学習を利用した案件で最近旁法について調べていて、最近旁とk最近旁は同じものかと勘違いしていました。
なので、改めての理解、そして機械学習初心者の方は間違えやすい所かなと思い、記事にしました。

k最近旁の他にも、k最近旁回帰、k平均法、k近傍探索など色々なアルゴリズムがあるのでそれについても今後調査を進めて行きます。

最後に、機械学習を利用されたご経験がある方のご飯とかの気軽なご連絡をお待ちしています！
機械学習何がなんだかわからないので...泣