Data Mining - Entscheidungsbauminduktion

Ein Entscheidungsbaum ist eine Struktur, die einen Wurzelknoten, Zweige und Blattknoten enthält. Jeder interne Knoten bezeichnet einen Test für ein Attribut, jeder Zweig bezeichnet das Ergebnis eines Tests und jeder Blattknoten enthält eine Klassenbezeichnung. Der oberste Knoten im Baum ist der Wurzelknoten.

Der folgende Entscheidungsbaum bezieht sich auf das Konzept buy_computer, das angibt, ob ein Kunde in einem Unternehmen wahrscheinlich einen Computer kauft oder nicht. Jeder interne Knoten repräsentiert einen Test für ein Attribut. Jeder Blattknoten repräsentiert eine Klasse.

Die Vorteile eines Entscheidungsbaums sind folgende:

• Es sind keine Domänenkenntnisse erforderlich.
• Es ist leicht zu verstehen.
• Die Lern- und Klassifizierungsschritte eines Entscheidungsbaums sind einfach und schnell.

Entscheidungsbaum-Induktionsalgorithmus

Ein Maschinenforscher namens J. Ross Quinlan entwickelte 1980 einen Entscheidungsbaumalgorithmus namens ID3 (Iterative Dichotomiser). Später präsentierte er C4.5, den Nachfolger von ID3. ID3 und C4.5 verfolgen einen gierigen Ansatz. In diesem Algorithmus gibt es kein Backtracking. Die Bäume sind von oben nach unten rekursiv geteilt und erobert.

Generating a decision tree form training tuples of data partition D
Algorithm : Generate_decision_tree

Input:
Data partition, D, which is a set of training tuples 
and their associated class labels.
attribute_list, the set of candidate attributes.
Attribute selection method, a procedure to determine the
splitting criterion that best partitions that the data 
tuples into individual classes. This criterion includes a 
splitting_attribute and either a splitting point or splitting subset.

Output:
 A Decision Tree

Method
create a node N;

if tuples in D are all of the same class, C then
   return N as leaf node labeled with class C;
   
if attribute_list is empty then
   return N as leaf node with labeled 
   with majority class in D;|| majority voting
   
apply attribute_selection_method(D, attribute_list) 
to find the best splitting_criterion;
label node N with splitting_criterion;

if splitting_attribute is discrete-valued and
   multiway splits allowed then  // no restricted to binary trees

attribute_list = splitting attribute; // remove splitting attribute
for each outcome j of splitting criterion

   // partition the tuples and grow subtrees for each partition
   let Dj be the set of data tuples in D satisfying outcome j; // a partition
   
   if Dj is empty then
      attach a leaf labeled with the majority 
      class in D to node N;
   else 
      attach the node returned by Generate 
      decision tree(Dj, attribute list) to node N;
   end for
return N;

Baumschnitt

Das Beschneiden von Bäumen wird durchgeführt, um Anomalien in den Trainingsdaten aufgrund von Rauschen oder Ausreißern zu beseitigen. Die beschnittenen Bäume sind kleiner und weniger komplex.

Baumschnitt-Ansätze

Es gibt zwei Ansätze, um einen Baum zu beschneiden:

• Pre-pruning - Der Baum wird beschnitten, indem der Bau vorzeitig eingestellt wird.

• Post-pruning - Dieser Ansatz entfernt einen Teilbaum von einem ausgewachsenen Baum.

Kostenkomplexität

Die Kostenkomplexität wird anhand der folgenden zwei Parameter gemessen:

• Anzahl der Blätter im Baum und
• Fehlerrate des Baumes.