Relative variable Bedeutung für das Boosting

33

Ich suche nach einer Erklärung, wie die relative variable Wichtigkeit in gradientenverstärkten Bäumen berechnet wird, die nicht allzu allgemein / simpel ist wie:

Die Kennzahlen basieren auf der Häufigkeit, mit der eine Variable zum Teilen ausgewählt wurde, gewichtet durch die quadratische Verbesserung des Modells als Ergebnis jeder Teilung und gemittelt über alle Bäume . [ Elith et al. 2008 Eine Arbeits Führung zu verstärkten Regressionsbäume ]

Und das ist weniger abstrakt als:

Ij2^(T)=t=1J1it2^1(vt=j)

Befindet sich die Summation über den Nicht-Endknoten des J- Endknotenbaums T , so ist v t die dem Knoten t zugeordnete Aufteilungsvariable und ^ i 2 t die entsprechende empirische Verbesserung des quadratischen Fehlers infolge der definierten Aufteilung als i 2 ( R l , R r ) = w l w rtJTvtticht2^, wobei ¯ y l , ¯ y r die linke undrechte Tochter Antwortmittel jeweils sind, undwl,wrdie entsprechenden Summen der Gewichte sind. ich2(Rl,Rr)=wlwrwl+wr(yl¯-yr¯)2yl¯,yr¯wl,wr[Friedman 2001, Greedy Function Approximation: eine Gradienten-Boosting-Maschine]

Schließlich fand ich die Elemente des statistischen Lernens (Hastie et al. 2008) hier nicht sehr hilfreich, da der relevante Abschnitt (10.13.1, Seite 367) der obigen zweiten Referenz (die erklärt werden könnte) sehr ähnlich schmeckt durch die Tatsache, dass Friedman Mitautor des Buches ist).

PS: Ich weiß, dass die Maße für die relative variable Wichtigkeit in der Datei summary.gbm im gbm R-Paket angegeben sind. Ich habe versucht, den Quellcode zu durchsuchen, aber ich kann anscheinend nicht herausfinden, wo die eigentliche Berechnung stattfindet.

Brownie-Punkte: Ich frage mich, wie ich diese Pläne in R bekommen kann.

Antoine
quelle
Ich habe gerade eine neue Antwort auf die verknüpfte Frage hinzugefügt, wie die Wichtigkeit von Variablen nach Klassen geplottet werden
see24

Antworten:

55

Ich werde den sklearn- Code verwenden, da dieser im Allgemeinen viel sauberer ist als der RCode.

Hier ist die Implementierung der Eigenschaft feature_importances des GradientBoostingClassifier (ich habe einige Codezeilen entfernt, die den konzeptionellen Aspekten im Wege stehen)

def feature_importances_(self):
    total_sum = np.zeros((self.n_features, ), dtype=np.float64)
    for stage in self.estimators_:
        stage_sum = sum(tree.feature_importances_
                        for tree in stage) / len(stage)
        total_sum += stage_sum

    importances = total_sum / len(self.estimators_)
    return importances

Das ist ziemlich einfach zu verstehen. self.estimators_ist ein Array, das die einzelnen Bäume im Booster enthält, sodass die for-Schleife über die einzelnen Bäume iteriert. Es gibt ein Problem mit der

stage_sum = sum(tree.feature_importances_
                for tree in stage) / len(stage)

Dies kümmert sich um den nicht-binären Antwortfall. Hier passen wir mehrere Bäume in jeder Stufe in einer Eins-gegen-Alles-Weise an. Es ist konzeptionell am einfachsten, sich auf den Binärfall zu konzentrieren, in dem die Summe einen Summanden hat, und das ist gerecht tree.feature_importances_. Im Binärfall können wir das also alles umschreiben als

def feature_importances_(self):
    total_sum = np.zeros((self.n_features, ), dtype=np.float64)
    for tree in self.estimators_:
        total_sum += tree.feature_importances_ 
    importances = total_sum / len(self.estimators_)
    return importances

Also, in Worten, fasse die Wichtigkeit der Merkmale der einzelnen Bäume zusammen und dividiere sie durch die Gesamtzahl der Bäume . Es bleibt abzuwarten, wie die Feature-Wichtigkeiten für einen einzelnen Baum berechnet werden.

Die Wichtigkeitsberechnung eines Baums wird auf Cython-Ebene implementiert , ist jedoch nachvollziehbar. Hier ist eine bereinigte Version des Codes

cpdef compute_feature_importances(self, normalize=True):
    """Computes the importance of each feature (aka variable)."""

    while node != end_node:
        if node.left_child != _TREE_LEAF:
            # ... and node.right_child != _TREE_LEAF:
            left = &nodes[node.left_child]
            right = &nodes[node.right_child]

            importance_data[node.feature] += (
                node.weighted_n_node_samples * node.impurity -
                left.weighted_n_node_samples * left.impurity -
                right.weighted_n_node_samples * right.impurity)
        node += 1

    importances /= nodes[0].weighted_n_node_samples

    return importances

Das ist ziemlich einfach. Iterieren Sie durch die Knoten des Baums. Solange Sie sich nicht an einem Blattknoten befinden, berechnen Sie die gewichtete Verringerung der Knotenreinheit aus der Aufteilung an diesem Knoten und ordnen Sie sie dem Feature zu, für das die Aufteilung ausgeführt wurde

importance_data[node.feature] += (
    node.weighted_n_node_samples * node.impurity -
    left.weighted_n_node_samples * left.impurity -
    right.weighted_n_node_samples * right.impurity)

Teilen Sie dann alles durch das Gesamtgewicht der Daten (in den meisten Fällen die Anzahl der Beobachtungen).

importances /= nodes[0].weighted_n_node_samples

Es lohnt sich daran zu erinnern, dass die Verunreinigung ein gebräuchlicher Name für die Metrik ist, um zu bestimmen, welche Aufteilung beim Wachsen eines Baums vorgenommen werden soll. In diesem Licht fassen wir einfach zusammen, wie viel Aufteilung für jedes Feature es uns ermöglicht hat, die Verunreinigung über alle Aufteilungen im Baum hinweg zu reduzieren.

Im Kontext der Gradientenverstärkung sind diese Bäume immer Regressionsbäume (quadratische Fehler gierig minimieren), die an den Gradienten der Verlustfunktion angepasst sind.

Matthew Drury
quelle
Vielen Dank für diese sehr ausführliche Antwort. Lassen Sie mir etwas Zeit, um es sorgfältig durchzugehen, bevor ich es akzeptiere.
Antoine
4
Während es den Anschein hat, dass verschiedene Verunreinigungskriterien verwendet werden können, war der Gini-Index nicht das von Friedman verwendete Kriterium. Wie in meiner Frage und Zeile 878 Ihres dritten Links erwähnt, verwendete Friedman das mittlere Quadratfehler-Verunreinigungskriterium mit Verbesserungsbewertung . Wenn Sie diesen Abschnitt Ihrer Antwort aktualisieren könnten, wäre das großartig. Und ja, Sie haben recht, es scheint, dass die Gewichte tatsächlich die Anzahl der Beobachtungen sind.
Antoine
3
oder könnte es Ihre Antwort noch verbessern, wenn Sie sowohl den Teil des Gini-Index als auch das ursprüngliche Kriterium von Friedman beibehalten und betonen, dass der erste Teil für die Klassifizierung und der zweite für die Regression verwendet wird?
Antoine
Antoine, danke für dieses Update. Es ist sehr hilfreich zu wissen, dass der mittlere quadratische Fehler das Verbesserungskriterium für die Regressionsbäume ist. Es war nicht offensichtlich, wie das für die Klassifizierung verwendet werden würde. Ich denke jedoch, dass auch bei der Gradientenanhebung für die Klassifizierung weiterhin Regressionsbäume verwendet werden, im Gegensatz zu Klassifizierungsbäumen. Zumindest in Python wird die Regressionsanalyse für den aktuellen Fehler in jeder Verstärkungsstufe durchgeführt.
Ziemlich Nerdy
Ihr habt Recht mit Regressionsbäumen.
Matthew Drury