3. Funciones discriminantes para la f.d.p normal.
• El clasificador de mínimo error (Bayes) se puede expresar en
términos de funciones discriminantes:
g i ( X )  log( p( X | wi ))  log(  i )
(9)
Si p( X | wi )  N (  i ,  i ),
gi ( X )  
1
2
1
( X  i ) i ( X  i ) 
T
d
log 2 
2
1
2
log |  i |  log  i
(10)
Forma general de las funciones discriminantes asumiendo
f.d.p. normales
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
3. Funciones discriminantes para la f.d.p normal.
• Casos particulares:
- Caso 1. i = 2 I (Clasificador . Lineal)
- Caso 2. i =  ( Clasificador Lineal)
- Caso 3. i arbitrarias ( Clasificador Cuadrático)
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
3. Funciones discriminantes para la f.d.p normal.
3.1 Clasificadores lineales
3.1.1 Caso 1: i = 2 I
• Variables estadísticamente independientes (no
correlacionadas) y todas tienen la misma varianza,
2(Homocedasticas)
• Las matrices de covarianza son diagonales con valor 2
i = Diagonal(2 ,,,2)
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
3. Funciones discriminantes para la f.d.p normal.
Clasificador lineal con i = 2 I
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
3. Funciones discriminantes para la f.d.p normal.
• Simplificaciones de las funciones discriminantes.
- En este caso | i |  2d
Sustituyendo en (10):
gi ( X )  
1
2
1
y i  Diagonal [(1  ) , , , (1  ) ]
2
2
( X   i ) ( X   i )  log(  i )
(11)
T
2
- Considerando que ||  || es la norma Euclídiana
|| X   i ||  ( X   i ) ( X   i )
2
gi ( X )  
T
|| X   i ||
2
2
2
 log(  i )
Reconocimiento de Formas en Data Mining
(12)
Prof: Héctor Allende
3. Funciones discriminantes para la f.d.p normal.
- Si i son iguales, no son significativas para g i ( X ):
g i ( X )   || X   i ||
2
(13)
Alternativamente,
d ( X )  wc si  E ( X ,  c )  min  E ( X , i )
2
2
i 1, 2 ,..., J
 E2 ( X , i )  || X  i ||2  ( X  i )T ( X  i )
Regla de mínima distancia Euclídiana
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
3. Funciones discriminantes para la f.d.p normal.
• Funciones discriminantes lineales:
gi ( X )  
1
2
2
X
T

X  2 i X   i  i  log(  i )
T
T
1

W

i
i
2

T

g i ( X )  Wi X  wi 0 
1
T
wi 0  

 i  log(  i )
i
2
2

• Superficies de decisión: g i ( X )  g j ( X )
Wi X  wi 0  W j X  w j 0  W ( X  X 0 )  0
T
T
T
donde:
W  i   j
X 0  12 (  i   j ) 
2
||  i   j ||
2
log
Reconocimiento de Formas en Data Mining
i
j
(i   j )
Prof: Héctor Allende
3. Funciones discriminantes para la f.d.p normal.
Front. de dec. Para un clasificador de mín. distancia
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
3. Funciones discriminantes para la f.d.p normal.
3.1.2 Caso 2: i = 
• Las variables no son estadísticamente independientes (correlacionadas) y las varianzas individuales son diferentes.
• Geométricamente: patrones distribuidos en agrupamientos
hiperelipsoidales de igual tamaño y forma. Cada agrupamiento
centrado en su media correspondiente, i
Clasif. Lineal con i= (120,12)
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
3. Funciones discriminantes para la f.d.p normal.
Clasif. Lineal con i= (12=0,12)
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
3. Funciones discriminantes para la f.d.p normal.
• Simplificación de las funciones discriminantes.
gi ( X )  
1
2
1
( X   i )  ( X   i )  log(  i )
T
(14)
• Si i son iguales, no son significativas para g i ( X ):
1
g i ( X )  ( X   i )  ( X   i )
T
(15)
Alternativamente,
d ( X )  wc si  M ( X ,  c )  min  M ( X , i )
2
2
i 1, 2 ,..., J
 M2 ( X , i )  || X  i ||T i1 ( X  i )
Regla de mínima distancia Mahalanobis.
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
3. Funciones discriminantes para la f.d.p normal.
• Funciones discriminantes lineales:
g i ( X )  Wi X  wi 0
T
 Wi   1 i

T
1
1
w




 i  log(  i )
i
2
 i0
• Superficies de decisión.
 Wi   1 (  i   j )

i
log
( i   j )
Wi ( X  X 0 )  0 
j
1
 X 0  2 ( i   j ) 
T
1
(



)

( i   j )
i
j

Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
3. Funciones discriminantes para la f.d.p normal.
3.2 Clasificadores cuadráticos
3.2.1 Caso 3: i arbitrarias
• Fronteras de decisión expresadas como una función cuadrática
(círculos, elipses, parábolas, hipérbolas).
• Este es el caso más general (i arbitrarias ), del cual se derivan
como casos particulares los dos estudiados anteriormente.
i = 2 I
i = 
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
3. Funciones discriminantes para la f.d.p normal.
Clasificadores Cuadráticos
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
3. Funciones discriminantes para la f.d.p normal.
• Simplificación de las funciones discriminantes.
gi ( X )  
1
2
1
( X  i ) i ( X  i ) 
T
1
2
log |  i |  log  i
(16)
• Si i son iguales, no son significativas para g i ( X ) :
gi ( X )  
1
1
i
( X  i )  ( X  i ) 
T
2
1
2
log |  i |
(17)
• Funciones discriminantes cuadráticas:
g i ( X )  X Wi X  Wi X  wi 0
T
T
donde:
1
Wi   12  i
1
y Wi   i  i
1
wi 0   12  i  i  i - 12 log |  i |  log  i
T
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
3. Funciones discriminantes para la f.d.p normal.
Fronteras de decisión (en dos dimensiones)
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
4. Diseño de clasificadores de mínima distancia
• Motivación: ¿Porqué no usar el caso i arbitrarias siempre?
Rpta: Dimensión del espacio de parámetros
1. Considerar los costes computacionales de calcular:
Caso 3:
gi ( X )  
1
Caso 2:
gi ( X )  
1
Caso1:
gi ( X )  
1
( X  i ) i ( X  i ) 
T
2
2
1
2
log |  i |  log  i
1
( X   i )  i ( X   i )  log  i
T
1
2
( X   i ) ( X   i )  log(  i )
T
2
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
4. Diseño de clasificadores de mínima distancia
2. Estabilidad de los estimadores
(Representatividad ; sesgo,variancia, eficiencia robustez)
• Etapas:
1. Análisis del conjunto de aprendizaje.
( Consistencia Número de prototipos )
2. Aprendizaje.
( Estimación de Parámetros)
3. Clasificación.
( Regla de decisión)
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
4. Diseño de clasificadores de mínima distancia
4.1. Diseño de clasificadores.
1. Análisis del conjunto de aprendizaje.
Estudiar y sacar conclusiones sobre los conjuntos de
aprendizaje: test de normalidad, comprobación de la
suficiencia del número de muestras de entrenamiento para
estimaciones y estudio de la estructura y propiedades
estadísticas estadísticas de las clases.
En resumen: Decidir el clasificador (casos 1,2 ó 3).
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
4. Diseño de clasificadores de mínima distancia
2. Aprendizaje.
Estimación de los parámetros de cada clase
1.- Caso 1 : Estimar i (i = 1,2, ..., J) y 2 
2.- Si acaso 2 ó 3, Estimar i y i para (i = 1,2, ..., J)
Si i =  Calcular  =
J

i
i
i 1
3. Clasificación.
Calcular g i ( X ) para i=1,2,...,J (según el caso)
d ( X ) c si g c ( X )  g i ( X ),
Reconocimiento de Formas en Data Mining
i  1,2,..., J
Prof: Héctor Allende
4. Diseño de clasificadores de mínima distancia
4.2. Clasificadores de mínima distancia.
Casos particulares de los clasificadores estudiados como los casos
1 y 2 cuando no se consideran las probabilidades a priori (todas
son iguales)
1. Distancia Euclídea:
g i ( X )  ( X   i ) ( X   i )
T
- Variables estadísticamente independientes
- Variables igualmente escaladas en todas las direcciones 2= cte
2. Distancia de Mahalanobis:
1
g i ( X )  ( X   i )  ( X   i )
T
- Variables correlacionadas.
- Variables escaladas de forma diferente (2 distinto)
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
4. Diseño de clasificadores de mínima distancia
4.2.1 Clasif. de mínima distancia Euclídea.
Cálculo de la distancia Euclídiana
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
4. Diseño de clasificadores. Clasif. de mín. distancia
 E2 ( A, B)  ( Ax  Bx ) 2  ( Ax  Bx ) 2  ( A  B)T ( A  B)
1
1
2
2
• Regla óptima de clasificación
d ( X )  wc si  E ( X ,  c )  min  E ( X ,  i )
2
2
i 1, 2 ,..., J
donde
 E2 ( X ,  i ) || X   i || 2  ( X   i ) T ( X   i )
Clasificador de mínima distancia Euclídiana
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
4. Diseño de clasificadores de mínima distancia
• Estamos “resumiendo” una clase por su valor medio: toda la
información de interés de una clase (para la clasificación) está
concentrada en su media
Un clasificador Euclídiana para tres clases
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
4. Diseño de clasificadores de mínima distancia
• Derivación de funciones discriminantes lineales para el
clasificador de mínima distancia Euclídiana
 E2 ( X ,  i )  ( X   i ) T ( X   i )  X T X  2 iT X   iT 
min  E ( X ,  i )  min {2 i X   i  i }
2
i 1, 2 ,..., J
T
T
i 1, 2,..., J
 max { X 
i 1, 2 ,..., J
T
i
Reconocimiento de Formas en Data Mining
1
2
 iT  i }
Prof: Héctor Allende
4. Diseño de clasificadores de mínima distancia
Expresado en forma de funciones discriminantes:
gi ( X )   X 
T
i
1
2
  i  Wi X  wi 0
T
i
T
Wi   i

T
1
w


i
i
2
 i0
De manera aún más compacta:
g i ( X )  Wi X
T

 Wi T   i ,  i ,...,  i , 12  iT  i
1
2
d
 T
 X  X 1 , X 2 ,..., X d ,1
Reconocimiento de Formas en Data Mining

Prof: Héctor Allende
4. Diseño de clasificadores de mínima distancia
Demostración:

g i ( X )  Wi X   i1 ,  i2 ,...,  id , 12  i  i
T
T

 X1 


X2


 ... 


X d 
 1 
 i ,  i ,...,  i , 12  iT  i  12  iT  i
2
1

d

 iT X
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
4. Diseño de clasificadores. Clasif. de mín. distancia
4.2.2 Clasif. de mínima distancia de Mahalanobis.
• Distancia de Mahalanobis.
 M2 ( X ,  i )  ( X   i ) T  1 ( X   i )
• Regla óptima de clasificación:
d ( X )  wc si  M ( X ,  c )  min  M ( X ,  i )
2
2
i 1, 2,..., J
donde
 M2 ( X ,  i )  ( X   i ) T  1 ( X   i )
Clasificador de mínima distancia Euclídiana
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
4. Diseño de clasificadores. Clasif. de mín. distancia
Dist. de Mahalanobis frente a dist. Euclídiana
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
4. Diseño de clasificadores. Clasif. de mín. distancia
Dist. de Mahalanobis frente a dist. Euclídiana(2)
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
5. El problema de la estimación de parámetros
• En teoría, el error de Bayes decrece conforme la
dimensionalidad de los datos se incrementa.
• En la práctica, se usa un número fijo de muestras, N, para
construir el clasificador: los estimadores están sesgados por
las muestras disponibles.
• Si suponemos distribuciones normales se requiere:
- Clasificador. Cuadrático: J  d  d (d  1)  estimaciones

- Clasificador. Lineal:
Jd 
2
d (d  1)

estimaciones
2
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
5. El problema de la estimación de parámetros
• Fenómeno de Hughes.
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
5. El problema de la estimación de parámetros
• Interpretación:
Existe un valor óptimo de dimensionalidad que es función del
tamaño del conjunto de entrenamiento.
Si el número de muestras de entrenamiento es suficiente y la
dimensionalidad de los datos es alta el fenómeno de Hughes se
manifiesta debido a que los estimadores obtenidos son
inestables y segados. Este fenómeno es más acusado cuanto
mayor sea la dimensionalidad.
• Diferencia entre las curvas:
- Clasificador cuadrático: proporcional a d2/N
- Clasificador lineal: proporcional a d/N
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
5. El problema de la estimación de parámetros
• Conclusiones:
•Aunque la decisión de adoptar un clasificador cuadrático o un
clasificador lineal depende fundamentalmente de la forma de
las matrices de covarianza de las clases, el clasificador
cuadrático requiere muchas más muestras de entrenamiento
que un clasificador lineal para conseguir resultados similares.
• Soluciones:
•1. Obtener más muestras de entrenamiento
•2. Utilizar las variables más relevantes (selección y/o
extracción de características)
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
6. Detección de puntos dudosos
• Motivación:
d ( X )  wc si g c ( X )  max g c ( X )
i 1, 2,..., J
Algunos patrones deben descartarse (asignarse a w0)
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
6. Detección de puntos dudosos
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
6. Detección de puntos dudosos
• Técnica: Umbralización
Sea wc tal que P(x | wc) = max P( x | wi )
i 1, 2,..., J
 wc si P( x | wc )  T
d(X )  
w0 si P( x | wc )  T
• Cálculo del umbral para el clasificador cuadrático.
1
g i ( X )   12 ( X   i )  i ( X   i )  12 log |  i |  log  i
T
g i ( X )
Sea wc tal que g i ( X ) = imax
1, 2 ,..., J
wc si g c (X)  Tc
d(X )  
w0 si g c (X)  Tc
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
6. Detección de puntos dudosos
La clasificación es aceptable (d(X) = wc) si
1
c
 ( X   c )  ( X   c )  12 log |  c |  log  c  Tc
T
1
2
1
( X   c )  c ( X   c )  2Tc  log |  c | 2 log  c  Tc



T
Sigue una distribución 2 con d grados de libertad si X está
normalmente distribuida.
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
6. Detección de puntos dudosos
- Procedimiento:
1.- Consultar la tabla 2 para determinar el valor de
(X- c)Tc-1(X-  c) por debajo del cual hay un determinado
porcentaje de puntos.
En esta figura, indicamos el valor de la 2 que tiene la
probabilidad P de ser sobrepasada (la proporción de la
población con un valor 2 mayor que un valor determinado)
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
6. Detección de puntos dudosos
2.- Una vez consultado el valor, ,
1
1
Tc     log |  c |  log  c
2
2
(18)
3.- El valor exacto de Tc se calcula directamente, conociendo
las probabilidades a priori y las matrices de covarianza de esa
clase.
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
Reconocimiento de Formas en Data Mining
Prof: Héctor Allende
Descargar

Capítulo 2