はじめに

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

使用したライブラリは以下の通りです．

requirement.txt

numpy
sklearn
pandas

特に特殊なライブラリは用いておりません．
sklearnを入れているのは，irisによって挙動を確認するためです．

コード

コードは以下の通りです．

knn.py

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としております．

knn.py

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を設定し，こちらを出力すると，

predict.txt

[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と比べて見ると，

answer.txt

[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