面試算法（二）—KNN

  最近看了一下KNN相關内容，做下總結；大緻過一下李航的書中KNN的講解：統計學習方法中隻讨論了分類K近鄰法，先講了KNN的算法流程，KNN的模型實際上是對特征空間做了一次劃分，kd樹中的每個節點對應了k維空間劃分中的一個超矩形區域，KNN中用到了距離度量，使用的距離度量類型有Lp距離，這個明科夫斯基距離定義公式可以引申出曼哈頓距離，歐式距離和切比雪夫距離，随後講到了K值的選擇，過小則容易過拟合，過大則容易欠拟合，可以使用交叉驗證法選取k值，最後KNN的分類決策規則采用的是多數表決法，這等價于經驗風險最小化；随後講到了如何使用kd樹對資料進行快速的k近鄰搜尋，線性掃描過于耗時。構造kd樹主要注意一個公式，l = j mod k + 1；l是特征的第l次元，j是kd樹深度，l也是此深度對應的切分特征次元，kd樹的搜尋書中以最近鄰法為例，K近鄰基本差不多，注意遞歸搜尋的想法，對于随機分布的資料，kd樹搜尋的平均複雜度為O（logN），kd樹适用于訓練執行個體數遠大于空間次元的資料搜尋，最後舉了一個簡單的最近鄰kd樹構造搜尋的例子。

注：距離計算時特征次元可以設定權值，KNN回歸預測時可以對不同的點設定權值

K近鄰法(KNN)原理小結

非常流暢簡潔的一篇KNN總結，主要從sklearn的KNN原理出發，講了sklearn的kd樹和球樹實作方式，對KNN的擴充以及優缺點做了簡潔概括。

從K近鄰算法、距離度量談到KD樹、SIFT+BBF算法

這篇文章比較多的提到了距離度量的不同方式，kd樹的各種操作，不過依然是以k=1去舉例，同時列舉出了其它一些查找樹結構。

【數學】kd 樹算法之詳細篇

這篇文章詳細的介紹了kd樹的建構和搜尋流程，且K ≥ 1，不過文中的周遊思想先子節點後父節點再另一子節點的順序稍有疑問，應該是中序周遊的思想才對，父節點放在最後才對。文中的例子很詳細，可以在不明白的時候看看。

【量化課堂】scikit-learn 之 kNN 分類

這篇文章承接上篇，對sklearn中的KNN包調用做了詳細講解。

一文搞懂k近鄰（k-NN）算法（一）

這篇文章着重提到了特征歸一化對于KNN結果的影響，一般采用特征歸一化後的歐式距離作為距離度量，表述方式非常直白淺顯，易懂。

完結篇|一文搞懂k近鄰（k-NN）算法（二）

承接上篇，列舉了kd樹在最好和最壞情形下的例子，同時列出了KNN的部分優缺點和改進方法。

KNN算法與Kd樹

KNN的python實作，順帶撸了一遍KNN和kd樹的流程。

Kd-Tree算法原理和開源實作代碼

介紹了構造kd樹時特征分割為何采用最大方差選取對應次元特征而非順序選取特征的方式，同時提到了所求點與其它子空間距離的計算方式，很簡單的一進制減法，最後對基于BBF的近似查找方法進行介紹。

疑惑：Kd-Tree：資料隻存放在葉子結點，而根結點和中間結點存放一些空間劃分資訊（例如劃分次元、劃分值）？

基礎-12：15分鐘了解KD樹

比較簡短但較正式的介紹了kd樹的建構和查詢算法，疑惑時可以看下裡面的僞代碼。

kNN 小結

主要是KNN的優缺點和優化方法。

《Machine Learning：Regression》課程第6章KNN-Regression & Kernel Regression & non-parametric問題集

對KNN做回歸的一些問題解釋