k-nn在軌跡數(shù)據(jù)采樣率合適的情況下，用于路網(wǎng)映射的子流程中；下面將介紹k鄰近算法的基本概念和算法實現(xiàn)方式；
1.對于給定的訓(xùn)練集合{(x1,y1),(x2,y2）.......(xn,yn)}其中，y為不同的類別，而k鄰近算法所起的作用為，對于給定的訓(xùn)練集合，當(dāng)給定新的輸入x時，通過k鄰近算法為其分配一個對應(yīng)的類；

2.一個k鄰近模型有三個要素；

1）距離的度量

對于給定的x要求出他到達(dá)最近k個訓(xùn)練點的距離，然后根據(jù)這k個點，依據(jù)某種決策規(guī)則，來預(yù)測x的類別；多數(shù)情況下取得是x-xi的二范數(shù)，值得注意的是，不同度量的選取會影響k個近鄰點的選取

2）k值得選取
如上，k的選擇會對k近鄰發(fā)的結(jié)果產(chǎn)生較大的影響，具體表現(xiàn)在：
k較小時，近似誤差小，估計誤差較大
k較大時，近似誤差大，估計誤差較小

3）分類決策規(guī)則
k近鄰算法的分類決策往往是多數(shù)表決，也就是把輸入實例的k個近鄰的訓(xùn)練實例中的多數(shù)類決定實例的類。

3.k近鄰算法的實現(xiàn)：kd樹
kd樹是一種類似于R樹的屬性結(jié)構(gòu)，但是我覺得他比R樹要簡單，他的具體構(gòu)造過程就是先選取一個和訓(xùn)練集x的維數(shù)k相同的超平面矩陣，首先，根結(jié)點是包含所有訓(xùn)練集的超平面矩陣，然后，選取x某個維的中值，來進(jìn)行劃分，分為左右子結(jié)點，再對左右子結(jié)點進(jìn)行遞歸操作，指導(dǎo)無法再分為止。

下面我將介紹兩種kd樹常用的算法：

1）構(gòu)造平衡kd樹：
輸入：k維訓(xùn)練集
輸出：kd樹

Step1：構(gòu)造根節(jié)點，其對應(yīng)包含所有訓(xùn)練集的k為超矩陣區(qū)域
step2：對于給定的結(jié)點，選取x的維的中值，在該緯度上，進(jìn)行垂直劃分，得到左右結(jié)點
step3：對于左右子結(jié)點進(jìn)行遞歸操作，終止條件為不可再分時

2）用kd樹實現(xiàn)最近鄰搜索
輸入：kd樹，目標(biāo)點x
輸出：x的最近鄰

step1：在kd樹中找到包含x的葉子結(jié)點，從根結(jié)點出發(fā)，向下訪問kd樹，到達(dá)葉子結(jié)點為止
step2：把得到的葉子結(jié)點作為當(dāng)前最近點。
step3：遞歸向上回退，執(zhí)行以下操作：
1.如果結(jié)點所保存的實例點比當(dāng)前最近點更近，那么把改點作為當(dāng)前最近點
2.當(dāng)前最近的點一定存在于該節(jié)點的一個子結(jié)點對應(yīng)的區(qū)域，檢查該區(qū)域的另外一個子節(jié)點是否有更近的點，并檢查以目標(biāo)點和當(dāng)前最近的點的距離為半徑的超球體相交，如果相交，那么可能純在另外一個子節(jié)點對應(yīng)區(qū)域內(nèi)存在距離目標(biāo)點更近的點，移動到另外一個子節(jié)點，然后進(jìn)行遞歸的最近鄰搜索
如過不相交，則向上回退
step4：當(dāng)回退到根節(jié)點時，搜索結(jié)束，最后的‘當(dāng)前最近點’即為x的最近鄰點