大きなスパース行列で「最大の」高密度サブ行列を見つける

StackOverflow https://stackoverflow.com/questions/1217355

質問

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

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

Googleでのクイックスキャンでは、厳密ではないが正確な結果が多数得られるようです。 どの用語を探すべきですか？

編集：明確にするため。サブ行列は連続的ではない 。実際、行と列の順序は完全に任意であるため、隣接関係は完全に無関係です。

Chad Okereのアイデアに基づいた思考

  1. 最大数から最小数への行の順序付け（必要ではありませんが、perfに役立つ可能性があります）
  2. ＆quot; large＆quot;がある2つの行を選択します。重複
  3. 重複を削減しない他のすべての行を追加
  4. 設定したレコード
  5. 重複を最小限に抑える行を追加します
  6. 結果が小さくなるまで＃3で繰り返します
  7. 別の開始ペアで＃2からやり直す
  8. 結果が十分であると判断するまで続行
役に立ちましたか？

解決

あなたはこのようなものが欲しいと思います。次のようなマトリックスがあります

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サブマトリックスの作成。

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

その後、しばらくしてそれ以上見つからない場合に停止します。

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

他のヒント

これは Netflixの問題ですか

MATLAB または他のスパースマトリックスライブラリには、それを処理します。

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

各行の1Dアプローチが役立つかもしれません。アルゴリズムは次のようになります。

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

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

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

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

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

しかし、以下の最後のコメントに基づいて、それは以下と同等かもしれません：

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

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

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

1 = D問題は、事実上、一連の数値の連続するサブセットの最大合計を見つけることです：

特定の前の要素から現在までの合計、およびこれまでに見られた最大小計（およびそれを生成した開始および終了要素）を追跡しながら、要素を反復処理します... maxrunning小計がこれまでに見られた最大合計よりも大きく、これまでに見られた最大値とendelemntはリセットされます...最大実行合計がゼロを下回ると、開始要素は現在の要素にリセットされ、実行合計はゼロにリセットされます...

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

編集：1次元ソリューションを調べるために、この本の第2版のコピーを整理しました。その中で、ジョンベントレーは次のように述べています。 。＆quot; 1999年です。

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

したがって、これは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
    3. を最大化するサブマトリックスを選択します

また、初期の完全な行列から保存する必要がある最小行数に関していくつかの考慮事項があり、最大 D 値。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top