RESUMEN:
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.