離散ボロノイテッセレーションを効率的に実行する方法

Question

d次元空間にc_1、c_2、...、c_Nの小数点があり、Nは約50-100であるとします。

ここで、Mは1e7と同じくらい大きいd次元空間にサンプルx_1、x_2、...、x_Mを持っています。

サンプルx_1、x_2、...、x_Mを分離する効率的な方法があります。各jに対して、x_jからc_kまでのユークリッド距離（すべてのkについて）がc_kになるようにx_jを割り当てます。一番小さい？

これまでのところ、私はブルートフォース手法を採用しています。すべてのjについて、x_jとすべてのc_kとの距離を計算するだけです。低次元では、Matlabのrepmatとベクトル化されたコードを使って簡単にこれを行うことができます。

しかし、高次元では、特にMが非常に大きい場合、repmatを実行するときにメモリの問題にぶつかります。その結果、forループを実行してすべてのx_jを反復処理することは非常に遅くなります。このクラスタリング手順を何度もやり直さなければならないので、私のシミュレーション全体は1日以上かかる。

クラスタリングプロセスをより効率的にする方法に関するアイデアはありますか？私は周りを見てみましたが、c_1、...、c_Nが与えられて以来、私には関係のないk-meansクラスタリングしか見つかりませんでした。

Answer 1

k-dツリーのような最近接構造は、高次元（次元の呪い）では非常に不十分です。私の最初の提案は、サンプルをMATLABインタプリタのオーバーヘッドを避けるのに十分な大きさであるが、キャッシュに快適に収まるくらい小さいチャンクで処理することです。