Finden Sie die „größte“ dichte Untermatrix in einer großen Sparse Matrix

Question

eine große Sparse Matrix Given (sagen 10k + von 1 M +) Ich brauche eine Teilmenge zu finden, die nicht notwendigerweise kontinuierlich, der Zeilen und Spalten, die eine dichte Matrix (alle Nicht-Null-Elemente) zu bilden. Ich möchte diese Untermatrix so groß wie möglich sein (nicht die größte Summe, aber die größte Anzahl der Elemente) innerhalb einiger Seitenverhältnis Einschränkungen.

Gibt es bekannte exakte oder aproxamate Lösungen für dieses Problem?

Ein schneller Scan auf Google scheint eine Menge close-aber-nicht-genau Ergebnisse. Was Begriffe soll ich suchen?

---

edit: Nur um zu klären; die Untermatrix muss nicht kontinuierlich sein . In der Tat ist die Zeilen- und Spaltenreihenfolge völlig willkürlich so adjacency ist völlig irrelevant.

---

Ein Gedanke basiert auf Chad Okere Idee

1. Bestellen Sie die Zeilen von der größten Zählung kleinste Zahl (nicht notwendig, aber vielleicht perf helfen)
2. Wählen Sie zwei Zeilen, die eine „große“ Überlappung
haben
3. Fügen Sie alle anderen Zeilen, die die Überlappung nicht verringern
4. Datensatz, der eingestellt
5. hinzufügen, was Zeile reduziert die Überlappung durch die am wenigsten
6. Wiederholen Sie auf # 3, bis das Ergebnis wird zu klein
7. Von vorn anfangen auf # 2 mit einem anderen Startpaar
8. Weiter, bis Sie das Ergebnis ist gut entscheiden genug

Answer 1

Ich nehme an, Sie so etwas wie dies wollen. Sie haben eine Matrix wie

1100101
1110101
0100101

Sie wollen Spalten 1,2,5,7 und Zeilen 1 und 2, nicht wahr? Das Submatrix würde mit 8 Elementen 4x2. Oder könnten Sie mit Spalten gehen 1,5,7 mit Reihen 1,2,3, die eine 3x3-Matrix sein würde.

Wenn Sie eine ‚ungefähre‘ Methode möchten, können Sie mit einem einzigen Nicht-Null-Element starten, dann gehen Sie auf eine andere Nicht-Null-Element zu finden und es in die Liste der Zeilen und Spalten hinzufügen. Irgendwann Sie in ein Nicht-Null-Element ausgeführt werden, das, wenn es Zeilen und Spalten ist, wurde zu Ihrer Sammlung, Ihre Sammlung wäre nicht mehr völlig ungleich Null.

Also für die obige Matrix, wenn man 1,1 und 2,2 hinzugefügt würden Sie Reihen und Spalten 1,2 1,2 in Ihrer Sammlung. Wenn Sie hinzufügen 3,7 versucht würde es ein Problem verursachen, weil 1,3 null ist. So konnte man nicht hinzufügen. Sie könnten allerdings 2,5 und 2,7 hinzufügen. Erstellen der 4x2 Submatrix.

Sie würden im Grunde durchlaufen, bis Sie keine weiteren neuen Zeilen und Spalten hinzufügen finden. Das würde Ihnen auch ein lokales Minimum bekommen. Sie könnten das Ergebnis speichern und wieder mit einem anderen Startpunkt beginnen (vielleicht eine, die nicht in der aktuelle Lösung paßten).

Dann hör nur, wenn Sie nicht mehr nach einer Weile finden.

Das, natürlich, würde eine lange Zeit, aber ich weiß nicht, ob Sie in der Lage sein werden es mehr schnell zu tun.

Answer 2

Ist das ein Netflix Problem ?

MATLAB oder einige andere Sparse Matrix Bibliotheken könnte müssen Wege damit umgehen.

Ist Ihre Absicht Ihre eigenen zu schreiben?

Vielleicht ist der 1D-Ansatz für jede Zeile würde Ihnen helfen. Der Algorithmus könnte wie folgt aussehen:

1. Schleife über jede Zeile
2. Finden Sie den Index des ersten Nicht-Null-Element
3. Finden Sie den Index des Nicht-Null-Zeile-Elements mit der größten Spannweite zwischen Nicht-Null-Spalten in jeder Zeile und speichern Sie beide.
4. sortiert die Zeilen vom größten zum kleinsten Abstand zwischen Nicht-Null-Spalten.

An diesem Punkt beginne ich immer fuzzy (sorry, nicht einen Algorithmus Designer). Ich würde versuchen, über jede Zeile Looping, die Indizes des Ausgangspunktes Schlange, für den maximalen Nicht-Null-Lauf von Spaltenindizes suchen, was ich kann.

Sie nicht angeben, ob die dichte Matrix quadratisch zu sein hat. Ich nehme an, es nicht.

Ich weiß nicht, wie effizient das ist oder was sein Big-O Verhalten wäre. Aber es ist eine Brute-Force-Methode zu beginnen.

Answer 3

EDIT. Dies ist nicht das gleiche wie das Problem unten .. Mein schlechte ...

Aber basierend auf den letzten Kommentar unten, könnte es zu folgendem equivilent werden:

1. Finden Sie das am weitesten vertikal getrennten Paar von Nullpunkten, die keinen Nullpunkt zwischen ihnen.
2. Finden Sie das am weitesten horizontal getrennten Paar von Nullpunkten, die keine Nullen zwischen ihnen?

3. Dann wird der horizontale Bereich Sie suchen ist das Rechteck, das zwischen diesen beiden Paaren von Punkten paßt?

   Das genaue Problem ist in einem Juwel von einem Buch diskutiert „Programming Pearls“ von Jon Bentley genannt, und, wie ich mich erinnere, obwohl es eine Lösung in einer Dimension ist, gibt es keine einfache Antwort für die 2-d oder höher dimensionale Varianten ...

Das 1 = D Problem ist, effektiv, finden Sie die größte Summe einer zusammenhängenden Teilmenge von einer Reihe von Zahlen:

iterieren durch die Elemente, aus einer laufenden Summe von einem bestimmten Element vorhergehenden und der maximale Wert Ihrer gesehen bisher (und der Anfang und das Ende, die es elemnt generateds) zu verfolgen ... bei jedem Element, wenn der maxrunning subtotale ist größer ist als die maximale gesamten bisher, die max so weit und endelemnt ist gesehen zurückgesetzt gesehen ... Wenn die maximale laufende Gesamt unter Null geht, ist das Startelement wieder auf das aktuelle Element und die laufende Summe auf Null zurückgesetzt ...

Das 2-D-Problem kam aus einem Versuch, einen visuellen Bildverarbeitungsalgorithmus zu erzeugen, der in einem Strom von bright Werten zu finden, wurde versucht, die Pixel darstellen, in einem 2-Farbbild, findet den „hellsten“ rechteckigen Bereich innerhalb der Bild. dh findet die enthaltene 2-D-Sub-Matrix mit der höchsten Summe von Helligkeitswerten, wobei „Helligkeit“ durch die Differenz zwischen dem brighness Wert des Pixels und der Gesamtdurchschnitt der Helligkeit des gesamten Bildes wurde gemessen (so viele Elemente hatten negative Werte)

EDIT: Um die 1-D-Lösung nachschlagen ich meine Kopie der zweiten Auflage dieses Buches ausgebaggert, und darin, Jon Bentley sagt: „Die 2-D-Version bleibt ungelöst, da diese Ausgabe in Druck geht ... "das war im Jahr 1999.

Answer 4

Ich weiß, dass Sie nicht mehr daran zu arbeiten, aber ich dachte, es könnte jemand die gleiche Frage wie ich in der Zukunft hat.

So, nach dieser Realisierung ist ein NP-hard Problem (durch Reduktion auf MAX-CLIQUE) entschied ich mich mit einer Heuristik zu kommen, das für mich bisher gut gearbeitet hat:

Da ein N x M Binär / boolean Matrix, finden sie eine große, dichte Submatrix:

Teil I : auskömmlichen Kandidat Untermatrizen

1. Betrachten Sie jede der N Reihen a M -dimensionalen binären Vektor zu sein, v_i , wobei i = 1 bis N
2. Berechnen einer Distanzmatrix für die N Vektoren, die die Hamming-Distanz
using
3. Mit der UPGMA (ungewichtet Paargruppenmethode mit arithmetisches Mittel) Algorithmus auf Clustervektoren

Zu Beginn jeder der v_i Vektoren ist ein Singleton-Cluster. Schritt 3 oben (clustering) gibt den Befehl, dass die Vektoren in Untermatrizen kombiniert werden sollen. So hat jeder interne Knoten in der hierarchischen Gruppierungsbaum ist ein Kandidat Submatrix.

Teil II : Partitur und Rang Kandidaten Untermatrizen

1. Für jede Submatrix berechnen D , die Anzahl der Elemente in dem dichten Teilmenge der Vektoren für die Submatrix durch die Säule mit einer Eliminierung oder mehr Nullen.
2. die Submatrix Wählen Sie die D
maximiert

Ich hatte auch einige Überlegungen in Bezug auf die min Anzahl der Zeilen, die von der anfänglichen vollständigen Matrix erhalten werden mußten, und ich würde alle Kandidaten Untermatrizen verwerfen, die diese Kriterien nicht erfüllt haben, bevor sie eine Submatrix mit max Auswählen D Wert.