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

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

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

查找點(2.1,3.1)

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

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

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

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

猜你喜歡：

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

為什么CNN對像素級別的分類很難?

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

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

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