k近傍法（KNN: K-Nearest Neighbors）のアルゴリズム解説

はじめ

k近傍法（KNN: K-Nearest Neighbors）は、分類問題と回帰問題に使われる教師あり学習です。動作としては、予測したいデータポイントの付近にあるデータポイント（近傍）を見つけて、そのラベル（または値）に基づいた予測を行います。

本記事では、k近傍法のアルゴリズムについて説明します。

アルゴリズム

1. 距離計算

予測したいデータポイントと他のデータポイントとの距離を計算します。距離の計算では、ユークリッド距離やマンハッタン距離、コサイン類似度、DTW距離などが用いられます。

まず、$n$次元で表される2つのデータポイントを$\boldsymbol{p} = (p_1, p_2, \cdots, p_n), \boldsymbol{q} = (q_1, q_2, \cdots, q_n)$とします。

• ユークリッド距離（Euclidean distance）

  2つのデータポイント$\boldsymbol{p}, \boldsymbol{q}$について、ベクトル間の直線的な距離を算出します。
  $$
  d_{Euclidean}(\boldsymbol{p}, \boldsymbol{q}) = \sqrt{\sum_{i = 1}^{n}{(p_i - q_i)^2}}
  $$

• マンハッタン距離（Manhattan Distance）

  2つのデータポイント$\boldsymbol{p}, \boldsymbol{q}$について、各次元の差の絶対値を合計します。
  $$
  d_{Manhattan}(\boldsymbol{p}, \boldsymbol{q}) = \sum_{i = 1}^{n}{|p_i - q_i|}
  $$

• コサイン類似度（Cosine Similarity）

  2つのデータポイント$\boldsymbol{p}, \boldsymbol{q}$について、ベクトル間の角度の類似度を算出します。
  $$
  cos (\boldsymbol{p}, \boldsymbol{q}) = \frac{\boldsymbol{p} \cdot \boldsymbol{q}}{||\boldsymbol{p}|| , ||\boldsymbol{p}||}
  $$

• DTW（Dynamic Time Warping）距離

  2つのデータポイント$\boldsymbol{p}, \boldsymbol{q}$について、各次元の数値を総当たりで求めて最短となるパスを探索することで波形間の非類似度を算出します。詳細は次の記事をご確認ください。

2. 近傍点の選定

予測したいデータポイントに対して$k$個の最も近いデータポイント（近傍点）を選択します。すなわち、先ほど算出した距離が小さい上位$k$個のデータポイントを選択します。

3. 予測

分類問題の場合、予測結果を$k$個の近傍点のラベル（クラス）の中で最も頻繁に出現するクラスで多数決あるいは、近傍の順位で重みづけをすることで決定します。

回帰問題の場合、予測結果は$k$個の近傍点の値で平均したものです。

特徴

k近傍法の特徴として、長所と短所をまとめます。

長所

• 特徴量（データポイントの次元数）の意味やデータの構造を特に考慮しなくても動作する簡易的なアルゴリズムである
• 非線形な関係データに対しても、近傍点の多数決や平均を取ることで柔軟に対応できる

短所

• 予測のときに訓練データ数だけのデータポイントと距離を計算するため、大規模なデータセットでは不向き（メモリの使用量も爆発する）
  • 計算量: $O(N_{train} \cdot N_{test} \cdot \rm{dist})$
    • $N_{train}$ : 訓練データ数
    • $N_{test}$ : テストデータ数
    • $\rm{dist}$ : 距離計算の計算量
      • ユークリッド距離 : $O(n)$
        • $n$: 次元数
      • マンハッタン距離 : $O(n)$
        • $n$: 次元数
      • コサイン類似度 : $O(n)$
        • $n$: 次元数
      • DTW距離 : $O(n \cdot m)$
        • $n, m$: 2つの時系列データの各データポイント数
• 近傍点の選択で距離を用いるため、特徴量のスケール（単位や範囲）に依存する
  • 前処理として、特徴量のスケーリングをする必要がある
    • 正規化: $x_{norm} = \frac{x - \rm{min}(X)}{\rm{max}(X) - \rm{min}(X)}$
      • データを任意の範囲に収める
        • 上記の数式では $0$ ~ $1$ の範囲になる
      • 最大値と最小値に基づくため、外れ値の影響を受ける
      • 元の分布や平均値に関する情報を保持しない
      • 距離ベースのアルゴリズムに有効
        • k近傍法の他にSVM
    • 標準化: $x_{std} = \frac{x - \mu}{\sigma}$
      • データの平均を $0$、標準偏差を $1$ にする（正規分布に近づける）
      • 外れ値の影響を受けない
      • 元の分布や平均値に関する情報を保持する
      • 単位が異なるデータ間の比較に有効である
        • 線形回帰、ロジスティック回帰、ニューラルネットワーク
• 距離計算に基づくため、特徴量が多いと計算量の爆発の他に、次元の呪い(下記を参照)の問題がある
  • 多量な特徴量による次元の呪いが与える影響として次が挙げられる
    • データポイント同士の距離に違いが生まれにくくなる
    • データが多次元空間に広がり、少ないサンプルで十分な情報を得ることが難しくなる
  • 前処理として、次の手法をとることで軽減できる
    • 次元の要約: 主成分分析（PCA）、t-SNEを用いる
    • 特徴の選択: 有用な特徴量のみを選択して次元数を減らす
  • 決定木、ランダムフォレストなど次元の呪いに耐久があるアルゴリズムを採用する

ハイパーパラメータ

k近傍法のモデルを構築するにあたり、次のパラメータを決定する必要があります。

• 距離の計算方法: ユークリッド距離、マンハッタン距離、コサイン類似度など
• 近傍点の数 $k$
  • $k$ が小さいと、訓練データに過剰に適合する（過学習）
  • $k$ が大きいと、モデルが単純すぎて汎用性が低くなる（学習不足）
  • 多数決をとるため、偶数の使用は控える
• 近傍点の重み付け
  • 近傍点の影響を一様に扱う
  • 近傍点のうち、近いものの影響を強くする

コーディング事情

基本的に、実装の簡易性と柔軟性はトレードオフの関係にあります。

フレームワーク	GPU対応	簡易性	柔軟性	備考
Scikit-learn	X	O	△	最も一般的なKNNライブラリ
TensorFlow	O	△	X	独自の実装、もしくは外部ライブラリの利用が必要?
PyTorch	O	△	△	PyTorch用のKNNライブラリが存在
Faiss	O	△	O	Facebook製、効率的な最近傍検索に特化
cuML	O	△	O	NVIDIA RAPIDSの一部、GPU高速化
MLlib	O	X	O	Spark MLlib、分散処理に適している