首頁(yè)人工智能技術(shù)資訊正文

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

更新時(shí)間:2022-04-26 來(lái)源:黑馬程序員 瀏覽量:

假設(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)。

1650955994550_kd樹(shù)案例.png

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

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

查找點(diǎn)


在(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)

分享到:
在線咨詢 我要報(bào)名
和我們?cè)诰€交談!