Rotation Forest

Rotation Forest
EIN NEUES ENSEMBLE-
KLASSIFIKATIONSVERFAHREN
Tim Schneider
EINLEITUNG
 Warum ein Ensemble-Klassifikator?
 um Vorhersagen von mehreren Klassifikatoren zu kombinieren anstelle eines einzelnen Klassifikators
 Motivation
 Verringerung der Varianz:
 um weniger abhängig von Besonderheiten einer einzelnen Trainingsmenge zu sein
 Reduzierung des Bias:
 lerne eine aussagekräftige Klasse anstatt eines einzigen Klassifikators
 Ansatz
 Ensembles werden aus verschiedenen Klassifikatoren aus einer Trainingsmenge gebildet
Bagging (Random Forest)
 Leistungsbeurteilung nach Vielfalt und Genauigkeit
 Beste Methode ⇒ AdaBoost ⇒ große Vielfalt, aber Genauigkeitsverlust
Boosting (AdaBoost)
Neuer Ansatz ⇒ Rotation Forest ⇒ soll beides erreichen
1
ROTATION FOREST
 stützt sich beim Klassifizieren auf die Idee des
Entscheidungsbaums
 Basis-Klassifikator ist ein Entscheidungsbaum
 reagieren empfindlich auf die Rotation der Parameterachsen.
⇒ Wald (Forest)
 nutzt zur Reduzierung der Parameter die PCA
 Daten werden mittels PCA transformiert
 Durch eine Drehung der Parameterachsen werden jeweils
neue Merkmale für den Basis-Klassifikator erstellt
 fördert gleichzeitig eine individuelle Genauigkeit
und eine Vielfalt innerhalb des Ensembles
2
IDEE
Erstellung der Trainingsdaten wie folgt:
1. Merkmale zufällig in K-Teilmengen aufteilen
2. PCA auf jede Teilmenge anwenden
3. Alle Hauptkomponenten sind erforderlich, damit die Variabilität an Informationen
in den Daten erhalten bleibt.
3
METHODE (1)
X: Alle Objekte in den Trainingsdaten
x = [x1, x2, …, xn]T Objekt mit n-Merkmalen
N×n Matrix
Y = [y1, y2, …, yN]T : Klassenbeschriftung der Trainingsdaten (N×1 Matrix)
4
METHODE (2)
Gegeben
 L: die Zahl der Klassifikatoren in dem Ensemble (D1, D2, ..., DL)
 F: Merkmalsraum
 X, Y
5
METHODE (3) - TRAININGSPHASE
Um für den Klassifikator Di einen Trainingsdatensatz zu konstruieren:
1. splitte F zufällig in K-Teilmengen: Fi,j
F: Merkmalsraum
Fi,1
Fi,K
Fi,2
K-Teilmengen (Fi,j für j=1…K)
jede hat M = n/K-Merkmale
…
Fi,3
(n stammt aus N×n Matrix)
6
METHODE (4) - TRAININGSPHASE
2.
X1,1: Teilmenge X für die Merkmale in F1,1
 Für jede Teilmenge Fi,j
 sei Xi,j der Datensatz X für die
Merkmale in Fi,j
F1,1
F1,2
 wähle nach dem Zufallsprinzip eine
…
nichtleere Teilmenge an Klassen aus Xi,j F1,K
F1,3
 wähle aus Xi,j eine BootstrapStichprobe von 75% der Anzahl der
Objekte
⇒ es entsteht X’i,j
 führe auf X’i,j eine PCA durch und
speichere die Koeffizienten in einer
Matrix
Wähle zufällig eine
Teilmenge an Klassen
aus X1,1
Wähle eine BootstrapStichprobe von 75%
aus der Anzahl der
Objekte aus X1,1 um
X’1,1 zu erhalten.
Führe mit X’1,1 und M-Merkmalen eine PCA durch,
um die Koeffizienten zu erhalten.
7
METHODE (5) - TRAININGSPHASE
3.
 Ordne die erhaltenen Koeffizienten in einer Rotationsmatrix Ri
 Um den Trainingsdatensatz für den Klassifikator Di zu berechnen,
 ordne die Spalten von Ri so neu an, dass sie den ursprünglichen Merkmalen aus F entsprechen und
bezeichne sie mit Ria
 bezeichne den Trainingsdatensatz für den Klassifikator Di mit ⇒ XRia
 Erstelle den Klassifikator Di unter Verwendung von (XRia, Y) als Trainingsdatensatz.
8
METHODE (6) - KLASSIFIKATIONSPHASE
 Um ein gegebenes Objekt x zu klassifizieren, sei di,j(xRia) die Wahrscheinlichkeit,
dass der Klassifikator Di annimmt, x stammt aus der Klasse
 Berechne das durchschnittliche Vertrauen
für jede Klasse über alle Klassifikatoren mit:
Satz von Klassenbeschreibungen
 Klassifiziere x in die Klasse mit dem größten Vertrauen
9
METHODE (6)
Warum wird eine Bootstrap-Stichprobe sowie eine Zufallsauswahl der Klassen in
Schritt 2 durchgeführt?
 man möchte voneinander verschiedene Klassifikatoren in einem Ensemble haben
Beispiel:
Die Möglichkeit, komplett verschiedene Klassifikatoren für
ein Ensemble von L = 50, für K = 3 und n = 9 zu erhalten, ist kleiner als 0.01
10
LEISTUNGSBEURTEILUNG
Vielfalt
 entsteht durch Merkmalsextraktion für jeden Basis-Klassifikator.
 Jeder Entscheidungsbaum verwendet einen unterschiedlichen Satz an Merkmalen.
Genauigkeit
 Keine Hauptkomponenten werden verworfen.
 Trotz der eingefügten Randomisierung des Datensatzes
wird der ganze Datensatz transformiert und anschließend für die Ausbildung des
Basis-Klassifikators genutzt (mit unterschiedlich extrahierten Merkmalen).
11
ERGEBNISSE EINES EXPERIMENTS
 Vergleich von Rotation Forest, Bagging, AdaBoost und Random Forest
 Verwendung von WEKA
 Datensatz: UCI Machine Learning Repository (33 Datensätze)
 Experimenteinstellungen:




Bagging, AdaBoost und Random Forest mit Standardwerten in WEKA
Random Forest M = 3
Alle Ensemble-Methoden haben das gleiche L = 10
Basis-Klassifikator: Decision-Tree J48 in WEKA
12
ERGEBNISSE EINES EXPERIMENTS
13
ERGEBNISSE EINES EXPERIMENTS
%
Y-Achse:
Prozentsatz der
Datensätze mit
den geringsten
Fehlern unter den
vier Verfahren
69,70%
Diagramm für
die 4 EnsembleMethoden mit
ungestutzten J48
Bäumen
3,03%
24,24 %
3,03%
3.03%%
X-Achse: Ensemblegröße L
14
FAZIT
 Rotation Forest Ensembles erstellen individuelle Klassifikatoren die genauer als jene
in AdaBoost und Random Forest und vielfältiger und manchmal auch genauer als
jene in Bagging sind.
15
QUELLEN
 http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=1677518
 http://pages.bangor.ac.uk/~mas00a/papers/lkjrmcs07.pdf
 http://archer.ee.nctu.edu.tw/.../Rotation%20Forest.ppt
 http://www.ehu.eus/ccwintco/uploads/3/34/RotationForest.pdf
16

Download Report