k近鄰法（k-nearest neighbor，k-nn），這裡隻讨論基于knn的分類問題，1968年由cover和hart提出，屬于判别模型
k近鄰法不具有顯式的學習過程，算法比較簡單，每次分類都是根據訓練集中k個最近鄰，通過多數表決的方式進行預測。是以模型需要保留所有訓練集資料，而象感覺機這樣的模型隻需要儲存訓練後的參數即可，訓練集不需要保留
k近鄰算法
k近鄰法三要素
和其他統計學習方法不同的，k近鄰法的三要素是，k值的選擇，距離度量和分類決策規則
距離度量
首先如何定義“近”？需要通過距離度量，比如最常見的歐氏距離
下面這個比較清楚，歐氏距離隻是p=2的case，也稱為l2距離
k值的選擇
選取比較小的k值（較複雜的模型），近似誤差（approximation error）會減小，而估計誤差（estimation error）會增大，因為影響分類的都是比較近的樣本，但一旦出現噪點，預測就會出錯
選取比較大的k值（較簡單的模型），相反，減小噪點的影響，但是較遠或不相似的樣本也會對結果有影響，極限情況下k=n，考慮所有樣本，極簡模型
k一般會選取比較小的值，通常采用交叉驗證來選取最優的k值
分類決策規則
往往采用多數表決，但是也可以采用其他的政策
kd樹
對于knn有個根本問題是，當訓練集比較大時，線性的掃描效率是很低的，需要更為高效的方法來找到k近鄰，這裡介紹的kd數是二叉樹，其實就是以二分的方式查找，将複雜度由n變小為logn。
那麼關鍵問題就是，如何能夠二分的索引訓練點和給定任意一個點如何從kd樹中找到最近鄰？
構造kd樹
基本思路，循環的以k維空間中的每一維對訓練資料進行劃分
劃分标準，往往是使用訓練集在該維上的中位數進行劃分，具體看下下面的例子
使用中位數可以保證樹是平衡的，但不一定效率最優
例子，
首先用x維劃分，中位數為7，(7,2)放在節點上
(2,3) (4,7) (5,4)劃分到左子樹，而(8,1) (9,6)劃分到右子樹
然後用y維進行劃分，
對于左邊區域，y維的中位數為4，(4,7)放在節點上，(2,3) (5,4)分布劃分到兩個子樹
對于右邊區域，y維的中位數為6。。。
然後再用x維進行劃分。。。
搜尋kd樹
對于搜尋k鄰近，就是k次搜尋最鄰近，是以直接看下最鄰近的搜尋算法
例子學習，
首先找到包含s的那個葉節點，這裡是d，那麼以sd為半徑畫個圓，有可能包含更近節點的區域一定會和這個圓相交，相交不一定有，但不相交一定沒有
是以下面做的隻是往根節點回溯，
首先b，b本身不是更近的節點，而b的另一個子節點f的區域和圓不相交
繼續回溯到a，a不是，但a的另一個子節點c的區域是和圓相交的
是以需要checka的c節點，c本身不是，g的區域不相交，但e的區域相交
并且e到s的距離更近，故e是最鄰近節點
本文章摘自部落格園，原文釋出日期：2014-03-18