Scribd
Cargar
6 vistas25 páginas

Árboles de Clasificación en Aprendizaje Automático

Árboles de decision

Cargado por

leon_ceibo4289
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPT, PDF, TXT o lee en línea desde Scribd
6 vistas25 páginas

Árboles de Clasificación en Aprendizaje Automático

Árboles de decision

Cargado por

leon_ceibo4289
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPT, PDF, TXT o lee en línea desde Scribd

Aprendizaje Automatizado

Árboles de
Clasificación
Á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.
Á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?
Play Tennis

Outlook

Sunny Overcast Rain

Humidity Yes Wind

High Normal Strong Weak

No Yes No Yes
Play Tennis

 Disyunción de conjunciones:

(Outlook = Sunny And Humidity = Normal)


Or (Outlook = Overcast)
Or (Outlook = Rain And Wind = Weak)
Play Tennis
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.
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.
Algoritmos: ID3 (Interactive
Dichotomizer Version 3)

 Entropía
Entropí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
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
Entropía y proporción de positivos
Ganancia de información

 Midela reducción esperada de entropía


sabiendo el valor del atributo A
Gain(S,A) 
Entropía(S) - vValores(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 prop. de
de humedad
humedad normal
Play Tennis
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.


Play
Tennis
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’.
Índice de diversidad de Gini
Índice de diversidad de Gini

A es el atributo para ramificar el árbol.


i

M es el número de valores diferentes del


i
atributo Ai.
p(A ) es la probabilidad de que Ai tome
ij
su j-ésimo valor (1 <= j <= Mi).
Índice de diversidad de Gini

p(C |Aij) es la probabilidad de que un


k
ejemplo pertenezca a la clase Ck cuando su
atributo Ai toma su j-ésimo valor.

p(¬C |Aij) es 1 - p(Ck|Aij).


k
 Este índice es utilizado como una medida de
impureza de la información al igual que la
entropía.
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
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'})
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
Matlab - Statistics Toolbox

>> view(t)
Matlab - Statistics Toolbox

 Clasificar datos:
sfit = eval(t,meas);

 Computar la proporción de clasificados


correctamente:
pct = mean(strcmp(sfit,species))
pct =
0.9800
Matlab - Statistics Toolbox

 Calcular el promedio de errores al cuadrado:


mse = mean((sfit - species).^2)

 Podar el árbol:
t2 = prune(t, 'level', 1)

También podría gustarte