2.3.9: 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 eine Funktion, in die mehrere Attribute eingehen.

Als Beispiel kann man aus zwei reellwertigen Attributen A₁,A₂:D->R das zusammengesetzte Attribut A_z:D->{0,1} mit

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. (Als Linearkombination bezeichnet man eine gewichtete Summe von Variablen, hier also Attributen.) Sie setzt 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 die Entscheidung zwischen zwei Zielmengen von 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ässt 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 nämlich eine lineare Maschine mit zwei Zielmengen, kann man die Entscheidung so charakterisieren:

A

(d)

=

{

1 falls d*x>d*y 0 sonst

Dabei sind x und y die Koeffizientenvektoren undd bezeichnet ein Werte-Tupel. d*x>d*y ist äquivalent zur Formulierung d*x-d*y>0 und weiter zu d*(x-y)>0 . Das heißt, (x-y) kann als Koeffizientenvektor einer äquivalenten linearen Schwellwertfunktion gewählt werden. Bei der Berechnung von Koeffizientenvektoren mit induktiven Lernverfahren muss aber geprüft werden, ob durch ein Verfahren für eine lineare Maschine die gleiche Entscheidungsfunktion gelernt wird wie bei einem für eine lineare Schwellwertfunktion.

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

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

2.3.9.1: Attributauswahl

2.3.9.2: Koeffizientenbestimmung

2.3.9.3: Evaluierung

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