0

このタイプのマイニングを行うための良い方法はありますか？線形計画法を使用して解決できます。しかし、私はこれに完全に慣れておらず、これを最小化として組み立てる最良の方法を知りません。

次のアプローチで大丈夫ですか？

  • 各行と列に連続変数を設定します。これは、その行/列のすべてのメンバーがまたがる「長さ」です。
  • 行または列のグループのメンバーであるかどうかを示す、各「ポイント」（各黒い点）の変数を用意します
  • 最初の変数の合計を最小化する

そして、これを行うためのより良い方法はありますか？どういうわけかこれを純粋な制約問題として（つまり最小化なしで）フレーム化することは可能ですか？用語は正しいですか？ありがとう！

4

2 に答える 2

1

はい、これには間違いなく線形計画法を使用できますが、それは難しく、問題をより正確に定義する必要があると思います。コメントするには質問が多すぎます。これを回答として書いても構いません...

あなたのポイントは、「列グループ」または「行グループ」のいずれかにあります。上記の提案から、列グループと行グループの数を事前に知っていると理解していますか?

グループの構成を知っているので、これらのグループ内のポイントの再分割を見つけて、以下によって決定されるコストの合計を最小化する必要があります。

  • 水平クラスターの垂直幅 ( c(H) = max (i,j in H) |yi - yj|)
  • 垂直クラスタの水平幅 ( c(V) = max (i,j in V) |xi - xj|)

H水平クラスター、垂直Vクラスターの場合、総コストは次のようになります。

c(H1) + c(H2) + ... + c(Hn) + c(V1) + c(V2) + ... + c(Vp)

n(水平クラスターの数) と(p垂直クラスターの数) は事前にわかっています。これは正しいです？

水平グループの場合、「穴」はあり得ないとおっしゃっています。穴のサイズを定量化できる場合は、これを問題の制約として表します。例えば：

for each i in C, ( min (j in C) |xi - xj|  ) < r

水平クラスター C に r を超えるギャップがないことを保証します。これでよろしいですか? 定数ですかr？

これは完全な問題ですか、それとも他の制約 (グループごとの最小ポイント数など) がありますか?

正確な最小限のソリューションが必要ですか、それとも「良い」ソリューションで十分でしょうか?

最後に、技術的な部分についてですが、あなたの以前の投稿は 'python' とタグ付けされていましたが、これはタグ付けされていないため、モデルを解決するために python を使用する必要がありますか?

于 2011-08-30T00:01:07.290 に答える
0

私は最終的に、この質問を線形形式で表現する方法を考え出しました。Is there a good way to do this type of mining? の回答に完全な説明があります。しかし、ここに簡単な要約があります：

  • 行の隣接するペアごとにバイナリ (0/1) 変数を使用しますF_i。ペアが同じグループにある場合、これは 1 になり、それ以外の場合は 0 になります。

  • 定数S_iを使用して、点の各ペア間のスペースの数を記述します。

  • 2 つの項の合計を最小化します。

    • の合計1 - F-i。これを最小限に抑えると、ペアがより大きなグループにまとめられます。

    • の合計F_i * S_i。これを最小化すると、大きな間隔でパリが分離されます。

2 つの用語の相対的な重み付けを変更することで、水平方向のグループ間の間隔の重要性を変更できます。

これは問題の非対称性に依存しており、水平グループは間隔に敏感ですが、垂直グループはそうではありません。

于 2011-08-30T11:24:06.993 に答える