Ich habe ungefähr 2 Millionen Datensätze in einer Tabelle gespeichert. Jeder Datensatz hat eine Zahl und etwa 5K boolesche Attribute.
So sieht die Tabelle ungefähr so aus.
%Vor% Und ich habe SUM(A, B) als Summe der Zahlen definiert, bei denen die Attribute Ath und Bth wahr sind.
Zum Beispiel aus den obigen Beispieldaten: SUM(1, 3) = 3 + ... + (-87) , weil das erste und das dritte Attribut T für 3 und -87
Und SUM() kann eine beliebige Anzahl von Parametern annehmen: SUM(1) und SUM(5, 7, ..., 3455) sind alle möglich.
Gibt es einige intelligente Algorithmen, um eine Liste von Attributen zu finden L , wobei SUM(L) zum maximalen Ergebnis führt?
Offensichtlich ist Brute Forcing für diesen großen Datensatz nicht durchführbar.
Es wäre toll, wenn es eine Möglichkeit gäbe, nicht nur die maximale, sondern die oberste N Liste zu finden.
BEARBEITEN Es scheint, als wäre es nicht möglich, die Antwort ohne Brute Forcing zu finden. Wenn ich die Frage ändern würde, um eine "gute Schätzung" zu finden, würde es einen guten Weg dazu geben? Oder, wenn ich sagte, dass die Kardinalität von L auf etwas wie 10 festgelegt ist, würde es eine Möglichkeit geben, das L zu berechnen? Ich würde mit jedem glücklich sein.
Leider ist dieses Problem NP-vollständig . Ihre Optionen beschränken sich darauf, eine gute, aber nicht maximale Lösung mit einem Approximationsalgorithmus zu finden, oder Verzweigung und Verzweigung zu verwenden und zu hoffen, dass Sie die exponentielle Laufzeit nicht erreichen.
Nachweis der NP-Vollständigkeit
Um zu beweisen, dass Ihr Problem NP-vollständig ist, reduzieren wir das Deckblatt Problem auf Ihr Problem. Angenommen, wir haben ein Set U von N -Elementen und ein Set S von M Untersets von U , wobei die Vereinigung aller Sets in S U ist. Das Set-Cover-Problem fragt nach der kleinsten Untermenge T von S , so dass jedes Element von U in einem Element von T enthalten ist. Wenn wir einen Polynomialzeitalgorithmus zur Lösung Ihres Problems hätten, könnten wir das Set-Cover-Problem wie folgt lösen:
Erstellen Sie zuerst eine Tabelle mit M+N rows und M attributes. Die ersten N Zeilen sind "Element" Zeilen, die jeweils einem Element von U entsprechen. Diese haben einen Wert "negativ genug"; -M-1 sollte ausreichen. Für die Elementreihe i ist das j th-Attribut wahr, wenn das entsprechende Element nicht in j th ist, das in S festgelegt wurde.
Die letzten M Zeilen sind "set" Zeilen, die jeweils einer Menge in S entsprechen. Diese haben den Wert 1 . Für die Set-Zeile N+i ist das i th-Attribut false und alle anderen sind wahr.
Die Werte der Elementreihen sind klein genug, dass jede Auswahl von Attributen, die alle Elementreihen ausschließt, jede Auswahl von Attributen übertrifft, die irgendeine Elementreihe enthält. Da die Vereinigung aller Mengen in S U ist, schließt die Auswahl aller Attribute alle Elementreihen aus. Daher ist die beste Auswahl an Attributen diejenige, die die am meisten gesetzten Zeilen enthält, ohne dass Elementreihen enthalten sind. Bei der Konstruktion der Tabelle schließt eine Auswahl von Attributen alle Elementreihen aus, wenn die Vereinigung der entsprechenden Mengen U ist, und wenn dies der Fall ist, wird ihre Punktzahl umso besser sein, je weniger Attribute sie enthält. Somit entspricht die beste Auswahl an Attributen direkt einer minimalen Deckung von S .
Wenn wir einen guten Algorithmus hätten, um eine Auswahl von Attributen auszuwählen, die die maximale Summe erzeugen, könnten wir sie auf diese Tabelle anwenden, um die minimale Deckung eines beliebigen S zu erzeugen. Daher ist Ihr Problem so schwierig wie das NP-Komplettset-Cover-Problem, und Sie sollten Ihre Zeit nicht damit verschwenden, einen effizienten Algorithmus zu entwickeln, um die perfekte Auswahl an Attributen zu erzeugen.
Sie könnten einen Ansatz mit genetischem Algorithmus ausprobieren, der mit einer bestimmten (großen) Anzahl zufälliger Attributkombinationen beginnt und den schlimmsten x% durch das Hinzufügen / Entfernen von Attributen einen bestimmten Prozentsatz der restlichen Population abtötet und mutiert.
Es gibt keine Garantie, dass Sie die optimale Antwort finden, aber eine gute Chance, eine gute Antwort innerhalb einer angemessenen Zeit zu finden.
Es kommen mir keine polynomischen Algorithmen zur Lösung dieses Problems in den Sinn. Ich kann dir nur eine gierige Heuristik vorschlagen:
Berechnen Sie für jedes Attribut die expected_score , d. h. den Summanden, der zu Ihrem SUM führen würde, wenn allein ausgewählt ist. In Ihrem Beispiel lautet der Wert 1 = 3 - 87 = -84.
Sortiere die Attribute nach expected_score in nicht aufsteigender Reihenfolge.
Wenn Sie dieser Reihenfolge folgen, fügen Sie gierig zu L die Attribute hinzu. Rufen Sie actual_score an, die das Attribut a tatsächlich zu Ihrer Summe bringt (es kann besser oder schlechter als expected_score sein, abhängig von den Attributen, die Sie bereits in L haben). Wenn actual_score(a) nicht streng positiv ist, verwerfen Sie a .
Dies gibt dir nicht die optimale L , aber ich denke eine "ziemlich gute".
Hinweis: Siehe unten, warum dieser Ansatz nicht die besten Ergebnisse liefert.
Mein erster Ansatz wäre, mit dem Sonderfall L = {} (der die Summe aller Ganzzahlen ergeben soll) zu beginnen und diesen zu einer Liste von Lösungen hinzuzufügen. Von dort fügen Sie mögliche Attribute als Beschränkungen hinzu. Versuchen Sie in der ersten Iteration jedes Attribut der Reihe nach und merken Sie sich diejenigen, die ein besseres Ergebnis erzielt haben. Fügen Sie die gemerkten nach dieser Iteration in eine Liste von Lösungen ein.
Versuchen Sie in der zweiten Iteration, jedem der gespeicherten ein weiteres Attribut hinzuzufügen. Erinnere dich an alle, die das Ergebnis verbessert haben. Entfernen Sie die Duplikate aus den gespeicherten Attributkombinationen und fügen Sie diese zur Liste der Lösungen hinzu. Beachte, dass {m, n} dasselbe ist wie {n, m}, also überspringe redundante Kombinationen, um deine Sets nicht in die Luft zu jagen.
Wiederholen Sie die zweiten Iterationen, bis keine weiteren möglichen Attribute mehr vorhanden sind, um die endgültige Summe zu verbessern. Wenn Sie dann die Liste der Lösungen nach ihrer Summe sortieren, erhalten Sie die gewünschte Lösung.
Beachten Sie, dass es ~ 20G Möglichkeiten gibt, drei Attribute aus 5k auszuwählen, also können Sie keine Datenstruktur erstellen, die diese enthält, aber Sie müssen sie unbedingt bei Bedarf generieren. Dennoch kann die schiere Menge viele temporäre Lösungen produzieren, so dass Sie diese effizient und vielleicht sogar auf der Festplatte speichern müssen. Sie können die Tatsache ausnutzen, dass Sie nur die Lösungen der vorherigen Iteration für die nächsten Iterationen benötigen, nicht die vorherigen.
Eine weitere Einschränkung besteht darin, dass Sie weniger als N beste Lösungen erhalten, da alle unter L = {} nicht berücksichtigt werden. In diesem Fall würde ich alle möglichen Lösungen akzeptieren, bis Sie N Lösungen haben, und nur wenn Sie die N Lösungen haben, verwerfen Sie diejenigen, die keine Verbesserung gegenüber der schlechtesten geben.
Python-Code :
%Vor%Warum das nicht funktioniert:
Betrachten Sie eine temporäre Lösung, bestehend aus den drei Datensätzen
%Vor%Die Gesamtsumme ist -1. Wenn ich jetzt das erste Attribut auswähle, verwerfe ich den zweiten und dritten Datensatz, was eine Summe von -2 ergibt. Wenn ich das zweite Attribut auswähle, verwerfe ich das erste und das dritte und gebe die gleiche Summe von -2. Wenn ich sowohl das erste als auch das zweite Attribut auswähle, verwerfe ich alle drei Datensätze, was eine Summe von Null ergibt, was eine Verbesserung darstellt.
Tags und Links algorithm