17

KDツリーのウィキペディアページを見ています。例として、リストされているkdツリーを構築するためのアルゴリズムをPythonで実装しました。

ただし、KDツリーを使用してKNN検索を実行するためのアルゴリズムは言語を切り替え、完全には明確ではありません。英語の説明は意味をなし始めますが、その一部（他のリーフノードをチェックするために「再帰をほどく」領域など）は、私には実際には意味がありません。

これはどのように機能し、PythonでKDツリーを使用してKNN検索を実行するにはどうすればよいですか？これは"send me the code!"タイプの質問を意味するものではなく、私はそれを期待していません。簡単な説明をお願いします:)

4

3 に答える 3

14

この本の紹介、ページ 3:

d 次元空間の n 個の点のセットが与えられると、kd ツリーは次のように再帰的に構築されます。最初に、点の i 番目の座標の値の中央値を見つけます (最初は i = 1)。つまり、点の少なくとも 50% が M 以上の i 番目の座標を持ち、点の少なくとも 50% が M 以下の i 番目の座標を持つように、値 M が計算されます。 x の値が格納され、集合 P は PL と PR に分割されます。PL には、i 番目の座標が M 以下の点のみが含まれ、|PR | PR | = |PL |±1。次に、 i を i + 1 (または i = d の場合は 1) に置き換えて、 PL と PR の両方でプロセスが再帰的に繰り返されます。ノードのポイントのセットのサイズが 1 になると、再帰は停止します。

次の段落では、最近傍を解く際の使用について説明します。

または、Jon Bentley による 1975 年のオリジナルの論文はこちらです。

編集: SciPy には kdtree 実装があることを追加する必要があります。

于 2010-12-12T03:33:50.713 に答える
9

アルゴリズムのウィキペディアの説明を自分で理解するのに少し時間を費やし、役立つかもしれない次の Python 実装を思いつきました: https://gist.github.com/863301

の最初のフェーズはclosest_point、最も一致する葉ノードを見つける単純な深さ優先検索です。

見つかった最良のノードをコール スタックに戻すだけでなく、第 2 フェーズで「離れた」側に近いノードがあるかどうかを確認します: (ASCII アート ダイアグラム)

            n     current node
 b          |     best match so far
 |      p   |     point we're looking for
 |<    >|   |     error
        |< >|     distance to "away" side
        |<  | >|  error "sphere" extends to "away" side
            | x   possible better match on the "away" side

現在のノードは線に沿ってスペースを分割するため、ポイントと最適一致の間の「誤差」がポイントと線からの距離よりも大きい場合nにのみ、「離れた」側を見る必要があります。そうである場合は、「離れた」側に近い点があるかどうかを確認します。pbpn

最も一致するノードがこの 2 番目のテストに渡されるため、分岐を完全にトラバーサルする必要はなく、間違った軌道に乗っている場合はすぐに停止します (「近い」子ノードに到達するまで、「近い」子ノードを下っていくだけです)。葉。）

p点とノードを介して空間を分割する線との間の距離を計算するにはn、軸がすべて直交 (水平または垂直) であるため、適切な座標をコピーすることにより、点を軸に単純に「投影」できます。

于 2011-03-10T04:13:06.250 に答える