前書き

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

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

最近傍点抽出器にはsklearn.neighbors.NearestNeighborsを、
最近傍分類器にはsklearn.neighbors.KNeighborsClassifierを使用します。

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

最近旁点について

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

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

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

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

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

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

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を例に距離空間における概念、用語を説明します。

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で提供される距離を元に例を挙げてみます。

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

ユークリッド距離

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

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

二次元の場合

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

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_ 変数に足して総和を出します。

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

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を使うことで行列計算が楽になります。

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関数を利用した場合

import numpy as np

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

方法２

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

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

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

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を参照するとユークリッド距離の定義がされていますが、プログラムで考えるとさほど難しくないかと思います。

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

最近傍点の抽出

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

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

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

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を指定しています。

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

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

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

extractor.fit(X)

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

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

test_data = [[3.8, 3.7]]

distances, indexes = extractor.kneighbors(test_data)

最近傍法について

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

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

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に分類されます。

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

最後に

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

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

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