KDツリーを生成し、KDツリーで最近接点を求める


本文は『KD-treeの原理及びクエリー操作を構築するpython実現』の解読である.
KDツリーは特殊なデータ構造で、Pythonでよく見られるデータ構造はこのデータ構造を表すことができません.著者らは、「ルートノード」、「カット次元」、「左サブツリー」、「右サブツリー」の4つのプロパティを持つKDツリーを基本コンポーネントに分割します.作成者は、ツリーノードを表すクラスを独自に作成し、そのクラスのオブジェクトでツリーノードを表します.クラスの定義コードは次のとおりです.
class KD_node:
    def __init__(self, point = None, split = None, LL = None, RR = None):
        """
        point:    
        split:    
        LL,RR:        
        """
        self.point = point
        self.split = split
        self.left  = LL
        self.right = RR

著者らが次元を選択する基準は,ある次元におけるサンプルの成分の分散が最も大きく,分散が大きいほど,この次元におけるデータの変動が大きくなることを示し,また,サンプルが同じ空間に属し得ないほど,この次元で点を区分する必要があることを示している.具体的にKDツリーを生成するプロセスコードは以下の通りである.