C4.5

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

C4.5 ist ein Algorithmus des Konzeptlernens, einer Form des maschinellen Lernens. Er wurde als Erweiterung des ID3-Algorithmus' von Ross Quinlan entwickelt[1]. C4.5 wird verwendet, um aus Trainingsdaten einen Entscheidungsbaum zu erzeugen, mit dem Datensätze klassifiziert werden können[2].

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 gilt 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:


Diagramm beispiel sarah geht segeln.png


Wetterlage Termperatur in °C Luftfeuchtigkeit in % Windstärke Sarah geht segeln
Sonnig 29 85 Leicht Falsch
Sonnig 27 90 Stark Falsch
Bedeckt 28 78 Leicht Wahr
Regnerisch 21 96 Leicht Wahr
Regnerisch 20 80 Leicht Wahr
Regnerisch 18 70 Stark Falsch
Bedeckt 17 65 Stark Wahr
Sonnig 22 95 Leicht Falsch
Sonnig 21 70 Leicht Wahr
Regnerisch 24 80 Leicht Wahr
Sonnig 24 70 Stark Wahr
Bedeckt 22 90 Stark Wahr
Bedeckt 27 75 Leicht Wahr
Regnerisch 21 80 Stark Falsch

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 - Aufwändig zu bestimmenden Merkmalen kann eine höhere Kostengewichtung zugeordnet werden. Merkmale mit hohen Kostengewichtungen werden tendenziell weiter unten im Entscheidungsbaum als Verzweigungen angeordnet, sodass für weniger Klassifizierungen dieses Merkmal überhaupt bestimmt werden muss. Beispielsweise könnte die Anwendung von C4.5 zur Krankheitsdiagnostizierung unter der Datenbasis von Symptomen und medizinischen Untersuchungswerten so angepasst werden, dass kostenintensive Untersuchungen eher vermieden werden und möglichst nur in Zweifelsfall zwischen mehreren möglichen Diagnosen zum Einsatz kommen.
  • Stutzen (Pruning) des Entscheidungsbaumes nach dessen Erstellung - Um die Anzahl der möglichen Ergebnisklassen der Klassifizierung zu verringern, schneidet C4.5 lange Äste ab. Dies verhindert außerdem Überanpassung an die Trainingsdaten.

Siehe auch[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. Quinlan, J. R. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers, 1993.
  2. Tom M. Mitchell: Machine Learning, 1997