« Clasificación Supervi… « || Inicio || » Análisis Formal de Co… »

Mapas Auto-Organizados

Última modificación: 8 de Diciembre de 2019, y ha tenido 4030 vistas

Etiquetas utilizadas: || || ||


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 multidimensionales (vectores) en espacios de dimensión inferior, normalmente, en 2D. Este proceso de reducir la dimensionalidad de vectores es una técnica de compresión de datos conocida como Cuantización Vectorial. Además, la técnica de Kohonen crea una red que almacena información de forma que las relaciones topológicas del conjunto de entrenamiento se mantienen.

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 reconocer los 8 colores que aparecen a su derecha. En la representación 2D 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.

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, 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 aprender.
  • 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 de pesos (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\) (que es 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 vector objetivo al que aproximarse, los SOM intentan dar unos representantes de pesos en los nodos de aprendizaje de forma que se verifique un doble objetivo:

  1. Nodos de aprendizaje cercanos tienen conjuntos de pesos cercanos.
  2. Los datos de entrada tienen algún representante cercano entre los nodos de aprendizaje (en sus pesos asociados, se entiende).

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. Una vez estabilizada la red, cualquier vector nuevo estimulará 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:

SOM(D,N) [D: conjunto de entrenamiento; N: Nodos de Aprendizaje]
Para cada n N:
W(n) [0,1]^n (normalmente al azar)
r = r_0
Repetir:
Para cada v shuffle(D):
BMU(v) = argmin{n N: d(W(n),v)}
Para cada n E(BMU(v),r):
Actualiza W(n)
Actualiza r
Devolver N

La fórmula que establece el radio en función de la iteración (que hace que vaya disminuyendo, pero no linealmente, para asegurar la convergencia del algoritmo) es:

$$r(t)=r_0 e^{-\frac{t}{\lambda} }$$

donde \(r_0\) es el radio inicial (habitualmente, el radio de la red, es decir, un valor suficientemente grande como para cubrir en el primer paso todos los nodos), y \(\lambda\) una constante que permite hacer que el radio sea muy pequeño cuando llegamos a la iteración máxima:

$$\lambda= \frac{Tiempo\_de\_Entrenamiento}{\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 al vector de entrenamiento (\(V\)) usamos la modificación que sugiere la fórmula siguiente:

$$W(t+1) = W(t) + L(t) (V(t)-W(t))$$

donde el factor \(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, podemos usar una expresión similar a la del radio:

$$L(t)=L_0 e^{-\frac{t}{\lambda} }$$

El valor de \(L_0\) se ajusta experimentalmente (suele ser común usar un valor de \(0'1\)). Además, y con el fin de que el efecto de aprendizaje sea más notable en las cercanías del BMU, añadiremos un factor más al producto anterior, que hace que los nodos más cercanos al BMU se vean más afectados:

$$W(t+1) = W(t) + D(t) L(t) (V(t)-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 de información acerca de las propiedades de un conjunto de animales:

 PalomaGallinaPatoGansoBuhoHalcónÁguilaZorroPerroLoboGatoTigreLeónCaballoCebraVaca
Pequeño No No No No No No No No No
Medio No No No No No No No No No No No No
Grande No No No No No No No No No No No
2 patas No No No No No No No No No
4 patas No No No No No No No
Pelo No No No No No No No
Pezuñas No No No No No No No No No No No No No
Melena No No No No No No No No No No No No
Plumas No No No No No No No No No
Caza No No No No No No No No
Corre No No No No No No No No No No
Vuela  No No No No No No No No No No No
Nada No No No No No No No No No No No No No No
 
Usando las columnas anteriores como vectores de entrenamiento, y un tamaño adecuado del mundo para que los vectores puedan distribuirse en él con comodidad (pero no tan grande como para que no se les olbigue a reorganizarse localmente), podemos obtener una clasificación 2D de los elementos a los que caracterizan (animales), dando relaciones de similaridad (clasificándose) automáticamente:
 

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 a que los nodos aprendan los patrones internos que relacionan la diversidad de datos de entrada entre sí. Esta última característica nos la 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]$).

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) 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, todos los algoritmos de Aprendizaje Automático).

Para saber más...

Self-Organizing Maps Research Lab

World Poverty Map

Self-Organizing Maps

Self-Organizing Maps for Pictures

SOM Tutorial

« Clasificación Supervi… « || Inicio || » Análisis Formal de Co… »