教育行業(yè)A股IPO第一股(股票代碼 003032)

全國(guó)咨詢/投訴熱線:400-618-4000

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

更新時(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ù)原理:

kd樹(shù)

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

kd樹(shù)root節(jié)點(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ù)分析有什么作用?常用的文本數(shù)據(jù)分析方法

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

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

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

0 分享到:
和我們?cè)诰€交談!