k-nn在軌跡數(shù)據(jù)采樣率合適的情況下嚷往，用于路網(wǎng)映射的子流程中岖免；下面將介紹k鄰近算法的基本概念和算法實(shí)現(xiàn)方式溉浙；
1.對(duì)于給定的訓(xùn)練集合{(x1,y1),(x2,y2）.......(xn,yn)}其中投放，y為不同的類別，而k鄰近算法所起的作用為，對(duì)于給定的訓(xùn)練集合，當(dāng)給定新的輸入x時(shí)瘟栖，通過k鄰近算法為其分配一個(gè)對(duì)應(yīng)的類承桥；
2.一個(gè)k鄰近模型有三個(gè)要素；
1）距離的度量
對(duì)于給定的x要求出他到達(dá)最近k個(gè)訓(xùn)練點(diǎn)的距離，然后根據(jù)這k個(gè)點(diǎn)，依據(jù)某種決策規(guī)則，來預(yù)測(cè)x的類別俱济；多數(shù)情況下取得是x-xi的二范數(shù)，值得注意的是钙勃，不同度量的選取會(huì)影響k個(gè)近鄰點(diǎn)的選取
2）k值得選取
如上蛛碌，k的選擇會(huì)對(duì)k近鄰發(fā)的結(jié)果產(chǎn)生較大的影響，具體表現(xiàn)在：
k較小時(shí)辖源，近似誤差小蔚携，估計(jì)誤差較大
k較大時(shí)，近似誤差大克饶，估計(jì)誤差較小
3）分類決策規(guī)則
k近鄰算法的分類決策往往是多數(shù)表決酝蜒，也就是把輸入實(shí)例的k個(gè)近鄰的訓(xùn)練實(shí)例中的多數(shù)類決定實(shí)例的類。
3.k近鄰算法的實(shí)現(xiàn)：kd樹
kd樹是一種類似于R樹的屬性結(jié)構(gòu)矾湃，但是我覺得他比R樹要簡單亡脑，他的具體構(gòu)造過程就是先選取一個(gè)和訓(xùn)練集x的維數(shù)k相同的超平面矩陣，首先，根結(jié)點(diǎn)是包含所有訓(xùn)練集的超平面矩陣霉咨，然后蛙紫，選取x某個(gè)維的中值，來進(jìn)行劃分途戒，分為左右子結(jié)點(diǎn)坑傅，再對(duì)左右子結(jié)點(diǎn)進(jìn)行遞歸操作，指導(dǎo)無法再分為止喷斋。
下面我將介紹兩種kd樹常用的算法：
1）構(gòu)造平衡kd樹：
輸入：k維訓(xùn)練集
輸出：kd樹
Step1：構(gòu)造根節(jié)點(diǎn)唁毒，其對(duì)應(yīng)包含所有訓(xùn)練集的k為超矩陣區(qū)域
step2：對(duì)于給定的結(jié)點(diǎn)，選取x的維的中值星爪，在該緯度上浆西，進(jìn)行垂直劃分，得到左右結(jié)點(diǎn)
step3：對(duì)于左右子結(jié)點(diǎn)進(jìn)行遞歸操作顽腾，終止條件為不可再分時(shí)
2）用kd樹實(shí)現(xiàn)最近鄰搜索
輸入：kd樹室谚，目標(biāo)點(diǎn)x
輸出：x的最近鄰
step1：在kd樹中找到包含x的葉子結(jié)點(diǎn)，從根結(jié)點(diǎn)出發(fā)崔泵，向下訪問kd樹，到達(dá)葉子結(jié)點(diǎn)為止
step2：把得到的葉子結(jié)點(diǎn)作為當(dāng)前最近點(diǎn)猪瞬。
step3：遞歸向上回退憎瘸，執(zhí)行以下操作：
1.如果結(jié)點(diǎn)所保存的實(shí)例點(diǎn)比當(dāng)前最近點(diǎn)更近，那么把改點(diǎn)作為當(dāng)前最近點(diǎn)
2.當(dāng)前最近的點(diǎn)一定存在于該節(jié)點(diǎn)的一個(gè)子結(jié)點(diǎn)對(duì)應(yīng)的區(qū)域陈瘦，檢查該區(qū)域的另外一個(gè)子節(jié)點(diǎn)是否有更近的點(diǎn)幌甘，并檢查以目標(biāo)點(diǎn)和當(dāng)前最近的點(diǎn)的距離為半徑的超球體相交，如果相交痊项，那么可能純?cè)诹硗庖粋€(gè)子節(jié)點(diǎn)對(duì)應(yīng)區(qū)域內(nèi)存在距離目標(biāo)點(diǎn)更近的點(diǎn)锅风，移動(dòng)到另外一個(gè)子節(jié)點(diǎn)，然后進(jìn)行遞歸的最近鄰搜索
如過不相交鞍泉，則向上回退
step4：當(dāng)回退到根節(jié)點(diǎn)時(shí)皱埠，搜索結(jié)束，最后的‘當(dāng)前最近點(diǎn)’即為x的最近鄰點(diǎn)
