MLlearning（1）——kNN算法
來自： http://www.cnblogs.com/Darksun/p/5170014.html
這篇文章講kNN（k近鄰， k -Nearest Neighbour）。這是一種lazy-learning，實現方便，很常用的分類方法。約定n為樣本集中的樣本數，m為樣本的維度，則這個算法的訓練復雜度為0，未加優化（線性掃描）的分類時間復雜度為 
，kd-Tree優化后復雜度可降為 
。
思路、優點及缺陷
該方法的思路是：如果一個樣本在特征空間中的 k 個最相似即特征空間中最鄰近)的樣本中的大多數屬于某一個類別，則該樣本也屬于這個類別。k NN 算法中，所選擇的鄰居都是已經正確分類的對象。該方法在分類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。
該方法在處理 多分類問題（multi-modal,對象具有多個類別標簽）時，表現比SVM的要好，而且是最簡單的分類方法，無需訓練。
該方法對于樣本的要求較高，不能給出數量不均衡的樣本，否則會出現大容量的樣本填充了選取的k個樣本中的多個，而這些樣本距離輸入對象的特征距離其實是很遠的。對于這種極端情況，在沒辦法獲得更多樣本情況下，可以通過加權的WAkNN (weighted adjusted k nearest neighbor)解決。另外，這種方法的時間復雜度較高，且kd-Tree會在維數高時（一般是當m>10時）遭遇維數災難（Curse of Dimensionality），時間復雜度退化至線性掃描（由于常數問題，實際耗時會比線性掃描更高）。
Lua實現
為了方便起見，通常把特征空間看做一個歐式空間。兩個向量之間的距離可由歐氏距離公式直接得出： 
有了這個假設，就可以直接把特征作為向量處理，進行kNN的計算。
這里筆者用Lua簡單實現了樸素的kNN算法，源碼托管于github，其中還包括手寫數字識別的Demo： https://github.com/Darksun2010/MLlearning/tree/master/kNN
實驗——測試算法速度及正確率
在git上clone代碼后，載入其中識別數字的Demo。調用其中函數 testkNN() ，會測試此Demo，返回兩個值：樣本總數及錯誤率。
筆者電腦上的結果如下(k=3)：
>print(testkNN())
answer of kNN: 0 , correct answer: 0
...
answer of kNN: 9 , correct answer: 9
946 0.011627906976744
錯誤率僅為約1.2%，相當不錯的成績！經試驗，k=3對于這個樣本集是最好的選擇。另外，我選擇用Lua語言實現它的原因有三：
- 我喜歡Lua
- Lua嵌入性強
- LuaJIT的執行效率比Python/CPython高好幾個數量級，直逼C/C++的執行效率！
后記
kNN只是個開始，我會寫更多的文字，介紹更多的機器學習算法。
</div>