82.k最近邻分类.md

k最近鄰分類

$k$最近鄰（簡稱kNN，k-Nearest Neighbor）是Cover和Hart在1968年提出的一種簡單的監督學習演算法，可用於字元識別、文字分類、影象識別等領域。kNN的工作機制非常簡單：給定測試樣本，基於某種距離度量（如：歐式距離、曼哈頓距離等）找出訓練集中與其最接近的$k$個訓練樣本，然後基於這$k$個“最近鄰居”的資訊來進行預測。對於分類任務，可以在$k$個最近鄰居中選擇出現次數最多的類別標籤作為預測的結果；對於迴歸任務，可以使用$k$個最近鄰居實際輸出（目標值）的平均值作為預測的結果，當然也可以根據距離的遠近進行加權平均，距離越近的樣本權重值就越大。

案例：電影分類預測

k值的選擇和交叉檢驗

k值的選擇對於kNN演算法的結果有非常顯著的影響。下面用李航博士的《統計學習方法》一書中的敘述，來對k值的選擇加以說明。

如果選擇較小的$k$值，就相當於用較小的鄰域中的訓練例項進行預測，“學習”的近似誤差會減小，只有與輸入例項較近（相似的）訓練例項才會對預測結果起作用；但缺點是“學習”的估計誤差會增大，預測結果會對近鄰的例項點非常敏感，如果近鄰的例項點剛好是噪聲，預測就會出錯。換句話說，$k$值的減小就意味著整體模型變得複雜，容易發生過擬合。

如果選擇較大的$k$值，就相當於用較大的鄰域中的訓練例項進行預測，其優點是可以減少學習的估計誤差，但缺點是學習的近似誤差會增大。這時候，與輸入例項較遠（不相似的）訓練例項也會對預測起作用，使預測發生錯誤。對於$k=N$的極端情況（其中$N$代表所有的訓練例項的數量），那麼無論輸入例項是什麼，都會預測它屬於訓練例項中最多的類，很顯然，這樣的模型完全忽略了訓練例項中大量的有用資訊，是不可取的。

實際應用中，$k$的取值通常都比較小，可以透過交叉檢驗的方式來選擇較好的$k$值。

演算法優缺點

優點：

1. 簡單有效
2. 重新訓練代價低
3. 適合類域交叉樣本
4. 適合大樣本分類

缺點：

1. 惰性學習
2. 輸出的可解釋性不強
3. 不擅長處理不均衡樣本
4. 計算量比較大