Upload
raquel-solano
View
6.454
Download
4
Embed Size (px)
DESCRIPTION
Define los diferentes algoritmos de clasificación aplicados a la Inteligencia Artificial y como construir un árbol de clasificación
Citation preview
UNIVERSIDAD TECNICA PARTICULAR DE LOJA
“La Universidad Católica de Loja”
INTELIGENCIA ARTIFICIAL AVANZADA
ÁRBOLES DE CLASIFICACIÓN
Verónica RamírezRaquel Solano
ÁRBOLES DE CLASIFICACIÓN
INTRODUCCIÓN
Dentro del aprendizaje automático el tema a tratar es árboles de clasificación o también conocidos como árboles de decisión.Los factores que han influido en su difusión son: accesibilidad a diferentes implementaciones, la explicación que aporta a la clasificación, la posibilidad de ser representados gráficamente, y la rapidez de clasificar nuevos patrones.Los árboles de clasificación están dentro de los métodos de clasificación supervisada, teniendo una variable dependiente o clase. La construcción del árbol de clasificación se realiza mediante un proceso de inducción.
DEFINICIÓN[2]
Los árboles de clasificación se basan en una estructura en forma de árbol, donde las ramas representan conjuntos de decisiones, las cuales generan reglas para la clasificación de un conjunto de datos en subgrupos de datos. Las ramificaciones se generan de forma recursiva hasta que se cumplan ciertos criterios de parada.
ESTRUCTURA DE UN ÁRBOL Nodo Raíz
Nodo Hoja
Nodo Intermedio
Nodo Padre
Nodo Hijo
Complejidad del árbol = # de nodos hoja
PROCESO DE CONSTRUCCIÓN
El proceso comienza por el nodo raíz Hacer un análisis para determinar cual es la variable
por la que hay que preguntar para dividir la muestra de entrenamiento original
El proceso pararía cuando los nodos hoja contuvieran casos de una única clase.
Es importante definir tres procedimientos:
1. ¿Cómo se realiza la selección de las divisiones?
2. ¿Cómo se toma la decisión de declarar a un nodo como intermedio o como hoja?
3. ¿Cómo se asigna la pertenencia de cada nodo hoja a las posibles clases?
Algoritmo General
PROFUNDIZANDO UN POCO
Los dos aspectos mas importantes a la hora de construir los árboles son: como se decide la división en un nodo y el criterio de parada en el desarrollo del árbol.
Las diferentes taxonomías para clasificar los tipos de árboles son: la división en función de la naturaleza de la variable dependiente, discreta o continua y el numero de ramas o hijos que se permitan salir del nodo.
Los árboles podrán ser binarios cuando solo permitan dividir cada nodo en 2, o n-arios cuando el numero de divisiones pueda ser mayor que 2.
SELECCIÓN DE LA DIVISIÓN…
Si la variable es discreta tendremos que plantearnos si desarrollamos una rama por cada una de las categorías que tiene dicha variable, o agruparlas en dos o más conjuntos.
Se aplica a árboles de clasificación.
Si la variable es continua habrá que decidir si queremos una división binaria y con que valor.
Se aplica a arboles de clasificación.
…SELECCIÓN DE LA DIVISION
Sea: tr,r=1,…l, el conjunto de nodos hijo consecuencia de dividir el nodo t.
pr= la proporción de casos de t que se distribuyen en cada uno de los hijos tr.
prj=proporción de casos de la clase j en el nodo tr
cm(m=1…M) numero de clases
Compara la heterogeneidad o impureza del nodo padre con la suma de las impurezas de los nodos hijos
Determina con que variable realizar la primera división.
EJEMPLOSe desea determinar las reglas que rigen el comportamiento de un alumno durante su vida académica para poder detectar casos que presenten riesgo de abandonar los estudios, para ello se dispone de los siguientes datos:
EJEMPLO[1]:
Patrones y variables predictoras
…EJEMPLO R1 : If X1 > 1;5 then C = 2 R2 : If 1 < X1 < 1;5 then C = 1 R3 : If X1 < 1 y X2 < 1 then C = 1 R4 : If X1 < 1 y X2 > 1 then C = 2
EJEMPLOPronostico Temperatur
aHumedad Viento Jugar
Sol Calor Alta No No
Sol Calor Alta Si No
Cubierto Calor Alta No Si
Lluvia Media Alta No Si
Lluvia Frio Normal No Si
Lluvia Frio Normal Si No
Cubierto Frio Normal Si Si
Sol Media Alta No No
Sol Frio Normal No Si
Lluvia Media Normal No Si
Sol Media Normal Si Si
Cubierto Media Alta Si Si
Cubierto Calor Normal No Si
lluvia Media Alta Si No
Variables predictorias
Variables discretas Variable dependiente
9
5
PRONOSTICO
SiSiNoNoNo
SiSiSiSi
SiSiSiNoNo
Sol
Cubierto
Lluvia
TEMPERATURA
SiSiNoNo
SiSiSiNoNo
SiSiSiNo
Calor
Media
Frío
HUMEDAD
SiSiSiNoNoNoNo
SiSiSiSiSiSiNo
Alta Normal
VIENTO
SiSiSiSiSiSiNoNoNo
SiSiSiNoNoNo
No Si
CALCULAR ENTROPIA
940,014/5log*14/514/9log*14/9])5,9([)_( 22 IraiznodoI
971,05/3log*5/35/2log*5/2])3,2([)( 22 IsolpronosticoI
0,0])0,4([)( IcubiertopronosticoI
971,05/2log*5/25/3log*5/3])2,3([)( 22 IlluviapronosticoI
693,0971,0*)14/5(0*)14/4(971,0*)14/5(])2,3[],0,4[],3,2([ IANTROPIA MEDIA
247,0693,0940,0])2,3[],0,4[],3,2([])5,9([)( IIpronosticogananciaGANANCIA
PRONOSTICO
SiSiNoNoNo
SiSiSiSi
SiSiSiNoNo
Sol
Cubierto
Lluvia
Ganancia (Pronostico)= 0.247Ganancia (Temperatura)=0.029Ganancia (Humedad) = 0.152Ganancia (viento)= 0.048
Si
PRONOSTICO
Si
Sol
Cubierto
Lluvia
HUMEDAD VIENTO
Alta NormalNo
SiSi No
No
Pronostico Temperatura
Humedad Viento Jugar
Sol Calor Alta No No
Sol Calor Alta Si No
Sol Media Alta No No
Sol Frio Normal No Si
Sol Media Normal Si Si
TABLA
Pronostico Temperatura
Humedad Viento Jugar
Cubierto Calor Alta No Si
Cubierto Frio Normal Si Si
Cubierto Media Alta Si Si
Cubierto Calor Normal No Si
Pronostico Temperatura
Humedad Viento Jugar
Lluvia Media Alta No Si
Lluvia Frio Normal No Si
Lluvia Frio Normal Si No
Lluvia Media Normal No Si
lluvia Media Alta Si No
02
2log*
2
2
2
0log*
2
02,0 22 IcaloratemperaturI
12
1log*
2
1
2
1log*
2
11,1 22 ImediaatemperaturI
01
0log*
1
0
1
1log*
1
10,1 22 IfrioatemperaturI
4.00*5
11*
5
20*
5
20,1,1,1,2,0
I
571,04,0971,00,1,1,1,2,03,2)( IIatemperaturganancia
Ganancia(Temperatura)=0,571
03
3log*
3
3
3
0log*
3
03,0 22 IaltahumedadI
02
0log*
2
0
2
2log*
0
20,2 22 InormalhumedadI
00*5
20*
5
30,2,3,0
I
971,00971,00,2,3,03,2)( IIhumedadganancia
Ganancia(humedad)=0,971
917.03
2log*
3
2
3
1log*
3
12,1 22 InovientoI
12
1log*
2
1
2
1log*
2
11,1 22 IsivientoI
950,01*5
2917,0*
5
31,1,2,1
I
021,0950,0971,01,1,2,13,2)( IIvientoganancia
Ganancia(viento)=0,021
Ganancia(Temperatura)=0,159
Ganancia(humedad)=0,159
Ganancia(viento)=0,971
ÁRBOLES PARSIMONIOSOS
Complejidad sea suficiente para resolver el problema y que sean capaces de enfrentarse a nuevos casos de una manera eficiente
No es deseable que los nodos terminales fueran homogéneos a los árboles de clasificación se les aplica la poda Pre-podaPost-poda
Pre-Poda
Van aplicando algún criterio según se va desarrollando el árbol, de manera que se decide parar el desarrollo de algunos nodos aun no siendo homogéneos del todo
Ejemplo La ganancia en información: Mínima ( > )
tD,
tD,
Post-Poda
El árbol se desarrolla del todo hasta conseguir nodos homogéneos, y posteriormente se van eliminando subárboles basándose en algún criterio (ganancia en información, x2), otros criterios para ir podando el árbol y reduciendo su complejidad
Información Incompleta: casos missing
Maneras para afrontar el problema:Estadística: rellena las variables con valores
medio o la moda del conjunto de datosEl algoritmo de construcción/clasificación sea
capaz de afrontar el problemaAñadir un nodo hijo demás a cada división para introducir en el los casos que no tienen valor definido
Repartir el caso proporcionalmente entre las ramas del nodo en el que se pregunta por el valor de la variable desconocida
Los mas conocidosAlgoritmo Variables
predictoriasTipo de división
Criterio de división
Casos missing
Método de poda
implementación
CART
(1984)
Continuas
Discretas
Binaria Ganancia
(gini index)
si Post-poda Libre
comercial
ID3
(1979)
Discretas n-aria Ganancia
(entropia)
no --- Comercial
C4.5
(1993)
Continuas
Discretas
Binaria
N-aria
Gain ratio
(entropía)
si Post-poda Libre
comercial
J4.8 Continuas
Discretas
Binaria
n-aria
Gain ratio
(entropía)
si Post-poda Libre (Weka)
C5.0 --- ---- ---- --- --- Comercial
CHAID
(1975)
Discretas n-aria x2 si Pre-poda Comercial
Referencias
[1]http://www.sc.ehu.es/ccwbayes/docencia/mmcc/docs/t10arboles.pdf
[2]http://www.eustat.es/document/datos/ct_04_c.pdf
http://www.ucm.es/info/pslogica/aprendizaje.pdf
Pronostico Temperatura
Humedad Viento Jugar
Sol Calor Alta No No
Sol Calor Alta Si No
Cubierto Calor Alta No Si
Lluvia Media Alta No Si
Lluvia Frio Normal No Si
Lluvia Frio Normal Si No
Cubierto Frio Normal Si Si
Sol Media Alta No No
Sol Frio Normal No Si
Lluvia Media Normal No Si
Sol Media Normal Si Si
Cubierto Media Alta Si Si
Cubierto Calor Normal No Si
lluvia Media Alta Si No