Minería de datos: inducción del árbol de decisiones

Un árbol de decisión es una estructura que incluye un nodo raíz, ramas y nodos hoja. Cada nodo interno denota una prueba sobre un atributo, cada rama denota el resultado de una prueba y cada nodo hoja tiene una etiqueta de clase. El nodo superior del árbol es el nodo raíz.

El siguiente árbol de decisiones corresponde al concepto buy_computer que indica si es probable que un cliente de una empresa compre una computadora o no. Cada nodo interno representa una prueba sobre un atributo. Cada nodo hoja representa una clase.

Los beneficios de tener un árbol de decisiones son los siguientes:

• No requiere ningún conocimiento de dominio.
• Es fácil de comprender.
• Los pasos de aprendizaje y clasificación de un árbol de decisiones son simples y rápidos.

Algoritmo de inducción del árbol de decisión

Un investigador de máquinas llamado J. Ross Quinlan en 1980 desarrolló un algoritmo de árbol de decisión conocido como ID3 (dicotomizador iterativo). Posteriormente, presentó C4.5, que fue el sucesor de ID3. ID3 y C4.5 adoptan un enfoque codicioso. En este algoritmo, no hay retroceso; los árboles están construidos de arriba hacia abajo de una manera recursiva de dividir y conquistar.

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 árboles

La poda de árboles se realiza para eliminar anomalías en los datos de entrenamiento debido al ruido o valores atípicos. Los árboles podados son más pequeños y menos complejos.

Enfoques de poda de árboles

Hay dos métodos para podar un árbol:

• Pre-pruning - El árbol se poda deteniendo temprano su construcción.

• Post-pruning - Este enfoque elimina un subárbol de un árbol completamente desarrollado.

Complejidad de costos

La complejidad del costo se mide mediante los siguientes dos parámetros:

• Número de hojas en el árbol y
• Tasa de error del árbol.