AI 摘要

K-近鄰演算法理論（K-Nearest Neighbors, KNN）

摘要

K-近鄰演算法（K-Nearest Neighbors, KNN）是一種非參數式（non-parametric）、實例為基礎（instance-based）的監督式學習方法，廣泛應用於分類（classification）與回歸（regression）問題。其核心思想並非建立顯式模型，而是透過樣本間的距離關係，對未知樣本的輸出進行局部推論。本文從理論定位出發，系統性整理 KNN 的數學觀點、方法流程與其在統計學與機器學習中的角色。

背景

在監督式學習中，多數方法嘗試學得一個參數化模型以近似輸入與輸出之間的映射關係；相對地，KNN 採取一種極端策略：不進行顯式建模。
對於查詢點 $x$，KNN 直接在訓練資料中搜尋與其最相近的樣本，並根據這些鄰近樣本的標記進行預測。

此特性使 KNN 成為理解「資料驅動推論（data-driven inference）」與「局部估計（local estimation）」的重要基準方法。

條件經驗分佈（conditional empirical distribution）

在有限樣本下，KNN 對 $P(Y \mid X=x)$ 的推論本質上是一種局部條件經驗分佈（conditional empirical distribution） 近似，因此結果依賴鄰域內有限觀測值，並非真實母體分佈。

$$P(Y \mid X=x)$$

問題設定

給定一組訓練資料集

$$\mathcal{D} = \{(x_i, y_i)\}_{i=1}^n, \quad x_i \in \mathbb{R}^d, \; y_i \in \mathcal{Y}$$

其中 $x_i \in \mathbb{R}^d$ 表示特徵維度，$y_i$ 為對應標記。

距離函數（Distance Function）

歐氏距離（Euclidean distance）

$$d(x, x') = \sqrt{\sum_{i=1}^{d}(x_i - x'_i)^2}$$

曼哈頓距離（Manhattan distance）

$$d(x, x') = \sum_{i=1}^{d}|x_i - x'_i|$$

更詳細的距離函數理論可以參考 https://renode.site/articles/artificial-intelligence/AI20250016

鄰居選取

根據 $x$ 與所有訓練樣本之間的向量距離計算，並選取距離最小的 $k$ 個樣本作為鄰居集合 $\mathcal{N}_k(x)$。

預測規則

• 在分類任務中，KNN 通常採用多數決機制

• 在回歸任務中，則使用鄰居標記的平均值作為預測結果

Hyperparameter

KNN 的超參數為鄰居數 $k$，反映了偏差與變異之間的權衡（bias–variance trade-off）

• $k$ 較小時，模型高度依賴局部樣本，易產生高變異

• $k$ 較大時，鄰域擴張，局部特性被平滑，偏差上升