Clustering (Agrupamiento)
UNIVERSIDAD NACIONAL DEL ALTIPLANO PUNO
FACULTAD DE INGENIERÍA MECÁNICA ELÉCTRICA, ELECTRÓNICA Y SISTEMAS
PROGRAMA DE ESTUDIOS DE INGENIERÍA DE SISTEMASApellidos y Nombres, {Vargas Figueroa William Jonathan}
Correo Electrónico, {reyvynz@gmail.com}
Clustering (Agrupamiento)
El clustering consiste en la agrupación automática de datos. Es un tipo de aprendizaje automático no-supervisado. En castellano se denomina agrupamiento. Vamos a ver en más detalle en qué consiste el clustering, el algoritmo de agrupamiento más popular: K-Means y algunos ejemplos.
En el siguiente gráfico podemos ver un conjunto de datos, representados por puntos en 2 dimensiones.
Con estos datos, algunas personas dirían que hay 2 grupos, tal y como se muestra en la siguiente figura.
Sin embargo, otras personas podrían decir que, en realidad, hay 5 grupos.
Esto no significa haya alguien equivocado. Tampoco que todos tengan razón. Tan sólo que los datos son tal y como son pero podemos elegir verlos como más nos convengan.
Las técnicas de clustering intentan descubrir cuál es el mejor agrupamiento de los datos. Algunas de estas técnicas necesitan que especifiquemos el número de grupos de queremos encontrar. Otras técnicas necesitan otros hiper-parámetros.
Cómo funciona K-Means
El algoritmo trabaja iterativamente para asignar a cada “punto” (las filas de nuestro conjunto de entrada forman una coordenada) uno de los “K” grupos basado en sus características. Son agrupados en base a la similitud de sus features (las columnas). Como resultado de ejecutar el algoritmo tendremos:
- Los “centroids” de cada grupo que serán unas “coordenadas” de cada uno de los K conjuntos que se utilizarán para poder etiquetar nuevas muestras.
- Etiquetas para el conjunto de datos de entrenamiento. Cada etiqueta perteneciente a uno de los K grupos formados.
Los grupos se van definiendo de manera “orgánica”, es decir que se va ajustando su posición en cada iteración del proceso, hasta que converge el algoritmo. Una vez hallados los centroids deberemos analizarlos para ver cuales son sus características únicas, frente a la de los otros grupos. Estos grupos son las etiquetas que genera el algoritmo.
Casos de Uso de K-Means
El algoritmo de Clustering K-means es uno de los más usados para encontrar grupos ocultos, o sospechados en teoría sobre un conjunto de datos no etiquetado. Esto puede servir para confirmar -o desterrar- alguna teoría que teníamos asumida de nuestros datos. Y también puede ayudarnos a descubrir relaciones asombrosas entre conjuntos de datos, que de manera manual, no hubiéramos reconocido. Una vez que el algoritmo ha ejecutado y obtenido las etiquetas, será fácil clasificar nuevos valores o muestras entre los grupos obtenidos.
Algunos casos de uso son:
- Segmentación por Comportamiento: relacionar el carrito de compras de un usuario, sus tiempos de acción e información del perfil.
- Categorización de Inventario: agrupar productos por actividad en sus ventas
- Detectar anomalías o actividades sospechosas: según el comportamiento en una web reconocer un troll -o un bot- de un usuario normal
Datos de Entrada para K-Means
Las “features” o características que utilizaremos como entradas para aplicar el algoritmo k-means deberán ser de valores numéricos, continuos en lo posible. En caso de valores categóricos (por ej. Hombre/Mujer o Ciencia Ficción, Terror, Novela,etc) se puede intentar pasarlo a valor numérico, pero no es recomendable pues no hay una “distancia real” -como en el caso de géneros de película o libros-. Además es recomendable que los valores utilizados estén normalizados, manteniendo una misma escala. En algunos casos también funcionan mejor datos porcentuales en vez de absolutos. No conviene utilizar features que estén correlacionados o que sean escalares de otros. Recordar los 7 pasos para el Aprendizaje Automático.
El Algoritmo K-means
El algoritmo utiliza una proceso iterativo en el que se van ajustando los grupos para producir el resultado final. Para ejecutar el algoritmo deberemos pasar como entrada el conjunto de datos y un valor de K. El conjunto de datos serán las características o features para cada punto. Las posiciones iniciales de los K centroids serán asignadas de manera aleatoria de cualquier punto del conjunto de datos de entrada. Luego se itera en dos pasos:
1- Paso de Asignación de datos
En este paso, cada “fila” de nuestro conjunto de datos se asigna al centroide más cercano basado en la distancia cuadrada Euclideana. Se utiliza la siguiente fórmula (donde dist() es la distancia Euclideana standard):
2-Paso de actualización de Centroid
En este paso los centroid de cada grupo son recalculados. Esto se hace tomando una media de todos los puntos asignados en el paso anterior.
El algoritmo itera entre estos pasos hasta cumplir un criterio de detención:
* si no hay cambios en los puntos asignados a los grupos,
* o si la suma de las distancias se minimiza,
* o se alcanza un número máximo de iteraciones.
El algoritmo converge a un resultado que puede ser el óptimo local, por lo que será conveniente volver a ejecutar más de una vez con puntos iniciales aleatorios para confirmar si hay una salida mejor. Recuerden siempre seguir los 7 pasos para construir IA
Elegir el valor de K
Este algoritmo funciona pre-seleccionando un valor de K. Para encontrar el número de clusters en los datos, deberemos ejecutar el algoritmo para un rango de valores K, ver los resultados y comparar características de los grupos obtenidos. En general no hay un modo exacto de determinar el valor K, pero se puede estimar con aceptable precisión siguiendo la siguiente técnica:
Una de las métricas usada para comparar resultados es la distancia media entre los puntos de datos y su centroid. Como el valor de la media diminuirá a medida de aumentemos el valor de K, deberemos utilizar la distancia media al centroide en función de K y entontrar el “punto codo”, donde la tasa de descenso se “afila”. Aquí vemos una gráfica a modo de ejemplo:
Este entrega soluciones iniciales de buena calidad en tiempos computacionales muy cortos.
Responde mejor a tipos de problemas como:
- Heurísticas
- Analizar rasgos de la personalidad de users.
- Ruteo de vehículos, Vehicle Routing Problem (VRP)
REFERENCIAS
https://www.iartificial.net/clustering-agrupamiento-kmeans-ejemplos-en-python/