算法簡介
給定一個(gè)訓(xùn)練數(shù)據(jù)集钝吮，對(duì)新的輸入實(shí)例秕衙，在訓(xùn)練數(shù)據(jù)集中找到與該實(shí)例最鄰近的k個(gè)實(shí)例止状，這k個(gè)實(shí)例的多數(shù)屬于某個(gè)類吱殉，就把該輸入實(shí)例分為這個(gè)類。
模型由三個(gè)基本要素決定： 距離度量珊拼、K值的選擇食呻、分類決策規(guī)則。
距離度量
Lp距離定義
二維空間中p取不同值時(shí)澎现，Lp=1的點(diǎn)的圖形
K值的選擇
K值過小仅胞，會(huì)對(duì)近鄰的實(shí)例點(diǎn)非常敏感，容易發(fā)生過擬合剑辫；
K值過大干旧，與輸入實(shí)例較遠(yuǎn)的訓(xùn)練實(shí)例也會(huì)對(duì)預(yù)測(cè)起作用，如果k=N,則預(yù)測(cè)為訓(xùn)練實(shí)例最多的類妹蔽，不可取椎眯。
應(yīng)用中，k值一般取一個(gè)比較小的值胳岂，采用交叉驗(yàn)證法選取最優(yōu)k值编整。
分類決策規(guī)則
多數(shù)表決規(guī)則，即由輸入實(shí)例的k個(gè)臨近的訓(xùn)練實(shí)例中的多數(shù)類決定輸入實(shí)例的類乳丰。
算法實(shí)現(xiàn)
構(gòu)造kd樹
以二維空間為例掌测，給定數(shù)據(jù)集
1、X(1)軸中位數(shù)為7产园，以平面X(1)=7將空間分為左右兩個(gè)子矩形（子節(jié)點(diǎn)）汞斧；
2、左矩形以X(2)=4分為兩個(gè)子矩形淆两，右矩形以X(2)=6分為兩個(gè)子矩形断箫；
3、如此遞歸秋冰，得到如下kd樹仲义。
搜索kd樹
1、在kd樹中找到包含點(diǎn)S的葉節(jié)點(diǎn)D，則最近鄰點(diǎn)在以S為圓心通過D的園內(nèi)埃撵；
2赵颅、返回父節(jié)點(diǎn)B，B的另一子節(jié)點(diǎn)F與圓不相交暂刘，不可能有最近鄰點(diǎn)饺谬；
3、返回上一級(jí)父節(jié)點(diǎn)A谣拣，A的另一子節(jié)點(diǎn)C與圓相交募寨，該區(qū)域有在圓內(nèi)的E，E成為新的最近鄰點(diǎn)森缠。
