Ich arbeite an einem Java-Orakel-basierten Projekt, bei dem ich an einem Problem festhalte, das meiner Ansicht nach eine analytische Lösung erfordert. Ich suche nach einer Lösung, die entweder auf einer SQL-Abfrage oder einem beliebigen Algorithmus oder einem beliebigen freien Analysewerkzeug basiert, dem ich folgen kann, um die gewünschten Ergebnisse zu erzielen.
Problembeschreibung: Lassen Sie uns sagen, ich habe unter Tabelle mit columnA-D und letzte Spalte als Score, ich möchte ein Kriterium für Werte für jede der Spalten finden, die, wenn in SQL-Klausel kombiniert wird mir immer positiven Wert für Score-Spalte geben. Also, welche Kombination von Spalte A-D wird mir immer eine positive Bewertung geben?
%Vor%Erwartetes Ergebnis für den obigen Datensatz: - Die visuelle Interpretation des obigen Datensatzes gibt mir die Bedingung: "ColumnA = 0 und columnB & gt; 10 und columnC & lt; 5 stellen die Bewertung immer & gt; 0" sicher. (optisch hat seine eindeutige columnD keinen Effekt).
Bitte beachten Sie, dass der obige Datensatz der Einfachheit halber verwendet wird. In Wirklichkeit enthält mein Projekt etwa 40 Spalten mit fast 2500 Zeilen. Eine Sache ist sicher, dass jede Spalte einen endlichen Wertebereich hat.
Hier ist ein Algorithmus, mit dem ich angefangen habe (brauche Eingaben, um ihn weiter zu verfeinern, wenn jemand denkt, dass ich in der richtigen Richtung bin):
Vorbereitung: Erstelle eine Liste aller möglichen Ausdrücke wie A = 0, B & gt; 10, C & lt; 5 (für 40 Spalten habe ich insgesamt ungefähr 150 Ausdrücke abgeschlossen)
Nennen wir es "Ausdruck" Variable.
Alogrithm für den 1. Lauf:
setze totalPositiveRows = wähle count (*) aus meinen Tabellen, wo Score & gt; 0;
set totalNegativeRows = wähle count (*) aus meinen Tabellen aus, wo punkte & lt; 0;
Berechnen Sie für jeden Ausdruck in Ausdrücken die folgenden drei Variablen set positivePercentage = finde den Prozentsatz von totalPositiveRows, die diesen Ausdruck erfüllen; // wie wenn 60 Zeilen von insgesamt 100 Zeilen mit der Punktzahl & gt; 0 expr befriedigen, dann positivePercentage = 60%
%Vor%Set initialexpr = Wähle einen Ausdruck mit einem maximalen Wert von diffPercentage set initalPositivePercentage = Wählen Sie den entsprechenden positivenPercentage-Wert; set initalNegativePercentage = wähle den entsprechenden negativenPercentage-Wert; Mein Gedanke ist, dass ich jetzt initalexpr erweitern muss, bis initalNegativePercentage 0 wird.
Alogrithm für nachfolgende Läufe bis initalNegativePercentage wird 0: -
Berechnen Sie für jeden Ausdruck in Ausdrücken folgende drei Variablen | setze newexpr = initialexpr + "und" + expr; set positivePercentage = finde den Prozentsatz von totalPositiveRows, die newexpr erfüllen; set negativePercentage = finde den Prozentsatz von totalNegativeRows, die newexpr erfüllen;
// berechnen wie viel negativer Prozentsatz es reduziert hat? gesetzt positivReduktion = initialPositivPercentage-positivPercentage; Negativ gesetztReduktion = initialNegativPercentage-negativPercentage; if (negativeReduktion & gt; = positiveReduktion) // Notiere es sonst // verwerfe es
Wählen Sie den Ausdruck aus, der eine maximale negative Reduktion ergibt, der zu einem neuen Anfangsausdruck wird. Set initialexpr = Wähle einen Ausdruck mit einem maximalen Wert von negativerReduktion set initalPositivePercentage = wähle den entsprechenden Wert; set initalNegativePercentage = wähle den entsprechenden Wert;
Wiederholen Sie den obigen Algorithmus.
Bitte kommentieren.
Unten ist eine Brute-Force-Lösung. Dies könnte auch eine gute Frage für die theoretische Informatikwebsite sein. Ich denke, dass dies ein NP-vollständiges Problem ist, das dem Booleschen Erfüllbarkeit ähnlich ist, aber das ist nur ein wildes vermuten. Es mag einen klügeren Weg geben, das zu lösen, aber ich glaube nicht, dass ich es finden werde.
Die Grundidee besteht darin, jeden Ausdruck mit jedem eindeutigen Wert für eine Spalte zu kreuzen und dann alle Spalten kreuzweise zu verbinden. Die Tabelle wird mit jeder Ausdrucksliste abgefragt und eine Zählung für positive und negative Bewertungen generiert. Wenn der Ausdruck die erwartete Anzahl positiver und keine der negativen Bewertungen zurückgibt, ist er gültig.
Dies setzt voraus, dass Sie nur die Ausdrücke > , < und = verwenden. Jede neue Spalte oder jeder Ausdruck wird dieses Problem exponentiell verlangsamen.
Testschema
%Vor%Codewand
%Vor%Ergebnisse
Die Ergebnisse scheinen korrekt zu sein. Sie sind etwas anders als deins, weil "columnB & gt; 10" falsch ist.
%Vor%Probleme
Dieser Brute-Force-Ansatz ist auf mindestens zwei Arten äußerst ineffizient. Sogar für dieses einfache Beispiel benötigt es 6370 Abfragen. Und die Ergebnisse können Duplikate enthalten, die nicht-trivial zu reduzieren sind. Oder vielleicht wirst du Glück haben und es gibt so wenige Lösungen, die du dir ansehen kannst.
Es gibt einige Dinge, die Sie tun können, um die Abfrageleistung zu verbessern. Am einfachsten wäre es, jede Bedingung einzeln zu prüfen und sie zu verwerfen, wenn sie für die Zählungen nichts "gewinnt".
Optimierungen
Einzelne Ausdrücke, die keine positiven Ergebnisse liefern, werden ausgeschlossen. Mit den Beispieldaten reduziert dies die Anzahl der Abfrageausführungen von 6370 auf 441.
Das parallele Ausführen des Prozesses kann die Leistung ebenfalls um eine Größenordnung verbessern. Es würde wahrscheinlich eine parallele Pipeline-Funktion erfordern.
Aber selbst eine 100-fache Leistungsverbesserung kann bei einem NP-vollständigen Problem nicht helfen. Möglicherweise müssen Sie einige zusätzliche "Abkürzungen" basierend auf Ihren Beispieldaten finden.
Es kann hilfreich sein, die Abfrage, die die Testabfragen generiert, auszudrucken, indem Sie eine der dbms_output.put_line -Anweisungen auskommentieren. Fügen Sie count(*) hinzu, um zu sehen, wie viele Abfragen ausgeführt werden, und führen Sie einen kleineren Datensatz aus, um eine Schätzung für die Dauer zu erstellen.
Wenn die Schätzung eine Milliarde Jahre beträgt und Sie keine Tricks kennen, um die Brute-Force-Methode schneller arbeiten zu lassen, ist es vielleicht an der Zeit, diese Frage auf Ссылка
Die Idee der Lösung ist, dass die Spalten unabhängig sind. So kann es Spalte für Spalte gelöst werden.
Sie können sich also vorstellen, dass Sie etwas im multidimensionalen Raum suchen und bauen. Jede Spalte repräsentiert eine Dimension mit Werten von -inf bis +inf . Und bauen Sie die Lösungsdimension nach Dimensionen auf.
A=1 => false, A=0 => true. Wenn Sie Dimensionsintervalle auf SQL-Ebene verbinden möchten, können Sie die LAG-Funktion verwenden. Mit der Partitionierung und Fensterung ordnen Sie Zeilen nach einer Spalte an. Dann berechnen Sie einen Wert wahr / falsch in einer gekochten Spalte. Und in der nächsten gekochten Spalte mit der LAG-Funktion erkennen Sie, ob sich das Wahr / Falsch-Flag gegenüber der vorherigen Zeile geändert hat.
%Vor% Diese Abfrage zeigt, dass der Wert B=15 signifikant ist, da sich dort das score_flag ändert.
Ich bin mir nicht sicher über den Wert B=10 in der Frage. Da dieser mit positiven und negativen Score-Werten verknüpft ist. Soll es dann ein- oder ausgeschlossen werden?
Sehr interessantes Problem. Mein Vorschlag basiert auf der Funktion check_column, Code unten. Ausführungsbeispiele:
%Vor%In Ihrem Beispiel Zeile 3, SpalteB habe ich den Wert 10 durch 32 ersetzt, weil das Beispiel nicht gut war und die Bedingung und die Spalte B & gt; 10 nicht richtig waren. Col04 dient nur zur Präsentation, da es neutral ist. Sie müssen Ausgabezeichenfolgen in Java oder SQL zusammenhalten, aber das sollte kein Problem sein.
Ich nannte die Basistabelle als scores und dann die erstellte Ansicht positives . Anstatt Daten in einer temporären Tabelle anzeigen zu können, sollte die Ausführung viel schneller sein.
Funktion ist:
%Vor%Diese Lösung ist weder optimiert noch stark getestet, bitte seien Sie vorsichtig. Wenn Sie die Oracle-Version & lt; 11 ersetze listagg durch wmsys.wm_concat.
Folgendes würde ich tun:
Nun für jede "Eingabe" -Spalte:
Beachten Sie, dass dies alles voraussetzt, dass Score (hypothetisch) von kontinuierlichen Bereichen in den "Eingabe" -Spalten gesteuert wird. Es wird nicht in der Lage sein, Bedingungen von "& lt; 5 oder & gt; 10" oder "& lt; & gt; 12" zu erkennen. Da keines davon in Ihrem Beispiel ist, spekuliere ich, dass es in Ordnung ist, aber wenn nicht, dann sind Sie wieder bei NP-complete ...
SQL zum Generieren von Abfragen zum Ausgeben der obigen Bedingungen für ein beliebiges Schema sollte relativ einfach zu erstellen sein. Lassen Sie es mich wissen, wenn Sie eine Hand damit haben wollen und ich werde mich darum kümmern.
Dies gibt Ihnen den Bereich jeder Spalte für positive Bewertungen und dann den Bereich dieser Spalten für alle Bewertungen. Wo diese Bereiche unterschiedlich sind, haben Sie eine Korrelation
Hier ist ein Algorithmus, mit dem ich begonnen habe (brauche Eingaben, um ihn weiter zu verfeinern, wenn jemand denkt, dass ich in der richtigen Richtung bin):
Vorbereitung: Erstelle eine Liste aller möglichen Ausdrücke wie A = 0, B & gt; 10, C & lt; 5 (für 40 Spalten habe ich insgesamt ungefähr 150 Ausdrücke abgeschlossen)
Nennen wir es "Ausdruck" Variable.
Alogrithm für den ersten Lauf:
%Vor%Ich denke, dass ich jetzt initalexpr erweitern muss, bis initalNegativePercentage 0 wird.
Alogrithm für nachfolgende Läufe bis zum AnfangNegativePercentage wird 0: -
%Vor%Bitte kommentieren.
Hier ist eine einfache Implementierung, die zu einem komplizierten Regelwerk führen wird.
Sei A die Menge aller Eingaben, die zu einer positiven Bewertung führen, und B die Menge aller Eingaben, die nicht zu einer positiven Bewertung führen.
Wenn ein Satz von Eingängen in A und B enthalten ist, gibt keine Regel alle positiven und keine negativen Werte. Unabhängig davon ist A-B eine Reihe von Regeln, die nur positive Werte ergeben, und kein Satz von Regeln, der alle Nicht-Positive ausschließt, kann besser sein.
In Ihrem Beispiel lauten unsere Regeln: (colA = 0, colB = 40, colC = 2, colD = 3), (colA = 0, colB = 10, colC = 3, colD = 3).