Data mining - Induzione dell'albero decisionale

Un albero decisionale è una struttura che include un nodo radice, rami e nodi foglia. Ogni nodo interno denota un test su un attributo, ogni ramo denota il risultato di un test e ogni nodo foglia contiene un'etichetta di classe. Il nodo più in alto nell'albero è il nodo radice.

Il seguente albero decisionale riguarda il concetto buy_computer che indica se un cliente di un'azienda è probabile che acquisti un computer o meno. Ogni nodo interno rappresenta un test su un attributo. Ogni nodo foglia rappresenta una classe.

I vantaggi di avere un albero decisionale sono i seguenti:

• Non richiede alcuna conoscenza del dominio.
• È facile da comprendere.
• Le fasi di apprendimento e classificazione di un albero decisionale sono semplici e veloci.

Algoritmo di induzione dell'albero decisionale

Un ricercatore di macchine di nome J. Ross Quinlan nel 1980 ha sviluppato un algoritmo di albero decisionale noto come ID3 (Iterative Dichotomiser). Successivamente, ha presentato C4.5, che era il successore di ID3. ID3 e C4.5 adottano un approccio avido. In questo algoritmo, non c'è backtracking; gli alberi sono costruiti in modo ricorsivo divide et impera dall'alto verso il basso.

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;

Potatura degli alberi

La potatura degli alberi viene eseguita al fine di rimuovere le anomalie nei dati di allenamento dovute a rumore o valori anomali. Gli alberi potati sono più piccoli e meno complessi.

Approcci alla potatura degli alberi

Esistono due approcci per potare un albero:

• Pre-pruning - La potatura dell'albero viene interrotta anticipatamente.

• Post-pruning - Questo approccio rimuove un sottoalbero da un albero completamente cresciuto.

Complessità dei costi

La complessità dei costi è misurata dai seguenti due parametri:

• Numero di foglie dell'albero e
• Tasso di errore dell'albero.