2011-09-16

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)

2011-09-08

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)