Free Press

Una tarea que implique aprendizaje automático puede no ser lineal, pero tiene una serie de pasos bien conocidos:

• Definición del problema.
• Preparación de los datos.
• Aprender un modelo subyacente.
• Mejorar el modelo subyacente mediante evaluaciones cuantitativas y cualitativas.
• Presentar el modelo.

Una buena manera de llegar a un nuevo problema es trabajar identificando y definiendo el problema de la mejor manera posible y aprender un modelo que capture información significativa de los datos. Aunque los problemas en el reconocimiento de patrones y el aprendizaje automático pueden ser de varios tipos, se pueden clasificar a grandes rasgos en tres categorías:

• Aprendizaje supervisado:
  El sistema se presenta con entradas de ejemplo y sus salidas deseadas, dadas por un «maestro», y el objetivo es aprender una regla general que mapea las entradas a las salidas.
• Aprendizaje no supervisado:
  No se dan etiquetas al algoritmo de aprendizaje, dejándolo por su cuenta para encontrar la estructura en su entrada. El aprendizaje no supervisado puede ser un objetivo en sí mismo (descubrir patrones ocultos en los datos) o un medio para alcanzar un fin (aprendizaje de características).
• Aprendizaje por refuerzo:
  Un sistema interactúa con un entorno dinámico en el que debe realizar un determinado objetivo (como conducir un vehículo o jugar a un juego contra un oponente). El sistema recibe retroalimentación en términos de recompensas y castigos a medida que navega por su espacio de problemas.

Entre el aprendizaje supervisado y el no supervisado se encuentra el aprendizaje semisupervisado, en el que el profesor da una señal de entrenamiento incompleta: un conjunto de entrenamiento en el que faltan algunas (a menudo muchas) de las salidas objetivo. En esta entrada del blog nos centraremos en el aprendizaje no supervisado y la agrupación de datos.

Aprendizaje no supervisado

En algunos problemas de reconocimiento de patrones, los datos de entrenamiento consisten en un conjunto de vectores de entrada x sin ningún valor objetivo correspondiente. El objetivo en estos problemas de aprendizaje no supervisado puede ser descubrir grupos de ejemplos similares dentro de los datos, lo que se denomina clustering, o determinar cómo se distribuyen los datos en el espacio, lo que se conoce como estimación de la densidad. Para decirlo en términos más sencillos, para un espacio de n muestras x1 a xn, no se proporcionan las verdaderas etiquetas de clase para cada muestra, de ahí que se conozca como aprendizaje sin profesor.

Cuestiones con el aprendizaje no supervisado:

• El aprendizaje no supervisado es más difícil en comparación con las tareas de aprendizaje supervisado..
• ¿Cómo sabemos si los resultados son significativos ya que no hay etiquetas de respuesta disponibles?
• Dejar que el experto mire los resultados (evaluación externa)
• Definir una función objetivo sobre la agrupación (evaluación interna)

¿Por qué es necesario el Aprendizaje No Supervisado a pesar de estos problemas?

• Anotar grandes conjuntos de datos es muy costoso y, por tanto, sólo podemos etiquetar unos pocos ejemplos manualmente. Ejemplo: Reconocimiento del habla
• Puede haber casos en los que no sepamos en cuántas/qué clases están divididos los datos. Ejemplo: Minería de datos
• Puede que queramos utilizar el clustering para conocer la estructura de los datos antes de diseñar un clasificador.

El aprendizaje no supervisado puede clasificarse a su vez en dos categorías:

• Aprendizaje no supervisado paramétrico
  En este caso, asumimos una distribución paramétrica de los datos. Se asume que los datos de la muestra provienen de una población que sigue una distribución de probabilidad basada en un conjunto fijo de parámetros. Teóricamente, en una familia de distribuciones normales, todos los miembros tienen la misma forma y están parametrizados por la media y la desviación estándar. Esto significa que si se conoce la media y la desviación estándar, y que la distribución es normal, se conoce la probabilidad de cualquier observación futura. El aprendizaje paramétrico no supervisado implica la construcción de modelos de mezclas gaussianas y el uso del algoritmo de maximización de expectativas para predecir la clase de la muestra en cuestión. Este caso es mucho más difícil que el aprendizaje supervisado estándar porque no hay etiquetas de respuesta disponibles y, por lo tanto, no hay una medida correcta de precisión disponible para comprobar el resultado.
• Aprendizaje no supervisado no paramétrico
  En la versión no parametrizada del aprendizaje no supervisado, los datos se agrupan en clústeres, donde cada clúster (con suerte) dice algo sobre las categorías y clases presentes en los datos. Este método se suele utilizar para modelar y analizar datos con tamaños de muestra pequeños. A diferencia de los modelos paramétricos, los modelos no paramétricos no requieren que el modelador haga ninguna suposición sobre la distribución de la población, por lo que a veces se denominan métodos libres de distribución.

¿Qué es el clustering?

El clustering puede considerarse el problema de aprendizaje no supervisado más importante; así, como cualquier otro problema de este tipo, trata de encontrar una estructura en una colección de datos no etiquetados. Una definición general de clustering podría ser «el proceso de organizar objetos en grupos cuyos miembros son similares de alguna manera». Un clúster es, por tanto, una colección de objetos que son «similares» entre sí y que son «disímiles» a los objetos que pertenecen a otros clústeres.

Clasificación basada en la distancia.

Dado un conjunto de puntos, con una noción de distancia entre puntos, agrupar los puntos en algún número de clusters, tal que

• las distancias internas (dentro del cluster) deben ser pequeñas i.e los miembros de los clústeres son cercanos/similares entre sí.
• Las distancias externas (dentro del clúster) deben ser grandes, es decir, los miembros de los diferentes clústeres son disímiles.

Los objetivos de la agrupación

El objetivo de la agrupación es determinar la agrupación interna en un conjunto de datos no etiquetados. Pero, ¿cómo decidir qué constituye una buena agrupación? Se puede demostrar que no existe un criterio absoluto «mejor» que sea independiente del objetivo final de la agrupación. En consecuencia, es el usuario quien debe suministrar este criterio, de forma que el resultado de la agrupación se adapte a sus necesidades.

En la imagen anterior, ¿cómo sabemos cuál es la mejor solución de agrupación?

Para encontrar una solución de clustering particular, necesitamos definir las medidas de similitud para los clusters.

Medidas de proximidad

Para el clustering, necesitamos definir una medida de proximidad para dos puntos de datos. La proximidad aquí significa cuán similares/disímiles son las muestras con respecto a la otra.

• Medida de similitud S(xi,xk): grande si xi,xk son similares
• Medida de disimilitud (o distancia) D(xi,xk): pequeña si xi,xk son similares

Hay varias medidas de similitud que se pueden utilizar.

• Vectores: Distancia Coseno

• Conjuntos: Distancia Jaccard

• Puntos: Distancia euclidiana
  q=2

Una «buena» medida de proximidad depende MUCHO de la aplicación. Los clusters deben ser invariantes bajo las transformaciones «naturales» del problema. Además, al agrupar no se aconseja normalizar los datos que se extraen de múltiples distribuciones.

Algoritmos de clustering

Los algoritmos de clustering pueden clasificarse como se indica a continuación:

• Clusterización exclusiva
• Clusterización superpuesta
• Clusterización jerárquica
• Clusterización probabilística

En el primer caso los datos se agrupan de forma exclusiva, de manera que si un determinado punto de datos pertenece a un cluster definido entonces no podría ser incluido en otro cluster. Un ejemplo sencillo de ello se muestra en la figura siguiente, donde la separación de los puntos se consigue mediante una línea recta en un plano bidimensional.

Por el contrario, el segundo tipo, el clustering de solapamiento, utiliza conjuntos difusos para agrupar los datos, de forma que cada punto puede pertenecer a dos o más clusters con diferentes grados de pertenencia. En este caso, los datos se asociarán a un valor de pertenencia apropiado.

Un algoritmo de clustering jerárquico se basa en la unión entre los dos clusters más cercanos. La condición inicial se realiza estableciendo cada punto de datos como un clúster. Después de unas cuantas iteraciones se llega a los clusters finales deseados.

Finalmente, el último tipo de clustering utiliza un enfoque completamente probabilístico.

En este blog hablaremos de cuatro de los algoritmos de clustering más utilizados:

• K-means
• Fuzzy K-means
• Clustering jerárquico
• Mezcla de Gaussianos

Cada uno de estos algoritmos pertenece a uno de los tipos de clustering mencionados anteriormente. Mientras que, K-means es un algoritmo de clustering exclusivo, Fuzzy K-means es un algoritmo de clustering superpuesto, el clustering jerárquico es obvio y por último la Mezcla de Gaussianos es un algoritmo de clustering probabilístico. Discutiremos sobre cada método de clustering en los siguientes párrafos.

K-Means Clustering

K-means es uno de los algoritmos más simples de aprendizaje no supervisado que resuelve el conocido problema de clustering. El procedimiento sigue una forma sencilla y fácil de clasificar un conjunto de datos dado a través de un cierto número de clusters (supongamos k clusters) fijados a priori. La idea principal es definir k centros, uno para cada cluster. Estos centros deben colocarse de forma inteligente, ya que una ubicación diferente provoca un resultado diferente. Por lo tanto, la mejor opción es colocarlos lo más lejos posible unos de otros. El siguiente paso es tomar cada punto perteneciente a un conjunto de datos determinado y asociarlo al centroide más cercano. Cuando no hay ningún punto pendiente, se completa el primer paso y se realiza un agrupamiento anticipado. En este punto tenemos que volver a calcular k nuevos centroides como baricentros de los clusters resultantes del paso anterior. Después de tener estos k nuevos centroides, hay que hacer un nuevo agrupamiento entre los mismos puntos del conjunto de datos y el nuevo centroide más cercano. Se ha generado un bucle. Como resultado de este bucle podemos observar que los k centroides cambian su ubicación paso a paso hasta que no se realizan más cambios. En otras palabras los centroides no se mueven más.

Por último, este algoritmo pretende minimizar una función objetivo, en este caso una función de error al cuadrado. La función objetivo

donde

es una medida de distancia elegida entre un punto de datos xi y el centro de cluster cj, es un indicador de la distancia de los n puntos de datos a sus respectivos centros de cluster.

El algoritmo se compone de los siguientes pasos:

• Déjese que X = {x1,x2,x3,……..,xn} sea el conjunto de puntos de datos y que V = {v1,v2,…….,vc} sea el conjunto de centros.
• Seleccione aleatoriamente ‘c’ centros de cluster.
• Calcule la distancia entre cada punto de datos y los centros de cluster.
• Asigne el punto de datos al centro de clúster cuya distancia al centro de clúster sea la mínima de todos los centros de clúster.
• Recalcule el nuevo centro de clúster utilizando:

donde, ‘ci’ representa el número de puntos de datos en ith clúster.

• Recalcular la distancia entre cada punto de datos y los nuevos centros de cluster obtenidos.
• Si ningún punto de datos fue reasignado entonces parar, de lo contrario repetir desde el paso 3).

Aunque se puede demostrar que el procedimiento siempre terminará, el algoritmo k-means no encuentra necesariamente la configuración más óptima, correspondiente al mínimo de la función objetivo global. Además, el algoritmo es muy sensible a los centros de conglomerados iniciales seleccionados al azar. El algoritmo k-means puede ejecutarse varias veces para reducir este efecto.

K-means es un algoritmo sencillo que se ha adaptado a muchos dominios de problemas. Como vamos a ver, es un buen candidato para la extensión para trabajar con vectores de características difusas.

El procedimiento de k-means puede verse como un algoritmo codicioso para la partición de las n muestras en k clusters con el fin de minimizar la suma de las distancias al cuadrado a los centros de los clusters. Tiene algunos puntos débiles:

• No se ha especificado la forma de inicializar las medias. Una forma popular de empezar es elegir aleatoriamente k de las muestras.
• Puede ocurrir que el conjunto de muestras más cercano a mi esté vacío, por lo que no se puede actualizar mi. Este es un problema que debe manejarse durante la implementación, pero generalmente se ignora.
• Los resultados dependen del valor de k y no hay una forma óptima de describir un mejor «k».

Este último problema es particularmente problemático, ya que a menudo no tenemos forma de saber cuántos clusters existen. En el ejemplo anterior, el mismo algoritmo aplicado a los mismos datos produce la siguiente agrupación de 3 medias. ¿Es mejor o peor que el clustering de 2 medias?

Desgraciadamente, no existe una solución teórica general para encontrar el número óptimo de clusters para cualquier conjunto de datos. Un enfoque sencillo consiste en comparar los resultados de múltiples ejecuciones con diferentes clases k y elegir la mejor según un criterio determinado, pero hay que tener cuidado porque al aumentar k se obtienen valores de la función de error más pequeños por definición, pero también aumenta el riesgo de sobreajuste.

Fuzzy K-Means Clustering

En el clustering difuso, cada punto tiene una probabilidad de pertenecer a cada cluster, en lugar de pertenecer completamente a un solo cluster como ocurre en el k-means tradicional. Fuzzy k-means trata específicamente de lidiar con el problema en el que los puntos están un poco entre los centros o de otra manera ambigua mediante la sustitución de la distancia con la probabilidad, que por supuesto podría ser alguna función de la distancia, como tener la probabilidad relativa a la inversa de la distancia. Fuzzy k-means utiliza un centroide ponderado basado en esas probabilidades. Los procesos de inicialización, iteración y terminación son los mismos que los utilizados en k-means. Los clusters resultantes se analizan mejor como distribuciones probabilísticas que como una asignación dura de etiquetas. Hay que tener en cuenta que k-means es un caso especial de k-means difuso cuando la función de probabilidad utilizada es simplemente 1 si el punto de datos es el más cercano a un centroide y 0 en caso contrario.

El algoritmo de k-means difuso es el siguiente:

• Supongamos un número fijo de clusters K.
• Inicialización: Inicializar aleatoriamente los k-means μk asociados a los clusters y calcular la probabilidad de que cada punto de datos Xi sea miembro de un cluster K dado,
  P(PuntoXiTieneEtiquetaK|Xi,K).
• Iteración: Recalcular el centroide del cluster como el centroide ponderado dadas las probabilidades de pertenencia de todos los puntos de datos Xi :

• Terminación: Iterar hasta la convergencia o hasta que se haya alcanzado un número de iteraciones especificado por el usuario (la iteración puede quedar atrapada en algunos máximos o mínimos locales)

Para una mejor comprensión, podemos considerar este sencillo ejemplo monodimensional. Dado un determinado conjunto de datos, supongamos que los representamos como distribuidos en un eje. La figura siguiente lo muestra:

Mirando la imagen, podemos identificar dos clusters en la proximidad de las dos concentraciones de datos. Nos referiremos a ellos utilizando «A» y «B». En el primer enfoque mostrado en este tutorial -el algoritmo k-means- asociamos cada punto de datos a un centroide específico; por lo tanto, esta función de pertenencia tenía el siguiente aspecto:

En el enfoque Fuzzy k-means, en cambio, el mismo punto de datos dado no pertenece exclusivamente a un cluster bien definido, sino que puede situarse en un camino intermedio. En este caso, la función de pertenencia sigue una línea más suave para indicar que cada punto de datos puede pertenecer a varios clusters con diferente grado de pertenencia.

En la figura anterior, el punto de datos mostrado como punto marcado en rojo pertenece más al cluster B que al cluster A. El valor 0,2 de ‘m’ indica el grado de pertenencia a A de dicho punto de datos.

Algoritmos de agrupación jerárquica

Dado un conjunto de N elementos a agrupar, y una matriz de distancias (o similitudes) N*N, el proceso básico de la agrupación jerárquica es el siguiente:

• Empiece asignando cada elemento a un clúster, de modo que si tiene N elementos, ahora tiene N clústeres, cada uno de los cuales contiene sólo un elemento. Deje que las distancias (similitudes) entre los clústeres sean las mismas que las distancias (similitudes) entre los elementos que contienen.
• Encuentre el par de clústeres más cercano (más similar) y fúndalo en un solo clúster, de modo que ahora tiene un clúster menos.
• Calcule las distancias (similitudes) entre el nuevo clúster y cada uno de los antiguos clústeres.
• Repita los pasos 2 y 3 hasta que todos los elementos estén agrupados en un solo clúster de tamaño N.

El clustering como mezcla de gaussianos

Hay otra forma de tratar los problemas de clustering: un enfoque basado en el modelo, que consiste en utilizar ciertos modelos para los clusters e intentar optimizar el ajuste entre los datos y el modelo.

En la práctica, cada cluster puede ser representado matemáticamente por una distribución paramétrica, como una gaussiana. Por lo tanto, todo el conjunto de datos se modela mediante una mezcla de estas distribuciones.
Un modelo de mezcla con alta probabilidad tiende a tener los siguientes rasgos:

• las distribuciones de los componentes tienen altos «picos» (los datos en un clúster están apretados);
• el modelo de mezcla «cubre» bien los datos (los patrones dominantes en los datos son capturados por las distribuciones de los componentes).

Principales ventajas de la agrupación basada en modelos:

• se dispone de técnicas de inferencia estadística bien estudiadas;
• flexibilidad en la elección de la distribución de componentes;
• obtener una estimación de la densidad para cada cluster;
• se dispone de una clasificación «suave».

Mezcla de Gaussianas
El método de agrupación más utilizado de este tipo se basa en el aprendizaje de una mezcla de Gaussianas:

Un modelo de mezcla es una mezcla de k distribuciones de componentes que colectivamente forman una distribución de mezcla f(x):

La αk representa la contribución del kº componente en la construcción de f(x). En la práctica, se suelen utilizar distribuciones paramétricas (por ejemplo, gaussianas), ya que se ha trabajado mucho para entender su comportamiento. Si se sustituye cada fk(x) por una gaussiana, se obtiene lo que se conoce como modelo de mezcla gaussiana (GMM).

El algoritmo EM

La maximización de expectativas asume que los datos están compuestos por múltiples distribuciones normales multivariantes (nótese que es una suposición muy fuerte, en particular cuando se fija el número de clusters). De forma alternativa, EM es un algoritmo para maximizar una función de verosimilitud cuando algunas de las variables de su modelo no son observadas (es decir, cuando tiene variables latentes).
Podría preguntarse, si sólo estamos tratando de maximizar una función, por qué no usamos la maquinaria existente para maximizar una función. Pues bien, si se intenta maximizarla tomando derivadas y poniéndolas a cero, se encuentra que en muchos casos las condiciones de primer orden no tienen solución. Hay un problema del huevo y la gallina en que para resolver los parámetros de tu modelo necesitas conocer la distribución de tus datos no observados; pero la distribución de tus datos no observados es una función de tus parámetros del modelo.

La maximización de expectativas trata de evitar esto adivinando iterativamente una distribución para los datos no observados, luego estimando los parámetros del modelo maximizando algo que es un límite inferior en la función de verosimilitud real, y repitiendo hasta la convergencia:

El algoritmo de maximización de expectativas

• Comienza con la conjetura de los valores de tus parámetros del modelo
• Paso E: Para cada punto de datos que tenga valores perdidos, utilice su ecuación del modelo para resolver la distribución de los datos perdidos dada su suposición actual de los parámetros del modelo y dados los datos observados (tenga en cuenta que está resolviendo una distribución para cada valor perdido, no para el valor esperado). Ahora que tenemos una distribución para cada valor que falta, podemos calcular la expectativa de la función de verosimilitud con respecto a las variables no observadas. Si nuestra conjetura para el parámetro del modelo era correcta, esta probabilidad esperada será la probabilidad real de nuestros datos observados; si los parámetros no eran correctos, sólo será un límite inferior.
• Paso M: Ahora que tenemos una función de probabilidad esperada sin variables no observadas en ella, maximice la función como lo haría en el caso totalmente observado, para obtener una nueva estimación de los parámetros de su modelo.
• Repita hasta la convergencia.

Problemas asociados a la agrupación

Hay una serie de problemas con la agrupación. Entre ellos:

• Tratar con un gran número de dimensiones y un gran número de datos puede ser problemático debido a la complejidad del tiempo;
• la eficacia del método depende de la definición de «distancia» (para la agrupación basada en la distancia). Si no existe una medida de distancia obvia debemos «definirla», lo que no siempre es fácil, especialmente en espacios multidimensionales;
• el resultado del algoritmo de clustering (que en muchos casos puede ser arbitrario en sí mismo) puede ser interpretado de diferentes maneras.

Posibles aplicaciones

Los algoritmos de clustering pueden aplicarse en muchos campos, por ejemplo:

• Marketing: encontrar grupos de clientes con un comportamiento similar dada una gran base de datos de clientes que contenga sus propiedades y registros de compras anteriores;
• Biología: clasificación de plantas y animales dadas sus características;
• Seguros: identificación de grupos de titulares de pólizas de seguros de automóviles con un coste medio de siniestros elevado; identificación de fraudes;
• Estudios de terremotos: agrupación de epicentros de terremotos observados para identificar zonas peligrosas;
• World Wide Web: clasificación de documentos; agrupación de datos de weblogs para descubrir grupos de patrones de acceso similares.