Data Mining - Indução de árvore de decisão

Uma árvore de decisão é uma estrutura que inclui um nó raiz, ramos e nós folha. Cada nó interno denota um teste em um atributo, cada ramificação denota o resultado de um teste e cada nó folha contém um rótulo de classe. O nó superior da árvore é o nó raiz.

A árvore de decisão a seguir é para o conceito buy_computer, que indica se um cliente de uma empresa provavelmente comprará um computador ou não. Cada nó interno representa um teste em um atributo. Cada nó folha representa uma classe.

Os benefícios de ter uma árvore de decisão são os seguintes -

• Não requer nenhum conhecimento de domínio.
• É fácil de compreender.
• As etapas de aprendizagem e classificação de uma árvore de decisão são simples e rápidas.

Algoritmo de indução de árvore de decisão

Um pesquisador de máquinas chamado J. Ross Quinlan em 1980 desenvolveu um algoritmo de árvore de decisão conhecido como ID3 (Dicotomizador Iterativo). Posteriormente, ele apresentou o C4.5, que foi o sucessor do ID3. ID3 e C4.5 adotam uma abordagem gananciosa. Nesse algoritmo, não há retrocesso; as árvores são construídas de uma maneira recursiva de divisão e conquista de cima para baixo.

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;

Poda de árvores

A poda da árvore é realizada para remover anomalias nos dados de treinamento devido a ruído ou outliers. As árvores podadas são menores e menos complexas.

Abordagens de poda de árvores

Existem duas abordagens para podar uma árvore -

• Pre-pruning - A árvore é podada interrompendo-se precocemente a sua construção.

• Post-pruning - Esta abordagem remove uma subárvore de uma árvore totalmente crescida.

Complexidade de custos

A complexidade do custo é medida pelos dois parâmetros a seguir -

• Número de folhas na árvore, e
• Taxa de erro da árvore.