K 近鄰演算法 是什麼？

KNN：K 近鄰演算法 的完整解釋

K 近鄰演算法（K-Nearest Neighbors, KNN）是一種非參數式監督學習演算法，透過尋找訓練集中距離最近的 K 個樣本進行多數投票（分類）或加權平均（回歸），無需建立顯式的模型參數。

核心概念

KNN 基於一個簡單的幾何直覺：在特徵空間中，相近的資料點往往屬於同一類別或具有相似的數值。演算法的核心思想是「讓訓練資料自己說話」，預測時不依賴學習到的模型參數，而是直接查找最相似的訓練樣本。

KNN 屬於非參數方法（Non-parametric Method），不對資料分布做任何假設，也不學習顯式的決策邊界。同時也是懶惰學習（Lazy Learning）方法，訓練階段幾乎不做計算，代價是推論階段需要遍歷全部訓練資料。

運作原理

距離度量

KNN 的核心操作是計算查詢點與訓練集中每個點的距離。常用距離度量包括：

• 歐氏距離（Euclidean Distance）：最常用，適合連續數值特徵
• 曼哈頓距離（Manhattan Distance）：在高維空間或稀疏特徵時較穩健
• 餘弦相似度（Cosine Similarity）：適合文字向量等方向比大小更重要的場景
• 漢明距離（Hamming Distance）：適合類別型或二元特徵

K 值的作用

K 是 KNN 中最重要的超參數：

• K = 1：決策邊界最曲折，對雜訊最敏感，容易過擬合
• K 較大：決策邊界更平滑，偏差增加，方差減少（類似正則化效果）
• K = N（全部訓練樣本）：退化為直接預測訓練集的多數類別，欠擬合

通常透過交叉驗證選擇最佳 K，K 為奇數可避免二分類時的平票問題。

分類與回歸

分類：K 個近鄰中，出現最多的類別標籤即為預測結果（多數投票）。可採用加權投票，距離較近的鄰居具有較高權重。

回歸：取 K 個近鄰的目標值平均值（或加權平均）作為預測輸出。

計算效率問題

樸素 KNN 的預測時間複雜度為 O(n × d)（n 為訓練樣本數，d 為特徵維度），在大規模資料集上效率低落。實務上常使用：

• KD-Tree：在低維空間（d < 20）能加速近鄰搜尋至 O(log n)
• Ball Tree：對高維資料優於 KD-Tree
• 近似近鄰搜尋（ANN）：如 FAISS、HNSW，以少量精度損失換取大幅速度提升，廣泛用於向量資料庫和推薦系統

實際應用

推薦系統

協作過濾（Collaborative Filtering）的核心即 KNN 思想：找到與目標用戶最相似的 K 個用戶，推薦他們喜歡但目標用戶尚未接觸的項目。用戶間的相似度通常以消費記錄的餘弦相似度衡量。

醫療診斷

KNN 用於根據患者的症狀和檢測指標，在歷史病例中尋找最相似的案例輔助診斷。由於 KNN 直觀可解釋（「根據 5 個最相似患者的病例判斷」），在醫療場景的可信度較高。

向量資料庫

大型語言模型的檢索增強生成（RAG）架構依賴向量資料庫進行語意搜尋，其核心操作本質上是近似 K 近鄰搜尋（ANN）：將查詢轉為嵌入向量，在向量庫中找出語意最相似的 K 個文件片段。

異常偵測

若一個新資料點與 K 個最近鄰的距離都很大，代表它與訓練資料中任何已知模式都不相似，可被視為異常點。這種方式稱為基於距離的異常偵測。

常見誤區

誤區一：KNN 不需要特徵縮放

KNN 基於距離計算，對特徵量綱極為敏感。若特徵 A 的取值範圍為 [0, 1000]，特徵 B 的取值範圍為 [0, 1]，距離將幾乎完全由特徵 A 主導。MUST 在使用 KNN 前進行 Min-Max 正規化或 Z-score 標準化。

誤區二：K 越大效果越好

K 值增大能降低過擬合風險，但同時增加偏差。K 太大時，決策邊界過於平滑，模型喪失對局部結構的感知能力。最佳 K 值應透過驗證集或交叉驗證確定，而非直接設大。

誤區三：KNN 無法處理高維資料

維度詛咒（Curse of Dimensionality）確實使 KNN 在高維空間中效果下降，但透過先進行降維（PCA、UMAP）或採用近似近鄰搜尋（ANN）結合適當距離度量，KNN 在高維嵌入空間（如文字嵌入）仍有廣泛應用。

與相關技術的比較

常見問題