Effizienter Algorithmus zur Berechnung der ROC-Kurve für einen Klassifikator, der aus einem Ensemble von disjunkten Klassifikatoren besteht

13

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.

Josh Brown Kramer
quelle
Klassifizieren Sie jeden Eingabefall als wahr oder falsch?
image_doctor
@image_doctor: yes
Josh Brown Kramer
Ich bin mir nicht sicher, "... dass in dem Sinne disjunkt sind, dass keine zwei bei derselben Eingabe wahr zurückkehren ..." und Sie klassifizieren zu einer Binärausgabe, wie Sie mehr als zwei Klassifikatoren in Ihrer haben können Ensemble, ich vermisse wahrscheinlich etwas?
image_doctor
@image_doctor: Sie denken vielleicht, ich sage, dass keine zwei Klassifikatoren dieselbe Ausgabe auf derselben Eingabe zurückgeben. Ich sage, keine zwei werden wahr zurückkehren. Sie können beide false zurückgeben.
Josh Brown Kramer
1
Vielleicht kann Ihnen dieses Papier über eine theoretisch optimale Art der Kombination von Klassifikatoren für ROC (oder Papiere, in denen es zitiert wird) helfen, den Stand der Technik zu verstehen: M. Barreno, A. Cardenas, JD Tygar, Optimale ROC-Kurve für eine Kombination von Klassifikatoren, Fortschritte in neuronalen Informationsverarbeitungssystemen, 2008.
Valentas

Antworten:

1

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?N10

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.veinlueweichGhtkk0N

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.1k-1p[0,1]k

Hier ist ein Python-Beispiel:

import numpy as np
from itertools import combinations, chain
import matplotlib.pyplot as plt
np.random.seed(1)
n_obs = 1000
n = 10

# generate clusters as indices of tree leaves
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import make_classification
from sklearn.model_selection import cross_val_predict
X, target = make_classification(n_samples=n_obs)
raw_clusters = DecisionTreeClassifier(max_leaf_nodes=n).fit(X, target).apply(X)
recoding = {x:i for i, x in enumerate(np.unique(raw_clusters))}
clusters = np.array([recoding[x] for x in raw_clusters])

def powerset(xs):
    """ Get set of all subsets """
    return chain.from_iterable(combinations(xs,n) for n in range(len(xs)+1))

def subset_to_metrics(subset, clusters, target):
    """ Calculate TPR and FPR for a subset of clusters """
    prediction = np.zeros(n_obs)
    prediction[np.isin(clusters, subset)] = 1
    tpr = sum(target*prediction) / sum(target) if sum(target) > 0 else 1
    fpr = sum((1-target)*prediction) / sum(1-target) if sum(1-target) > 0 else 1
    return fpr, tpr

# evaluate all subsets
all_tpr = []
all_fpr = []
for subset in powerset(range(n)):
    tpr, fpr = subset_to_metrics(subset, clusters, target)
    all_tpr.append(tpr)
    all_fpr.append(fpr)

# evaluate only the upper bound, using knapsack greedy solution
ratios = [target[clusters==i].mean() for i in range(n)]
order = np.argsort(ratios)[::-1]
new_tpr = []
new_fpr = []
for i in range(n):
    subset = order[0:(i+1)]
    tpr, fpr = subset_to_metrics(subset, clusters, target)
    new_tpr.append(tpr)
    new_fpr.append(fpr)

plt.figure(figsize=(5,5))
plt.scatter(all_tpr, all_fpr, s=3)
plt.plot(new_tpr, new_fpr, c='red', lw=1)
plt.xlabel('TPR')
plt.ylabel('FPR')
plt.title('All and Pareto-optimal subsets')
plt.show();

Dieser Code wird ein schönes Bild für Sie zeichnen:

TPR, FPR und optimale Kurve

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 :)

David Dale
quelle
Großartige Idee. Theoretisch könnte es immer noch eine exponentiell große Anzahl von "positiven Anrufen" geben, aber in der Praxis ist dies wahrscheinlich kein Problem.
Valentas
Warum exponentielle Anzahl von Anrufen? Ich berechne Wert / Gewicht für jeden Cluster (nimmt lineare Zeit in Anspruch), sortiere sie (N * log (N)) und bewerte TPR und FPR für jeden ersten K-Cluster (kann auch linear gemacht werden).
David Dale
Sie lösen den Rucksack für jeden möglichen Wert positiver Vorhersagen, und es gibt eine exponentielle Anzahl von Teilmengen. Dies ist jedoch eine theoretische Technik, wenn Sie speziell nach den Punkten in der konvexen Hülle fragen, was nicht interessant ist - dies sollte die akzeptierte Antwort sein.
Valentas
@Valentas, OK, ich verstehe deinen Standpunkt. Wenn Sie jedoch in einigen Blättern eine zufällige Vorhersage treffen, können Sie jeden Punkt in der konvexen Hülle erreichen. In diesem Fall ist der Rumpf also die ROC selbst.
David Dale
@DavidDale, um zusammenzufassen: 1) Jede Strategie, die in Bezug auf (Sensitivität, PPV) paretooptimal ist, maximiert die Anzahl von echten Positiven unter Strategien mit dieser Anzahl von positiven Vorhersagen. 2) Dies ist das Rucksackproblem. 3) Es ist bekannt, dass die Auswahl der Knoten nach Anzahl der positiven Beispiele / Anzahl der Beispiele eine gute ungefähre Lösung für das Rucksackproblem darstellt. 4) Aber das ist genauso, als würde man einen Schwellenwert für die Wahrscheinlichkeiten festlegen.
Josh Brown Kramer
0

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

Durch eine Neuzuweisung kann das Wohlbefinden mindestens eines Teilnehmers verbessert werden, ohne dass das Wohlbefinden eines anderen Teilnehmers beeinträchtigt wird.

Die Verbesserung der Pareto-Effizienz ist für jeden Teilnehmer, der jedem Klassifikator entsprechen kann. Wie definieren Sie die Verbesserung gegenüber einem Klassifikator?

Wilhelm
quelle
1
Was ich damit meine, ist Folgendes: Wenn ich Ensembles 1 und 2 mit (Empfindlichkeit, positiver Vorhersagewert) = (.90, .80) bzw. (.97, .93) habe, dann ist 1 nicht paretooptimal, weil es gibt ein anderes Ensemble, nämlich 2, das es in jeder Hinsicht übertrifft. In Bezug auf Ihren vorgeschlagenen Algorithmus: Es gibt einen Kompromiss zwischen Empfindlichkeit und PPV, sodass "das Ensemble die beste Leistungsverbesserung erzielt" nicht genau definiert ist.
Josh Brown Kramer