Mapas Auto-Organizados
Los Self Organizing Maps (Mapas Auto-Organizados), o SOM, fueron inventados en 1982 por Teuvo Kohonen, profesor de la Academia de Finlandia, y proporcionan una forma de representar datos numéricos multidimensionales (vectores de toda la vida) en espacios vectoriales de dimensión inferior, normalmente, en 2D/3D. Este proceso de reducir la dimensionalidad de vectores es una técnica de compresión de datos conocida como Cuantización Vectorial. Además, el algoritmo de Kohonen usa una red que intenta almacenar la información topológica del conjunto de entrenamiento.
Un ejemplo habitual que se usa para mostrar cómo funcionan los SOM se basa en la proyección de colores (asociados a vectores 3D formados a partir de, por ejemplo, sus 3 componentes RGB) en un espacio 2D. La siguiente figura muestra un SOM entrenado para comprimir los 8 colores que aparecen a su derecha. La compresión hemos de verla como la posición que ocupan en la representación 2D, donde se puede observar cómo el proceso de construcción termina agrupando colores similares (similares respecto a los vectores 3D que los representan) en regiones adyacentes (se debe tener en cuenta que aquí usamos un nivel de representación intermedio, el color se representa por medio de un vector, que es todo lo que "ve" un SOM).
Uno de los aspectos más interesantes de los SOM es que aprenden a clasificar sin supervisión, lo que implica que no necesitamos un objetivo que aproximar, sino que genera la distribución a partir de la similitud entre los vectores. Proporcionan, por tanto, un método de Aprendizaje No Supervisado.
A continuación veremos los dos elementos fundamentales que intervienen en el algoritmo SOM ideado por Kohonen. Comenzaremos viendo la arquitectura de red que se usa como soporte topológico donde se comprimirá la información original, y posteriormente veremos cómo se usa esta red para el proceso de proyección.
Arquitectura en red
En general, el algoritmo SOM considera una arquitectura en 2 capas:
- Por una parte tenemos una capa de nodos de aprendizaje, de la que nos importa la relación topológica que hay entre ellos (es decir, las conexiones y estructura que forman), y que serán los que finalmente contendrán la información acerca de la representación resultante. Contendrán las representaciones cuantizadas asociadas a los datos que queremos proyectar.
- Por otra parte, una capa de nodos de entrada, que servirán de alimentadores de los nodos de aprendizaje por medio de los vectores originales (datos) durante el proceso de entrenamiento.
- Además, todos los elementos de la primera capa están conectados con todos los elementos de la segunda capa. Estas conexiones tienen un "peso" que puede modificarse para que los nodos de aprendizaje "aprendan" la información de los nodos de entrada. Estos pesos son los parámetros modificables del modelo.
La siguiente figura muestra una posible arquitectura 2D para un entrenamiento SOM, la red de aprendizaje viene representada por los nodos rojos, y los vectores de entrenamiento vienen representados en verde. Como en muchos sistemas similares (por ejemplo, las redes neuronales, que son modelos muy cercanos), la idea del algoritmo consistirá en encontrar los pesos adecuados de las conexiones entre ambas capaz para dar una "representación adecuada" de los datos de entrada en la estructura geométrica de los nodos de aprendizaje.
En realidad, como no nos importa la representación geométrica ni topológica de los nodos de entrada, es común que solo se de una representación en la que aperecen los nodos de aprendizaje, y los pesos asociados a cada uno de ellos se muestran como un vector $n$-dimensional (cada elemento de este vector es el peso de la conexión con el correspondiente nodo de entrada). De esta forma, si la capa de entrada tiene tamaño \(n\) (la dimensión del espacio original, es decir, cada dato original viene representado por un vector de esa dimensión), cada nodo de aprendizaje tendrá asociado un vector de pesos, \(W\), de dimensión \(n\), aquel que viene determinado por los valores de los pesos de sus conexiones con los nodos de entrada.
Algoritmo de Aprendizaje
A grandes rasgos, ya que no hay función objetivo que aproximar, los SOM intentan dar unos representantes de pesos en los nodos de aprendizaje de forma que se verifique un doble objetivo:
- Nodos de aprendizaje cercanos tienen vectores de pesos cercanos.
- Cada dato de entrada tiene algún representante cercano entre los nodos de aprendizaje (en el sentido de que hay algún nodo de aprendizaje cuyo vector de pesos se parece al dato de entrada).
Para ello, el método que siguen los SOM es que, en aquellas zonas en las que la red tiene nodos con pesos que coinciden con vectores de entrenamiento, el resto de nodos de su entorno tienden a aproximarse también a ese mismo vector. De esta forma, partiendo de una distribución de pesos inicial (normalmente aleatorios), el SOM tiende a aproximarse a una distribución de pesos estable. Tras la estabilización (convergencia del algoritmo), cada una de estos nodos de aprendizaje (y los nodos cercanos a él) agrupa los datos originales que más se le parecen, de forma que la red completa se convierte en una herramienta de clasificación topológica. Una vez estabilizada la red, cualquier dato de entrada nuevo se podrá asociar a la zona de la red que tiene pesos más similares.
De forma más detallada, los pasos, a grandes rasgos, que se siguen para el proceso de entrenamiento son (para facilitar el algoritmo, se considerará que los datos del conjunto de entrenamiento han sido normalizados en $[0,1]^n$):
SOM(D,NA) [D: conjunto de entrenamiento; NA: Nodos de Aprendizaje]
Para cada nod ∈ NA:
W(nod) ∈ [0,1]^n (normalmente al azar)
r = r_0
Repetir T veces:
Para cada v ∈ shuffle(D):
BMU(v) = argmin{nod ∈ NA: d(W(nod),v)}
Para cada nod ∈ E(BMU(v),r):
Actualiza W(nod)
Actualiza r
Devolver NA
Es decir, en cada paso, para cada vector de aprendizaje, $v$, se selecciona el nodo que almacena el peso que más se le parece (es lo que se llama el BMU, Best Matching Unit), y se aproximan a $v$ un poco todos los nodos que rodean al BMU.
La actualización del radio en función de la iteración (que hace que vaya disminuyendo, pero no linealmente, para asegurar la convergencia del algoritmo) es ($t$ es la iteración):
$$r(t)=r_0 e^{-\frac{t}{\lambda} }$$
donde \(r_0\) es el radio inicial (habitualmente un valor suficientemente grande como para cubrir en el primer paso todos los nodos), y \(\lambda\) es una constante que permite hacer que el radio sea muy pequeño cuando llegamos a la iteración máxima, es decir:
$$\lambda= \frac{T}{\ln r_0}$$
La siguiente figura muestra el efecto de ir reduciendo paulatinamente el radio del entorno, donde se marcan los nodos que se verían afectados si el nodo BMU es el nodo amarillo:
Para aproximar los pesos (\(W\)) de los nodos del entorno del BMU hacia el vector de entrenamiento ($v$) podemos usar una simple aproximación algebraica como:
$$W(t+1) = W(t) + L(t) (v-W(t))$$
donde \(L(t)\) se denomina tasa de aprendizaje, y permite aproximar $W$ a $v$ con el paso del tiempo. Como normalmente querremos que su valor también disminuya a medida que el tiempo pasa (para que a medida que pasa el tiempo el aprendizaje disminuya), podemos usar una expresión similar a la del radio:
$$L(t)=L_0 e^{-\frac{t}{\lambda} }$$
done el valor de \(L_0\) se ajusta experimentalmente (suele ser común usar un valor de \(L_0=0'1\)).
Además, y con el fin de que el efecto de aprendizaje sea más pronunciado en las cercanías del BMU, podemos añadir un factor más al producto anterior para que los nodos más cercanos al BMU se vean más afectados:
$$W(t+1) = W(t) + D(t) L(t) (v-W(t))$$
Por ejemplo, haciendo que \(D(t)\) siga una gaussiana de la forma:
$$D(t)=e^{-\frac{d^2}{2r^2(t)} }$$
donde \(d\) es la distancia del nodo que estamos ajustando al BMU (centro del entorno).
Ejemplo de Aplicación
Los SOM se usan habitualente para proporcionar un procedimiento topológico de reducción de la dimensionalidad a la vez que un procedimiento de clustering, ya que permiten mostrar relaciones entre grandes cantidades de datos y que precisarían muchas más dimensiones para ser mostradas adecuadamente (muy por encima de las 3 a las que solemos estar acostumbrados). Con el fin de trabajar con una topología en los nodos que refleje un mayor número de conexiones entre ellos, pero sea realista desde un punto de vista 2D, es habitual trabajar con un teselado hexagonal del plano, identificando los hexágonos con los nodos de la red.
Mostremos un par de ejemplos que puedan dar una idea de cómo usar SOM como algoritmo no supervisado:
Paises organizados según su nivel de pobreza
Según los diversos factores que se usan para medir la calidad de vida de los países, podemos usar SOM para representar las agrupaciones que forman los diversos países en una red 2D.
Junto a la representacion anterior, una vez extraídos los colores, podemos volver a proyectar los países en un mapa estándar, de forma que visualmente podamos interpretar simultáneamente la información geográfica con la proporcionada por SOM:
En general, los SOM se pueden usar para representar datos complejos de una forma muy visual, ya que las relaciones abstractas se destacan como relaciones de carcanía y por colores... desde relaciones semánticas hasta estructuras topológicas.
Clasificación de animales
Supongamos ahora que tenemos la siguiente tabla con propiedades de un conjunto de animales:
| Paloma | Gallina | Pato | Ganso | Buho | Halcón | Águila | Zorro | Perro | Lobo | Gato | Tigre | León | Caballo | Cebra | Vaca | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Pequeño | Sí | Sí | Sí | Sí | Sí | Sí | No | No | No | No | Sí | No | No | No | No | No |
| Medio | No | No | No | No | No | No | Sí | Sí | Sí | Sí | No | No | No | No | No | No |
| Grande | No | No | No | No | No | No | No | No | No | No | No | Sí | Sí | Sí | Sí | Sí |
| 2 patas | Sí | Sí | Sí | Sí | Sí | Sí | Sí | No | No | No | No | No | No | No | No | No |
| 4 patas | No | No | No | No | No | No | No | Sí | Sí | Sí | Sí | Sí | Sí | Sí | Sí | Sí |
| Pelo | No | No | No | No | No | No | No | Sí | Sí | Sí | Sí | Sí | Sí | Sí | Sí | Sí |
| Pezuñas | No | No | No | No | No | No | No | No | No | No | No | No | No | Sí | Sí | Sí |
| Melena | No | No | No | No | No | No | No | No | No | Sí | No | No | Sí | Sí | Sí | No |
| Plumas | Sí | Sí | Sí | Sí | Sí | Sí | Sí | No | No | No | No | No | No | No | No | No |
| Caza | No | No | No | No | Sí | Sí | Sí | Sí | No | Sí | Sí | Sí | Sí | No | No | No |
| Corre | No | No | No | No | No | No | No | No | Sí | Sí | No | Sí | Sí | Sí | Sí | No |
| Vuela | Sí | No | No | Sí | Sí | Sí | Sí | No | No | No | No | No | No | No | No | No |
| Nada | No | No | Sí | Sí | No | No | No | No | No | No | No | No | No | No | No | No |
Al igual que en el caso anterior, se normalizan las componentes de los vectores (ya están normalizados, convirtiendo No = 0, Sí = 1) y se generan pesos al azar con componentes aleatorias entre 0 y 1. En este caso, debido a que cada vector tiene 13 componentes, usamos sólo las 3 primeras para dar una ligera clasificación por colores, pero no reflejan la información adicional que hay en los pesos reales que se usan en el algoritmo.
Puede observarse que la clasificación tiene sentido, ya que agrupa de forma coherente animales que consideramos similares por causas diversas.
En ambos casos se debe elegir el tamaño del mundo de representación (es decir, el número y distribución de nodos de entrenamiento) teniendo en cuenta que debe ser lo suficientemente grande como para poder representar las diferencias existentes en el conjunto original pero, a la vez, debe ser lo suficientemente pequeño como para obligar que los nodos aprendan los patrones internos que relacionan la diversidad de datos de entrada entre sí teniendo en cuenta las propiedades de los vectores cercanos.
Este hecho nos lo vamos a encontrar muchas veces:
El espacio de representación debe tener un tamaño adecuadamente pequeño para que el proceso de estrés informativo que se produce en el entrenamiento fuerce el aprendizaje de patrones inherentes a la estructura de datos originales.
Preprocesado de Datos
Rara vez los conjuntos de datos sirven tal como nos los dan, ya que es habitual encontrar que vienen dados en escalas muy diferentes, con altos grados de variabilidad (y diferente para cada atributo almacenado), e incluso con distintos tipos de datos, donde algunos son numéricos y otros categóricos. Por eso, normalmente, y antes de realizar el entrenamiento, hay que realizar algún tipo de preprocesamiento que tiene como objetivo conseguir que todas las variables tengan aproximadamente el mismo rango y la misma desviación estándar.
Una de las formas (quizás la más simple) para conseguir este objetivo es la siguiente:
- Convertir variables categóricas que tengan \(n\) posibles valores (categorías) en \(n\) variables distintas. Los valores de estas variables dependerán de cómo hayamos preprocesado el resto del fichero, pero normalmente se pondrá al valor máximo de la normalización ($1$) en caso de que la variable corresponda a esa categoría y al valor mínimo en caso de que no ($0$ o $-1$).
- Normalizar las columnas numéricas restando la media y dividiento por la desviación estándar. Así todas las variables tendrán la mayor parte de sus valores en $[-1,1]$ (a veces también se proyectan sobre $[0,1]$ por medio de un escalado lineal).
Otros preprocesos posibles consisten en aplicar logaritmos en caso de que el rango de variación pase por varios órdenes de magnitud, o restar el mínimo y dividir por el rango de variación, para dar diferentes variables en el rango $[0,1]$. Aún así, cuando se trata de variables con distribución muy desigual, es habitual que los modelos obtenidos no sean excesivamente buenos, y habría que someterlos a algún preprocesamiento adicional, que será totalmente heurístico (es decir, hecho ad hoc), y que puede incluir la eliminación de algunas de las variables, algún proceso estadístico adicional sobre el conjunto resultante y ejecuciones preliminares del algoritmo para comprobar la calidad de los resultados que se consiguen.
En cualquier caso, lo más importante del preprocesado es no desvirtuar las relaciones métricas entre los diferentes valores de los atributos, ya que un mal preprocesado puede dar lugar a artefactos (es decir, características no presentes en los datos iniciales, sino que reflejan características incluidas durante el preprocesamiento) en los resultados del algoritmo. Por ejemplo, si las categorías de una variable categórica son totalmente diferentes, el vector que represente cada categoría tendrá que hacerse de forma que la distancia a todas las demás sea la misma. Sin embargo, con variables que tengan una distancia "natural", por ejemplo, con valores del tipo mediano, pequeño, grande, habrá que convertirlas a números enteros, o a valores numéricos que mantengan esa misma relación de proximidad entre ellas.
Es importante destacar que este tipo de preprocesamientos no son exclusivos de este modelo SOM, sino comunes a cualquier tipo de aproximación de modelado de datos (por ejemplo, a todos los algoritmos de Aprendizaje Automático).
Para saber más...
Self-Organizing Maps Research Lab