機器學習_學習筆記系列(70)：球樹(Ball Tree)
上一回我們介紹了KD Tree接下來我們要來介紹，新的演算法Ball Tree。
關於Ball Tree他也是一種適用於高維度資料的樹狀演算法。所以一樣也有建立和搜尋的相關演算法。
關於ball tree其是由Stephen Malvern Omohundro提出，其論文名稱為
Five balltree construction algorithms
另外這位作者，雖然其背景是Stanford物理和數學雙學士，UCBekerly物理博士，但是他也在動態系統、機器視覺和人工智慧上有非常大的貢獻，他甚至還是*Lisp的開發人員。
Build
回歸正題，對於Ball Tree的核心概念就是，當我們每次分資料的時候
我們會先計算當前node底下所有資料的中心位置centroid，接著看哪筆資料離centroid最遠，並標記這個資料為child1，然後看再看哪個資料離child1最遠標記為child2。(這裡的距離都是指歐幾里得距離)
有了child1和child2後，我們就會根據這兩個點，檢查當前node底下所有資料，如果距離child1比較近就分到child1的node底下，反之離child2比較近就分到child2的node底下。
而我們會依照這樣的方式，把資料分成兩半child1和child2，直到兩邊的資料數量，都少於我們所設定的大小(leaf size)。整體演算法如下
Search
而對於其搜尋方法的邏輯也很相似，當我們給定一筆資料後，我們會根據當前node底下所記錄的兩個點child1和child2，看此資料距離哪個比較近，如果離child1近就往child1繼續往下找，反之往child2繼續往下找，直到我們到達樹的最終端為止。其演算法如下
所以用這樣的演算法，我們就可以快速找到一個數據點其鄰近的資料點，而這樣的特性，也可以讓我們在之後manifold learning上有非常大的幫助。
Python Sample Code:
Github:
Reference:
[1] Omohundro, S. M. (1989). Five balltree construction algorithms (pp. 1–22). Berkeley: International Computer Science Institute.
