はじめに
k-NN(k-nearest neighbor algorithm, k近傍法)は，機械学習の基礎のアルゴリズムとして有名であり，各々の点の距離を計算するため計算量が大きいものの，直感的に理解しやすいアルゴリズムとして，広く用いられています．
今回はそんなK-NNを用いる際に，特徴量が多く，高次元なデータの場合はどうするのかを考えます．
一般的に，ユークリッド距離は高次元空間上では，最近傍の点と，最遠傍の点の距離が近くなるため，距離が重要なファクターとなるK-NNにおいては，結果の信頼性が怪しいです[1]．
そこで，高次元空間上では，コサイン類似度(cosine similarity)など，高次元でもきちんと機能する距離を用いる必要があります．また，どの距離を用いるかについて，ノーフリーランチ定理といい，常にこの距離を用いれば良いという指針はなく，2017年に執筆されたK-NNのレビュー[2]においてもそのことが述べられており，cosine類似度もデータセットによってはきちんと機能しております．
しかし，scikit-learnにおいては，cosine類似度の実装はなく，また，日本語の文献で高次元上でのK-NNについて書かれた文献はなかったため，記事を書くことにしました！
Set Up
使用したライブラリは以下の通りです．
numpy
sklearn
pandas
特に特殊なライブラリは用いておりません．
sklearnを入れているのは，irisによって挙動を確認するためです．
コード
コードは以下の通りです．
import numpy as np
import pandas as pd
from sklearn.datasets import load_iris
from collections import Counter
from sklearn.model_selection import train_test_split
"""
input:
train_X: pd.DataFrame(N1, d)
test_X: pd.DataFrame(N2, d)
train_Y: pd.DataFrame(N1, 1)
k: int
output:
pred_Y: np.ndarrray(N2, k)
"""
def calculate_similar_vector(vector: np.ndarray, train_X: pd.DataFrame, train_Y: np.ndarray, K: int) -> np.ndarray:
"""
input: vector (shape=(d, )), train_X (shape=(N1, d)), train_Y (shape=(N1, ))
output: sim_df (shape=(K, ))
"""
norms = np.linalg.norm(train_X.iloc[:, 1:], ord=2, axis=1)
inner_product_df = pd.DataFrame({"inner_product": np.dot(train_X.iloc[:, 1:], vector) / (norms * np.linalg.norm(vector, ord=2)), "snode": train_X["index"], "label": train_Y})
argmax_df = inner_product_df.sort_values(by="inner_product", ascending=False)
labels = argmax_df["label"].values[:K]
return labels
def exec_knn(train_X: pd.DataFrame, test_X: pd.DataFrame, train_Y: np.ndarray, K: int) -> np.ndarray:
# 形を整える
train_X = train_X.reset_index()
test_X = test_X.reset_index()
test_size = test_X.shape[0]
pred_Y = []
for i in range(test_size):
node = test_X["index"].iloc[i]
vector = test_X[test_X["index"] == node].values[0, 1:]
count_arrays = calculate_similar_vector(vector, train_X, train_Y, K)
uniques, counts = np.unique(count_arrays, return_counts=True)
for i, (key_, value_) in enumerate(zip(uniques, counts)):
if i == 0:
max_key = key_
max_num = value_
else:
if max_num <= value_:
max_key = key_
max_num = value_
pred_Y.append(max_key)
return np.array(pred_Y)
inputの型に注意してください．N1は，学習データの数，N2はテストデータの数，dは次元数です．
irisで確認
この章はirisを使って挙動を確認します．
irisは高次元なデータではありませんが，あくまで挙動確認のためです．
以下を実行してみてください．今回は簡単のため，k=1としております．
if __name__ == '__main__':
iris = load_iris()
X = pd.DataFrame(iris.data, columns=["a", "b", "c", "d"])
Y = iris.target
train_X, test_X, train_Y, test_Y = train_test_split(X, Y, test_size=0.3, random_state=0)
k = 1
exec_knn(train_X, test_X, train_Y, k)
実際に使う際には，こちらのデータセットを変更すれば良いです．
これのrandom_stateを設定し，こちらを出力すると，
[2 1 0 2 0 2 0 1 1 1 2 1 1 1 1 0 1 1 0 0 2 1 0 0 2 0 0 1 1 0 2 1 0 2 2 1 0
2 1 1 2 0 2 0 0]
となり，実際のtest_Yと比べて見ると，
[2 1 0 2 0 2 0 1 1 1 2 1 1 1 1 0 1 1 0 0 2 1 0 0 2 0 0 1 1 0 2 1 0 2 2 1 0
1 1 1 2 0 2 0 0]
一つを除き，正答であることがわかります．
おわりに
何か間違いがあればコメントいただけると嬉しいです！
参考文献
[1] 高次元上でのユークリッド距離
https://qiita.com/tn1031/items/96e7131cd41df1aebe85
[2] K-NNレビュー
https://arxiv.org/pdf/1708.04321.pdf