Knn算法三個要素包括什么？

一 三大要素

KNN算法三大要素：K值的選擇，距離向量，以及分類規則。

KNN屬于懶惰學習算法，不需要訓練過程。既可以分類，也可以進行回歸分析。

（1）K值的選擇會對算法的結果產生重大影響。K值較小意味著只有與輸入實例較近的訓練實例才會對預測結果起作用，但容易發生過擬合；如果 K 值較大，優點是可以減少學習的估計誤差，但缺點是學習的近似誤差增大，這時與輸入實例較遠的訓練實例也會對預測起作用，是預測發生錯誤。在實際應用中，K 值一般選擇一個較小的數值，通常采用交叉驗證的方法來選擇最有的 K值。隨著訓練實例數目趨向于無窮和 K=1 時，誤差率不會超過貝葉斯誤差率的2倍，如果K也趨向于無窮，則誤差率趨向于貝葉斯誤差率。

（2）該算法中的分類決策規則往往是多數表決，即由輸入實例的 K 個最臨近的訓練實例中的多數類決定輸入實例的類別，對應于經驗風險最小化。

（3）距離度量一般采用 Lp 距離，當p=2時，即為歐氏距離，在度量之前，應該將每個屬性的值規范化，這樣有助于防止具有較大初始值域的屬性比具有較小初始值域的屬性的權重過大。

二 優化方法

實現K近鄰，主要考慮的問題是如何對訓練數據進行快速K近鄰搜索。這點在特征空間維數大以及訓練數據量大的時候，尤其重要。一種解決方式就是KD樹。

KD樹是一種對K維空間中的實例點進行存儲以便對其進行快速檢索的樹形數據結構，KD樹是一顆二叉樹，表示對K維空間的一個劃分。時間復雜度為O(logn)。

KNN是基于準確率的，不需要訓練過程。