1.基本做法：對給定的訓練實例點和輸入實例點，首先確定輸入實例點的k個最近鄰訓練實例點，然后利用這k個訓練實例點的類的多數(shù)來預(yù)測輸入實例點的類坪圾。
2.k近鄰模型對應(yīng)于基于訓練數(shù)據(jù)集對特征空間的一個劃分致稀。k近鄰法中，當訓練集稼稿、距離度量薄榛、k值以及分類決策規(guī)則確定后，其結(jié)果唯一確定让歼。
3.k近鄰法三嚴肅：距離度量敞恋、k值的選擇和分類決策規(guī)則。
4.k近鄰法的實現(xiàn)需要考慮如何快速搜索k個最近鄰點是越。
3.1 k近鄰算法
3.2 k近鄰模型
3.2.1 模型
單元（cell）：在特征空間中耳舅，對每個訓練實例點xi，距離該點比其他點更近的所有點組成的區(qū)域倚评。每個訓練實例點擁有一個單元浦徊，所有訓練實例點的單元構(gòu)成對特征空間的一個劃分。
3.3.2 距離度量
距離：兩個實例點相似程度的反映天梧。歐氏距離盔性、Lp距離、Minkowski距離呢岗。
3.2.3 k值的選擇
k值過忻嵯恪：approximation error會減小，estimation error會增大后豫，預(yù)測結(jié)果對近鄰的實例點敏感悉尾，容易過擬合
k值過大：estimation error會減小，approximation error會增大挫酿。
通常采用交叉驗證法選取最優(yōu)的k值
3.2.4 分類決策規(guī)則
3.3 k近鄰法的實現(xiàn)：kd樹
對訓練數(shù)據(jù)進行快速k近鄰搜索
3.3.1 構(gòu)造kd樹
kd樹是二叉樹构眯，表示對k維空間的一個劃分。構(gòu)造kd樹相當于不斷地用垂直于坐標軸的超平面將k維空間切分早龟，構(gòu)成一系列的k維超矩形區(qū)域惫霸。kd樹的每個結(jié)點對應(yīng)于一個k維超矩形區(qū)域。
3.3.2 搜索kd樹
若實例點隨機分布葱弟，則kd樹搜索平均復雜度維O(logN)壹店。
kd樹更適用于訓練實例數(shù)遠大于空間維數(shù)的k近鄰搜索。
