![Page 1: Aprendizaje Automatizado Ár boles de Clasificación](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4581a28abb57c90b681/html5/thumbnails/1.jpg)
Aprendizaje Automatizado
Árboles de Clasificación
![Page 2: Aprendizaje Automatizado Ár boles de Clasificación](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4581a28abb57c90b681/html5/thumbnails/2.jpg)
Árboles de Clasificación
Entrada: Objetos caracterizables mediante propiedades.
Salida: – En árboles de decisión: una decisión (sí o no).– En árboles de clasificación: una clase.
Conjunto de reglas.
![Page 3: Aprendizaje Automatizado Ár boles de Clasificación](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4581a28abb57c90b681/html5/thumbnails/3.jpg)
Árboles de Clasificación
Se clasifican las instancias desde la raíz hacia las hojas, las cuales proveen la clasificación.
Cada nodo especifica el test de algún atributo. Ejemplo: Si (Outlook = Sunny, Temperature = Hot, Humedity = High,
Wind = Strong)
Juego al tenis?
![Page 4: Aprendizaje Automatizado Ár boles de Clasificación](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4581a28abb57c90b681/html5/thumbnails/4.jpg)
Play Tennis
Outlook
WindHumidity
Sunny
No YesNoYes
WeakStrongNormalHigh
Yes
RainOvercast
![Page 5: Aprendizaje Automatizado Ár boles de Clasificación](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4581a28abb57c90b681/html5/thumbnails/5.jpg)
Play Tennis
Disyunción de conjunciones:
(Outlook = Sunny And Humidity = Normal)
Or (Outlook = Overcast)
Or (Outlook = Rain And Wind = Weak)
![Page 6: Aprendizaje Automatizado Ár boles de Clasificación](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4581a28abb57c90b681/html5/thumbnails/6.jpg)
Play Tennis
![Page 7: Aprendizaje Automatizado Ár boles de Clasificación](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4581a28abb57c90b681/html5/thumbnails/7.jpg)
Problemas Apropiados
Las instancias pueden ser representadas por pares (atributo, valor) .
La función objetivo tiene valores discretos (o pueden ser discretizados).
Pueden ser requeridas descripciones en forma de disjunción.
Posiblemente existen errores en los datos de entrenamiento (robustos al ruido).
Posiblemente falta información en algunos de los datos de entrenamiento.
![Page 8: Aprendizaje Automatizado Ár boles de Clasificación](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4581a28abb57c90b681/html5/thumbnails/8.jpg)
Algoritmo básico para obtener un árbol de decisión
Búsqueda exhaustiva, en profundidad (de arriba hacia abajo), a través del espacio de posibles árboles de decisión (ID3 y C4.5).
Raíz: el atributo que mejor clasifica los datos
Cuál atributo es el mejor clasificador?
respuesta basada en la ganancia de información.
![Page 9: Aprendizaje Automatizado Ár boles de Clasificación](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4581a28abb57c90b681/html5/thumbnails/9.jpg)
Algoritmos: ID3 (Interactive Dichotomizer Version 3)
EntropíaEntropía(S) - p log2 p - p log2 p
p = proporción de ejemplos positivos.
p = proporción de ejemplos negativos.
S: conjunto de datos actual.
Por ejemplo, en el conjunto de datos Play Tennis
p= 9/14, p = 5/14 y E(S) = 0.940
En general: Entropía(S) = - i=1,c pi log2 pi
![Page 10: Aprendizaje Automatizado Ár boles de Clasificación](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4581a28abb57c90b681/html5/thumbnails/10.jpg)
Algoritmos: ID3 (Interactive Dichotomizer Version 3)
Por ejemplo:
Si S1 es el subconjunto de S en el cual
Humedity = High
Entonces:– p = 3/7
– p = 4/7
– Entropía(S1) = -3/7 log2 3/7 - 4/7 log2 4/7 = 0.985
![Page 11: Aprendizaje Automatizado Ár boles de Clasificación](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4581a28abb57c90b681/html5/thumbnails/11.jpg)
Entropía y proporción de positivos
![Page 12: Aprendizaje Automatizado Ár boles de Clasificación](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4581a28abb57c90b681/html5/thumbnails/12.jpg)
Ganancia de información
Mide la reducción esperada de entropía sabiendo el valor del atributo AGain(S,A)
Entropía(S) - vValores(A) (|Sv|/|S|)Entropía(Sv)
Valores(A): Conjunto de posibles valores del atributo A
Sv: Subconjunto de S en el cual el atributo A tiene el valor v
Ej: Gain(S, Humedad) = 0.940 - (7/14)0.985 - (7/14)0.592
proporción de
humedad alta
prop. de humedad normal
![Page 13: Aprendizaje Automatizado Ár boles de Clasificación](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4581a28abb57c90b681/html5/thumbnails/13.jpg)
Play Tennis
![Page 14: Aprendizaje Automatizado Ár boles de Clasificación](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4581a28abb57c90b681/html5/thumbnails/14.jpg)
Play Tennis
Gain(S,Outlook) = 0.246
Gain(S,Humidity) = 0.151
Gain(S,Wind) = 0.048
Gain(S,Temperature) = 0.029
Outlook es el atributo del nodo raíz.
![Page 15: Aprendizaje Automatizado Ár boles de Clasificación](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4581a28abb57c90b681/html5/thumbnails/15.jpg)
Play Tennis
![Page 16: Aprendizaje Automatizado Ár boles de Clasificación](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4581a28abb57c90b681/html5/thumbnails/16.jpg)
Algoritmo: CART (Classification and Regression Trees)
Árboles de clasificación: predicen categorías de objetos.
Árboles de regresión: predicen valores continuos.
Partición binaria recursiva. En cada iteración se selecciona la
variable predictiva y el punto de separación que mejor reduzcan la ‘impureza’.
![Page 17: Aprendizaje Automatizado Ár boles de Clasificación](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4581a28abb57c90b681/html5/thumbnails/17.jpg)
Índice de diversidad de Gini
![Page 18: Aprendizaje Automatizado Ár boles de Clasificación](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4581a28abb57c90b681/html5/thumbnails/18.jpg)
Índice de diversidad de Gini
Ai es el atributo para ramificar el árbol.
Mi es el número de valores diferentes del
atributo Ai.
p(Aij) es la probabilidad de que Ai tome
su j-ésimo valor (1 <= j <= Mi).
![Page 19: Aprendizaje Automatizado Ár boles de Clasificación](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4581a28abb57c90b681/html5/thumbnails/19.jpg)
Índice de diversidad de Gini
p(Ck|Aij) es la probabilidad de que un
ejemplo pertenezca a la clase Ck cuando su
atributo Ai toma su j-ésimo valor.
p(¬Ck|Aij) es 1 - p(Ck|Aij). Este índice es utilizado como una medida de
impureza de la información al igual que la entropía.
![Page 20: Aprendizaje Automatizado Ár boles de Clasificación](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4581a28abb57c90b681/html5/thumbnails/20.jpg)
Sobreentrenamiento
Se debe evitar el sobreentrenamiento– Parar de crecer el árbol temprano.– Postprocesamiento del árbol (poda)
Cómo?– Usar un conjunto de ejemplos de validación– Usar estadísticas
![Page 21: Aprendizaje Automatizado Ár boles de Clasificación](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4581a28abb57c90b681/html5/thumbnails/21.jpg)
Matlab - Statistics Toolbox
La clase @classregtree está diseñada para manipular árboles de regresión y árboles de decisión (CART).
Ejemplo:
>> load fisheriris;
>> t = classregtree(meas, species, 'names', {'SL' 'SW' 'PL' 'PW'})
![Page 22: Aprendizaje Automatizado Ár boles de Clasificación](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4581a28abb57c90b681/html5/thumbnails/22.jpg)
Matlab - Statistics Toolbox
t =
Decision tree for classification
1 if PL<2.45 then node 2 else node 3
2 class = setosa
3 if PW<1.75 then node 4 else node 5
4 if PL<4.95 then node 6 else node 7
5 class = virginica
6 if PW<1.65 then node 8 else node 9
7 class = virginica
8 class = versicolor
9 class = virginica
![Page 23: Aprendizaje Automatizado Ár boles de Clasificación](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4581a28abb57c90b681/html5/thumbnails/23.jpg)
Matlab - Statistics Toolbox
>> view(t)
![Page 24: Aprendizaje Automatizado Ár boles de Clasificación](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4581a28abb57c90b681/html5/thumbnails/24.jpg)
Matlab - Statistics Toolbox
Clasificar datos:
sfit = eval(t,meas);
Computar la proporción de clasificados correctamente:pct = mean(strcmp(sfit,species))
pct =
0.9800
![Page 25: Aprendizaje Automatizado Ár boles de Clasificación](https://reader035.vdocumento.com/reader035/viewer/2022062309/5665b4581a28abb57c90b681/html5/thumbnails/25.jpg)
Matlab - Statistics Toolbox
Calcular el promedio de errores al cuadrado:
mse = mean((sfit - species).^2)
Podar el árbol:t2 = prune(t, 'level', 1)