Download n - bienvenidos a comunidad itam
Document related concepts
Transcript
La Combinación de Redes Neuronales y Algoritmos Genéticos Angel Kuri Instituto Tecnológico Autónomo de México Octubre de 2001 22/10/01 Redes Neuronales Una de las más populares alternativas es el perceptrón multi-capa entrenado con el algoritmo de retropropagación (BMLP). 22/10/01 Perceptrón Multi-Capa de Retropropagación (BMLP) El BMLP se basa en la regla delta generalizada: ∆w ji (n ) = α ∆w ji (n − 1) + ηδ j (n )y i (n ) que se ha usado con éxito para clasificar y predecir 22/10/01 BMLP Sin embargo, el BMLP impone varias restricciones: a) La función de activación debe ser derivable b) La derivada debe ser “fácil” 1 c) El error a minimizar es E = ∑ ( zi − oi )2 2 22/10/01 i BMLP d) La tasa de aprendizaje, momento, etc. deben determinarse a priori e) El entrenamiento no se garantiza 22/10/01 BMLP Funciones de activación típicas son: Función Derivada Lineal Logística Sigmoide 22/10/01 Redes Neuronales Genéticas (RNG) Una alternativa para superar las limitaciones mencionadas es entrenar la RNs usando un Algoritmo Genético. A las redes así entrenadas las llamamos “Redes Neuronales Genéticas”. 22/10/01 Algoritmo Básico de Programación Evolutiva t := 0 Genera P(0) Mientras t < Máximo número de Poblaciones Evalúa P(t) Selecciona µ individuos 22/10/01 Algoritmo Básico Recombina Muta t := t+1 Fin mientras 22/10/01 (continúa) Modelo Simple de AGs El llamado modelo simple de algoritmos genéticos (SGA) fue definido y estudiado por Holland y considera: l Representación genética haploide l Selección proporcional 22/10/01 Modelo Simple (continúa) Elección aleatoria l Cruzamiento lineal en locus aleatorios l Mutación con baja probabilidad l 22/10/01 Algoritmos Genéticos Sin elitismo l Con cadenas binarias l Con una población de tamaño constante l Con un número máximo de poblaciones l 22/10/01 Algoritmos Genéticos El algoritmo,entonces, parte de una colección de cadenas binarias 22/10/01 Algoritmos Genéticos Cada una de estas cadenas (correspondientes a una solución candidata) es evaluada, como se ilustra en la siguiente figura: 22/10/01 Algoritmos Genéticos 22/10/01 Algoritmos Genéticos Las cadenas son ordenadas de mejor a peor de acuerdo con su desempeño 22/10/01 Algoritmos Genéticos A cada cadena se le asigna una probabilidad de selección proporcional a su desempeño 22/10/01 Algoritmos Genéticos (...continúa Selección) Individuo Cadena 1 Cadena 2 Cadena 3 Cadena 4 Cadena 5 22/10/01 E valuac ión 5 4 3 2 1 15 P robabilidad d e S e lec c ión 33.33% 26.67% 20.00% 13.33% 6.67% 100.00% Algoritmos Genéticos De esta manera, a la larga, los individuos con mejor desempeño tienen una más alta probabilidad de ser seleccionados y sus mejores genes intervienen con más frecuencia en el pool genético de la población. 22/10/01 Algoritmos Genéticos Se elige una pareja de individuos con las probabilidades mencionadas y se genera un punto de cruzamiento de manera aleatoria, como se ilustra en la siguiente figura. 22/10/01 Algoritmos Genéticos 22/10/01 Algoritmos Genéticos Se intercambian los contenidos genéticos 22/10/01 Algoritmos Genéticos Este proceso se repite m/2 veces dando origen a m individuos que son descendientes de los m individuos originales. 22/10/01 Algoritmos Genéticos La idea “genética” es que los mejores genes se perpetúen en la población dando origen a nuevos individuos (genéticamente hablando) que se desempeñen “mejor”. 22/10/01 Algoritmos Genéticos Una vez que se tiene la nueva población, se alteran ciertos genes de manera aleatoria (se “muta”). La idea es que es necesario dotar de cierta dosis de novedad a la población. 22/10/01 Algoritmos Genéticos Sin embargo, los porcentajes de mutación son muy bajos (típicamente del orden de 0.1% a 0.5%). 22/10/01 Algoritmos Genéticos El conjunto de nuevos individuos reemplaza al conjunto anterior y el proceso se repite un cierto número de veces hasta que se alcanza un criterio de convergencia. En nuestro caso, demandamos un número de generaciones máximo. 22/10/01 Algoritmos Genéticos El resultado neto de este proceso es que el algoritmo nos entrega un conjunto de valores que resuelven la función de ajuste de manera óptima. 22/10/01 Redes Neuronales Genéticas Aquí nos preguntamos si la norma 1 E = ∑ ( zi − oi )2 2 i puede ser reemplazada por una más apropiada, cuáles son las alternativas y cómo determinar sus ventajas. 22/10/01 Algoritmo Genético Ecléctico El AG que usamos no es el algoritmo genético simple propuesto por Holland. Usamos el llamado AG Ecléctico (AGE) que incorpora: a) Elitismo total b) Selección determinística c) Cruzamiento anular 22/10/01 Algoritmo Genético Ecléctico d) Activación probabilística de un EMA e) Determinación autoadaptable de Pc (probabilidad de cruzamiento) Pm (probabilidad de mutación) N (número de descendientes) (prob. de activación del EMA) 22/10/01 ητ Elitismo Total 22/10/01 Selección Determinista 22/10/01 Cruzamiento Anular 22/10/01 Representación El genoma de la RNG se formó encadenando secuencias de bits de longitud 32. Cada cadena representa un peso en −28 −28 ( 8 2 ) ( 8 2 ) − − ≤ w ≤ + − el rango i Los pesos se inicializaron así: −0.0625 ≤ wi ≤ +0.0625 22/10/01 Representación 22/10/01 Solución La solución al problema es, por tanto, un genoma de longitud 32 × w donde w denota el número de conexiones de la red. Al ser interpretados, estos pesos y la topología de la RNG determinan la solución del problema 22/10/01 PROBLEMAS DE PRUEBA ARQUITECTURA CAPAS NEURONAS EN LA CAPA DE PRESENTACIÓN NEURONAS EN LA CAPA ESCONDIDA FUNCIÓN NEURONAS EN LA CAPA DE SALIDA FUNCIÓN CONEXIONES GENOMA CONJUNTO DE ENTRENAMIENTO CONJUNTO DE PRUEBA 22/10/01 LOGÍSTICO 3 3 PROBLEMA CLASIFICACION 3 13 PREDICCIÓN 3 12 2 5 2 SIGMOIDE 2 SIGMOIDE 3 TANH 1 SIGMOIDE 14 448 54 SIGMOIDE 88 2816 160 LINEAL 29 928 108 12 18 12 Ejemplo de Pesos BIAS * * * * 22/10/01 PESO W[1]( 1, 1) W[1]( 1, 2) W[1]( 2, 1) W[1]( 2, 2) W[1]( 3, 1) W[1]( 3, 2) W[1]( 4, 1) W[1]( 4, 2) W[2]( 1, 1) W[2]( 1, 2) W[2]( 2, 1) W[2]( 2, 2) W[2]( 3, 1) W[2]( 3, 2) VALOR -1.8574 2.9398 3.8708 -4.5245 -0.0062 0.3795 -0.2853 -1.5044 -1.5631 2.5868 7.9438 -7.7568 -7.7481 3.6868 Normas Alternativas nL 1 O(i )− Z (i ) MEE = ∑ ∑ 10 s s i =1 nL 1 MAE = ∑ ∑ O(i ) − Z (i ) s s i =1 nL 1 MSE = ∑ ∑ (O(i ) − Z (i )) 2 s s i =1 SAE = max O(i ) − Z (i ) s, i 22/10/01 Problema Logístico Rasgo 1 0.8421 0.5711 0.5605 0.8789 0.5816 0.3421 0.6947 0.3526 0.3000 0.3526 22/10/01 Rasgo 2 0.1917 0.2055 0.3202 0.2391 0.3656 0.0711 0.1008 0.0771 0.1403 0.0929 Rasgo 3 0.5722 0.4171 0.7005 0.6096 0.8075 0.4920 0.2995 0.4278 0.6257 0.6417 Vino A Vino B 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 Problema de Agrupamiento Rasgo 1 Rasgo 2 0.8421 0.5711 0.5605 0.8789 0.3421 0.6947 0.3526 0.3000 0.4868 0.4684 0.4395 0.4132 22/10/01 0.1917 0.2055 0.3202 0.2391 0.0711 0.1008 0.0771 0.1403 0.4447 0.3103 0.5553 0.3399 Rasgo3 0.5722 0.4171 0.7005 0.6096 0.4920 0.2995 0.4278 0.6257 0.5561 0.5561 0.5348 0.4492 ... ... ... ... ... ... ... ... ... ... ... ... ... Rasgo 13 0.5613 0.5506 0.6469 0.8573 0.2867 0.2511 0.1013 0.0549 0.1797 0.2011 0.2297 0.2974 Vino 1 Vino 2 Vino 3 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 Problema de Predicción t-12 t-11 t-10 t-9 t-8 t-7 t-6 t-5 t-4 t-3 t-2 t-1 Venta 0.323 0.358 0.404 0.382 0.348 0.424 0.487 0.482 0.437 0.352 0.287 0.358 0.404 0.382 0.348 0.424 0.487 0.482 0.437 0.352 0.287 0.368 0.404 0.382 0.348 0.424 0.487 0.482 0.437 0.352 0.287 0.368 0.378 0.382 0.348 0.424 0.487 0.482 0.437 0.352 0.287 0.368 0.378 0.386 0.348 0.424 0.487 0.482 0.437 0.352 0.287 0.368 0.378 0.386 0.469 0.424 0.487 0.482 0.437 0.352 0.287 0.368 0.378 0.386 0.469 0.411 0.487 0.482 0.437 0.352 0.287 0.368 0.378 0.386 0.469 0.411 0.432 0.482 0.437 0.352 0.287 0.368 0.378 0.386 0.469 0.411 0.432 0.439 0.437 0.352 0.287 0.368 0.378 0.386 0.469 0.411 0.432 0.439 0.498 0.352 0.287 0.368 0.378 0.386 0.469 0.411 0.432 0.439 0.498 0.491 0.287 0.368 0.378 0.386 0.469 0.411 0.432 0.439 0.498 0.491 0.435 0.368 0.378 0.386 0.469 0.411 0.432 0.439 0.498 0.491 0.435 0.358 0.378 0.386 0.469 0.411 0.432 0.439 0.498 0.491 0.435 0.358 0.299 22/10/01 Resultados (Clasificación) CONJUNTO DE ENTRENAMIENTO (160/54 ELEMENTOS EN EL CONJUNTO) Número de Indice de Número de Indice de Promedio Respuestas Entrenamiento Respuestas Entrenamiento Correctas en el Correctas en Problema de el Problema Agrupación Logístico Exponencial 148 92.50% 26 48.15% 70.32% Media 159 99.38% 43 79.63% 89.50% Absoluta Media 146 91.25% 51 94.44% 92.85% Cuadrática MiniMax 159 99.38% 48 88.89% 94.13% BMLP 155 96.88% 44 81.48% 89.18% 22/10/01 Resultados (Clasificación) CONJUNTO DE PRUEBA (18/12 ELEMENTOS EN EL CONJUNTO) Número de Indice de Número de Indice de Promedio Respuestas Generalización Respuestas Generalización Correctas en el Correctas en Problema el Problema Logístico Logístico Exponencial 11 61.11% 7 58.33% 59.72% Media 14 77.78% 6 50.00% 63.89% Absoluta Media 12 66.67% 8 66.67% 66.67% Cuadrática MiniMax 14 77.78% 9 75.00% 76.39% BMLP 13 72.22% 9 75.00% 73.61% 22/10/01 Resultados (Predicción) 22/10/01 PRUEBA (12 ELEMENTOS EN EL CONJUNTO) Error Promedio Exponencial 5.74% Media Absoluta 9.34% Media Cuadrática 10.04% MiniMax 9.50% BMLP 17.67% ENTRENAMIENTO (108 ELEMENTOS EN EL CONJUNTO) Error Promedio Exponencial 10.62% Media Absoluta 5.27% Media Cuadrática 5.26% MiniMax 5.68% BMLP 3.35% Resultados (Predicción) V E 22/10/01 Resultados (Predicción) 22/10/01 Resultados (Predicción) 22/10/01 Resultados (Predicción) 22/10/01 Resultados (Entrenamiento) 22/10/01 Resultados (Predicción) 22/10/01 Conclusiones è Entrenamiento de RNs con AGs l El entrenamiento genético es una alternativa viable l Se evitan los parámetros de BMLP l Con un buen AG se garantiza la convergencia 22/10/01 Conclusiones è Normas No-estándar l RNs entrenadas con normas noestándar se desempeñan tan bien como o mejor que las tradicionales l En este conjunto de experimentos la norma SAE resultó ser la más efectiva 22/10/01 Conclusiones l El entrenamiento en modo de lotes es más conveniente cuando se trabaja con RNGs 22/10/01 Conclusiones Este tipo de entrenamiento se puede aplicar a cualquier RN que implique optimización Por ejemplo, podemos optimizar: l Mapas Auto-Organizados (Redes de Kohonen) 22/10/01 Conclusiones l Máquinas de Soporte Vectorial l Máquinas de Funciones de Base Radial l Redes Auto-Organizadas Difusas 22/10/01 Evolución de Arquitecturas Una interesante forma de interacción entre RNs y AGs es la de evolucionar las redes (y no los pesos, como en el primer caso discutido). Yao y Liu han propuesto un algoritmo basado en programación evolutiva y no en AGs, mismo que consideramos de interés y comentamos a continuación. 22/10/01 EPNet Genérese una población de M redes al azar. El número de nodos escondidos y la densidad de conexiones inicial se generan uniformemente al azar dentro de ciertos rangos. Los pesos iniciales aleatorios se generan dentro de un rango restringido. Se entrena cada una de las RNs parcialmente durante un cierto número de épocas K0 usando un RP modificado (MRP) con tasas de aprendizaje adaptables. 22/10/01 EPNet El número de épocas K0 es especificado por el usuario. El error E de cada RN se checa después del entrenamiento parcial. Si E no se ha reducido significativamente, se asume que la RN ha sido atrapada en un óptimo local y la RN se marca como “fracaso” (f ); de otra forma se marca como “éxito” (x). 3. Se ordenan las RNs de acuerdo con sus errores de mejor a peor. 22/10/01 EPNet 4. Si la mejor RN es aceptable o se ha llegado al máximo número de generaciones, ir al paso 11. 5. Usar selección basada en rango para seleccionar una RN padre de la población. Si es de tipo x ir al paso 6; si no, ir al paso 7. 6. M1. Entrenar parcialmente la RN padre durante K1 épocas usando MRP para obtener una RN hija y marcarla como en el paso 2, en donde K1 es un parámetro del usuario. 22/10/01 EPNet Reemplazar la RN padre por la RN hija en la población actual e ir al paso 3. 7. M2. Entrenar la RN padre usando un AG para obtener una RN hija. Si el AG reduce el error E de la RN padre significativamente, marcar la RN hija con x, reemplace la RN padre con la hija e ir al paso 3. De otra forma, descartar esta RN e ir al paso 8. 8. M3. Decidir el número de nodos escondidos NE que van a eliminarse generando un número aleatorio entre 1 y un máximo del usuario. NE es, normalmente, muy pequeño: no mayor de 3. 22/10/01 EPNet Borrar ahora NE nodos de la red padre uniformemente al azar. Entrenar parcialmente la RN podada con MRP para obtener una RN hija. Si esta RN es mejor que la peor en la población, reemplazar la peor con la hija e ir al paso 3; o descartar a la RN hija e ir al paso 9. 9. M4. Calcular la importancia relativa de cada conexión en la RN padre usando el método noconvergente. Decidir el número de conexiones a quitar de la misma forma como se hizo en el paso 8. 22/10/01 EPNet Aleatoriamente eliminar las conexiones de la RN padre de acuerdo con la importancia calculada. Parcialmente entrenar la red podada con MRP para obtener una hija. Si esta RN es mejor que la peor RN en la población, reemplazar e ir al paso 3; o descartar esta RN e ir al paso 10. 10. M5. Decidir el número de conexiones que deben ser agregadas igual que en el paso 8. Calcular la importancia relativa de cada conexión virtual con peso =0. 22/10/01 EPNet Aleatoriamente agregar las conexiones a la RN padre para obtener el descendiente 1 (D1) de acuerdo con su importancia. La agregación de nodos se implementa dividiendo un nodo elegido aleatoriamente en la RN padre. La nueva RN crecida es el descendiente 2 (D2). Parcialmente entrenar a D1 y a D2 con MRP para obtener un descendiente sobreviviente (DS). Reemplazar la peor red en la población con DS e ir al paso 3. 22/10/01 EPNet 11. Después del proceso evolutivo, terminar el entrenamiento de la mejor red hasta que converja con los conjuntos de entrenamiento y prueba. 22/10/01 Eliminación de Conexiones y el Método no Convergente Ciertas conexiones se eliminan probabilísticamente de acuerdo con su importancia. El número máximo de conexiones que se pueden eliminar se determina con un parámetro de usuario. La importancia se define con una prueba de significación para la desviación del peso en el proceso de actualización de los mismos. 22/10/01 Eliminación de Conexiones y el Método no Convergente Denotamos la actualización ∆wij = −η [δLt / δwij ] por el gradiente local de la función lineal de error L con respecto a la muestra t y el peso T n wij, en donde L = ∑∑ Yi (t ) − Z i (t ) t =1 i =1 La significación de la desviación de wij de cero se define por la variable de prueba: 22/10/01 Eliminación de Conexiones y el Método no Convergente T test ( wij ) = ∑ξ t =1 T ∑ (ξ i =1 t ij t ij − ξi j ) 2 t t ξ = w − ∆ w en donde ij ij ij y ξ ij denota el promedio sobre ξ ijt ; t=1,...,T 22/10/01 Eliminación de Conexiones y el Método no Convergente Un valor más alto de test(wij ) indica una mayor importancia de la conexión con peso wij. La ventaja de este método es que no requiere de que el método converja para probar las conexiones. 22/10/01 Evolución de Arquitecturas EPNet ha sido aplicado en varios problemas prácticos con éxito. En general, puede encontrar RNs quasióptimas; puede agregar y podar RNs dinámicamente dependiendo de si la RN es mayor o menor de los necesario. Además, el ordenamiento de las cinco mutaciones ha resultado en RNs muy compactas debido al sesgo hacia la eliminación de conexiones y nodos. 22/10/01 Evolución de Arquitecturas Las conexiones se modifican más frecuentemente que los nodos porque las mutaciones a las conexiones causan menor alteración que las mutaciones a los nodos. El algoritmo puede producir redes con buena capacidad de generalización. 22/10/01 Redes Neuronales de Kohonen Las Redes de Kohonen, también llamadas Mapas Auto-Organizados o SOMs (por sus siglas en inglés) son sistemas de clasificación no supervisada que permiten encontrar individuos de una población que comparten características comunes. Esto los hace ideales para explorar espacios vectoriales en los que se desconoce la estructura de clasificación de los vectores. 22/10/01 Redes de Kohonen En esta ilustración se muestra un SOM de dos dimensiones. Las neuronas se representan... 22/10/01 Redes de Kohonen ...en el mapa bidimensional, mientras que los vectores de datos (representados por Xi) están en la parte inferior. Cada neurona “apunta” a los vectores, de manera que cada neurona tiene tantas coordenadas como rasgos hay en un vector. 22/10/01 Redes de Kohonen Supongamos, por ejemplo, que cada vector de datos tiene 13 rasgos y que el mapa tiene una estructura de 4 X 4. La neurona (1,1) tiene 13 coordenadas: 22/10/01 Redes de Kohonen Por otra parte, la neurona 16 (4,4) tiene las siguientes 13 coordenadas: 22/10/01 Redes de Kohonen Nuestro problema consiste en encontrar los valores de las coordenadas de c/u de las neuronas del mapa de manera que, en el espacio bidimensional de las neuronas, las neuronas vecinas apunten a aquellos datos que forman parte del mismo grupo. Por ejemplo, en el caso anterior, cada dato es una muestra de las componentes químicas de alguno de tres medicamentos. 22/10/01 Mapas Auto-Organizados En el mapa que se muestra, cada color identifica una de las tres medicinas; y cada círculo corresponde a una neurona. Como puede verse, las neuronas correspondientes a cada tipo de medicina son vecinas entre si. 22/10/01 Mapas Auto-Organizados Así, lo que pedimos de este tipo de redes, es un mapa del espacio multidimensional (en el ejemplo, de 13 dimensiones) al espacio bi-dimensional de tal manera que haya una cercanía geográfica entre las neuronas que mapean a miembros del mismo grupo. ¿Cómo logramos eso? Kohonen propuso el siguiente algoritmo: 22/10/01 Algoritmo de Kohonen 1. Todas las coordenadas de las neuronas reciben, inicialmente, valores aleatorios. 2. Se inicializa un contador de épocas n ← 1 3. Se define la tasa de aprendizaje α (n) para la época n. (Una época es la presentación de todas las muestras). 4. Se define la función de retroalimentación rik(n) de la neurona i a la neurona ganadora k en la época 2 n, dada por: d rik (n) = exp(− 22/10/01 ik σ ( n) 2 ) Algoritmo de Kohonen en donde σ (n) es el radio de aprendizaje para la época n y d es la distancia (euclidiana) entre la iésima neurona y la k-ésima neurona (o neurona ganadora, como se define más adelante). 5. Se define el factor de aprendizaje fα . Este tiene un valor cercano a 1 (por ejemplo 0.99) 6. Se define el factor radial fσ . Este tiene, asimismo, un valor cercano a 1 (p.e. 0.995). 7. Se presenta la muestra x(t) de entrenamiento a la red. 22/10/01 Algoritmo de Kohonen 8. Se determina cuál de las neuronas está más cerca de la muestra. Normalmente se calcula la distancia euclidiana entre el vector de pesos de las neuronas y el vector de entrenamiento. A esta neurona (la késima) se le denomina la neurona ganadora. 9. Los vectores de peso de c/u de las neuronas perdedoras se modifican de acuerdo con: wij (t + 1) = wij (t ) + α (n) ⋅ rik (n) ⋅ ( x (t ) − wij (t )) 10. Se ha cumplido una época? Si: Se actualizan los los parámetros de aprendizaje, de acuerdo con: 22/10/01 Algoritmo de Kohonen α (n + 1) = α (n) ⋅ fα σ (n + 1) = σ (n) ⋅ fσ 11. Se cumple algún criterio de convergencia? Si: Fin No: Ir al paso 7 22/10/01 Algoritmo de Kohonen Debe notarse que la transformación del espacio M-dimensional (de los M rasgos o elementos del vector de c/u de las muestras) al espacio bidimensional de las N neuronas se produce al encontrar la distancia d ik 2 rik (n) = exp(− ) 2 σ ( n) puesto que d ik = i − k = (i x − k x ) + (i y − k y ) 2 22/10/01 2 Algoritmo de Kohonen La distancia entre dos neuronas vecinas es, convencionalmente, igual a 1, como se ilustra. 22/10/01 Algoritmo de Kohonen Nótese que la expresión de rik es similar a la de una distribución normal, centrada en dik y con una desviación ó(n) como se ilustra. 22/10/01 Algoritmo de Kohonen Lo anterior implica que el ajuste al peso wik está en función de la diferencia que existe entre la neurona ganadora y la i-ésima ponderada por la desviación estándar para esta época. Como en cada época σ (n + 1) = σ (n) ⋅ fσ la influencia de la neurona ganadora en sus vecinas se reduce exponencialmente con el número de época (n). 22/10/01 Algoritmo de Kohonen σ (1) = fσ ⋅ σ (0) = fσ ⋅ σ 0 σ (2) = fσ ⋅ σ (1) = fσ ⋅ ( fσ ⋅ σ 0 ) = 2 fσ (σ 0 ) y, en general : σ ( n) = 22/10/01 n fσ ⋅σ 0 Algoritmo de Kohonen Análogamente: α (1) = fα ⋅ α (0) = fα ⋅ α 0 α (2) = fα ⋅ α (1) = fα ⋅ ( fα ⋅ α 0 ) = 2 fα (α 0 ) y, en general : α (n) = fαn ⋅ α 0 22/10/01 Algoritmo de Kohonen Este algoritmo garantiza que neuronas que apuntan a datos similares sean vecinas en el mapa de la red, pero no resuelve el problema de cómo están sectorizadas (a qué grupo pertenecen) las neuronas individuales. En otras palabras, empezamos con un mapa de neuronas disociadas de los vectores de datos y las asociamos en las coordenadas del mapa. Pero falta “pintar” los grupos. 22/10/01 Agrupamiento Dado: 22/10/01 Obtener: Agrupamiento (Labeling) Al problema de encontrar los grupos a los que pertenecen las neuronas se le llama “etiquetamiento” (labeling) de las neuronas. Este proceso se puede automatizar de manera sencilla si se conocen, a priori, los grupos a los que pertenecen los datos de entrenamiento. 22/10/01 Algoritmo de Agrupamiento Dadas N clases y un conjunto de objetos Oi (muestras) cada uno de los cuales pertenece a las clase C (i ) ∈ {1,..., N } se define una matriz P de N X M elementos, en donde M es el número de neuronas de la red. Los elementos de P se inicializan a 0. Entonces se puede aplicar el siguiente procedimiento. 22/10/01 Algoritmo de Agrupamiento 1. Preséntese el objeto Oi de la clase C(i) a la red y calcúlese la distancia Oi − w j de todas las neuronas a este objeto. 1 2. Hágase P =P + ∀j C ( i ), j C ( i ), j Oi − w j 3. Repetir los pasos 1-2 hasta que todos los objetos hayan sido presentados a la red. 4. Calcular I m = max {Pn,m } para m = 1,..., M 22/10/01 n =1,..., N Algoritmo de Agrupamiento 5. Asigne la etiqueta de clase Im a la neurona m. Puede ser que no haya un máximo único ni está garantizado que haya al menos una neurona asignada a cada clase. En estos casos es necesario aplicar algún heurístico para desambiguar el sistema. Adicionalmente, se requieren, al menos, tantos objetos como neuronas haya en la red. 22/10/01 Matriz de Distancia 22/10/01 Agrupamiento Automático Cuando se desconocen los grupos a los que pertenecen las neuronas, el problema es considerablemente más complejo. Debemos de determinar, en este caso, en dónde están los límites de las vecindades entre las neuronas del mapa. 22/10/01 El Problema de las Particiones ¿Es este el número correcto de particiones? ¿Son adecuadas estas particiones? 22/10/01 Métrica de Clases Para establecer un sistema que determine, dado un número de clases, a qué clase pertenece cada una de las muestras, propusimos 4 métricas: a) Distancia absoluta b) Distancia absoluta agrupada c) Distancia euclidiana d) Distancia euclidiana agrupada 22/10/01 Métrica de Clases Distancia Absoluta: N C ∑∑ max(dist )+ dist i =1 j =1 22/10/01 j =1,...,C j k k =1,...,C k≠ j Métrica de Clases Distancia Absoluta Agrupada: 1 C ( j) 22/10/01 N C ∑∑ max(dist i =1 j =1 C ( j ) ) + dist k k =1,...,C j =1,...,C k≠ j Métrica de Clases Distancia Euclidiana: N C ∑ ∑ i =1 22/10/01 j =1 (max(dist j )− dist k ) j =1,...,C 2 k =1,...,C k≠ j Métrica de Clases Distancia Euclidiana Agrupada: 1 C ( j) 22/10/01 N C ∑ ∑ (max(dist i =1 j =1 C ( j ) ) − dist k ) k =1,...,C j =1,...,C k≠ j 2 Resultados Numéricos En la figura se muestran los valores obtenidos de muestrear valores aleatoriamente para los 4 tipos de métrica. 22/10/01 Resultados Numéricos Lo que se observa es el resultado de medir las distancias entre los grupos cuando los grupos son los conocidos (1a fila) y cuando la agrupación se hace aleatoriamente. Lo que buscamos es la métrica que nos entregue el menor valor posible para una agrupación aleatoria, de manera que tratemos de encontrar la agrupación que minimice ese valor. 22/10/01 Una Medida de Agrupamiento El razonamiento anterior se deriva del hecho de que una asignación aleatoria debe arrojar distancias menores que aquellas obtenidas del caso “real”. Si logramos una métrica que tenga el comportamiento deseado, nuestro problema se convierte en uno de minimización de los valores derivados de agrupar las muestras según la métrica más adecuada. 22/10/01 Simulaciones En la siguiente figura se muestra una tabla con los resultados de aplicar las distintas métricas a 5 grupos de 10, 15 y 20 muestras cada uno. En las 1as 4 columnas se muestra la desviación. En las últimas 4 se muestra el número de veces que la métrica equivocó su diagnóstico. 22/10/01 Simulaciones 22/10/01 Métricas Robustas De la tabla se puede ver que, en principio, las métricas 1 y 3 inducen errores. Por otra parte las métricas 2 y 4 no se “equivocan”. De estas, la mejor es la #4 cuya desviación es, consistentemente, menor que el el caso de la #2. Es decir, la métrica euclidiana agrupada se desempeña mejor. 22/10/01 Elección de los Elementos del Grupo Una vez convencidos que la métrica mejor es 1 C ( j) N C ∑ ∑ i =1 j =1 (max(dist C ( j ) )− dist k ) 2 j =1,...,C k =1,...,C k≠ j debemos encontrar un método para encontrar la agrupación que minimice esta distancia. 22/10/01 El Problema de Minimización Este problema es no trivial. Supongamos que tenemos 160 muestras y 3 clases. ¿Cuántas formas de agrupar estas 160 muestras en 3 clases existen? El número es O(2320) que es, aproximadamente, O(1096). Obviamente una búsqueda exhaustiva es inaplicable. Pero para un AG la solución de este problema es trivial. 22/10/01 Genoma Para resolver el problema de optimización debemos de construir un genoma (binario) que nos permita representar la solución. Una posible forma de proponiendo una cadena de números (un número por muestra) tal que cada número indique a qué grupo corresponde una muestra. 22/10/01 Genoma Siguiendo con el ejemplo anterior, donde hay 160 muestras y 3 categorías, el genoma se compone de 160 números entre 1 y 3. Por ejemplo: 1232323231112323...123123 160 números 22/10/01 Genoma Nosotros decidimos codificar en binario, de manera que un individuo está representado por 160 X 2 bits; es decir, asociando parejas de bits representamos un número entre 0 y 2 (y no usamos la combinación “11”). El genoma es de 320 bits y, por lo tanto, hay del orden de 2320 posibles combinaciones de individuos. 22/10/01 Solución al Problema 22/10/01 Solución al Problema En la gráfica anterior se muestra el comportamiento de los métodos de Las líneas inferiores corresponden a las mejores métricas. 22/10/01 Conclusiones Estableciendo una métrica adecuada es posible convertir el problema de determinación de grupos en problemas de clasificación a uno de minimización. El problema de minimización se puede resolver fácil y eficientemente usando AGs. Para determinar el número de grupos se requiere ir aplicando el AG consecutivamente para 2, 3, ..., N grupos. 22/10/01 Conclusiones Los resultados obtenidos hasta el momento son alentadores pero no definitivos ya que el criterio de elección de la métrica más adecuada no asegura que los grupos encontrados sean los óptimos. En el futuro inmediato buscaremos un modelo matemático del comportamiento de la métrica para garantizar sus adecuadas propiedades matemáticas en todos los casos. 22/10/01