Características principales
-
Permite encontrar grupos de datos con características similares.
-
Se pueden agrupar para:
-
Identificar clientes con características similares para ofrecer servicios adecuados.
-
Identificar alumnos con rendimientos académicos similares con el objetivo de reducir la deserción escolar.
-
Seguridad: detección de fraudes.
-
Clasificación de documentos.
-
-
Requiere de una medida de similitud o distancia.
Distancia Euclidea
La distancia euclidiana es un número positivo que indica la separación entre dos puntos en un espacio, donde se cumplen los axiomas y teoremas de la geometría de Euclides. La distancia entre dos puntos A y B de un espacio euclidiano es la longitud del vector AB perteneciente a la única recta que pasa por dichos puntos.
Métricas del agrupamiento obtenido
Hay varios medidas de distancia, por eso lo que debemos buscar es un buen método de agrupamiento que produzca grupos de alta calidad donde se tiene que cumplir:
-
El parecido entre los elementos que componen un mismo grupo es alto (intra-cluster).
-
El parecido entre los elementos de grupos distintos es bajo (inter-cluster).
La calidad del agrupamiento depende, entre otros aspectos, de la medida de similitud empleada.
Proceso de Agrupamiento
Existen una serie para realizar un correcto Proceso de Agrupamiento
-
Seleccionar las características relevantes
-
Definir una representación adecuada.
-
Definir la medida de similitud a utilidad (medida de distancia). Depende del problema.
-
Aplicar un algoritmo de agrupamiento
-
Validar los grupos obtenidos y de ser necesario volver a repetir el proceso.
Objetivo del Agrupamiento
Como dijimos previamente el objetivo es buscar que todos los miembros del mismo grupo sean lo más similares posibles:
Buscando:
-
Minimizar la distancia intracluster
-
Maximizar la distancia entre clusters
Algoritmo: Clustering Jerárquicos
Los algoritmos jerárquicos producen como resultado un dendrograma.
A partir del dendrograma se pueden obtener distintas particiones (estructuras de clusters) de los datos.
Dendograma de Agrupamiento
Jerárquico
Tipos de Clustering Jerárquicos
Se pueden definir dos tipos de clustering jerárquico dependiendo de la dirección en la que el algortimo ejecute el agrupamiento (información y gráficos obtenidos de https://estrategiastrading.com/clustering-jerarquico/):
Tipo Aglomerativo: Se agrupa desde los elementos individuales, al inicio cada punto o dato está en un clúster separado. A cada paso, los dos clústers más cercanos se fusionan. Estas fusiones de clústers se siguen produciendo de forma sucesiva produciendo una jerarquía de resultados de clustering. Al final del proceso solo queda un único clúster que aglutina todos los elementos.
Divisible: Empieza a la inversa, se parte desde un único clúster que aglomera todos los datos y vamos dividiendo en clústers más pequeños.
Algoritmo: Clustering Partitivos
Es una técnica de partición de clustering que se enfoca en dividir n observaciones iniciales en k clusters, de modo que cada observación pertenece al cluster cuyo promedio esté más cercano, sirviendo este como el prototipo del cluster.
A diferencia de los jerárquicos se obtiene una única partición de los datos.
Algoritmo K-Means o K-Medias
K-Means es un método de agrupamiento, que tiene como objetivo la partición de un conjunto de n observaciones en k grupos en el que cada observación pertenece al grupo cuyo valor medio es más cercano.
Características
-
El algoritmo K-Medias fue propuesto por MacQueen, en 1967.
-
Requiere conocer a priori el número K de grupos a formar.
-
Cada cluster tiene asociado un centroide (centro geométrico del cluster).
-
Está basado en la minimización de la distancia interna, es decir la suma de las distancias de los patrones asignados a un agrupamiento al centroide de dicho agrupamiento.
-
De hecho, este algoritmo minimiza la suma de las distancias al cuadrado de cada patrón al centroide de su agrupamiento.
-
El algoritmo es sencillo y eficiente.
-
Procesa los patrones secuencialmente (por lo que requiere un almacenamiento mínimo).
-
Está sesgado por el orden de presentación de los patrones (los primeros patrones determinan la configuración inicial de los agrupamientos)
-
Su comportamiento depende enormemente del parámetro K.
-
Los puntos se asignan al cluster cuyo centroide esté más cerca (utilizando cualquier métrica de distancia).
-
Iterativamente, se van actualizando los centroides en función de las asignaciones de puntos a clusters, hasta que los centroides dejen de cambiar.
Pasos del algoritmo K-Means
-
Escoger k centroides aleatoriamente (hay métodos más sofisticados).
-
Formar k grupos, asignando cada punto al centroide más cercano.
Inicialización
Proceso Iterativo
Mientras que los centroides cambien:
-
Calcular las distancias de todos los puntos a los k centroides.
-
Formar k grupos, asignando cada punto al centroide más cercano.
-
Recalcular los nuevos centroides.
¿Cómo saber cual es el valor de K óptimo para un problema dado?
Existen varias alternativas, pero una estrategia es el método del codo o elbow method, ya que es una forma precisa y sencilla (tal como lo menciona Joaquín Rodriguez en https://rpubs.com/Joaquin_AR/310338), cuando afirma que cuando no se dispone de información adicional y se aplica el algoritmo de K-Means, una forma de conocer el K óptimo es identificar aquel valor a partir del cual la reducción en la suma total de varianza intra-cluster deja de ser sustancial. A continuación se muestra un ejemplo del mismo:
De la misma se observa que con un K = 4 la reducción en la suma total de cuadrados internos parece estabilizarse, indicando que ese número es una opción apropiada
¿Qué es el Índice Silhouette?
Un método muy utilizado para la interpretación y validación de la coherencia dentro de CLUSTER DE DATOS. La técnica proporciona una representación gráfica sucinta de lo bien que se ha clasificado cada objeto.
Luego de formar k grupos, puede calcularse el índice Silhouette de cada ejemplo aplicando la siguiente fórmula:
Donde:
-
a(i) es la distancia promedio del ejemplo i a todos los otros ejemplos dentro del mismo cluster.
-
b(i) es la distancia promedio del ejemplo i a todos los otros ejemplos del cluster más cercano.
Promediando todos los valores de s(i) se tendrá el índice Silhouette del agrupamiento.
Clasificación de los Algoritmos de Clustering
Nos parece importante conocer una forma de clasificación de los algoritmos, tal cual la plantea Fernando Berzal en "Clustering basado en particiones"
-
Agrupamiento por particiones
-
k-Means (es importante considerar aquí que k-Medoids se considera como una mejora de K-Means)
-
PAM/CLARA/CLARANS
-
BFR
-
-
Métodos basados en densidad
-
DBSCAN
-
Optics
-
DenClue
-
-
Clustering jerárquico
-
Diana/Agnes
-
BIRCH
-
CURE
-
Chameleon
-
ROCK
-
Algoritmo K-Medoids
El algoritmo K-Means es sensible a la presencia de outliers, como una posible mejora se utiliza el algoritmo K-Medoids; el cual en lugar de utilizar centroides, emplea medoides; es decir, toma como referencia un objeto ya existente en el cluster (idealmente, el objeto más
central del cluster).
