DISEÑO DE UNA CLASE DE SISTEMAS BORROSOS RECURRENTES MEDIANTE ALGORITMOS GENÉTICOS PARA

LA TAREA DE CLASIFICACIÓN DE PATRONES

J. Estévez

iestevez@ull .es S. Alayón

sil via@cyc.dfis.ull .es L. Moreno

lmoreno@ull .es R. Aguilar

raguilar@ull .es J. Sigut

jfsigut@ull .es Centro Superior de Informática, Universidad de La Laguna

Tenerife – España

Resumen El presente artículo aborda la problemática del reconocimiento de patrones con una máquina de estados borrosa. Mediante algoritmos genéticos se pretende encontrar una máquina óptima que sea capaz de reconocer distintos patrones. Para validar este sistema, se ha apli cado la máquina al reconocimiento de patrones simulados (reconocimiento de series temporales generadas por modelos ocultos de Markov) para luego aplicarla a un problema real: reconocimiento de patrones en imágenes médicas. Además, se ha comparado la efectividad de este método como clasifi cador de patrones con otros métodos ya existentes, tanto supervisados como no supervisados. Palabras Clave: Reconocimiento de Patrones, Sistemas Borrosos Recurrentes, Algoritmos Genéticos. 1 INTRODUCCIÓN Una Máquina de Estados Borrosa Finita (Fuzzy Finite State Machine - FFSM) es una extensión del Autómata Determinista Finito (Finite Deterministic Automaton - FDA). Este algoritmo se apli ca en diversas áreas: reconocimiento de patrones, modelado de agentes inteligentes, interfaces humano-máquina y en la ingeniería de control. A pesar de basarse en uno de los modelos computacionales más clásicos, la investigación y la obtención de apli caciones para este algoritmo es aún un tema relativamente poco investigado, extremo que se comenta en algunas de las últimas publicaciones sobre autómatas borrosos. Sin embargo, se trata de un algoritmo que puede tener un gran potencial dado que incorpora un procesamiento recurrente basado en el concepto de estado interno y el esqueleto simbólico proporcionado por la teoría de la lógica borrosa, conceptos que por separado se han mostrado

enormemente útiles en los campos mencionados [13,3]. Muchos sistemas automáticos diseñados para la detección de patrones encajan en este modelo. Como un ejemplo, podemos citar el sistema de análisis de objetos y escenarios denominado VISOR [8,9]. Está basado en la apli cación combinada de esquemas visuales y redes neuronales para la detección de objetos y el análisis de escenarios. En este sistema se asocian niveles de activación a la percepción de las componentes básicas del objeto así como a la activación global de los subsistemas. El sistema de percepción VISOR evoluciona dinámicamente en base a los niveles de activación registrados en la etapa anterior. Otro ejemplo, es el sistema borroso recurrente utili zado en [15] para la predicción de una serie temporal. En este caso el proceso reali zado tiene como objetivo la extracción de información simbólica obtenida mediante la adaptación automática de un sistema borroso recurrente, una estrategia que se estudia en la investigación que se plantea en este artículo. En el campo del análisis de señales médicas, que es el campo donde esta investigación tendrá su apli cación real, tenemos como referencia los trabajos de [14,5]. En el primero de ellos se plantea la utili zación de autómatas borrosos para la detección de morfologías en señales monitorizadas, mientras el segundo introduce el concepto de perfil borroso para el mismo propósito. Sin embargo, estos trabajos no abordan algunos problemas importantes del diseño y lo más importante, la extracción de información relevante a partir del resultado obtenido con el algoritmo del procesamiento simbólico, cuando éste alcanza cierta complejidad. Estas lagunas son importantes ya que imposibilit an la apli cación sistemática de las máquinas de estado borrosas, por lo que uno de los aspectos de este trabajo, como se comentará más adelante, será la automatización de los métodos de diseño y análisis de resultados.

De hecho, la automatización del procedimiento de diseño de máquinas de estado borrosas se puede entender como un problema de búsqueda en un espacio complejo. Este tipo de problemas se ha afrontado en el caso de las memorias asociativas borrosas también conocidas como sistemas de inferencia borrosos, mediante algoritmos evolutivos [2], lo que nos ha sugerido la apli cación de esta técnica para la síntesis automática de máquinas de estado borrosas para la clasificación de patrones en medicina, concretamente para la clasificación de texturas en imágenes médicas. Este problema es muy importante en áreas como la detección precoz del cáncer mediante el análisis de núcleos celulares [10].

El siguiente artículo está distribuido en tres partes principales que son la descripción de los sistemas borrosos así como de los algoritmos genéticos utili zados, el estudio y apli cación de los algoritmos a la clasificación de series temporales sobre modelos simulados y patrones extraídos de imágenes médicas y, finalmente, las conclusiones de la investigación reali zada. 2 DESCRIPCIÓN DE LOS

ELEMENTOS BÁSICOS 2.1 DESCRIPCIÓN DE LA MÁQUINA DE

ESTADOS BORROSA Como se ha mencionado anteriormente, una Máquina de Estados Borrosa Finita (Fuzzy Finite State Machine - FFSM) es una extensión del Autómata Determinista Finito (Finite Deterministic Automaton - FDA). Un modelo FFSM se caracteriza por tener dos propiedades importantes: los eventos externos producen transiciones graduales entre los estados internos del sistema y todos los estados del sistema están activos a la vez, pero con diferentes niveles de activación. Como se muestra en la Figura 1, los elementos más importantes para implementar el sistema basado en máquinas de estado borrosas son los Sistemas de Inferencia Borrosos (Fuzzy Inference Systems – FISs) [7], donde se obtiene el nivel de activación de cada estado. Las entradas para estos sistemas son por una parte, la señal externa, y por otra, los niveles de activación de todos los estados de la máquina de estados borrosa. En este trabajo estamos utili zando sistemas borrosos del tipo TSK. La definición del modelo FFSM empieza a partir de un modelo discreto donde los estados pueden ser activados simultáneamente con diferentes niveles de

activación. El modelo discreto de FSM es un conjunto compuesto por ocho elementos:

,,,,,,, 0 WTsIS pLM Ω=Φ ησ

El conjunto S= S1, S2, …, SM está constituido por los estados internos del sistema. El conjunto I= I1, I2, …, IL contiene las entradas externas. σM se obtiene como el producto cartesiano de los M conjuntos σi: σM = σ1 × σ2 × … × σM. Cada σi es un conjunto totalmente ordenado compuesto por los N(i) niveles de activación del estado interno Si: σi = σi

1, σi

2, …, σiN(i) . Los indices se asignan de modo que si

i > j, entonces σki > σk

j. ηL es el producto cartesiano de los L conjuntos ηi, donde cada ηi está compuesto por los niveles de activación de la entrada externa I i. Por lo tanto, ηL = η1 × η2 × … × ηM y ηi = ηi

1, ηi2,

…, ηIR(i) . También existe una relación de orden

definida en cada ηi y los índices se asignan tal que si i>j entonces ηk

i > ηk

j.

Figura 1. Diagrama de bloques de una máquina

borrosa con tres estados. El estado inicial es s0 y está definido por los niveles de activación de los estados internos en el instante inicial. La función de transición W: ηL×σM→σM da la dinámica del sistema. Esta función se usa para obtener un nuevo estado F’=W(O,F) que proviene de una pareja (O,F) con O ∈ σM y F∈ ηL (descripción de los estados internos y de la entrada externa). El primer paso en el proceso de hacer borroso el modelo discreto consiste en definir los elementos σi

j

y ηij como conjuntos borrosos sobre ℜ, con

funciones de pertenencia )(xijσµ y )(xi

jηµ que

cumplan las propiedades de normalidad y convexidad. El modelo discreto incluye la función de transferencia W: ηL×σM→σM. Esta función puede ser expresada por medio de un conjunto de reglas lógicas RσM×ηL, σM del tipo: Si E1= ηi1 y E2= ηi2 y …EL= ηiL S1=sj1 y S2 = sj2 …y SM=sjM entonces S’=Sc donde E=(ηi1, ηi2, …, ηiL) ∈ ηL, S=(si1,si2,…,siM) ∈ σM y Sc∈ σM. El sistema FFSM que responde a estas características será diseñado y utili zado por nosotros para abordar la problemática del reconocimiento de patrones en dos situaciones distintas: con datos simulados, para la clasificación de series temporales, y con datos médicos reales, para la detección de núcleos de células afectadas por cáncer. La elección de este tipo de algoritmos está motivada por las siguientes propiedades:

1. El sistema “recuerda” los estados pasados. Esto es importante cuando las muestras previas influyen en el reconocimiento del patrón.

2. Tiene un comportamiento borroso, que permite tratar situaciones donde el patrón a detectar no está definido de manera “precisa”.

3. Proporciona información simbólica sobre el detector: la base de reglas contiene información simbólica que explica los motivos por los cuales el patrón es detectado. La estructura FFSM está basada en una base de reglas formada por dos partes: en primer lugar, el conjunto de antecedentes, descrito por funciones de pertenencia gaussianas con desviaciones fijas y centros variables. Estas funciones de pertenencia representan los niveles de activación para los estados internos del sistema y la entrada externa. En segundo lugar, el conjunto de consecuentes, donde cada vector consecuente cambia para cada estado de la máquina. Hemos adoptado el modelo TSK en su forma más sencill a, donde los valores de los consecuentes son constantes. 2.2 DESCRIPCIÓN DE LOS ALGORITMOS

EVOLUTIVOS UTILIZADOS Para buscar el sistema FFSM más óptimo capaz de reconocer los patrones de cada problemática, hemos empleado una estrategia basada en algoritmos evolutivos. El primer paso es extraer características del dominio de aprendizaje de cada problema. En nuestro caso, el

vector de características es un conjunto de datos ordenado que denominaremos “traza”. Esta extracción de características y elaboración de trazas será comentada en detalle más adelante, cuando describamos los problemas concretos en los que se utili zó el modelo FFSM para reconocer patrones. Una vez analizado el dominio de esta manera, se agrupan las trazas en dos conjuntos distintos: el conjunto de entrenamiento y el conjunto de test. Estas trazas serán la entrada externa del modelo FFSM. Las trazas del conjunto de entrenamiento constituyen para el sistema FFSM ejemplos sobre lo que debe aprender a reconocer. Con un algoritmo genético, hacemos evolucionar una población de máquinas de forma que la capacidad de clasificación de los individuos sea mejorada en cada iteración. Es un algoritmo supervisado porque además de las trazas de entrenamiento, se le proporciona la solución correcta de la clasificación. Una vez encontrada la mejor máquina según este algoritmo, se comprueba la calidad del aprendizaje. Para ello, se evalúa la máquina con el conjunto de test y se analiza su capacidad de generali zación. El conjunto de test está constituido por trazas del mismo dominio de aprendizaje distintas a las utili zadas en el entrenamiento de la máquina. Se ha utili zado un procedimiento estándar para el diseño del algoritmo genético [1]. En la figura 2 se muestra un diagrama de este proceso. El algoritmo diseñado se desarrolla en los siguientes pasos:

1. Generación aleatoria de una población inicial compuesta por un número determinado de modelos FFSM. Estas estructuras iniciales evolucionarán en cada iteración del algoritmo.

2. Evaluación de cada máquina de la población con las trazas del conjunto de entrenamiento. A cada individuo se le asigna una cota numérica o valor de fitness que refleja la bondad de su capacidad de clasificación (es una medida de cuánto se acerca su salida con la deseada). Si alguna máquina tiene el valor de fitness buscado el algoritmo para y ofrece como resultado esa máquina. Si no, continúa en los siguientes pasos. En nuestro caso, cuanto mejor sea la máquina, más pequeño será el valor de fitness.

3. Se ordena la población según su fitness y se seleccionan las mejores máquinas con un algoritmo de selección. A partir de estas máquinas seleccionadas, se reali za una repoblación mediante el uso de operadores genéticos hasta completar el número total de máquinas que componen la población.

4. Se repiten los pasos 2 y 3.

Figura 2. Algoritmo evolutivo usado para encontrar

el mejor modelo FFSM. Los algoritmos genéticos son optimizadores globales que tienen la capacidad de llevar a cabo una búsqueda en el espacio de entrada. Son muy flexibles porque la función de fitness puede incluir líneas de diseño y restricciones y la naturaleza del proceso de búsqueda evita mínimos locales. Por esta razón han sido usados en muchas ocasiones para encontrar configuraciones adecuadas y parámetros en sistemas borrosos [2]. En nuestro caso, el algoritmo genético se usa para reali zar una búsqueda en un espacio compuesto por modelos FFSM.

La función de fitness compara la salida del modelo FFSM con el resultado deseado y calcula el valor de fitness de la siguiente manera: el modelo FFSM tiene un número fijo de estados, el último de ellos se selecciona como estado de detección. Tras evaluar el FFSM con una traza del conjunto de entrenamiento, se extrae como parámetro el número de veces que el nivel de activación del estado de detección supera un umbral predefinido. Este valor se divide por el número total de muestras de la traza (contador de activación). Este parámetro es una medida de la reacción de la máquina al procesar una traza. Una vez que se obtiene este parámetro para todas las trazas que componen el conjunto de entrenamiento, se apli ca un algoritmo de clustering que trata de dividir los parámetros en dos grupos. A continuación, se compara estos grupos con la clasificación real de las trazas y se asigna un valor numérico de fitness en función de esta comparación. La población inicial suele tener valores de fitness malos. Por eso es necesario hacerla evolucionar por medio de operadores genéticos. Hemos elegido la aproximación de Pittsburgh [2] para evolucionar nuestros modelos FFSM, usando cruce, mutación y

reproducción (cada operador con una probabili dad diferente) y apli cándolos sobre las máquinas escogidas por el algoritmo de selección (paso 3). Estas máquinas, junto con las generadas con los operadores genéticos, constituirán la población de la siguiente evolución del algoritmo. A continuación se describe lo que hacen exactamente los tres operadores: - Cruce: seleccionamos al azar dos máquinas, y cruzamos un número determinado de reglas (antecedentes y consecuentes) entre ellas. Las dos nuevas máquinas resultantes se introducen en la nueva población. - Mutación: la mutación opera sólo sobre un individuo de la población. Una vez escogido este individuo (máquina), se selecciona al azar un número determinado de sus reglas (antecedentes y consecuentes) y se sustituyen por antecedentes y consecuentes nuevos generados aleatoriamente. Este nuevo individuo se añade a la nueva población. - Reproducción: es el más simple de todos. Se elige una máquina que será copiada e introducida en la nueva población, de modo que existan dos versiones de la misma máquina en la población. A continuación, se detallan los problemas concretos que se han tratado de solucionar con la combinación de sistemas borrosos y algoritmos genéticos. 3 PRIMER PROBLEMA:

CLASIFICACIÓN DE SERIES TEMPORALES

3.1 DESCRIPCIÓN DEL PROBLEMA Se han generado dos series temporales distintas utili zando para ello dos modelos ocultos de Markov (HMM) [11]. El objetivo del algoritmo genético es encontrar la máquina de estados borrosa capaz de reconocer las dos series y clasificarlas correctamente. Los dos modelos utili zados en este experimento constan de dos estados ocultos. La dinámica del modelo se establece porque cada estado tiene asociado una probabili dad de activación inicial y una probabili dad de transición a los estados del modelo. Los valores generados se obtienen a partir de experimentos aleatorios que hacen uso de las distribuciones de probabili dad asociadas a cada estado. Para ambos modelos, la distribución de probabili dad es una gaussiana que para el primer estado está centrada en 0.2 y tiene una desviación igual a 0.2, y la gaussiana asociada al segundo estado está centrada en 0.8, con desviación 0.2. La diferencia entre los dos modelos es la probabili dad de transición entre los estados, de modo que los datos resultantes corresponden a series temporales distintas.

Creación aleatoria de la población

inicial

Evaluación de la población.

Cálculo del fitness

Selección de los mejores individuos

Variación de los individuos

Inserción en la población

Solución final

Dichas probabili dades de transición entre estados se describen para cada modelo en la siguiente tabla (Tabla 1):

Probabili dades de transición del primer

estado

Probabili dades de transición del segundo

estado Al estado 1 0.5 0.8 Modelo 1 Al estado 2 0.5 0.2 Al estado 1 0.5 0.6 Modelo 2 Al estado 2 0.5 0.4

Tabla 1. Probabili dades de transición entre estados de

los modelos ocultos de Markov Como se aprecia, se trata de dos modelos de características similares, la única diferencia es que el modelo 1 tiene una tendencia más acentuada a regresar desde el estado 2 al estado 1. De cada modelo se extraen 60 vectores de 15 muestras cada uno. Estos vectores constituyen las trazas con las que se evalúan las máquinas de estados borrosas (señales externas de entrada). La mitad de las trazas de cada modelo constituirá el conjunto de entrenamiento y la otra mitad, el conjunto de test. En la siguiente figura (Figura 3) se muestran trazas pertenecientes a ambos modelos. Como se puede apreciar, para un observador es difícil clasificarlas a priori.

0 5 10 150.4

0.45

0.5

0.55

0.6

0.65

0.7

0.75

0 5 10 15

0.25

0.3

0.35

0.4

0.45

0.5

0.55

0.6

0.65

0 5 10 150.4

0.45

0.5

0.55

0.6

0.65

0.7

0.75

0 5 10 150.3

0.35

0.4

0.45

0.5

0.55

0.6

0.65

0 5 10 150.4

0.45

0.5

0.55

0.6

0.65

0.7

0.75

0 5 10 150.3

0.35

0.4

0.45

0.5

0.55

0.6

0.65

Figura 3. Primera columna: trazas pertenecientes al primer modelo. Segunda columna: trazas

pertenecientes al segundo modelo. 3.2 RESULT ADOS DEL ENTRENAMIENTO Como se ha mencionado antes, el conjunto de entrenamiento está compuesto por 30 trazas pertenecientes a la primera serie temporal y otras 30 pertenecientes a la segunda.

El procedimiento de aprendizaje se desarrolló bajo las siguientes condiciones: - Umbral de fitness: 0 - Tamaño de la población: 200. Cada individuo de esta población es una máquina de estados borrosa (FFSM). - Parámetro del algoritmo de selección: 0.5 (esto implica que el 50% de la población es seleccionada, en orden, según los mejores valores de fitness). - Parámetros de probabili dad para los operadores genéticos usados: p1=0.05 (probabili dad de reproducción), p2=0.75 (probabili dad de mutación), p3=0.2 (probabili dad de cruce). Las variables lingüísticas en los antecedentes de las reglas son representadas por conjuntos borrosos con funciones de pertenencia gaussianas. Cada modelo FFSM se forma según las siguientes especificaciones: - 4 estados. - 10 reglas. - Estado de detección: número 4. - Desviación fija: 0.2. - Centro: elegido aleatoriamente del conjunto 0.1, 0.3, 0.5, 0.7, 0.9 . Tras 4 iteraciones, el algoritmo encontró una máquina capaz de separar los dos tipos de trazas con el valor de fitness requerido (0). En la siguiente figura (Figura 4) se muestra la curva de evolución de fitness del algoritmo:

1 1.5 2 2.5 3 3.5 40

0.002

0.004

0.006

0.008

0.01

0.012

0.014

0.016

0.018

Figura 4. Evolución del fitness. Eje X: número de

iteración. Eje y: valor de fitness La máquina resultante de nuestro experimento se expone a continuación en la siguiente tabla (Tabla 2). Cada fila es una regla. Las primeras cinco columnas son los antecedentes de las reglas. La primera columna es el centro de la función de pertenencia gaussiana para la entrada externa (traza) mientras que las siguientes 4 columnas son los centros de dichas funciones de pertenencia para las activaciones de los estados (4 estados). Las restantes columnas

constituyen los consecuentes de las reglas, cada columna contiene el consecuente de cada estado.

0.5 0.3 0.9 0.5 0.7 0.1294 0.3033 0.2783 0.2890 0.3 0.9 0.3 0.7 0.1 0.3755 0.0228 0.2816 0.3201 0.5 0.9 0.7 0.7 0.3 0.3179 0.2219 0.2639 0.1964 0.1 0.1 0.3 0.1 0.9 0.3724 0.1898 0.4176 0.0202 0.5 0.5 0.1 0.3 0.9 0.2903 0.2725 0.3600 0.0772 0.3 0.1 0.9 0.5 0.3 0.1640 0.2122 0.3198 0.3040 0.1 0.5 0.7 0.7 0.9 0.3469 0.2247 0.3195 0.1089 0.9 0.7 0.9 0.5 0.3 0.2223 0.0792 0.2886 0.4099 0.7 0.1 0.1 0.1 0.9 0.0857 0.0218 0.0860 0.8065 0.1 0.7 0.9 0.5 0.1 0.1536 0.3330 0.0365 0.4769

Tabla 2. Máquina borrosa resultante (ver expli cación

en el texto). Esta máquina, junto con los centros del algoritmo de clustering, forma el clasificador final. Estos centros son [0.8101, 0.2539]. Este clasificador final clasificó correctamente todas las trazas pertenecientes al conjunto de entrenamiento (100% aciertos). 3.3 RESULT ADOS DEL TEST Para medir la capacidad de generali zación de la máquina obtenida, se evaluó dicha máquina con las trazas pertenecientes al conjunto de test y se separaron los resultados por medio del algoritmo de clustering. También en este caso, todas las trazas fueron clasificadas correctamente (100% aciertos). 3.4 RESULT ADOS OBTENIDOS

MEDIANTE ESTIMACIÓN DE PARÁMETROS DEL HMM

Para contrastar este resultado se usó un método alternativo de clasificación. En este sentido, se eligió un algoritmo expresamente diseñado para la clasificación del tipo de series temporales generadas por un modelo oculto de Markov. Con el conjunto de entrenamiento y con el algoritmo de Baum Welch [6] se estimaron los modelos ocultos de Markov para cada clase (modelo 1 y modelo 2). El proceso de clasificación de una traza consiste en calcular la verosimilit ud de que el modelo X haya generado dicha traza. La clase asignada a la traza será aquella cuyo modelo asociado tenga mayor verosimilit ud de haberla generado. Aplicando este proceso de clasificación sobre las trazas pertenecientes al conjunto de test, se obtienen los siguientes resultados: - De las 30 trazas pertenecientes a la primera serie, 17 son clasificadas como tales y 13 se clasifican como pertenecientes al otro modelo, es decir, tiene un porcentaje de aciertos del 56.67% y 43.33% de error.

- De las 30 trazas pertenecientes a la segunda serie, 21 son clasificadas correctamente, lo que representa un 70% de aciertos y un 30% de error. Es evidente que el clasificador basado en la máquina de estados borrosa encontrada por el algoritmo genético ofrece resultados mucho mejores (100% aciertos), demostrando tener una mayor capacidad de generali zación. Es precisamente esta capacidad de generali zación ante este tipo de series temporales Markovianas uno de los atributos más reseñables del algoritmo. 4 SEGUNDO PROBLEMA:

CLASIFICACIÓN DE NÚCLEOS DE CÉLULAS AFECTADAS POR CÁNCER

4.1 DESCRIPCIÓN DEL PROBLEMA Existen varios métodos para la detección del cáncer. La biopsia (método quirúrgico) es el más eficaz, pero es invasivo, costoso y consume mucho tiempo. Los sistemas de diagnóstico basados en el análisis de imágenes digitales permiten un diagnóstico muy aproximado sin necesidad de intervenciones quirúrgicas. La citología es uno de estos métodos. Nuestro objetivo es clasificar correctamente núcleos de células sanas y núcleos de células patológicas en imágenes digitali zadas de citologías. Para tal fin, contamos con la colaboración del Dr. D. Lucio Díaz Flores (Departamento de Anatomía Patológica del Hospital Universitario de Canarias), que nos cede las imágenes y nos ayuda en la clasificación, desde su conocimiento experto del dominio. La primera aproximación a este problema de reconocimiento de patrones y clasificación la reali zamos con imágenes de cáncer de mama, imágenes correspondientes a la prueba médica de aspiración por aguja fina (Fine Needle Aspirate – FNA) [4]. Sin embargo, en este artículo se presenta el trabajo reali zado con imágenes procedentes de citologías de la zona peritoneal. Utili zando esta base de imágenes, intentamos diseñar y apli car un clasificador que ayude al diagnóstico a partir de este tipo de imágenes. En la siguiente figura (Figura 5), se muestran dos imágenes procedentes de esta base de imágenes de citologías, donde aparecen tejidos sanos y tejidos patológicos.

Figura 5. Izquierda: tejido sano. Derecha: tejido afectado por cáncer.

4.2 EXTRACCIÓN DE

CARACTERÍSTICAS En primer lugar, es necesario seleccionar núcleos de la imagen y extraer características de ellos. Con técnicas estándar de visión por computador, cada imagen se pasa a escala de grises (8 niveles) y cada núcleo de la imagen se aísla del resto. El efecto de la tintura de la muestra se suaviza pasando un filt ro pasa-baja a cada imagen. En el siguiente paso, se lleva a cabo una medida de la textura de cada núcleo diseñada por nosotros. Esta medida constituirá la traza que representa a ese núcleo y entrada al sistema clasificador. Para obtener dicha traza, se reali za un mapa topográfico o mapa de contornos del núcleo. Con este mapa es posible encontrar una característica importante de la textura del núcleo consistente en calcular una medida de complejidad que refleja cómo están distribuidos los contornos en el mapa. Los mapas tienen los contornos distribuidos en 10 escalas o niveles distintos. La medida de complejidad se obtiene contando los contornos que hay en cada nivel y normalizando todos esos valores. Este vector normalizado constituye una traza de 10 valores que representa la textura del núcleo y la entrada externa al sistema FFSM. La razón de desarrollar este descriptor es que hemos observado que las texturas de células benignas tienen áreas grises más homogéneas y contornos más concéntricos que las texturas de células malignas. Es de destacar que la normalización de la traza es un paso importante ya que según se probó en [4] usando trazas no normalizadas, la capacidad de generali zación era bastante pobre. Sin embargo, la utili zación de trazas normalizadas mejora sensiblemente este aspecto, por lo que concluimos que existía una fuerte relación entre la clase del núcleo analizado y la forma relativa en la que se distribuye el conjunto de contornos detectados entre los diferentes niveles.

En la siguiente figura (Figura 6), se muestran los resultados de todo este procedimiento a un núcleo benigno (primera columna) y a un núcleo maligno (segunda columna). El objetivo del algoritmo genético en esta ocasión es encontrar la máquina de estados borrosa capaz de reconocer las dos texturas y clasificarlas correctamente. Para tal fin, y siguiendo el procedimiento anteriormente descrito, se forma un conjunto de entrenamiento y otro de test, con trazas de células que previamente han sido catalogadas como “benignas” o “malignas” por el experto que colabora con nosotros. Encontrar estructuras en series de datos es un problema bien conocido que encuentra apli caciones en muchos campos donde el reconocimiento de patrones es necesario. Para este propósito, se han usado modelos estadísticos lineales (como el ARMAX) y no lineales (como las redes neuronales). Sin embargo, hemos elegido otra aproximación a este problema basado en los sistemas de inferencia borrosos, porque este método nos proporciona información simbólica sobre los motivos por los que las texturas son clasificadas en una u otra categoría. Este hecho es muy importante en áreas como la automatización del diagnóstico médico.

20 40 60 80 100 120

20

40

60

80

100

120

140

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

20 40 60 80 100 120 140 160 180

20

40

60

80

100

120

140

160

180

200

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1 2 3 4 5 6 7 8 9 1 00

0 .1

0 .2

0 .3

0 .4

0 .5

0 .6

0 .7

0 .8

0 .9

1

1 2 3 4 5 6 7 8 9 100

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Figura 6. Núcleo aislado, mapa del núcleo y traza correspondiente para un núcleo benigno (primera

columna) y otro maligno (segunda columna). 4.3 RESULT ADOS DEL ENTRENAMIENTO El conjunto de entrenamiento está compuesto por 15 trazas pertenecientes núcleos benignos y por 15 pertenecientes a núcleos malignos. El procedimiento de aprendizaje se desarrolló bajo las mismas condiciones que en el anterior problema expuesto (reconocimiento de patrones y clasificación de series temporales), al igual que los sistemas

borrosos diseñados. El umbral de fitness en esta ocasión fue fijado en 0.04. Tras 33 iteraciones, el algoritmo encontró una máquina cuyo valor de fitness estaba por debajo del umbral (0.0333) y, por tanto, capaz de separar los dos tipos de trazas. En la siguiente figura (Figura 7) se muestra la curva de evolución de fitness del algoritmo:

0 5 10 15 20 25 30 350

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

Figura 7. Evolución del fitness. Eje X: número de

iteración. Eje y: valor de fitness La máquina resultante de nuestro experimento se expone a continuación en la siguiente tabla (Tabla 3). Al igual que en la notación anterior, cada fila es una regla. Las primeras cinco columnas son los antecedentes de las reglas. La primera columna es el centro de la función de pertenencia gaussiana para la entrada externa (traza) mientras que las siguientes 4 columnas son los centros de dichas funciones de pertenencia para las activaciones de los estados (4 estados). Las restantes columnas constituyen los consecuentes de las reglas, cada columna contiene el consecuente de cada estado. 0.7 0.9 0.3 0.3 0.1 0.2486 0.3173 0.4074 0.0267 0.1 0.7 0.3 0.9 0.7 0.1890 0.3840 0.4064 0.0206 0.3 0.7 0.7 0.9 0.3 0.2149 0.0032 0.0478 0.7341 0.9 0.9 0.1 0.3 0.1 0.2644 0.3974 0.1002 0.2380 0.1 0.7 0.3 0.9 0.7 0.1890 0.3840 0.4064 0.0206 0.1 0.7 0.3 0.9 0.7 0.1890 0.3840 0.4064 0.0206 0.9 0.7 0.9 0.7 0.7 0.1634 0.1603 0.3680 0.3083 0.3 0.7 0.1 0.9 0.3 0.1535 0.0461 0.0599 0.7405 0.7 0.3 0.9 0.3 0.1 0.3254 0.3496 0.2732 0.0518 0.5 0.5 0.1 0.1 0.9 0.4685 0.0465 0.0647 0.4203

Tabla 3. Máquina borrosa resultante (ver expli cación

en el texto). Esta máquina, junto con los centros del algoritmo de clustering, forma el clasificador final. Estos centros son [0.0495, 0.2503]. El grupo de entrenamiento fue clasificado de la siguiente forma:

- De las 15 trazas pertenecientes a células catalogadas como “benignas” por el experto, 14 fueron clasificadas como tal (93 % aciertos, 7% error). - Las 15 trazas correspondientes a células identificadas como “malignas” por el experto fueron clasificadas como tales en su totalidad (100% aciertos). 4.4 RESULT ADOS DEL TEST El conjunto de test está formado por 72 trazas de células benignas y 7 trazas de células malignas, todas ellas clasificadas previamente por el experto. Tras evaluar la máquina resultante con este conjunto, se obtienen los siguientes resultados: - De las 72 trazas de células benignas, 55 fueron clasificadas correctamente (76.38% aciertos, 23.62% error). - Las 7 trazas de células malignas fueron clasificadas todas como tales (100% aciertos).

En resumen, evaluando la máquina sobre el conjunto total (unión del conjunto de entrenamiento y del conjunto de test: 87 trazas de núcleos benignos: 15 de entrenamiento y 72 de test, y 22 trazas de núcleos malignos: 15 de entrenamiento y 7 de test) se obtiene lo siguiente: - De las 87 trazas de núcleos benignos, 69 se clasifican correctamente (79.31% aciertos, 20.69% error). - Las 22 trazas de núcleos malignos se clasifican como tales en su totalidad (100% aciertos). A continuación, se analiza el mismo problema con otros tipos de clasificadores, para comparar sus resultados con los del sistema borroso y analizar de forma comparada la bondad de esta clasificación así como la complejidad del problema de clasificación. 4.5 COMPARACIÓN CON OTROS

MÉTODOS DE RECONOCIMIENTO DE PATRONES Y CLASIFICACIÓN

El primer método de clasificación utili zado fue un método de clustering borroso no supervisado (fuzzy c-means clustering). Se apli có sobre el conjunto total (conjunto de entrenamiento y conjunto de test). Los resultados de la clasificación según este algoritmo fueron los siguientes: - De las 87 trazas correspondientes a células benignas, 65 se clasifican correctamente (74.71% aciertos, 25.29% error). - De las 22 trazas correspondientes a células malignas, 17 se clasifican correctamente (77.27% aciertos, 22.73% error). Estos resultados sirven para obtener una impresión previa de la dificultad de la clasificación sobre el

espacio de vectores de características definido por las trazas extraídas. Es evidente que estos resultados aunque indicativos de la existencia de dos regiones diferenciadas no son buenos, lo que nos lleva al uso de técnicas más elaboradas. Los siguientes clasificadores que se apli caron estaban basados en redes neuronales alimentadas hacia adelante y supervisadas. Se han probado tres redes: con una neurona (red 1), dos neuronas (red 2) y tres neuronas (red 3) en la primera capa y todas ellas, con una neurona en la segunda capa. Se entrenaron con el mismo conjunto de entrenamiento con que entrenamos el algoritmo genético de aprendizaje para la máquina de estados borrosa y se reali zó el test con el mismo conjunto de test. A modo de resumen, en la siguiente tabla (Tabla 4) se muestran los resultados sobre el conjunto de test de las distintas redes neuronales probadas.

Red Neuronal

1

Red Neuronal

2

Red Neuronal

3 Aciertos en

clasificación de trazas benignas

31 aciertos 43.05% aciertos

55 aciertos 76.38% aciertos

48 aciertos 66.66 % aciertos

Error en clasificación de trazas benignas

41 fallos 56.95%

error

17 fallos 23.62%

error

24 fallos 33.34%

error Aciertos en

clasificación de trazas malignas

5 aciertos 71.42% aciertos

5 aciertos 71.42% aciertos

5 aciertos 71.42% aciertos

Error en clasificación de trazas malignas

2 fallos 28.58%

error

2 fallos 28.58%

error

2 fallos 28.58%

error

Tabla 4. Resultados de las redes neuronales.

Comparándolas entre ellas, se observa que las tres tienen el mismo porcentaje de aciertos y fallos en la clasificación de las trazas malignas, pero la red neuronal que tiene dos neuronas en la primera capa se comporta mejor en la clasificación de las trazas benignas, ya que tiene el mayor porcentaje de aciertos. Comparando este resultado con los resultados del clasificador basado en la máquina de estados borrosa, se aprecia claramente que la máquina tiene mejores resultados (100% aciertos en las trazas malignas, 79.31% aciertos en las trazas benignas), lo que puede ser un indicador de que su capacidad de generali zación es mayor. Lo más importante en este tipo de clasificadores es que sean capaces de clasificar las trazas malignas sin error ya que es lo que más ayuda al diagnóstico de este tipo de patologías. Desde esta perspectiva, se observa que es mejor el clasificador constituido por el sistema borroso.

4.6 EVALUACIÓN DE LOS

CLASIFICADORES – CURVAS ROC Es importante evaluar estos clasificadores desde el punto de vista de ayuda al diagnóstico. Para ello, utili zamos el análisis ROC, una metodología desarrollada en el seno de la Teoría de la Decisión en los años 50 y que ha sido muy aplicada en el ámbito de la biomedicina [12,16]. En la toma de decisiones clínicas es necesario valorar la utili dad de cualquier prueba diagnóstica, es decir, conocer su exactitud o capacidad de clasificar correctamente a los pacientes en distintas categorías. Las categorías típicas son: estar enfermo/ no estar enfermo, respuesta positi va/ negativa a la terapia, etc. En nuestro caso, los núcleos se clasifican según la categoría núcleo benigno/ maligno. La “exactitud” diagnóstica se mide en términos de “sensibili dad” y “especificidad” . La “sensibili dad” representa la probabili dad de clasificar correctamente a un individuo cuyo estado real sea definido como “positivo” respecto a la condición que estudia la prueba, es decir, la fracción de verdaderos positi vos (FVP). La “especificidad” es la probabili dad de clasificar correctamente a un individuo cuyo estado real sea definido como “negativo” por la prueba, equivale a 1-FFP (FFP: fracción de falsos positi vos). En la siguiente tabla, se expone esta nomenclatura con mayor claridad (Tabla 5).

Verdadero diagnóstico ENFERMO SANO

Prueba positiva (estar enfermo)

Verdadero Positivo (VP)

Falso Positivo (FP)

Resultado de la prueba

Prueba negativa (no estar enfermo)

Falso Negativo (FN)

Verdadero Negativo (VN)

Sensibili dad =VP/(VP + FN) = FVP (fracción de verdaderos

positivos) Especificidad = VN/(VN + FP) = FVN (fracción de

verdaderos negativos) = 1 - FFP (fracción de falsos positivos)

Tabla 5. Resultado de una prueba y su estado

respecto a la enfermedad.

Supongamos que, tanto para la población sana como para la enferma, la variable de decisión que representa el resultado de la prueba diagnóstica se distribuye normalmente, con media y desviación típica conocidas. En la figura 8 se muestran las funciones de densidad de probabili dad para ambas variables, que mostrarán un determinado nivel de solapamiento. Si consideramos un valor arbitrario del resultado de la prueba, x –valor de corte–, la FVP (sensibili dad) y la FFP (1-especificidad) se corresponderán respectivamente con el área a la

derecha de ese punto bajo la función de densidad de probabili dad de la población enferma (áreas clara y oscura) y de la población sana (área oscura). La curva ROC se obtiene representando, para cada posible elección de valor de corte, la FVP en ordenadas y la FFP en abscisas.

Figura 8. Distribución de los resultados de una prueba en las poblaciones de pacientes sanos y

enfermos. Mediante esta representación de los pares (1-especificidad, sensibili dad) obtenidos al considerar todos los posibles valores de corte de la prueba, la curva ROC nos proporciona una representación global de la exactitud diagnóstica. La curva ROC es necesariamente creciente, propiedad que refleja el compromiso existente entre sensibili dad y especificidad: si se modifica el valor de corte para obtener mayor sensibili dad, sólo puede hacerse a expensas de disminuir al mismo tiempo la especificidad. Si la prueba no permitiera discriminar entre grupos, la curva ROC sería la diagonal que une los vértices inferior izquierdo y superior derecho. La exactitud de la prueba aumenta a medida que la curva se desplaza desde la diagonal hacia el vértice superior izquierdo. Si la discriminación fuera perfecta (100% de sensibili dad y 100% de especificidad) pasaría por dicho punto. En el clasificador obtenido con el algoritmo genético basado en maquinas de estado borrosas, el valor de corte es el umbral que debe superar el nivel de activación del estado de detección. Haciendo un barrido de este parámetro y analizando los resultados de la clasificación (aciertos y errores) se calculan los pares (sensibili dad, 1-especificidad) y la siguiente curva ROC (figura 9):

Valor de corte 1-Especificidad Sensibili dad

0 1 1 0.1 1 1 0.2 1 1 0.3 0.9771 1 0.4 0.8851 1 0.5 0.7702 1 0.6 0.6897 1 0.65 0.4828 1 0.68 0.3679 1 0.7 0.2069 1 0.72 0.1035 0.7272 0.74 0 0 0.8 0 0 0.9 0 0 1 0 0

Figura 9. Curva ROC del clasificador basado en la

máquina de estados borrosa. El mejor clasificador se obtiene con un valor de corte igual a 0.7, ya que con ese valor se obtiene una sensibili dad igual a 1 (100% aciertos en núcleos malignos) y la mayor especificidad posible (mayor porcentaje de aciertos en núcleos benignos). Los resultados expuestos en los apartados 4.3. y 4.4. son los correspondientes al clasificador con este valor de corte (0.7). Esta coincidencia indica la adecuación de la medida de fitness utili zada en el proceso evolutivo. Repitiendo estos mismos cálculos para los clasificadores basados en redes neuronales recurrentes se obtienen las siguientes curvas ROC (figuras 10, 11, 12):

Valor de corte 1-Especificidad Sensibili dad 0 0 0.3181

0.1 0 0.4545 0.2 0 0.5000 0.3 0 0.6818 0.4 0 0.8181 0.5 0.0690 0.8181 0.6 0.1380 0.8181 0.7 0.2759 0.8636 0.8 0.5058 0.9090 0.9 0.7932 0.9090 1 1 1

Figura 10. Curva ROC obtenida para el clasificador formado por la red neuronal 1

Esta red neuronal clasifica mejor cuando su valor de corte está establecido en 0.8, punto donde la sensibili dad y la especificidad son las mayores posibles.

Valor de

corte 1-Especificidad Sensibili dad

0 0.0345 0.2727 0.1 0.1150 0.9090 0.2 0.1150 0.9090 0.3 0.1265 0.9090 0.4 0.1380 0.9090 0.5 0.1495 0.9090 0.6 0.1610 0.9090 0.7 0.1610 0.9090 0.8 0.1610 0.9090 0.9 0.1610 0.9090 1 1 1

Figura 11. Curva ROC obtenida para el clasificador formado por la red neuronal 2

Esta red neuronal clasifica mejor cuando su valor de corte está establecido en 0.1, punto donde la

sensibili dad y la especificidad son las mayores posibles.

Valor de corte

1-Especificidad Sensibili dad

0 0.1955 0.7727 0.1 0.2989 0.8636 0.2 0.3104 0.8636 0.3 0.3219 0.8636 0.4 0.3219 0.8636 0.5 0.3219 0.8636 0.6 0.3219 0.8636 0.7 0.3219 0.8636 0.8 0.3219 0.8636 0.9 0.3449 0.8636 1 1 1

Figura 12. Curva ROC obtenida para el clasificador

formado por la red neuronal 3

Esta red neuronal clasifica mejor cuando su valor de corte está establecido en 0.1, punto donde la sensibili dad y la especificidad son las mayores posibles. Como se mencionaba antes, la exactitud de la prueba aumenta a medida que la curva se desplaza desde la diagonal hacia el vértice superior izquierdo. Un clasificador ideal (100% de sensibili dad y 100% de especificidad) pasaría por dicho vértice. Un modo de comparar los clasificadores, es comparar sus curvas ROC. A simple vista se aprecia que la curva correspondiente al clasificador basado en la máquina de estados borrosa es la que más se aproxima a este vértice, por lo tanto, desde el punto de vista médico, es el método con mejores resultados de clasificación y el que más podría ayudar al diagnóstico. 5 CONCLUSIONES Este trabajo presenta un estudio preliminar de la apli cación de máquinas de estado borrosas obtenidas mediante algoritmos evolutivos en la tarea de clasificación de patrones. Uno de los resultados que se ha obtenido al comparar con otros algoritmos, tanto con datos simulados como con patrones extraídos de datos médicos, es la capacidad de generali zación superior en el caso concreto estudiado. El motivo puede ser atribuible al

mayor número de parámetros libres en la FSM elegida en las pruebas reali zadas unido a la utili zación de un método de optimización global para su síntesis, pero este extremo debe ser analizado más cuidadosamente en futuras investigaciones. Otro punto destacable y relacionado con el problema de la determinación del número de reglas para la FSM es la observación de que un número insuficiente de reglas provoca un “estancamiento” en el proceso evolutivo pudiendo ser debido no necesariamente a una incapacidad estructural de la máquina para clasificar los patrones, sino a la carencia de intrones [1] que protejan a las reglas importantes de su destrucción en el proceso evolutivo. De hecho, estos intrones se han observado en las máquinas sintetizadas al encontrarse reglas con activaciones despreciables y que, por lo tanto, no juegan un papel en el proceso de clasificación. Un análisis aparte merece también el hecho de haber tomado como constante el ancho de las funciones de pertenencia quedando fuera este factor del conjunto de parámetros de diseño. Desde el punto de vista de los sistemas borrosos que constituyen la máquina esto supone el cubrimiento regular del espacio de entradas con parches gaussianos del mismo tamaño aproximadamente. Esto simpli fica el espacio de búsqueda del algoritmo evolutivo, pero conlleva el problema de la elección adecuada del ancho prefijado para las funciones de pertenencia. Si este ancho es excesivamente grande se pierde precisión y si es excesivamente pequeño se incrementa notablemente el número de reglas necesarias para un recubrimiento correcto, lo que además va en detrimento del objetivo inicial de simpli ficar el espacio de búsqueda y hace mucho menos comprensible la base de reglas. Nuestro propósito en futuras investigaciones es combinar el método de diseño presentado con la técnica de simpli ficación de la base de reglas por recombinación de antecedentes [17], idea que se basa en producir máquinas con particiones en el espacio de entrada regulares y suficientemente finas para luego simpli ficarlas con la técnica mencionada que equivale a una reconfiguración de la partición. Nos parece reseñable la característica mencionada en el artículo acerca del umbral de corte predefinido para el parámetro extraído del estado de detección, cuyo valor coincide con el que según las curvas ROC produce una sensibili dad igual a 1 (máxima) y la mayor especificidad posible, lo que indica la adecuación de la expresión elegida para el fitness. También es importante destacar la comparativa de curvas ROC que es ventajosa para la máquina de estados borrosa frente al resto de algoritmos estudiados. El trabajo futuro debe llevarnos a una comparativa más extensa y a un análisis más profundo de los resultados obtenidos.

Agradecimientos Queremos agradecer al Dr. D. Lucio Díaz Flores y a todo su equipo del Departamento de Anatomía Patológica del Hospital Universitario de Canarias la ayuda que nos ha prestado durante el desarrollo de esta investigación. Además de cedernos bases de imágenes, nos ha asesorado en la clasificación de las distintas patologías. Sin su colaboración, este trabajo no habría sido posible. Referencias [1] Banzhaf W., Nordin P., Keller R. E., Francone F.

D., Genetic Programming, Morgan Kaufmann Publishers, Inc., 1998.

[2] Cordón O., Herrera F., Hoffmann F., Magdalena

L., Genetic Fuzzy Systems: Evolutionary Tuning and Learning of Fuzzy Knowledge Bases, World Scientific Pub Co, 2002.

[3] J.I. Estévez, L. Moreno, S. Alayón, R. Aguilar, J.

Sigut, “T wo problems in fuzzy state machine design: structure definition and rule base simplifi cation” , Proceedings IFAC’02, 2002.

[4] J. Estévez, S. Alayón, L. Moreno, R. Aguilar, J.

Sigut, Cytological Breast Fine Needle Aspirate Images Analysis with a Genetic Fuzzy Finite State Machine, Fifteenth IEEE Symposium on Computer-Based Medical Systems, Maribor, Eslovenia, 2002.

[5] P. Féli x, S. Fraga, S. Barro, “T rend detection

based on Fuzzy Temporal Profile Model” , Engineering of Intelli gent Systems, EIS’98, Vol 1, pp. 134-140, 1998.

[6] Ghahramani, Z., An introduction to Hidden

Markov Models and Bayesian Networks, International Journal of Pattern Recognition and Artificial Intelli gence, 15(1):9-42, 2001.

[7] Jang J., Sun C., Mizutani E., Neurofuzzy and Soft

Computing, Englewood Cli ffs: Prentice-Hall , 1997.

[8] W. Leow, R. Miikkulainen, “ Visor: Schema-

based scene analysis with structured neuronal networks” , Neural Processing Letters, Vol 1(2), pp. 18-23, 1994.

[9] W. Leow, “ Visor: Learning visual schemas in

neural networks for object recognition in scene analysis” , Technical Report AI94-219, 1994.

[10] Mayer G., Image Texture Analysis using Zero

Crossing Information, Tesis Doctoral,

Cytometrics Group, Center for Sensor Signal and Information Processing, Universidad de Queensland, Australia.

[11] Rabiner, L, A tutorial on Hidden Markov models

and selected applications in speech recognition, Proceedings of the IEEE, 77(2):257-286, 1989.

[12] Robertson EA, Zweig MH, Use of receiver

operating characteristic curves to evaluate the clinical perfomance of analytical systems. Clin Chem 1981; 27: 1569-1574.

[13] F. Steimann, “T he interpretation of time-varying

data with diamon-1” , Artificial Intelli gence in Medicine, Vol 8, pp.343-357, 1996.

[14] F. Steimann, K. Adlassing, “ Clinical

Monitoring with Fuzzy Automata” , Fuzzy Sets and Systems, Man and Cybernetics, Vol 3, pp. 2840-2843, 1995.

[15] Surmann, H., Maniadakis, M., Learning feed-

forward and recurrent fuzzy systems: A genetic approach, Journal of Systems Architecture, 47, 2001.

[16] Sweets JA, Pickett RM, Evaluation of diagnostic

systems: methods from signal detection theory. Nueva York, Academic Press, 1982.

[17] Yan Y., Baranyi P., Yang C. T., Reduction of

fuzzy rule base via singular value decomposition, IEEE Transactions on Fuzzy Systems, 7(2),120-132, 1994.