Pythonのインクリメンタルな最近傍アルゴリズム

Question

Pythonでインプリメントされた最も近いネイバーアルゴリズムを認識している人は、徐々に更新できますか？ this oneのような私が見つけたすべてのものは、バッチ処理のようです。増分NNアルゴリズムを実装することは可能ですか？

Answer 1

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://www.java2s.com/Open-Source/Python/Math/SciPy/scipy/scipy/spatial/kdtree.py.htm

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

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

Answer 2

あります。 Scipy Cookbook WebSiteには、徐々に更新できるkNN algorithmの完全な実装が含まれています。

多分、数行の背景が、専門用語に慣れていても慣れていない人にとって役に立ちます。

A k最近傍エンジンは、二つのデータ表現のいずれかによって供給されて - 多次元アレイに記憶されたデータセット内のすべての点の間のペアワイズ距離（距離行列）、またはkdツリー、そのデータポイント自体を多次元バイナリツリーに格納するだけです。あなたは（他のMLアルゴリズムでバッチモードで実行トレーニングステップに類似した）データセットからツリーを作成し、ツリーを検索：

これらは、KD-ツリーベースKNNアルゴリズムが必要とする2つだけの操作です「最も近い近隣」を見つける（テストのステップに類似）。

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

SciPy Cookbookのkd-Tree実装に戻る：ノード挿入を担当する特定のコード行は、コメント行 "kd-treeにノードを挿入"の後に表示されます（実際にコメントの後のコードはすべてノードの挿入を指示する）。

最後に、そこKDTree（scipy.spatial.KDTree）と呼ばれるscipyのダウンロードライブラリ（scipy.spatialモジュール）の空間的なモジュール内のkdツリーの実装があるが、私はそれがノードの挿入をサポートしています信じていません、少なくともそのような関数はDocsにはない（私はソースを見ていない）。

Answer 3

これは道後半ですが、後世のために：

KD-のようなバッチ処理のアルゴリズムを変換するための技術が実際にあります増分アルゴリズムへのツリー：静的から動的への変換と呼ばれています。

KDツリーのインクリメンタルバリアントを生成するには、1つのツリーではなくツリーのセットを格納します。最も近いネイバー構造にN要素がある場合、構造体には、Nというバイナリ表現の各 "1"ビットのツリーがあります。ツリーT_IがNのI番目のビットに対応する場合また、次にツリーT_Iは2^I要素を含みます。だから、

、あなたがバイナリであなたの構造の11個の要素、そしてN = 11、または1011を持っているので、あなたは3本の木がある場合 - T_3、T_1、およびT_0から8つの要素とを、2つの要素、および1つの要素である。

ここで、eという要素を私たちの構造に挿入しましょう。挿入後、12個の要素、つまり1100個のバイナリがあります。新しいと前のバイナリ文字列を比較すると、我々はT_3が変化しないことがわかり、我々は4つの要素、および木T_1とT_0削除されますと新しいツリーT_2を持っています。私たちは、新しいツリーT_2はT_2「の下に」木のすべての要素と一緒に電子の一括挿入を行うことによって構築し、T_1とT_0です。

このようにして、静的な基本構造からインクリメンタルポイントクエリ構造を作成します。O（Nログ（：構造中N要素を挿入

• ：余分ログ（N）因子の形態では、このような静的構造を「incrementalizing」に漸近的減速は、しかし、ありますN）ログ（N））N要素を持つ構造のため
• 最近傍クエリー：N O（ログ（n）のログ（））