一、kd-tree和ball-tree在算法實現(xiàn)原理上的區(qū)別

KD樹是對依次對K維坐標軸，以中值切分構造的樹,每一個節(jié)點是一個超矩形，在維數(shù)小于20時效率較高；ball tree 是為了克服KD樹高維失效而發(fā)明的，其構造過程是以質心C和半徑r分割樣本空間，每一個節(jié)點是一個超球體。

kd 樹是一個二叉樹，每一個內部的節(jié)點都代表了一個超矩形空間，并且它的子樹包含在這個超矩形空間內部的所有樣本點。

但是 kd 樹對于一些樣本分布情況而言效率并不高，比如當大量樣本落在一個超矩形的角落的情況，此時使用球樹的效率會更高。

球樹的結構與 kd 樹類似，同樣是一個二叉樹，根節(jié)點選擇方式如下：

找到一個中心點，使所有樣本點到這個中心點的距離最短。

對于每一個節(jié)點的子節(jié)點的選擇，方式如下：

讓我們舉一個具體的例子：

對以下樣本點構建球樹：[1,2], [5,3], [7,9], [1,6], [9,2], [8,4], [4,4], [5,7]

首先建立根節(jié)點，找到包含所有樣本點的超球體，記錄球心位置，作為根節(jié)點（超球體可以是最小外接超球體，也可以不是，只需要將符合要求的樣本點包含進去即可，當然越小的超球體，在搜索過程中效率越高，最小外接超球體的擬合存在很多方法，可以拉到最后查看本文最后一章，現(xiàn)在假設已經找到最小外接超球體）

找到所有點中距離最遠的兩個點，并判斷其他樣本點與這兩個點的距離，距離哪個點最近，則將該樣本點劃分到該點所在的圓內，并得到包含所有相同類別的點的圓的圓心坐標和半徑，生成兩個子節(jié)點。

何時停止空間分割呢，可以設定一個閾值 r，當子節(jié)點中包含的樣本點數(shù)量 <= r 時，即可停止對這個子節(jié)點的分割。如果 r=4，此時我們的球樹已經構建完畢。

當 r=3，或 r=2，我們還需要對兩個子節(jié)點做同樣的空間分割操作：

球樹的每個節(jié)點中，需要包含的信息如下：

延伸閱讀：

二、隨機增量法

對于一個已經將 i-1 個點包含在內的最小外接圓來說，我們增加一個點 i，如何找到所有點的最小外接圓呢？過程如下：

以上就是關于kd-tree和ball-tree在算法實現(xiàn)原理上的區(qū)別的內容希望對大家有幫助。

上一篇

腳本語言和c語言，c++，java有啥區(qū)別?

下一篇

編程語言鄙視鏈這個視頻里頭這些語言啥區(qū)別?