KDツリーを生成し、KDツリーで最近接点を求める
本文は『KD-treeの原理及びクエリー操作を構築するpython実現』の解読である.
KDツリーは特殊なデータ構造で、Pythonでよく見られるデータ構造はこのデータ構造を表すことができません.著者らは、「ルートノード」、「カット次元」、「左サブツリー」、「右サブツリー」の4つのプロパティを持つKDツリーを基本コンポーネントに分割します.作成者は、ツリーノードを表すクラスを独自に作成し、そのクラスのオブジェクトでツリーノードを表します.クラスの定義コードは次のとおりです.
著者らが次元を選択する基準は,ある次元におけるサンプルの成分の分散が最も大きく,分散が大きいほど,この次元におけるデータの変動が大きくなることを示し,また,サンプルが同じ空間に属し得ないほど,この次元で点を区分する必要があることを示している.具体的にKDツリーを生成するプロセスコードは以下の通りである.
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ツリーを生成するプロセスコードは以下の通りである.