Este artículo introduce el problema de la selección de características para clasificadores basados en redes neuronales artificiales. Primero se describe el estado del arte, incluyendo una taxonomía de métodos de selección de características. Luego se introduce el algoritmo de ramificación y acotamiento, y un algoritmo genético de nichos. Se presentan resultados de simulaciones y comparaciones entre estos algoritmos para varias bases de datos. Por último se ilustra una aplicación a un problema del mundo real. Este consiste en la selección de características de imágenes de tablas de madera con fines de clasificación. Para este problema se compara el método de los algoritmos genéticos con un enfoque basado en medidas estadísticas de las características. Los resultados muestran que los algoritmos genéticos son un método muy competitivo para problemas de altas dimensiones.
1. Introducción.
En el problema de reconocimiento de patrones se desea clasificar ejemplos de determinados objetos en una de varias categorías o clases preestablecidas [5]. El patrón se describe mediante un conjunto de observaciones físicas, las que se combinan en un vector de características. La tarea de clasificación de patrones consiste en construir un mapa de relaciones entre el espacio de características y el conjunto de las clases, de modo de poder reconocer a qué clase corresponde cualquier patrón de entrada representado por un vector de características.
A modo de ejemplo, en medicina se distingue entre pacientes con hipertensión arterial de tipo hipervolémicos y vasocontraídos [18]. En el primer caso, las observaciones sugerentes de hipervolemia son: obesidad, presencia de edemas, fluctuaciones de peso, respuesta hipertensiva a la sal, etc. En el segundo caso, las observaciones sugerentes de vasocontricción son: enfriamiento de la piel, pruebas de reactividad exageradas, elevación desproporcionada de la presión diastólica durante las crisis hipertensivas, etc. Todas estas observaciones cuantificables conforman las características que permiten discriminar entre las dos categorías de pacientes hipertensos.
En muchos otros problemas de clasificación no se conoce a priori, por falta de una teoría sólida establecida, cuáles son las características relevantes que permiten discriminar entre diversas categorías.
El problema de la selección de características consiste en seleccionar un subconjunto de m características de entre un conjunto original de n características candidatos
, bajo algún criterio de desempeño [12,19]. Hay un total de
de tales subconjuntos. El número de posibilidades crece exponencialmente, haciendo impráctica la búsqueda exhaustiva, aun para valores moderados de n.
Entre los propósitos de la selección de características se cuentan:
- reducir la complejidad del clasificador y su implementación en hardware/software.
- compresión de información (eliminar caracterís-ticas redundantes e irrelevantes).
- reducir el costo de medición al disminuir el número de características.
- proveer una mejor clasificación debido a efectos por tamaño finito de la muestra.
Hay varios tipos de problemas en donde existe un gran número de características [11]:
- Aplicaciones donde se fusionan datos provenientes de múltiples sensores.
- Integración de múltiples modelos, donde se juntan los parámetros de diferentes modelos matemáticos para propósitos de clasificación. Por ejemplo, combinación de características de diferentes modelos de textura en imágenes [11].
- Aplicaciones de data mining, donde el objetivo es recuperar las relaciones escondidas entre un gran número de características.
Desde el punto de vista de las reglas de decisión Bayesianas, no existen las malas características. No se puede mejorar el desempeño de un clasificador ideal Bayesiano eliminando una característica (propiedad de monotonicidad). En la práctica, las condiciones del clasificador Bayesiano no se cumplen, p.ej. se dispone sólo de un número finito de datos.
Para tamaños pequeños de muestra aparece el efecto conocido como "la maldición de la dimensionalidad" (curse of dimensionality), en donde el desempeño del clasificador mejora al agregar nuevas características hasta alcanzar un máximo, para luego decaer. Trunk [21] ha demostrado este efecto en un problema simple, en que se conocen las funciones de distribución de probabilidad. La probabilidad de error se aproxima monotónicamente a cero cuando el número de características aumenta y los valores medios de las distribuciones son conocidos. Por el contrario, la probabilidad de error aproxima a ½ cuando la dimensionalidad crece y los parámetros son estimados a partir de una muestra de tamaño finito. Jain y Zongker [11] muestran los peligros de ocupar selección de características en la situación de unos pocos datos esparcidos en espacios de altas dimensiones. Básicamente la calidad de la selección será muy pobre, pero esta puede mejorar al crecer el tamaño del conjunto de entrenamiento.
El problema de selección de características es equivalente a buscar en un grafo dirigido, donde el nodo raíz corresponde al conjunto de todas las características. El número total de posibles subconjuntos de un conjunto de características de n-elementos es 2n. En el grafo, cada nodo corresponde a un subconjunto de características y cada rama representa la inclusión del subconjunto. Los subconjuntos se codifican como tiras binarias, donde el entero 1 indica que una característica está presente en un subconjunto y 0 indica que la característica está ausente.
2. Métodos de Selección de Características.
Un método de selección de características típicamente requiere de los siguientes ingredientes:
- un criterio de evaluación J para comparar subconjuntos de características.
- un procedimiento de búsqueda.
- un criterio de detención, típicamente un umbral de significancia o la dimensión del espacio final de características.
Sea Y el conjunto original de características, de cardinalidad n. Sea m el número deseado de características en el subconjunto seleccionado X,
. Sea J(X) la función objetivo para el conjunto X. Sin pérdida de generalidad se supone que un mayor valor de J indica un mejor subconjunto de características. Un posible criterio es 1-pe, donde pe es la probabilidad de error. Formalmente, el problema de la selección de características consiste en encontrar un subconjunto
tal que
, y
Cover y Van Campenhout [4] demostraron que ningún procedimiento secuencial de selección de características puede garantizar la obtención del subconjunto óptimo, salvo la búsqueda exhaustiva. Estos autores encontraron que cualquier ordenamiento de las probabilidades de error de cada uno de los (
)! subconjuntos de características es posible, número que se reduce aen caso de cumplirse la condición de monotonicidad. Esto quiere decir por ejemplo que el mejor subconjunto de m características no necesariamente está compuesto por las m mejores características individuales.
En la Figura 1 se presenta una taxonomía de métodos de selección de características. La primera distinción es entre métodos basados en la teoría estadística de reconocimiento de patrones y aquellos basados en redes neuronales artificiales. Dentro de los primeros, a su vez, se diferencia entre métodos óptimos o subóptimos, con solución única o múltiple, determinístico o estocástico.
Tal como se dijo anteriormente, sólo el método exhaustivo es óptimo; sin embargo, se considera también óptimo el método de ramificación y acotamiento (branch and bound), que es exhaustivo bajo la condición de monotonicidad. Esta condición requiere que una función objetivo J usada para evaluar subconjuntos de características, crezca monotónicamente sobre una secuencia anidada de subconjuntos de características {X1,...,Xk}, i.e.,
donde
es el conjunto de k características del conjunto original
Dentro de los métodos que mantienen una solución única se encuentran los algoritmos secuenciales y simulated annealing. Los primeros agregan o eliminan características iterativamente hasta satisfacer algún criterio de detención. Hay dos categorías: los métodos hacia delante (forward) que comienzan con el conjunto vacío y van agregando características y los métodos hacia atrás (backward) que comienzan con todas las características disponibles y van eliminando una a una. Estos métodos son subóptimos y sufren del problema de que las características descartadas en el método de búsqueda hacia atrás no pueden volver a seleccionarse. Del mismo modo, una vez seleccionadas las características en el método de búsqueda hacia delante, éstas no pueden ser descartadas posteriormente. Una solución a estas dificultades es permitir que "floten" los valores que controlan tanto la inclusión como la exclusión de características. El algoritmo SFFS (Sequential forward floating selection) [15] incluye nuevas características por medio de un procedimiento secuencial hacia adelante, seguido por una serie de exclusiones condicionales de la peor característica en el nuevo subconjunto de características seleccionadas. El algoritmo análogo, pero con búsqueda hacia atrás, se denomina SBFS. Ambos métodos son mucho más rápidos que el de ramificación y acotamiento, además no requieren que se satisfaga la condición de monotonicidad. Su eficiencia computacional permite el uso de métodos de búsqueda flotante hasta dimensión 100, en contraste con ramificación y acotamiento cuya utilidad se limita a dimensiones de menos de 20.
El simulated annealing, en su formulación original, tiene relación con la conducta de sistemas térmicos en equilibrio de bajas temperaturas. Cuando la temperatura del sistema baja, el sistema gobernado por la distribución de Boltzmann colapsa en uno de los estados de mínima energía. La temperatura se reduce lentamente siguiendo un esquema de enfriamiento. El algoritmo de Metrópolis simula la conducta de los sistemas térmicos. El modelo siempre acepta cambios que correspondan a una disminución en la energía interna del sistema, pero también acepta con cierta probabilidad cambios que aumentan la energía, probabilidad que disminuye con la temperatura (para escapar de mínimos locales).
Figura 1. Taxonomía de Métodos de Selección de Características (tomada de [11]).
Dentro de los métodos que permiten obtener múltiples soluciones se encuentran los algoritmos genéticos y beam search. Los primeros mantienen una población de posibles soluciones, la que evoluciona mediante el uso de operadores estocásticos de selección, recombinación y mutación. El segundo método, beam search, es una versión del procedimiento de best-first (se restringe el largo de la cola a un máximo, con lo que algunos nodos no se visitan nunca). Este método puede no encontrar la solución óptima a menos que se almacenen todos los nodos factibles en la cola y que la tasa de error satisfaga la propiedad de monotonicidad. Beam search es una generalización de los métodos secuenciales (largo de la cola es uno).
2.1 Redes Neuronales Artificiales.
La idea de redes neuronales artificiales nace de emular los sistemas biológicos que funcionan como clasificadores naturales de patrones. Matemática-mente una neurona artificial se describe por el producto interno del vector de entradas x con el vector de pesos w, seguido por una función de activación no-lineal sigmoidal
,
vale decir la salida de una neurona se representa por
. En la Figura 2 se representa una arquitectura típica de redes neuronales llamada perceptrón multicapa (MLP), en donde existen conexiones completas entre capas adyacentes [10,16]. La capa de entrada normalmente sólo recibe las entradas, y no realiza ningún procesamiento. La capa oculta o escondida realiza un primer procesamiento con neuronas no-lineales, y su salida sirve de entrada a la capa de salida. Eventualmente podrían existir múltiples capas ocultas. Las capas de entrada y salida se distinguen porque son visibles, es decir se tiene acceso al valor de las entradas y las salidas deseadas. Las capas ocultas en cambio deben su nombre a que sus salidas no tienen asociadas valores deseados de referencia.
Cibas et al. [2], proponen tres métodos de selección de variables basados en redes neuronales: un método de poda denominado Optimal Cell Damage (OCD), y dos métodos basados en la teoría de regularización usando probabilidades Gaussianas y mezcla de Gaussianas. Estos métodos son subóptimos.
Figura 2. Arquitectura de una Red Neuronal tipo Perceptrón Multicapa.
Cibas et al. [2] extienden el conocido método de poda Optimal Brain Damage (OBD) [13] a la supresión de nodos de entrada. Tomando como criterio el error cuadrático medio, OBD utiliza la información de las segundas derivadas de la superficie de error para lograr un compromiso entre la complejidad de la red y el error de entrenamiento. La superficie de error se aproxima usando una expansión de Taylor de segundo orden. Sea dwi la perturbación en el peso wi. El cambio correspondiente en la función de costos E está dada por:
donde 
es la componente i-ésima del vector gradiente y 
es el elemento ji-ésimo del Hessiano de E.
Luego se aplica una aproximación extrema, cuadrática y diagonal. Primero se entrena la red hasta converger, de modo de obtener un mínimo local o global en la superficie de error, donde gi =0. Se supone que la superficie de error es cuadrática en torno del mínimo local o global, despreciando los términos de tercer orden o mayores. Finalmente, para simplificar los cálculos se supone que el Hessiano es una matriz diagonal, vale decir
Luego,
Se define la saliencia del peso wi como una estimación del cambio en la función objetivo causado por la eliminación de ese parámetro. Si wi se hace cero, entonces
Se define la saliencia de la entrada k, SEk, como
donde Fan_Out(k) está definido por todos los pesos wjk que salen de la entrada k. El costo resultante es la suma de los costos asociados a la supresión de los pesos individuales correspondientes a esa entrada.
La estrategia consiste en eliminar las entradas con saliencia pequeña, es decir cuya eliminación cause el mínimo aumento en el valor de E. Debido a las aproximaciones se recomienda usar OCD iterativamente: alternar la poda de un pequeño número de entradas con el reentrenamiento.
El uso de redes neuronales artificiales para la selección de variables es atractivo porque estas tienen el potencial de optimizar simultáneamente la clasificación y la selección de características.
3. Algoritmo de Ramificación y Acotamiento.
Narendra y Fukunaga [14] propusieron el algoritmo de ramificación y acotamiento (branch and bound). Este método garantiza la selección de un conjunto óptimo de características si se cumple la condición de monotonicidad.
La base del algoritmo de ramificación y acotamiento es por una parte que la función criterio sea monotónica y por otra, imponer una cota inferior al valor máximo (óptimo) de esta función. De esta manera, si la función criterio es evaluada en un nodo y su valor es inferior al umbral, entonces por monotonicidad todos los nodos sucesivos tendrán valores menores y no pueden ser soluciones óptimas.
El problema es cómo seleccionar funciones de evaluación monotónicas. La selección de características se realiza en base a muestras finitas y debe referirse al desempeño de un clasificador particular en vez de las propiedades discriminantes intrínsecas de los datos. La tasa de error de un clasificador no Bayesiano, no satisface la condición de monotonicidad, porque la estimación basada en un número finito de muestras introduce errores. Por esta razón la tasa de error del clasificador es poco útil en el procedimiento de ramificación y acotamiento.
Cuando se cumple la condición de monotonicidad, se escoge visitar el nodo con la mayor tasa de error, porque esto aumenta la posibilidad de encontrar el próximo nodo no factible y podar parte del reticulado.
Para predecir el mejor valor del umbral, se pueden utilizar los métodos de búsqueda secuenciales hacia adelante o hacia atrás para encontrar la mejor trayectoria en el reticulado. De esta manera se obtiene una estimación del mínimo error alcanzable, como una función del número de características eliminadas. Ambos métodos pueden descarrilarse fácilmente. Por eso se recomienda una búsqueda bidireccional comenzando por los dos extremos.
El algoritmo de ramificación y acotamiento presenta dos problemas importantes. Primero, debido a la condición de monotonicidad impuesta sobre la función objetivo, el algoritmo puede ser incapaz de encontrar la solución óptima si la región de factibilidad es inconexa. Segundo, el algoritmo realiza una exploración exhaustiva de la región factible, la que crece en función de 2n-m, donde n es la dimensión del espacio original de entradas y m es la dimensión del espacio de entradas seleccionadas. Varios autores han señalado que el algoritmo de ramificación y acotamiento se vuelve poco práctico para dimensiones mayores que 20 del espacio de búsqueda (se puede abandonar la optimalidad y recurrir a métodos heurísticos).
Sólo los métodos que son potencialmente capaces de visitar todos los nodos del reticulado son óptimos. Cuando no se ponen restricciones al examen de los nodos del grafo, el método de rama y acotamiento conduce a una búsqueda exhaustiva.
4. Algoritmos Genéticos y Redes Neuronales.
Los algoritmos genéticos (AGs) [6] parecen adecuados para resolver el problema de selección de características debido a su paralelismo inherente, su búsqueda guiada de las regiones más promisorias, su habilidad para encontrar y mantener múltiples óptimos, y su habilidad para optimizar criterios no derivables.
En [1,7] se propuso un algoritmo genético de nichos para la selección de características para clasificadores neuronales. Los métodos de nichos permiten la formación de subpoblaciones estables de tiras binarias diferentes dentro de un algoritmo genético, permitiendo encontrar y mantener múltiples óptimos locales. En el método de nichos denominado hacinamiento determinístico (deterministic crowding) [6], todos los elementos de la población son apareados aleatoriamente y recombinados. La descendencia resultante sostiene un torneo con su padre más cercano (en términos de distancia de Hamming). Los ganadores se copian a la nueva población para la próxima generación.
Para el problema de selección de características, los individuos de la población se representan como tiras binarias, donde un "0" en la i-ésima posición indica que la i-ésima característica se excluye del subconjunto de características, y un "1" indica que la característica está presente [20].
En la Figura 3 se ilustra el enfoque híbrido utilizado: el algoritmo genético optimiza la selección de entradas mientras que para la evaluación de los individuos de la población se entrenan clasificadores neuronales.
Figura 3. Combinación de Algoritmos Genéticos y Redes Neuronales para la Selección de Características.
Para evaluar la adaptación de un individuo, el subconjunto de características seleccionadas se usa como entrada a un clasificador neuronal de arquitectura fija. La función de adaptación combina dos criterios de optimización: minimizar la tasa de error del clasificador y minimizar el número de características. La adaptación de un individuo z se expresa como,
donde exactitud(z) es la tasa de clasificación por unidad del individuo z en el conjunto de validación, ncar(z) es el número de características seleccionadas y L es el número original de características disponibles. El parámetro l controla el compromiso entre los dos criterios (típicamente l =0,01). El cálculo del término exactitud(z) es la parte más costosa del algoritmo.
Para reducir el ruido en la evaluación de la adaptación cada individuo se evalúa un número fijo de veces (típicamente tres veces) y la máxima adaptación alcanzada se escoge como representativa de ese individuo. Por otra parte, para evitar cálculos repetitivos, los individuos sobrevivientes de una generación a otra heredan sus evaluaciones de adaptación. Este procedimiento ahorra tiempo computacional en las generaciones posteriores debido a la convergencia de la mayoría de la población.
Un nuevo operador de mutación se ha introducido con el propósito de acelerar la convergencia del algoritmo genético [7]. Este operador de mutación se basa en un método de eliminación de pesos denominado SSM [3] que elimina los pesos no-significativos de una red neuronal. Este método elimina los pesos pequeños relativos a su desviación estándar estimada. La idea central detrás de este operador de mutación es extender el método SSM a la eliminación de entradas (características) mediante la poda de todos los pesos asociados a tales entradas.
4.1 Enfoque Estadístico.
Un método alternativo de selección de características es utilizar medidas estadísticas. En [8] se utilizan tres funciones objetivos: variación intra-clase (i.e. varianza de las características dentro de la misma clase), variación inter-clase (i.e. separación entre clases), y correlación entre características.
Supongáse que el conjunto de entrenamiento contiene 
patrones de la clase j. Sea 
el valor medido de la característica x para el i-ésimo patrón en la clase j. La variación intra-clase normalizada de la característica x dentro de la clase j se define como:
donde
es la varianza,
es el valor medio de la característica x para la clase j, y 
es la variación intra-clase promedio de la característica x.
La variación inter-clase total de la característica x, entre la clase j y las otras K clases se calcula como sigue:
.
Por otra parte la correlación entre la característica x y la característica y dentro de la clase j se mide mediante el siguiente coeficiente de correlación:
.
El criterio de rechazo de características utilizado en [8] es eliminar la característica con la mayor variación intra-clase si su variación inter-clase es menor que un cierto valor (empíricamente escogido como 8). Las características examinadas en cada clase son después examinadas por redundancia. Para esto se utiliza un diagrama en donde los nodos representan características y las líneas unen características altamente correlacionadas (i.e. con un coeficiente de correlación de valor absoluto mayor que 0,9). Cuando dos nodos están unidos entonces el nodo con la menor variación inter-clase total es rechazado. Cuando un nodo está conectado con varios nodos, los nodos externos son retenidos con el objeto de minimizar el número de nodos a ser rechazado. Este procedimiento se sigue comenzando desde el nodo 1 y luego moviéndose en la dirección de los punteros de reloj hasta que todas las características han sido recorridas [8].
5. Resultados de Simulaciones.
Para fines de comparación entre el algoritmo genético y el algoritmo de ramificación y acotamiento se utilizaron 6 bases de datos publicadas por la Universidad de California en Irvine, comúnmente citadas en la literatura de reconocimiento de patrones [1,9]. A continuación se entrega una breve descripción de estas bases de datos:
- Reconocimiento de Vinos. Los datos corresponden a la medida de 13 componentes químicas en tres clases de vinos italianos provenientes de cultivos diferentes. Se dispone de 178 muestras en total.
- Flores Iris. Los datos corresponden a cuatro atributos (largo y ancho de sépalos y pétalos) medidos para tres clases de flores. Se dispone de 150 muestras en total.
- Ionosfera. Los datos corresponden a 34 características de señales de retorno de radar medidas para dos clases. Se dispone de 351 muestras en total.
- Enfermedades del Hígado. Los datos corresponden a seis exámenes y se clasifican en dos grupos. Se dispone de 345 muestras en total.
- Diabetes. Los datos corresponden a ocho atributos que son el resultado de exámenes médicos y se clasifican en dos grupos. Se dispone de 768 muestras en total.
- Cáncer Mamario. Los datos corresponden a 30 atributos de imágenes digitalizadas de tejido mamario. Se dispone de 569 muestras en total.
En la Tabla 1 se observa como el algoritmo genético tiene una conducta similar al de ramificación y acotamiento para dimensiones menores a 20. Por otro lado en los casos del alta dimensionalidad del espacio de búsqueda, como en las bases de datos de la ionosfera y del cáncer, el resultado obtenido con el algoritmo genético supera al obtenido por ramificación y acotamiento.
Tabla 1. Comparación de resultados de simulación entre algoritmo genético (AG) y algoritmo de ramificación y acotamiento (BB).
|
Base Datos |
N° Caract. Original |
N° Caract Selec |
AG |
BB |
||
|
Clasif. Correc |
N° Sol |
Clasif. Correc |
N° Sol |
|||
|
Vino |
13 |
3 |
100% |
2 |
97% |
1 |
|
Iris |
4 |
2 |
98% |
1 |
98% |
1 |
|
Ionosfera |
34 |
5 |
94% |
4 |
87% |
1 |
|
Higado |
6 |
5 |
75% |
1 |
75% |
1 |
|
Diabetes |
8 |
5 |
75% |
5 |
75% |
1 |
|
Cáncer |
30 |
2 |
99% |
11 |
95% |
1 |
Nótese que ambos métodos permiten disminuir drásticamente el número de características.
5.1 Clasificación de Defectos en Maderas.
Se ha construido una base datos conteniendo imágenes a color (320x240 pixeles) de madera de pino radiata. La Tabla 2 muestra los 900 objetos detectados, distribuidos en 9 categorías: acículas, bolsillos de corteza, bolsillos de resina, cantos muertos, grietas, manchas, médulas, nudos y perforaciones. La Figura 4 ilustra una muestra por cada una de las nueve categorías de defectos. Estas categorías fueron seleccionadas en base a las normas chilenas de calidad para tablas de pino radiata.
Tabla 2. Base de Datos de Defectos en Madera.
| Categoría | Defectos | |
| A | Acículas | 100 |
| B | Bolsillos de Corteza | 100 |
| C | Bolsillos de Resina | 100 |
| D | Canto Muerto | 100 |
| E | Grietas | 100 |
| F | Manchas | 100 |
| G | Médulas | 100 |
| H | Nudos | 100 |
| I | Perforaciones | 100 |
| Total | 900 | |
De cada objeto detectado se extrajeron setenta y dos características. Primero, se midieron 24 características geométricas sobre la imagen binarizada obtenida a partir de la imagen de niveles de gris. Luego se extrajeron 12 características de color para cada uno de los cuatro canales (RGB + gris), del área correspondiente al objeto en la imagen original con 256 niveles de intensidad.
Figura 4: Muestras de imágenes de cada una de las nueve categorías. En la fila superior de izquierda a derecha: acículas, bolsillos de resina y de corteza; en la segunda fila: canto muerto, grieta y mancha; en la fila inferior: médula, nudo y perforación.
Los datos se dividieron aleatoriamente en tres conjuntos: un conjunto de entrenamiento (540 muestras), un conjunto de validación (180 muestras) y un conjunto de prueba (180 muestras).
En el enfoque estadístico, las características con mayor variación intra-clase fueron eliminadas si su variación inter-clase era menor que 8. En segundo lugar, se eliminaron aquellas características con una variación inter-clase total de menos de 1,5. En tercer lugar, se usó el criterio de correlación para identificar características redundantes.
La selección de características para cada clase se completó haciendo la operación AND entre las tablas resultantes al aplicar los tres criterios mencionados más arriba. Aquellas características rechazadas por 5 o más clases fueron eliminadas. Con este procedimiento (ES1: Enfoque estadístico usando los cuatro canales), 29 de 72 características fueron eliminadas. Un análisis de las características eliminadas mostró que 8 de 12 características del canal verde habían sido descartadas. Entonces se diseñó un segundo procedimiento para descartar completamente el canal verde (ES2: Enfoque estadístico sin canal verde) mediante el reemplazo de las características seleccionadas del canal verde por otras correlacionadas dentro de lo posible, o simplemente eliminándolas.
En la Tabla 3 se muestran los resultados de simulaciones para el conjunto de prueba, obtenidos mediante tres métodos de selección de características: ES1, ES2 y AG, además de método de control (TODOS), que usa el conjunto completo de características disponibles. En los experimentos que se reportan aquí, se usó una red MLP con 15 unidades ocultas y 9 unidades de salida. El número de entradas varió de acuerdo al número de características seleccionadas por cada método. Se hicieron 10 simulaciones en cada caso, con inicializaciones aleatorias de pesos. Para controlar la aleatoriedad introducida por las condiciones iniciales, las mismas 10 inicializaciones aleatorias de pesos fueron usadas en cada método (descartando las columnas de la matriz de pesos correspondientes a las características eliminadas). Este procedimiento se diseñó para llevar a cabo una prueba t pareada, donde las tres variaciones (ES1, ES2 y AG) se comparan con el método base (TODOS).
El clasificador se modeló como una red perceptrón multicapa entrenada mediante un algoritmo de segundo orden del tipo cuasi-Newton denominado BPQ [17]. Las redes se entrenaron por 300 épocas, y los pesos correspondientes al mínimo error sobre el conjunto de validación fueron almacenados y probados en el conjunto de prueba. Se utilizó un término de regularización del tipo weight decay con un factor de e=0,005 [5].
En el método AG se utilizaron los siguientes parámetros: tamaño de la población P=100, l =0,01, parámetros de mutación (M=3, g=0,6 y d =10%, ver [7]). Las tiras binarias representando subconjuntos de características evolucionaron por 100 generaciones, usando el algoritmo de entrenamiento BPQ sobre redes MLP de 10 unidades ocultas (este número se escogió de manera de no sobrecargar los cálculos del algoritmo genético). No se requieren parámetros adicionales ya que el método BPQ usa un tamaño de paso adaptivo y el algoritmo AG utiliza selección por torneo y recombinación binomial con probabilidad 1.0. Con este procedimiento (AG) se eliminaron 51 de 72 características. El mejor individuo evolucionado se utilizó para obtener los resultados que se muestran en la Tabla 3.
Tabla 3. Resultados de Simulación en Conjunto de Prueba (m es la tasa promedio de clasificaciones correctas y s es desviación estándar).
|
TODOS |
ES1 |
ES2 |
AG |
|
|
No Caract. |
72 |
43 |
42 |
21 |
|
Media |
88,6 |
91,4 |
88,8 |
91,2 |
|
s |
1,51 |
0,87 |
1,42 |
1,55 |
|
Valor-p |
2E-4 |
0,766 |
7E-4 |
Pruebas t pareadas de doble cola muestran que ES1 es mejor que TODOS, y que AG es mejor que TODOS al nivel de significancia 0,01, usando el ajuste de Bonferroni para múltiples pruebas (significancia nominal 3,3·10-3 por cada prueba pareada) [8]. Notar que AG utiliza sólo la mitad de características que ES1.
6. Conclusiones.
Se ha realizado una introducción a la selección de características para clasificadores neuronales, revisándose los conceptos fundamentales del problema así como los principales algoritmos existentes.
Por otra parte se han mostrado resultados de simulaciones que comparan los algoritmos genéticos con el método de ramificación y acotamiento en varias bases de datos, encontrándose desempeños similares para dimensiones menores que 20. También se compararon los algoritmos genéticos con métodos basados en medidas estadísticas, para un problema del mundo real. Los resultados indican que los algoritmos genéticos son muy efectivos en la selección de características, reduciendo drásticamente el número de características y mejorando incluso el desempeño del clasificador.
Agradecimientos.
Se agradece el financiamiento obtenido a través de Conicyt-Chile bajo el Proyecto Fondecyt 1980909, y del Departamento de Ingeniería Eléctrica de la Universidad de Chile.
Referencias.
[1] Caballero, R., Algoritmos Genéticos para la Selección de Entradas a Clasificadores Neuronales, Memoria de Ingeniero Civil Electricista, Universidad de Chile, 1998.
[2] Cibas, T., Fogelman-Soulie, F., Gallinari, P., and Raudys, S., Variable Selection with Neural Networks, Neurocomputing, Vol. 12, pp. 223-248, 1996.
[3] Cottrell, M., Girard, B., Girard, Y., Mangeas., M and Miller, C., Neural Modeling for Time Series: A Statistical Stepwise Method for Weight Elimination, IEEE Tran. Neural Networks, Vol. 6, N° 6, pp. 1355-1364, Nov. 1995.
[4] Cover, T. and Van Campenhout, J., On the Possible Orderings in the Measurement Selection Problem, IEEE Trans. Systems, Man and Cybernetics, Vol. SMC-7, pp. 657-661, Sept. 1977.
[5] Estévez, P., Clasificación de Patrones mediante Redes Neuronales Artificiales, Anales del Instituto de Ingenieros de Chile, Vol. 111, N°1, pp.24-31, Abril 1999.
[6] Estévez, P., Optimización mediante Algoritmos Genéticos, Anales del Instituto de Ingenieros de Chile, Vol. , N°1, pp. 83-92, Agosto 1997.
[7] Estévez, P., and Caballero, R., A Niching Genetic Algorithm for Selecting Features for Neural Network Classifiers, Perspectives in Neural Computation (ICANN-98), Vol. 1 , pp. 311-316, Springer-Verlag, 1998.
[8] Estévez, P., Fernández, M., Alcock, R., and Packianather, M., Selection of Features for the Classification of Wood Board Defects, ICANN-99, Vol. I, pp. 347-352, IEE Press, 1999.
[9] Estévez, P., Combination of Neural Networks and Genetic Algorithms for Classification and Prediction Tasks, in Novel Intelligent Automation and Control Systems, J. Pfeiffer (editor), Papierflieger, Clausthal-Zellerfeld, pp. 97-104, 1998.
[10] Haykin, S. Neural Networks a Comprenhensive Foundation, IEEE Press, 1994.
[11] Jain, A. and Zongker, D., Feature Selection: Evaluation, Application and Sample Performance, IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 19, N° 2, pp. 153-158, February 1997.
[12] Kittler, J. Feature Selection and Extraction, in Handbook of Pattern Recognition and Image Processing, T.Y. Young and K.S. Fu Eds., Academic Press, Chapter 3, pp. 59-83, 1986.
[13] Le Cun, Y., Denker, J.S. and Solla, S.A., Optimal Brain Damage, Neural Information Processing Systems (NIPS-89), D. Touretzky ed., Morgan-Kauffman, Vol. 2, pp. 598-605, 1990.
[14] Narendra, P.M. and Fukunaga, K., A Branch and Bound Algorithm for Feature Subset Selection, IEEE Trans. Computers, Vol. 26, N° 9, pp. 917-922, Sept. 1977.
[15] Pudil, P., Novovicova, J. and Kittler, J., Floating Search Methods in Feature Selection, Pattern Recognition Letters, Vol. 15, pp. 1119-1125, Nov. 1994.
[16] Rumelhart, D.E., Hinton G.E., and Williams R.J., Learning Internal Representations by Error Propagation, in Parallel Distributed Processing: Explorations in the Microstructure of Cognition (D.E. Rumelhart, J.L. McClelland and PDP Research Group Eds.), Vol. I, Cambridge, MA: MIT Press, pp. 318-362, 1986.
[17] Saito, K. and Nakano, R. Partial BFGS Update and Efficient Step-Length Calculation for Three-Layer Neural Networks, Neural Computation, Vol. 9, pp. 123-141, 1997.
[18] Schifferli, G. Sistema de Apoyo al Tratamiento Farmacológico de la Hipertensión Arterial Esencial, Tesis de Magister en Ingeniería Biomédica, Depto. Ing. Eléctrica, Universidad de Chile, 1998.
[19] Siedlecki, W. and Sklansky, J., On Automatic Feature Selection, Int. J. of Pattern Recognition and Artificial Intelligence, Vol. 2, N° 2, pp. 197-220, 1988.
[20] Siedlecki, W. and Sklansky, J., A Note on Genetic Algorithms for Large-Scale Feature Selection, Pattern Recognition Letters, Vol. 10, pp. 335-347, Nov. 1989.
[21] Trunk, G.V., A Problem of Dimensionality: A Simple Example, IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. PAMI-1, pp. 306-307, July 1979.