Técnicas Supervisadas
Aproximación no paramétrica
Reconocimiento de Patrones
2003
• Notas basadas en el curso Reconocimiento de Formas de F.Cortijo, Univ. de Granada y en el libro
Pattern Clasification de Duda, Hart y Storck
• Parte del material se extrajo de las notas:Técnicas Supervisadas II: Aproximación no paramétrica
de F.Cortijo, Univ. de Granada
Edición del conjunto de
entrenamiento
•
•
•
•
•
Objetivo:
Reducir el conjunto de referencia
Mejorar la “calidad” del mismo
Eliminar outliers
Para aumentar tasa de acierto de 1-NN
Edicion de Wilson
• Reduce prototipos problemáticos.
• Genera dependencia estadística entre los
prototipos retenidos (validación cruzada)
• Edicion con la regla k-NN
Edicion por particiones
• Realizo una partición del conjunto de
entrenamiento.
• Aplico la regla k-NN a cada prototipo pero
considerando los vecinos de una partición
particular distinta a la del prototipo.
• Desempeño depende:
– Paso de difusión
– Partición inicial
– Regla k-NN
Edicion por particiones
• Difusión: Ti generado por la partición de S
• Clasificación: prototipo usando como
referencia otro conjunto diferente
• Edición: elimina el prototipo
incorrectamente clasificado al terminar el
proceso de clasificación
• Confusión: El conjunto de prototipos
resultante contiene todos los que han sido
correctamente clasificados
Multiedición
• Para evitar la dependencia respecto a la
partición inicial se aplica en forma iterativa
el método de edición por particiones. En
cada iteración se genera una nueva partición
del conjunto de prototipos que se mantienen
sin editar.
• Edición con la regla 1-NN
Conjunto | S| iteraciones | SM|
6884
18
6653
A1
1027
8
734
A2
Figura 33: Número de prototipos
descartados por iteración.
Paro cuando en I iteraciones no hay descartes.
Reducción del coste computacional para
los métodos del vecino más cercano
• Objetivo:
– Incrementar eficacia computacional mediante la
selección de un conjunto reducido y
representativo del conjunto de prototipos
• Contrapartida:
– Genera ligera pérdida de bondad.
Métodos
Condensado de Hart
Idea:
• Un conjunto SC se dice consistente respecto a
otro conjunto S, donde SC S, si S puede
clasificarse correctamente usando los
elementos de SC como referencia.
• Selección de prototipos que determinen las
fronteras de decisión
• Incremental sin vuelta atrás
Cla
se
1
2
S
3806
7542
SM
458
267
3
5463 492
4
2796
34
5
8834 490
Tot
28441 1741
al
SM
C
6
4
11
2
16
39
Reducción del conjunto de referencia
Clase S
SM
SMC
1
3806
458
6
2
7542
267
4
3
5463
492
11
4
2796
34
2
5
8834
490
16
Total 28441 1741 39
Bondades de las clasificaciones 1-NN
Clase
S
SM
SMC
SC
1
100.00%
100.00%
100.00%
100.00%
2
99.29%
99.29%
98.58%
99.29%
3
30.10%
97.45%
96.43%
29.59%
Bondad71.63%
98.57%
97.96%
71.43%
Condensado de Hart
• Requiere un conjunto previamente editado
para asegurar la consistencia del conjunto
condensado
• No proporciona un conjunto mininal, sólo
un conjunto reducido
• Las fronteras de decisión no son tan buenas
• Conjunto condensado no es único depende
de las condiciones iniciales.
Métodos de aprendizaje
adaptativo
• LVQ (Learning Vector Quantization) o
aprendizaje por cuantificación vectorial,
propuestos por Kohonen [E.3]
• DSM (Decision Surface Mapping) o
construcción de superficies de decisión,
propuesto por Geva y Sitte [E.2].
Métodos de aprendizaje
adaptativo
• Fija a priori la cantidad de prototipos del
conjunto de aprendizaje resultante Np
• El conjunto resultante no tiene porque estar
incluido en el conjunto Inicial.
• Heurística sencilla
• Rapidez de cálculo
• Dificultad para establecer valores
adecuados de los parámetros.
Aprendizaje competitivo y
cuantificación vectorial
• Sistema aprende de una secuencia de patrones:
X = X(t) P, t = 1, 2,... 2.
{mi(t) : mi(t) P, i = 1, 2,..., Np}
• Un conjunto fijo de vectores de referencia o
prototipos modifican durante el aprendizaje.
1. {mi(0), i = 1, 2,..., Np} ha sido inicializado de alguna
forma.
2. Actualizo mc(t) que mejor empareje con X(t) se
Cuantificación Vectorial
mc(t + 1)
mi(t + 1)
mc(t) + (t) [X(t) - mc(t)]
mi(t) para i  c
• (t) secuencia monótona decreciente de
coeficientes escalares : 0 < (t) < 1
Función de Ganancia o Razón de Aprendizaje
Aprendizaje por cuantificación
vectorial (LVQ)
Inicialización :
Determinación de Npi :
1. Proporcional a Ni.
2. Npi sea el mismo para todas las clases.
Seleccionan los prototipos de SLVQ(0):
1. Para cada clase, se procesan secuencialmente sus
prototipos.
2. Se añaden a SLVQ(0) si la clasificación k-NN es
correcta.
Aprendizaje
•SLVQ (0), SLVQ (1), ..., SLVQ(r - 1) = SLVQ
Método LVQ-1
mj(t + 1)
mj(t) + (t)[X(t) - m j(t)]
{Premio a mj(t)}
mi(t + 1)
mi(t) -  (t)[X(t) - mi(t)]
{Castigo a mi(t)}
•Premio: Si la clase de mc(t), coincide con la
X(t),
•Castigo: En otro caso, mc(t) se aleja de X(t).
LQV-1
• Tiende a mover los prototipos hacia prototipos de
aprendizaje de su misma clase y a alejarlos de los de
otra clase
• Recomendable fijar un valor peqeño para (0),
bastante menor que 0.1 (0.02 ó 0.03).
• Número de pasos de aprendizaje es suficiente con
presentar un número de prototipos
50 x Np < r < 200 x Np.
• No es tan importante el valor de r si el conjunto inicial es
de buena calidad (previamente editado).
Método LVQ-1 Optimizado
(OLVQ-1)
(t)
•Positivo si (Clase (mc(t)) = Clase (X(t)).
•Negativo si (Clase (mc(t)) = Clase (X(t)).
•cmáx =0.3
•30Np < r < 50Np (usualmente, r = 40Np).
•Se desestabiliza para valores altos de r
LVQ-2.1
Patrón modifica dos prototipos ( el más cercano de la
misma clase y el más cercano de distinta clase)
mj(t + 1)
mj(t) +
(t)[X(t) - m j(t)]
mi(t + 1)
mi(t) -
(t)[X(t) - mi(t)]
• valores bajos para (0)= 0.02
• 30Np < r < 200Np
{Premio a mj(t)}
{Castigo a mi(t)}
LVQ-3
Modifica los dos patrones más cercanos:
1. Si mi y mj son de la distinta clase LVQ2.1
2. Si mi y mj son de misma clase:
mi(t + 1)
mi(t) +(t)[X(t) - mi(t)]
mj(t + 1)
mj(t) +  (t)[X(t) - mj(t)]
=[0.1, 0.5]
El desempeño es similar, idea: usar métodos con
menos parámetros
Aprendizaje de superficies de decisión (DSM)
•Se castiga al prototipo más cercano (el inductor del error).
•Se premia al prototipo más cercano de la misma clase que Z(t).
mc(t + 1)
mc(t) +
(t)[X(t) - mc(t)]
{Premio}
mw(t + 1)
mw(t) -
(t)[X(t) - mw(t)]
{Castigo}
Tabla 11: Error de clasificación 1NN para diferentes valores de Np
Np
DSM
LVQ-1
6
7.14
19.00
8
3.82
19.55
9
1.86
14.64
10
0.43
12.34
20
0.43
4.44
24
0.41
3.06
50
0.49
2.51
250
0.79
1.84
Arboles de Clasificación
• Estructura resultante de la partición recursiva del
espacio de representación
• Cada nodo interior contiene una pregunta sobre un
atributo concreto
• Cada nodo hoja se refiere a una decisión
(clasificación).
• CART (Classification And Regression Trees o
árboles de clasificación y regresión),
Arboles de Clasificación
• Aprendizaje. Construcción del árbol a partir de
un conjunto de prototipos, S
• Clasificación. Preguntas sobre los valores
de sus atributos, empezado por el nodo raíz y
siguiendo el camino determinado por las
respuestas a las preguntas de los nodos internos,
hasta llegar a un nodo hoja. La etiqueta asignada a
esta hoja es la que se asignará al patrón a clasificar
Construcción del árbol de
clasificación
•
•
•
•
Nodo raiz- tiene a todos los prototipos
Parto el nodo raiz:
•
Para una carácterística eligo la mejor partición que
separe a los prototipos en clases más puras.
•
Realizo lo mismo para las otras caráctersticas
Repito para los nodos hijos hasta llegar a
condición de parada (nodo hoja).
Los prototipos asociados a un nodo hoja
agrupamiento homogéneo, al nodo se le
asigna una etiqueta.
Selección de las particiones
• ¿De qué forma se hacen las particiones y se
selecciona la mejor de entre las posibles en
cada momento?
• objetivo de una partición: es incrementar la
homogeneidad de los conjuntos resultantes
que sean mas puros.
• medida de pureza
Criterios de partición
• Función de impureza  definida sobre J-uplas de
la forma (c1, c2,..., cJ) tales que: a) cj  0 para j =
1, 2,..., J y b)  cj = 1,
–  max cuando (1/J, 1/J, 1/J,..., 1/J)
–  min =0 cuando tengo una sola clase (1, 0, 0,..., 0)
– Función simétrica
Medida de impureza de un nodo t:
i(t) =  ( p(1| t), p(2| t),..., p(J| t) ) p(j| t) =
Bondad de una partición
• bondad de la partición s en un nodo t,
(s, t): decrecimiento en impureza
 (s, t) = i(s, t) = i(t) - pL i(tL) pR i(tR)
Impureza de un árbol
I(T) =
I(t) =
i(t)p(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)
Sumo en el conjunto de nodos terminales.
Criterios de medida de
impureza
• Medida de entropía.
i(t) = • Indice de Gini
i(t) =
p(j| t) log p(j| t)
p(i| t) p(j| t) = 1 -
p(j| t)2
El clasificador no es muy sensible a la elección del criterio de
impureza.
Regla de asignación de clases
• ¿Cómo asignar una etiqueta a un nodo
terminal?
• La clase más representada en ese nodo.
j(t) = j si p (j| t) =
{p (i| t)}
Criterio de parada
• ¿Cual es el criterio para determinar que un
nodo es homogéneo ?
• Basado en un criterio de poda, se construye
un árbol muy grande y se poda hacia la raíz
de manera adecuada. La poda permite
eleiminar ramas en forma asimétrica, es más
eficiente que detener el crecimiento.
La estrategia de poda
1. Particionar nodos hasta que se cumpla alguna
de estas condiciones:
• a) que sea totalmente puro, o
• b)N(t) < Nmin (habitualmente Nmin = 5)
T' es un subárbol podado de T
2. Se asocia una medida de error a cada árbol
de la secuencia y se escoge aquel que tenga
asociado el menor error.
Poda por mínimo coste-complejidad
• Complejidad de un subarbol como el
número de nodos terminales, |T |.
• Error de clasificacion R(T).
• Medida de coste-complejidad :
• R  (T) = R(T) +  |T |
•
•  0:parámetro de complejidad
• R (T()) =
{R (T)}
Selección del mejor árbol
podado
• Escoger aquel que tenga asociado el menor
error R*(Tk)
• ¿cómo estimar honestamente R*(Tk)?.
• Estimación por conjunto de prueba
• Estimación por validación cruzada.
• La regla 1-SE:
SE (Rts(T)) =
Descargar

Document