kNN算法大概是機器學(xué)習(xí)相關(guān)算法中最容易理解的算法了。這篇文章的目的大概是介紹一下kNN算法，介紹一下其錯誤率的推導(dǎo)，以及論文中的精確推導(dǎo)。大概是這三個方面。

kNN算法介紹

kNN（k nearest neighbor）算法的就用下面的圖來介紹好了。

kNN

從上圖中我們可以看到，圖中的有兩個類型的樣本數(shù)據(jù)，一類是藍色的正方形，另一類是紅色的三角形。而那個綠色的圓形是我們待分類的數(shù)據(jù)。

• 如果K=3，那么離綠色點最近的有2個紅色三角形和1個藍色的正方形，這3 個點投票，于是綠色的這個待分類點屬于紅色的三角形。
• 如果K=5，那么離綠色點最近的有2個紅色三角形和3個藍色的正方形，這5個點投票，于是綠色的這個待分類點屬于藍色的正方形。
  這個算法體現(xiàn)了當(dāng)前主流機器學(xué)習(xí)算法的核心，基于統(tǒng)計。

注意

這里需要注意的地方有兩個

k的選取

從上圖也可以看出來，對于不同的k值，結(jié)果可能大不相同，因此，具體選取哪幾個值，需要根據(jù)你的數(shù)據(jù)集來確定。

距離度量

• 曼哈頓距離
• 歐幾里得距離
• L1距離
• ...

改進方法

我們看這樣一張圖，雖然每一類分布相對集中。但是偏離分類中心的點會對結(jié)果造成影響。

考慮到這個問題，我們?yōu)槊總€樣本的到測試樣本的距離增加權(quán)重，距離越遠權(quán)重越低。

錯誤率推導(dǎo)（大致）

推導(dǎo)過程來自周志華老師的《機器學(xué)習(xí)》
給定測試樣本x，若最近樣本為在， 分類器出錯的概率就是與z不同的概率。即

假設(shè)樣本獨立同分布，對任意x和任意小的整數(shù) \delta ,在x附近\delt 距離內(nèi)總能找到一個訓(xùn)練樣本。即任意測試樣本任意近的距離內(nèi)總能相應(yīng)的訓(xùn)練樣本z。令

即其泛化誤差不超過貝葉斯分類器的兩倍。（關(guān)于貝葉斯分類器，后面的文章再做分析）。

論文中的推導(dǎo)以及介紹

todo