李航統計學習方法-K鄰近法

k鄰近簡單的理解一下就是，給定一部分帶標籤樣本和一個未知標籤樣本，將未知標籤樣本和帶標籤樣本一一比較求距離，然後根據最近k個樣本來決定未知標籤樣本的類別。

如上圖：確定圓圈的類別，如K=3，則爲三角；若K=5，則爲正方形。

那麼怎麼求距離？選擇何種求距離算法。
書中給出了Lp距離的求解：

除了距離度量外，K鄰近法的K值如何選取也很重要，書中介紹如下：

K值較小，模型較複雜，易過擬合；K值較大，模型簡單。

按照開始我說了，用未知樣本和已知樣本一一對比方法，在樣本數很大時，會花費很多很多時間，有沒有一種策略，來加速這種對比呢：下面就要將書中提到的KD樹。
構建平衡KD樹：

KD樹搜索：

除了KD樹這種方式還有其他的加速方式：先要詳細瞭解的見：
http://www.cnblogs.com/v-July-v/archive/2012/11/20/3125419.html
上述鏈接詳細講解了knn算法中的距離度量和k鄰近優化方法。
理論永遠都在紙上，怎麼用纔是關鍵，python代碼鏈接奉上：
http://blog.csdn.net/wds2006sdo/article/details/51933044