Bootstrap-Aggregation - Bootstrap aggregating

Teil einer Serie über
Maschinelles Lernen und Data Mining
Probleme Einstufung Clustering Rückschritt Anomalieerkennung Datenreinigung AutoML Vereinsregeln Verstärkungslernen Strukturierte Vorhersage Feature-Engineering Feature-Lernen Online lernen Teilüberwachtes Lernen Unbeaufsichtigtes Lernen Rangieren lernen Grammatikeinführung
Überwachtes Lernen ( Klassifikation  • Regression ) Entscheidungsbäume Ensembles Absacken Erhöhen Zufälliger Wald k -NN Lineare Regression Naive Bayes Künstliche neurale Netzwerke Logistische Regression Perzeptron Relevanzvektormaschine (RVM) Support-Vektor-Maschine (SVM)
Clustering BIRKE HEILUNG Hierarchisch k -bedeutet Erwartung-Maximierung (EM) DBSCAN OPTIK Mittlere Verschiebung
Dimensionsreduktion Faktorenanalyse CCA ICA LDA NMF PCA PID t-SN
Strukturierte Vorhersage Grafische Modelle Bayes-Netz Bedingtes Zufallsfeld Versteckte Markov
Anomalieerkennung k -NN Lokaler Ausreißerfaktor
Künstliche neuronale Netz Autoencoder Kognitives Rechnen Tiefes Lernen DeepDream Mehrschichtiges Perzeptron RNN LSTM GRÜ ESN Eingeschränkte Boltzmann-Maschine GAN SO M Faltungsneurales Netzwerk U-Netz Transformator Spiking neuronales Netzwerk Speichertransistor Elektrochemischer RAM (ECRAM)
Verstärkungslernen Q-Lernen SARSA Zeitliche Differenz (TD)
Theorie Bias-Varianz-Kompromiss Computergestützte Lerntheorie Empirische Risikominimierung Occam-Lernen PAC-Lernen Statistisches Lernen VC-Theorie
Veranstaltungsorte für maschinelles Lernen NeurIPS ICML ML JMLR ArXiv:cs.LG
In Verbindung stehende Artikel Glossar der künstlichen Intelligenz Liste der Datensätze für die maschinelle Lernforschung Überblick über maschinelles Lernen
v T e

Bagging , auch genannt Absacken (von b ootstrap agg Regat ing ) ist ein Maschinengesamteindrucks - Lern meta-Algorithmus entwickelt , um die zur Verbesserung der Stabilität und die Genauigkeit der Maschinenlernalgorithmen in statistischer Klassifikation und Regression . Es reduziert auch die Varianz und hilft, Overfitting zu vermeiden . Obwohl es normalerweise auf Entscheidungsbaummethoden angewendet wird , kann es mit jedem Methodentyp verwendet werden. Bagging ist ein Sonderfall des Modellmittelungsansatzes .

Beschreibung der Technik

Bei einem gegebenen Standard- Trainingssatz der Größe n erzeugt das Einsacken m neue Trainingssätze , jeder mit der Größe n' , durch einheitliches Abtasten von D und mit Ersetzen . Durch Probenahme mit Austausch können einige Beobachtungen in jedem wiederholt werden . Wenn n ′ = n ist , dann wird für große n erwartet, dass die Menge den Bruchteil (1 – 1/ e ) (≈63,2%) der eindeutigen Beispiele von D hat , der Rest sind Duplikate. Diese Art von Sample wird als Bootstrap- Sample bezeichnet. Durch das Sampling mit Ersetzung wird sichergestellt, dass jeder Bootstrap unabhängig von seinen Peers ist, da er beim Sampling nicht von zuvor ausgewählten Samples abhängt. Dann werden m Modelle unter Verwendung der obigen m Bootstrap-Samples angepasst und durch Mittelung der Ausgabe (zur Regression) oder Abstimmung (zur Klassifizierung) kombiniert. ${\displaystyle D}$${\displaystyle D_{i}}$ ${\displaystyle D_{i}}$${\displaystyle D_{i}}$

Eine Illustration für das Konzept der Bootstrap-Aggregation

Bagging führt zu "Verbesserungen für instabile Verfahren", zu denen beispielsweise künstliche neuronale Netze , Klassifikations- und Regressionsbäume sowie die Teilmengenauswahl bei der linearen Regression gehören . Es wurde gezeigt, dass das Einsacken das Lernen von Vorbildern verbessert. Auf der anderen Seite kann es die Leistung stabiler Methoden wie K-nächster Nachbarn leicht verschlechtern.

Ablauf des Algorithmus

Originaldatensatz

Der Originaldatensatz enthält mehrere Einträge von Stichproben von s1 bis s5. Jedes Sample hat fünf Funktionen (Gen 1 bis Gen 5). Alle Proben werden für ein Klassifizierungsproblem mit Ja oder Nein gekennzeichnet.

Erstellung von Bootstrapped-Datensätzen

Angesichts der obigen Tabelle, um eine neue Stichprobe zu klassifizieren, muss zuerst ein Bootstrapping-Dataset mit den Daten aus dem ursprünglichen Dataset erstellt werden. Dieses Bootstrapping-Dataset hat normalerweise die Größe des ursprünglichen Datasets oder kleiner.

In diesem Beispiel beträgt die Größe fünf (s1 bis s5). Der Bootstrapping-Datensatz wird durch zufällige Auswahl von Stichproben aus dem Originaldatensatz erstellt. Wiederholungsauswahlen sind erlaubt. Alle Stichproben, die nicht für das Bootstrapping-Dataset ausgewählt wurden, werden in einem separaten Dataset platziert, das als Out-of-bag-Dataset bezeichnet wird.

Sehen Sie sich unten ein Beispiel für ein Bootstrapped-Dataset an. Es hat fünf Einträge (gleiche Größe wie der ursprüngliche Datensatz). Es gibt doppelte Einträge wie z. B. zwei s3, da die Einträge zufällig mit Ersetzung ausgewählt werden.

Dieser Schritt wird wiederholt, um m Bootstrapped-Datasets zu generieren.

Erstellen von Entscheidungsbäumen

Für jedes Bootstrapping-Dataset wird ein Entscheidungsbaum erstellt, wobei zufällig ausgewählte Spaltenwerte verwendet werden, um die Knoten aufzuteilen.

Vorhersage mit mehreren Entscheidungsbäumen

Wenn der Tabelle eine neue Stichprobe hinzugefügt wird, wird das Bootstrapping-Dataset verwendet, um den Klassifikatorwert des neuen Eintrags zu bestimmen.

Die neue Stichprobe wird in der zufälligen Gesamtstruktur getestet, die von jedem Bootstrapping-Dataset erstellt wird, und jeder Baum erzeugt einen Klassifikatorwert für die neue Stichprobe. Für die Klassifizierung wird ein Verfahren namens Voting verwendet, um das Endergebnis zu bestimmen, wobei das am häufigsten von der Zufallsstruktur erzeugte Ergebnis das gegebene Ergebnis für die Stichprobe ist. Für die Regression wird der Stichprobe der von den Bäumen erzeugte durchschnittliche Klassifikatorwert zugewiesen.

Nachdem die Stichprobe im Random Forest getestet wurde, wird der Stichprobe ein Klassifikatorwert zugewiesen und der Tabelle hinzugefügt.

Algorithmus (Klassifizierung)

Flussdiagramm des Bagging-Algorithmus bei Verwendung zur Klassifizierung

Verwenden Sie für die Klassifizierung einen Trainingssatz , Inducer und die Anzahl der Bootstrap-Samples als Eingabe. Klassifikator als Ausgabe generieren${\displaystyle D}$${\displaystyle I}$${\displaystyle m}$${\displaystyle C^{*}}$

1. Erstellen Sie neue Trainingssätze , ab mit Ersatz${\displaystyle m}$${\displaystyle D_{i}}$${\displaystyle D}$
2. Classifier aus jedem Satz gebaut unter Verwendung von auf die Klassifizierung des Satzes zu bestimmen ,${\displaystyle C_{i}}$${\displaystyle D_{i}}$${\displaystyle I}$${\displaystyle D_{i}}$
3. Schließlich wird der Klassifikator generiert, indem der zuvor erstellte Satz von Klassifikatoren für den ursprünglichen Datensatz verwendet wird. Die von den Unterklassifikatoren am häufigsten vorhergesagte Klassifizierung ist die endgültige Klassifizierung${\displaystyle C^{*}}$${\displaystyle C_{i}}$${\displaystyle D}$${\displaystyle C_{i}}$

for i = 1 to m {
    D' = bootstrap sample from D    (sample with replacement)
    Ci = I(D')
}
C*(x) = argmax    Σ 1               (most often predicted label y)
         y∈Y   i:Ci(x)=y

Beispiel: Ozondaten

Um die Grundprinzipien des Absackens zu veranschaulichen, folgt unten eine Analyse der Beziehung zwischen Ozon und Temperatur (Daten von Rousseeuw und Leroy (1986), Analyse in R ).

Die Beziehung zwischen Temperatur und Ozon scheint in diesem Datensatz basierend auf dem Streudiagramm nicht linear zu sein. Um diesen Zusammenhang mathematisch zu beschreiben, werden LOESS- Glätter (mit Bandbreite 0,5) verwendet. Anstatt einen einzelnen Smoother für den gesamten Datensatz zu erstellen, wurden 100 Bootstrap- Stichproben gezogen. Jede Stichprobe besteht aus einer zufälligen Teilmenge der Originaldaten und behält einen Anschein der Verteilung und Variabilität der Hauptmenge bei. Für jedes Bootstrap-Sample wurde ein LOESS-Glättungser angepasst. Vorhersagen von diesen 100 Glättern wurden dann über den gesamten Datenbereich gemacht. Die schwarzen Linien repräsentieren diese anfänglichen Vorhersagen. Die Linien stimmen in ihren Vorhersagen nicht überein und neigen dazu, ihre Datenpunkte zu überstimmen, was durch den wackeligen Fluss der Linien deutlich wird.

Indem wir den Durchschnitt von 100 Glättern bilden, die jeweils einer Teilmenge des ursprünglichen Datensatzes entsprechen, erhalten wir einen eingesackten Prädiktor (rote Linie). Der Fluss der roten Linie ist stabil und passt sich keinem Datenpunkt zu sehr an.

Vorteile und Nachteile

Vorteile:

• Viele aggregierte schwache Lernende übertreffen in der Regel einen einzelnen Lernenden über das gesamte Set und haben weniger Overfit
• Entfernt die Varianz bei schwachen Lernenden mit hoher Varianz und niedrigem Bias
• Kann parallel ausgeführt werden , da jeder separate Bootstrap vor der Kombination einzeln verarbeitet werden kann

Nachteile:

• Für schwache Lernende mit hoher Voreingenommenheit trägt das Einsacken auch eine hohe Voreingenommenheit in die Gesamtheit ein
• Verlust der Interpretierbarkeit eines Modells.
• Kann je nach Datensatz rechenintensiv sein

Geschichte

Das Konzept des Bootstrap Aggregating leitet sich vom Konzept des Bootstrapping ab, das von Bradley Efron entwickelt wurde. Bagging wurde von vorgeschlagen Leo Breiman , der auch die abgekürzte Bezeichnung „Absacken“ (geprägt b ootstrap agg Regat ing ). Breiman entwickelte 1994 das Konzept des Bagging, um die Klassifikation durch die Kombination von Klassifikationen von zufällig generierten Trainingssätzen zu verbessern. Er argumentierte: "Wenn die Störung des Lernsatzes zu signifikanten Änderungen des konstruierten Prädiktors führen kann, kann das Einsacken die Genauigkeit verbessern".

Siehe auch

• Boosting (Meta-Algorithmus)
• Bootstrapping (Statistik)
• Kreuzvalidierung (Statistik)
• Fehler außerhalb des Beutels
• Zufälliger Wald
• Zufällige Subspace-Methode (Attribut-Bagging)
• Effiziente Grenze neu abgetastet
• Prädiktive Analyse: Klassifikations- und Regressionsbäume

Verweise

Weiterlesen

• Breiman, Leo (1996). "Einsacken Prädiktoren". Maschinelles Lernen . 24 (2): 123–140. CiteSeerX  10.1.1.32.9399 . doi : 10.1007/BF00058655 . S2CID  47328136 .
• Alfaro, E., Gámez, M. und García, N. (2012). "adabag: Ein R-Paket zur Klassifizierung mit AdaBoost.M1, AdaBoost-SAMME und Bagging" . Cite Journal erfordert |journal=( Hilfe )
• Kotsiantis, Sotiris (2014). "Bagging und Boosting Varianten für den Umgang mit Klassifizierungsproblemen: eine Umfrage". Wissen Eng. Überprüfen Sie . 29 (1): 78–100. doi : 10.1017/S0269888913000313 .
• Böhmke, Bradley; Greenwell, Brandon (2019). "Einsacken". Praktisches maschinelles Lernen mit R . Chapman & Halle. S. 191–202. ISBN 978-1-138-49568-5.