k-近鄰算法介紹

  k-近鄰算法是一種簡單的算法，基本的算法思想是通過相似性的比較，最終得到最相似的k類中最為相似的。

  在k-近鄰算法中有幾個很重要的地方：第一是k的取值，其實k的取值就是模型的選擇，模型的選擇可以采用交叉驗證的方式或者通過正則化的方式，顯然這里是 采用交叉驗證的方式。第二點就是實例的距離度量。第三是分類決策規則的選取。kNN唯一的也可以說最致命的缺點就是判斷一篇新文檔的類別時，需要把它與現 存的所有訓練文檔全都比較一遍，這個計算代價并不是每個系統都能夠承受的 （比如我將要構建的一個文本分類系統，上萬個類，每個類即便只有20個訓練樣本，為了判斷一個新文檔的類別，也要做20萬次的向量比較！）。一些基于 kNN的改良方法比如Generalized Instance Set就在試圖解決這個問題。

    k-近鄰算法簡單、直觀：給定一個訓練數據集，對新的輸入實例，在訓練數據集中找到與該實例最鄰近的k個實例，這k個實例的多數屬于某個類，就把該輸入實例分為這個類

  算法如下所示：

    上文提到的k值的選取：k值如果選擇過小，就相當于用較小的鄰域實例進行預測，這樣會減小近似誤差，但是同時也會使得模型對鄰域實例變得異常敏感，如果鄰 域實例恰巧是噪聲，那該實例被分錯的可能性就會變得異常大（增大了估計誤差）。換句話說，較小的k值會使得模型變得復雜，容易發生過擬合現象。

    k值選取過大，離預測實例較遠的數據也會起作用，估計誤差會減少，但是這會增加結果的近似誤差，使 預測發生錯誤。k值的增大意味著模型會變得較為簡單。在實際應用中，K 值一般選擇一個較小的數值，通常采用交叉驗證的方法來選擇最有的 K 值。隨著訓練實例數目趨向于無窮和 K=1 時，誤差率不會超過貝葉斯誤差率的2倍，如果K也趨向于無窮，則誤差率趨向于貝葉斯誤差率。

   距離度量：特征空間中兩個實例點的距離是兩個實例點相似程度的反映，kNN模型的特征空間一般是n維實數向量空間Rn。距離計算方法：歐式距離、Lp距離或Minkowski距離等。

   分類決策規則：該算法中的分類決策規則往往是多數表決，即由輸入實例的 K 個最臨近的訓練實例中的多數類決定輸入實例的類別。

    k緊鄰算法的實現需要考慮如何快速搜索k個最近鄰點。kd樹是一種便于對k維空間的中的數據進行快速檢索的數據結構。kd樹是一種二叉樹，表示對k維空間 的一個劃分，其每個節點對應于k維空間劃分中的一個超矩形區域。利用kd樹可以省去對大部分數據點的搜索，從而減少搜索的計算量。

kd tree的構造：

kd tree的最近鄰搜索：