Ansätze zur Konstruktion von Entscheidungsbäumen

Inhaltsverzeichnis

1. Einleitung

2. Grundlagen der Entscheidungsbäume
2.1. Thematische Einordnung im Data Mining
2.2. Einführung in die Klassifikation
2.3. Begriffsbestimmungen

3. Preprocessing
3.1. Data Cleaning
3.2. Relevance Analysis
3.3. Data Transformation

4. Algorithmen zur Erzeugung
4.1. Ursprünge
4.2. Splittingkriterien
4.2.1. Informationstheoretische Ansätze
4.2.2. Split basierend auf Distanzmaßen
4.2.3. Hybride Ansätze
4.2.4. Evaluation der Splittingkriterien
4.3. Pruning
4.3.1. Prepruning
4.3.2. Postpruning
4.3.3. Kombinierte Ansätze
4.3.4. Evaluation der Pruningansätze
4.4. Spezialisierungen oder Erweiterungen
4.4.1. Soft Splits
4.4.2. Skalierbarkeit
4.4.3. Parallele Verarbeitung
4.4.4. Multiple Bäume
4.4.5. Alternativen zur top-down Strategie
4.4.6. Inkrementelle Entscheidungsbauminduktion
4.4.7. Splits basierend auf mehr als einem Attribut

5. Entscheidungsbäume in der Praxis
5.1. Anwendungsfelder
5.2. Angebotene Softwarelösungen

6. Fazit

Abbildungs-, und Tabellenverzeichnis

Abb.1: Ross Quinlan entnommen von [Rul05]

Abb. 2.1: Lernphase der Klassifikation in Anlehnung an [HK01]

Abb. 2.2: Anwendung des gelernten Models in Anlehnung an [HK01]

Abb. 2.3: Beispiel für einen Entscheidungsbaum in Anlehnung an [HK01]

Tabelle 5.1: Übersicht über Softwarelösungen, die Entscheidungsbäume zur Klassifikation einsetzen

Tabelle 6.1: Übersicht der Algorithmen zur Entscheidungsbaumerzeugung

1. Einleitung

Abbildung in dieser Leseprobe nicht enthalten

Quelle: RuleQuest Research Pty Ltd, 2005

Abb. 1: Ross Quinlan

Entscheidungsbäume sind eine weit verbreitete Technik für Aufgaben der Klassifikation im Data Mining. Die Ursprünge der Entscheidungsbaumverfahren im Data Mining gehen auf die Arbeiten von Ross Quinlan Anfang der 1980er Jahre zurück. Ausgehend von seinem ursprünglichen Ansatz wurde seither eine Vielzahl von Algorithmen zur Konstruktion von Entscheidungsbäumen entwickelt. Ziel dieser Studienarbeit ist es, eine Übersicht über existierende Verfahren zur Konstruktion von Entscheidungsbäumen zu erarbeiten. Dabei soll herausgestellt werden, welche typischen Probleme Entscheidungsbäume aufwerfen und wie deren Relevanz für den praktischen Einsatz im betrieblichen Umfeld zu bewerten ist.

Im weiteren Verlauf dieser Arbeit wird zunächst auf die Grundlagen der Entscheidungsbäume eingegangen, im Rahmen dessen eine thematische Einordnung der Klassifikation im Data Mining geliefert wird. Daran anschließend wird das Preprocessing, das eine notwendige Voraussetzung für eine Klassifikation darstellt, vorgestellt. Des Weiteren werden Algorithmen zur Entscheidungsbauminduktion erörtert. Als Abschluß werden Beispiele für die Verwendung von Entscheidungsbäumen in der Praxis geliefert.

2. Grundlagen der Entscheidungsbäume

In diesem Kapitel werden die nötigen Grundlagen, die zum Verständnis dieses Themas benötigt werden erläutert. Dazu folgt zunächst eine thematische Einordnung dieser Arbeit im Rahmen des Data Mining. Daran anschließend wird eine Einführung in die Klassifikation gegeben. Abschließend werden einige für dieses Thema unerlässliche Begriffe definiert.

2.1. Thematische Einordnung im Data Mining

In der heutigen Zeit gibt es eine Vielzahl von Applikationen, in denen riesige Datenmengen anfallen (z.B. Daten von Scannerkassen). In diesen Daten können Informationen wie z.B. Muster verborgen liegen, deren Kenntnis potentiell nützlich seien könnten. Das Problem hierbei ist jedoch, dass die gespeicherten Datenmengen rapide anwachsen und immer unüberschaubarer werden. Das Data Mining ist die Wissenschaft, die sich die Extraktion von interessanten (d.h. nicht-trivialen, impliziten, zuvor unbekannten und potentiell nützlichen) Informationen oder Mustern aus derartigen großen Datensätzen zur Aufgabe gemacht hat. Diese Daten können sowohl aus Datenbanken wie auch aus Data Warehouses oder anderen Datenquellen (z.B. dem WWW) stammen.

In einigen Publikationen wird das Data Mining mit „ Knowledge Discovery in Databases“ (KDD) gleichgesetzt. Es dominiert jedoch die Auffassung, dass das KDD einen umfassenden Prozess darstellt, in dem das Data Mining einen Teilschritt darstellt. Insgesamt besteht der Prozess des Knowledge Discovery in Databases (KDD) aus sieben Teilschritten (vgl. [HK01]):

1. Data cleaning (Bereinigung von Ausreißern und Inkonsistenzen)
2. Data integration (Kombination von Daten aus mehreren Quellen)
3. Data selection (Reduktion der Daten auf interessante Attribute)
4. Data transformation (Normierung und Anpassung von Daten)
5. Data Mining (Mustererkennung durch die Anwendung intelligenter Methoden)
6. Pattern evaluation (Identifikation von interessanten Mustern, die neuartiges Wissen darstellen)
7. Knowledge presentation (Visualisierung oder anderweitige Darstellung des zuvor extrahierten Wissens)

Das Data Mining selbst gliedert sich wiederum in fünf unterschiedliche Aufgabenbereiche (vgl. [Han]):

1. Explorative Datenanalyse (EDA),
2. Mustererkennung,
3. Inhaltserkennung,
4. Beschreibende Modellierung und
5. Vorhersagende Modellierung.

Die Aufgabe der Explorativen Datenanalyse ist es, die Daten zu durchforschen, ohne dass eine konkrete Idee vorliegt, nach was eigentlich gesucht wird. Ziel der Mustererkennung ist es, durch das Entdecken von typischen oder atypischen Mustern in den Datensätzen, spezielle Phänomene aufzudecken. Und Aufgabe der Inhaltserkennung ist es, anhand eines vorgegebenen Musters, ähnliche Muster in den Datensätzen aufzuspüren. Das Ziel der beschreibenden Modellierung ist es, eine Beschreibung für die vorliegenden Datensätze zu finden (oder für den Prozess, der die Daten erzeugt). Dagegen ist es die Aufgabe der Vorhersagenden Modellierung, auf den in den Datensätzen vorliegenden Attributen basierend den Wert eines weiteren Attributes vorherzusagen.

Für die Vorhersagende Modellierung, die für das Data Mining verwendet wird, werden wiederum unterschiedliche Methoden verwendet. Mögliche Methoden sind beispielsweise Klassifikation oder Regression. Thema dieser Arbeit soll ausschließlich die Klassifikation sein.

In der Vergangenheit wurden viele unterschiedliche Klassifikationsmodelle in der Literatur vorgeschlagen (vgl. [MST94] und [Han97]). Darunter befinden sich Entscheidungsbäume (engl. Decision Trees), lineare Regression, Nachbarschaftssuche, Regelinduktion, Künstliche Neuronale Netze, Fuzzy set theory, und Bayes-Klassifikation. Entscheidungsbäume ([BFOS84]) sind jedoch aus folgenden Gründen in der Data Mining Umgebung besonders attraktiv. Erstens ist das erzeugte Klassifikationsmodell für Menschen besonders gut nachvollziehbar, aufgrund seiner intuitiven Repräsentation (vgl. [BFOS84] und [MAR96]). Zweitens werden zur Konstruktion von Entscheidungsbäumen keinerlei Eingabeparameter vom Benutzer benötigt. Drittens können Entscheidungsbäume, verglichen mit anderen Methoden, in relativ kurzer Zeit erzeugt werden (vgl. [SAM96] und [GRG98]). Viertens ist die Genauigkeit (engl. accuracy) der durch Entscheidungsbäume erstellten Modelle vergleichbar oder sogar besser als die anderer Klassifikationsmodelle (vgl. [MST94], [Mur95] und [LLS97]).

Hier ist zu bemerken, dass teilweise nahtlose Übergänge zwischen den einzelnen Verfahren existieren. So können z.B. Entscheidungsbäume mittels evolutionärer Programmierung (vgl. [DD04]) erstellt werden, oder es können beispielsweise Entscheidungsbäume mit Neuronalen Netzen in der Weise kombiniert werden, dass die Ausgabe von Künstlichen Neuronalen Netzen als Eingabeparameter für Algorithmen zur Entscheidungsbaumerzeugung dienen können (vgl. [SAG99]). Andere Verfahren wie z.B. CN2 (Clark & Niblett 2) (vgl. [CN89]) generieren Entscheidungsregeln ohne Entscheidungsbaumkonstruktion. Es existieren viele unterschiedliche Disziplinen neben dem Data Mining (darunter Mustererkennung, Statistik, Entscheidungstheorie, Machine Learning, Mathematische Programmierung, und andere), die im Bereich der Entscheidungsbäume weitere Forschungen betreiben.

Im weiteren Verlauf meiner Arbeit, werde ich mich darauf beschränken, Algorithmen der Klassifikation zu behandeln, die zur Erzeugung von Entscheidungsbäumen (engl. Decision Tree Induction) dienen.

2.2. Einführung in die Klassifikation

Der Prozess der Klassifikation besteht in der Regel aus zwei Schritten (vgl. [HK01]).

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2.1: Lernphase der Klassifikation

Im ersten Schritt, der Lernphase oder Trainingsphase, dargestellt in Abbildung 2.1, wird aus einem vorgegebenen Datensatz ein Model erzeugt, dass die Daten innerhalb dieses Datensatzes beschreibt. Es wird dabei angenommen, dass jedes Tupel des Datensatzes einer bestimmten Klasse angehört, die Klassenzugehörigkeit wird durch ein bestimmtes Attribut, dem „Class-label“ bestimmt. Im Kontext der Klassifikation werden die einzelnen Tupel eines Datensatzes auch als „Samples“, „Examples“ oder „Objekte“ bezeichnet. Die Tupel, die analysiert werden um das Model zu konstruieren, bilden den Trainingsdatensatz. Die individuellen Tupel innerhalb des Trainingsdatensatzes werden auch als „Training Samples“ bezeichnet, und sind willkürlich aus der Menge der Samples gewählt. Da für jedes Tupel des Trainingsdatensatzes ein Class-label zur Verfügung steht, ist dieser erste Schritt als überwachtes Lernen (engl. Supervised learning) bekannt. Im Gegensatz dazu ist beim unüberwachten Lernen (oder auch Clustering) das Class-label unbekannt.

Typischerweise wird das gelernte Model in Form von Klassifikationsregeln (engl. Classification rules), Entscheidungsbäumen oder mathematischen Formeln präsentiert. Diese Klassifikationsregeln können sowohl dazu verwendet werden, ein besseres Verständnis von dem vorliegendem Datensatz zu erlangen, als auch die Klassenzugehörigkeit (das Class-label) von zukünftigen Datensätzen vorherzusagen.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2.2: Anwendung des gelernten Models

Der zweite Schritt ist dann die Anwendung des Models zur Klassifikation, dargestellt in Abbildung 2.2. Dabei wird als erstes die Vorhersagegenauigkeit (engl. Accuracy) des Models (oder der Klassifikationsregeln) überprüft. Bei der Holdout-Methode wird z.B. nur ein Teil aller Tupel eines vorliegenden Datensatzes als Trainingsdatensatz verwendet. Die restlichen Tupel werden dazu verwendet, die Vorhersagegenauigkeit des Models abzuschätzen. Dabei wird für jedes dieser restlichen Tupel das bekannte Class-label mit der vom Model vorhergesagten Klassenzugehörigkeit verglichen. Ganz wichtig für eine erfolgreiche Klassifikation ist bei der Anwendung der Holdout-Methode, dass keine statistische Abhängigkeit zwischen Trainingsdatensatz und den restlichen Daten besteht.

Sobald das Model als akzeptabel eingeschätzt wird, kann das Model anschließend zur Klassifikation von zukünftigen Tupeln eingesetzt werden, deren Klassenzugehörigkeit (d.h. deren Class-label) unbekannt ist. Tupel, deren Klassenzugehörigkeit nicht bekannt ist, werden in der Literatur auch als „unknown“ oder „previously unseen“ bezeichnet.

Das Verfahren der Klassifikation kann beispielsweise angewendet werden, um Klassifikationsregeln aus einer Kundendatenbank einer Bank abzuleiten. Anhand dieser Klassifikationsregeln kann anschließend z.B. die Kreditwürdigkeit zukünftiger Kunden beurteilt werden.

2.3. Begriffsbestimmungen

Im Zusammenhang der Klassifikation werden in der Literatur häufig unterschiedliche Begriffe als Synonym verwendet. Um Klarheit zu schaffen, werden an dieser Stelle einige Begriffe erläutert.

So wird z.B. ein einigen Publikationen davon gesprochen, dass es Unterschiede zwischen einem Klassifikationsbaum (engl. Classification Tree) und einem Entscheidungsbaum (engl. Decision Tree) gibt. Da in den meisten Publikationen jedoch davon ausgegangen wird, dass diese beiden Begriffe identisch sind, schließe ich mich dieser Auffassung an.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2.3: Beispiel für einen Entscheidungsbaum

Ein Entscheidungsbaum (vgl. [HK01]) ist ein gerichteter, zyklenfreier Graph, der eine baumartige Struktur hat, die aus einer Wurzel, Kanten, Knoten und Blättern besteht. Jeder Knoten kennzeichnet dabei den Test für ein Attribut, jede Kante kennzeichnet das Ergebnis eines solchen Testes und jedes Blatt repräsentiert eine Klasse. Abbildung 2.3 zeigt einen typischen Entscheidungsbaum. Dieser Baum repräsentiert eine beispielhafte Klassifikation für einen Computerkauf. D.h. anhand dieses Models lässt sich vorhersagen, ob ein neuer Kunde einen Computer kaufen wird oder nicht. Interne Knoten des Baumes stellen dabei die Tests für ein Attribut dar. Blätter zeigen die jeweilige Klassenzugehörigkeit an.

Um ein zuvor unbekannten Kunden zu klassifizieren, werden die Attribute des Kunden (Alter, Student, Kreditwürdigkeit) gemäß des Entscheidungsbaumes getestet. Dabei wird von der Wurzel des Baumes an vorgegangen. In dem Beispiel würde als erstes das Alter des Neukunden erfragt werden. Anschließend würde entsprechend der Antwort darauf solange dem Pfad des Baumes gefolgt werden, bis ein Blatt erreicht ist. Das entsprechende Blatt würde dann die Klassenzugehörigkeit des zu klassifizierenden Neukunden voraussagen.

Die Knoten eines Baumes werden auch als nicht - terminale Knoten oder als Testknoten bezeichnet. Die Blätter eines Baumes nennt man auch terminale Knoten oder Entscheidungsknoten (vgl. [Mur98]).

Anhand der Anzahl von Verzweigungen an den Knoten unterscheidet man in der Regel zwischen binären und nicht-binären Entscheidungsbäumen. Bei einem binären Baum hat jeder Knoten genau zwei Verzweigungen, gemäß dem Ausgang eines Tests (wahr oder falsch). Bei nicht-binären Bäum ist in der Regel die Anzahl der Verzweigungen an einem Knoten identisch mit der Anzahl an verschiedenen Ausprägungen (oder Werten) eins Attributs.

Oft wird bei einem Baum zwischen geordneten und ungeordneten Attributen unterschieden (vgl. [AJY04]). Ein geordnetes Attribut (oder Variable) ist ein Attribut, dass kontinuierliche Werte (auch numerische Werte oder engl. Continuous values) (beispielsweise real oder integer) besitzt. Ein ungeordnetes Attribut besitzt dagegen diskrete Werte (kategorische, freie Werte oder auch engl. symbolic values) (bespielsweise boolean). Es gibt einige Algorithmen, die nur mit geordneten bzw. nur mit ungeordneten Attributen umgehen können. Der Algorithmus C4.5 beispielsweise kann in seiner ursprünglichen Version nur mit ungeordneten Attributen umgehen. Da in der Literatur Verfahren vorgestellt wurden, mit denen geordnete in ungeordnete Attribute (vgl. [Qui96], [FI92], [Ker92], [Mer93] und [MW94]) und umgekehrt (vgl. [FI93] und [FKS95]) umgewandelt werden können, ist diese Problematik jedoch zu vernachlässigen.

Außerdem kann zwischen univariaten, multivariat-lineare und nicht-linearen Entscheidungsbäumen unterschieden werden (vgl. [IS96]). Bei univariaten Entscheidungsbäumen wird an jedem Knoten nur ein Attribut getestet. Diese Art von Bäumen ist sehr populär wird z.B. bei den später angesprochenen Algorithmen ID3 und C4.5 verwendet. Bei multivariat-linearen Bäumen (oder auch einfach nur multivariate Bäume oder auch engl. oblique Trees) wird an jedem Knoten nicht nur ein Attribut getestet, sondern eine Linearkombination aus mehreren Attributen. Nicht-lineare Entscheidungsbäume, sind Bäume, an deren Knoten Nicht-Linearkombinationen aus mehreren Attributen getestet werden.

An jedem Knoten eines Entscheidungsbaumes wird eine Rangfolge aus allen zur Verfügung stehenden Attributen gebildet. Das Attribut, das am nützlichsten ist, um die Tupel an diesem Knoten in Klassen zu unterscheiden, wird als Testkriterium T ausgewählt. Dieses Testkriterium wird in der Literatur auch Splittingkriterium, oder engl. „Split criteria“, „Feature evaluation” oder auch als „goodness measure“, „feature evaluation criteria“, „feature selection criteria“, oder als „impurity measure“ bezeichnet (vgl. [Mur98]).

Die Technik der Erzeugung oder Generierung eines Entscheidungsbaumes aus einem vorliegenden Datensatz nennt man in der englischen Literatur „decision tree induction“, „tree building“, oder auch „tree growing“ (vgl. [Mur98]).

3. Preprocessing

Vor der eigentlichen Klassifikation werden meistens die vorliegenden Datensätze „vorbehandelt“ (engl. Preprocessing), da das Data Preprocessing oftmals dabei helfen kann, die Genauigkeit (engl. accuracy), die Effizienz und die Skalierbarkeit eines anschießenden Klassifikationsverfahrens zu steigern (vgl. [HK01]). Der Vorteil am Preprocessing ist, dass dieses Verfahren unabhängig (d.h. zeitversetzt) von der Klassifikation durchgeführt werden kann, und die Performance des Klassifikationsverfahrens nicht beeinträchtigt wird. Oftmals ist das Preprocessing sogar eine Voraussetzung für die erfolgreiche Anwendung der Methoden der Klassifikation auf einen gegebenen Datensatz. Bei dem Algorithmus C4.5 wird beispielsweise vorausgesetzt, dass in einem vorliegenden Trainingsdatensatz keine fehlenden Werte (engl. Missing Values) vorhanden sind. Fehlende Werte würde die Qualität des Ergebnisses des C4.5 Algorithmus erheblich verschlechtern.

Typischerweise besteht das Data Preprocessing (vgl. [HK01]) aus den drei Phasen des Data Cleanings, der Relevance Analysis und der Data Transformation, die im Folgenden genauer vorgestellt werden.

3.1. Data Cleaning

Das Data Cleaning (dt. Datenbereinigung) stellt in der Regel den ersten Schritt im Data Preprocessing dar. In dieser Phase geht es darum, Störungen in den Daten zu erkennen, zu reduzieren und wenn möglich zu beseitigen. Störungen könnten z.B. Ausreißer darstellen, die durch Glättungstechniken (engl. Smoothing) eliminiert werden sollten. Weiterhin fällt die Behandlung von fehlenden Werten in den Bereich des Data Cleaning. Ein fehlender Wert ist z.B. ein Attribut, zu dem keine Ausprägung vorhanden ist. Fehlende Werte könnten durch den am häufigsten vorkommenden Wert oder durch den am wahrscheinlichsten Wert ersetzt werden (zu bestimmen durch Methoden der Statistik).

3.2. Relevance Analysis

Viele Attribute innerhalb eines gegebenen Datensatzes sind oftmals für eine bestimmte Klassifikationsaufgabe irrelevant. Wiederum andere Attribute können hingegen redundant sein. Daher ist es die Aufgabe der Relevanzanalyse, irrelevante oder redundante Attribute von der weiteren Betrachtung auszuschließen, weil diese nicht benötigten Informationen ansonsten den Klassifikationsprozess unnötig verlangsamen würden. In der Disziplin des Machine Learning wird dieser Schritt auch als „Feature selection“ oder „Feature subset selection“ bezeichnet. In diversen Disziplinen wurden Algorithmen entwickelt, mit Hilfe deren automatisiert irrelevante und redundante Attribute aufgespürt werden können (vgl. [Mur98]).

In manchen Fällen bringt es erhebliche Vorteile für die Klassifikation, nicht nur relevante Attribute auszuwählen, sondern auch Kombination von Attributen zu erstellen. Solche logischen oder arithmetischen Kombinationen werden „composite features“ genannt (vgl. [Mur98]).

Eine weitere Aufgabe der Relevanzanalyse ist es, eine sinnvolle Aufteilung der vorliegenden Daten in einen Trainingsdatensatz zur Modellerstellung und einen Testdatensatz zu Modellverifikation zu bestimmen. Mit dieser Problematik beschäftigt sich die Technik der „subsample selection“. Wichtig ist vor allem, dass zwischen den Trainings- und Testdaten keinerlei statistische Abhängigkeit besteht, da sonst die Qualität des erstellten Klassifikationsmodells in Frage zu stellen ist. Murthy [Mur98] liefert auch hier gute Einstiegspunkte in die Literatur. Unter anderem ist hier eine Technik namens „windowing“ von Quinlan zu erwähnen, die in die Algorithmen ID3 und C4.5 Einzug gefunden hat. Beim „windowing“ wird per Zufall ein Trainingsdatensatz gewählt, der solange um Tupel erweitert wird, bis alle „wichtigen“ Tupel im Trainingsdatensatz enthalten sind.

3.3. Data Transformation

In dieser Phase des Data Cleaning könnten oder besser sollten die vorliegenden Daten generalisiert und normalisiert werden, um weiterhin die Genauigkeit (engl. accuracy), die Effizienz und die Skalierbarkeit des anschließenden Klassifikationsverfahrens zu steigern.

Unter der Generalisierung von Daten versteht man unter anderem, dass z.B. numerische Werte kategorisiert werden. Dieser Vorgang wird in der Literatur auch Diskretisierung oder engl. discretization genannt (vgl. [WZ00]). Beispielsweise könnten die Werte des Attributs „Einkommen“ in die Kategorien „Gering“, „Mittel“ und „Hoch“ kategorisiert werden. Aber auch für nominale Variablen ist eine Generalisierung denkbar. So könnte z.B. das Attribut „Adresse“ in ein Attribut „Stadt“, „Region“ oder „Land“ überführt werden. Die Generalisierung führt zu einer Art Komprimierung oder Abstraktion der Daten und erleichtert somit insbesondere bei riesigen Datenmengen die Klassifikation ganz erheblich.

Die Normalisierung von Daten versteht man in der Regel, dass sämtliche Werte in einen bestimmten Skalenbereich überführt werden. So könnte man z.B. sämtliche Werte in den Bereich von 0,0 bis ± 1,0 überführen. Dies hat den Vorteil, dass die Werte unterschiedlicher Attribute miteinander vergleichbar gemacht werden. Attribute mit großen Werten (z.B. Einkommen - 40.000) würden dann nicht mehr Attribute mit kleinen Werten (z.B. Alter - 35) überwiegen. Die Normalisierung spielt besonders bei den Splittingkriterien (vgl. Kapitel 4.2.) eine große Rolle.

4. Algorithmen zur Erzeugung

In den folgenden Abschnitten werden Algorithmen, die zur Erzeugung von Entscheidungsbäumen dienen, erläutert. Dazu werden zunächst die Ursprünge dieser Algorithmen kennzeichnet. Anschließend wird auf Splittingkriterien und Pruning eingegangen. Abschließend werden einige Spezialisierungen oder Erweiterungen eingegangen.

4.1. Ursprünge

Mit der Notwendigkeit der Analyse von Umfragedaten in der Statistik begann die Forschung an Entscheidungsbäumen. Die meisten Verfahren, zur Induktion von Entscheidungsbäumen, die seit dem entwickelt wurden, basieren auf Hunt’s Methode aus dem Jahre 1966 (vgl. [HMS66]), die im so genannten Concept Learning System (CLS) integriert wurde.

CLS benutzt zur Konstruktion von Entscheidungsbaum eine recht aufwändige „look-ahead“ Strategie (vgl. [Qui86]). An jedem Knoten eines Baumes bildet CLS aus den vorliegenden Daten alle möglichen Unterbäume bis zu einer vorgegebenen Tiefe und wählt aus diesen erzeugten Unterbäumen den am besten geeigneten Unterbaum aus. In Abhängigkeit von der vorgegebenen Tiefe benötigt CLS demnach ein erhebliches Maß an Berechnungszeit, ist jedoch letztendlich dazu fähig verborgene Muster in den vorliegenden Daten aufzuspüren.

Auch Statistische Programme wie AID ([SBM71]), MAID ([Gil72]), THAID ([MM73]) und CHAID ([Kas80]) konstruieren Bäume, mit dem Ziel Abhängigkeiten zwischen verschiedenen Attributen aufzudecken.

Die neueren Verfahren zur Induktion von Entscheidungsbäumen verfahren in der Regel nach dem folgenden Schema, das erstmals von Breiman et al. [BFOS84] vorgestellt und dann von Quinlan 1986 im Rahmen des von ihm entwickelten ID3 Algorithmus (vgl. [Qui86]) übernommen wurde. Und zwar gehen die Verfahren in zwei Phasen zur Modelerstellung vor (vgl. [RS98]), der Konstruktionsphase und der Pruningphase.

In der ersten Phase, der Konstruktionsphase (engl. building phase) werden die Trainingsdaten solange rekursiv partitioniert, bis alle Tupel in einer Partition derselben Klasse angehören. Für jede Partition wird ein neuer Knoten an den Entscheidungsbaum angehängt. Die meisten Algorithmen gehen dabei von oben nach unten vor, d.h. im Anfangszustand hat der Baum lediglich einen einzigen Knoten, die Wurzel, für den gesamten Trainingsdatensatz. Für jede Partition P wird ein Testkriterium T zur weiteren Partitionierung in P1, …, Pm bestimmt. Neue Knoten für P1, …, Pm werden dem Entscheidungsbaum als Kindknoten zu P angehängt. Anschließend wird der Knoten P mit dem Test T benannt, und danach werden die Partitionen P1, …, Pm rekursiv weiterpartitioniert. Eine Partition, in der alle Tupel einer identischen Klasse angehören (ein identisches Class-Label) haben, wird nicht weiter aufgeteilt, und das Blatt wird entsprechend seiner Klassenzugehörigkeit benannt. Abbildung 2.3 ist ein Beispiel für einen resultierenden Entscheidungsbaum.

Auf diese Art und Weise wird in der ersten Phase ein Entscheidungsbaum erstellt, der jedes Tupel aus den Trainingsdaten perfekt in eine bestimmte Klasse einordnet. Meistens sind es aber nicht-perfekte und verkleinerte Bäume, die es erlauben mit höherer Genauigkeit neue (zukünftige) Tupel zu klassifizieren. Der Grund dafür ist, dass ein perfekter Baum aufgrund von statistischen Unregelmäßigkeiten zu sensitiv auf den Trainingsdatensatz angepasst ist. Dieses Problem des „overfitting“ wird bei den meisten Algorithmen dadurch gelöst, dass sich an die Konstruktionsphase eine Pruningphase anschließt, in der die Knoten des Entscheidungsbaumes iterativ wieder „beschnitten“ werden, um die Genauigkeit des Baumes zu verbessern.

Seit der Einführung des ID3-Algorithmusses wurden inzwischen zahlreiche erweiterte und verbesserte Verfahren vorgestellt. Darunter befindet sich beispielsweise der C4.5 Algorithmus (vgl. [Qui93]), der von Quinlan 1993 als Nachfolger von ID3 eingeführt wurde und bis heute einer der am häufigsten benutzten Entscheidungsbauminduktionsalgorithmen ist. Unter den verbesserten Verfahren befindet sich beispielsweise auch der PUBLIC-Algorithmus (vgl. [RS98]), der von dem hier vorgestellten Zwei-Phasenschema abweicht, indem das Building und das Pruning zu einer einzigen Phase zusammengefasst wurden. Im weiteren Verlauf dieser Arbeit werden die einzelnen Verbesserungen bzw. Erweiterungen zu dem ursprünglichen Schema von ID3 nach und nach vorgestellt, insbesondere in Kapitel 4.4.

4.2. Splittingkriterien

Viele Algorithmen zur Induktion von Entscheidungsbäumen, die seit der Entwicklung von ID3 vorgestellt wurden, haben ein gemeinsames Vorgehen: An jedem Knoten eines Entscheidungsbaumes wird eine Rangfolge aus allen zur Verfügung stehenden Attributen gebildet. Das Attribut, das am nützlichsten ist, um die Tupel an diesem Knoten in Klassen zu unterscheiden, wird als Testkriterium T ausgewählt. Diese Algorithmen unterscheiden sich jedoch vor allem darin, welches Testkriterium T (oder auch Splittingkriterium) eingesetzt wird. In dem folgenden Abschnitt sollen die unterschiedlichen Splittingkriterien, unterteilt in die Kategorien Informationstheorie, Distanzmaße und hybride Ansätze, vorgestellt werden.

4.2.1. Informationstheoretische Ansätze

Quinlan optimierte das zeitaufwändige Vorgehen der Look-ahead-Strategie des CLS-Algorithmuses (vgl. Kapitel 4.1) dadurch, dass er in seinem Verfahren ID3 eine simple Heuristik verwendete. Diese Heuristik basiert auf Shannon’s Informationstheorie (vgl. [Sha48]). Bei diesem Ansatz liegt die Annahme zu Grunde, dass bei einer Entscheidungsbaumkonstruktion eine Minimierung der Knotenanzahl in der Regel zu relativ einfachen (wenig komplexen) Bäumen führt (vgl. [HK01]). Deshalb wird bei diesem informationstheoretischen Ansatz versucht, die Anzahl an Partitionierungen, die benötigt wird um einen Testdatensatz zu klassifizieren, zu minimieren.

Das iterative Vorgehen eines Algorithmus ist dabei wie folgt: für die Partitionierung an einem bestimmten Knoten des Entscheidungsbaumes wird aus dem Trainingsdatensatz das Attribut mit dem größten Informationsgehalt (engl. Information Gain) oder der größten Entropy-Reduktion als Testkriterium T ausgewählt. Dieses Attribut minimiert die Informationen, die nötig sind, um die Tupel in die resultierenden Partitionen aufzuteilen.

Formel 4.1

Entropy (E)

Abbildung in dieser Leseprobe nicht enthalten

Formel 4.2

Entropy (E)

Abbildung in dieser Leseprobe nicht enthalten

Formel 4.3

Information Gain (IG)

Abbildung in dieser Leseprobe nicht enthalten

Formel 4.4

Gain Ratio (GR)

Abbildung in dieser Leseprobe nicht enthalten

Formel 4.5

Abbildung in dieser Leseprobe nicht enthalten

Die Menge an Informationen, die zur Klassifikation einer Menge I von Tupeln benötigt werden, kann durch die Entropy (Formel 4.1, vgl. [VO03]) berechnet werden. Dabei bezeichnet P(ci) die empirische Häufigkeit einer Kategorie Ci, und n ist die Anzahl von unterschiedlichen Kategorien, die innerhalb der Tupelmenge auftauchen. Falls der Wert eines Attributes X bekannt ist, reduziert sich die Menge an benötigten Informationen zur Klassifikation, und lässt sich gemäß Formel 4.2 (vgl. [VO03]) berechnen. Dabei gilt X={x1,x2,…,xk} und mi ist die Anzahl von Kategorien innerhalb der Untermenge von Tupeln li. Der Informationsgehalt (engl. Information Gain), der durch die Kenntnis des Wertes von Attribut X entsteht, kann durch Formel 4.3 (vgl. [VO03]) berechnet werden. An jedem Knoten wird das Attribut, das den höchsten Informationsgehalt besitzt, ausgewählt.

Die Algorithmen ID3 und C4.5 versuchen gemäß der Formel 4.4 (vgl. [VO03]) die Gain Ratio, also den Informationsgehalt, beim Partitionieren der Tupel eines Knotens, zu optimieren. Mingers (vgl. [Min89]) schlug im Jahre 1989 eine Variante vor, in dem er die G-Statistik als Splittingkriterium anstelle der Gain Ration einführte. Die G-Statistik berechnet sich nach Formel 4.5 (vgl. [VO03]), wobei N für die Anzahl aller Tupel an einem Knoten steht. Mir ist allerdings kein Algorithmus bekannt, indem die G-Statistik als Splittingkriterium implementiert ist.

4.2.2. Split basierend auf Distanzmaßen

Die Distanzmaße stellen Alternativen zur Verwendung des informationstheoretischen Ansatzes dar. Diese Splittingkriterien messen die Separierbarkeit, Divergenz oder die Diskriminierung zwischen verschiedenen Klassen. Ein sehr populäres Distanzmaß ist der Gini-Index, der in zahlreichen Algorithmen, wie CART [BFOS84], OC1 [Mur95], SLIQ [MAR96], SPRINT [SAM96] und CLOUDS [ARS98] gemäß Formel 4.6 verwendet wird (vgl. [VO03]).

Formel 4.6

Gini-Index

Abbildung in dieser Leseprobe nicht enthalten

Formel 4.7

Abbildung in dieser Leseprobe nicht enthalten

Abbildung in dieser Leseprobe nicht enthalten

Formel 4.8

Laplace

Abbildung in dieser Leseprobe nicht enthalten

Breiman et. al konnten jedoch nachweisen, dass der Gini-Index als zuverlässiges Kriterium versagt, sobald eine große Anzahl von unterschiedlichen Klassen vorhanden ist, und schlugen daher als Verbesserung eine Twoing-Regel vor (vgl. [BFOS84]). Zahlreiche andere Distanzmaße sind in der Literatur vorgeschlagen worden, wie z.B. die Bhattacharya-Distanz [LF83], die Kolmogorov-Smirnof Distanz [Fri77], die Abbildung in dieser Leseprobe nicht enthalten-Statistik [Bel59] (verwendet in CHAID, Berechnung gemäß Formel 4.7), die Laplace-Distance (Berechnung gemäß Formel 4.8) und das Mean-Posterior-Improvement (MPI) [TS93]. All diese Splitkriterien haben aber kaum in einem Algorithmus zur Entscheidungsbauminduktion Verwendung gefunden.

4.2.3. Hybride Ansätze

In der Literatur wurden auch Ansätze vorgeschlagen, bei denen verschiedene Kriterien miteinander kombiniert werden. Gleser und Collen (vgl. [GC72]) benutzten z.B. eine Kombination aus Informationsgewinn und Abbildung in dieser Leseprobe nicht enthalten-Statistik. Murthy [Mur98] bietet einen guten Einstiegspunkt in die Literatur zu weiteren hybriden Ansätzen.

Ein sehr viel versprechender Ansatz sollte an dieser Stelle aber dennoch erwähnt werden. Mit „RainForest“ wurde von Gehrke et al. im Jahre 1998 ein Framework geschaffen (vgl. [GRG98]). Dieses Framework wurde so konzipiert, dass jedes beliebige Splittingkriterium innerhalb des Frameworks verwendet werden kann. Somit erlaubt dieser Ansatz dem Anwender die Freiheit das Kriterium, das er für seine Anwendung als am besten geeignet hält, selbst auszuwählen. Im Gegensatz dazu wurde in den bisherigen Verfahren jeweils nur ein einziges Splittingkriterium implementiert (C4.5 verwendet Information Gain, SLIQ und SPRINT verwenden den Gini-Index usw.).

4.2.4. Evaluation der Splittingkriterien

Da eine große Anzahl an unterschiedlichen Splittingkriterien, wie in Kapitel 4.2.1 bis 4.2.3 vorgestellt, verfügbar ist, ist es sicherlich interessant, deren Eigenschaften bei der Konstruktion von Entscheidungsbäumen miteinander zu vergleichen.

In der Literatur sind vor allem empirische Vergleiche zu finden. Das Ergebnis zweier Studien von Hart [Har84] und Quinlan [Qui86] ist, das das Information Gain Attribute bevorzugt, die eine große Anzahl von unterschiedlichen Ausprägungen besitzen. Quinlan [Qui93] schlägt daher als Abhilfe vor, die Gain Ratio als Splittingkriterium zu verwenden. Mantaras [Man91] zeigte auf, dass es mit Gain Ratio auch Probleme gibt, und schlug ein weiteres Distanzmaß, das auf die Informationstheorie basiert, als Splittingkriterium vor. White und Liu [WL94] fanden in ihren Experimenten heraus, dass sowohl Information Gain, als auch Gain Ratio, als auch Mantara’s Maß unter bestimmten Umständen schlechter ist, als die Verwendung einer Abbildung in dieser Leseprobe nicht enthalten-Statistik.

In den Studien von Baker und Jain [BJ76], Ben-Bassat [Ben78], Breiman et al. [BFOS84] und Mingers [Min89], kommen die Autoren alle zu einem ähnlichen Ergebnis (vgl. [Mur98]): Kein Kriterium ist in sämtlichen Bereichen allen anderen Splittingkriterien überlegen. Und es gibt auch keine effektive Strategie, bei der Splittingkriterien alternierend angewendet werden können. Die Qualität eines erzeugten Entscheidungsbaumes hängt im Allgemeinen nur geringfügig davon ab, welches Splittingkriterium benutzt wird. Viel entscheidender ist dagegen das Pruning, das im folgenden Kapitel vorgestellt wird.

Besonders hervorzuheben ist das RainForest Framework durch seine Vielseitigkeit. Da jedes beliebige Splittingkriterium innerhalb des Frameworks verwendet werden kann, ist RainForest am vielseitigsten verwendbar.

4.3. Pruning

Das engl. Wort „Pruning“ bedeutet im deutschen das „Entästen“, „Beschneiden“ oder „Zurückstutzen“ eines Baumes. Damit ist im Zusammenhang des Data Mining gemeint, dass ein erzeugter Entscheidungsbaum so verkleinert wird, dass die Genauigkeit des Baumes optimiert wird. Damit löst das Pruning das Problem des Overfittings (vgl. Kapitel 4.1). Wie auch schon im vorigen Kapitel angedeutet wurde, spielt das Pruning eine ganz entscheidende Rolle für die Qualität und die Performance eines Entscheidungsbaumes.

Im Pruning kommen typischerweise statistische Methoden, die Anomalien wie z.B. Ausreißer aufdecken und die entsprechenden Verästelungen eines Baumes entfernen, zur Anwendung (vgl. [HK01]). Durch die Anwendung dieser Methoden resultieren Bäume, die eine schnellere Klassifikation mit einer geringeren Fehlerwahrscheinlichkeit ermöglichen. Bei dem Pruning gibt es zwei verschiedene Ansätze, das Prepruning und das Postpruning. Beide Ansätze werden im Folgenden genauer vorgestellt. Außerdem wird im Weiteren beispielhaft ein aus beiden Ansätzen kombiniertes Verfahren vorgestellt. Abschließend werden diese unterschiedlichen Ansätze miteinander verglichen.

4.3.1. Prepruning

Bei dem Ansatz des Preprunings, wird ein Baum dadurch, dass bei seiner Konstruktion rechtzeitig angehalten wird, gestutzt (vgl. [HK01]). D.h. bei der rekursiven Induktion eines Entscheidungsbaumes muss an einem entsprechenden Knoten rechtzeitig entschieden werden, die Tupelmenge an diesem Knoten nicht weiter zu partitionieren. Wenn entschieden wird, die Partitionierung an einem Knoten zu stoppen, so wird bei diesem Ansatz der Knoten zu einem Blatt. Dem Blatt wird diejenige Klassenzugehörigkeit zugeteilt, die bei den entsprechenden Tupeln am häufigsten vorkommt.

Technisch kann die Entscheidung zu stoppen beispielsweise wie folgt realisiert werden (vgl. [HK01]): bei der Konstruktion eines Baumes kann eines der Splittingkriterien, die in Kapitel 4.2 besprochen wurden, dazu benutzt werden, zu entscheiden, gemäß welchem Attribut die Tupel eines Knotens unterteilt werden. Wenn die Partitionierung der Tupel eines Knotens unter einen gewissen Schwellwert fällt, so wird die Partitionierung gestoppt, und der Knoten wird zu einem Blatt. Schwierigkeiten könnte es jedoch dabei geben, einen entsprechenden Schwellwert zu finden, mit dem weder zu verästelte noch zu vereinfachte Bäume konstruiert werden.

4.3.2. Postpruning

Alternativ zum Prepruning kann auch das Postpruning verwendet werden (vgl. [HK01]). Bei dem Postpruning wird zuerst ein Entscheidungsbaum vollständig aufgebaut, und anschließend wieder zurechtgestutzt. Ein Beispiel für diesen Ansatz ist der Cost-Complexity Pruning Algorithmus (vgl. [BFOS84] und [Qui87]). Der Algorithmus berechnet für jeden Knoten des Baumes eine erwartete Fehlerquote, die entstehen würde wenn alle von diesem Knoten ausgehenden Äste entfernt würden. Als nächstes wird die erwartete Fehlerquote berechnet, die entstehen würde, wenn die von diesem Knoten ausgehenden Äste nicht entfernt würden. Wenn die zweite Fehlerquote geringer ist, als die erste, bleiben die Äste erhalten, andernfalls wird der Knoten zu einem Blatt gemacht. Nachdem auf diese Weise unterschiedliche, stufenweise zurechtgestutzte Bäume erstellt wurden, werden Tupel, die nicht dem Trainingsdatensatz angehören, dazu benutzt, die Qualität jedes dieser Bäume abzuschätzen. Der Baum mit der minimalen Fehlerquote wird bevorzugt.

Quinlan führte als Variante zum Cost-Complexity Pruning das Reduced-Error Pruning ein (vgl. [Qui87]). Dieses Verfahren geht ähnlich vor, jedoch wird anstelle mehrerer alternativer Bäume nur ein Baum erstellt, wodurch sich der Erfinder vor allem Geschwindigkeitsvorteile verspricht.

Breiman et al. [BFOS84] haben erkannt, dass die Notwendigkeit eines Datensatzes, der unabhängig vom Trainingsdatensatz ist, in manchen Fällen problematisch sein kann, vor allem wenn nur wenige Daten vorliegen. Daher haben sie das Cross-Validation vorgeschlagen (vgl. [MAR96]). Bei diesem Verfahren wird der Trainingsdatensatz in verschiedene Gruppen aufgeteilt. Für jede Gruppe von Daten wird ein Baum erzeugt. Diese Bäume werden anschließend dazu benutzt, die Qualität des originalen Baumes abzuschätzen. Dieses Verfahren hat den Vorteil, dass es kompakte Bäume mit geringer Fehlerquote erzeugt, und ist für kleine Datensätze gut geeignet. Quinlan hat z.B. dieses Verfahren in sein Softwareprodukt C5.0 integriert. Für große Datensätze ist dieses Verfahren jedoch nicht geeignet, da die Erzeugung von mehreren Bäumen viel zu viel Rechenzeit benötigen würde.

Crawford [Cra89] analysierte das Verfahren der Cross-Validation, und fand heraus, dass dieses eine hohe Varianz aufweist, besonders bei kleinen Datensätzen (vgl. [Mur89]). Daher schlug er die Methode des Bootstrapping als Alternative dazu vor. Beim Bootstrapping wird ein Trainingsdatensatz durch zufälliges Ziehen mit Zurücklegen in unabhängige Datensätze unterteilt. Bei der Cross-Validation-Methode dagegen wird kein Zurücklegen angewandt. Crawford argumentiert, dass seine Methode weniger Varianz als das Verfahren der Cross-Validation aufweist. Kohavi [Koh95] wiederum argumentiert allerdings, dass in der Praxis die Cross-Validation ganz klar gegenüber dem Bootstrapping vorzuziehen ist. Trotzdem wird das Bootstrapping beispielsweise in dem Algorithmus BOAT von Gehrke et al. [GGR99] zum Pruning verwendet.

Anstatt einen Entscheidungsbaum basierend auf geschätzten Fehlerquoten zurechtzustutzen, wird bei dem Minimum Definition Length (MDL) Prinzip die Anzahl an Bits, die benötigt wird, um einen Baum darzustellen zum Stutzen benutzt (vgl. [HK01]). Der am besten geeignete Baum ist dann der, der aus den wenigsten Bits besteht. Dieses Prinzip verfolgt den Ansatz, dass die einfachsten Bäume bevorzugt werden. Der Vorteil dieses Prinzips ist, dass im Gegensatz zum Cost-Complexity Pruning keine weiteren Tupel außer dem Trainingsdatensatz benötigt werden. Mehta et al. [MRA95] wiesen sogar nach, dass das MDL-Prinzip bei ganz verschiedenen Datensätzen immer zu Bäumen mit einer guten Genauigkeit führt, und dass diese Baume signifikant kleiner und weniger rechenzeitintensiv sind, als bei anderen Verfahren.

4.3.3. Kombinierte Ansätze

Zusätzlich zu den bisher genannten Ansätzen, gibt es auch die Möglichkeit, in einem Kombinierten Ansatz sowohl Prepruning als auch Postpruning zu verwenden. Aber auch hier gilt, dass eine geringere Fehlerquote durch einen höheren Rechenaufwand benötigen „erkauft“ werden muss.

Der Algorithmus “PrUning and BuiLding Integrated in Classification” (PUBLIC) von Rastogi und Shim [RS98] gehört beispielsweise zu diesen kombinierten Ansätzen, indem er Pruning- und Konstruktionsphase kombiniert. PUBLIC geht dabei wie folgt vor: während der Konstruktionsphase wird bestimmt, ob ein Knoten in der folgenden Pruningphase zurechtgestutzt werden muss. Ist dies der Fall, so wird dieser Knoten gar nicht erst weiter partitioniert. Durch dieses Vorgehen kann garantiert werden, dass der erzeugte Baum identisch mit dem Baum ist, der beim Postpruning entstehen würde. Die Schwierigkeit ist jedoch, während der Konstruktionsphase zu bestimmen, ob ein Knoten weiter partitioniert werden soll, oder nicht, weil der zu erstellende Baum in der Konstruktionsphase nur partiell vorliegt. Zu diesem Zweck haben die Autoren ein spezielles Abschätzungsverfahren entwickelt. Mit Hilfe von Experimenten gelingt es den Autoren abschließend nachzuweisen, dass deren Verfahren beträchtliche Geschwindigkeitsvorteile bringt, ohne die Qualität des erzeugten Entscheidungsbaumes erheblich zu verringern.

4.3.4. Evaluation der Pruningansätze

Der Nachteil bei allen Postpruning-Ansätzen ist, dass diese Ansätze generell mehr Rechenaufwand benötigen, als das Prepruning. Dafür führen die Postpruning-Ansätze aber auch zu Entscheidungsbäumen mit geringeren Fehlerquoten. Kim und Köhler [KK94] analysieren in ihrem Werk genauer, unter welchen Bedingungen das Postpruning besser geeignet ist als das Prepruning.

Es gibt einige Studien (vgl. [Min89], [Coh93] und [EMS95]), in denen die relative Effektivität von verschiedenen Pruningmethoden verglichen wird (vgl. [Mur98]). Das Ergebnis dieser Studien ist, genau wie bei den Splittingkriterien, dass es keine Pruningmethode gibt, die in sämtlichen Fällen allen anderen Methoden überlegen ist. Die Wahl einer geeigneten Methode hängt dabei wieder einmal vor allem von der Größe und den Eigenschaften des vorliegenden Datensatzes und von der Verfügbarkeit von zusätzlichen Informationen für das Pruning ab.

4.4. Spezialisierungen oder Erweiterungen

In den folgenden Abschnitten wird auf Spezialisierungen oder Erweiterungen zu den traditionellen Entscheidungsbauminduktionsalgorithmen eingegangen. Dazu werden im Folgenden Soft-Splits, Skalierbarkeitsaspekte, Möglichkeiten zur parallelen Verarbeitung, die Verwendung multipler Bäume, sowie Alternativen zur top-down Strategie, inkrementelle Entscheidungsbauminduktion und Splits, die auf mehr als einem Attribut basieren, erläutert.

4.4.1. Soft Splits

Bei den traditionellen Entscheidungsbäumen werden zwei Eigenschaften besonders oft kritisiert (vgl. [Mur98]): (1) Je weiter ein Knoten von der Wurzel entfernt ist, desto weniger Tupel, auf denen eine weitere Partitionierung beruht, sind an diesem Knoten verfügbar, so dass diese Partitionierungen immer weniger statistische Signifikanz haben (Datenfragmentation). Und (2) können verschiedene Blätter eines Entscheidungsbaumes derselben Klasse angehören, was bei Datensätzen mit vielen unterschiedlichen Merkmalsausprägungen des Class-Labels in unnötig großen Bäumen resultieren kann (viele Klassenüberschneidungen).

Daher haben sich verschiedene Forscher mit der Idee beschäftigt, Soft Splits bei Entscheidungsbäumen einzusetzen. Bei einem Hard Split (dem Gegenteil von einem Soft Split) werden die Tupel an einem Knoten in sich gegenseitig ausschließende Partitionen unterteilt. Bei einem Soft Split wird dagegen jedes Tupel eines Knotens mit einer Wahrscheinlichkeit, mit der es zu den entstehenden Partitionen gehört, versehen. Dadurch wird es einem Tupel ermöglicht, zu mehreren Partitionen zu gehören.

C4.5 [Qui93] setzt beispielsweise eine einfache Version der Soft Splits ein. Die Verwendung von Soft Splits wird beispielsweise in Publikationen zur Mustererkennung (vgl. [SD84] und [WS87]) beschrieben. Jordan und Jacobs (vgl. [JJ94]) beschreiben eine parametrische und hierarchische Klassifizierung mit Hilfe von Soft Splits. Multivariate Entscheidungsbäume, die Soft Splits benutzen, werden von Forouraghi et al. (vgl. [FSP94]) betrachtet. Die Induktion von unscharfen Entscheidungsbäumen (engl. Fuzzy Decision Trees) wird in der Literatur in den Publikationen [Lee92], [YS95], [CL00], [SMV03] und [BBY04] vorgestellt.

4.4.2. Skalierbarkeit

Die traditionellen Algorithmen zur Induktion von Entscheidungsbäumen, wie ID3 und C4.5, wurden so entwickelt, dass sie vor allem für relativ kleine Datensätze gut geeignet sind. Wenn diese Algorithmen jedoch auf größere Datensätze, die beispielsweise bei Scannerkassen in Supermärkten anfallen, angewendet werden, zeigt sich, dass diese nur schlecht skalierbar sind. Der Grund dafür ist, dass bei dem Entwurf dieser traditionellen Algorithmen davon ausgegangen wurde, dass ein gesamter Trainingsdatensatz in den Arbeitsspeicher eines Computers geladen werden kann. Bei den heutigen Data Mining Anwendungen sind jedoch riesige Datensätze, die aus mehreren Millionen Tupeln bestehen, keine Seltenheit. Folglich ist die Skalierbarkeit der traditionellen Algorithmen stark eingeschränkt. Passt ein Trainingsdatensatz nicht vollständig in einen Arbeitsspeicher, so müssen einige Tupel während der laufenden Entscheidungsbauminduktion in den Arbeitsspeicher geladen und aus dem Arbeitsspeicher wieder gelöscht werden, wodurch die Induktion sehr ineffizient werden kann.

In frühen Ansätzen zur Lösung dieses Problems wurde das Sampling als Heuristik (vgl. [HK01]) eingesetzt. Beim Sampling wird nicht der gesamte vorliegende Datensatz verwendet, sondern es werden zufällige Stichproben ausgewählt, auf Basis dieser Stichproben wird dann anschließend ein Entscheidungsbaum konstruiert.

Ein alternativer Ansatz zum Sampling teilt den Originaldatensatz in verschiedene Trainingsdatensätze, die jeweils in den Arbeitsspeicher passen, auf, und konstruiert für jeden einzelnen Trainingsdatensatz einen Entscheidungsbaum. Abschließend werden die resultierenden Entscheidungsbäume zu einem endgültigen Entscheidungsbaum kombiniert.

Das Sampling wird zumindest die Klassifikation von großen Datenmengen ermöglicht, jedoch ist Genauigkeit bei diesem Ansatz schlechter als bei einer Methode, die alle Daten auf einmal klassifizieren würde. Daher wurden neue Verfahren, die die Klassifikation von großen Datenmengen ermöglichen, vorgestellt. Darunter befinden sich SLIQ (vgl. [MAR96]) und SPRINT (vgl. [SAM96]) von Mehta et al. Beide Verfahren bieten Techniken zur Vorsortierung von Daten, die sich in einem permanenten Speicher befinden, an. Und bei beiden Verfahren werden neue Datenstrukturen vorgeschlagen, mit deren Hilfe die Entscheidungsbauminduktion erleichtert wird. SLIQ verwendet Attributlisten, die im permanenten Speicher residieren und beschränkt sich im Arbeitsspeicher auf eine Klassenliste. Für jedes Attribut wird solch eine Attributliste erstellt. Jedes Tupel wird dabei durch einen Zeiger, der das Class-Label des gegebenen Tupels trägt, von einer Attributliste auf einen Eintrag in der Klassenliste repräsentiert. Die Baumkonstruktion geschieht sowohl in der Konstruktionsphase als auch in der Pruningphase durch Änderungen der Einträge in der Klassenliste, die daher im Arbeitsspeicher verbleiben (genauere Hinweise dazu in [MAR96]). Nachteil bei diesem Verfahren ist allerdings, dass die Klassenliste proportional zur Anzahl an Tupel wächst. Sobald die Klassenliste nicht mehr in den Arbeitsspeicher passen sollte, nimmt auch die Performanz dieses Verfahrens ab.

SPRINT wurde mit einer ähnlichen Datenstruktur entworfen, die allerdings einen entscheidenden Vorteil hat (vgl. [HK01]). Und zwar speichert SPRINT die Klassenzugehörigkeit eines Tupels nicht in einer arbeitsspeicherresidenten Klassenliste, sondern in der Attributliste. Wird ein Knoten aufgeteilt, so wird auch die dazugehörige Attributliste entsprechend partitioniert. Dank einer günstigen Vorsortierung kann nach einer Partitionierung die Sortierung der Einträge einer Attributliste beibehalten werden. Also bedarf es nach der Partitionierung eines Knotens keiner Neusortierung. Damit ist SPRINT dazu geeignet, auch Datensätze zu verarbeiten, die so groß sind, dass selbst SLIQ diese nicht mehr effizient verarbeiten kann. Bei der Größe eines Datensatzes sind also kaum noch Grenzen gesetzt. Mehta et al. (vgl. [SAM96]) schlagen daher eine Kombination aus diesen beiden Verfahren vor.

Allerdings bleibt festzustellen (vgl. [Li96]), dass je nach Größe eines vorliegenden Datensatzes entweder SLIQ oder SPRINT vorzuziehen ist. Bei Datensätzen, bei denen eine Klassenliste vollständig in den Arbeitsspeicher passt, ist SLIQ besser geeignet, denn bei SLIQ müssen für eine Partitionierung lediglich Zeiger im Arbeitsspeicher modifiziert werden, wohingegen bei SPRINT Operationen im permanenten Speicher ausgeführt werden müssen, was ineffizienter ist. Wenn allerdings eine Klassenliste nicht vollständig in den Arbeitsspeicher passt, ist wiederum SPRINT vorzuziehen.

Einen sehr viel versprechenden Ansatz bietet auch hier das bereits zuvor erwähnte RainForest Framework von Gehrke et al. (vgl. [GRG98]). Dieses Framework wurde so entworfen, dass der Skalierbarkeitsaspekt bei der Entscheidungsbauminduktion von Splitting- und Pruningkriterien getrennt wird. Dieser Ansatz basiert auf zwei verschiedenen Beobachtungen.

(1) Beinahe alle Verfahren zur Entscheidungsbauminduktion in der Literatur gehen nach demselben top-down Schema vor, bei dem ein Trainingsdatensatz rekursiv anhand eines Splittingkriteriums partitioniert wird.

(2) Für eine erfolgreiche Partitionierung ist es bereits ausreichend, die Klassenverteilung für jeden Attributwert zu kennen.

Mit RainForest wurde eine neue Datenstruktur, eine AVC-Liste (Attribute, Value, und Class-Label) (vgl. [Li96]), eingeführt, die die zweite Beobachtung ausnutzt. Jeder Eintrag in der AVC-Liste beinhaltet einen Attributwert und die Anzahl an Tupel, die derselben Klasse angehören. Diese AVC-Liste stellt somit eine Art Abstraktion der vorliegenden Trainingsdaten dar. Die AVC-Liste lässt sich jedoch erheblich effizienter verarbeiten, als der ursprüngliche Trainingsdatensatz. Zusätzlich passt sich RainForest automatisch an die Größe des zur Verfügung stehenden Arbeitsspeichers an.

Das RainForest Framework wurde so entworfen, dass jedes Verfahren, dass (1) genügt, darin integriert werden kann. Als Input bekommt das eingesetzte Verfahren nicht mehr den ursprünglichen Trainingsdatensatz sondern eine entsprechende AVC-Liste zur Verfügung gestellt.

Wie bereits in Kapitel 4.2.3 angesprochen, kann jedes beliebige Splittingkriterium und auch jedes beliebige Pruningverfahren innerhalb des Frameworks angewendet werden. Nach Angaben der Entwickler (vgl. [GRG98]) ist dabei der entstehende Entscheidungsbaum absolut identisch mit dem Baum, der entstehen würde, wenn der Originalalgorithmus mit ausreichendem Arbeitsspeicher angewendet werden würde. Eine Entscheidungsbauminduktion anhand des RainForest Frameworks ist signifikant schneller als beispielsweise SPRINT (vgl. [HK01]). Für weiterführende Informationen zu diesem Ansatz möchte ich an dieser Stelle auf die Literatur verweisen.

Ein Verfahren namens BOAT (Bootstrapped Optimistic Algorithm for Tree construction) wurde ebenfalls von Gehrke et al. wurde vorgestellt, um das Problem der Skalierbarkeit zu lösen (vgl. [GGR99]). Bei allen bisherigen Verfahren war pro Ebene eines Entscheidungsbaumes ein Datenbank-Scan erforderlich. Mit einem Datenbank-Scan ist in diesem Zusammenhang gemeint, dass von jedem einzelnen Tupel in einer Datenbankrelation dessen Eigenschaften analysiert werden müssen. BOAT wurde so entwickelt, dass es durch ein optimistisches Vorgehen in der Lage ist, mit einem Datenbank-Scan mehrere Ebenen eines Entscheidungsbaumes zu konstruieren. Ein optimistisches Vorgehen bedeutet, dass zunächst ein vorläufiger Entscheidungsbaum anhand einer Untermenge von Daten aus dem Datensatz konstruiert wird. Die restlichen Daten des Datensatzes werden anschließend dazu verwendet, den Entscheidungsbaum zu verbessern. Durch dieses optimistische Vorgehen ist das Verfahren nach Aussage der Autoren bis zu 300% schneller als alle bisherigen Verfahren, wodurch sich auch große Datenmengen schneller verarbeiten lassen (vgl. [GGR99]). Dieser Geschwindigkeitsgewinn ist jedoch nicht mit einem Qualitätsverlust verbunden, denn die Autoren des Verfahrens garantieren dafür, dass der resultierende Entscheidungsbaum identisch ist mit einem Entscheidungsbaum, der mit einem traditionellen Verfahren wie C4.5 konstruiert wird.

Das Verfahren CLOUDS (Classification for Large or Out-of-core Data Sets), das von Alsabti et al. vorgestellt wurde (vgl. [ARS98]), verwendet eine Technik des Sampling, um die Skalierbarkeit der Entscheidungsbauminduktion zu erhöhen. Bei CLOUDS wird ein Splittingkriterium eingesetzt, dass ähnlich zum Gini-Koeffizienten ist, bei dem jedoch ein Schätzer verwendet wird. Zur Berechnung eines Gini-Koeffizienten ist es notwendig, sämtliche Tupel an einem Knoten zu analysieren. Bei der Verwendung eines Schätzers reicht es jedoch aus, nur einige Tupel an einem Knoten zu analysieren und daraus die Eigenschaften der restlichen Tupel abzuschätzen. Dadurch, dass weniger Tupel analysiert werden müssen, kann Rechenzeit und auch Speicherplatz im Arbeitsspeicher gespart werden. Die Autoren zeigen durch experimentelle Ergebnisse, dass deren Verfahren in den meisten Fällen ähnlich gute Ergebnisse liefert, wie bei Verwendung des Gini-Koeffizienten als Splittingkriterium.

Von Agrawal und Jin wurde ein Verfahren namens SPIES (Statistical Pruning of Intervals for Enhanced Scalability) vorgestellt (vgl. [AJ03]). Dieses Verfahren kombiniert die AVC-Listen, die bereits durch das RainForest Framework eingeführt wurden, mit einer Methode zum Sampling als Heuristik für eine noch bessere Skalierbarkeit. Durch die Verwendung einer AVC-Liste ist die Menge an benötigtem Arbeitsspeicher äußerst gering. Weiterhin benötigt das Verfahren keine Vorsortierung der Trainingsdaten, wodurch Rechenzeit eingespart werden kann.

4.4.3. Parallele Verarbeitung

In der Vergangenheit wurde eine Menge Bemühungen gemacht, Entscheidungsbauminduktionsalgorithmen zu entwerfen, die sich zur parallelen Ausführung auf mehreren Rechnern bzw. Prozessoren eignen. Viele Bemühungen gingen in die Richtung, bestehende Algorithmen so zu erweitern, dass sie verteilten Arbeitsspeicher mehrerer Computer verwenden können (vgl. [AJY04]).

In der Literatur existieren beispielsweise knotenbasierte und attributbasierte Ansätze zur Zerlegung des Gesamtproblems der Entscheidungsbauminduktion (vgl. [HSK98]). Bei der Knotenbasierten Zerlegung, bekommt jeder Prozessor, der an einer parallelen Verarbeitung beteiligt ist, einen bestimmte Ebene von Knoten zugeteilt (horizontale Schnitte durch den Entscheidungsbaum), die dieser Prozessor weiter partitionieren soll. Es konnte jedoch nachgewiesen werden, dass eine knotenbasierte Zerlegung alleine einige Probleme mit sich bringt. Ein Problem ist, dass anfangs nur wenige Prozessoren genutzt werden, aufgrund der geringern Anzahl an Baumknoten im Wurzelbereich. Die attributbasierte Zerlegung wird benutzt, um dieses Problem zu lösen. Bei der attributbasierten Verarbeitung, wird jedem Prozessor ein bestimmtes Attribut der Trainingsdaten zuteilt (vertikale Schnitte durch den Entscheidungsbaum), für die dieser Prozessor eine Partitionierung berechnen soll. Pearson präsentiert einen Ansatz (vgl. [Pea94]), der eine knotenbasierte und attributbasierte Zerlegung der Entscheidungsbauminduktion miteinander kombiniert.

Kufrin (vgl. [Kuf97]) führte einen Ansatz, Parallel Decision Trees (PDT), ein, der einen Prozessor als „Host“ und die übrigen Prozessoren als „Worker“ bestimmt. Der Host-Prozessor selbst übernimmt keine Berechnung für Tupel, sondern übernimmt die Koordination. Basierend auf den Berechnungen der anderen Prozessoren bestimmt dieser, wie ein Knoten partitioniert wird, und teilt diese Entscheidung den übrigen Prozessoren mit. Bei diesem Ansatz kann allerdings wiederum ein Engpass entstehen, da vom und zum Hostprozessor ein erhöhter Kommunikationsaufwand besteht.

Für den Algorithmus SPRINT (vgl. [SAM96]) wurde eine Variante zur parallelen Verarbeitung eingeführt. Bei dieser Variante wird die Attributliste, die SPRINT vorhält, gleichmäßig zwischen allen zur Verfügung stehenden Prozessoren zur weiteren Verarbeitung aufgeteilt. Für dieses Verteilen wird ein all-to-all Broadcast verwendet, was die Effizienz des Verfahrens negativ beeinträchtigt. Als Alternative wurde der Algorithmus ScalParC (vgl. [JKK98]) vorgeschlagen, der ebenfalls auf SPRINT basiert und eine parallele Verarbeitung ermöglicht. Um die Splittingphase von SPRINT effizienter zu implementieren, verwendet ScalParC anstelle einer Attributliste eine verteilte Hashtabelle. Diese Hashtabelle wird unter den Prozessoren zur Verarbeitung aufgeteilt und mit Hilfe von effizienteren Kommunikationstechniken als bei SPRINT aktualisiert.

Von Agrawal und Jin wurde im Jahre 2003 (vgl. [AJ03]) ein Verfahren namens SPIES vorgestellt. Bei dem Entwurf dieses Verfahrens, wurden die verwendeten Datenstrukturen bereits für eine parallele Verarbeitung ausgelegt.

Agrawal et al. (vgl. [AJY04]) haben im Jahre 2004 das Design des RainForest Frameworks noch einmal so überarbeitet, dass eine parallele Ausführung der Entscheidungsbauminduktion ermöglicht werden kann. Andere Autoren haben diverse andere Verfahren ebenfalls so modifiziert (vgl. [HB04]), dass sie parallelisierbar sind, beispielsweise SLIQ und SPRINT.

4.4.4. Multiple Bäume

Ein bekanntes Problem bei Entscheidungsbäumen ist deren Varianz, vorallem wenn der Trainingsdatensatz klein ist, das Class-Label jedoch viele unterschiedliche Ausprägungen hat (vgl. [Mur98], [DK95]). Varianz kann unter anderem dann entstehen, wenn ein Datensatz willkürlich in Trainingsdaten und Pruningdaten aufgeteilt wurde, oder wenn die Cross-Validation-Methode angewandt wurde. Mehrere Autoren haben daher vorgeschlagen, statt einem einzigen Entscheidungsbaum, mehrere Bäume zu verwenden, um das Problem der Varianz zu lösen (vgl. [KC90], [Shl90], [Shl92], [Bun92], [HKS93] und [Bre94]).

Bei diesem Ansatz werden aus demselben Datensatz mehrere Bäume (multiple Bäume oder engl. Decision Forest, vgl. [CH00]) erzeugt, und diese Bäume werden anschließend zu einem endgültigen Entscheidungsbaum kombiniert (vgl. [Mur98]). Dieses kombinieren der Bäume kann beispielsweise durch eine simple Voting-Methode vorgenommen werden (vgl. [HKS93]), oder aber auch durch diverse statistische Methoden (vgl. [Shl90]). Ali und Pazzani (vgl. [AP95]) haben die die Fehlerhäufigkeiten von Verfahren, die traditionelle Entscheidungsbäume verwenden, mit den Fehlerhäufigkeiten von Verfahren, die multiple Bäume verwenden, miteinander verglichen.

Die Technik des Bagging (Boostrap AGGregratING) beispielsweise wurde von Breiman vorgestellt (vgl. [Bre94]). Ziel dieser Technik ist es, die Zuverlässigkeit und die Genauigkeit von Entscheidungsbäumen zu verbessern. Dazu werden aus einem Trainingsdatensatz D, der aus N Tupeln besteht, L neue TrainingsdatensätzeAbbildung in dieser Leseprobe nicht enthalten, ebenfalls aus N Tupeln bestehend, generiert. Das Generieren läuft dabei in Form von Ziehen mit Zurücklegen statt. Es ist demnach sehr wahrscheinlich ist, dass ein Tupel aus D in jedem Abbildung in dieser Leseprobe nicht enthalten enthalten ist. Anschließend wird für jedes Abbildung in dieser Leseprobe nicht enthalten jeweils ein Entscheidungsbaum konstruiert. Die resultierenden L Entscheidungsbäume können danach per Voting zu einem endgültigen Entscheidungsbaum kombiniert werden. Das Voting läuft dabei so ab, das an jedem Knoten des endgültigen Entscheidungsbaumes das Attribut als Testattribut verwendet wird, dass von der Mehrheit der L Entscheidungsbäume verwendet wird (vgl. [MO97]).

Eine Alternative zu dem Einsatz multipler Entscheidungsbäume, ist die Verwendung eines hybriden Verfahrens, bei dem mehrere kleine Bäume als Teil eines gesamten Entscheidungsbaumes konstruiert werden. Brodley (vgl. [Bro94]) beschreibt solch ein System, das automatisch den am besten geeigneten unter verschiedenen Entscheidungsbäumen wählt.

4.4.5. Alternativen zur top-down Strategie

Die meisten Induktionsverfahren gehen nach einer gierigen Art und Weise vor: Bäume werden durch Partitionierung von oben nach unten (top-down) Knoten für Knoten erzeugt. Verschiedene Autoren (vgl. [GG74], [RR93]) zeigten auf, dass dieses Vorgehen in bestimmten Situationen zu unpassenden Entscheidungsbäumen führt. Moret (vgl. [Mor82], [Mur98]) stellt eine der ersten Ansätze vor, die mit Hilfe dynamischer Programmierung und einer Branch-and-Bound Technik optimierte Entscheidungsbäume generiert.

Seither haben viele verschiedene Autoren dieses Problem betrachtet (vgl. [Mur98]). Partielle oder vollständige Look-Ahead-Strategien wurden beispielsweise im Umfeld der Statistik (vgl. [Fie77], [Cho91] und [Eld95]) sowie in der Mustererkennung (vgl. [HVM82]), für Bayssche Klassenwahrscheinlichkeitsbäume (vgl. [Bun92]), für Neuronale Bäume (vgl. [AZN94]) und im Machine Learning (vgl. [Nor89], [RR93], [MS95]) erörtert. Die meisten dieser Studien kommen jedoch zu dem Ergebnis, dass eine rechenaufwendige Look-Ahead-Strategie keine erheblichen Verbesserungen gegenüber der traditionellen top-down Strategie bringt (vgl. [Mur98]). Murthy und Salzberg (vgl. [MS95]) demonstrieren dass eine One-Level-Look-Ahead-Strategie, die nur eine Ebene zurückschaut, nicht dazu beträgt, dass Bäume mit einer erheblich besseren Qualität generiert werden. Diese Strategie kann sogar zu einer Verschlechterung der Qualität eines Baumes führen (vgl. [Nau83]).

Die Konstruktion von optimalen oder beinahe optimalen Entscheidungsbäumen durch eine Two-Level-Look-Ahead-Strategie wurde ebenfalls durch verschiedene Autoren untersucht (vgl. [Mur98]). In der ersten Ebene wird dabei eine Partitionierung durch ein gieriges (top-down) Verfahren erzeugt. In der zweiten Ebene wird der Baum dann so verfeinert, dass er möglichst optimal ist. Derartige Techniken wurden beispielsweise durch dynamische Programmierung (vgl. [MM73]), Fuzzy-Logik-Suche (vgl. [WS87]) und multi-lineare Programmierung (vgl. [Ben94]) vorgestellt. Diese Strategie, dass zuerst durch ein gieriges Verfahren ein Entscheidungsbaum erzeugt wird, der anschließend verfeinert wird, kann mit der Suche durch den Raum aller möglichen Entscheidungsbäume verglichen werden. Um lokale Minima in diesem Suchraum zu vermeiden, wurden von einigen Autoren Techniken wie zufälliges Suchen (z.B. durch genetische Algorithmen vgl. [Koz91] oder Simulated Annealing vgl. [BD93], [LK93]) verwendet. Sun et al. haben dagegen eine Technik der sequentiellen Fehlerdiagnose (vgl. [SQC95]) vorgeschlagen. Kroger (vgl. [Kro96]) diskutiert zahlreiche Strategien, die nötig sind, um optimale Entscheidungsbäume zu erzeugen.

4.4.6. Inkrementelle Entscheidungsbauminduktion

Die meisten Algorithmen zur Entscheidungsbauminduktion sind so entworfen worden, dass sie nicht mit veränderlichen Datensätzen umgehen können. Es kann jedoch beispielsweise passieren, dass sich der Trainingsdatensatz während oder nach der Bauminduktion verändert. Bei den traditionellen Algorithmen muss in diesem Fall der gesamte Entscheidungsbaum neu generiert werden. Beispielsweise treffen bei Kreditkartengesellschaften wie Visa oder Mastercard ständig neue Transaktionen ein (vgl. [GRG99]). Bei einem entscheidungsbaumbasierten System zur Aufdeckung von Kreditkartenbetrug ist es entscheidend, dass dieses System auch die aller neuesten Transaktionen berücksichtigen kann. Eine Möglichkeit wäre es also z.B. in jeder Nacht den Entscheidungsbaum zu aktualisieren.

Bei der inkrementellen Entscheidungsbauminduktion, mit der sich verschiedene Autoren in der Vergangenheit beschäftigt haben (vgl. [Mur98], [KP00], [AR02]), wird dieses Problem auf andere Weise gelöst. Bei diesem Ansatz werden Änderungen im Trainingsdatensatz in den entsprechenden Entscheidungsbaum nachträglich eingearbeitet, es wird also ein Update an dem Entscheidungsbaum vorgenommen.

Friedman’s [Fri77] beschreibt in seiner Methode zur Induktion von binären Entscheidungsbäumen beispielsweise die Verwendung von anpassungsfähigen Splits (engl. adaptive splits). Ein sehr einfaches Beispiel für ein anpassungsfähiges Split ist eine Partitionierung, die auf dem Mittelwerte von Attributwerten beruht).

Utgoff et al. schlugen in unterschiedlichen Publikationen inkrementelle Induktionsmethoden sowohl für univariate (vgl. [Utg89], [Utg94], [UBC97]) als auch für multivariate (vgl. [UB90]) Entscheidungsbäume vor, woraus die Algorithmen ID4, ID5, ID5R sowie ITI als Erweiterungen des ID3 von Quinlan hervorgingen. Crawford (vgl. [Cra89]) argumentierte dagegen, dass Ansätze, die nach einer Änderung in dem Trainingsdatensatz immer wieder den Entscheidungsbaum entsprechend anpassen, aufgrund dieser Umstrukturierungen sehr ineffizient sein können. Der Grund dafür ist, dass das „beste“ Split an einem Knoten großen Schwankungen unterliegt, auch wenn die Änderungen an den Tupeln eines Knotens nur geringfügig sind. Crawford verwendet in seiner inkrementellen Variante des CART-Algorithmus daher einen Signifikanz-Schwellwert. Erst wenn dieser Schwellwert durch eine Änderung in den Tupeln eines Knotens überschritten wird, wird die Partitionierung an dem entsprechenden Knoten angeglichen.

Das von Gehrke et al. (vgl. [GRG99]) vorgestellte Verfahren BOAT wurde ebenfalls so entworfen, dass es in der Lage ist, per inkrementeller Induktion dynamische Änderungen im Trainingsdatensatz in den erzeugten Entscheidungsbaum einzuarbeiten.

4.4.7. Splits basierend auf mehr als einem Attribut

Die traditionellen Algorithmen zur Entscheidungsbauminduktion erzeugen, wie bereits in Kapitel 2.3 erwähnt, so genannte univariaten Entscheidungsbäume. Bei univariaten Entscheidungsbäumen wird an jedem Knoten nur auf ein Attribut getestet.

Es gibt jedoch die Möglichkeit, an jedem Knoten nicht nur auf ein Attribut zu testen, sondern auf eine Linearkombination von mehreren Attributen. Dieses Vorgehen hat den Vorteil, dass das entstehende Modell besser an die Gegebenheiten des vorliegenden Datensatzes angepasst ist, als bei univariaten Bäumen, allerdings ist dieses Verfahren auch komplizierter. Algorithmen wie CART (Classification And Regression Tree) (vgl. [BFOS84]) oder OC1 (Oblique Classifier 1) (vgl. [Mur95]) sowie CRUISE (Classificaition Rule with Unbiased Interaction Selection and Estimation) von Kim und Loh (vgl. [KL01]) erzeugen derartige multivariat-lineare Entscheidungsbäume.

Nicht-lineare Entscheidungsbäume, sind Bäume, an deren Knoten auch Nicht-Linearkombinationen von Attributen getestet werden können. Der Algorithmus NDT (Non-linear Decision Trees) von Ittner und Schlosser (vgl. [IS96]) beispielsweise erzeugt nicht-lineare Entscheidungsbäume.

5. Entscheidungsbäume in der Praxis

Die Diskussion in dieser Arbeit hat sich bis hier her auf Techniken zur Entscheidungsbaumkonstruktion konzentriert. All dieses ist jedoch nutzlos, solange diese Techniken nicht in der Praxis angewendet werden und dort einige alternative Techniken übertreffen können. In diesem Kapitel sollen daher zwei weitere Aspekte angesprochen werden: Um zu zeigen, dass die Verwendung von Entscheidungsbäumen in der Praxis eine sehr nützliche Technik ist, werden Beispiele von unterschiedlichen praktischen Anwendungen aufgeführt. Anschließend sollen existierende Softwarepakete, die Entscheidungsbäume verwenden, kurz vorgestellt werden, um einen kleinen Ausblick zu liefern.

5.1. Anwendungsfelder

Nachdem in den vorigen Kapiteln die Entwicklung von Ansätzen zur Entscheidungsbaumkonstruktion dargestellt wurde, sollen in diesem Kapitel einige wenige Anwendungsgebiete beispielhaft vorgestellt werden, bei denen Entscheidungsbäume zum Einsatz kommen (vgl. [Mur98]). Das Ziel dieses Kapitels ist es, dem Leser eine Vorstellung davon zu verleihen, wie vielseitig und nützlich Entscheidungsbäume in den unterschiedlichsten Problemfeldern eingesetzt werden können. Die Anwendungsgebiete folgen in alphabetischer Ordnung:

- Landwirtschaft: Zahlreiche Applikationen für das Machine Learning Methoden einschließlich Entscheidungsbäumen in Landwirtschaft und Gartenbau.
- Astronomie: Die Astronomie ist ein Gebiet, in dem viel nach Techniken zur automatisierten Klassifikation geforscht wurde. Entscheidungsbäume werden z.B. benutzt um Störungen in den Satellitenbildern des Hubble Teleskops herauszufiltern.
- Finanzanalyse: Beurteilung der Attraktivität von unterschiedlichen Anlageformen.
- Bildbearbeitung: Für die Interpretation von digitalen Bildern in der Radiologie, für die Erkennung von 3-D Objekten, oder für Freiland-Bild-Segmentierung.
- Sprachverarbeitung: Für die Klassifizierung von medizinischen Texten, oder zur Erstellung eines statistischen Parsers aus einer Menge von geparsten Sätzen.
- Produktionswirtschaft: Für die Halbleiterherstellung, zur Prduktivitätssteigerung, zur Beschleunigung des Rotationstiefdrucks, und vieles mehr.
- Medizin: Die medizinische Forschung war lange Zeit ein wichtiges Anwendungsgebiet für Entscheidungsbäume, z.B. in der Kardioligie, Psychatrie, Gastroenterologie oder zur Analyse des plötzlichen Kindstod Syndroms (SID).
- Molekularbiologie: Initiativen wie das Menschliche Genome Projekt und die GenBank Datenbank bieten faszinierende Möglichkeiten für das Machine Learning.
- Physik: Für die Erkennung von physikalischen Partikeln.
- Stromkraftwerke: Zur Abschätzung der Sicherzeit und Stabilität von Kraftwerken.
- Softwareentwicklung: Um den Entwicklungsaufwand für ein gegebenes Softwaremodul abzuschätzen.

5.2. Angebotene Softwarelösungen

Heutzutage existiert eine Vielzahl von frei verfügbaren Codeschnipseln (oftmals zu Forschungszwecken erstellt) und kommerziellen Produkten, deren Zweck es ist, Entscheidungsbäume aus gegebenen Datensätzen zu konstruieren. Zusätzlich gibt es einige Data-Mining-Tool Suites, die ebenfalls Entscheidungsbauminduktionsalgorithmen beinhalten. Die verfügbaren Softwareprodukte unterscheiden sich vor allem darin, welcher Algorithmus implementiert wurde, wie viel Sorgfalt auf Hilfsfunktionen wie z.B. Visualisierung gelegt wurde, welche Datenformate unterstützt werden und vor allem in der Geschwindigkeit.

Ein objektiver Vergleich der angebotenen Software in Bezug auf Funktionalität, Effizienz und Benutzerfreundlichkeit, Visualisierungsmöglichkeiten, Datanbankschnittstellen und Preis wäre sehr interessant, würde jedoch den Rahmen dieser Studienarbeit überscheiten. Daher folgt lediglich eine Auflistung einiger existierender Softwarelösungen ohne Anspruch auf Vollständigkeit (vgl. [Mur98]):

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 5.1: Übersicht über Softwarelösungen, die Entscheidungsbäume zur Klassifikation einsetzen

6. Fazit

Im Rahmen dieser Arbeit wurde zunächst auf die Grundlagen der Entscheidungsbäume eingegangen. Dazu wurde eine thematische Einordnung im Data Mining sowie eine Einführung in die Klassifikation und eine Begriffsbestimmung geliefert. Daran anschließend wurde das Preprocessing, bestehend aus der Datenbereinigung, der Relevanzanalyse und der Datentransformation, erläutert, da das Preprocessing eine notwenige Voraussetzung für eine erfolgreiche Klassifikation ist.

Im Verlauf dieser Arbeit wurden Algorithmen zur Entscheidungsbauminduktion besprochen. Dazu wurde zunächst auf die Ursprünge dieser Technik eingegangen, die auf dem Concept Learning System beruhen. Weiterhin wurden verschiedene Splittingkriterien und verschiedene Pruningkriterien erörtert. Bei den Splittingkriterien gibt es vorallem Ansätze, die auf Informationstheorie oder auf Distanzmaße basieren, sowie einige hybride Ansätze. Bei den Pruningkriterien gibt es die Möglichkeiten des Preprunings sowie des Postprunings sowie einer Kombination aus diesen beiden Möglichkeiten. Gängige Meinung in der Literatur ist vorallem, dass das Pruning für die Qualiät der Klassifikation wesentlich entscheidender ist, als die Wahl eines geeigneten Splittingkriteriums. Weiterhin ist die gängige Meinung, dass es sowohl beim Splitting als auch beim Pruning kein universelles Kriterium gibt, und dass die Wahl eines geeigneten Kriteriums vorallem von den Eigenschaften des zugrundeliegenden Datensatzes abhängt.

Bei vielen Algorithmen zur Entscheidungsbauminduktion wurden ganz spezielle Splitting- und Pruningkriterien verwendet, meist je nach Präferenz des Autors. Somit ist die Wahl eines geeigneten Algorithmus zur Entscheidungsbauminduktion vorallem abhängig von Splitting- und Pruningkriterien. C4.5 verwendet beispielsweise die Gain Ratio als Splittingkriterium und eine Technik des Postprunings als Pruningkriterium. Erst mit der Einführung des RainForest Frameworks von Gehrke et al. im Jahre 1998 wurde für die soeben angesprochene Problematik eine Abhilfe geschaffen. Dieses Framework wurde so konzipiert, dass jedes beliebige Splitting- und Pruningkriterium innerhalb des Frameworks verwendet werden kann. Somit erlaubt dieser Ansatz dem Anwender die Freiheit das Kriterium, das er für seine Anwendung als am besten geeignet hält, selbst auszuwählen.

Im weiteren Verlauf dieser Arbeit wurden viele unterschiedliche Algorithmen zur Entscheidungsbauminduktion vorgestellt. Bei vielen Algorithmen handelt es sich dabei um Spezialisierungen oder Erweiterungen des ursprünglichen Algorithmus ID3 bzw. C4.5 von Quinlan. So wurden z.B. Soft Splits, Skalierbarkeitsaspekte, Möglichkeiten zur Parallelen Verarbeitung, Verwendung von multiplen Bäumen, sowie Alternativen zur top-down Strategie , Inkrementelle Entscheidungsbauminduktion und Splits, die auf mehr als einem Attribut basieren, angesprochen. Bei all diesen Ansätzen handelt es jedoch um Spezialisierungen auf besondere Gegebenheiten des vorliegenden Datensatzes. Die Wahl eines geeigneten Algorithmus zur Entscheidungsbauminduktion hängt also wiederum insbesondere von den Eigenschaften des vorliegenden Datensatzes ab.

Um dem Leser einen Ausblick zu verschaffen und zugleich die Relevanz von Entscheidungsbäumen in der Praxis zu verdeutlichen wurden zum Abschluß dieser Arbeit einige Anwendungsfelder für den Einsatz von Entscheidungsbäumen sowie angebotene Softwarelösungen, die Entscheidungsbäume einsetzen, vorgestellt.

Die nachfolgende Tabelle 6.1 liefert einen zusammenfassenden Überblick über die in dieser Arbeit aufgeführten Algorithmen sowie deren verwendete Splitting- und Pruningkriterien und deren Besonderheiten.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 6.1: Übersicht der Algorithmen zur Entscheidungsbaumerzeugung

Literaturverzeichnis

[AJ03] G. Agrawal, R. Jin. Communication and memory efficient parallel decision tree construction. In Proceedings of Third SIAM Conference on Data Mining (May 2003).

[AJY04] G. Agrawal, R. Jin, G. Yang. Shared memory parallelization of data mining algorithms: techniques, programming interface, and performance. IEEE Transactions on knowledge and data engineering, 2004, Volume 16, No. 10.

[AP95] K.M. Ali, M.J. Pazzani. On the link between error correlation and error reduction in decision tree ensembles. Technical Report ICS-TR-95-38, University of California, Irvine, Department of Information and Computer Science, September 1995.

[AR02] F. d’Alche´-Buc, L. Ralaivola. Incremental Learning Algorithms for Classification and Regression: local strategies. AIP Conference Proceedings; 2002, Vol. 627 Issue 1, pages 320-330.

[ARS98] K. Alsabti, S. Ranka, V. Singh. CLOUDS: A decision tree classifier for large datasets. In Knowledge Discovery and Data Mining, 1998, pages 2-8.

[AZN94] F. Alchfie-Buc, D. Zwierski, J.-P. Nadal. Trio learning: A new strategy for building hybrid neural trees. International Journal of Neural Systems; 1994, Volume 5, Issue 4, pages 259-274.

[BBY04] M.J. Beynon, K.L. Buchanan, T. Yu-Cheng. The application of a fuzzy-rule-based system in an exposition of the antecedents of sedge warbler song flight. Expert Systems; 2004, Volume 21, Issue 1, pages 1-11.

[BD93] R.S. Bucy, R.S. Diesposti. Decision tree design by simulated annealing. Mathematical Modieling and Numerical Analysis; 1993, Volume 27, Issue 5, pages 515-534.

[Bel59] W.A. Belsen. Matching and Prediction on the Principle of Biological Classification. Applied Statistics; 1959, Volume 8, pages 65-75.

[Ben78] M. Ben-Bassat. Myopic policies in sequential classification. IEEE Trans. on Computing; 1978, Volume 27, Issue 2, pages 170-174.

[Ben94] K.P. Bennett. Global tree optimization: A non-greedy decision tree algorithm. In Proceedings of Interface, the 26th Symposium on the Interface, Research Triangle, North Carolina, 1994.

[BFOS84] L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. Belmont, CA. Wadsworth, 1984.

[BJ76] F.A. Baker, A.K. Jain. On feature ordering in practice and some finite sample effects. Proceedings of the third International Joint Conference on Pattern Recognition; 1976, pages 45-49.

[Bre94] L. Breiman. Bagging predictors. Technical report, Department of Statistics, Univ. of California, Berkeley, CA, 1994.

[Bro94] C.E. Brodley. Recursive Automatic Algorithm Selection for Inductive Learning. PhD thesis, Univ. of Massachusetts, Amherst, MA, 1994.

[Bun92] W. Buntine. Learning classification trees. Statistics and Computing; 1992, Volume 2, pages 63-73.

[CH00] H. Chen, T. K. Ho. Evaluation of decision forests on text categorization. Proc. 7th SPIE Conference on Document Recognition and Retrieval (2000), pages 191-199.

[Cho91] P.A. Chou. Optimal partitioning for classification and regression trees. IEEE Transactions on Pattern Analysis and Machine Intelligence; 1991, Volume 13, Issue 4, pages 340-354.

[CL00] S.-M. Chen, S.-Y. Lin. A new method for constructing fuzzy decision trees and generating fuzzy classification rules from training examples. Cybernetics & Systems; 2000, Vol. 31 Issue 7, pages 763-786.

[CN89] P. Clark, T. Niblett. The CN2 Induction Algorithm. Machine Learning 3, 1989, pages 261-283.

[Coh93] W.W. Cohen. Efficient pruning methods for separate-and-conquer rule learning systems. Proceedings of the Thirteenth Int. Joint Conference on Artificial Intelligence; 1993, Volume 2, pages 988-994. Editor: Ruzena Bajcsy.

[Cra89] S.L. Crawford. Extensions to the CART algorithm. Int. J. of Man-Machine Studies; 1989, Volume 31, Issue 2, pages 197-217.

[DD04] R. K. DeLisle, S. L. Dixon. Induction of decision trees via evolutionary programming. Journal of Chemical Information and Computer Sciences (now called Journal of Chemical Information and Modeling); 2004, Volume 44, Number 3, pages 862 – 870.

[DK95] T.G. Dietterich, E.B. Kong. Machine learning bias, statistical bias and statistical variance of decision tree algorithms. Proceedings of the Twelfth International Conference in Machine Learning; 1995.

[Eld95] J.F. Elder. Heuristic search for model structure. Preliminary Papers of the Fifth Int. Workshop on Artificial Intelligence and Statistics; 1995, pages 199-210.

[EMS95] F. Esposito, D. Malerba, G. Semeraro. A further study of pruning methods in decision tree induction. Preliminary Papers of the Fifth Int. Workshop on Artificial Intelligente and Statistics; 1995, pages 211-218.

[FI93] U. M. Fayyad, K. B. Irani. Multi-interval discretization of continuous valued attributes for classification learning. Proceedings of the 13th International Conference on Artificial Intelligence; 1993, Vol. 2, pages 1022-1027.

[Fie77] A. Fielding. Binary segmentation: the automatic interaction detector and related techniques for exploring data structure. In O'Muircheartaigh and Payne. The analysis of survey data, 1977, volume I. John Wiley & Sons, Chichester, UK.

[FKS95] T. K. Fulton, S. Kasif, S. Salzberg. Efficient algorithms for finding multi-way splits for decision trees. In Proceedings of the Twelfth International Conference on Machine Learning; 1995, pages 244-251.

[Fri77] J. H. Friedman. A recursive partitioning decision rule for nonparametric classifiers. IEEE Transactions on Computers; 1977, Volume 26, pages 404-408.

[FSP94] F. Forouraghi, L.W. Schmerr, G.M. Prabhu. Induction of multivariate regression trees for design optimization. Proceedings of the Twelfth National Conference on Artificial Intelligence; 1994, Volume 1, pages 607-612.

[GC72] M.A. Gleser, M.F. Collen. Towards automated medical decision. Computer and Biomedical Research; 1972; Volume 5, Issue 2, pages 180-189.

[GG74] M.R. Garey and R.L. Graham. Performance bounds on the splitting algorithm for binary testing. Acta Informatica; 1974, Volume 3, Fasc. 4, pages 347-355.

[GGR99] J. Gehrke, V. Ganti, R. Ramakrishnan, W.-Y. Loh. BOAT - optimistic decision tree construction. In Proc. of ACM-SIGMOD International Conference on Management of Data (1999), Philadelphia, pages 169-180.

[Gil72] M. W. Gillo. MAID: A Honeywell 600 program for an automatised survey analysis. Behavioral Science, 17:251 Nr. 252, 1972.

[GRG98] J. Gehrke, R. Ramakrishnan, V. Ganti. Rainforest - a framework for fast decision tree construction of large datasets. Data Mining and Knowledge Discovery, 1998, 4(2/3), pages 127-162.

[Han] D. Hand et al.: Principles of Data Mining (chapter 10).

[Han97] D. J. Hand.: Construction and Assessment of Classification Rules. John Wiley & Sons, Chichester, England, 1997.

[Har84] A. Hart. Experience in the use of an inductive system in knowledge engineering. Research and Developments in Expert Systems, M. Bramer., Ed. Cambridge, U.K.: Cambridge Univ. Press, 1984.

[HB04] J. Hofer, P. Brezany. Distributed decision tree induction within the grid data mining framework GridMiner-core. Master's thesis, Fakultät für Wirtschaftswissenschaften und Informatik, Universität Wien, February 2004.

[HK01] J. Han, M. Kamber. Data Mining: Concepts and Techniques. Morgan Kaufmann, San Francisco, CA, pages 279-296, 2001.

[HKS93] D. Heath, S. Kasif, S. Salzberg. k-DT: A multi-tree learning method. Proceedings of the Second International Workshop on Multistrategy Learning; 1993, pages 138-149.

[HMS66] E.B. Hunt, J. Martin, P.T. Stone. Experiments in Induction. New York: Academic Press, 1966.

[HSK98] E. Han, A. Srivastava, V. Kumar, V. Singh. Parallel formulations of decision-tree classification Algorithms. Kluwer Academic Publishers, Boston, 1998.

[HVM82] C.R.P. Hartmann, P.K. Varshney, Ki.G. Mehrotra, C.L. Gerberich. Application of information theory to the construction of efficient decision trees. IEEE Transactions on Information Theory; 1982, Volume 28, Issue 4, pages 565-577.

[IS96] A. Ittner, M. Schlosser. Non-Linear Decision Trees - NDT. Proceedings of the 13th International Conference on Machine Learning (ICML'96).

[JJ94] M.I. Jordan, R.A. Jacobs. Hierarchical mixtures of experts and the EM algorithm. Neural Computation; 1994, Volume 6, pages 181-214.

[JKK98] M. V. Joshi, G. Karypis, V. Kumar. Scalparc: A new scalable and efficient parallel classification algorithm for mining large datasets. Proceedings International Parallel Processing Symp (1998).

[Kas80] G.V. Kass. An exploratory technique for investigating large quantities of categorical data. Applied Statistics; 1980, 29, pages 119-127.

[KC90] S.W. Kwok, C. Carter. Multiple decision trees. Uncertainty in Artificial Intelligence; 1990, Volume 4, pages 327-335.

[Ker92] R. Kerber. Chimerge: Discretization of numeric attributes. Proceedings of the Tenth National Conference on Artificial Intelligence; 1992, pages 123-128. AAAI Press/MIT Press.

[KK94] H. Kim, G. J. Koehler. An investigation on the conditions of pruning an induced decision tree. European J. of Operational Research; 1994, Volume 77, Issue 1, page 82.

[KL01] H. Kim, W.-Y. Loh. Classification trees with unbiased multiway splits. Journal of the American Statistical Association; 2001, Vol. 96, pages 589-604.

[Koh95] R. Kohavi. A study of cross-validation and bootstrap for accuracy estimation and model selection. Proceedings of the Fourteenth Int. Joint Conference on Artificial Intelligence; pages 1137-1143. Editor: Chris Mellish.

[Koz91] J. R. Koza. Concept formation and decision tree induction using the genetic programming paradigm. In H. P. Schwefel and R. Männer (editors), Parallel Problem Solving from Nature. Proceedings of 1st Workshop; 1991, Volume 496, pages 124-128.

[Kro96] M. Kroger. Optimization of classification trees: strategy and algorithm improvement. Computer Physics Communications; 1996, Volume 99, Issue 1, pages 81-93.

[KP00] D. Kalles, A. Papagelis. Stable decision trees: using local anarchy for efficient incremental learning. International Journal of Artificial Intelligence Tools; 2000, Vol. 9 Issue 1, pages 79-96.

[Kuf97] R. Kufrin. Decision trees on parallel processors. In J. Geller, H. Kitano, C.B. Suttner, editors. Parallel processing for Artificial Intelligence 3. Elsevier Science, 1997.

[Lee92] S.-W. Lee. Noisy Hangul character recognition with fuzzy tree classifier. Proceedings of SPIE. Conference location: San Jose, CA. 10th-12th February, 1992. Volume title: Machine vision applications in character recognition and industrial inspection; 1992, pages 127-136.

[LF83] Y.K. Lin , K.S. Fu. Automatic classification of cervical cells using a binary tree classifier. Pattern Recognition; 1983, Volume 16, No. 1, pages 69-80.

[Li96] J. Li. Constructing classification trees with exception annotations for large datasets. Master's thesis, Dalian University of Science and Technology, China, 1996. Internet resource, accessed 20.07.2005 at http://fas.sfu.ca/pub/cs/theses/1999/JinLiMSc.ps.gz.

[LK93] J.F. Lutsko, B. Kuijpers. Simulated annealing in the construction of near-optimal decision trees. Preliminary Papers of the Fourth International Workshop on Artificial Intelligence and Statistics; 1993.

[LLS97] T.-S. Lim, W.-Y. Loh, Y.-S. Shih. An empirical comparison of decision trees and other classification methods. Technical Report 979, Department of Statistics, University of Wisconsin, Madison, June 1997.

[LS97] W.-Y. Loh, Y.-S. Shih. Split selection methods for classification trees. Statistica Sinica; 1997, Vol. 7, pages 815-840.

[Man91] L. de Mantaras. Technical note: A distance-basedattribute selection measure for decision tree induction. Machine Learning; 1991, Volume 6, Issue 1, pages 81-92.

[MAR96] M. Mehta, R. Agrawal, J. Rissanen. SLIQ: A fast scalable classifier for data mining. In Proceedings of International Conference on Extending Database Technology; 1996, pages 18-32.

[Mer93] T. Van de Merckt. Decision trees in numerical attribute spaces. In Proceedings of the 13th IJCAI; 1993. Chambery, France. REFERENCES 195, pages 1016-1021.

[Min89] J. Mingers. An empirical comparison of selection measures for decision-tree induction. Machine Learning; 1989, Volume 3, pages 319–342.

[MM73] J.N. Morgan, R. C. Messenger. THAID: A sequential search program for the analysis of nominal scale dependent variables. Technical report, Institute for Social Research, University of Michigan, Ann Arbor, 1973.

[MM73] W.S. Meisel, D.A. Michalopoulos. A partitioning algorithm with application in pattern classification and the optimization of decision trees. IEEE Transactions on Computation; 1973, Volume 22, Issue 1, pages 93-103.

[MO97] R. Maclin, D. Opitz. An empirical evaluation of bagging & boosting. The fourteenth National Conference on Artificial Learning; 1997.

[Mor82] B.M.E. Moret. Decision trees and diagrams. Computing Surveys; 1982, Volume 14, Issue 4, pages 593-623.

[MRA95] M. Mehta, J. Rissanen, R. Agrawal. MDL-based decision tree pruning. In Proceedings of the First International Conference on Knowledge Discovery and Data Mining (KDD'95); 1995, pages 216-221.

[MS95] S.K. Murthy, S, Salzberg. Lookahead and pathology in decision tree induction. Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence; 1995.

[MST94] D. Michie, D.J. Spiegelhalter, C.C. Taylor. Machine learning: neural and statistical classification. Ellis Horwood, London, 1994.

[Mur95] S. K. Murthy. On growing better decision treesfim data. PhD thesis, Department of Computer Science, Johns Hopkins University, Baltimore, Maryland 1995.

[Mur98] S. K. Murthy. Automatic construction of decision trees from data: A MultiDisciplinary Survey. Data Mining and Knowledge Discovery; 1998, Vol. 2, pages 345-389.

[MW94] W. Müller, F. Wysotzki. Automatic construction of decision trees for classification. Annals of Operations Research; 1994, Vol. 52; pages 231-247.

[Nau83] D.S. Nau. Decision quality as a function of search depth on game trees. Journal of the Association of Computing Machinery; 1983, Volume 30, Issue 4, pages 687-708.

[Nor89] S.W. Norton. Generating better decision trees. Proceedings of the Eleventh International Joint Conference on Artificial Intelligence; 1989, pages 800-805. Editor: N. S. Sridharan.

[Pea94] R.A. Pearson. A coarse grained parallel induction heuristic. In H. Kitano, V. Kumar, C.B. Suttner, editors. Parallel processing for Artificial Intelligence 2, Elsevier Science, 1994, pages 207-226.

[Qui86] J. R. Quinlan. Induction of decision trees. Machine Learning; 1986, Vol. 1 No. 1, pages 81-106.

[Qui87] J. R. Quinlan. Simplifying decision trees. International Journal of Man-Machine Studies, 27(3), 1987, pages 221-234.

[Qui93] J. R. Quinlan. C4.5: programs for machine learning. Morgan Kaufmann Publishers Inc., Los Altos, California, 1993.

[Qui96] J. R. Quinlan. Improved use of continuous attributes in C4.5. Journal of Artificial Intelligence Research, 4, 1996, pages 77-90.

[RR93] L. Rendell, H. Ragavan. Improving the design of induction methods by analyzing algorithm functionality and data-based concept complexity. In Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence; 1993, volume 2, pages 952-958. Editor: Ruzena Bajcsy.

[RR93] H. Ragavan, L. Rendell. Lookahead feature construction for learning hard concepts. Machine Learning: Proceedings of the Tenth International Conference; 1993, pages 252-259. Editor: P.E. Utgoff.

[RS98] R. Rastogi, K. Shim. Public: A decision tree classifier that integrates building and pruning. In Proceedings of 24th International Conference on Very Large Data Bases (1998), pages 404-415.

[Rul05] Rulequest Research Pty Ltd. Is See5/C5.0 better than C4.5? Internet resource, accessed 07.07.2005 at http://www.rulequest.com/see5-comparison.html.

[SAG99] G.P. J. Schmitz, C. Aldrich, F.S. Gouws. ANN-DT: An Algorithm for Extraction of Decision Trees from Artificial Neural Networks. Transactions on Neural Networks 10, 1999, pages 1392-1401.

[SAM96] J. Shafer, R. Agrawal, M. Mehta . SPRINT: A scalable parallel classifier for data mining. In Proceedings of 22nd International Conference on Very Large Data Bases (1996), pages 544-555.

[SBM71] J.A. Sonquist , E. L. Baker, J. N. Morgan. Searching for Structure, revised edition, Ann Arbor: Institute for Social Research, The University of Michigan. 1971

[SD84] J. Schuermann, W. Doster. A decision-theoretic approach in hierarchical classifier design. Pattern Recognition; 1984, Volume 17, pages 359-369.

[Sha48] C. E. Shannon. A mathematical theory of communication. Bell System Technical Journal; 1948, Volume 27, pages 379-423 and 623-656.

[Shl90] S. Shlien. Multiple binary decision tree classifiers. Pattern Recognition; 1990, Volume 23, Issue 7, pages 757-763.

[Shl92] S. Shlien. Nonparametric classification using matched binary decision trees. Pattern Recognition Letters; 1992, Volume 13, Issue 2, pages 83-88.

[SMV03] A. Stepnowski, M. Moszynski, T. Van Dung . Adaptive Neuro-Fuzzy and Fuzzy Decision Tree Classifiers As Applied to Seafloor Characterization. Acoustical Physics; 2003, Volume 49, Issue 2, pages 193-203.

[SQC95] X. Sun, Y. Qiu, L.A. Cox. A hill-climbing approach to construct near-optimal decision trees. Preliminary Papers of the Fifth International Workshop on Artificial Intelligence and Statistics; 1995, pages 513-519.

[TS93] P.C. Taylor, B.W. Silverman. Block diagrams and splitting criteria for classification trees. Statistics & Computing ; 1993, Volume 3, pages 147-161.

[UBC97] P.E. Utgoff, N.C. Berkman, J.A. Clouse. Decision tree induction based on eficient tree restructuring. Machine Learning; 1997, Volume 29, pages 5-44.

[UB90] P.E. Utgoff, C.E. Brodley. An incremental method for finding multivariate splits for decision trees. Proceedings of the Seventh International Conference on Machine Learning; 1990, pages 58-65.

[Utg89] P.E. Utgoff. Incremental induction of decision trees. Machine Learning; 1989, Volume 4, pages 161-186.

[Utg94] P.E. Utgoff. An improved algorithm for incremental induction of decision trees. Proceedings of the Eleventh International Conference of Machine Learning; 1994, pages 318-325. Editors: W.W. Cohen, H. Hirsh.

[VO03] R. Vilalta, D. Oblinger. Evaluation metrics in classification: a quantification of distance-bias. Computational Intelligence; 2003, Vol. 19 Issue 3, pages 264-284.

[WL94] A.P. White, W.Z. Liu. Technical note: Bias in information-based measures in decision tree induction. Machine Learning; 1994, Volume 15, Issue 3, pages 321-329.

[WS87] Q.R. Wang, C.Y. Suen. Large tree classifier with heuristic search and global training. IEEE Transactions on Pattern Analysis and Machine Intelligence; 1987, PAMI-9, Volume 1, pages 91-102.

[WZ00] H. Wang, C. Zaniolo. CMP: a fast decision tree classifier using multivariate predictions. Proceedings of the 16th International Conference on Data Engineering 2000, Page 449.

[YS95] Y. Yuan, M. J. Shaw. Induction of fuzzy decision trees. Fuzzy Sets and Systems, 1995, Volume 69, Issue 2, page 125.

Hiermit erkläre ich an Eides Statt, dass ich die vorliegende Arbeit selbstständig verfasst und keine anderen als die angegebenen Quellen und Hilfsmittel verwendet habe.

Braunschweig, im September 2005

Moritz Duhme

Persönliche Angaben des Verfassers

Vorname: Moritz

Name: Duhme

Studiengang: Wirtschaftsinformatik

Matrikelnummer: 2666156,

Telefonnummer: 0179 – 780 91 94

E-Mail-Adresse: m.duhme@tu-bs.de