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

一 三大要素

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

KNN屬于懶惰學(xué)習(xí)算法，不需要訓(xùn)練過程。既可以分類，也可以進行回歸分析。

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

（2）該算法中的分類決策規(guī)則往往是多數(shù)表決，即由輸入實例的 K 個最臨近的訓(xùn)練實例中的多數(shù)類決定輸入實例的類別，對應(yīng)于經(jīng)驗風(fēng)險最小化。

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

二 優(yōu)化方法

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

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

KNN是基于準確率的，不需要訓(xùn)練過程。