1. 算法
KNN算法也是使用距離來衡量樣本點之間的相似性，但其與Kmeans中的K含義不同诗良。
KNN的決策過程：
1嚷兔、計算測試集樣本點到訓(xùn)練集中每個樣本點的距離
2垃你、按照距離的遠近排序
3、選取與當(dāng)前測試樣本最近的K個訓(xùn)練樣本缭嫡，作為該測試樣本的鄰居
4缔御、統(tǒng)計這K個鄰居的類別頻率，即為該測試樣本的類別
如果每個測試樣本點都要計算一遍到所有訓(xùn)練集的距離妇蛀，再加上排序耕突，時間復(fù)雜度為o(Bn*Tn*ln(Bn))笤成，因此一般使用kd樹來降低時間復(fù)雜度，建樹時間復(fù)雜度為o(n)眷茁，具體參考文末鏈接疹启。
2. 優(yōu)缺點
2.1、優(yōu)點：
理論成熟蔼卡，思想簡單喊崖，既可以用來做分類也可以用來做回歸；
可用于非線性分類雇逞；
訓(xùn)練時間復(fù)雜度為O(n)荤懂；
對數(shù)據(jù)沒有假設(shè)，準(zhǔn)確度高塘砸，對outlier（異常值）不敏感节仿；
2.2、缺點
屬于懶惰算法掉蔬，時間復(fù)雜度較高廊宪，因為需要計算未知樣本到所有已知樣本的距離
樣本平衡度依賴高，當(dāng)出現(xiàn)極端情況樣本不平衡時女轿，分類絕對會出現(xiàn)偏差箭启，可以調(diào)整樣本權(quán)值改善
可解釋性差，無法給出類似決策樹那樣的規(guī)則
向量的維度越高蛉迹，歐式距離的區(qū)分能力就越弱
樣本空間太大不適合傅寡，因為計算量太大，預(yù)測緩慢
需要大量的內(nèi)存北救；
在訓(xùn)練集較小時荐操，泛化能力很差，非常容易陷入過擬合珍策。
無法判斷特征的重要性托启。
鏈接
k近鄰法的原理與實現(xiàn)
https://blog.csdn.net/beckham999221/article/details/80135042
https://blog.csdn.net/weixin_44508906/article/details/90116509
KD樹簡介
https://zhuanlan.zhihu.com/p/53826008
KNN算法和kd樹詳解（例子+圖示）（例子最詳細）
