python - Python の増分最近傍アルゴリズム

Question

インクリメンタルに更新できる Python で実装された最近傍アルゴリズムを知っている人はいますか? this oneなど、私が見つけたものはすべてバッチプロセスのようです。インクリメンタルNNアルゴリズムを実装することは可能ですか?

Answer 1

これはかなり遅いですが、後世のために：

実際には、KD-Tree のようなバッチ処理されたアルゴリズムをインクリメンタル アルゴリズムに変換する手法があります。これは、静的から動的への変換と呼ばれます。

KD ツリーのインクリメンタル バリアントを生成するには、1 つのツリーではなく一連のツリーを格納します。最近傍構造にN 個の要素がある場合、構造にはNのバイナリ表現の「1」ビットごとにツリーがあります。さらに、ツリー T_i が N の i 番目のビットに対応する場合、ツリーT_iには2 ^ i 要素が含まれます。

したがって、構造体に 11 個の要素がある場合、N = 11、またはバイナリで 1011 であるため、それぞれ 8 個の要素、2 個の要素、および 1 個の要素を持つ 3 つのツリー ( T_3、T_1、およびT_0 ) があります。

それでは、要素eを構造体に挿入しましょう。挿入後、12 個の要素、つまりバイナリで 1100 個の要素ができます。新しいバイナリ文字列と以前のバイナリ文字列を比較すると、T_3は変更されていないことがわかります。4つの要素を持つ新しいツリーT_2があり、ツリーT_1とT_0が削除されています。T_1とT_0であるT_2の「下」のツリー内のすべての要素とともにeのバッチ挿入を行うことにより、新しいツリーT_2を構築します。

このようにして、静的基本構造からインクリメンタル ポイント クエリ構造を作成します。ただし、追加のlog(N)係数の形で、このような静的構造を「インクリメンタル化」する際に漸近的な速度低下があります。

• 構造にN 個の要素を挿入: O(N log(N) log(n))
• N 個の要素を持つ構造の最近傍クエリ: O(log(n) log(n))

Answer 2

KDツリーまたはKNNツリーの増分構築の問題は、コメントでほのめかしたように、ツリーが最終的に不均衡になり、バランスの問題を修正して維持するために単純なツリーの回転を行うことができないことだと思います一貫性。少なくとも、バランスの再調整のタスクは簡単ではなく、挿入のたびに実行したくないことは間違いありません。多くの場合、バッチ メソッドでツリーを構築し、一連の新しいポイントを挿入して、あるポイントまでツリーのバランスを崩してから、バランスを取り直すことを選択します。

非常によく似た方法は、M ポイントのデータ構造をバッチで構築し、それを M' ポイントに使用してから、M+M' ポイントでデータ構造をバッチで再構築することです。再調整は通常ではなく、ツリーでよく知られている高速アルゴリズムであるため、再構築は比較して必ずしも遅くはなく、場合によっては高速になる可能性があります (ポイントのシーケンスがインクリメンタル アルゴリズムにどのように入力されるかによって異なります)。

そうは言っても、再構築のアプローチを採用すれば、作成するコードの量、デバッグの難しさ、およびコードに対する他のユーザーの理解の容易さは大幅に小さくなる可能性があります。その場合、バッチ メソッドを使用して、まだツリーに挿入されていないポイントの外部リストを保持できます。力ずくのアプローチを使用して、これらのいずれもがツリー内のものより近くにないようにすることができます。

Python の実装/ディスカッションへのリンクをいくつか以下に示しますが、漸進的であると明示的に主張しているものは見つかりませんでした。幸運を。

http://www.scipy.org/Cookbook/KDTree

http://cgi.di.uoa.gr/~compgeom/pycgalvisual/kdppython.shtml

http://sites.google.com/site/mikescoderama/Home/kd-tree-knn

http://en.wikipedia.org/wiki/Kd-tree

注: ここでの私のコメントは、高次元空間に適用されます。2D または 3D で作業している場合、私が言ったことは適切ではないかもしれません。(非常に高次元の空間で作業している場合は、ブルート フォースを使用するか、近似最近傍を使用します。)

Answer 3

がある。Scipy Cookbook Web サイトには、段階的に更新できるkNN アルゴリズムの完全な実装が含まれています。

興味はあるが用語に慣れていない人にとっては、数行の背景が役立つかもしれません。

kNN エンジンは、2 つのデータ表現 (多次元配列 (距離行列) に格納されたデータセット内のすべてのポイント間のペアごとの距離) 、またはデータ ポイント自体を多次元二分木。

これらは、kd ツリーベースの KNN アルゴリズムが必要とする 2 つの操作のみです。データセットからツリーを作成し (他の ML アルゴリズムのバッチ モードで実行されるトレーニングステップに類似)、ツリーを検索して「最近傍」を見つけます。 (テストステップに類似)。

KNN アルゴリズムのコンテキストでのオンラインまたはインクリメンタル トレーニング (kd ツリーに基づく場合) は、既に構築された kd ツリーにノードを挿入することを意味します。

SciPy クックブックの kd-Tree 実装に戻る: ノード挿入を担当する特定のコード行は、コメント行「insert node in kd-tree」の後に表示されます (実際、そのコメントの後のすべてのコードはノード挿入に向けられています）。

最後に、KDTree ( scipy.spatial.KDTree ) と呼ばれるSciPy ライブラリ ( scipy.spatialモジュール)の空間モジュールに kd-tree 実装がありますが、ノード挿入をサポートしているとは思いません。少なくともそのような関数はサポートされていません。ドキュメントで（ソースを見ていません）。