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)


Keine Kommentare:

Kommentar veröffentlichen