R. Ferber: Data Mining & Information Retrieval 1.5.4.3

4.4.1: Multivariate Entscheidungsbäume

Neben dem Ableiten vereinfachter Attribute können neue Attribute auch aus mehreren Attributen zusammengesetzt werden. Auch dabei muss natürlich darauf geachtet werden, dass das Skalenniveau der Attribute diese Operationen erlaubt. Unter einem zusammengesetzten Attribut versteht man also eine Funktion, in die mehrere Attribute eingehen. Als Beispiel kann man zu zwei reellwertigen Attributen A₁,A₂:D->R das zusammengesetzte Attribut A_z:D->{0,1} mit

bilden. Mit diesem Attribut könnten die Kategorien in Abbildung _60_ direkt getrennt werden. Entscheidungsbäume, die zusammengesetzte Attribute verwenden, werden multivariate Entscheidungsbäume genannt.

Die Menge möglicher Funktionen, nach denen zusammengesetzte Attribute konstruiert werden können, ist im Allgemeinen sehr groß. Sie kann deshalb nicht vollständig nach geeigneten Funktionen durchsucht werden. Man muss sich also auf eine handhabbare Klasse von Funktionen beschränken. Eine solche Klasse ist z. B. die der Linearkombinationen aus Attributen, die mit einer Schwellwertfunktion versehen sind. Sie setzt natürlich Attribute mit einem entsprechenden Skalenniveau, also z. B. Intervallskalen, voraus. (Manchmal kann es sinnvoll sein, Attribute mit Nominalskalen in einzelne Attribute zu zerlegen, die angeben, ob ein Wert angenommen wird oder nicht. Diese binären Attribute können dann mit {0,1} kodiert und in eine Linearkombination einbezogen werden (siehe Brodley und Utgoff, 1995 [->]), auch wenn sie streng genommen kein Intervallskalenniveau haben.)

Brodley und Utgoff (1995 [->]) vergleichen verschiedene Verfahren, mit denen multivariate Entscheidungsbäume mit Linearkombinationen von reellwertigen Attributen berechnet werden können. Dabei unterscheiden sie zunächst zwischen der Entscheidung zwischen nur zwei Zielmengen und der Einteilung in n>2 Zielmengen. (Hier wird von Zielmengen gesprochen, weil es sich um die Entscheidungen in einem Knoten handelt. Deshalb brauchen die Zielmengen keine Kategorien zu sein.) Bei zwei Zielmengen - also bei einem binären Entscheidungsbaum - kann man mit linearen Schwellwertfunktionen ( linear threshold unit LTU) arbeiten. Dazu benötigt man einen Vektor x=(x₀,...,x_n) aus Koeffizienten für die beteiligten Attribute und einer Schwelle x₀ . Übersteigt die mit den Koeffizienten gewichtete Summe der Attributwerte w₁,...,w_n die gegebene Schwelle, wird die eine Zielmenge angenommen, liegt sie unter der Schwelle, die andere. Die lineare Schwellwertfunktion ist also durch einen Koeffizientenvektor charakterisiert, der einen Koeffizienten mehr enthält (die Schwelle) als Attribute bearbeitet werden. Die Bedingung läßt sich mit w₀=-1 , d:=(w₀,w₁,...,w_n) als Skalarprodukt d*x>0 schreiben.

Bei mehr als zwei Zielmengen wird für jede Zielmenge ein solcher Koeffizientenvektor benötigt. Ein Tupel wird derjenigen Zielmenge zugewiesen, für die die mit dem zugehörigen Koeffizientenvektor gewichtete Summe der Attributwerte am größten ist (dieses Verfahren wird auch als lineare Maschine ( linear machine) LM bezeichnet).

Formal gesehen ist die lineare Schwellwertfunktion ein Spezialfall der linearen Maschine: Hat man eine lineare Maschine mit zwei Zielmengen, kann man die Entscheidung so charakterisieren:

dabei sind x und y die Koeffizientenvektoren und d bezeichnet ein Wertetupel. d*x>d*y ist äquivalent zur Formulierung d*x-d*y>0 und weiter zu d*(x-y)>0 . D. h. (x-y) kann als Koeffizientenvektor einer äquivalenten linearen Schwellwertfunktion gewählt werden. Bei der Berechnung von Koeffizientenvektoren mit induktiven Lernverfahren muss aber natürlich geprüft werden, ob durch ein Verfahren für eine lineare Maschine die gleiche Entscheidungsfunktion gelernt wird, wie für eine lineare Schwellwertfunktion.

Brodley und Utgoff unterteilen die Konstruktion einer multivariaten Entscheidungsfunktion für einen Knoten in verschiedene Schritte:

Auswahl von Attributen aus denen die Linearkombination zusammengesetzt werden soll
Bestimmung der Koeffizienten für mehrere verschiedene Linearkombinationen
Auswahl einer Linearkombination (also eines zusammengesetzten Attributs) für den aktuellen Knoten

In jedem dieser Schritte können unterschiedliche Optimierungskriterien verwendet werden. Dadurch können Funktionen konstruiert werden, die nur noch formal multivariat sind, tatsächlich aber nur von einem Attribut abhängen. Oder solche, die zwar mehrere Attributwerte einbeziehen, aber sie dann durch sehr kleine Koeffzienten nicht nutzen. Auch Entscheidungsfunktionen, die von allen Attributen abhängen, entsprechen nicht unbedingt der Idee von Entscheidungsbäumen.

4.4.1.1: Attributauswahl

4.4.1.2: Koeffizientenbestimmung

4.4.1.3: Evaluierung

Insgesamt muss aber gesagt werden, dass bei den multivariaten Verfahen so viele Variationsmöglichkeiten bestehen, dass die beschriebene Untersuchung allenfalls Hinweise auf Unterschiede und Einflussfaktoren geben kann, sicherlich aber keine abschließende Berwertung der Verfahren darstellt.