Random Forests

Baum (Knoten / Kanten, die in hierarchischer Form organisiert sind)

innere Knoten: split Nodes, haben >= Kindknoten (üblicherweise 2)

• split Functions: Entscheidungsregel, schicke Daten entweder in rechten oder linken Teilbaum

• Weitergabe, bis Blattknoten erreicht

End-Knoten: Blattknoten

• enthölt Entscheidungskriterium -> basierend auf Klassenwahrscheinlichkeiten (Verteilung über Klassen)

Eingabe: Merkmalsvektoren (Dimension kann groß oder unendlich sein)

optimiert Parameter der Split Functions

ermittelt Entscheidungskriterium in Blättern

Ziel: Split Function soll Information Gain maximieren

Stopping Criteria: min split size, max depth

Entscheidungskriterium:

• zähle, wie viele Datenpunkte jeder Klasse im Blatt ankommen

• schätze Wahrscheinlichkeitsverteilung der Trainingsdaten über die Klassen -> a-posteriori-Wahrscheinlichkeiten

wie viel Informationsgehalt wird bei einem bestimmten Split an einem Node gewonnen?

Entropie der Daten vor Split minus gewichtete Summe der Entropien der Daten im rechten / linken Teilbaum (nach dem Split)

• Entropie der Verteilung der Datenpunkte über die Klassen

I = H(S) - Σ |Si|/|S| H(Si)

geringere Entropie in Teilbäumen -> höherer Information Gain (besserer Split)

Ensemble von Entscheidungsbäumen

Bäume sind unterschiedlich, da

• mit zufälliger Teilmenge der Trainingsdaten trainiert

• zufällige Teilmenge der Features verwendet

Verhältnis M’/M (Anzahl ausgewählter Features / Gesamtzahl der Features): Maß für Zufälligkeit

split functions an Knoten: “weak learners”

finale Entscheidung:

• kombiniere Klassenverteilungen in Blättern der Bäume, wo geg. Sample ankommt

• basiert auf gemittelter Verteilung p(c|v) = 1/T Σpt(c|v)

maximale Tiefe D erreicht

(vordefinierter) minimaler Information Gain unterschritten

Knoten enthält zu wenige Training Samples

zu große Bäume overfitten leicht -> vermeiden für bessere Generalisierung

jeder Knoten i hat binäre Split Function h(v, θi) -> {0,1}

• sende Sample v entweder in linken (0) oder rechten (1) Teilbaum

Parameter θi = (φi, ψi, τi) charakterisieren weak learner

• φi: wählt (zufällig) Teilmenge der Merkmale aus

• τi: Schwellenwerte

• ψi: “geometric primitive” zur Trennung der Daten

Optimiere θi so, dass θi = max Ii über alle θi

• Ii: Information gain, der mit θi entsteht