1

ここに私の問題のシナリオがあります:

私は数千のオブジェクトを持っています。各オブジェクトには、256 個のブール次元 (true または false) があります。次のようなクラスターを見つけたい

  1. 各クラスターには最小量の真の次元があります (そのクラスター内のいずれかのオブジェクトがこの次元市場を真として持つ場合、クラスターの次元は真です)。
  2. すべてのクラスターにわたるすべての真のディメンションの全体的な合計は最小です。
  3. 各クラスターは、事前定義された特定の値より大きくありません。

解が最適である必要はありませんが、アルゴリズムは高速である必要があります。

この問題にどのようにアプローチするのが最善ですか? お勧めのアルゴリズムはありますか？

注: この問題に対してブルート フォース アプローチを既に実装しましたが、かなり遅いです。

4

2 に答える 2

2

これを混合整数線形計画法 (MILP)として記述できます。

一定量のクラスターとオブジェクトがあります。
各クラスターは最大 256 の真の次元を持つことができます。
オブジェクト k で次元 i が true の場合、パラメーターD_{k,j}は 1 に等しくなります。

次の変数があります。

  1. d_{i,j}次元 j がクラスター i の真の次元である場合、1 に等しいバイナリ変数です。
  2. o_{i,k}オブジェクト k がクラスター i にある場合に true になるバイナリ変数です。

次の制約があります。

  1. 各オブジェクトは 1 つのクラスターにのみ含めることができます
  2. クラスター内のすべてのオブジェクトで true の場合、ディメンションはクラスターで true です
  3. 各クラスタは M 個のオブジェクトのみを保持できます

2 番目の制約は、線形に感じられないため難しいものですが、実際には線形に記述できます。制約は次のように記述できます。

  1. C1すべての k に対して
  2. C2すべての i と j について
  3. C3すべての私のために

目的関数はすべての合計になる可能性があるd_{i,j}ため、すべてのクラスターですべての真の次元の全体的な合計を最小化します。

2 番目の制約について説明します。右側では、クラスター i 内の要素の数から、次元 j が 1 に設定されているオブジェクトの数を差し引いた値を計算します。これは、すべてのオブジェクトが次元 j を持つ場合はゼロに等しく、そうでない場合は正の値になります。

これがゼロに評価される場合、制約違反を避けるために 1 に等しくd_{i,j} なければなりません。そうでない場合は、何でもかまいませんd_{i,j}(0 または 1)。これd_{i,j}は、 が目的関数に現れるため機能します。つまり、プログラムが 0 か 1 のどちらかを選択できる場合は、0 を選択します。

これを書いたら、商用のソルバー (持っている場合は学生に無料ライセンスを提供します) またはコイン ORを使用して解決できます。

念のために言っておきますが、MILP を解くことはNP 完全問題です。

于 2012-11-19T21:55:58.493 に答える
0

そこで、思いついた（理論上の）解決策を書き留めることにしました。部分的にはそれが私を助けるかもしれないからです（これについては以下を参照してください）そして部分的には興味のある人にとってまともな解決策を持っているからです. これは、シンプレックス アルゴリズムを使用して解くことができる線形方程式のシステムです。

私が思いついた制約は次のとおりです。

1) すべてのオブジェクトが正確に 1 つのクラスター内にある

2) すべてのクラスターには、最大で M (定数) 個のオブジェクトがあります

3) クラスタ内の少なくとも 1 つのオブジェクトでそのディメンションが true に設定されている場合、そのクラスタのディメンションは true です。

制約がどのように適用されるかを説明します。

n 個のオブジェクトと k 個のクラスターがあるとします。合計を検討します（以下では、これは1行です）

x 1 1 + x 2 1 + x 3 1 + ... + x n 1 + d 1 1 + d 2 1 + d 3 1 + ... + d n 1 +

x 1 2 + x 2 2 + x 3 2 + ... + x n 2 + d 1 2 + d 2 2 + d 3 2 + ... + d n 2 +

...

x 1 k + x 2 k + x 3 k + ... + x n k + d 1 k + d 2 k + d 3 k + ... + d n k

どこ

オブジェクト a が int クラスタ c の場合、 x a cは true

クラスター c の次元 b が true の場合、 d b cは true

オブジェクトをクラスター化することは常に良い (または少なくとも有害ではない) ため、クラスターの数はceil(オブジェクトを M で割った値)であることがわかっています。簡単にするために、ここでは変数を省略し、係数のみを記述します。

1)すべてのオブジェクトが正確に 1 つのクラスター内にある

10...0 0...0 10...0 0...0 10...0 0...0 ... 10...0 0...0 = 1

010...0 0...0 010...0 0...0 010...0 0...0 ... 010...0 0...0 = 1

...

0..01 0...0 0...01 0...0 0...01 0...0 ... 0...01 0...0 = 1

これにより、すべてのオブジェクトが厳密に 1 つのクラスターに配置されます。これにより、理論的には、オブジェクトが複数のクラスター内のパーツ (<1) を持つことが可能になります。しかし、最適なソリューションを探しているため、これは起こりません。

2)すべてのクラスターには、最大で M (定数) 個のオブジェクトがあります

11...1 0...0 0...0 0...0 0...0 0...0 ... 0...0 0...0 <= M

0...0 0...0 11...1 0...0 0...0 0...0 ... 0...0 0...0 <= M

...

0...0 0...0 0...0 0...0 0...0 0...0 ... 11...1 0...0 <= M

オブジェクトの合計は M より大きくありません。この制約は明確です。

ここでトリッキーな部分が来ます:

3)クラスタ内の少なくとも 1 つのオブジェクトでそのディメンションが true に設定されている場合、そのクラスタのディメンションは true です。

すべての次元とすべてのクラスターについて、この次元が true に設定されている要素を考慮します (false も考慮することができますが、それらは重要ではありません)。それらのそれぞれ (および各クラスター) に対して行を記述します。

0..010...0 -10...0 0...0 0...0 ... 0...0 0...0 <= 0

ここで、1 はこのオブジェクト (このクラスター内) のこのディメンションが true に設定されていることを示し、-1 はディメンション (この場合は最初のディメンション) を識別します。オブジェクトがこのクラスターに設定されている場合、このクラスターの次元は 1 (1*1 -1*d <= 0) である必要があり、設定されていない場合、次元はゼロ (0*1 - 1*d < = 0)。

最初のクラスターの 2 番目の次元の場合、これは次のようになります。

0..010...0 0-10...0 0...0 0...0 ... 0...0 0...0 <= 0

最後のクラスターと最後の次元はこのように

0...0 0...0 0...0 0...0 ... 0..010..0 0...0-1 <= 0

これで、x a cの合計を最小化するだけで完了です。

これはおそらくより良い方法で書き留めることができますが、理解できることを願っています。

問題は次のとおりです。70 個のクラスター、3000 個のオブジェクト、2300 個のディメンションを使用しています。上記のアプローチを使用すると、371000 個の変数 (クラスター * オブジェクト + クラスター * ディメンション) と 1292095 行 (行をオブジェクト + クラスター + ディメンション * ログ (オブジェクト) * クラスターとして推定) になります。

私は、最適な解決策は実現可能ではないと信じがちです。ここで説明するアプローチを最適化できたとしても、同様のアプローチがはるかに優れたパフォーマンスを発揮する可能性は低いです。だから今、私は良い概算を探しています.この問題に取り組む方法についてのアイデアは大歓迎です.

ありがとうございました ：）

于 2013-02-10T17:49:09.963 に答える