10

大きなスパース行列（たとえば、10k + x 1M +）が与えられた場合、密行列（すべてゼロ以外の要素）を形成する行と列のサブセット（必ずしも連続ではない）を見つける必要があります。このサブ行列は、アスペクト比の制約内で可能な限り大きくする必要があります（最大の合計ではなく、要素の最大数）。

この問題に対する既知の正確なまたはアプロキサメートの解決策はありますか？

グーグルでのクイックスキャンは、多くの近いが正確ではない結果を与えるようです。どのような用語を探す必要がありますか？

編集：明確にするために; サブ行列は連続である必要はありません。実際、行と列の順序は完全に任意であるため、隣接関係は完全に無関係です。

チャド・オケレの考えに基づく考え

  1. 行を最大数から最小数の順に並べます（必須ではありませんが、パフォーマンスに役立つ場合があります）
  2. 「大きな」オーバーラップがある2つの行を選択します
  3. 重複を減らさない他のすべての行を追加します
  4. そのセットを記録する
  5. オーバーラップを最小限に抑える行を追加します
  6. 結果が小さくなるまで＃3で繰り返します
  7. 別の開始ペアで＃2からやり直します
  8. 結果が十分に良いと判断するまで続けます
4

4 に答える 4

2

このようなものが欲しいと思います。あなたは次のような行列を持っています

1100101
1110101
0100101

列 1、2、5、7 と行 1 および 2 が必要ですよね? その部分行列は、8 つの要素を持つ 4x2 になります。または、列 1,5,7 に行 1,2,3 を使用すると、3x3 マトリックスになります。

「近似」方法が必要な場合は、単一の非ゼロ要素から始めて、別の非ゼロ要素を見つけて、行と列のリストに追加できます。ある時点で、コレクションに行と列が追加された場合、コレクションが完全に非ゼロではなくなるゼロ以外の要素に遭遇します。

したがって、上記のマトリックスの場合、1,1 と 2,2 を追加すると、コレクションに行 1,2 と列 1,2 が含まれます。3,7 を追加しようとすると、1,3 はゼロなので問題が発生します。したがって、追加できませんでした。ただし、2,5 と 2,7 を追加できます。4x2 サブマトリックスの作成。

基本的に、追加する新しい行と列が見つからなくなるまで繰り返します。それはあまりにも局所的な最小値を取得します。結果を保存して、別の開始点 (おそらく現在のソリューションに適合しないもの) からやり直すことができます。

その後、しばらくして見つからなくなったら停止します。

明らかに、それには長い時間がかかりますが、これ以上早くできるかどうかはわかりません.

于 2009-08-01T21:58:05.537 に答える
2

あなたがもうこれに取り組んでいないことは知っていますが、将来誰かが私と同じ質問をするかもしれないと思いました.

したがって、これが NP 困難な問題であることに気付いた後 (MAX-CLIQUE への還元による)、これまでのところうまく機能しているヒューリスティックを考え出すことにしました。

N x Mのバイナリ/ブール行列を指定して、大きな密な部分行列を見つけます。

パート I : 妥当な候補部分行列を生成する

  1. N行のそれぞれがM次元のバイナリ ベクトルv_iであると考えます。ここで、i =1 ～Nです。
  2. ハミング距離を使用して、 Nベクトルの距離行列を計算します。
  3. UPGMA (算術平均による重み付けされていないペア グループ法) アルゴリズムを使用してベクトルをクラスター化する

最初は、各v_iベクトルはシングルトン クラスターです。上記のステップ 3 (クラスタリング) は、ベクトルを部分行列に結合する順序を示します。したがって、階層クラスタリング ツリーの各内部ノードは候補部分行列です。

パート II : 候補部分行列のスコア付けとランク付け

  1. 各部分行列について、1 つ以上のゼロを含む列を削除することにより、部分行列のベクトルの密なサブセット内の要素数Dを計算します。
  2. Dを最大化する部分行列を選択してください

また、最初の完全なマトリックスから保持する必要がある行の最小数に関していくつかの考慮事項があり、最大D値を持つサブマトリックスを選択する前に、この基準を満たさない候補サブマトリックスを破棄しました。

于 2011-10-20T18:06:38.150 に答える
1

これはNetflixの問題ですか?

MATLABまたはその他の疎行列ライブラリには、それを処理する方法がある場合があります。

自分で書くつもりですか？

おそらく、各行の 1D アプローチが役立つでしょう。アルゴリズムは次のようになります。

  1. 各行をループします
  2. 最初の非ゼロ要素のインデックスを見つける
  3. 各行の非ゼロ列間のスパンが最大の非ゼロ行要素のインデックスを見つけ、両方を格納します。
  4. ゼロ以外の列間の最大スパンから最小スパンに行を並べ替えます。

この時点で、私は曖昧になり始めます (申し訳ありませんが、アルゴリズム設計者ではありません)。各行をループして、開始点のインデックスを並べて、できる限りゼロ以外の列インデックスの最大実行を探します。

密行列が正方形である必要があるかどうかを指定しません。私はそうではないと仮定します。

これがどれほど効率的であるか、または Big-O の動作がどうなるかはわかりません。しかし、それは最初から強引な方法です。

于 2009-08-01T20:18:46.110 に答える
1

編集。これは、以下の問題と同じではありません..私の悪い...

しかし、以下の最後のコメントに基づいて、次のものと同等である可能性があります。

  1. 間にゼロ点がなく、垂直方向に最も離れたゼロ点のペアを見つけます。
  2. 間にゼロがない、水平方向に最も離れたゼロ点のペアを見つけますか?

  3. 次に、探している水平領域は、これらの 2 つの点のペアの間に収まる長方形ですか?

    この正確な問題は、Jon Bentley による「Programming Pearls」という本の宝石で説明されており、私が思い出したように、1 次元には解決策がありますが、2 次元以上のバリアントには簡単な答えはありません。 ..

1=D 問題は、事実上、一連の数値の連続する部分集合の最大和を見つけることです。

要素を反復処理し、特定の前の要素からの実行中の合計と、これまでに確認された最大小計 (およびそれを生成した開始要素と終了要素) を追跡します...各要素で、最大実行小計がこれまでに見られた最大合計、これまでに見られた最大および endelemnt がリセットされます...最大現在の合計がゼロを下回る場合、開始要素は現在の要素にリセットされ、現在の合計はゼロにリセットされます...

2-D の問題は、2 色の画像内のピクセルを表す輝度値のストリーム内で、画像内の「最も明るい」四角形の領域を見つけようとする視覚画像処理アルゴリズムを生成する試みから生じました。つまり、輝度値の合計が最も高い、含まれている 2-D サブマトリックスを見つけます。ここで、「輝度」は、ピクセルの輝度値と画像全体の全体的な平均輝度との差によって測定されます (非常に多くの要素が負の値を持っていました)。

編集: 1-D ソリューションを検索するために、この本の第 2 版のコピーを掘り起こしました。その中で、Jon Bentley は、「この版が印刷されるため、2-D バージョンは未解決のままです...」と述べています。 1999年。

于 2009-08-01T20:07:01.203 に答える