Departamento de Informática
Área Métodos y Modelos Cuantitativos
Reconocimiento
de Formas en
Data Mining
Profesor : Héctor Allende O.
Departamento de Informática
Área Métodos y Modelos Cuantitativos
Árboles de clasificación
en Reconocimiento de
Formas
Alumno : Sergio Ahumada N.
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
Contenidos
1. Introducción
2. Construcción del árbol de clasificación
3. Selección de particiones
4. Regla de asignación de clases
5. Criterio de parada
6. Ejemplos
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
1. Introducción
• Características principales
– Aproximación radicalmente distinta
– Uno de los métodos de aprendizaje inductivo supervisado
no paramétrico más utilizado
– Una forma de representar el conocimiento obtenido en el
proceso de aprendizaje inductivo:
* La estructura resultante de la partición recursiva de P a
partir de un conjunto de prototipos S
* Organización jerárquica de P que se modela con una
estructura de tipo árbol
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
1. Introducción
– Esquema general estructural
* Nodos interiores: una pregunta sobre un atributo
concreto (con un hijo por cada posible respuesta)
* Nodos hoja: están etiquetados y representan una
decisión o clasificación
– Modelos: ID3, C4, C4.5, ..., CART
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
1. Introducción
• Metodología.
1. Aprendizaje: Construcción del árbol a partir de S
2. Clasificación: Consiste en el etiquetado de un patrón, X,
independiente del conjunto de aprendizaje.
Responder a las preguntas asociadas a los nodos interiores
utilizando los valores de los atributos de X.
Repetir el proceso de evaluación desde el nodo raíz del
árbol hasta alcanzar una hoja
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
1. Introducción
1. Aprendizaje:
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
1. Introducción
2. Clasificación:
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
1. Introducción
• Ejemplo 1:
Un A.C. para un problema con J = 3 y d = 25
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
1. Introducción
• Ejemplo 1:
• El problema es de dimensionalidad d = 25
• Observar las pocas variables utilizadas (6/25)
• Cada pregunta tiene asociadas dos únicas respuestas
(si o no)  particiones binarias (CART)
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
1. Introducción
• Ejemplo 2: Introducción al aprendizaje (1)
– Problema de clasificación no separable linealmente
– J=2, d=2, N=46 (N1=26 y N2=20)
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
1. Introducción
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
1. Introducción
Primera partición
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
1. Introducción
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
1. Introducción
Segunda partición
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
1. Introducción
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
1. Introducción
Resumen del proceso de partición.
Las regiones de decisión tiene forma de paralelepípedos
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
1. Introducción
• Ejemplo 3: Introducción al aprendizaje (2)
– Las particiones se hacen con hiperplanos arbitrarios
Primera partición (alternativa)
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
1. Introducción
Segunda partición (alternativa)
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
1. Introducción
Tercera partición (alternativa)
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
1. Introducción
Cada nodo tiene asociada una región en P
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
1. Introducción
• ¿Qué representa un árbol de clasificación?
Un árbol de clasificación T representa una
partición recursiva del espacio de representación,
P, realizada en base a un conjunto de prototipos, S.
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
1. Introducción
• Nodos de T, regiones en P y conjuntos en S.
1. Cada nodo de T tiene asociado un subconjunto de
prototipos de S.
2. El nodo raíz tiene asignado el conjunto completo
3. Cada hoja, t, tiene asociada una región, Rt, en P.
~
Si T es el conjunto de nodos hoja del árbol T :
R
~
tT
t
P
Los conjuntos de prototipos asignados a los nodos hoja
constituyen una partición de P
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
1. Introducción
4. Cada nodo no terminal tiene asociada una región en P,
que es la unión de las regiones asociadas a los nodos hoja
del subárbol cuya raíz es ese nodo.
5. La unión de los conjuntos de prototipos asignados a los
nodos de un mismo nivel da como resultado el conjunto
inicial
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
2. Construcción de árbol de clasificación
• Constituye la fase de aprendizaje.
• Esquema recursivo:
1. El avance está basado en la partición de un nodo de
acuerdo a alguna regla, normalmente evaluando una
condición sobre el valor de alguna variable:
Los prototipos que verifican la condición se asignan
a uno de los dos nodos hijo (normalmente el
izquierdo) y los restantes, al otro.
Si un nodo se particiona  nodo intermedio.
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
2. Construcción de árbol de clasificación
2. El caso base o condición de parada tiene como objetivo
detener el proceso de partición de nodos.
Si se verifica la condición de parada  nodo hoja.
Los prototipos asociados a un nodo hoja constituyen
un agrupamiento homogéneo, por lo que al nodo se
le asigna una etiqueta.
• En ocasiones, se poda el árbol resultante utilizando
alguna regla de poda.
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
2. Construcción de árbol de clasificación
• Puntos clave en la construcción del árbol.
1. ¿De qué forma se hacen las particiones y se selecciona la
mejor de entre las posibles en cada momento?
1.1 ¿Cómo se formulan las preguntas? ó ¿De qué tipo
son las condiciones a evaluar para formar una
partición?
1.2 ¿Qué partición es la mejor?
2. ¿Cual es el criterio para determinar que un nodo es
homogéneo? ó ¿Cuando se debe declarar un nodo como
terminal, o por el contrario, continuar su división?
3. ¿Cómo asignar una etiqueta a un nodo terminal?
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
2. Construcción de árbol de clasificación
• Ejemplo. Construcción de un árbol.
Supongamos el siguiente problema:
– d = 25
–J=3
– N = 300 (Ni = 100, i = {1,2,3})
1. Construcción del nodo raíz.
Nodo raíz del árbol
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
2. Construcción de árbol de clasificación
2. Partir el nodo raíz.
Objetivo: Seleccionar la mejor partición del nodo
raíz entre todas las posibles.
2.1 Examinar todas las particiones de la forma
¿ X1  C ?
donde:
min( X 1 )  C  max( X 1 )
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
2. Construcción de árbol de clasificación
Por ejemplo, C = 1.1 Los prototipos para los que X1 < 1.1
van al nodo izquierdo, los otros, al derecho.
Partición asociada a ¿X1 < 1.1?
Guardar la mejor partición, P.e. ¿X1 < 10.7?
2.2 Repetir el proceso anterior para X2, X3, ..., X25
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
2. Construcción de árbol de clasificación
2.3 Seleccionar la mejor partición entre las mejores de X1,
X2, X3, ...,X25
P.e. ¿X8 < 3.2?
Partición asociada a ¿X8 < 3.2?
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
2. Construcción de árbol de clasificación
3. Repetir el paso 2 para los nodos hijo.
Por ejemplo, sea ¿X3 < -0.8? la mejor partición para el
nodo izquierdo y ¿X1 < 17.9? la mejor para el derecho.
Árbol resultante de partir el árbol anterior
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
2. Construcción de árbol de clasificación
* Los nodos 4 y 5 diferencian claramente las clases 2 y 1,
respectivamente, mientras que en los nodos 6 y 7 se
diferencian las clases 2 y 3, respectivamente.
* Las particiones efectuadas han ido “definiendo” una
clase mayoritaria en cada nodo resultante  han ido
aumentando la pureza de los nodos.
* Este proceso de división puede continuar para cada uno
de los 4 nodos o, para cada caso, plantearse si debemos
detenernos.
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
2. Construcción de árbol de clasificación
4. ¿Parada?
* Establecer el criterio de parada para obtener un buen
árbol de decisión no es sencillo.
* Uno muy simple: un nodo se declarará terminal si la
clase dominante tiene más del 60% de los prototipos
asociados a ese nodo.
• 4. N(4) = 78. 60% = 46.8. N2(4) = 53  Parar.
• 5. N(5) = 83. 60% = 49.8. N1(5) = 51  Parar.
• 6. N(6) = 45. 60% = 27.0. N2(6) = 25  Seguir.
• 7. N(7) = 94. 60% = 56.4. N3(7) = 65  Parar.
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
2. Construcción de árbol de clasificación
Los nodos 4, 5 y 7 se declaran nodos hoja
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
2. Construcción de árbol de clasificación
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
2. Construcción de árbol de clasificación
A) Árbol resultado de partir el nodo 6. B) Final
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
3. Selección de las particiones
¿De qué forma se hacen las particiones y se
selecciona la mejor de entre las posibles en cada
momento?
• Una partición divide un conjunto de prototipos en
conjuntos disjuntos.
En CART: particiones binarias.
• Objetivo de una partición: Incrementar la homogeneidad
(en términos de clase) de los subconjuntos resultantes
que sean más puros que el conjunto originario.
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
3. Selección de las particiones
• Cada partición tiene asociada una medida de pureza:
- Para la selección de la mejor partición.
- Como criterio de parada (no es muy recomendable)
• Puntos a estudiar:
- ¿Cómo se formulan las preguntas?
- ¿Qué partición es la mejor?
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
3.1 Formulación de la regla de partición
¿Cómo se formulan las preguntas?
• Introducción.
Sea Q el conjunto de preguntas binarias de la forma:
¿ X  A ?,
A P
El conjunto Q genera un conjunto de particiones s en cada
nodo t. Un nodo t se particiona en tL y tR.
- Los casos de t que verifican la condición ¿X A? se
asignan al nodo izquierdo, tL,
tL  t  A
- Los casos de t que no verifican la condición se asignan a tR,
tR  t  A
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
3.1 Formulación de la regla de partición
• Conjunto estándar de preguntas.
1. Cada partición depende de un único atributo.
2. Si Xi es un atributo categórico, que toma valores en
{c1,c2,...,cL}, Q incluye las preguntas:
¿ Xi C?
donde C es un conjunto de entre los subconjutos de
{c1,c2,...,cL}.
P.e. Si X2 toma valores en {Rojo, Verde, Azul},
¿X2 {Rojo}?, ¿X2 {Verde}?, ¿X2 {Azul}?
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
3.1 Formulación de la regla de partición
3. Si Xi es un atributo continuo, Q incluye las preguntas:
¿ Xi  v?
donde v es valor real, teóricamente cualquiera. En CART,
v es el punto medio de dos valores consecutivos de Xi
P.e. Si X1 es real, con valores 0.1, 0.5, 1.0,
¿X1  (0.1 + 0.5)/2?, ¿X1  (0.5 + 1.0)/2?
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
3.2 Criterios de partición
¿Qué partición es la mejor?
Cada partición tiene asociada una medida de pureza:
Se trata de incrementar la homogeneidad de los
subconjuntos resultantes de la partición
 que sean más puros que el conjunto originario.
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
3.2 Criterios de partición
• Función de impureza, 
Una función  definida sobre J-uplas (c1,c2,...,cJ), tales que:
a) cj  0 para j = 1,2,...,J y b)  j c j  1 , con las siguiente
propiedades
i)  tiene un único máximo en (1/J, 1/J, ..., 1/J).
ii)  alcanza su mínimo en
(1,0,0,...,0), (0,1,0,...,0), ..., (0,0,0,...,1)
y el valor mínimo es 0.
iii)  es una función simétrica de c1, c2, ..., cJ
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
3.2 Criterios de partición
• Medida de impureza de un nodo, i(t)
Dada una función de impureza , definamos la medida de
impureza de cualquier nodo t, i(t), como:
i(t )   p(1 | t ), p(2 | t ),..., p( J | t )
donde p(j|t) es la probabilidad de que un caso (prototipo)
del nodo t sea de clase j. Empíricamente: la proporción de
casos de clase j en el nodo t:
p( j | t ) 
N j (t )
N (t )
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
3.2 Criterios de partición
Observar que:
a) p(j|t)  0
b)  j p( j | t )   j
N j (t )
N (t )

1
N (t )

j
N j (t )  1
i) Máxima impureza (resp. mínima pureza): cuando todas
las clases están igualmente representadas en t.
ii) Mínima impureza (resp. máxima pureza): cuando en t
sólo hay casos de una sola clase.
iii) Cualquier permutación de los cj produce el mismo
resultado. P.e., para dos nodos tj  tk, i(tj) = (0.7, 0.2,
0.1) = (0.2, 0.1, 0.7) = i(tk)
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
3.2 Criterios de partición
• Bondad de la partición s en un nodo t, (s,t)
Para cualquier nodo t, supongamos la partición candidata s,
que divide t en tL y tR, de forma que una proporción pL de
los casos de t van a tL y una proporción pR van a tR:
La partición s divide t en tL y tR
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
3.2 Criterios de partición
La bondad de la partición s en un nodo t, (s,t), se define
como el decrecimiento en impureza conseguido con ella:
(s, t )  i(s, t )  i(t )  pL i(t L )  pR i(t R )
Si conocemos cómo calcular i(t), para cada s podemos
calcular (s,t) y seleccionar la mejor partición s como la
que proporciona la mayor bondad (s,t).
• Impureza de un árbol, I(T)
Para establecer el efecto que produce la selección de la
mejor partición en cada nodo sobre el árbol final
necesitamos una medida de la impureza global del árbol.
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
3.2 Criterios de partición
Sea I(t) = i(t)p(t), donde p(t) es la probabilidad de que un
caso cualquiera esté en el nodo t.
La impureza del árbol T, se define como:
I (T )   I (t )   i(t ) p(t )
~
tT
~
tT
donde T~ es el conjunto de nodos terminales de T.
La selección continuada de las particiones que maximizan i(s,t)
es equivalente a seleccionar las particiones que minimizan la
impureza global I(T).
Esto significa que la estrategia de selección de la mejor partición
en cada nodo conduce a la solución óptima considerando el árbol
final
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
3.2 Criterios de partición
• Criterios de medida de impureza
* Medida de entropía.
J
i(t )   p( j | t ) log p( j | t )
j 1
Se asume que 0 log0 = 0
* Índice de Gini.
Mide la diversidad de clases en un nodo.
i (t ) 
J
J
i , j 1
i j
j 1
2
p
(
i
|
t
)
p
(
j
|
t
)

1

p
(
j
|
t
)


Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
3.2 Criterios de partición
¡Importante!
La elección del criterio de partición depende del
problema, aunque el clasificador generado no
parece muy sensible a esta elección, como
demuestra la experiencia.
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
4. Regla de asignación de clases
¿Cómo asignar una etiqueta a un nodo terminal?
• Regla de asignación de clase
~
Asigna una clase j a cada nodo terminal t  T. La clase
~
asignada al nodo t  T se notará por j(t)
La forma más simple:
Elección de la clase para la cual p(i|t) es máxima
j (t )  j si
p( j | t )  max p(i | t )
i1, 2,..., J
Si el máximo se alcanza para dos o más clases, asignar
arbitrariamente cualquiera de ellas.
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
5. Criterio de parada
¿Cual es el criterio para determinar que un nodo es
homogéneo? o ¿Cuándo se debe declarar un nodo
terminal, o por el contrario, continuar su división?
• Criterios simples (insatisfactorios)
1. Mayoría absoluta.
2. Umbral de decrecimiento en impureza.
Fijar un valor  > 0. t será nodo terminal si:
max i( s, t )  
s
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
5. Criterio de parada
-  bajo, muy “exigente”  árboles muy grandes.
-  alto, muy “permisivo”  menos altura.
En un momento dado pueden encontrarse nodos en los que
maxs{i(s,t)}es pequeño, pero una posterior partición de
sus descendientes podría proporcionar mayores
decrecimientos de impureza.
Puede verse como una poda de ambas ramas
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
5.1 Estimadores de error
• Objetivo:
Estimar R*(T), el error real asociado a T.
• Estimador por resustitución del error global de
clasificación de T, R(T):
R(T )   R(t )   r (t ) p(t )
~
tT
~
tT
donde r(t) = 1 - maxj{p(j|t)} y p(t) es la probabilidad de
que un caso cualquiera esté en el nodo t.
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
5.1 Estimadores de error
¡Muy importante! (Breiman)
Si T’ se construye a partir de T a través de una partición
arbitraria de un nodo terminal de T, entonces,
R(T ' )  R(T )  R(t )  R(t L )  R(t R )
Si R(T) decrece conforme el tamaño del árbol se hace
mayor, podemos construir árboles en los que los nodos
terminales tengan un solo prototipo. En éstos R(T)=0
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
5.1 Estimadores de error
~
Error de clasificación según | T |. R(T): estimador por
resustitución. Rts(T): estimador por conjunto de prueba
- Conclusión:
R(T), induce a sobreaprendizaje, esto es, el clasificador
está muy ajustado al conjunto de entrenamiento,
proporcionando índices de error muy bajos, pero que no
son realistas ya que no son extrapolables a otros
conjuntos.
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
5.1 Estimadores de error
Se necesita establecer un estimador más certero del error
real: un estimador honesto de R*(T).
a) Rts(T), Estimador por conjunto de prueba.
b) Rcv(T), Estimador por validación cruzada.
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
5.1 Estimadores de error
• Procedimiento recomendado para establecer un
criterio de parada.
1. Podar en lugar de impedir el crecimiento.
Construir un árbol muy grande y podar hacia la raíz de
manera adecuada.
- Se podan subárboles que producen pequeños
beneficios de bondad.
- Resultado: secuencia decreciente (en tamaño) de
árboles “anidados”
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
5.1 Estimadores de error
2. Utilizar estimadores honestos de R*(T).
Se usarán para seleccionar el árbol del tamaño adecuado
de entre la secuencia de árboles podados. Dependerá del
tamaño del conjunto de entrenamiento:
- Rts(T) Estimador por conjunto de prueba.
Conjunto de aprendizaje suficientemente grande.
- Rcv(T) Estimador por validación cruzada.
Conjunto de aprendizaje pequeño.
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
5.2 La estrategia de poda
Resulta más eficiente podar un árbol que detener
su crecimiento (Breiman)
1. Particionar hasta que se cumpla:
a) sea totalmente puro, o
b) N(t) < Nmin (habitualmente Nmin = 5)
Se obtiene un árbol muy grande, Tmax.
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
5.2 La estrategia de poda
2. Podar este árbol, obteniendo una secuencia decreciente
y anidada de árboles.
Si T’ se obtiene a partir de T por poda, T’ es un
subárbol podado de T y se denota por T’ T
{t1}  ...  T1  T2  Tmax
Uno de estos árboles será el que se seleccione.
Para realizar esta selección se asocia una medida de
error a cada árbol de la secuencia y se escoge aquel
que tenga asociado el menor error
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
5.3 Poda por mínimo coste-complejidad
• Complejidad de un árbol.
Para cualquier subárbol T  Tmax se define su complejidad
~
como el número de nodos terminales, | T |.
• Medida de coste-complejidad
Medida de coste-complejidad, R(T):
R(T) = R(T) +  | T~|
donde  es un valor real (  0) (parámetro de complejidad)
que se interpreta como el coste de complejidad por nodo
terminal.
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
5.3 Poda por mínimo coste-complejidad
R(T) es una combinación lineal del coste del árbol y su
complejidad, ponderada apropiadamente.
Para cada , se trata de encontrar el árbol T(), T()  Tmax,
que minimiza R(T),
R(T()) = min R (T )
TTmax
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
5.3 Poda por mínimo coste-complejidad
• Ejemplo
1. Sea  = 0.10
1.1 Considerar el subárbol T1 (figura A)
~
Sea R(T1) = 0.25, y | T1 | = 3
~
R(T1) = R(T1) +  | T1 | = 0.25 + (0.10 x 3) = 0.55
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
5.3 Poda por mínimo coste-complejidad
1.2 Supongamos que se reemplaza el subárbol derecho de
T1 por una hoja, obteniendo T2 (figura B)
Sea R(T2) = 0.38, y | T~2 | = 2
~
R(T2) = R(T2) +  | T2| = 0.38 + (0.10 x 2) = 0.58
2. Sea  = 0.15 (R(T1) y R(T2) se mantienen).
R(T1) = R(T1) +  | T~1 | = 0.25 + (0.15 x 3) = 0.70
R(T2) = R(T2) +  | T~2| = 0.38 + (0.15 x 2) = 0.68
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
5.3 Poda por mínimo coste-complejidad
• Discusión.
- Problema: escoger un valor apropiado para .
- Solución: incrementar gradualmente , empezando con
 = 0. Este procedimiento genera una secuencia finita y
única de subárboles anidados
{t1}  ...  T2  T1
donde Tk = T(k), 1 = 0
- El procedimiento concreto en que se implementa este
método de poda resulta demasiado complejo para el ámbito
del curso (más detalles en [B.1])
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
5.3 Poda por mínimo coste-complejidad
A grandes rasgos: Empieza con T1 (1=0), encuentra la rama
más débil de T1 y la poda, creando T2 cuando  alcanza 2. A
continuación encuentra la rama más débil de T2 y la poda,
creando T3 cuando  alcanza 3 , ...
Conforme crece , tiende a podar menos nodos ya que los
árboles son más pequeños (menos complejos) y el resultado
es una secuencia decreciente de subárboles.
{t1} = T9  ...  T2  T1
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
5.4 Selección del mejor árbol podado
• Objetivo:
Dada una secuencia decreciente de subárboles:
{t1}  ...  T2  T1
Se trata de seleccionar uno de éstos como el óptimo.
• ¿Cómo?
Se asocia una medida de error a cada árbol de la
secuencia y se escoge aquel que tenga asociado el menor
error.
Escoger Tk0 si Rˆ (Tk0) = mink Rˆ (Tk)
¡Cuidado! ¿Cómo obtener honestamente R*(Tk)?
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
5.4 Selección del mejor árbol podado
• Estimación por conjunto de prueba.
- Aplicable si el conjunto de entrenamiento es
suficientemente grande.
- S  Sl y St
Sl es el conjunto de aprendizaje
Se usa para construir Tmax, y a partir de él,
{t1}  ...  T2  T1
St es el conjunto de prueba
Para cada Tk, se clasifican las muestras de St utilizando
el clasificador Tk y se obtiene Rts(Tk).
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
5.4 Selección del mejor árbol podado
- El árbol más adecuado, Tk0, es el que verifica:
Rts(Tk0) = mink Rts(Tk)
• Estimación por validación cruzada.
- Recomendado cuando el conjunto de entrenamiento tiene
pocos prototipos.
- El árbol más adecuado, Tk0, es el que verifica
Rcv(Tk0) = mink Rcv(Tk)
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
5.4 Selección del mejor árbol podado
• La regla 1 SE.
- Calibrar la incertidumbre de los estimadores Rts(T) y
Rcv(T) calculando su error estándar (SE).
ts
1

R
(T )
SE ( R ts (T ))  R ts (T )
| St |
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
5.4 Selección del mejor árbol podado
- Mínimo de Rˆ (Tk ) muy inestable  regla 1-SE.
1. Reducir la inestabilidad asociada a la selección del
mínimo exacto.
2. Seleccionar el árbol más simple cuya bondad es
comparable a mink Rˆ (Tk )
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
5.4 Selección del mejor árbol podado
- Regla 1 SE.
Si Tk0 es tal que Rˆ (Tk0 ) = mink Rˆ (Tk ), entonces, el árbol
seleccionado será Tk1, donde k1 es el máximo k que
satisface:
Rˆ (Tk1 )  Rˆ (Tk0 ) + SE( Rˆ (Tk0 ))
Se selecciona Tk1 al ser el árbol más simple (con mayor
subíndice de la secuencia {t1},...,Tk1,...,Tk0,...,T1) que
verifica que Rˆ (Tk1 )  Rˆ (Tk0 ) + SE( Rˆ (Tk0 ))
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
5.4 Selección del mejor árbol podado
La regla 1-SE sobre el ejemplo anterior
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
6. Ejemplo 1
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
6. Ejemplo 1
• Tmax se construyó con Nmin = 1
• SE(Rts(Tk)) < 0.07 (despreciables).
• Para Rcv(Tk) se indica SE(Rcv(Tk)). V = 10
* T2 : Rcv(T2) = mink Rcv(Tk)
** T6 es el árbol seleccionado por la regla 1 SE.
Rcv(T2) + SE(Rcv(Tk2)) = 0.27 + 0.03 = 0.30
T1(0.30), T2(0.27), T3(0.30), T4(0.30) y T6(0.30)
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
6. Ejemplo 2
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
6. Ejemplo 2
• Nmin = 1 y SE(Rts(Tk)) < 0.07 (despreciables).
* T7 : Rcv(T7) = mink Rcv(Tk) y Rts(T7) = mink Rts(Tk)
** T7 es el árbol seleccionado por la regla 1 SE.
Rcv(T7) + SE(Rcv(Tk7)) = 0.31 + 0.03 = 0.34
T6(0.32) y T7(0.31)
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
6. Ejemplo 3
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
6. Ejemplo 3
• Nmin = 1 y SE(Rts(Tk)) < 0.07 (despreciables).
* T4 : Rcv(T4) = mink Rcv(Tk)
** T6 es el árbol seleccionado por la regla 1 SE.
Rcv(T4) + SE(Rcv(Tk4)) = 0.28 + 0.03 = 0.31
T1(0.31), T2(0.31), T3(0.30), T4(0.28), T5(0.29) y T6(0.29)
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
6. Ejemplo 4
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
6. Ejemplo 4
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
6. Ejemplo 5
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
7. Bibliografía
• [B.1] Breiman, L. et al. Classification and Regression Trees
(1984)
• [B.2] Cortijo, F. Un estudio comparativo de métodos de
clasificación de imágenes de multibanda (1995)
• [B.3] Fukunaga, K. Introduction to statistical pattern
recognition (1998)
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
Descargar

Introduccion al reconocimiento de formas