Análisis discriminante evolutivo

  1. Echeverría Rey, Alejandro
Dirigida per:
  1. Alejandro Sierra Urrecho Director/a

Universitat de defensa: Universidad Autónoma de Madrid

Fecha de defensa: 25 de de febrer de 2009

Tribunal:
  1. José Ramón Dorronsoro Ibero President/a
  2. Carlos Santa Cruz Fernández Secretari/ària
  3. Ricardo Aler Mur Vocal
  4. José M. Valls Ferrán Vocal
  5. Basilio Sierra Araujo Vocal

Tipus: Tesi

Resum

En este trabajo se propone una nueva extensión no lineal del Análisis Discriminante de Fisher (ADF) denominada Análisis Discriminante Evolutivo (ADE). ADE es un nuevo algoritmo de clasificación que comparte con su análogo clásico características como su naturaleza libre de etiquetas, pero que supera limitaciones como su incapacidad para aprovechar posibles relaciones no lineales entre las variables de entrada. R. Fisher introdujo ADF en 1936 como un procedimiento de reducción dimensional supervisada que obtiene, para problemas de clasificación binarios, un nuevo atributo como combinación lineal de los originales, independientemente del número de éstos. Este atributo es el que maximiza la separación entre las medias de las clases, manteniendo los ejemplos tan agrupados como es posible alrededor de sus medias. Este criterio se puede expresar sucintamente en términos de las matrices de covarianza y posee una solución analítica muy elegante. ADF es un método de reducción dimensional, no un algoritmo de clasificación. Cuando se utiliza como clasificador, la regla más utilizada consiste en asignar cada ejemplo a la clase de la media proyectada más próxima. No es necesario decir que esta regla no tiene por qué ser la regla óptima y, de hecho, es también habitual utilizar una red neuronal para aprovechar adecuadamente la proyección o proyecciones (en problemas con más de dos clases) de Fisher. Esta situación no es del todo satisfactoria pues supone optimizar dos criterios diferentes: el de Fisher en primer lugar y posteriormente el error cuadrático de clasificación.%&/El algoritmo propuesto en este trabajo soluciona este problema pues minimiza directamente el error de clasificación sin criterios intermedios. Al igual que en ADF, no se aprenden etiquetas como hacen las redes neuronales, sino que los ejemplos se clasifican por proximidad a las medias proyectadas. Sin embargo, a diferencia de lo que ocurre con ADF, en ADE la proyección es óptima para esta regla de clasificación pues el único criterio que se optimiza es el número de ejemplos mal clasificados. Ya que este criterio es discreto hemos de recurrir a un algoritmo capaz de optimizar cantidades no diferenciables. En concreto, ADE utiliza una estrategia evolutiva. La versión más elemental del algoritmo utiliza una estrategia evolutiva 1+1 y se puede expresar de la siguiente manera:%&/- Se genera una proyección inicial.- El valor o fitness de la proyección es el número de errores cometidos al asignar ejemplos a la clase de la media más cercana en el espacio proyectado.- Se repiten los siguientes pasos hasta que se alcanza un número determinado de generaciones sin mejoras:%&/- Se genera una nueva proyección añadiendo a los coeficientes de la actual una perturbación gaussiana.- Se calcula el número de ejemplos mal clasificados por la nueva proyección.- La nueva proyección sustituye a la actual cuando reduce el error.%&/- La proyección actual es la respuesta del algoritmo.%&/Una de las grandes ventajas de este algoritmo es que el número de proyecciones puede escogerse libremente. En el caso de ADF y de sus principales extensiones no lineales, como el Análisis Discriminante de Fisher con Núcleos (ADFN) y el Análisis Discriminante No Lineal (ADNL), el número de proyecciones es necesariamente igual al de clases menos uno. Esto es así debido al rango de una de las matrices de covarianza que intervienen en el criterio de Fisher. Sin embargo, ADE no optimiza este criterio y se libera de esta limitación de forma muy natural. Ahora sí es posible obtener proyecciones bidimensionales de problemas de clasificación con un número arbitrario de clases, lo cual tiene mucho interés para la visualización de problemas complejos.%&/A lo largo del trabajo se introducen distintos algoritmos que comparten el núcleo básico que acabamos de describir. ADEL es la versión lineal, es decir, busca una combinación lineal de atributos o proyección lineal. Una forma de construir proyecciones no lineales consiste en combinar proyecciones lineales de forma jerárquica. Esta idea da lugar al Análisis Discriminante Evolutivo Jerárquico (ADEJ). Sin embargo, la extensión no lineal general de ADEL se denomina Análisis Discriminante Evolutivo (ADE) y se basa en una red neuronal con una capa oculta de pesos. Todos estos algoritmos se describen en las siguientes secciones y se comparan con los principales algoritmos de clasificación y discriminación de la literatura.