Tema 1. Clasificación PDF

720504 - Procesado de Señales Multimedia Máster en Ingenierı́a en Tecnologı́as de Telecomunicación Tema 1. Clasificación Javier Navallas UPNA  Tema 1. Clasificación Introducción Introducci...

720504 - Procesado de Señales Multimedia Máster en Ingenierı́a en Tecnologı́as de Telecomunicación Tema 1. Clasificación Javier Navallas UPNA  Tema 1. Clasificación Introducción Introducción Tema 1. Clasicación Reconocimiento de patrones Extracción de caracterı́sticas Entrenamiento Evaluación Ciclo de diseño Javier Navallas (UPNA) Procesado de Señales Multimedia 2 / 84  Tema 1. Clasificación Introducción Objetivos Identicar el problema y la utilidad del reconocimiento de patrones. Analizar la estructura y ciclo de diseño de un sistema de reconocimiento de patrones. Aplicar técnicas de selección de caracterı́sticas. Aplicar técnicas de evaluación de un clasicador. Bibliografı́a R. O. Duda, P. E. Hart, D. G. Stork Pattern classification. John Wiley and sons, 2001 (2nd ed.) S. Theodoridis, K. Koutroumbas Pattern recognition. Elsevier, 2009 (4th ed.) J. P. Marques de Sá Pattern recognition. Academic Press, 1999 (1st ed.) Javier Navallas (UPNA) Procesado de Señales Multimedia 3 / 84  Tema 1. Clasificación Reconocimiento de patrones Reconocimiento de patrones Reconocimiento de patrones Estructura del sistema Ejemplos Clasicación supervisada y no supervisada Fases de diseño Javier Navallas (UPNA) Procesado de Señales Multimedia 4 / 84  Tema 1. Clasificación Reconocimiento de patrones Reconocimiento de patrones El reconocimiento de patrones consiste en la clasificación automática de objetos en distintas categorı́as o clases. Los objetos a clasicar pueden ser, entre otros y dependiento de la aplicación: Señales unidimensionales: cualquier medida obtenida por un sensor puntual a lo largo del tiempo. Señales bidimensionales: imágenes o registros de matrices de sensores en general. Señales tridimensionales: vı́deo, imagen funcional, ecografı́a dopler, etc. Se denominan patrones a los objetos a clasicar. Por ello, en la literatura se habla de forma indistinta de reconocimiento de patrones o clasificación de patrones. Javier Navallas (UPNA) Procesado de Señales Multimedia 5 / 84  Tema 1. Clasificación Reconocimiento de patrones Algunas de las numerosas aplicaciones del reconocimiento de patrones: Visión artificial: permite la inspección visual (búsqueda de defectos, etc.) o la automatización de procesos de producción (guı́a de brazos robóticos, separación de objetos, etc.). También tiene aplicaciones de vigilancia (reconocimiento y seguimiento de personas) y domésticas (enfoque en la cara de la persona, foto con caras sonrientes, etc.). Diagnóstico médico: permite asistir al médico mediante un diagnóstico automático (clasicación sano/patológico o entre distintas patologı́as). Reconocimiento de voz, gestos, texto: facilita la interacción hombre-máquina. From Wikimedia Commons by Sylenius [CC A3.0] Javier Navallas (UPNA) Procesado de Señales Multimedia 6 / 84  Tema 1. Clasificación Reconocimiento de patrones El sistema de reconocimiento de patrones: Recibe la señal registrada (un vector de N dimensiones, tantas como muestras tenga la señal). Determina la clase a la que corresponde dicha señal (un elemento de un conjunto nito de clases: una etiqueta). Las señales viven en un espacio de señal Javier Navallas (UPNA) Procesado de Señales Multimedia 7 / 84  Tema 1. Clasificación Reconocimiento de patrones Hay que tener en cuenta que la dimensionalidad del espacio de señal es muy alta: tanta como muestras tenga la señal a clasicar. Ası́: Una señal unidimensional discreta de longitud N (N muestras) es un vector en un espacio de N dimensiones. Si dicha señal está codicada con B bits, cada muestra puede tomar 2B valores distintos. Existirán, entonces, 2BN señales diferentes posibles en dicho espacio de señal. Además, los valores concretos de las muestras no tienen por qué estar proporcionando información relevante de cara a la clasicación. Basta pensar, por ejemplo, cuántas fotos diferentes podemos tomar de una silla, y lo difı́cil que resultarı́a identicarla a partir de los valores concretos de los pixeles. Esto nos tiene que hacer pensar en la necesidad de: Extraer medidas que proporcionen información relevante para la clasicación. Reducir la dimensionalidad del espacio en el que se representan las señales a clasicar. Javier Navallas (UPNA) Procesado de Señales Multimedia 8 / 84  Tema 1. Clasificación Reconocimiento de patrones Estructura del sistema Como acabaremos teniendo tantas señales, resolveremos el problema en distintas secciones El reconocimiento de patrones consta de dos fases: la fase de extracción de caracterı́sticas y la fase de clasificación. Tomamos la info. útil y estamos reduciendo una brutalidad la cantidad de datos que teníamos. Por eso mismo, el clasificador se va a enfrentar a un problema más simple porque la dimensionalidad es más baja. Javier Navallas (UPNA) Procesado de Señales Multimedia 9 / 84  Tema 1. Clasificación Reconocimiento de patrones La fase de extracción de caracterı́sticas extrae una serie de medidas de la señal (las caracterı́sticas) con las que se construye un vector de caracterı́sticas que pasa a ser la nueva representación de la señal. Esta fase: Extrae la información verdaderamente relevante para la clasicación. Reduce la dimensionalidad del espacio en el que se va a clasicar. La fase de clasificación: Particiona el espacio de caracterı́sticas en regiones (hipervolúmenes) y las asocia a las distintas clases. From Wikimedia Commons by MoodyGroove [GNU 1.2] From Wikimedia Commons by Jer5150 [GNU 1.2] Javier Navallas (UPNA) Procesado de Señales Multimedia 10 / 84  Tema 1. Clasificación Reconocimiento de patrones Ejemplos En el mundo de las comunicaciones, muchos decodicadores son ejemplos de sistemas de reconocimiento de patrones. Hará una partición sobre el espacio de caracteríticas (amplitud y frecuencia) Javier Navallas (UPNA) Procesado de Señales Multimedia 11 / 84  Tema 1. Clasificación Reconocimiento de patrones Una de las cosas más importantes va a ser la separabilidad entre clases. Traducido a este ejemplo, hacer la separación de las zonas correspondientes a la detección de cada bit. From Mathworks - Matlab online documentation Javier Navallas (UPNA) Procesado de Señales Multimedia 12 / 84  Tema 1. Clasificación Reconocimiento de patrones Clasificación supervisada y no supervisada Los ejemplos que vamos a mostrar al sistema en un caso están previamente clasificados (etiquetados) y en el otro no. Los clasificados (supervisados) se basan en pasar x 1s por ejmplo y decir que son 1s. Se hará esto iterativamente. Hace falta una gran cantidad de muestras. El problema de etiquetado en deep learning es que hay que hacerlo muchas veces. En el diseño del clasicador, hace falta entrenarlo para que aprenda a asociar las observaciones (vectores de caracterı́sticas a la entrada del clasicador) con la clase que le corresponde a cada una. Para ello hace falta disponer de observaciones etiquetadas (con la información de la clase correspondiente) para ser empleadas en el entrenamiento. Esto se denomina clasificación supervisada. Javier Navallas (UPNA) Procesado de Señales Multimedia 13 / 84  Tema 1. Clasificación Reconocimiento de patrones Voy más a ciegas. Difícilmente voy a poder poner etiquetas. Es el sistema de forma autónoma el que hace la clasificación buscado parecidos. Trabajas con la esperanza de que haya una clasificación clara. Es más exploratoria. Clasificación supervisada: utiliza la información a priori sobre la clase a la que pertenece cada observación durante el entrenamiento. Clasificación no supervisada: el sistema busca la división en clases más apropiada para explicar las agrupaciones (clusters) de las observaciones, sin más información que las propias observaciones. Javier Navallas (UPNA) Procesado de Señales Multimedia 14 / 84  Tema 1. Clasificación Reconocimiento de patrones Fases de diseño Estamos en disposición de plantearnos las preguntas básicas del diseño de un sistema de reconocimiento de patrones: ¿Cómo escogemos y generamos las caracterı́sticas adecuadas? ¿Cuál es el conjunto óptimo de caracterı́sticas? ¿Cómo particionamos el espacio de caracterı́sticas? ¿Cómo determinamos el rendimiento del clasicador diseñado? Es un punto importante tanto para valorar la calidad de las estimaciones como para ver la mejora de una iteración a otra (o si no hay mejora) Esto nos lleva a las fases de diseño de un sistema de reconocimiento de patrones: Generación de las caracterı́sticas. Selección de las caracterı́sticas: vector de caracterı́sticas. Diseño del clasicador (elección y entrenamiento). Evaluación del clasicador. Javier Navallas (UPNA) Procesado de Señales Multimedia 15 / 84  Tema 1. Clasificación Reconocimiento de patrones Generación de datos Gaussianos bidimensionales (1) m1 = [-1 1]; % vector de medias s1 = [0.4 0; 0 1]; % matriz de covarianzas X1 = mvnrnd(m1, s1, 1000); % generación aleatoria plot(X1(:,1),X1(:,2),’.’); % representación Ejecuta el código dado. ¿Qué hace la función mvnrdn? ¿Qué dimensiones tiene la variable X1 (función size)? ¿Es coherente con las entradas que le pasamos a mvnrdn? ¿Qué representa cada la de la variable X1? ¿Y cada columna? ¿Qué hace el operador : en X1(:,1)? ¿Por qué escribimos X1(:,1) y X1(:,2) en el plot como entradas distintas? ¿Es coherente la distribución con los valores de m1 y s1? Javier Navallas (UPNA) Procesado de Señales Multimedia 16 / 84  Tema 1. Clasificación Reconocimiento de patrones Generación de datos Gaussianos bidimensionales (2) Genera otro conjunto de 1000 puntos  que siga una distribución Gaussiana con µ = ( 1 −1 ) y Σ = 0,5 0,6 0,6 0,9. Representa en la misma gráca los dos conjuntos de puntos empleando dos colores distintos. Añande una leyenda (función legend) que identique los conjuntos como ’Conjunto 1’ y ’Conjunto 2’. ¿Cuál es la diferencia fundamental entre los dos conjuntos de puntos? ¿En qué parámetro de las distribuciones se reeja esta diferencia? ¿Qué caracterı́stica permitirı́a la clasicación correcta de las dos clases? Javier Navallas (UPNA) Procesado de Señales Multimedia 17 / 84  Tema 1. Clasificación Reconocimiento de patrones Etiquetado y diagramas de dispersión Agrupa todas las observaciones en una sola matriz: X=[X1; X2]; Genera un vector G de etiquetas de 2000 elementos donde los 1000 primeros valgan 1 y los 1000 siguientes valgan 2 (función ones). Emplea la función gplotmatrix para representar los datos etiquetados (help gplotmatrix o doc gplotmatrix: gplotmatrix(X,[],G)). ¿Qué representa la función gplotmatrix? Observa la leyenda de las observaciones. Genera un cell-array de etiquetas de 2000 elementos donde los 1000 primeros valgan ’normal’ y los 1000 siguientes valgan ’patologico’. Dada la limitación inherente a la indexación de los cell-array, no quedará más remedio que implementarlo con bucles for. Vuelve a emplear la función gplotmatrix para representar los datos etiquetados y observa ahora la leyenda. Javier Navallas (UPNA) Procesado de Señales Multimedia 18 / 84  Tema 1. Clasificación Reconocimiento de patrones Estimación de parámetros de distribuciones Usa la ayuda de Matlab de la función mean para determinar la mejor manera de estimar el vector de media de las obsevaciones dadas en la matriz X. ¿Tiene sentido hacer la estimación para todas las observaciones a la vez? Observando la ayuda de las funciones std, var y cov, determina cuales serán útiles en la estimación de los valores que alberga la matriz de covarianzas. Compara los valores obtenidos con los valores reales de los momentos de las distribuciones. Repite las estimaciones empleando ahora sólo 10 observaciones de cada clase. Para ello, selecciónalas de forma aleatoria empleando la función randsample. ¿Son mejores o peores las estimaciones? ¿Por qué? Javier Navallas (UPNA) Procesado de Señales Multimedia 19 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Extracción de caracterı́sticas Medidas de distancia: métricas Distribución de las observaciones Ecualización de caracterı́sicas Separabilidad de las clases Cuanticación de la separabilidad Dimensionalidad del espacio de caracterı́sticas Javier Navallas (UPNA) Procesado de Señales Multimedia 20 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Medidas de distancia: métricas La tarea del clasicador es particionar el espacio de caracterı́sticas en subvolúmenes correspondientes a las distintas clases. Para ello: Las caracterı́sticas extraı́das han de permitir diferenciar las clases: la información que aportan ha de ser relevante para el problema. Ha de denirse una medida de similitud en el espacio de caracterı́sticas: necesitamos una métrica que indique cuándo dos observaciones (vectores de caracterı́sticas) se parecen y cuánto. Javier Navallas (UPNA) Procesado de Señales Multimedia 21 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Una métrica es una medida de distancia denida sobre un conjunto. En nuestro caso el conjunto es un espacio vectorial: el espacio de caracterı́sticas. Para un espacio vectorial de vectores de la forma − →x = (x1 ,..., xd )T donde d es el número de dimensiones del espacio vectorial, se denen las distancias entre dos vectores → − x e− → y como: Métrica de potencia:  d 1/r → − x −− →  p y= |xi − yi | i=1 Métrica de Minkowski: p = r  d 1/p → − x −− →  p y= |xi − yi | i=1 Métrica Euclı́dea: p = r = 2  d 1/2 El número de dimensiones es la cantidad → − x −− →  2 de valores del sumatorio. y= |xi − yi | i=1 Javier Navallas (UPNA) Procesado de Señales Multimedia 22 / 84  Tema 1. Clasificación Extracción de caracterı́sticas La distancia Euclı́dea no es más que un caso concreto de métrica de Minkowski, pero conocemos más ejemplos de esta métrica: Métrica de Chebyshev: p = r = ∞ − → x −− →   y  = max |xi − yi | Métrica Euclı́dea: p = r = 2  d 1/2 → − x −− →  2 y= |xi − yi | i=1 Métrica city-block o Manhattan: p = r = 1 d − → x −− →  y= |xi − yi | i=1 Nótese que la distancia de Hamming no es más que una distancia city-block (o Manhattan) en un espacio donde cada conponente en cada dimensión sólo tiene permitido adoptar los valores 0 y 1. Javier Navallas (UPNA) Procesado de Señales Multimedia 23 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Una representación gráca de estas tres métricas en un espacio de 2 dimensiones: Tengo que sumar las distancias por separado porque no existen las diagonales Javier Navallas (UPNA) Procesado de Señales Multimedia 24 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Las métricas denidas (y en particular la métrica Euclı́dea): Consideran todas las dimensiones igual de importantes (tienen el mismo peso) para el cálculo de la distancia. Tratan de forma independiente cada dimensión para el cálculo de la distancia. Sin embargo, esto puede no ser lo más adecuado cuando trabajamos con observaciones cuyas caracterı́sticas: No están adecuadamente normalizadas, con lo que el rango de variación es diferente en cada dimensión y los datos se estiran en alguna de las dimensiones (distintas varianzas de las distintas dimensiones). Presentan algún tipo de correlación, con lo que los datos rotan (distintas covarianzas entre las distintas dimensiones). Javier Navallas (UPNA) Procesado de Señales Multimedia 25 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Escribiendo la distancia Euclı́dea como un producto escalar de vectores:  d 1/2 [(→ − y )T (− x −− → → x −− → y )]1/2 = − → x −− →  2 y= |xi − yi | i=1 Podemos generalizar la métricas: Métrica de Mahalanobis: − → x −− → y  = [(− → x −− → y )T Σ−1 (− → x −− → y )]1/2 Métrica Euclı́dea: Σ = Id − → x −− → y  = [(− → x −− → y )T (− → x −− → y )]1/2 La métrica Euclı́dea es un caso de la de Mahalanobis con Σ igual a la matriz identidad de tamaño d. Javier Navallas (UPNA) Procesado de Señales Multimedia 26 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Observamos que los lugares de puntos equidistantes a otro: Forman cı́rculos, esferas o hiperesferas cuando se emplea la distancia Euclı́dea. Forman elipses, elipsoides o hiperelipsoides cuando se emplea la distancia de Mahalanobis. En este caso, la longitud y orientación de los semiejes vienen dados por la estructura de la matriz de covarianzas Σ (más especı́camente sus vectores propios). Javier Navallas (UPNA) Procesado de Señales Multimedia 27 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Resumen de relaciones entre las métricas denidas: Javier Navallas (UPNA) Procesado de Señales Multimedia 28 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Métricas y distancias (1) Ejecuta el siguiente código e interpreta la gráca resultante: load data dist.mat; X1=X(G==1,:); X2=X(G==2,:); [pX,pY]=meshgrid(-8:0.1:14); P=[pX(:) pY(:)]; pD1=pdist2(mean(X1),P); pD2=pdist2(mean(X2),P); pG=3*ones(size(pD1)); pG(pD1>pD2)=4; gplotmatrix([X;P],[],[G pG],’grgr’,’**..’); Javier Navallas (UPNA) Procesado de Señales Multimedia 29 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Métricas y distancias (2) Interpreta el código, identicando qué lı́neas se encargan de: Cargar los datos etiquetados del archivo de Matlab. Generar dos subconjuntos con las observaciones de sendas clases. Generar un conjunto de puntos P equiespaciados en un plano. Calcular la distancia de cada punto al punto medio de cada clase. Clasificar los puntos en la clase cuya media es más cercana. Representar los conjuntos de puntos. ¿Qué efecto tiene escribir G==1 en el comando X1=X(G==1,:);? ¿Qué efecto tiene escribir pX(:) en el comando P=[pX(:) pY(:)];? ¿Qué es mean(X1)? ¿Qué hace la función pdist2?? ¿Qué efecto tiene pD1>pD2 en el comando pG(pD1>pD2)=4;? ¿Qué valor toma el resto de elementos de la variable pG? ¿Qué efecto tiene ’grgr’,’**..’ en el comando gplotmatrix([X;P],[],[G pG],’grgr’,’**..’);? A la vista de esto, ¿es coherente el uso de los valores 3 y 4 en pG? Javier Navallas (UPNA) Procesado de Señales Multimedia 30 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Métricas y distancias (3) Modica ahora la parte del cálculo de las distancias a las medias empleando ahora el código que se presenta más abajo. Observa que para el cálculo de la distancia de Mahalanobis hemos proporcionado una estimación de la matriz de covariazas de los datos, C. C=0.5*cov(X1)+0.5*cov(X2); pD1=pdist2(mean(X1),P,’mahalanobis’,C); pD2=pdist2(mean(X2),P,’mahalanobis’,C); ¿Qué cambios se producen en la clasicación? ¿A qué se deben? La matriz de covarianzas estimada: ¿es la de los datos en conjunto o un promedio de las estimaciones para cada clase? Prueba a calcular ahora la distancia con una estimación de la matriz de covarianzas sin tener en cuenta las clases y analiza los cambios. Prueba ahora con la distancia cityblock y analiza los cambios (doc pdist2). Javier Navallas (UPNA) Procesado de Señales Multimedia 31 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Distribución de las observaciones Población: conjunto de casos existentes o posibles. Observación: cada uno cada uno de los casos de una población que se estudian, miden y caracterizan. Muestra: conjunto de observaciones. Javier Navallas (UPNA) Procesado de Señales Multimedia 32 / 84  Tema 1. Clasificación Extracción de caracterı́sticas En general, las observaciones con las que entrenar, evaluar y utilizar el clasicador tendrán una distribución compleja de la cual podremos extraer algunas caracterı́sticas. Recordar que: La estimación de los momentos mejora cuantas más observaciones haya. Esto es, conforme mayor sea la muestra. La estimación de los momentos, con un tamaño muestral dado, es mejor para los momentos de orden inferior. Recordar que, para el caso de observaciones con una distribución Gaussiana, x ∼ fX (x) = N (µ, σ), los estimadores de máxima verosimilitud de la media y la varianza se obtienen como: Cuanto mayor sea el orden del momento peor van a ser las estimaciones. N 1   σ  σ2 µ̂ = xi ∼ N µ, √ ⇒ E[µ̂] = µ Var[µ̂] = N i=1 N N N 1  σ2 2 2σ 4 σ̂ 2 = (xi − µ̂)2 ∼ χ ⇒ E[σ̂ 2 ] = σ 2 Var[σ̂ 2 ] = N − 1 i=1 N N −1 N −1 Javier Navallas (UPNA) Procesado de Señales Multimedia 33 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Otras veces interesará tener información más completa acerca de la distribución, como puede ser una aproximación a la forma de la función de densidad de probabilidad (PDF). Para ello disponemos de varias herramientas: Histograma: representa la frecuencia de aparición de las observaciones dentro de intervalos acotados de la variable aleatoria. PDF estimada: aproximación continua a la PDF a partir de las observaciones, normalmente resultado de una convolución por un kernel de suavizado, h(x): Pongo una delta donde está cada una de las observaciones de este conjunto. Además, se selecciona un kernel (una distribución de suavizado) para que las deltas pasen a ser una distrinbución bastante continua. N fˆX (x) = h(x) ∗  {xi }N i=1 ⇒ δ(x − xi ) i=1 Diagrama de cajas: resume los puntos principales de la distribución como los percentiles p25, p50 y p75, la extensión plausible de las colas de la distribución, y los posibles valores extremos (outliers). Javier Navallas (UPNA) Procesado de Señales Multimedia 34 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Histograma Obtén una muestra de 100 observaciones unidimensionales que sigan una distribución Gaussiana de media 10 y varianza 9 (función normrnd). Representa el histograma de las observaciones (función hist). Emplea las funciones mean y std para estimar los momentos de las distribución Gaussiana a partir de las observaciones. Representa la función de densidad de probabilidad (PDF) empleando la función normpdf. Para ello, evalúa la PDF estimada en 200 puntos equidistantes que recorran un rango de µ ± 5σ. Emplea la función linspace para generar dicho vector. Compara las dos grácas. ¿Qué diferencias encuentras? ¿Cómo se podrı́a escalar el histograma para que coincidiera en las amplitudes con la PDF? Recuerda que el área de una PDF es siempre 1 y que en el histograma cada barra tiene una anchura determinada. Escala adecuadamente el histograma y representa la PDF superpuesta para comprobarlo. Javier Navallas (UPNA) Procesado de Señales Multimedia 35 / 84  Tema 1. Clasificación Extracción de caracterı́sticas PDF estimada Emplea la función ksdensity para representar la PDF a partir de las observaciones. Para ello, evalúa la PDF estimada en 200 puntos equidistantes que recorran un rango de µ ± 5σ. Emplea la función linspace para generar dicho vector. Superpón la PDF estimada al histograma escalado. Compara el resultado con las grácas anteriores. Observa la inuencia del parámetro ’bandwidth’ en la forma de la PDF estimada variándolo de forma manual por encima y por debajo del valor empleado por defecto (tercer parámetro de salida de la función ksdensity cuando no se dene la anchura de forma explı́cita). Prueba, por ejemplo, con valores entre 0.25 o 3. Javier Navallas (UPNA) Procesado de Señales Multimedia 36 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Diagrama de cajas Emplea la función boxplot para representar la distribución de las observaciones. ¿Qué representa cada elemento de la gráca? Emplea la función quantile para obtener de forma manual los percentiles 25, 50 (mediana) y 75. Compara los valores obtenidos con la representación del diagrama de cajas. Obtén una nueva muestra de 30 observaciones unidimensionales que sigan una distribución Gaussiana de media 1 y varianza 3. Genera las etiquetas necesarias en un cell-array y emplea boxplot para representar las distribuciones etiquetadas de forma conjunta (boxplot(X,G)). ¿Qué información aporta esta gráca respecto del empleo de esta caracterı́stica para separar las clases en una futura clasicación? ¿Cómo la implementarı́as? Javier Navallas (UPNA) Procesado de Señales Multimedia 37 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Ecualización de caracterı́sticas Al considerar observaciones multidimensionales (más de una caracterı́stica extraı́da) el estudio de las distribuciones de los datos y de la separabilidad de las clases no puede hacerse sólo analizando las caracterı́sticas por separado, sino teniendo en cuenta que son componentes de un espacio vectorial. El problema es que las distintas caracterı́sticas pueden provenir de distintas medidas en distintas escalas y que comprendan distintos órdenes de magnitud, haciendo que la distribución de los datos no sea similar en las distintas dimensiones lo que puede plantear problemas a la hora de medir las distancias entre las observaciones. Si no puedo usar la distancia del majalanovis vamos a ingeniárnoslas para que ambos rangos (pej. peso y altura) varíen de forma idéntica o muy similar Javier Navallas (UPNA) Procesado de Señales Multimedia 38 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Existen varias técnicas para igualar el rango de variación de las distintas caracterı́sticas, de forma que ninguna prevalezca por encima de las otras en el cálculo de las distancias. Entre las más empleadas destacan: Normalización: emplea el rango de valores de las observaciones para escalar cada caracterı́stica al intervalo [0, 1]. Importante todas las observaciones a la vez y todas las características por separado al normalizar. xi − xmin x∗i = xmax − xmin Normalización con percentiles: emplea los percentiles α y 100 − α para escalar las caracterı́sticas. Podríamos omitir parte de los outliers xi − xpα porque en vez de trabajar con máximos y mínimos trabajamos con los valores que x∗i = tienden a rondar y eliminamos valores xp(100−α) − xpα extremos. Estandarización: emplea la media y desviación estándar para aproximar la distribución a la distribución estándar N (0, 1). xi − µ̂ x∗i = σ̂ Javier Navallas (UPNA) Procesado de Señales Multimedia 39 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Además, a veces es conveniente eliminar los valores extremos (outliers) que pueden distorsionar el escalado o afectar al clasicador en el entrenamiento: Eliminación de outliers: elimina las observaciones por debajo del percentil α y/o por encima de 100 − α. Hay que tener cuidado si hay pocas observaciones, dado que se reduce aún más el número de observaciones disponibles. Nótese que la normalización tras la eliminación de outliers es equivalente a la normalización con percentiles, salvo por el hecho de que los outliers se mantienen en el conjunto de observaciones en el segundo caso pero no en el primero. Javier Navallas (UPNA) Procesado de Señales Multimedia 40 / 84  Tema 1. Clasificación Extracción de caracterı́sticas La ecualización individual de las caracterı́sticas no capta adecuadamente las posibles correlaciones entre las caracterı́sticas en la medida de distancia. Para ello puede emplearse, en lugar de la métrica Euclı́dea, una métrica de Mahalanobis en la lasicación posterior. Ésta tiene en cuenta, de forma simultánea, las variazas y covarianzas de los datos. Javier Navallas (UPNA) Procesado de Señales Multimedia 41 / 84  Tema 1. Clasificación Extracción de caracterı́sticas La estimación de la matriz de covarianzas de los datos para emplear una métrica de Mahalanobis debe hacerse promediando las matrices de covarianzas estimadas para cada una de las clases. Cuando la distribución de las características es muy asimétrica busco que sea más simétrica haciendo transformaciones no lineales. Aun así lo que es más grande tiene que seguir siendo más grande y lo que es más pequeño tiene que seguir siendo más pequeño. Si se emplean los datos conjuntos de todas las clases, la métrica obtenida no es útil para la clasicación. Javier Navallas (UPNA) Procesado de Señales Multimedia 42 / 84  Tema 1. Clasificación Extracción de caracterı́sticas En algunos casos la ecualización tampoco es suciente, y es necesario realizar una transformación de alguna de las caracterı́sticas. Las transformaciones han de ser funciones monótonas que no alteren el orden de los valores de la caracterı́stica. El objetivo, en todo caso, es obtener agrupaciones los más parecidas a distribuciones Gaussianas; esto es: glóbulos relativamente compactos y simétricos. Dada una variable aleatoria X distribuı́da según la PDF dada por fX (x), la nueva variable aleatoria obtenida aplicando la transformación monótona y = g(x) seguirá la distribución dada por la PDF:  dg −1 (y)  fY (y) = fX (g −1 (y))   dy  En el marco más general de las transformaciones de variables aleatorias, la normalización y la estandarización no son más que transformaciones lineales de la caracterı́stica. Javier Navallas (UPNA) Procesado de Señales Multimedia 43 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Ecualización de caracterı́sticas Carga los datos del archivo data ecu 1.mat. Represéntalos mediante una gráca de dispersión. ¿Observas la necesidad de una ecualización de caracterı́sticas? ¿En qué caracterı́sticas en más necesario el escalado? Genera dos nuevos conjuntos de datos: uno normalizado (funciones min y range) y otro estandarizado. Represéntalos mediante sendas gracas de dispersión. ¿Qué diferencias se observan entre ambos métodos? Carga los datos del archivo data ecu 2.mat y repite el proceso anterior. ¿Son útiles la normalización o la estandarización? Genera un nuevo conjunto de datos normalizando las caracterı́sticas respecto de sus percentiles p5 y p95. Representa los nuevos datos y analiza las diferencias. Javier Navallas (UPNA) Procesado de Señales Multimedia 44 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Transformación de caracterı́sticas Carga los datos del archivo data trans.mat. Represéntalos mediante una gráca de dispersión. ¿Observas la necesidad de una transformación de alguna de las caracterı́sticas? ¿De cuál? ¿Por qué? Prueba con una transformación exponencial y una logarı́tmica. Representa los nuevos datos mediante una gráca de dispersión. ¿Qué transformación es más adecuada? Observa las distribuciones de cada caracterı́stica. ¿Podrı́as haber predicho cuál de las dos iba a ser la correcta? Con los datos correctamente transformados, determina la necesidad de una ecualización e impleméntala. Javier Navallas (UPNA) Procesado de Señales Multimedia 45 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Separabilidad de las clases La representación de las distribuciones de las observaciones de las distintas clases permite comprobar de forma gráca la separabilidad de las clases para las distintas caracterı́sticas. Javier Navallas (UPNA) Procesado de Señales Multimedia 46 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Buscaremos caracterı́sticas que den resultados diferenciados para cada una de las clases que queremos clasicar: que hagan las clases separables. La calidad de la clasicación dependerá de la separabilidad de las clases en el espacio de caracterı́sticas. Esta, a su vez, dependerá de las caracterı́sticas escogidas. Ası́, el diseño y la selección de las caracterı́sticas a emplear en el clasicador pasa por determinar si son adecuadas o no para la clasicación. Para ello, hay que determinar lo separables que son las clases con las caracterı́sticas dadas. Encontraremos: Técnicas cualitativas: normalmente grácas, basadas en la representación de las distribuciones o de las propias observaciones. Técnicas cuantitativas: basadas en medidas de distancia entre observaciones de las distintas clases o pruebas de hipótesis de las distribuciones. Javier Navallas (UPNA) Procesado de Señales Multimedia 47 / 84  Tema 1. Clasificación Extracción de caracterı́sticas La representación de las distribuciones de las caracterı́sticas para cada clase nos permite una evaluación cualitativa rápida de la separabilidad de las clases. Herramientas como el histograma, la PDF estimada o los diagramas de cajas nos pueden ayudar en esta prospección inicial. Si tuviera que elegir elegiría este porque el umbral que tengo que definir será más fácil de definir. Solo se mezclan las colas. Ahí vemos que coinciden menos. Javier Navallas (UPNA) Procesado de Señales Multimedia 48 / 84  Tema 1. Clasificación Extracción de caracterı́sticas No basta con comprobar la separabilidad individual de las clases con cada caracterı́stica. Puede ser necesario observar las caracterı́sticas de forma simultánea para adivinar una buena separación de clases. Herramientas como los diagramas de dispersión nos permitirán evaluar la separabilidad en proyecciones bidimensionales del espacio de caracterı́sticas. Javier Navallas (UPNA) Procesado de Señales Multimedia 49 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Representación de las distribuciones Carga los datos del archivo data separ.mat. Observa e identica las variables cargadas. Estima las distribuciones de la primera caracterı́stica para cada clase y represéntalas en una misma gráca. Representa un diagrama de cajas de las distribuciones de la primera caracterı́stica pasándole a boxplot tanto las observaciones como las etiquetas. Determina la separabilidad de las clases en base a esta caracterı́tica. ¿Qué método de representación ofrece mayor información? ¿Qué método resulta más práctico para una inspección visual rápida? Repite el proceso con la segunda y tercera caracterı́stica de las observaciones. ¿Alguna de las caracterı́sticas te parece más importante para la clasicación? ¿Alguna te parece irrelevante? ¿Cuáles escogerı́as para diseñar un clasicador? ¿Alguna de las clases te parece que será más fácilmente clasicada? ¿Alguna será más difı́cil de clasicar? Javier Navallas (UPNA) Procesado de Señales Multimedia 50 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Grácas de dispersión Con los datos del archivo data separ.mat, representa un gráco de dispersión mediante la función gplotmatrix. Se recomienda forzar a la función al uso de ’*’ como sı́mbolo de representación de las observaciones. Teniendo en cuenta que ahora analizamos las tres caracterı́sticas de forma simultánea, determina la relación entre los grácos obtenidos para cada caracterı́stica y los diagramas de dispersión representados. ¿Alguna de las caracterı́sticas te parece más importante para la clasicación? ¿Alguna te parece irrelevante? ¿Cuáles escogerı́as para diseñar un clasicador? ¿Alguna de las clases te parece que será más fácilmente clasicada? ¿Alguna será más difı́cil de clasicar? ¿Eliminar alguna de las clases podrı́a mejorar la clasicación de las otras? ¿Qué habrı́a que hace para conseguir clasicar correctamente las cuatro clases? Javier Navallas (UPNA) Procesado de Señales Multimedia 51 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Cuantificación de la separabilidad Es una cantidad que está medida para cada observación La silueta (silhouette) se dene, para cada observación, como: Indicadores para definir si unas características son mejores o b i − ai peores. si = máx{ai , bi } donde ai es la distancia promedio de la observación al resto de observaciones de su clase y bi es la distancia promedio a las observaciones de la clase más cercana. Se puede demostrar que:  Cuanto mayor sea la 1 − ai /bi si ai < b i diferencia más separable es     b i − ai  Está en la frontera de las si = = 0 si ai = b i clases máx{ai , bi }     ai /bi − 1 si ai > b i Si sale un número negativo sale esta conclusión. Esá más cerca de las otras observaciones que las suyas Javier Navallas (UPNA) Procesado de Señales Multimedia 52 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Los valores de la silueta en cada caso y sus interpretaciones serán: Si si ∼ 1 : ai ≪ bi : observación bien separada, mucho más cerca de su grupo que del cluster más cercano. Si si ∼ 0 : ai ∼ bi : observación fronteriza entre dos clusters. Si si < 0 : ai > bi : observación mal separada, más lejos de su grupo que del cluster más cercano. Observación bien separada Observación fronteriza Observación mal separada Si vemos que la silueta es cercana a 1 en casi todos los casos tenemos un buen conjunto de muestras Javier Navallas (UPNA) Procesado de Señales Multimedia 53 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Con los valores si obtenidos, se representa el conjunto de valores de la silueta ordenados por clases. De la forma del perl de la gráca (la silueta) podemos obtener información sobre el grado de solapamiento de las observaciones de las distintas clases. Es mas importante la extracción de características que un buen separador Idealmente, se busca que la silueta de los grupos tome los valores más cercanos a 1 posible, sin valles (y mucho menos valores negativos) en la silueta. Javier Navallas (UPNA) Procesado de Señales Multimedia 54 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Otro método se basa en la relación entre las matrices de covarianzas de las observaciones: Matriz de covarianza intra-clase (within-class scatter matrix): Cuando varia la matriz de covarianza entre clases C  Sw = Pi Σi i=1 La matriz de covarianzas de cada clase donde: Pi = ni /N es la probabilidad a priori de la clase i-ésima y Σi es la matriz de covarianzas de la clase i-ésima. Matriz de covarianza entre clases (between-class scatter matrix): Es importante ver cuanto se C dispersan las clases pero también P i(− → µi −− → µ 0 )(− → µi −− →  cuanto se separan las clases Sb = µ 0 )T entre ellas i=1 donde: C − → P i− →  µ0 = µi i=1 Matriz de covarianza total (mixture scatter matrix): Sm = Sw + Sb Javier Navallas (UPNA) Procesado de Señales Multimedia 55 / 84  Tema 1. Clasificación Extracción de caracterı́sticas En base a estas matrices, se denen tres medidas diferentes del grado de agrupación de las observaciones o ı́ndices de separabilidad: La suma de los elementos de la diagonal trace{Sm } Se suman las varianzas de las características J1 = por separaso. Tengo una medida de cuánto se trace{Sw } dispersan en cada dimensión. det{Sm } J2 = = det{Sw −1 Sm } det{Sw } J3 = trace{Sw −1 Sm } Estos tres ı́ndices: Están basados en las trazas y determinantes de las matrices de covarianzas interpretados como medidas escalares de la dispersión de los datos en el espacio de caracterı́sitcas. Toman valores mayores cuanto más agrupados estén los datos de cada clase y más separadas las medias de cada clase. Esto es: toman valores mayores cuanto más separables sean las clases. Javier Navallas (UPNA) Procesado de Señales Multimedia 56 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Aunque nos hayamos centrado en estudiar la separabilidad de las clases, las posibles acciones para mejorar la separabilidad de las clases pasan por: Generar nuevas caracterı́sitcas más adecuadas. Seleccionar un subconjunto de las caracterı́sticas que maximice la separabilidad, como ya hemos visto en los ejemplos de las grácas de dispersión. Un método que permite descartar caracterı́sticas es la prueba de hipótesis de igualdad de medias: si dos clases tienen la misma media para una caracterı́stica determinada, no serán separables con dicha caracterı́stica. Esta prueba puede realizarse, por ejemplo, con un test t de Student. En este caso, dados los conjuntos de observaciones {xi }N N i=1 y {yi }i=1 : H0 : µx = µy H1 : µx = µy La incapacidad de rechazar la hipótesis nula sugiere la no separabilidad de las clases y, por ende, la no idoneidad de la caracterı́stica estudiada. Javier Navallas (UPNA) Procesado de Señales Multimedia 57 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Silueta Con los datos del archivo data separ 1.mat, obtén la silueta de los datos etiquetados mediante la función silhouette. ¿Qué representa la silueta? Identica los casos de las distintas clases (observaciones bien separadas, fronterizas o mal separadas). ¿Es coherente con lo que se habı́a observado en la gráca de dispersión de las observaciones? Genera una nueva matriz de observaciones y una nueva matriz de etiquetas suprimiendo los elementos de la clase que resultarı́a más problemática en clasicación (emplea la función find). Repite la representación de la silueta y de la gráca de dispersión. ¿Será mejor el resultado de una clasicación ahora? ¿Es coherente la información que proporcionan ambas representaciones? ¿Por qué aparecen menos valores negativos en la silueta? ¿Por qué aparecen más valores cercanos a 1? Javier Navallas (UPNA) Procesado de Señales Multimedia 58 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Índices de separabilidad Obtén la matriz de covarianzas de cada clase y, a partir de ellas, obtén la matriz de covarianzas intra-clase, Sw. Obtén la matriz de covarianzas total, Sm , estimando simplemente la matriz de covarianzas de todas las observaciones en conjunto. Obtén los criterios J1 , J2 y J3 para las cuatro clases. Repite el análisis completo (obtención de la silueta y de los ı́ndices de separabilidad) con los datos del archivo data separ 2.mat y compara los resultados, recordando que las clases más separadas arrojan ı́ndices de separabilidad mayores. ¿Qué conjunto de datos obtiene unos ı́ndices de separabilidad mejores? Representa las grácas de dispersión de estos nuevos datos. ¿Justican estas grácas los resultados numéricos obtenidos? Javier Navallas (UPNA) Procesado de Señales Multimedia 59 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Selección de caracterı́sticas Con las grácas de dispersión de los datos de data separ 2.mat, determina qué par de caracterı́sticas serı́an las mejores para implementar un clasicador. Para las tres posibles combinaciones de dos caracterı́sticas, genera las siluetas y obtén los ı́ndices de separabilidad. Identica la mejor de las tres combinaciones. ¿Es la misma que considerabas mejor observando las grácas de dispersión? Realiza tests t de Student (función ttest) para cada par de caracrecterı́sticas de cada par de clases. ¿En alguno de los casos no se rechaza la hipótesis nula? ¿Qué signica eso? ¿Guardan estos resultados alguna relación con la caracterı́stica descartada basada en los métodos anteriores? Javier Navallas (UPNA) Procesado de Señales Multimedia 60 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Dimensionalidad del espacio de caracterı́sticas El número de muestras para tener uniformemente cubierto el espacio de parámetros se incrementa como potencia del número de dimensiones. N ∝ Md Javier Navallas (UPNA) Procesado de Señales Multimedia 61 / 84  Tema 1. Clasificación Extracción de caracterı́sticas La proporción de muestras de una distribución Gaussiana en el intervalo ±σ decrece como potencia del número de dimensiones. µ ± σ ∝ 0,68d Lo ideal en la estadística es que unas muestras sean gaussianas d µ ± 2σ ∝ 0,95 Conforme aumenta la dimensionalidad más caminos tienen los datos para escaparse. Javier Navallas (UPNA) Procesado de Señales Multimedia 62 / 84  Tema 1. Clasificación Extracción de caracterı́sticas Al aumentar la dimensionalidad del espacio de caracterı́sticas: Se necesitan más observaciones para tener el espacio muestreado con la misma resolución, dado que el hiper-volumen aumenta con la potencia de la dimensión. Las observaciones de una distribución normal se dispersan conforme aumenta la dimensión. Cuanto menor sea la dimensión del espacio de caracterı́sticas: Menos observaciones para cubrir el espacio de caracterı́sticas. Las observaciones de una misma clase serán más compactas. Este fenómeno se conoce como la maldición de la dimensión (curse of dimensionality). Sin embargo, hace falta un mı́nimo número de caracterı́sticas para recoger toda la información necesaria para poder resolver la clasicación. Javier Navallas (UPNA) Procesado de Señales Multimedia 63 / 84  Tema 1. Clasificación Extracción de caracterı́sticas En algunos casos, las caracterı́sticas extraı́das son muchas y necesitaremos una forma de reducir el número de caracterı́sticas para no vernos afectados por una dimensionalidad excesiva: Una de las aproximaciones es seleccionar las caracterı́sticas que nos proporcionan una mayor separabilidad de las clases. Otra aproximación es realizar una transformación global dentro del espacio vectorial que concentre la información fundamental en unas pocas dimensiones y nos permita descartar el resto. Para ello se pueden emplear técnicas automáticas de reducción de la dimensionalidad, entre las que destacan: Análisis de componentes principales (PCA) Cambiamos los ejes para que uno sea el que tome mayor cantidad de los datos de las muestras. Análisis de discriminantes lineales (LDA) Análisis de correlación canónica (CCA) Javier Navallas (UPNA) Procesado de Señales Multimedia 64 / 84  Tema 1. Clasificación Entrenamiento Entrenamiento Clasicadores y entrenamiento Generalización y sobre-aprendizaje Javier Navallas (UPNA) Procesado de Señales Multimedia 65 / 84  Tema 1. Clasificación Entrenamiento Clasificadores y entrenamiento Existen muchos tipos distintos de clasicadores, entre los cuales podemos destacar: Clasicadores lineales Clasicadores bayesianos K-nearest-neighbor Clasicadores difusos (fuzzy) Support vector machine (SVM) Redes neuronales Pese a ser implementaciones distintas para resolver el mismo problema de la clasicación, todos tienen que pasar por una fase de aprendizaje que permite ajustar los parámetros internos del clasicador. Esta fase comunmente se denomina entrenamiento del clasicador. Javier Navallas (UPNA) Procesado de Señales Multimedia 66 / 84  Tema 1. Clasificación Entrenamiento El aprendizaje o entrenamiento del clasicador es el proceso de ajuste de los parámetros internos del clasicador para resolver los ejemplos propuestos (conjunto de entrenamiento) con un mı́nimo de errores. Es, pues: Un proceso de optimización basado en la minimización del error de clasicación. Un entrenamiento supervisado que necesita de observaciones etiquetadas para llevarse a cabo. Javier Navallas (UPNA) Procesado de Señales Multimedia 67 / 84  Tema 1. Clasificación Entrenamiento Visto como un proceso de optimización: El aprendizaje supone el ajuste de parámetros internos del clasicador que determinan su funcionamiento. El proceso de ajuste dependerá del algoritmo de aprendizaje empleado. Son normales algoritmos iterativos que emplean métodos de optimización diseñados para minimizar el error de clasicación. Javier Navallas (UPNA) Procesado de Señales Multimedia 68 / 84  Tema 1. Clasificación Entrenamiento Generalización y sobre-aprendizaje El objetivo del entrenamiento es que el clasicador adquiera la capacidad de generalización: Una solución excesivamente sencilla puede no captar adecuadamente la distribución y separación de las clases de los casos propuestos. Una solución excesivamente compleja puede llevar al sobre-aprendizaje, donde se pierde la capacidad de la generalización. En concreto, en el sobre-aprendizaje (over-learning) se produce un sobre-ajuste (over-fitting) de la frontera de decisión de las clases. La solución de compromiso pasa por equilibrar entre la capacidad de generalización del clasicador y el posible sobre-aprendizaje. Javier Navallas (UPNA) Procesado de Señales Multimedia 69 / 84  Tema 1. Clasificación Evaluación Evaluación Validación cruzada Figuras de mérito Coste Jacknife y boostrap Javier Navallas (UPNA) Procesado de Señales Multimedia 70 / 84  Tema 1. Clasificación Evaluación Validación cruzada En la validación cruzada o cross-validation se dividen las observaciones en un conjunto de entrenamiento y un conjunto de evaluación (o test). Permite evitar una evaluación no honesta que serı́a evaluar con los ejemplos que se ha entrenado. Javier Navallas (UPNA) Procesado de Señales Multimedia 71 / 84  Tema 1. Clasificación Evaluación Figuras de mérito A partir de los resultados de la clasicación con el conjunto de evaluación se puede calcular una matriz de resultados o matriz de confusión, R, contando los casos de cada clase que son clasicados como casos de cada una de las clases posibles. Para ello, en la evaluación, se necesitan las etiquetas reales de los datos y las que nos proporciona el clasicador como resultado. Javier Navallas (UPNA) Procesado de Señales Multimedia 72 / 84  Tema 1. Clasificación Evaluación La tasa de aciertos se dene a partir de la matriz de confusión como: K 1  TA = Rii N i=1 En el caso de una clasificación binaria, con sólo 2 clases disponibles (pertenece o no a A, posee o no la cualidad A, etc.), los casos concretos de la matriz de confusión se redenen como: Verdaderos positivos (TP) Verdaderos negativos (TN) Falsos positivos (FP) Falsos negativos (FN) Javier Navallas (UPNA) Procesado de Señales Multimedia 73 / 84  Tema 1. Clasificación Evaluación Se denen las siguientes guras de mérito para computar los aciertos y errores de un clasicador binario: Tasa de acierto: T A = (T P + T N )/(T P + F P + T N + F N ) Tasa de error: T E = (F P + F N )/(T P + F P + T N + F N ) Sensibilidad: T P R = T P/(T P + F N ) Especificidad: T N R = T N/(F P + T N ) Proporción de falsos positivos: F P R = F P/(F P + T N ) Proporción de falsos negativos: F N R = F N/(T P + F N ) Son conceptos muy importantes en clasicación orientada al diagnóstico médico, sobre todo la sensibilidad (True Positive Ratio) y la especificidad (True Negative Ratio). Javier Navallas (UPNA) Procesado de Señales Multimedia 74 / 84  Tema 1. Clasificación Evaluación Coste A veces interesa asociar un coste a una clasicación concreta. Para ello se dene una matriz de coste, C: Javier Navallas (UPNA) Procesado de Señales Multimedia 75 / 84  Tema 1. Clasificación Evaluación El coste total se dene a partir de la matriz de confusión y de la matriz de coste como: K K 1  CT = Cij Rij N i=1 j=1 La denición del coste permite modular las equivocaciones (errores de clasicación) en función de su gravedad: Si se plantean criterios de coste, no sólo deben estar presentes en la evaluación, sino que deben implementarse en el diseño del clasicador o en el algoritmo de entrenamiento. Javier Navallas (UPNA) Procesado de Señales Multimedia 76 / 84  Tema 1. Clasificación Evaluación Jacknife y boostrap Cuando hay escasez de observaciones, se emplean técnicas estadı́sticas para aumentar la robustez de la estimación del rendimiento del clasicador o su comparación. Recordemos la validación cruzada: Javier Navallas (UPNA) Procesado de Señales Multimedia 77 / 84  Tema 1. Clasificación Evaluación Jacknife: promediamos N evaluaciones de N entrenamientos. En cada uno de esos entrenamientos: Se toman todas las observaciones menos 1 para el entrenamiento. Se evalúa con la observación descartada (leave-one-out). Javier Navallas (UPNA) Procesado de Señales Multimedia 78 / 84  Tema 1. Clasificación Evaluación Bootstrap: promediamos B evaluaciones de B entrenamientos. En cada uno de esos entrenamientos: Se entrena con las N observaciones. Se evalúa tomando N observaciones aleatorias con repetición del conjunto original de N observaciones. Javier Navallas (UPNA) Procesado de Señales Multimedia 79 / 84  Tema 1. Clasificación Evaluación Figuras de mérito Con los datos del archivo data merit 1.mat, donde C real son las clases verdadera y C clas son los resultados de la clasicación binaria (0: normal y 1: patológico), obtén el número de verdaderos positivos, verdaderos negativos, falsos positivos y falsos negativos. A partir de estos valores, calcula la tasa de acierto, sensibilidad y especicidad. Repite el proceso con los datos del archivo data merit 2.mat. ¿Qué clasicador da mejores resultados? ¿En qué caso es ventajoso cada uno de los clasicadores? Si asignamos un coste de 10 a una clasicación incorrecta de un caso normal, y de 90 al de la clasicación incorrecta de un caso patológico, ¿qué clasicador da mejores resultados en términos de coste total? Javier Navallas (UPNA) Procesado de Señales Multimedia 80 / 84  Tema 1. Clasificación Evaluación Matriz de confusión Con los datos del archivo data merit 3.mat, donde C real son las clases verdadera y C clas son los resultados de la clasicación obtén la matriz de confusión de la clasicación. A partir de la matriz de confusión, obtén la tasa de acierto total. Analizando la matriz de confusión, ¿cuál de las clases presenta más problemas en la clasicación? Javier Navallas (UPNA) Procesado de Señales Multimedia 81 / 84  Tema 1. Clasificación Ciclo de diseño Ciclo de diseño Ciclo de diseño de un clasicador Javier Navallas (UPNA) Procesado de Señales Multimedia 82 / 84  Tema 1. Clasificación Ciclo de diseño Ciclo de diseño de un clasificador Recolección de datos: Determinación tamaño necesario Etiquetado de los datos registrados Elección de las caracterı́sticas: Uso de información previa como invarianzas Diseño de nuevas caracterı́sticas por comparación Evaluación de separabilidad con las caracterı́sticas Elección del modelo: Determinación de las posibles combinaciones de caracterı́sticas Determinación de los posibles clasificadores Determinación de los métodos de entrenamiento Entrenamiento del modelo: Aplicar el entrenamiento con los datos etiquetados Evaluación del modelo: Obtener las figuras de mérito escogidas Iterar sobre los pasos anteriores Javier Navallas (UPNA) Procesado de Señales Multimedia 83 / 84  Tema 1. Clasificación Ciclo de diseño Javier Navallas (UPNA) Procesado de Señales Multimedia 84 / 84