C4.5

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung.
Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Die fraglichen Angaben werden daher möglicherweise demnächst entfernt. Bitte hilf der Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst. Näheres ist eventuell auf der Diskussionsseite oder in der Versionsgeschichte angegeben. Bitte entferne zuletzt diese Warnmarkierung.
Artikel komplett unbelegt --160.45.45.65 15:15, 4. Feb. 2013 (CET)

C4.5 ist ein Algorithmus, der zur Entscheidungsfindung dient. Er wird bei Entscheidungsbäumen eingesetzt und gilt als Nachfolger des ID3-Algorithmus'[1].

Neben den bekannten CARTs und CHAIDs gewinnt C4.5 immer mehr an Bedeutung. Er wird mittlerweile bereits von verschiedenen Softwarepaketen eingesetzt.

Grundsätzlich verhält sich dieser Algorithmus sehr ähnlich zum CART-Algorithmus. Der Hauptunterschied besteht darin, dass bei C4.5 keine binäre Aufteilung erfolgen muss, sondern eine beliebige Anzahl Verzweigungen eingebaut werden können. Der Baum wird breiter. Er ist meist weniger tief als der korrespondierende CART-Baum. Dafür werden nach der ersten Klassifizierung die nachfolgenden Aufsplittungen weniger bedeutungsvoll.

Ein weiterer Unterschied zeigt sich beim so genannten Pruning, beim Stutzen des Baumes. CART erzeugt einige Subtrees und testet diese mit neuen, vorher noch nicht klassifizierten Daten. C4.5 hingegen beschneidet den Baum ohne Beachtung der gegebenen Datenbasis.

Algorithmus[Bearbeiten]

C4.5 generiert aus Trainingsdaten einen Entscheidungsbaum, mit dem zukünftige Instanzen, die nicht in den Trainingsdaten enthalten waren, klassifiziert werden können. Dabei wird, ähnlich wie beim ID3 Algorithmus, die Berechnung der Entropie verwendet, um die Reihenfolge der Entscheidungsknoten in deren Abstand zum Wurzelknoten innerhalb des zu generierenden Entscheidungsbaumes zu bestimmen.

Ablauf[Bearbeiten]

Die Trainingsdaten seien eine Menge S = \{ s_1, s_2, ... \} , bestehend aus den bekannten Trainingsbeispielen. Jedes Trainingsbeispiel s_i \in S dieser Menge sei ein p+1 -dimensionaler Vektor aus den zu erlernenden Merkmalen (Instanz) x_{1,i}, x_{2,i}, ..., x_{p,i} und der zu erlernenden Zielklassifikation c_i: s_i = (x_{1,i}, x_{2,i}, ..., x_{p,i}, c_i). Bei der Erzeugung des obersten Knotens im Entscheidungsbaum sucht C4.5 nach dem ersten Entscheidungsmerkmal. Zu dessen Bestimmung vergleicht C4.5 für jedes Merkmal die Effizienz, mit der die Trainingsdatenmenge unter diesem Merkmal aufgeteilt würde, und entscheidet sich für das beste. Als Kriterium gillt dabei der durch das Merkmal zu erreichende höchste Information Gain (Kullback-Leibler-Divergenz). Die Trainingsdaten werden daraufhin in Teilmengen gemäß ihren Werten des ausgewählten Merkmales aufgeteilt, für die jeweils ein Ast unterhalb des Wurzelknotens entsteht. Der Algorithmus wird rekursiv fortgeführt, indem der bisherige Ablauf erneut für jeden dieser Äste unter Einschränkung der diesem Ast zugeordneten Teilmenge der Trainingsdaten angewandt wird. Wenn an einem Ast keines der Merkmale zu weiterer Unterteilung der Trainingsdaten mehr führen würde ( Information Gain = 0 ), entsteht an diesem Ast ein Blatt mit der verbleibenden Zielklassifikation. Der höchst mögliche maximale Grad des Baumes beträgt somit p + 1.

Beispiel[Bearbeiten]

Sarah geht an einigen Tagen segeln, an anderen Tagen nicht. Ob sie an einem bestimmten Tag segeln geht sei vorwiegend von den folgenden Merkmalen abhängig: Wetterlage (sonnig / bedeckt / regnerisch); Temperatur; Luftfeuchtigkeit; Windstärke (leicht / stark). An 14 zufälligen Tagen wurden diese Daten zusammen mit der Information, ob Sarah segeln geht, erfasst:

Wetterlage Termperatur in °C Luftfeuchtigkeit in % Windstärke Sarah geht segeln
Sonnig 85 85 Leicht Falsch
Sonnig 80 90 Stark Falsch
Bedeckt 83 78 Leicht Wahr
Regnerisch 70 96 Leicht Wahr
Regnerisch 68 80 Leicht Wahr
Regnerisch 65 70 Stark Falsch
Bedeckt 64 65 Stark Wahr
Sonnig 72 95 Leicht Falsch
Sonnig 69 70 Leicht Wahr
Regnerisch 75 80 Leicht Wahr
Sonnig 75 70 Stark Wahr
Bedeckt 72 90 Stark Wahr
Bedeckt 81 75 Leicht Wahr
Regnerisch 71 80 Stark Falsch
Diagramm beispiel sarah geht segeln.png

Maschinelles Lernen soll eingesetzt werden, um den Zusammenhang zwischen den vier tagesbedingten Merkmalen und der Aussage, ob Sarah segeln geht, aufzudecken. Hat man einmal diesen Zusammenhang ermittelt, dann lässt sich auch für beliebige andere Tage bei Kenntnis der Wetterdaten bestimmen, ob Sarah segeln geht. C4.5 generiert aus den in der Tabelle gegebenen Trainingsdaten den abgebildeten Entscheidungsbaum. Die Zahlen in den Klammern geben die Anzahl der Trainingsdatensätze an, die diesem Pfad entsprächen.

Verbesserungen gegenüber ID3[Bearbeiten]

Als Erweiterung des ID3 Algorithmus bietet C4.5 einige Verbesserungen:

  • Anwendbarkeit sowohl auf diskrete als auch auf kontinuierliche Attribute - Enthalten die Datensätze beispielsweise eine reelle Größe als eines der Merkmale, so werden die Merkmalswerte in diskrete Intervalle eingeordnet.
  • Anwendbarkeit auf Trainingsdaten mit fehlenden Attributswerten - Unter Anwendung von C4.5 können nicht verfügbare Merkmalswerte als unbekannt (?) markiert werden. Unbekannte Werte werden bei der Berechnung des Information Gain einfach ignoriert.
  • Mögliche Kostengewichtung der Attribute
  • Stutzen (Pruning) des Entscheidungsbaumes nach dessen Erstellung - Um die Anzahl der möglichen Ergebnisklassen der Klassifizierung zu verringern, schneidet C4.5 lange Äste ab.

Siehe auch[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. Tom Mitchell: Machine Learning. 1997. S. 71