最近傍点について #Python

前書き

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

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

最近傍点抽出器には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}

最後に

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

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

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