9

規則的な密度でポイントのサブセットを選択するにはどうすればよいですか？より正式には、

与えられた

  1. 不規則な間隔の点のセットA 、
  2. 距離のメトリックdist（たとえば、ユークリッド距離）、
  3. および目標密度d、

以下を満たす最小のサブセットBを選択するにはどうすればよいですか？

  • Aのすべての点xについて、
  • Bに点yが存在する
  • これはdist(x,y) <= d

私の現在のベストショットは

  • A自体から始める
  • 最も近い（または特に近い）2つのポイントを選択します
  • それらの1つをランダムに除外します
  • 条件が成立する限り繰り返す

幸運を祈って、手順全体を繰り返します。しかし、もっと良い方法はありますか？

私は280,000の18-Dポイントでこれを行おうとしていますが、私の質問は一般的な戦略です。ですから、2Dポイントでそれを行う方法も知りたいです。そして、私は本当に最小のサブセットの保証を必要としません。どんな便利な方法でも大歓迎です。ありがとうございました。

ボトムアップ方式

  • ランダムな点を選択します
  • 選択されていないものの中からy最大のものをmin(d(x,y) for x in selected)選択します
  • 立ち止まるな！

これをボトムアップと呼び、最初にトップダウンで投稿したものと呼びます。これは最初ははるかに高速なので、スパースサンプリングの場合はこれが良いはずですか？

パフォーマンス測定

最適性の保証が必要ない場合は、次の2つの指標が役立つと思います。

  • カバレッジの半径：max {y in unselected} min(d(x,y) for x in selected)
  • 経済の半径：min {y in selected != x} min(d(x,y) for x in selected)

RCは最小許容dであり、これら2つの間に絶対的な不等式はありません。しかしRC <= RE、より望ましいです。

私の小さな方法

その「パフォーマンス測定」の少しのデモンストレーションのために、均一にまたは標準の正規分布によって分布された256の2Dポイントを生成しました。次に、トップダウンとボトムアップの方法を試してみました。そして、これは私が得たものです：

bottom-up.norm top-down.norm

RCは赤、REは青です。X軸は選択したポイントの数です。ボトムアップも同じくらい良いと思いましたか？アニメーションを見てそう思ったのですが、トップダウンの方がかなりいいようです（まばらな領域を見てください）。それにもかかわらず、それがはるかに高速であることを考えると、それほど恐ろしいことではありません。

ここにすべてを詰め込みました。

http://www.filehosting.org/file/details/352267/density_sampling.tar.gz

4

4 に答える 4

3

グラフで問題をモデル化し、ポイントをノードとして想定し、距離がdより小さい場合は、2つのノードをエッジで接続できます。これで、接続された頂点がグラフのすべてのノードをカバーするように、頂点の最小数を見つける必要があります。これは最小頂点被覆問題（一般にNP-Hard）ですが、高速2近似を使用できます。エッジの両方の端点を頂点被覆に繰り返し取り込み、グラフから削除します。

PS：グラフから完全に切断されているノードを選択する必要があります。このノードを削除した後（つまり、ノードを選択した後）、問題は頂点被覆です。

于 2012-06-11T07:06:04.620 に答える
2

遺伝的アルゴリズムはおそらくここで良い結果を生み出すかもしれません。

更新：

私はこの問題で少し遊んでいます、そしてこれらは私の発見です：

記載された条件を満たすポイントのセットを取得する簡単な方法（ランダム選択と呼びます）は次のとおりです。

  1. 空のBで開始
  2. Aからランダムな点xを選択し、それをBに配置します
  3. dist（x、y）<dとなるようにすべての点yをAから削除します
  4. Aが空でない間、2に進みます

kd-treeを使用すると、ステップ3のルックアップを比較的高速に実行できます。

私が2Dで実行した実験では、生成されたサブセットは、トップダウンアプローチで生成されたサブセットの約半分のサイズであることが示されています。

次に、このランダム選択アルゴリズムを使用して遺伝的アルゴリズムをシードし、サブセットのサイズをさらに25％削減しました。

突然変異の場合、サブセットBを表す染色体を与えて、Aのすべてのポイントをカバーする最小軸整列ハイパーボックス内のハイパーボールをランダムに選択します。次に、ハイパーボールにもあるすべてのポイントをBから削除し、ランダムを使用します。 -再度完了するための選択。

クロスオーバーの場合、私は同様のアプローチを採用し、ランダムなハイパーボールを使用して母と父の染色体を分割します。

GAULライブラリのラッパーを使用してPerlですべてを実装しました（GAULはここから取得できます）。

スクリプトはここにあります：https ：//github.com/salva/p5-AI-GAUL/blob/master/examples/point_density.pl

stdinからn次元の点のリストを受け取り、遺伝的アルゴリズムのすべての反復に最適なソリューションを示す画像のコレクションを生成します。コンパニオンスクリプトhttps://github.com/salva/p5-AI-GAUL/blob/master/examples/point_gen.plを使用して、一様分布のランダムポイントを生成できます。

于 2012-06-13T14:29:13.930 に答える
2

マンハッタン距離計量を仮定した提案は次のとおりです。

  1. スペース全体を粒度のグリッドに分割しますd。正式には：（floor（x1 / d）、...、floor（xn / d）のときに、ポイント（x1、...、xn）と（y1、...、yn）が正確に同じパーティションにあるようにパーティションA ））=（floor（y1 / d）、...、floor（yn / d））。
  2. 各グリッドスペースから（任意に）1つのポイントを選択します。つまり、手順1で作成したパーティションの各セットから代表を選択します。一部のグリッドスペースが空であっても心配しないでください。このスペースの代表者を選ばないでください。

実際には、実装はステップ1を実行するために実際の作業を行う必要はなく、ステップ2は、パーティション識別子のハッシュ（（floor（x1 / d）、。。 。、floor（xn / d）））を使用して、特定のグリッドスペースの代表をすでに選択しているかどうかを確認します。これにより、非常に高速になります。

他のいくつかの距離メトリックは、適応されたアプローチを使用できる場合があります。たとえば、ユークリッド距離はd / sqrt（n）サイズのグリッドを使用できます。この場合、カバーを少し小さくしようとする後処理ステップを追加することをお勧めします（上記のグリッドは、正確に半径dのボールではなくなったため、ボールは隣接するグリッドと少し重なっています）。 mその部分がどのように見えるかわからない。

于 2012-06-20T08:01:23.960 に答える
0

怠惰になるために、これは集合被覆問題にキャストすることができます。これは、混合整数問題ソルバー/オプティマイザーによって処理できます。これは、GLPK LP/MIPソルバーのGNUMathProgモデルです。ここでCは、どのポイントが各ポイントを「満たす」ことができるかを示します。

param N, integer, > 0;
set C{1..N};

var x{i in 1..N}, binary;
s.t. cover{i in 1..N}: sum{j in C[i]} x[j] >= 1;
minimize goal: sum{i in 1..N} x[i];

正規分布の1000ポイントでは、4分で最適なサブセットが見つかりませんでしたが、真の最小値を知っているとのことで、あと1ポイントしか選択しませんでした。

于 2013-09-26T19:38:18.663 に答える