kd樹是什么？kd樹的原理【機(jī)器學(xué)習(xí)課程】

根據(jù)KNN每次需要預(yù)測一個(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樹：為了避免每次都重新計(jì)算一遍距離，算法會把距離信息保存在一棵樹里，這樣在計(jì)算之前從樹里查詢距離信息，盡量避免重新計(jì)算。其基本原理是，如果A和B距離很遠(yuǎn)，B和C距離很近，那么A和C的距離也很遠(yuǎn)。有了這個(gè)信息，就可以在合適的時(shí)候跳過距離遠(yuǎn)的點(diǎn)。

這樣優(yōu)化后的算法復(fù)雜度可降低到O(DNlog(N))。感興趣的讀者可參閱論文：Bentley，J.L.，Communications of the ACM(1975)。

1989年，另外一種稱為Ball Tree的算法，在kd Tree的基礎(chǔ)上對性能進(jìn)一步進(jìn)行了優(yōu)化。感興趣的讀者可以搜索Five balltree construction algorithms來了解詳細(xì)的算法信息。

kd樹原理：

黃色的點(diǎn)作為根節(jié)點(diǎn)，上面的點(diǎn)歸左子樹，下面的點(diǎn)歸右子樹，接下來再不斷地劃分，分割的那條線叫做分割超平面(splitting hyperplane)，在一維中是一個(gè)點(diǎn)，二維中是線，三維的是面。

黃色節(jié)點(diǎn)就是Root節(jié)點(diǎn)，下一層是紅色，再下一層是綠色，再下一層是藍(lán)色。

1.樹的建立;

2.最近鄰域搜索(Nearest-Neighbor Lookup)

kd樹(K-dimension tree)是一種對k維空間中的實(shí)例點(diǎn)進(jìn)行存儲以便對其進(jìn)行快速檢索的樹形數(shù)據(jù)結(jié)構(gòu)。kd樹是一種二叉樹，表示對k維空間的一個(gè)劃分，構(gòu)造kd樹相當(dāng)于不斷地用垂直于坐標(biāo)軸的超平面將K維空間切分，構(gòu)成一系列的K維超矩形區(qū)域。kd樹的每個(gè)結(jié)點(diǎn)對應(yīng)于一個(gè)k維超矩形區(qū)域。利用kd樹可以省去對大部分?jǐn)?shù)據(jù)點(diǎn)的搜索，從而減少搜索的計(jì)算量。

類比“二分查找”：給出一組數(shù)據(jù)：[9 1 4 7 2 5 0 3 8]，要查找8。如果挨個(gè)查找(線性掃描)，那么將會把數(shù)據(jù)集都遍歷一遍。而如果排一下序那數(shù)據(jù)集就變成了：[0 1 2 3 4 5 6 7 8 9]，按前一種方式我們進(jìn)行了很多沒有必要的查找，現(xiàn)在如果我們以5為分界點(diǎn)，那么數(shù)據(jù)集就被劃分為了左右兩個(gè)“簇” [0 1 2 3 4]和[6 7 8 9]。

因此，根本就沒有必要進(jìn)入第一個(gè)簇，可以直接進(jìn)入第二個(gè)簇進(jìn)行查找。把二分查找中的數(shù)據(jù)點(diǎn)換成k維數(shù)據(jù)點(diǎn)，這樣的劃分就變成了用超平面對k維空間的劃分。空間劃分就是對數(shù)據(jù)點(diǎn)進(jìn)行分類，“挨得近”的數(shù)據(jù)點(diǎn)就在一個(gè)空間里面。

決策樹的劃分依據(jù)一：信息增益

文本數(shù)據(jù)分析有什么作用？常用的文本數(shù)據(jù)分析方法

OPenCV中如何實(shí)現(xiàn)ORB算法？【OpenCV教程】

meanshift算法原理：meanshift跟蹤算法實(shí)戰(zhàn)

傳智教育Ai人工智能開發(fā)培訓(xùn)課程