【圖文】K近鄰算法PPT

1、 K近鄰法的實(shí)現(xiàn)：kd樹 o 2017/1/9 11 K近鄰法的實(shí)現(xiàn)：kd樹 Ø 搜索kd樹 利用kd樹可以省去大部分?jǐn)?shù)據(jù)點(diǎn)的搜索，從而減少搜索的計(jì)算量 。這里以最近鄰為例，同樣的方法可以應(yīng)用到K近鄰。 給定一個(gè)目標(biāo)點(diǎn)，搜索其最近鄰。首先找到包含目標(biāo)點(diǎn)的葉結(jié)點(diǎn) ；然后從該葉結(jié)點(diǎn)出發(fā)，依次回退到父結(jié)點(diǎn)；不斷查找與目標(biāo)點(diǎn) 最鄰近的結(jié)點(diǎn)，當(dāng)確定不可能存在更近的結(jié)點(diǎn)時(shí)終止。這樣搜索 就被限制在空間的局部區(qū)域上，效率大為提高。 包含目標(biāo)點(diǎn)的葉結(jié)點(diǎn)對(duì)應(yīng)包含目標(biāo)點(diǎn)的最小超矩形區(qū)域。以此葉 結(jié)點(diǎn)的實(shí)例點(diǎn)作為當(dāng)前最近點(diǎn)。目標(biāo)點(diǎn)的最近鄰一定在以目標(biāo)點(diǎn) 為中心并通過當(dāng)前最近點(diǎn)的超球體內(nèi)部。然后返回當(dāng)前結(jié)點(diǎn)

2、的父 結(jié)點(diǎn)，如果父結(jié)點(diǎn)的另一子結(jié)點(diǎn)的超矩形區(qū)域與超球體相交，那 么在相交的區(qū)域內(nèi)尋找與目標(biāo)點(diǎn)更近的實(shí)例點(diǎn)。如果存在這樣的 點(diǎn)，將此點(diǎn)作為新的當(dāng)前最近點(diǎn)。 12 2017/1/9 K近鄰法的實(shí)現(xiàn)：kd樹 Ø 搜索kd樹 算法轉(zhuǎn)到更上一級(jí)的父結(jié)點(diǎn)，繼續(xù)上述過程。如果父結(jié)點(diǎn)的另一 子結(jié)點(diǎn)的超矩形區(qū)域與超球體不相交，或不存在比當(dāng)前最近點(diǎn)更 近的點(diǎn)，則停止搜索。 例：給定一個(gè)如圖所示的kd樹，根結(jié)點(diǎn)為A，其子結(jié)點(diǎn)為B,C等。樹上 共存儲(chǔ)7個(gè)實(shí)例點(diǎn)；另有一個(gè)輸入目標(biāo)實(shí)例點(diǎn)S，求S的最近鄰 解：首先在kd樹中找到包含S的葉結(jié)點(diǎn)D，以點(diǎn)D作為近似最鄰。真正 最近鄰一定在以點(diǎn)S為中心通過點(diǎn)D的圓的內(nèi)部。然后返回結(jié)點(diǎn)D的父 結(jié)點(diǎn)B，在結(jié)點(diǎn)B的另一子結(jié)點(diǎn)F的區(qū)域內(nèi)搜索最近鄰。結(jié)點(diǎn)F的區(qū)域與 圓不想交，不可能有最近鄰。繼續(xù)返回上一級(jí)父結(jié)點(diǎn)A，在結(jié)點(diǎn)A的另 一子結(jié)點(diǎn)C的區(qū)域內(nèi)搜索最近鄰。結(jié)點(diǎn)C的區(qū)域與圓相交；該區(qū)域在圓 內(nèi)的實(shí)例點(diǎn)有點(diǎn)E，點(diǎn)E比點(diǎn)D更近，成為新的最近鄰近似。最后得到 點(diǎn)E是點(diǎn)S的