Angenommen, ich habe Klassifizierer C_1 ... C_n, die in dem Sinne disjunkt sind, dass keine zwei bei derselben Eingabe true zurückgeben (z. B. die Knoten in einem Entscheidungsbaum). Ich möchte einen neuen Klassifikator erstellen, der die Vereinigung einer Teilmenge von diesen darstellt (z. B. möchte ich entscheiden, welche Blätter eines Entscheidungsbaums eine positive Klassifizierung ergeben sollen). Dabei wird es natürlich einen Kompromiss zwischen Sensitivität und positivem Vorhersagewert geben. Daher würde ich gerne eine ROC-Kurve sehen. Im Prinzip könnte ich dies tun, indem ich alle Untergruppen der Klassifikatoren aufzähle und die resultierende Empfindlichkeit und PPV berechne. Dies ist jedoch unerschwinglich teuer, wenn n mehr als etwa 30 beträgt. Auf der anderen Seite gibt es mit ziemlicher Sicherheit einige Kombinationen, die nicht pareto-optimal sind. Es könnte also eine verzweigte und gebundene Strategie geben, oder so etwas.
Ich möchte Ratschläge dazu erhalten, ob dieser Ansatz wahrscheinlich fruchtbar ist und ob es Arbeit gibt oder ob Sie in der obigen Situation Ideen zur effizienten Berechnung der ROC-Kurve haben.
quelle
Antworten:
Wenn ich die Frage richtig verstanden habe, haben Sie einen Algorithmus trainiert, der Ihre Daten in disjunkte Cluster aufteilt. Nun mögen Sie Vorhersage zuweisen 1 zu einem gewissen Teil der Cluster und 0 auf den Rest von ihnen. Und unter diesen Teilmengen möchten Sie die pareto-optimalen finden, dh diejenigen, die die wahre positive Rate bei einer festgelegten Anzahl positiver Vorhersagen maximieren (dies entspricht der Festlegung des PPV). Ist es richtig?N 1 0
Das klingt sehr nach einem Rucksackproblem ! Clustergrößen sind "Gewichte" und die Anzahl der positiven Stichproben in einem Cluster sind "Werte". Sie möchten Ihren Rucksack mit fester Kapazität mit so viel Wert wie möglich füllen.
Das Rucksackproblem hat mehrere Algorithmen, um exakte Lösungen zu finden (z. B. durch dynamische Programmierung). Aber eine nützliche gierig Lösung ist Ihre Cluster in absteigender Reihenfolge der sortieren (d. h. Anteil positiver Proben) und nimm das erstek. Wenn Siekvon0nachN nehmen, können Sie Ihre ROC-Kurve sehr billig skizzieren.v a l u ew e i gh t k k 0 N
Und wenn Sie den ersten k - 1 - Clustern und dem Zufallsbruchteil p ∈ [ 0 , 1 ] der Stichproben im k - ten Cluster zuweisen , erhalten Sie die Obergrenze für das Rucksackproblem. Hiermit können Sie die Obergrenze für Ihre ROC-Kurve zeichnen.1 k - 1 p ∈ [ 0 , 1 ] k
Hier ist ein Python-Beispiel:
Dieser Code wird ein schönes Bild für Sie zeichnen:
Die blauen Punkte sind (FPR, TPR) Tupel für alle Teilmengen, und die rote Linie verbindet (FPR, TPR) für die paretooptimalen Teilmengen.210
Und jetzt das bisschen Salz: Sie mussten sich überhaupt nicht um Teilmengen kümmern ! Was ich getan habe, ist das Sortieren der Baumblätter nach dem Anteil der positiven Proben in jeder. Was ich aber bekommen habe, ist genau die ROC-Kurve für die probabilistische Vorhersage des Baumes. Dies bedeutet, dass Sie den Baum nicht übertreffen können, indem Sie seine Blätter anhand der Zielhäufigkeiten im Trainingssatz von Hand auswählen.
Sie können sich entspannen und die normale Wahrscheinlichkeitsvorhersage verwenden :)
quelle
Ich könnte vorschlagen, dass Sie eine gierige Methode anwenden. Geben Sie einen Klassifikator an, um zu beginnen, und fügen Sie den Klassifikator hinzu, mit dem das Ensemble die beste Leistungsverbesserung erzielt. Wenn keine Verbesserung erzielt werden kann, schließen Sie weitere Klassifikatoren ein, und beenden Sie den Vorgang. Sie werden mit jedem Klassifikator beginnen. Die Komplexität wird höchstens N * N sein.
Ich habe noch eine Frage: Was meinen Sie mit "Pareto optimal", insbesondere in Ihrem Kontext? Ich fand aus dem Wiki diese Erklärung, https://en.wikipedia.org/wiki/Pareto_efficiency
Die Verbesserung der Pareto-Effizienz ist für jeden Teilnehmer, der jedem Klassifikator entsprechen kann. Wie definieren Sie die Verbesserung gegenüber einem Klassifikator?
quelle