Arbol decision

Aprendizaje Autom´tico: a Arboles de Decisi´n. o
Dr. Alejandro Guerra Hern´ndez a Universidad Veracruzana Facultad de F´ ısica e Inteligencia Artificial Maestr´ en Inteligencia Artificial ıa Sebasti´n Camacho No. 5, Xalapa, Ver., M´xico 91000 a e aguerra@uv.mx www.uv.mx/aguerra Marzo 15, 2004

1.

Introducci´n o

El aprendizaje de arboles de decisi´n es una de las t´cnicas de inferencia ´ oe inductiva m´s usadas. Se trata de un m´todo para aproximar funciones de vaa e lores discretos, capaz de expresar hip´tesis disyuntivas y robusto al ruido en los o ejemplos de entrenamiento. La descripci´n que presento en este cap´ o ıtulo, cubre una familia de algoritmos para la inducci´n de arboles de decisi´n que incluyen o ´ o ID3 [3] y C4.5 [5]. Estos algoritmos llevan a cabo su b´squeda dehip´tesis en un u o espacio completamente expresivo, evitando as´ los problemas mencionados en la ı sesi´n pasada, con respecto a espacios de hip´tesis incompletos. El sesgo induco o tivo en este caso, consiste en la preferencia por ´rboles peque˜os, sobre arboles a n ´ grandes. Un arbol aprendido puede representarse tambi´n como un conjunto de ´ e reglas si-entonces, m´s f´ciles de entender paraun usuario. a a

2.

Representaci´n de los ´rboles de decisi´n o a o

La figura 1 muestra un arbol de decisi´n t´ ´ o ıpico. Cada nodo del arbol est´ con´ a formado por un atributo y puede verse como la pregunta: ¿Qu´ valor tiene este e atributo en el ejemplar a clasificar? Las ramas que salen de los nodos, corresponden a los posibles valores del atributo correspondiente. Un arbol de decisi´nclasifica a un ejemplar, filtrandolo de manera descen´ o dente, hasta encontrar una hoja, que corresponde a la clasificaci´n buscada. o Consideren el proceso de clasificaci´n del siguiente ejemplar, que describe un o d´ en part´ ıa ıcular:
cielo = soleado, temperatura = caliente, humedad = alta, viento = f uerte

1

Soleado Nublado Lluvia

Alta

Normal

Fuerte Débil

Figura 1: Un ejemplode arbol de decisi´n para el concepto “buen d´ para jugar o ıa tenis”. Los nodos representan un atributo a ser verificado por el clasificador. Las ramas son los posibles valores para el atributo en cuesti´n. Los textos en o may´sculas, representan las clases consideradas, i.e., los valores posibles del u atributo objetivo.

Como el atributo cielo, tiene el valor soleado en el ejemplar, ´ste esfiltrado e hac´ abajo del arbol por la rama de la derecha. Como el atributo humedad, ıa ´ tiene el valor alta, el ejemplo es filtrado nuevamente por rama de la derecha, lo cual nos lleva a la hoja que indica la clasificaci´n del ejemplar: Buen d´ para o ıa jugar tenis = no. El algoritmo de clasificaci´n se muestra en el cuadro 1. o La funci´n toma-valor encuentra el valor de un atributo, en el ejemplarque o se est´ clasificando. El predicado hoja es verdadero si su argumento es un nodo a terminal del arbol y falso si se trata de un nodo interno. La funci´n sub-´rbol ´ o a se mueve por la rama del ´rbol que corresponde al valor del atributo probado en a el ejemplar. De esta forma, obtiene un sub-´rbol. En nuestro ejemplo, a partir a del nodo ra´ cielo, esta funci´n obtiene el sub-´rbol que resultade moverse por ız o a la rama soleado, etc. En general, un arbol de decisi´n representa una disyunci´n de conjunciones ´ o o de restricciones en los posibles valores de los atributos de los ejemplares. Cada rama que va de la ra´ del ´rbol a una hoja, representa una conjunci´n de tales ız a o restricciones y el ´rbol mismo representa la disyunci´n de esas conjunciones. a o Por ejemplo, el arbol dela figura 1, puede expresarse como sigue: ´
∨ ∨ (cielo = soleado ∧ humedad = normal) (cielo = nublado) (cielo = lluvia ∧ viento = d´bil) e

2

fun clasifica(ejemplar, ´rbol) a input: ejemplar: el ejemplar a ser clasificado; a ´rbol: el ´rbol de decisi´n usado para clasificar; a o output: clase: la clase del ejemplar. clase ← toma-valor(ra´ arbol), ejemplar); ız(´ if hoja(ra´ arbol)) then...