Inteligencia Artificial: Árboles de Decisión (III)

Tweet

Después de la introducción que hice en la primera parte de este post y la explicación de la técnica en la segunda parte, en este último post os voy a explicar con pseucódigo el algoritmo en sí para crear un árbol de decisión.

El pseucódigo para crear un árbol de decisión es el siguiente:

ID3(E,A,X){
Si (A == vacío or MismaClase(E)) entonces Clase(X) == Clase(Mayoría)
sino
    Am = MejorAtributo(A)
    Para cada valor v de Am:
          N = CrearNodo(Am,v)
          hijos(X) = hijos(X) + N
          Em = ejemplos(E,Am,v)
          ID3(Em,A-Am,N)   
Devolver X
}

La explicación del algoritmo es la vista en la segunda parte de este post. Se crea una función que consiste en construir un árbol de decisión que en función de un ejemplos de entrenamiento E, y unos atributos A nos permita clasificar ejemplos futuros.

Se comienza comprobando si no hay atributos para los ejemplos o si todos los ejemplos pertenecen a la misma clase. Si se da este caso se asigna la clase de la mayoría para el nodo en cuestión. Si no es el caso obtenemos el mejor atributo Am del conjunto de atributos A del ejemplo X a través de la función de entropía comentada en post anteriores. Una vez escogido el mejor atributo Am, para cada valor v construimos un nuevo nodo N, lo asignamos a los hijos del nodo X, clasificamos los ejemplos Em que cumplan el valor v para el tributo Am y llamamos recursivamente al algoritmo para el subgrupo de ejemplos de entrenamiento Em, excluyendo el atributo Am y como nodo raíz el nodo N que se está tratando. El algoritmo devuelve en todo caso el nodo raíz tratado.

Al final del proceso contamos con una estructura de nodos que conforma un árbol que nos permitirá clasificar ejemplos futuros. Su implementación depende lógicamente del lenguaje utilizado y de las estructuras de datos que nos proporcione.

Para clasificar futuros ejemplos, basta con crear una función a la que se pase el árbol de decisión obtenido y el ejemplo a clasificar, de manera que compruebe en cada nodo la clasificación que debe seguir en función de sus atributos.