Interaktionen in Entscheidungsbäumen II

Im letzten Eintrag hatte ich schon mit relativ kleinen Beispielen gezeigt, dass die Berücksichtigung von Interaktionen in Entscheidungsbäume zweierlei Nutzen haben kann:

1. Der Baum wird kleiner und somit einfacher zu interpretieren.

2. Der Baum wird genauer und eignet sich somit auch besser für Prognosen.

(Natürlich gilt das nur, wenn die Interaktion relevant für die Erklärung der Zielgröße ist.)

An dieser Stelle möchte ich das noch an einem kurzem aber etwas komplexeren Beispiel verdeutlichen.

In dieser 3-dimensionalen Situation sind die zugrunde liegenden Interaktionen, die die Zielgröße (Cyan/Blau) beeinflussen, zu komplex um sie in einer geometrischen Form zu beschreiben. Ein einfacher Entscheidungsbaum versucht die Farbe der Punkte auf folgende Weise zu erklären:

Ohne ein Pruning durchgeführt zu haben ergibt sich ein Baum mit 12 Blättern und einer Missklassifikationsrate von 10%.

Im Vergleich dazu der Baum, der die Interaktion berücksichtigt:

Dieser Baum benutzt nur 3 Blätter um die (nicht verrauschten) Daten perfekt zu erklären.

Natürlich ist es nicht sonderlich verwunderlich, dass der Baum der die volle Information über das zugrundeliegende Problem hat besser ist als einer dem entscheidende Information fehlt. Interessant ist aber, dass die Berücksichtigung von Interaktionen in der Praxis bis dato keine Rolle spielt. Tatsächlich unterstützt weder R noch JMP die Verwendung von Interaktionen in Entscheidungsbäumen von sich aus. In beiden Fällen müssen die Wechselwirkungen zunächst händisch erzeugt werden bevor sie als Einflussgrößen angegeben werden können.

Anhang:

# Entscheidungsbäume und Interaktionen II

# Sebastian Hoffmeister - Statcon

library(tree)

x1 = rnorm(100, 0, 1)

x2 = rnorm(100, 0, 1)

x3 = rnorm(100, 0, 1)

interaction = x1*0.5*x2*3*x3 # Die wahre Interaktion

y =  rep(0, 100)

for(i in 1:100) { # Erzeugen der Zielgröße

    if(abs(interaction[i])<0.5) y[i] = 1

}

simple.tree = tree(as.factor(y) ~ x1 + x2 + x3) # Ein einfacher Baum

summary(simple.tree)

plot(simple.tree)

text(simple.tree)

int = x1*x2*x3 # Man kennt natürlich nicht die einzelnen Koeffizienten in der Interaktion

interaction.tree = tree(as.factor(y) ~ x1 +x2 + x3 + int)

summary(interaction.tree)

plot(interaction.tree)

text(interaction.tree)

Notiz am Rand: Interaktionen in Entscheidungsbäumen

Kürzlich hatte ich das Vergnügen einen Kurs zum Thema Data Mining mit SAS zu Besuchen. Da mir der Inhalt im wesentlichen schon bekannt war, blieb etwas Zeit zur Reflektion. Dabei fiel mir ein mehr oder weniger erstaunlicher Sachverhalt auf.

Nicht nur in diesem Kurs, auch in der gängigen Literatur, wird immer wieder bemerkt, dass ein entscheidender Schritt für erfolgreiches Datamining die Datenaufbereitung ist. Das beinhaltet nicht nur das Prüfen der Plausibilität der Daten, sondern auch das Ersetzen von fehlenden Werten, möglicherweise Standardisieren der Daten, etc. Allgemein wird das kreative Bilden von neuen Variablen als äußerst wichtiger Teil der Datenaufbereitung betrachtet.

Ich möchte mich mit dem letzten Punkt näher beschäftigen. Neue Variablen können zum einen natürlich einfach transformierte Variablen sein. Interessant ist, dass mögliche Transformationen im Bereich des Dataminings ein völlig anderes Ziel haben, als Transformationen in der klassischen Statistik. Während der Statistiker gewohnt ist Variablen z.B. zu logarithmieren, in der Hoffnung, dass die Annahmen einer Regressionsanalyse mit transformierte Variable besser erfüllt sind, will der Dataminer vor allem neue Informationen generieren.

Zu dieser Art von Transformationen gehören auch Interaktionen! Die einschlägige Literatur scheint diesen Sachverhalt nicht als extra erwähnenswert zu betrachten. Ich will an 2 kleinen Beispielen sichtbar machen, dass sich die Berücksichtigung von Interaktionen von Variablen bei der Anwendung von Decision-Trees sehr wohl lohnen kann.

Betrachten wir ein kleines Beispiel:

Offensichtlich sind die beiden Gruppen in den Daten (schwarz und rot) entlang der Diagonalen getrennt. Was tut der Entscheidungsbaum nun? Er sucht nach dem besten Schnitt durch die Daten um die beiden Gruppen zu trennen. Dabei sind jedoch nur Schnitte parallel zur X- bzw. Y-Achse möglich.

R schlägt nun folgende Schnitte vor:

Man sieht, dass der Baum versucht die Diagonale nachzubilden. Allerdings braucht er zu viele Splits, wie wir im Vergleich mit dem nächsten Baum sehen werden. Zudem ist es nicht ganz einfach anhand des Baums zu erkennen, dass eine Interaktion in den Daten vorliegt, bzw. wie sich Diese gestaltet.

Das Ganze vereinfacht sich wesentlich, wenn man die Variable X3 = X1 + X2 als Einflussgröße zulässt. Dann finden wir einen Baum, der mit einem Split die Zielgröße perfekt erklären kann.

Das haben wir erreicht indem der Baum flexibler gestaltet wurde. Er kann jetzt nicht nur senkrechte und waagrechte Splits vornehmen, sondern auch diagonale Splits.

Das gleiche lässt sich natürlich für gewöhnliche Interaktionen der Form X1*X2 konstruieren.

Daten: Y = 1 für X1*X2 < 0.2

Entscheidungsgrenzen für einen Baum mit  EG X1, X2 und X1*X2

Entscheidungsgrenzen für einen Baum mit EG X1 und X2

 Während der konventionelle Baum 4 Splits braucht und nur einen ungenügenden Abstraktionsgrad erreicht kann der Baum bei dem die Interaktion als Einflussgröße (EG) zugelassen wurde, die Daten mit einem Split perfekt erklären.

Ich konnte also zeigen, dass es sich lohnen kann Interaktionsterme bei der Konstruktion von Bäumen zu Berücksichtigen. Möglicher Nutzen sind:

• kleinere Bäume, die
• genauere Prognose und Zusammenhangsanalysen zulassen.

Gleichzeitig ist klar, dass in vielen Bereichen des Dataminig das Arbeiten mit Interaktionen allein wegen der schieren Menge an Variablen oft nicht oder nur bedingt möglich ist. Dann können Interaktionen nur noch aufgrund eines konkreten inhaltlichen Verdachts berücksichtigt werden.

Hier noch der benutzte R-Code:

# Decision Trees und Interaktionen

# 8. Sept. 2011

# Sebastian Hoffmeister - Statcon

library(tree)

library(lattice)

# Daten erzeugen

simple = as.data.frame(matrix(NA, ncol=4, nrow=100))

simple[,1] = rnorm(100, 0,1)

simple[,2] = rnorm(100, 0, 1)

simple[,3] = simple[,1] + simple[,2]

for(i in 1:100) {

if(simple[i,3] > 0.2) {

simple[i,4] = 1

} else {

simple[i,4] = 0

}

}

colnames(simple) = c("X1", "X2", "Combined", "Y")

xyplot(X1 ~ X2, data=simple,col=simple[,"Y"]+1, type=c("p","g"), pch=16)

# Baum erstellen

standardTree = tree(as.factor(Y) ~ X1 + X2, data=simple)

plot(standardTree)

text(standardTree)

# Fitted Values und Konfusionsmatrix

p = predict(standardTree, as.data.frame(simple), type="class")

ftable(Predicted=p, True=simple[,"Y"])

# Vorhersage grafisch

thispch = rep(16, 20)

thispch[which(p != simple[,"Y"])] = 8

xyplot(X1 ~ X2, data=simple,col=p, type=c("p","g"), pch=thispch)

# Baum mit kombinierter Variable

X3 = simple[,1] + simple[,2]

interactionTree = tree(as.factor(simple[,4]) ~ X3 + simple[, "X1"] + simple[,"X2"])

pred = predict(interactionTree, as.data.frame(simple), type="class")

ftable(pred, simple[,4])

plot(interactionTree)

text(interactionTree)

# 2. Beispiel - Richtige Interaktion:

simple = as.matrix(matrix(NA, ncol=4, nrow=100))

simple[,1] = rnorm(100, 0,1)

simple[,2] = rnorm(100, 0,1)

simple[,3] = simple[,1] * simple[,2]

for(i in 1:100) {

if(simple[i,3] > 0.2) {

simple[i,4] = 1

} else {

simple[i,4] = 0

}

}

colnames(simple) = c("X1", "X2", "X1*X2", "Y")

xyplot(X1 ~ X2, data=as.data.frame(simple),col=simple[,"Y"]+1, type=c("p","g"), pch=16)

# einfacher Baum

standardTree = tree(as.factor(Y) ~ X1 + X2, data=as.data.frame(simple))

pred.st = predict(standardTree, as.data.frame(simple), type="class")

ftable(pred.st, simple[,"Y"])

plot(standardTree)

text(standardTree)

# Baum mit Interaktion

interactionTree = tree(as.factor(simple[,4]) ~ simple[,1] + simple[,2] + simple[,3], data=as.data.frame(simple))

pred.ia = predict(interactionTree, as.data.frame(simple), type="class")

ftable(pred.ia, simple[,"Y"])

plot(interactionTree)

text(interactionTree)

Wiegen - Nur Besser!

Immer wieder entsteht in Kursen zum Thema Versuchsplanung die Diskussion ob Versuchsplanung überhaupt nötig (oder möglich oder sinnvoll) ist. Vor allem die Befürchtung, dass man beim systematischen Vorgehen wesentlich mehr Aufwand betreiben muss, als bei naivem Vorgehen (z.B. OFAT: One-Factor-At-A-Time), ist nicht leicht auszuräumen.

Statt mit Formelsalat versuche ich meist die Gemüter mit einfachen Beispielen zu beruhigen. Ein relativ anschauliches Beispiel ist Hotellings Wiegeproblem (Harold Hotelling – Some Improvements in Weighing and Other Experimental Techniques; Annuals of Mathematical Statistics 15 (1944) p.297-306).

Ziel

Mit diesem Beispiel soll die Befürchtung, dass systematisches Arbeiten gleichbedeutend mit Mehraufwand ist, relativiert werden. Das geschieht indem man zeigt, wie viel mehr an Info

rmation in einem einfachen Beispiel gewonnen werden kann ohne dass mehr Experimente durchgeführt werden müssen. (Die Varianz wird durch das systematische Vorgehen im Vergleich zum naiven Vorgehen auf ein Viertel gesenkt!)

Fragestellung

Es sollen 7 Gegenstände mit einer Balkenwaage gewogen werden. Ziel ist es mit möglichst wenigen Wägungen eine möglichst genaue Gewichtsangabe für die einzelnen Gegenstände machen zu können. Dabei ist auch ein Versuch zu berücksichtigen mit dem die Waage auf 0 eingestellt wird.

Es wird angenommen, dass jedes Wiegen ein Messvorgang mit einer Standardabweichung von σ ist.

Naives Vorgehen

In dieser Situation ist das einfachste Vorgehen natürlich jedes Objekt einzeln zu Wiegen. Einschließlich der „Null“ Messungen werden also 8 Versuche oder Messungen durchgeführt.

Damit ergibt sich für jedes Wiegen eine Standardabweichung von 2σ. Die 2σ kommen zustande, da die Bestimmung des Gewichts eines Gegensandes aus dem Vergleich von 2 Messungen hervorgeht.

1. Die Waage wird auf die 0 eingestellt. Dieser Vorgang ist, da er eine Messung darstellt, mit dem Fehler σ behaftet.

2. Es wird das Gewicht des Gegenstandes auf der Waage gemessen. Dieser Messvorgang hat auch wieder eine Standardabweichung von σ.

Um das Gewicht des Gegenstandes zu bestimmen werden also 2 Messwerte verglichen. Die Messung ohne den Gegenstand und die Messung mit dem Gegenstand.

Fazit: Die Messung jedes Gegenstandes hat eine Varianz von 4σ².

Hotellings Vorschlag

Statt jeden Gegenstand einzeln zu wiegen werden immer mehrere Gegenstände, die hier mit den Buchstaben A, B, C,...G bezeichnet werden, gleichzeitig auf die Waage gelegt. Wir beginnen mit dem Wiegen von allen Gegenständen gemeinsam.

Anschließend wird jeder Gegenstand noch 3 mal gewogen.

• Dabei werden immer 3 Gegenstände gemeinsam gewogen.

• Es soll jeder Gegenstand noch genau einmal mit jedem anderen Gegenstand gewogen werden.

Damit ergibt sich folgendes Schema:

Tabelle 1: Die verschiedenen Messungen nach Hotelling

Ausrechnen der Einzelgewichte

Diese Gleichungen lassen sich relativ leicht lösen, um die einzelnen Gewichte zu erhalten:

Es müssen jeweils alle Gleichungen die den Gegenstand enthalten aufaddiert werden und anschließend alle Gleichungen, die den Gegenstand nicht enthalten subtrahiert werden. Das Resultat ist das vierfache des Gewichts des jeweiligen Gegenstandes. Für Gegenstand A sieht das also so aus:

4*A = Y1+Y2+Y3+Y4-Y5-Y6-Y7-Y8

(Rechnen Sie es einfach mal nach.) D.h. Wir erhalten das Gewicht von A als:

A = (Y1+Y2+Y3+Y4-Y5-Y6-Y7-Y8)/4

Es werden also 8 Messwerte (Zufallsvariablen) aufaddiert, die jeweils mit dem Wert ¼ multipliziert werden. Was bedeutet das für die Varianz unserer Messung?

Erwartete Varianz der Resultate nach Hotellings Vorgehen

Wir benutzen zwei einfache Regeln der Varianzrechnung:

1. Die Varianz zweier unabhängiger Zufallsvariablen ist gleich der Summe der Varianzen der einzelnen Zufallsvariablen:

   Var(A+B) = Var(A) + Var(B).

2. Multipliziert man eine Zufallsvariable mit einer Zahl c, so wirkt diese Zahl quadratisch auf die Varianz der Zufallsvariable:

   Var(c*A) = c*c*Var(A).

Damit ergibt sich für unseren Fall:

Var(A) = 1/16 Var(Y1) + 1/16Var(Y2) + … + 1/16Var(Y8)

Da die Varianz jeder Messung gleich σ² ist ergibt sich:

Var(A) = 8/16 σ² = ½ σ²

Fazit: Durch geschickte Methodik beim Messen können wir die Genauigkeit unserer Aussagen verbessern. Die Varianz der Messungen in unserem Beispiel verringert sich von 2σ² auf ½ σ², während sich die Standardabweichung um den Faktor 1/Wurzel(2) verringert. Dabei wurden nicht mehr Messungen durchgeführt, als wenn nur die einzelnen Gegenstände gemessen worden wären.

Probieren wir das mal aus an einem ...

Beispiel

Es liegen die 7 Gegenstände A, B, C, D, E, F und G vor. Da ich keine Waage zur Hand habe simuliere ich meine Messungen. Ich muss also auch die wahren Gewichte vorgeben.

Tabelle 2: Überblick über die simulierten Gewichte

Ich simuliere also in JMP jeweils 15 naive Messungen pro Gegenstand. Es wird also auf den wahren Wert des Gegenstandes ein zufälliger Fehlerterm aufaddiert. Hier nehme ich Zufallszahlen aus einer Standardnormalverteilung.

Für Hotellings Methode gehe ich ähnlich vor. Ich simuliere zunächst die Messungen Y1, Y2, … , Y8. Ich kenne für jede Messung den wahren Wert. Auch hier wird ein Fehlerterm aus einer Standardnormalverteilung hinzugezählt. Im Anschluss können die Gewichte, wie oben beschrieben ausgerechnet werden.

Abbildung 1: Simulierte Messungen: a,b,c,... naiv, A2,B2,C2,... nach Hotelling

Berechnet man nun die Standardabweichung für die Messungen jedes Gegenstandes und für jede Methode getrennt bestätigen sich die theoretischen Überlegungen.

Tabelle 3: Vergleich der Standardabweichungen für die Messung der Gewichte pro Gegenstand

In der Grafik sieht man gut, dass die Standardabweichung der Messungen nach Hotellings Methode (fast) durchgehend bei etwa 0.7 liegen. Die 0.707 ist die Standardabweichung der naiven Methode (=1) geteilt durch Wurzel(2).

Abbildung 2: Graphischer Vergleich der Standardabweichungen

Histogramme: Verteilung der Resultate mit beiden Wiegemethoden

Was hat das jetzt mit Versuchsplanung zu tun? Werfen wir mal einen Blick auf den einen Versuchsplan, wie ihn JMP für diese Situation erstellt.

Wir definieren 7 zwei-stufige Faktoren A,B,C,...G (z.B. A der Gegenstand wird gewogen werden oder nicht gewogen). Wir interessieren uns nur für Haupteffekte und erstellen deshalb einen teilfaktoriellen Plan mit Resolution III. Dieser Plan wird manchmal auch als „Taguchi L8“ bezeichnet.

Abbildung 3: Taguchi-Versuchsplan in JMP

In der Muster-Spalte finden wir genau die von Hotelling beschriebene Systematik wieder.

Es gibt noch eine Möglichkeit noch effizienter zu messen. Die bessere Lösung wird vielleicht beim nächsten Mal vorgestellt.

Literatur:

• Harold Hotelling – Some Improvements in Weighing and Other Experimental Techniques; Annuals of Mathematical Statistics 15 (1944) p.297-306