k-近傍法（K-Nearest Neighbors）

k-近傍法（KNN）アルゴリズムは、機械学習における分類および回帰タスクに使用される非パラメトリックな教師あり学習アルゴリズムです。このアルゴリズムは近さの概念に基づき、類似したデータポイント同士が近くに存在すると仮定します。KNNはラーニングフェーズを持たない「遅延学習」アルゴリズムであり、トレーニングデータ全体を保持し、新しいデータポイントのクラスや値を決定する際にそれらを利用して予測を行います。テスト用データポイントの予測時には、そのデータに最も近い‘k’個のトレーニングデータポイントを特定し、これらの近傍に基づいて出力を推定します。この手法は非常に直感的であり、人間が既知の事例と新しいデータを比較する認識戦略を模倣しています。

KNNの仕組み

KNNは、クエリポイントに最も近い‘k’個のデータポイントを特定し、これらの近傍を用いて予測を行います。

• 分類タスクでは、アルゴリズムはクエリポイントを、その‘k’個の近傍の中で最も多いクラスに割り当てます。これは多数決（majority voting）と呼ばれます。多数決は複数クラスの場合には「最多得票制（plurality voting）」として理解され、絶対多数でなくとも最多のクラスに割り当てられます。
• 回帰タスクでは、‘k’個の近傍の値の平均を取ることで予測値を算出します。

近さや類似性の原理は人間の知覚の中核であり、KNNの機能の中心でもあります。特徴空間で近接しているデータポイントは、より似ていると仮定され、したがって結果も似ていると考えられます。

距離指標

KNNで最も近い近傍を決めるために、さまざまな距離指標が用いられます。これらはアルゴリズムの性能にとって非常に重要です。

• ユークリッド距離：多次元空間における2点間の直線距離で、連続値変数に最もよく使用されます。KNNで最も一般的な距離指標であり、データが密で連続している場合に特に有用です。
• マンハッタン距離：タクシー距離とも呼ばれ、2点間の座標差の絶対値の合計で距離を計算します。移動が直交方向に制約されるグリッド状の経路で有効です。
• ミンコフスキー距離：ユークリッド距離とマンハッタン距離の一般形で、‘p’というパラメータで制御されます。p=1でマンハッタン距離、p=2でユークリッド距離となり、選択した‘p’値によって柔軟に調整可能です。
• ハミング距離：カテゴリカルデータ向けで、2つのバイナリベクトル間のビットの相違数をカウントします。属性が2値の場合のバイナリ分類問題で特に有効です。

適切な‘k’値の選び方

KNNのパラメータ‘k’は、考慮する近傍の数を示します。適切な‘k’の選定はとても重要です。

• ‘k’が小さいと過学習しやすく、トレーニングデータのノイズに過度に反応し、一般化できないパターンを拾ってしまいます。
• ‘k’が大きいと過少適合となり、モデルが一般化しすぎて重要なパターンを無視し、予測性能が低下します。
• 通常はクロスバリデーションによって‘k’を決定し、分類では同点回避のため奇数が選ばれます。‘k’の選択はモデルの精度に大きく影響し、多くの場合経験的に設定されます。

長所と短所

長所

• シンプルで直感的：理解しやすく実装も容易で、初心者にも適した手法です。KNNのシンプルさは、テストデータと保存済み例を直接比較する直線的な手法にあります。
• 学習フェーズ不要：KNNは明示的な学習フェーズを必要とせず、保存されたデータセットを使って予測を行います。つまり、新しいデータポイントをデータセットに追加することで簡単にモデル更新が可能です。
• 多用途：分類・回帰の両方に利用でき、さまざまな分野で広く活用されています。マルチラベル分類問題にも有効です。

短所

• 計算コストが高い：新しいデータポイントごとに全データセットと比較が必要なため、大規模データでは計算資源や時間を多く消費します。KNNの計算量はO(n)（nはトレーニングサンプル数）です。
• 外れ値に敏感：外れ値の存在が予測結果に大きく影響する場合があり、特に‘k’が小さいときにその傾向が顕著です。
• 次元の呪い：高次元空間ではデータポイント間の距離の有意性が低下し、KNNの性能が劣化します。次元数が増えると空間の体積も増え、データが疎になり、適切な近傍を見つけにくくなります。

活用例

KNNはそのシンプルさと有効性からさまざまな分野で利用されています。

• レコメンデーションシステム：類似ユーザーの嗜好を評価し、ユーザーに商品やコンテンツを提案する際に利用されます。
• パターン認識：手書き文字認識などのパターン認識タスクで、ピクセル値の類似性に基づいて画像を分類できます。
• データ補完：データセットの欠損値を類似データポイントに基づいて推定し、データの完全性を維持します。
• 金融・医療：株価予測、リスク評価、医療診断など、過去データの類似性分析に基づく予測に応用されています。医療では、症状を既知の症例と比較して患者の診断を予測できます。

Pythonによる実装例

KNNはPythonのscikit-learnなどのライブラリで簡単に実装できます。以下は分類タスクにおけるKNNの基本的な例です。

from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.datasets import load_iris
from sklearn.metrics import accuracy_score

# データセットの読み込み
iris = load_iris()
X, y = iris.data, iris.target

# トレーニングとテストデータへの分割
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# k=3のKNN分類器を初期化
knn = KNeighborsClassifier(n_neighbors=3)

# モデルの学習
knn.fit(X_train, y_train)

# 予測
y_pred = knn.predict(X_test)

# 精度評価
accuracy = accuracy_score(y_test, y_pred)
print(f"Accuracy: {accuracy:.2f}")

科学研究におけるk-近傍法（KNN）

k-近傍法（KNN）は、マルチメディア情報検索、データマイニング、機械学習など、特に大規模データセットの文脈で広く利用される基本アルゴリズムです。

代表的な研究論文：

• “Approximate k-NN Graph Construction: a Generic Online Approach”（Wan-Lei Zhaoほか）：
  多様なデータ規模や次元に対応し、オンライン更新が可能な近似k-近傍探索およびグラフ構築手法を提案しています。多くの既存手法では困難なオンライン更新に対応しており、動的かつ実用的なソリューションを示しています。詳細はこちら。

• “Parallel Nearest Neighbors in Low Dimensions with Batch Updates”（Magdalen Dobson, Guy Blelloch）：
  kd-treeとMorton順序を組み合わせたzd-tree構造による並列アルゴリズムを提案し、低次元データで最適化。既存アルゴリズムより高速で、並列処理による大幅なスピードアップを実現しています。zd-treeは、k-近傍データ構造として初めて並列バッチ動的更新をサポートします。詳細はこちら。

• “Twin Neural Network Improved k-Nearest Neighbor Regression”（Sebastian J. Wetzel）：
  ツインニューラルネットワークによる新しいk-近傍回帰手法を提案。回帰ターゲット間の差分予測に注目し、従来のニューラルネットワークやk-近傍回帰と比較して、小～中規模データセットで優れた性能を示しています。詳細はこちら。