Python 100 Days Day82 Introduction to KNN

author: jackfrued

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. 計算量比較大