INTRODUCCION AL RECONOCIMIENTO DE PATRONES

INTRODUCCION ALRECONOCIMIENTO DEPATRONES

Objetivos generales

Brindar un marco terico para el anlisis y resolucin de problemas de reconocimiento, clasificacin e identificacin de patrones, en forma automtica.

Realizar hincapi en la evaluacin de desempeo delos modelos propuestos y su aplicacin en la resolucin de problemas prcticos.

Objetivos especficos

Identificar los principales componentes de un Sistema de Reconocimiento de Patrones

Estudio de algoritmos asociados a las distintas etapas y modelos de un SRP

Herramientas de evaluacin de desempeo

Anlisis de casos prcticos

Algunas preguntas que buscaresponder el curso

Cual es la mejor estrategia para resolver un problema

concreto?

Cuales son las caractersticas ms significativas?

Cuantas muestras necesito?

Cual es el grado de correccin de mi solucin?

De las soluciones propuestas cual es ms eficiente y eficaz?

Estrategia

Presentar un diagrama de bloques completo de un SRP

Presentar distintos algoritmos que resuelven los bloques.

Analizar mtodos de evaluacin

Analizar estrategias de fusin y combinacin de clasificadores.

Actividades especficas

Clases tericas: Martes y Jueves de 8:15-10:00

Responder cuestionario

Entrega de ejercicios obligatorios- clases de consulta.

Defensa trabajo final de curso.

Materiales y mtodos

Guas de clase

Bibliografa

Software de simulacin (Matlab, Weka)

Bibliografa

Pattern Classification (2nd. Edition) Duda, Hart Stork John

Wiley & Son 0471056693-2001

Pattern Classification. A unified view of statistical and neural approaches. Jrgen Schrmann. John Wiley & Son. 1996

Pattern Recognition: A Statistical Approach Devijver y Kittler-

Prentice-Hall - 1982

Combining Pattern Classifiers Methods and Algorithms-

Ludmila I Kuncheva 047121078 2004

Pattern Recognition and Machine Learning C. M Bishop, 2006

Anil Jain-Statistical Pattern Recognition: A Review - 2000

Notas del Curso de Reconocimiento de Patrones y Anlisis de

Imgenes de Francisco Cortijo. Decsai UGR

1- Introduccin

Percepcin

Porqu vemos caras en la luna?

Percepcin

Pareidolia: la percepcin imaginada de un patrn o un significado donde no lo hay

Percepcin

Percepcin vs SRP

Por qu los humanos son tan buenos reconociendo patrones?

Dra. Nouchine Hadjkhani de la Universidad de Hardvard: Los humanos llegan a este mundo con los cables preconectados para detectar caras. Un buen sistema de RP proporciona una ventaja competitiva a la hora de la supervivencia (discriminar amigo/enemigo) y reproduccin.

Por qu no imitarlos al disear sistemas automticos de reconocimiento de patrones?

An no se sabe como los humanos reconocen los patrones

Que es el reconocimiento de patrones?

El estudio de cmo las mquinas pueden observando el

ambiente aprender a distinguir patrones de inters de un fondo y realizar decisiones razonables sobre las categoras de los mismos. Anil Jain.

El acto de tomar datos crudos y hacer una accin basados en la categora de los patrones. Duda et al.

Encontrar regla de decisin automtica que transforma medidas en asignaciones a clases.

Dar nombres a los objetos basados en observaciones.

Percepcin

A la edad de cinco aos la mayora de los nios pueden

reconocer dgitos y letras: Grandes, pequeos, escritos a

mano, rotados, incompletos... Variaciones de la letra R

Reproducir esta capacidad por medio de los ordenadores es sorprendentemente difcil , de hecho, tras 50 aos de investigacin no existe actualmente ningn sistema de R.P. de propsito general que sea capaz de aproximarse a la capacidad humana.

Percepcin vs SRP

Que ventajas tienen los SRP?:

Pueden realizar tareas montonas y repetitivas con menos errores.

Trabajar en zonas peligrosas

Funcionar en lugares inhspitos.

Econmicos y autnomos.

Realizar clculos precisos

Aplicaciones Interesantes

Maquinas de recomendaciones: Ej: Netflix. El 75% de los

videos seleccionados por un usuario promedio provienen de las recomendaciones producidas por su sistema de propuesta.

Sistemas de reconocimiento: de escritura manual (servicio postal USA), biometra (facial, huellas, andar)

Aplicaciones de Big Data: descubrir patrones y correlaciones en datos no estructurados, encontrar relaciones dependencias, anomalas.

Anlisis de un ejemplo deSRP

CSI (Crime Scene Investigation)

Identificacin de un criminal a travs de la

observacin de la escena del crimen.

procesar la escena: adquisicin de objetos

analizar sus caractersticas

clasificarlos

identificarlos

post-procesar aumentar confiabilidad

Sistema Biomtrico

Huellas dactilares

ADN

Iris

Forma y tamao de la mano

Escritura

Rasgos faciales

Forma de caminar

Adquisicin- Sensado

Toma de la huella

Toma directa entintado

Sensores capacitivos

Critico calidad y tipo de informacin adquirida que condiciona el

procesamiento posterior. Ej: rodada o plana, manchones (entintado)

Complementariedad: Cada caracterstica fsica tiene ventajas y

limitaciones:

Poder de discriminacin

Invasiva vs no invasiva

Colaborativa vs no colaborativa

Problemas de adquisicin

Ejemplos

DominioAplicacinPatrnEntradaClasesData miningBsqueda patrones significativosPuntos espacio multidimensionalClusters compactos y bien separadosClasificacin de documentosBsqueda enInternetTextoCategoras(dep.,negocios)BiomtricaIdentificacin depersonasIris, huellas, carasUsuariosautorizadosSensado remotoPronstico de cosechasImgenes multiespectralesCategoras de tierras.Reconocimiento de vozAcceso a informacin sin operadorSeal de vozPalabras habladas

Identificacin de los conceptos y componentes bsicos de un SRP

Objetivo de SRP

Asignar un objeto o fenmeno fsico (patrn, en general)

a una clase o categora.

Reconocimiento de Patrones: regla de decisin

automtica que transforma medidas en asignaciones a clases.

Conceptos Generales

En el R.P. no se clasifican directamente las entidades u objetos sino su descripcin.

Esta descripcin se crea a partir de un modelo de laentidad construida a partir de unas caractersticas y algn tipo de representacin.

La representacin tambin es dependiente del problema y puede ser un vector, una cadena, un grafo, etc... Esta representacin es utilizada por un clasificador para asignar la entidad a una clase.

Conceptos Generales

Modelo: representacin de un patrn.

Caractersticas o atributos: medidas que componen las representaciones.

Espacio de representacin o de caractersticas: conjuntode todas las representaciones posibles para un cierto problema, universo de operacin del SRP.

Caractersticas (features)

Los objetos se describen por caractersticas :

Cuantitativas:

Continuos: presin, longitud

Discretos : nmero de ciudadanos, tantos

Cualitativas

Ordinal : grado de educacin

Nominal: profesin, marca de auto.

Se necesita una metodologa para pasar de caractersticas cualitativos a cuantitativos en general son mtodos heursticos subjetivos , Ej: medida inteligencia, conocimiento, belleza, sentido del humor.

Ejemplo: Reconocimiento de caracteres

x=(x1.x8 ) con xi distancia extremos semirrectas y centro

gravedad.

Buena representacin: una en la que las relaciones estructurales entre los

componentes son simples y se revelan en forma natural y en la que el modelo verdadero

(desconocido) se puede expresar.

Clases y Etiquetas

Para el reconocimiento automtico, es importante que patrones que describen objetos de una misma clase, presenten caractersticas similares. Patrones que describen objetos de diferentes clases presenten caractersticas diferenciadas.

Asumiremos:

C= {w1.. wc}: conjunto finito de eventos

wi de C : clase del conjunto de clases

c = card(C) : nmero de clases

Las c clases wi son mutuamente excluyentes y completas

CLASIFICACION DE PATRONES

x: vector de caractersticas: coleccin de observaciones.

Clasificacin de patrones: proceso de inferir w de x, proceso de asignar nombres a las observaciones x.

Mapeo wx, uno a muchos debido a la variabilidad,

muchos patrones representan el mismo concepto: EjA A A A A ,

El mapeo x w, puede o no ser nico.

Variabilidad: descrita por la distribucin de las clases en el espacio de caractersticas Rd.

Sistemas de Reconocimiento de Patrones

Modelos perceptuales:

adquisicin de datos sensoriales/preproceso

extraccin de caractersticas

toma de decisiones

Diseo de SRP

1. Inferencia del modelo a partir de un conjunto de

datos de entrenamiento

2. Desarrollo de reglas de decisin prcticas

3.Simulacin y evaluacin del rendimiento del sistema.

(Machine learning, reconocimiento de patrones estadstico)

SRP Estadstico

Sensor

Funcin del sensor: Medicin, dar representacin de

los elementos a ser clasificados.

Condiciona el rendimiento del sistema

Debera adquirir todas las propiedades fsicas que

permiten discriminar los objetos.

Limitaciones: no se dispone conocimiento, mediciones no intrusivas, econmicamente no viable, datos histricos (fichas dactilares)

Preproceso

Modificar la representacin inicial para poder

resaltar las caractersticas relevantes: Filtraje, Realce, Cambio de espacio, etc.

No suele existir mucho conocimiento que dirija el preproceso.

Aprendizaje

El proceso de aprendizaje permite establecer un modelo: establecer los parmetros del modelo o adquirir conocimiento sobre el problema.

Tipos de aprendizaje:

Recopilar conocimiento (deductivo) humano sobre el problema.

(Sistemas expertos).

Adquirir (inductivamente) el conocimiento a partir de ejemplos especficos. Ej. Inferencia gramatical, estimacin de parmetros.

Aprendizaje

El aprendizaje se puede realizar en una fase previa al reconocimiento (diseo del clasificador) o continuar durante el proceso de reconocimiento (Aprendizaje continuo).

Un objetivo del Aprendizaje puede ser la determinacin del conjunto de descriptores ptimo. Este proceso se llama seleccin de caractersticas.

La seleccin de caractersticas se suele llevar a cabo mediante tcnicas estadsticas y puede requerir conocimiento profundo de la naturaleza del problema.

Seleccin y Extraccin de Caractersticas:

Extraer la informacin que puede permitir la discriminacin.

Eliminar informacin redundante e irrelevante.

Reducir la dimensionalidad del problema.

Dimensionalidad de los datos

El desempeo de un clasificador depende de la relacin entre

el nmero de muestras, el nmero de caractersticas y la

complejidad del clasificador.

Maldicin de la Dimensionalidad: En la prctica se ha observadoque el agregar caractersticas puede degradar el desempeo si el nmero de muestras es pequeo en relacin al de atributos.

En clasificadores paramtricos la confiabilidad con la que se estiman los parmetros disminuye al aumentar nmero de caractersticas para un nmero de muestras dado.

Dimensionalidad de los datos

Para mejorar el rendimiento del sistema la otra alternativa es

aumentar la complejidad del clasificador

El rendimiento disminuye cuando aumenta la complejidad del clasificador. A este hecho se le llama el problema de la generalizacin, su explicacin es que el clasificador se ajusta tanto a las muestras de entrenamiento que no captura bien el comportamiento de las muestras nuevas (sobre-entrenamiento)

Hay una teora filosfica para la eleccin de clasificadores sencillos. Ya William de Occam (1284-1347?) afirmaba (navaja de Occam) que si dos explicaciones son igual de buenas se debe elegir la simple sobre la complicada.

Maldicin de la dimensionalidad

Buena prctica: n/d >10

Reduccin de la Dimensionalidad

Razones para mantener la dimensionalidad tan baja como sea posible:

Costo de medida

Precisin de la clasificacin

Un conjunto saliente de caractersticas simplifica la representacin y el diseo del clasificador. El bajar mucho puede hacer que se pierda poder de discriminacin.

Seleccin de Caractersticas

Tiene por objeto seleccionar las caractersticas (sensadas o

transformadas en el proceso de extraccin) con mayor poder de discriminacin.

Filtrado (filtering): Selecciona las caractersticas en forma independiente del clasificador, usando un criterio de relevancia .

Encapsulado (wrapping): Selecciona los subconjuntos de

caractersticas en funcin del desempeo de un clasificador.

Intrnseco (embedding): Realizan la seleccin en el proceso de aprendizaje devuelve un subconjunto de caractersticas y el clasificador entrenado. Evalo costo de agregar o quitar caracterstica pero no reentreno.

Mtodos de Seleccin de caractersticas

MtodoPropiedadesComentariosBsqueda exhaustivaEvala todas las combinaciones dep tomadas de dGarantiza encontrar elsubconjunto ptimoMejores caractersticas individualesSelecciona las p mejores caractersticas individualesComputacionalmente simple pero no garantiza un subconjunto ptimoSeleccin secuencial haciadelante (SFS)Selecciona la mejor caracterstica y agrega una por vez tal que combinada maximiza funcin criterio.Una vez que se agrega una no se puede quitar, Computacionalmente eficiente.Seleccin secuencial hacia atrs(SBS)Empieza con todas y quita una a la vezUna vez que se quita una no se puede volver al conjunto optimo.

Mtodos que permiten determinar un conjunto de dimensionalidad

menor en el espacio original (d menor p). Crean nuevas caractersticas combinacin

de las caractersticas sensadas.

MtodoPropiedadesComentariosAnlisis de componentes principales (PCA)Mapas lineales, rpidos, basados en vectores propios.Tradicional, bueno para datosGaussianos.Anlisis de DiscriminanteLinealesMapas lineales supervisados, rpidos, basados en vectores prop.Mejor que PCA paraclasificacin.Anlisis de ComponentesIndependientes (ICA)Mapas lineales, iterativo, noGaussianoSe usa para separar mezclas de fuentes con distribucin no Gaussiana.PCA no linealCriterio no Gaussiano, usualmente iterativoEnfoque redes neuronales.Self-Organizing Map (SOM)No lineales, iterativosBasados en redes neuronales, adecuado para baja dimensionalidad

Clasificador

Objetivo: dividir el espacio de caractersticas en regiones de decisin

asociadas a las clases.

La clasificacin de un patrn consiste en localizar a que Regin

pertenece.

Las fronteras entre las Regiones de decisin se llaman Fronteras de

Decisin.

La eleccin de un clasificador depende del problema.

Cuestiones a resolver son: - Como hacer mnimo el error de clasificacin? - Cual debe ser su complejidad?

Clasificador

Asigna los objetos percibidos (a los que no se le

conoce la clase de pertenencia) a la clase adecuada.

Dado un patrn x Rd, x = (x1, x2, ..., xd)

Objetivo determinar a cul de las c clases de

C={w1,w2, ..., wc} pertenece dicho patrn

D : Rd C, D(x) = w i i = 1, ..., c

Funciones Discriminantes

Regin de Decisin

Enfoque estadstico

Enfoque estadstico

Regla de mnimo error de Bayes

Costo de decisin

Clasificacin

Reconstruccin de leyes de probabilidad

Reconocimiento de Patrones Estadstico

Aprendizaje

Aproximaciones

Aprendizaje supervisado

Estimacin de densidades - Parzen

Regla del vecino ms cercano 1-NN

Aprendizaje no supervisado y anlisis de Agrupamiento

Distribucin conjunta multimodal

Algoritmo de k-medias

El algoritmo k-mean

Evaluacin de desempeo

Estimacin de error y confianza

Aplico el clasificador a un conjunto de test de

patrones cuya clase es conocida Zts

Estimo el error contando discrepancias entre clase verdadera y etiqueta asignada por el clasificador

Error (D) =Nerror/Nts tasa de error aparente

Necesitamos un nmero grande de muestras para

verificar con confianza relativamente razonable.

Conjunto de entrenamiento y de test

Queremos usar la mayor cantidad de datos posibles para el entrenamiento y para la

evaluacin del desempeo del clasificador.

Si usamos todos los datos para el entrenamiento y el mismo conjunto para la evaluacin

podemos SOBREENTRENAR el clasificador. Lo que puede hacer que falle con datos no vistos.

Reclasificacin: procedimiento de evaluacin de desempeo usando el conjunto de aprendizaje.

Generalizacin: Evaluacin con un conjunto de test

independiente.

Utilizacin de los datos: entrenamiento vs

Testing

Utilizacin de los datos: entrenamiento vs

Testing

Bootstrap: se utiliza para corregir la estimacin optimista del R-mtodo.

Se hace generando L conjuntos de cardinalidad n a partir del conjunto Z con remplazo.

Luego se promedia error de clasificacin de los conjuntos.

Hold out: Utilizo 3 conjuntos: entrenamiento, validacin y test.

Se continua el entrenamiento hasta que no se logra mejora con

el conjunto de validacin.

Matrices de Confusin

Para determinar como se distribuyen los errores en las clases se construyen las matrices de confusin usando el conjunto de test Zts.

La entrada aij de cada matriz indica el nmero de elementos de Zts cuya clase cierta es wi y que se le asign clase wj

Huellas Dactilares

Comparacin de desempeo

Evaluacin de Desempeo

En una aplicacin de control de acceso o de

verificacin (confrontacin) existen dos clases:

w1 la identidad es autntica o

w2 la identidad es falsa

En este contexto podemos cometer dos errores de clasificacin que tienen dos costos muy distintos, minimizar el error promedio no es lo adecuado

Receiver Operating Characteristic

Ejemplo de Problema Real

Una planta procesadora de pescado quiere automatizar el

Proceso de clasificacin de pescado con respecto a la especie

(Salmn o Rdalo).

El sistema automatizado consiste en:

Una cinta transportadora para los productos recibidos

Dos cintas transportadoras para los productos clasificados

Un brazo robtico para tomar y colocar objetos

Un sistema de visin con una cmara

Una computadora para clasificar las imgenes y controlar el robot

Ejemplo de Problema Real

Censado: El sistema de visin captura una imagen en cuanto un nuevo pescado entra en el rea de clasificacin.

Preprocesado Algoritmos de Procesamiento de Imgenes

Ajuste de niveles de intensidad

Segmentacin para separar el pescado del fondo de la imagen

Extraccin de caractersticas Supongamos que sabemos que en media, el

rdalo es ms largo que el salmn

A partir de la imagen segmentada estimamos la longitud del pescado

Clasificacin

Seleccionar un conjunto de muestras de ambas especies.

Calcular la distribucin de longitudes para ambas clases.

Determinar la frontera de decisin (umbral) que minimiza el error de clasificacin.

Estimamos la probabilidad de error y se obtiene un mal resultado del orden del 40%

Qu hacemos ahora?

Mejora del Desempeo: Para obtener un error inferior al 5%,

probamos con nuevas caractersticas:

Anchura, rea, posicin de los ojos respecto a la cara,...

Finalmente encontramos una buena caracterstica: Intensidad media

media de las escamas .

Combinamos: longitud e intensidad media de las escamas para

mejorar Longitud la separabilidad de las clases

Buscamos un clasificador que proporcione una frontera de decisin lineal (clasificador lineal) y obtenemos un 4.3% de error.

Costo y Error de Clasificacin

El clasificador que se dise hace mnimo el error de clasificacin.

Es ste el mejor criterio para procesar pescado?

El costo de clasificar errneamente salmn como rdalo es que el consumidor encontrar una pieza sabrosa de salmn cuando compra rdalo.

El costo de clasificar errneamente rdalo como salmn es que el consumidor encontrar una pieza rdalo comprada al precio de salmn

Deberamos ajustar la frontera de decisin para minimizar una funcin

de costo que incluya diferentes costos de confusin.

Resumen

Los objetivos del Reconocimiento de Patrones est

relacionados con la eleccin del algoritmo ms apropiado para

el problema a resolver.

Esto requiere conocimiento a priori (distribucin de los datos, probabilidades a priori, complejidad del problema, fsica del fenmeno que gener los datos, etc).

En ausencia de conocimiento a priori no hay ningn clasificador mejor que otro. Sin embargo con informacin a priori, algunos clasificadores funcionan mejor con determinados tipos de problemas.

El reto es entonces identificar el clasificador o la combinacin adecuada para el problema a resolver.

Deteccin de melanomas

Deteccin de focos epilpticos

Deteccin de plipos en colonoscopa virtual

Clasificacin de trfico en redes de datos

Deteccin de fraudes en consumos de energa

Reconocimiento de Caras

Reconocimiento de Melodas

Proyectos de Investigacin recientes: