K-Nearest Neighbors (KNN)

k 近傍法（KNN）は教師あり学習アルゴリズムで、新しいサンプルのラベルを、そのサンプルに最も近い k 個のラベル付きサンプルから予測します。分類では近傍の多数決を使い、回帰では近傍の平均を使います。KNN はノンパラメトリックで「遅延型」のアルゴリズムです。重みを学習せず、学習データをそのまま保存し、予測が求められたときに処理を実行します。Evelyn Fix と Joseph Hodges が 1951 年にこの手法を導入し、1967 年には Thomas Cover と Peter Hart が、データが無限にある場合、最近傍ルールの誤り率は最良の分類器の 2 倍以下になることを証明しました。現在では同じ最近傍検索が、ベクトルデータベースや、ニューラルネットワークの埋め込みを比較する画像検索システムで大規模に実行されています。

KNN による予測の仕組み#

KNN はクエリ点ごとに、次の 3 つのステップを実行します。

1. 距離の測定: クエリから保存されているすべてのサンプルまでの距離を計算します。ユークリッド距離がデフォルトで、マンハッタン距離とミンコフスキー距離もよく使われます。また、ベクトルの向きが意味を持つ埋め込みでは、コサイン類似度が標準的です。
2. 近傍の選択: 距離が最も小さい k 個のサンプルを選びます。
3. ラベルの集約: 分類では近傍の中で最も多いクラスを選び、回帰では値の平均を取ります。距離による重み付け（scikit-learn の weights="distance"）では、近い近傍ほど大きな重みを持ちます。

すべての特徴量が距離に影響するため、スケールの大きい特徴量が支配的になります。たとえば、ドル単位の所得は年単位の年齢より大きな影響を与えます。そのため KNN のパイプラインでは、まず特徴量を標準化するか、特徴抽出モデルの埋め込みを比較して、各次元のスケールが同程度になるようにします。

k の選択#

k の値は、過学習と未学習のバランスを決めます。k = 1 では、ノイズや誤ラベルを含むすべての学習点がそれぞれ独自の領域を持つため、決定境界がぎざぎざになります。k が非常に大きいと、各投票がクエリから遠くまで及び、実際のクラス境界がぼやけます。2 クラスの場合、奇数の k を使えば投票が同数になるのを避けられます。k の選択には交差検証が標準的に使われます。scikit-learn のノイズを含む two-moons データセットでは、このトレードオフが 3 つの値に表れます。

from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier

# Two interleaving half-moons with overlapping, noisy points
X, y = make_moons(n_samples=1000, noise=0.35, random_state=0)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=0)

# Fitting only stores the points; each prediction is a vote among the k nearest ones
for k in (1, 15, 300):
    knn = KNeighborsClassifier(n_neighbors=k)
    knn.fit(X_train, y_train)
    print(f"k={k}: train {knn.score(X_train, y_train):.2f}, test {knn.score(X_test, y_test):.2f}")

k = 1 では分類器が学習点を記憶し、学習点で 1.00、保留データで 0.83 のスコアになります。k = 15 ではそれぞれ 0.90 と 0.89 となり、3 つの中で最良のテスト結果です。学習点 700 個のほぼ半数にあたる k = 300 では境界が平滑化され、両方のスコアが 0.84 と 0.81 に低下します。

近傍検索の高速化#

総当たり検索では、d 次元にある保存済みの n 個すべての点とクエリを比較するため、各予測にかかるコストは n × d の演算量となり、メモリ使用量はデータセットとともに増加します。k-d 木やボール木などの空間分割構造は、低次元では比較の大部分を省略できます。scikit-learn の algorithm="auto" は、総当たり、k-d 木、ボール木から手法を選択します。高次元では次元の呪いによって点間の距離がほぼ等しくなり、木の枝刈りが効果を失います。そのため大規模システムでは、HNSW グラフや、積量子化を使った転置ファイル（IVF）インデックスなどの近似最近傍（ANN）インデックスに切り替えます。これらは FAISS などのライブラリで実装されています。このようなインデックスは、保存済みベクトルのごく一部だけをクエリと比較しながら、真の最近傍の大部分を返します。

KNN と関連手法の比較#

• k-means クラスタリング: 学習済みの重心を中心に、ラベルのない点を k 個のクラスタに分類する教師なしアルゴリズムです。名称に同じ文字が含まれるのは偶然です。k-means の k はクラスタ数を表します。
• ベクトル検索: 同じ処理を検索に応用したもので、通常は近似インデックスを使って、クエリ埋め込みに最も近い保存済みアイテムを返します。アプリケーションはそれらのアイテムを直接利用します。
• サポートベクターマシンとロジスティック回帰: 学習時に決定境界を学習するパラメトリックモデルです。そのため、学習セットが大きくなっても予測コストは一定です。

実際のアプリケーション#

• レコメンデーションシステム: アイテムベースの協調フィルタリングでは、ユーザーがすでに好んだアイテムに評価ベクトルまたは購入ベクトルが最も近い商品を推薦します。
• 異常検知: 点から k 番目に近い近傍までの距離を異常スコアとして使うため、正常なサンプルのいずれからも遠い取引やセンサー値を検出できます。
• 欠損値補完: scikit-learn の KNNImputer は、類似度が最も高い k 行における各特徴量の平均値で欠損を埋めます。
• 画像検索と再識別: システムは画像の埋め込みをギャラリーと比較し、別のカメラで撮影された同じ商品、顔、人物を見つけます。Ultralytics の類似画像検索ソリューションは、OpenAI の CLIP で画像フォルダーを埋め込み、総当たりの正確な検索で「赤い車」などのテキストクエリとインデックス内の各画像とのコサイン類似度を計算し、デフォルトで最大 30 件の最近傍を返します。