更新時(shí)間:2022年04月26日14時(shí)27分 來(lái)源:傳智教育 瀏覽次數(shù):
根據(jù)KNN每次需要預(yù)測(cè)一個(gè)點(diǎn)時(shí),我們都需要計(jì)算訓(xùn)練數(shù)據(jù)集里每個(gè)點(diǎn)到這個(gè)點(diǎn)的距離,然后選出距離最近的k個(gè)點(diǎn)進(jìn)行投票。當(dāng)數(shù)據(jù)集很大時(shí),這個(gè)計(jì)算成本非常高。
kd樹(shù):為了避免每次都重新計(jì)算一遍距離,算法會(huì)把距離信息保存在一棵樹(shù)里,這樣在計(jì)算之前從樹(shù)里查詢距離信息,盡量避免重新計(jì)算。其基本原理是,如果A和B距離很遠(yuǎn),B和C距離很近,那么A和C的距離也很遠(yuǎn)。有了這個(gè)信息,就可以在合適的時(shí)候跳過(guò)距離遠(yuǎn)的點(diǎn)。
這樣優(yōu)化后的算法復(fù)雜度可降低到O(DNlog(N))。感興趣的讀者可參閱論文:Bentley,J.L.,Communications of the ACM(1975)。
1989年,另外一種稱為Ball Tree的算法,在kd Tree的基礎(chǔ)上對(duì)性能進(jìn)一步進(jìn)行了優(yōu)化。感興趣的讀者可以搜索Five balltree construction algorithms來(lái)了解詳細(xì)的算法信息。
kd樹(shù)原理:
黃色的點(diǎn)作為根節(jié)點(diǎn),上面的點(diǎn)歸左子樹(shù),下面的點(diǎn)歸右子樹(shù),接下來(lái)再不斷地劃分,分割的那條線叫做分割超平面(splitting hyperplane),在一維中是一個(gè)點(diǎn),二維中是線,三維的是面。
黃色節(jié)點(diǎn)就是Root節(jié)點(diǎn),下一層是紅色,再下一層是綠色,再下一層是藍(lán)色。
1.樹(shù)的建立;
2.最近鄰域搜索(Nearest-Neighbor Lookup)
kd樹(shù)(K-dimension tree)是一種對(duì)k維空間中的實(shí)例點(diǎn)進(jìn)行存儲(chǔ)以便對(duì)其進(jìn)行快速檢索的樹(shù)形數(shù)據(jù)結(jié)構(gòu)。kd樹(shù)是一種二叉樹(shù),表示對(duì)k維空間的一個(gè)劃分,構(gòu)造kd樹(shù)相當(dāng)于不斷地用垂直于坐標(biāo)軸的超平面將K維空間切分,構(gòu)成一系列的K維超矩形區(qū)域。kd樹(shù)的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)k維超矩形區(qū)域。利用kd樹(shù)可以省去對(duì)大部分?jǐn)?shù)據(jù)點(diǎn)的搜索,從而減少搜索的計(jì)算量。
類比“二分查找”:給出一組數(shù)據(jù):[9 1 4 7 2 5 0 3 8],要查找8。如果挨個(gè)查找(線性掃描),那么將會(huì)把數(shù)據(jù)集都遍歷一遍。而如果排一下序那數(shù)據(jù)集就變成了:[0 1 2 3 4 5 6 7 8 9],按前一種方式我們進(jìn)行了很多沒(méi)有必要的查找,現(xiàn)在如果我們以5為分界點(diǎn),那么數(shù)據(jù)集就被劃分為了左右兩個(gè)“簇” [0 1 2 3 4]和[6 7 8 9]。
因此,根本就沒(méi)有必要進(jìn)入第一個(gè)簇,可以直接進(jìn)入第二個(gè)簇進(jìn)行查找。把二分查找中的數(shù)據(jù)點(diǎn)換成k維數(shù)據(jù)點(diǎn),這樣的劃分就變成了用超平面對(duì)k維空間的劃分??臻g劃分就是對(duì)數(shù)據(jù)點(diǎn)進(jìn)行分類,“挨得近”的數(shù)據(jù)點(diǎn)就在一個(gè)空間里面。
文本數(shù)據(jù)分析有什么作用?常用的文本數(shù)據(jù)分析方法
OPenCV中如何實(shí)現(xiàn)ORB算法?【OpenCV教程】
北京校區(qū)