Arboles de Clasificacion

Introduccion ID3 Mejoras C4.5 M5 Conclusiones

Tema B.6: ARBOLES DE CLASIFICACION

Concha Bielza, Pedro Larranaga

Departamento de Inteligencia ArtificialFacultad de Informatica, Universidad Politecnica de Madrid

Aprendizaje Automatico


Indice

1 Introduccion

2 Algoritmo basico: ID3

3 Mejoras a ID3

4 C4.5

5 Variable clase continua

6 Conclusiones


Indice

1 Introduccion


3 Mejoras a ID3

4 C4.5


6 Conclusiones


Introduccion

Arbol de decisionMuy utilizado y popularAproxima funciones que toman valores discretos. Lafuncion aprendida se representa como un arbolRobusto a datos con ruidoAprende expresiones disyuntivas: los arboles aprendidosse pueden re-representar como reglas if-then(intuitivas)Numerosas aplicaciones: diagnosticos medicos, causa defallo en equipos, evaluacion de riesgos de creditos en laconcesion de prestamos...Arbol de clasificacion y de regresion


Introduccion

Representacion como arbolesCada nodo (no terminal) especifica un test de algunatributo de la instanciaCada rama corresponde a un posible valor del atributoCada nodo terminal indica la clase en la que se clasificaInstancias no vistas se clasifican recorriendo el arbol:pasandoles el test en cada nodo, por orden desde el nodoraız hasta algun nodo hoja, que da su clasificacion


Introduccion

Ejemplo: PlayTennisClasificar las mananas de Sabado en si son o no adecuadaspara jugar al tenis

Instancia:Outlook=Sunny, Temperature=Hot, Humidity=High, Wind=Strongentra por el camino izdo. y se predice PlayTennis=No


Introduccion

Ejemplo: PlayTennisEl arbol representa una disyuncion de conjunciones derestricciones sobre los valores de los atributos de lasinstanciasUn camino = una conjuncion de tests de atributosTodo el arbol = disyuncion de estas conjunciones

Este arbol es:

(Outlook=Sunny ∧ Humidity=Normal)∨ (Outlook=Overcast)

∨ (Outlook=Rain ∧Wind=Weak)


Introduccion

Generacion de reglasR1: If (Outlook=Sunny) AND (Humidity=High) then PlayTennis=NoR2: If (Outlook=Sunny) AND (Humidity=Normal) then PlayTennis=YesR3: If (Outlook=Overcast) then PlayTennis=YesR4: If (Outlook=Rain) AND (Wind=Strong) then PlayTennis=NoR5: If (Outlook=Rain) AND (Wind=Weak) then PlayTennis=Yes


Introduccion

Tipos de problemas apropiadosInstancias representadas como pares atributo-valor(atributos discretos o reales)Funcion objetivo toma valores discretos (clasificacion)......pero extensiones a valores continuos: arboles deregresionRobustez a errores en los datos (de entrenamiento), tantoen la variable respuesta como en los atributosPuede haber datos perdidos (missing) para algunasinstancias en los valores de los atributosDominios complejos donde no existe una clara separacionlineal


Introduccion

Ejemplo

Se divide el espacio en regiones etiquetadas con una sola clase y son

hiperrectangulos (ojo!)


Introduccion

Tipos de arboles

Arboles de clasificacion: valores de salida discretosCLS, ID3, C4.5, ID4, ID5, C4.8, C5.0

Arboles de regresion: valores de salida continuosCART, M5, M5’


Indice

1 Introduccion


3 Mejoras a ID3

4 C4.5


6 Conclusiones


Algoritmo basico: ID3

ID3=Iterative dicotomiser [Quinlan, 1986]Basado en el algoritmo CLS (Concept Learning Systems) [Hunt et al., 1966],que usaba solo atributos binarios

Estrategia de busqueda voraz (greedy) por el espacio de posibles arboles declasificacion

Construir el arbol de arriba a abajo, preguntando: ¿Que atributo seleccionarcomo nodo raız?

Se evalua cada atributo para determinar cuan bien clasifica los ejemplos el solo

Se selecciona el mejor como nodo, se abre el arbol para cada posible valor delatributo y los ejemplos se clasifican y colocan en los nodos apropiados

Repetir todo el proceso usando los ejemplos asociados con el nodo en el queestemos (siempre hacia delante, buscando entre los atributos no usados en estecamino)

Parar cuando el arbol clasifica correctamente los ejemplos o cuando se hanusado todos los atributos

Etiquetar el nodo hoja con la clase de los ejemplos



ID3Paso clave: como seleccionar el atributo a testear en cadanodo del arbol?Nos gustarıa el mas util para clasificar ejemplos; el que lossepara bienID3 escoge la cantidad de informacion mutua comomedida de la valıa de cada atributo (maximizarla)

I(C,Xi) = H(C)− H(C|Xi) (ganancia de informacion)

H(C) = −∑

cp(c) log2 p(c), H(C|X) = −

∑c

∑x

p(x , c) log2 p(c|x)

Reduccion esperada en entropıa (incertidumbre), causadaal particionar los ejemplos de acuerdo a este atributo



Ejemplo ID3: PlayTennisDatos:

Day Outlook Temperature Humidity Wind PlayTennis1 Sunny Hot High Weak No2 Sunny Hot High Strong No3 Overcast Hot High Weak Yes4 Rain Mild High Weak Yes5 Rain Cool Normal Weak Yes6 Rain Cool Normal Strong No7 Overcast Cool Normal Strong Yes8 Sunny Mild High Weak No9 Sunny Cool Normal Weak Yes10 Rain Mild Normal Weak Yes11 Sunny Mild Normal Strong Yes12 Overcast Mild High Strong Yes13 Overcast Hot Normal Weak Yes14 Rain Mild High Strong No



Ejemplo ID3: PlayTennisWind?

H(C) = − 914 log2

914 −

514 log2

514 = 0.940

H(C|Wind) =

−p(Strong,Yes) log2 p(Yes|Strong)− p(Strong,No) log2 p(No|Strong)−p(Weak ,Yes) log2 p(Yes|Weak)− p(Weak ,No) log2 p(No|Weak) =

− 314 log2

36 −

314 log2

36 −

614 log2

68 −

214 log2

28 = 0.892

⇒ I(C,Wind) = 0.940− 0.892 = 0.048

Analogamente,

I(C,Humidity) = 0.151I(C,Outlook) = 0.246⇐ Escoger Outlook como nodo raızI(C,Temperature) = 0.029



Ejemplo ID3: PlayTennis



Ejemplo ID3: PlayTennis

Todos los ejemplos con Outlook=Overcast son positivos⇒ Se convierte en nodohoja

El resto tienen entropıa no cero y el arbol debe seguir



Ejemplo ID3: PlayTennisSe repite el proceso para cada nodo descendiente noterminal, usando solo los ejemplos asociados con el nodoCualquier atributo aparece como mucho una vez en cadacamino

P.e., por la rama Sunny (con 5 instancias), buscamos el atributosiguiente:

H(Csunny ) = −35 log2

35 −

25 log2

25 = 0.97

I(Csunny ,Temperature) = 0.97− 0.4 = 0.57I(Csunny ,Humidity) = 1.94I(Csunny ,Wind) = 0.019

⇒ ...Arbol final es el visto antes



Observaciones generalesAl ser voraz, puede que conduzca a una solucion optimalocal en vez de global

Extension de ID3 para anadir una forma de backtracking (post-poda)

Por usar propiedades estadısticas de todos los ejemplos(en ganancia de info), busqueda menos sensible a erroresen los datos

Extension de ID3 para manejar datos con ruido modificando su criterio deparada: crear hoja sin necesidad de esperar a que todas las etiquetassean iguales (etiquetar con la mayorıa)

Complejidad crece linealmente con el numero deinstancias de entrenamiento y exponencialmente con elnumero de atributosMatematicamente se demuestra que favorece la eleccionde variables con mayor numero de valores


Indice

1 Introduccion


3 Mejoras a ID3

4 C4.5


6 Conclusiones


Mejoras a ID3

Cuestiones practicas a tener en cuenta¿Cuanto hacer crecer el arbol?¿Es adecuada esta medida de seleccion de los atributos?¿Como manejar atributos continuos?¿Como manejar datos de entrenamiento con valoresperdidos (desconocidos) en los atributos?¿Como manejar atributos con costes diferentes?


Cuanto hacer crecer el arbol

Problema de sobreajusteProblemas por hacer crecer el arbol hasta que clasifiquecorrectamente todos los ejemplos de entrenamiento:

Si hay ruido en los ejemplos, !podemos aprender el ruido!Si hay pocos ejemplos asociados a los nodos hoja, no sonrepresentativos de la verdadera funcion

⇒ ID3 produce arboles que sobreajustan los ejemplos deentrenamiento (y no funciona adecuadamente con nuevosejemplos). El modelo no es capaz de generalizar


Sobreajuste

Soluciones al sobreajusteHay dos grupos de tecnicas, que tratan de simplificar el arbol:

Pre-poda: parar de aumentar el arbol antes de quealcance el punto en el que clasifica perfectamente losejemplos de entrenamiento⇒ Difıcil estimar cuandoPost-poda: permitir que sobreajuste los datos, y despuespodarlo reemplazando subarboles por una hoja⇒ La mejor en la practica, aunque mayor coste comput.


Sobreajuste

Pre-podas

Aplicar un test estadıstico para estimar si expandiendo un nodo particular esprobable producir una mejora mas alla del conjunto de entrenamiento (e.g. testχ2 como en Quinlan, 1986)

Post-podas

Comenzando desde abajo, examinar los subarboles de los nodos no terminales

Podar un nodo significa eliminar su subarbol correspondiente con raız en esenodo, convertir el nodo en nodo hoja y asignarle la clasificacion mas comun delos ejemplos de entrenamiento asociados a ese nodo

Se poda solo si el arbol podado resultante mejora o iguala el rendimiento delarbol original sobre el conjunto de testeo

Podar iterativamente, escogiendo siempre el nodo a podar que mejore mas laprecision en el conjunto de testeo

... hasta que ya no convenga (precision disminuye)


Otras medidas de seleccion de atributos

Favorece eleccion de atributos con muchos valoresEjemplo extremo: “Fecha” en el problema de PlayTennis sale elegido como raız(predice perfectamente los ejemplos de entrenamiento y tendrıamos un arbolmuy ancho y de profundidad 1, con un nodo hoja por cada ejemplo)

Su ganancia de info es la mayor (al tener tantas ramas le obliga a separar losejemplos en subconjuntos muy pequenos)

...Pero serıa muy malo en ejemplos no vistos

Por ello hay otras medidas en vez de la ganancia de info:⇒ p.e. ratio de ganancia I(C,Xi )/H(Xi ) , que penaliza los atributos conmuchos valores y muchos uniformemente distribuidos

Algunos estudios experimentales hablan de no demasiada influencia de estasmedidas sobre el rendimiento y sı de las post-podas


Atributos con valores continuos

DiscretizarlosParticionar en un conjunto discreto de intervalos, e.g. 2 intervalos A < c y A ≥ c

Buscar c que produzca la mayor ganancia de informacion

Tal valor se demuestra que esta siempre en donde el valor de la clase cambia

(una vez ordenados los ejemplos por el atributo continuo A)

⇒ Ordenar los ejemplos de acuerdo al valor continuo de A, tomar 2 valores de A

que van seguidos con distinto valor de C y promediarlos

⇒ Entre estos candidatos a ser c, escoger el que produzca mayor ganancia de info

en este momento

⇒ Escogido el c, este nuevo atributo compite con los otros discretos para ver si es

elegido

⇒ Si A no es elegido, puede que salga luego otro valor de c distinto

⇒ Es decir, el atributo se crea dinamicamente


Atributos con valores continuos

DiscretizarlosEjemplo: candidatos son c1 = (48 + 60)/2 = 54 yc2 = (80 + 90)/2 = 85:

Temperature 40 48 60 72 80 90PlayTennis No No Yes Yes Yes No

Otras alternativas: mas de 2 intervalos o incluso usarcombinaciones lineales de varias variables αA + βB > c...Tambien si es discreta pero con muchos valores: agruparlos valores


Atributos con valores perdidos (missing)

ImputarlosEliminar instancias incompletasEstimar dichos valores –imputacion–:

Asignarles la moda: valor mas comun entre los ejemplosasociados al nodo donde estamos calculando I o entre losejemplos del nodo que tienen la misma etiqueta que lainstancia a imputarAsignar distribucion de probabilidad de cada posible valordel atributo, estimada con las frecuencias observadas en elnodo (Si fueran e.g. 0.6/0.4, esas fracciones de la instancia son las que se distribuyen por el

arbol y con las que se calcula la ganancia)


Atributos con diferentes costes

Introducir el coste en la medida de seleccion de atributosFiebre, Biopsia, Pulso, Analisis de sangre... todos condiferentes coste (monetario y de comfort para el paciente)Tratar de situar los de bajo coste arriba del arbol,acudiendo a los de alto coste solo cuando sea necesario(para mejorar las clasificaciones)Ası, por ejemplo:

I(C,Xi)

coste(Xi)


Indice

1 Introduccion


3 Mejoras a ID3

4 C4.5


6 Conclusiones


Algoritmo C4.5 [Quinlan, 1993]

C4.5Escoge atributos usando el ratio de ganancia (maximizarla)

I(C,Xi )/H(Xi ) (ratio de ganancia)

Incorporacion de post-poda de reglas: generar las reglas (1 por camino) yeliminar precondiciones (antecedentes) siempre que mejore o iguale el error

Convertir el arbol en un conjunto de reglas R

Error = error de clasificacion con R

Para cada regla r de R:

Nuevo-error = error al eliminar antecedente j de r

Si Nuevo-error ≤ Error, entonces Nuevo-error = Error y eliminar de r este antecedente

Si no hay mas antecedentes en r , borrar r de R

Ordenar las reglas por su error estimado (de menos a mas) y considerar estasecuencia cuando se clasifiquen instancias


Algoritmo C4.5

C4.5Poda pesimista: C4.5 suele estimar el error e por resustitucion, perocorrigiendolo hacia una posicion pesimista: da la aproximacion e + 1.96 ∗ σ, conσ una estimacion de la desviacion tıpica

Por que usar reglas en vez del arbol?

Podemos podar contextos (caminos), en vez de subarbolesFaciles de entender

Ultima version: C4.8, que es el C4.5 revision 8, ultima version publica de estafamilia de algoritmos antes de la implementacion comercial C5.0⇒ implementado en WEKA como J48


Indice

1 Introduccion


3 Mejoras a ID3

4 C4.5


6 Conclusiones


Arboles de regresion y arboles de modelos

Variable clase continua (prediccion numerica)Generalizar estas ideas para dar funciones de regresion continuas

Arbol de regresion: en las hojas el valor representa el valor medio de larespuesta de las instancias que llegan a esa hoja

Es lo que utiliza el sistema CART [Breiman et al., 1984]Aproxima la funcion objetivo mediante una funcion constante a trozosSirve para cualquier tipo de atributos

Arbol de modelos de regresion: en las hojas hay un modelo de regresion linealpara predecir la respuesta de las instancias que llegan a esa hoja

Algoritmo M5 [Quinlan, 1992] y M5’ [Wang y Witten, 1997]Todo tipo de atributos, especialmente continuos

Arboles de regresion son un caso particular de arboles de modelos de regresion


Arboles de modelos de regresion

Algoritmos M5 y M5’M5 genera arboles de decision similares a los de ID3

Escoge el atributo que minimiza la variacion en los valoresde la clase que resulta por cada ramaLas hojas son modelos lineales

M5’ introduce mejoras para:Tratar atributos discretosTratar valores perdidosReducir el tamano del arbol



Ejemplo209 configuraciones diferentes de ordenadores:

Salida (potencia de procesamiento) y atributos son continuos



EjemploEcuacion de regresion (a) y arbol de regresion (b)



EjemploArbol de modelos de regresion:



Fases de los algoritmos M5 y M5’Construir el arbolEstimar el errorConstruir modelos lineales en cada nodo intermedio delarbolSimplificar los modelos linealesPodar nodosSuavizar (las predicciones)



Construccion del arbol con M5Sea T el conjunto de ejemplos que llegan a un nodoLa desviacion tıpica de los valores de la clase que llegan aun nodo se trata como medida del error en ese nodoMinimizar la variacion en los valores de la clase queresultan por cada rama:

Calcular la desv. tıpica SD de la clase en T (≈ error en T )Calcular la reduccion esperada del error cuando se usa unatributo determinado

RSD = SD(T )−∑

i|Ti ||T | SD(Ti)

donde Ti son los conjuntos que resultan al partir el nodo deacuerdo al atributo escogidoEscoger el atributo que maximiza dicha reduccion–Que disminuya mucho la dispersion al bajar de nivel



Tratar atributos discretosLos atributos X discretos se tratan transformandolosprimero en varias variables binarias:Antes de construir el arbol, hacer:

Para cada valor de X , promediar sus correspondientesvalores de la clase. Ordenar los valores de X de acuerdo aestoSi X toma k valores, reemplazar X por k − 1 var. binarias:la i-esima vale 0 si el valor es uno de los primeros i en elorden y vale 1 e.o.c.



Ejemplo de M5: 2 atributos continuos y 2 discretosDiscretos son motor y screw (5 valores). Clase = tiempo elevacion sistema de servo

Orden de sus valores fue D,E ,C,B,A para ambos



Usandolos para clasificacion [Frank et al., 1998]Generar data sets de cada clase vs resto, del mismo tamano que el original.

Salidas fi aproximan la probabilidad. Escoger la mas alta


Extensiones

MARS: Multivariate Adaptive Regression Splines[Friedman, 1991]

Generalizacion continua de CARTFunciones base son un producto de funciones splinesUna variable puede ser elegida varias vecesLos test en los nodos pueden ser multivariantes (concombinaciones lineales de variables)


Indice

1 Introduccion


3 Mejoras a ID3

4 C4.5


6 Conclusiones


Conclusiones

Arboles de decisionAlgoritmo ID3 selecciona de forma voraz el siguiente mejoratributo a anadir al arbolEvitar sobreajuste es un aspecto importante paraconseguir que el arbol generalice bien⇒ Podas del arbolGran variedad de extensiones del ID3: manejar atributoscontinuos, con valores missing, otras medidas deseleccion, introducir costesClase continua: arboles de modelos de regresion (M5) conregresiones lineales en las hojas


Software

Arboles con WEKAPestana Classifier⇒ Trees

Id3 J48 M5P


Bibliografıa

TextosAlpaydin, E (2004) Introduction to Machine Learning, MIT Press [Cap. 9]

Duda, R., Hart, P.E., Stork, D.G. (2001) Pattern Classification, Wiley [Cap. 8]

Hernandez-Orallo, J., Ramırez, M.J., Ferri, C. (2004) Introduccion a la Minerıade Datos, Pearson Educacion [Cap. 11]

Mitchell, T. (1997) Machine Learning, McGraw-Hill [Cap. 3]

Webb, A. (2002) Statistical Pattern Recognition Wiley [Cap. 7]

Witten, I., Frank, E. (2005) Data Mining, Morgan Kaufmann, 2a ed. [Secciones4.3, 6.1, 6.5, 10.4]


Bibliografıa

ArtıculosQuinlan, J.R. (1986) Induction of trees, Machine Learning, 1, 81-106. [ID3]

Breiman, L., Friedman, J.H., Olshen, R.A., Stone, C.J. (1984) Classification andRegression Trees, Wadsworth. [CART]

Quinlan, J.R. (1993) C4.5: Programs for Machine Learning, Morgan Kaufmann.[C4.5]

Quinlan, J.R. (1992) Learning with continuous classes, Proc. of the 5thAustralian Joint Conference on AI, 343-348. [M5]

Wang, Y., Witten, I. (1997) Induction of model trees for predicting continuousclasses, Proc. of the Poster Papers of the ECML, 128-137 [M5’]

Frank, E., Wang, Y., Inglis, S., Holmes, G., Witten, I. (1998) Using model trees forclassification, Machine Learning, 32, 63-76

Friedman, J.H. (1991) Multivariate adaptive regression splines, Annals ofStatistics, 19, 1-141 [MARS]


Tema B.6: ARBOLES DE CLASIFICACION

Concha Bielza, Pedro Larranaga

Departamento de Inteligencia ArtificialFacultad de Informatica, Universidad Politecnica de Madrid

Aprendizaje Automatico

Documents

Arboles de Clasificacion