kd樹(shù)案例：最近領(lǐng)域的搜索和查找點(diǎn)

假設(shè)標(biāo)記為星星的點(diǎn)是 test point， 綠色的點(diǎn)是找到的近似點(diǎn)，在回溯過(guò)程中，需要用到一個(gè)隊(duì)列，存儲(chǔ)需要回溯的點(diǎn)，在判斷其他子節(jié)點(diǎn)空間中是否有可能有距離查詢點(diǎn)更近的數(shù)據(jù)點(diǎn)時(shí)，做法是以查詢點(diǎn)為圓心，以當(dāng)前的最近距離為半徑畫(huà)圓，這個(gè)圓稱為候選超球(candidate hypersphere)，如果圓與回溯點(diǎn)的軸相交，則需要將軸另一邊的節(jié)點(diǎn)都放到回溯隊(duì)列里面來(lái)。

樣本集{(2,3),(5,4), (9,6), (4,7), (8,1), (7,2)}。

查找點(diǎn)(2.1,3.1)

在(7,2)點(diǎn)測(cè)試到達(dá)(5,4)，在(5,4)點(diǎn)測(cè)試到達(dá)(2,3)，然后search_path中的結(jié)點(diǎn)為<(7,2),(5,4), (2,3)>，從search_path中取出(2,3)作為當(dāng)前最佳結(jié)點(diǎn)nearest, dist為0.141;

然后回溯至(5,4)，以(2.1,3.1)為圓心，以dist=0.141為半徑畫(huà)一個(gè)圓，并不和超平面y=4相交，如上圖，所以不必跳到結(jié)點(diǎn)(5,4)的右子空間去搜索，因?yàn)橛易涌臻g中不可能有更近樣本點(diǎn)了。

于是再回溯至(7,2)，同理，以(2.1,3.1)為圓心，以dist=0.141為半徑畫(huà)一個(gè)圓并不和超平面x=7相交，所以也不用跳到結(jié)點(diǎn)(7,2)的右子空間去搜索。

至此，search_path為空，結(jié)束整個(gè)搜索，返回nearest(2,3)作為(2.1,3.1)的最近鄰點(diǎn)，最近距離為0.141。

猜你喜歡：

OpenCV圖像處理：基礎(chǔ)模塊和高層次模塊

為什么CNN對(duì)像素級(jí)別的分類很難?

人工智能之人臉識(shí)別綜合應(yīng)用與實(shí)踐

SVM的推導(dǎo)，特性?多分類怎么處理?

黑馬程序員AI人工智能開(kāi)發(fā)師培訓(xùn)