K近鄰算法（K-Nearest Neighbors, KNN）詳解及案例

一、基本原理

K近鄰算法是一種監督學習算法，核心思想是“物以類聚，人以群分”：對于一個新樣本，通過計算它與訓練集中所有樣本的“距離”，找出距離最近的K個樣本（即“近鄰”），再根據這K個近鄰的標簽（分類問題）或數值（回歸問題）推斷新樣本的結果。

KNN屬于“惰性學習（Lazy Learning）”，它沒有顯式的“訓練過程”，不會提前構建模型，而是在預測時直接依賴訓練數據進行計算，因此也被稱為“實例-based學習”。

二、核心要素與關鍵步驟

1. 距離度量

距離用于衡量樣本間的相似性，距離越小，樣本越相似。常用的距離度量包括：

• 歐氏距離（最常用）：適用于連續特征，計算n維空間中兩個點的直線距離。
  公式：對于樣本$x=(x_1,x_2,...,x_n)$和$y=(y_1,y_2,...,y_n)$，歐氏距離為：
  $$d(x,y)=\sqrt{\sum _{i=1}^n(x_i?y_i{)}^2}$$

• 曼哈頓距離：適用于高維數據，計算坐標軸上的“城市街區距離”。
  公式：$d(x,y)={\sum }_{i=1}^n|x_i?y_i|$

• 余弦相似度：適用于高維稀疏數據（如文本），衡量向量方向的相似性（與模長無關）。
  公式：$\cos \theta =\frac{x?y}{||x||?||y||}=\frac{{\sum }_{i=1}^n{x}_i{y}_i}{\sqrt{{\sum }_{i=1}^n{x}_i^2}?\sqrt{{\sum }_{i=1}^n{y}_i^2}}$

2. K值選擇

K值是KNN的核心超參數，直接影響預測結果：

• K值過小：近鄰數量少，易受噪聲樣本影響，導致“過擬合”（模型對訓練數據太敏感）。
• K值過大：近鄰包含過多無關樣本，導致“欠擬合”（模型忽略局部特征，偏向全局平均）。
• 常見選擇：通常取奇數（避免投票平局），如3、5、7等；實際應用中通過交叉驗證（如5折交叉驗證）選擇最優K值。

3. 決策規則

• 分類問題：對K個近鄰的標簽進行“多數投票”（少數服從多數），得票最多的標簽即為新樣本的預測類別。
• 回歸問題：對K個近鄰的數值取“平均值”（或加權平均值），作為新樣本的預測值。

4. 核心步驟

1. 確定距離度量方式（如歐氏距離）和K值；
2. 計算新樣本與訓練集中所有樣本的距離；
3. 按距離從小到大排序，選取前K個樣本作為“近鄰”；
4. 根據K個近鄰的標簽（分類）或數值（回歸），得到新樣本的預測結果。

三、優缺點

優點

• 簡單直觀：無需復雜的模型訓練，原理易懂，實現難度低；
• 適應性強：可處理非線性數據，對特征分布無嚴格假設；
• 擴展性好：可通過優化距離計算（如KD樹、球樹）提升效率。

缺點

• 計算成本高：預測時需與所有訓練樣本計算距離，樣本量過大時速度慢；
• 對不平衡數據敏感：若某類樣本占比極高，K近鄰易被其主導；
• 對噪聲和異常值敏感：離群點可能被誤判為“近鄰”，影響預測結果；
• 依賴距離度量：高維數據中“距離”的意義會弱化（維度災難）。

四、案例詳情（分類問題：電影類型預測）

問題描述

已知4部電影的特征（搞笑鏡頭數、打斗鏡頭數）和標簽（喜劇片/動作片），預測一部新電影的類型。

訓練數據

電影ID	搞笑鏡頭數（特征1）	打斗鏡頭數（特征2）	標簽
A	30	10	喜劇片
B	20	5	喜劇片
C	5	40	動作片
D	10	30	動作片

新樣本

待預測電影E：搞笑鏡頭數=25，打斗鏡頭數=20，需預測其類型。

預測步驟

步驟1：確定參數

選擇歐氏距離作為度量方式，K=3（奇數，避免平局）。

步驟2：計算新樣本與訓練樣本的距離

電影E（25,20）與A、B、C、D的歐氏距離：

• 與A（30,10）的距離：$\sqrt{(25?30{)}^2+(20?10{)}^2}=\sqrt{(?5{)}^2+10^2}=\sqrt{25+100}=\sqrt{125}\approx 11.18$
• 與B（20,5）的距離：$\sqrt{(25?20{)}^2+(20?5{)}^2}=\sqrt{5^2+15^2}=\sqrt{25+225}=\sqrt{250}\approx 15.81$
• 與C（5,40）的距離：$\sqrt{(25?5{)}^2+(20?40{)}^2}=\sqrt{20^2+(?20{)}^2}=\sqrt{400+400}=\sqrt{800}\approx 28.28$
• 與D（10,30）的距離：$\sqrt{(25?10{)}^2+(20?30{)}^2}=\sqrt{15^2+(?10{)}^2}=\sqrt{225+100}=\sqrt{325}\approx 18.03$

步驟3：排序并選K=3個近鄰

距離從小到大排序：
A（11.18）→ B（15.81）→ D（18.03）→ C（28.28）
前3個近鄰為：A、B、D。

步驟4：多數投票

• 近鄰A的標簽：喜劇片；
• 近鄰B的標簽：喜劇片；
• 近鄰D的標簽：動作片；
• 投票結果：喜劇片（2票）＞動作片（1票）。

預測結果

電影E被預測為喜劇片。

五、總結

KNN是一種基于“相似性”的簡單算法，核心依賴距離度量和K值選擇。盡管存在計算成本高的問題，但因其直觀性和適應性，在推薦系統、圖像識別、文本分類等領域仍被廣泛應用（如推薦系統中“相似用戶喜歡的商品”推薦）。實際使用時需注意優化樣本量和距離計算，以提升效率。