Autor

Alejandro Alcalde

Graduado en Ingeniería Informática en la ETSIIT, Granada. Creador de El Baúl del Programador

Más artículos de Alejandro Alcalde

Este articulo forma parte de una serie de artículos sobre clustering, detección de anomalías y reglas de asociación. Originalmente forman parte de un trabajo para el Máster Universitario Oficial en Ciencia de Datos e Ingeniería de Computadores de la Universidad de Granada en la asignatura Aprendizaje no supervisado y detección de anomalías. El resto de artículos son:

El aprendizaje automático se distingue en dos tipos. Supervisado, donde se dispone de información sobre la clase a la que pertenece una instancia o no supervisado, donde esta información no está disponible. Estos apuntes se centran en el último tipo. En la figura se muestra un árbol de tipos de clasificaciones.

Árbol de tipos de clasificaciones

Clustering

Clustering intenta encontrar patrones en los datos que formen grupos claramente separados. Encontrar estos grupos tiene varias aplicaciones. Por ejemplo si los datos tratan sobre clientes, cada grupo encontrado podría usarse para realizar una segmentación de clientes en marketing, y ofrecer así distintos productos a cada grupo. Otra posible aplicación es agrupar documentos por temática, donde cada cluster o grupo pertenece a un tipo de documento. En este tipo de aplicaciones clustering se usa como aplicación final, sin embargo puede usarse como paso previo a otras técnicas de aprendizaje. Algunos ejemplos son exploración de datos y preprocesamiento de datos.

Uno de los problemas del clustering es su subjetividad. En la Figura de abajo aparece un conjunto de datos, pero bajo este mismo conjunto se pueden hacer agrupamientos diferentes.

Agrupar es subjetivo. Créd. Prof. Juan Carlos Cubero


¿Te gusta el blog? Ayúdame a seguir escribiendo


Medidas de similitud

Una solución al problema descrito en la sección anterior es definir una buena medida de similitud. Para ello es necesario usar únicamente los atributos adecuados, no es necesario usar todos los atributos para calcular la similitud de una instancia frente a otra. También es importante tener en cuenta las magnitudes de cada atributo como paso previo a calcular la similitud, y por tanto es necesario normalizar. Principalmente hay dos formas de normalizar un conjunto de datos para atributos continuos. El método Min-Max y z-score. Estas normalizaciones se deben llevar a cabo para cada atributo del conjunto de datos. Es recomendable eliminar cualquier outlier, ya que puede afectar mucho al proceso de normalización. De los dos anteriores, es recomendable usar z-score, ya que preserva el rango de los datos.

Para crear medidas de similitud se consideran la semejanzas o distancias. A mayor valor de semejanza, más se parecen los dos puntos en comparación, sin embargo, a mayor distancia, menor parecido. Es común usar medidas de distancia para descubrir cómo de semejantes son dos puntos. Toda medida de distancia debe cumplir una serie de propiedades, listadas a continuación.

La desigualdad triangular puede comprenderse mejor visualmente en la figura. Es decir, la suma de dos de los lados del triángulo siempre va a ser mayor o igual a la del lado restante. Como muestra la figura, conforme menos área tiene el triángulo, más cercana es la suma de dos lados al lado restante.

Desigualdad triangular explicada visualmente. Créd. Wikipedia

Medidas de distancia

Las principales medidas de distancia son:

La distancia Euclídea es la línea recta entre dos puntos. En la distancia Manhattan la distancia entre dos puntos es la suma en valor absoluto de las diferencias de sus coordenadas cartesianas. La Figura muestra cómo pueden existir varios caminos a dos puntos usando Manhattan, pero solo uno y el más corto por Euclídea.

Distancias Manhattan y Euclidea. Las líneas roja, azul y amarilla tienen distancia Manhattan 12, la menor posible. La verde tiene distancia Euclídea 8.49. *Créd. [Wikipedia]

La distancia de Minkowski es una generalización de las dos anteriores

En la distancia de Chebyshev la distancia entre dos puntos es la mayor de sus diferencias a lo largo de cualquiera de sus dimensiones coordenadas. También conocida como la distancia del tablero de ajedrez, por coincidir con el número de movimientos que puede hacer el rey para moverse por el tablero, como muestra la figura.

Distancia de Chebyshev. *Créd. Wikipedia*

Por último la distancia de Minkowski es una generalización de las anteriores. Cuando \(p = 1\) corresponde con la distancia de Manhattan, para \(p = 2\) distancia Euclídea, y cuando \(p \to \infty\) corresponde con la distancia de Chebyshev. En la figura aparecen distintas distancias para varios valores de \(p\), en esta imagen se aprecia la distancia Manhattan para \(p=1\), Euclídea para \(p=2\) y Chebyshev para \(p=\infty\).

Distintos valores de \\(p\\) para la distancia de Minkowski. *Créd. Wikipedia*

Tipos de Clustering

Dentro de la clasificación no supervisada se distinguen principalmente los siguientes tipos de clustering:

Tipos de medidas de proximidad para clustering aglomerativo
Agrupamiento por particiones. Cred. Transparencias de clase.
Distintos tipos de clustering para los mismos datos

Algoritmos de clustering

K-Means

K-Means es un un algoritmo de clustering por particiones. Tiene un parámetro de entrada, k, indicando el número de clusters a generar, por tanto es necesario conocer a priori el número de grupos a encontrar. Cada cluster está representado por su centroide (centro geométrico del cluster). Los centroides pueden ser puntos reales o no, en caso de ser un punto real del conjunto de datos se denominan menoides. En cada iteración del algoritmo dichos centroides se recalculan hasta llegar a un criterio de parada. La figura muestra ejemplos de varias iteraciones de K-Means, en él se ilustra el proceso de actualización de los centroides.

Ejemplo ejecución de k-means

Descripción del algoritmo

K-Means se compone de dos fases principales:

El proceso de inicialización consta de dos pasos. Primeramente se escoge el número de centroides (k) y se asignan aleatoriamente, como muestra la figura (a). Una vez colocados los a cada punto se le asigna su correspondiente cluster usando la media como medida de proximidad. Posteriormente se recalculan los centroides con los puntos asignados y se actualizan.

El proceso iterativo actualiza los centroides en cada iteración mientras los centroides cambien. En cada iteración se calcula la distancia de todos los puntos a los k centroides, formando k grupos y asignando a cada punto su centroide más cercano.

Asignación de clusters a los puntos

Para asignar a un punto el cluster más cercano es necesario usar una medida de proximidad, la más común es la distancia Euclídea (\(L_2\)), aunque no es la única y la elección depende del tipo de datos. Al re-calcular los centroides de cada cluster se optimiza una función objetivo, por ejemplo minimizar la distancias al cuadrado de cada punto a su cluster más cercano, como muestra la siguiente ecuación: \[SSE = \sum^K_{i=1}\sum_{\textbf{x}\in C_i} dist \left ( c_i, x \right )^2\] donde \(C_i\) es el i-ésimo cluster, \(c_i\) es el centróide del cluster \(C_i\) y \(\textbf{x}\) es un punto y \(dist\) es la distancia.

Con esta función objetivo, se calcula el error de cada punto, es decir, su distancia euclídea al cluster más cercano, luego se calcula la suma total de los errores al cuadrado. Con este dato, y dados dos conjuntos de clusters distintos generados por el algoritmo, K-Means escoge aquel con menor error cuadrático.

Dada esta función objetivo, lo ideal es resolver el problema de optimización y encontrar el óptimo global, sin embargo es computacionalmente imposible de realizar. Por ello se realizan aproximaciones, como gradiente descendente. Esta técnica consiste en escoger una solución inicial y repetir estos dos pasos: Calcular el cambio en la solución que mejor optimizar la función objetivo (Mediante derivadas) y actualizar la solución.

Elección de los centroides iniciales

Elegir los centroides iniciales al azar usualmente no da buenos resultados, ya que el SSE variará notablemente en función de qué centroides iniciales se escojan. Una posible solución consiste en lanzar el algoritmo varias veces con distintos centroides iniciales y escoger los mejores, pero el problema sigue existiendo debido a la naturaleza aleatoria de este proceso. Otra alternativa es estimar seleccionar el primero punto de forma aleatoria, o calcular el centroide usando todos los puntos. Posteriormente, para cada centroide inicial, seleccionar el punto más alejado de cualquiera de los centroides iniciales ya seleccionados. De esta forma está garantizado elegir un conjunto de centroides iniciales aleatorios y separados entre sí.

Elección del k óptimo

No hay ninguna forma de obtener el k óptimo salvo prueba y error. Sin embargo, se pueden usar algunas técnicas que suelen dar buenos resultados. Un ejemplo de ello es la técnica del codo. Se lanza el algoritmo para varios k y se genera un gráfico de cada k junto a su error. Un buen k debería ser el que se corresponda con un codo en el gráfico. La figura muestra un ejemplo.

Método del codo para elección de k

Problemas de K-Means

Los principales problemas de este algoritmo son los outliers, ya que alteran las media de la distancia bastante. Una posible solución es usar la mediana como medida de proximidad en lugar de la media, en dicho caso es necesario usar la distancia de Manhattan. Una posible solución es eliminar dichos outliers, pero dependiendo del tipo de datos esto puede ser otro problema en sí mismo. Otra forma es usar menoides en lugar de centroides. Al usar un dato existente como centroide se minimiza el error introducido por los outliers.

Cuando se tratan datos no numéricos, es posible usar k-modes. Esta variación del algoritmo escoge como centroide el valor de moda en el conjunto. El punto fuerte de esta técnica es que es muy robusto a outliers.

Pre y Post procesamiento requerido

Debido a que K-Means usa distancias, es necesario normalizar los datos para que todas contribuyan en igual medida, de lo contrario los atributos con mayores magnitudes tienen a dominar las decisiones del algoritmo.

En cuanto al post procesamiento, es posible eliminar clusters demasiado pequeños, y tratarlos como clusters outliers, dividir clusters con un elevado SSE en varios o combinar aquellos con un SSE bajo.

DBSCAN

Este algoritmo es de la familia jerárquica del clustering, concretamente basado en densidad. Su principal característica es detectar regiones de puntos densas separadas de otras regiones poco densas. Al contrario que K-Means, detecta automáticamente el número de clusters. Debido a que las regiones poco densas son descartadas, no produce un clustering completo, es decir, habrá puntos sin clasificar.

DBSCAN está basado en una aproximación basada en el centro. Consiste en medir la densidad como el número de puntos que caen dentro de un radio especificado. El radio por tanto, es un parámetro del algoritmo que se debe ajustar. Una vez definido el radio, un punto puede caer en el interior de una región densa, en el borde o completamente fuera. A estos puntos se les llama puntos core, border o noise, respectivamente ( en español Principales, frontera o ruido). La figura muestra un ejemplo de cada uno de ellos.

Tipos de puntos en DBSCAN

Descipción del algoritmo.

Para cualquier par de puntos core lo suficientemente cercanos entre sí – dentro de un radio definido – se colocan en el mismo cluster. Análogamente, cualquier punto border cercano a un core se asigna al mismo cluster del core. Los puntos de ruido, se descartan, por ello se indicó en el párrafo anterior que DBSCAN no es un clustering completo.

Selección de parámetros.

DBSCAN necesita de dos parámetros antes de ser ejecutado, MinPts y Eps, definiendo el número mínimo de puntos necesarios para considerar a un punto como core y el radio, respectivamente. Lo más usual es observar cómo evoluciona la distancia de un punto a sus k-ésismos vecinos más cercanos (k-distancia). Para los puntos que forman parte de un cluster, el valor k-distancia será pequeño si k no es mayor que el tamaño del cluster. Para los puntos que no pertenecen al cluster, la k-distancia será elevada. Por tanto, de forma visual es posible determinar el valor del parámetro Eps, como muestra la figura, y tomando el valor de k como MinPts.

Elección de Eps y MinPts

Pros y Contras de DBSCAN.

Que DBSCAN al use una aproximación basada en densidad le proporciona resistencia al ruido y es capaz de trabajar con clusters de tamaños y formas arbitrarias, por tanto puede encontrar clusters que K-Means no podría. Sin embargo, DBSCAN encuentra dificultades al trabajar con clusters de distintas densidades. De igual manera, no funciona bien cuando los datos son de gran dimensionalidad, ya que medir la densidad en espacios de gran dimensión es difícil.

Evaluación de resultados

Para la evaluación del resultado de un clustering es necesario tener en cuenta varios aspectos, entre ellos: 1. Determinar la tendencia del *clustering*, es decir, distinguir si realmente existe una estructura no aleatoria en los datos. 2. Determinar el número correcto de clusters. 3. Evaluar si realmente el resultado del clustering corresponde con los patrones de los datos, sin referenciar a información externa (Criterios internos). 4. Comparar los resultados del clustering usando información externa, como etiquetas de las clases (criterios externos). 5. Comprar dos conjuntos de clusters y determinar cual es mejor.

Debido a que las técnicas 1,2 y 3 no usan información externa, son técnicas no supervisadas, la cuarta sin embargo necesita información externa, y por tanto es supervisada. La quita puede considerarse un híbrido, ya que puede realizarse de forma supervisada o no supervisada.

Las técnicas no supervisadas tratan me medir si la estructura del clustering es adecuada sin información externa. Un ejemplo de ello es mediante el uso de SSE. Usando esta medida es posible definir la cohesión del cluster, la cual determina cómo están de juntos los puntos del cluster así como la separación, que mide cómo de separado está un cluster con respecto a otro. Para realizar estas mediciones pueden usarse o no los centroides, como muestra la figura.

Formas de medir la cohesión y separación. *Créd. J.C Cubero*

En cuanto a las técnicas supervisadas, usando información externa, como por ejemplo datos etiquetados, mide hasta qué punto el clustering consiguió descubrir la estructura de los datos. Un ejemplo de este tipo de técnica es la entropía, la cual mide cómo de bien coinciden las etiquetas de los clusters con unos datos etiquetados previamente.

Por último, comparar dos conjuntos de clusterings puede hacerse de forma supervisada o no supervisada. Por ejemplo, lanzar dos veces K-Means y compararlos usando SSE o entropía.

Erratas

Bibliografía

¿Has visto algún error?: Por favor, ayúdame a corregirlo contactando conmigo o comentando abajo.

Quizá también te interese leer...