¿Qué es el Clustering K-Medias?

El clustering K-medias es un algoritmo de aprendizaje no supervisado, y de todos los algoritmos de aprendizaje no supervisado, el clustering K-medias podría ser el más ampliamente utilizado, gracias a su potencia y simplicidad. ¿Cómo funciona exactamente el clustering K-medias?

La respuesta breve es que el clustering K-medias funciona creando un punto de referencia (un centroide) para un número deseado de clases, y luego asignando puntos de datos a clusters de clases en función de qué punto de referencia esté más cerca. Aunque esa es una definición rápida para el clustering K-medias, tomémonos un momento para sumergirnos más profundamente en el clustering K-medias y obtener una mejor intuición de cómo opera.

Definiendo Clustering

Antes de examinar los algoritmos exactos utilizados para llevar a cabo el clustering K-medias, tomémonos un momento para definir el clustering en general.

Los clusters son simplemente grupos de elementos, y el clustering es simplemente poner elementos en esos grupos. En el sentido de la ciencia de datos, los algoritmos de clustering tienen como objetivo hacer dos cosas:

• Asegurarse de que todos los puntos de datos en un cluster sean lo más similares posible entre sí.
• Asegurarse de que todos los puntos de datos en clusters diferentes sean lo más disímiles posible entre sí.

Los algoritmos de clustering agrupan elementos en función de alguna métrica de similitud. Esto se hace a menudo encontrando el “centroide” de los diferentes grupos posibles en el conjunto de datos, aunque no de manera exclusiva. Hay una variedad de diferentes algoritmos de clustering, pero el objetivo de todos los algoritmos de clustering es el mismo, determinar los grupos intrínsecos de un conjunto de datos.

Clustering K-Medias

El clustering K-medias es uno de los algoritmos de clustering más antiguos y comúnmente utilizados, y opera en función de la cuantificación de vectores. Hay un punto en el espacio elegido como origen, y luego se dibujan vectores desde el origen hasta todos los puntos de datos en el conjunto de datos.

En general, el clustering K-medias se puede desglosar en cinco pasos diferentes:

• Colocar todas las instancias en subconjuntos, donde el número de subconjuntos es igual a K.
• Encontrar el punto medio/centroide de las particiones de cluster recién creadas.
• En función de estos centroides, asignar cada punto a un cluster específico.
• Calcular las distancias desde cada punto hasta los centroides, y asignar puntos a los clusters donde la distancia desde el centroide es mínima.
• Después de que los puntos hayan sido asignados a los clusters, encontrar el nuevo centroide de los clusters.

Los pasos anteriores se repiten hasta que se completa el proceso de entrenamiento.

En la fase inicial, los centroides se colocan en algún lugar entre los puntos de datos.
Foto: Weston.pace a través de wikimedia commons, Licencia de Documentación Libre de GNU (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_1.svg)

Alternativamente, después de que los centroides hayan sido colocados, podemos concebir el clustering K-medias como alternar entre dos fases diferentes: etiquetar puntos de datos y actualizar centroides.

En el segundo paso, se utiliza una métrica de distancia como la distancia euclidiana para calcular a qué centroide está más cerca un punto determinado, y luego los puntos se asignan a la clase de ese centroide. Foto: Weston.pace a través de Wikimedia Commons, Licencia de Documentación Libre de GNU (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_2.svg)

En la fase de etiquetado de puntos de datos, cada punto de datos se asigna una etiqueta que lo coloca en el cluster que pertenece al centroide más cercano. El centroide más cercano se determina típicamente utilizando la distancia euclidiana al cuadrado, aunque se pueden utilizar otras métricas de distancia como la distancia de Manhattan, la distancia del coseno y la distancia de Jaccard, dependiendo del tipo de datos que se alimentan al algoritmo de clustering.

En el tercer paso, los centroides se mueven al promedio de todos los puntos de datos. Las clases se reasignan. Foto: Weston.pace a través de Wikiemedia Commons, CC SA 3.0 (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_3.svg)

En la fase de actualización del centroide, los centroides se calculan encontrando la distancia media entre todos los puntos de datos actualmente contenidos en un cluster.

Cómo elegir el valor correcto para “K”

Considerando que el clustering K-medias es un algoritmo no supervisado y el número de clases no se conoce de antemano, ¿cómo se decide el número adecuado de clases/valor correcto para K?

Una técnica para seleccionar el valor correcto de K es llamada “la técnica del codo”. La técnica del codo consiste en ejecutar un algoritmo de clustering K-medias para una gama de diferentes valores de K y utilizar una métrica de precisión, típicamente la suma de los errores cuadrados, para determinar qué valores de K dan los mejores resultados. La suma de los errores cuadrados se determina calculando la distancia media entre el centroide de un cluster y los puntos de datos en ese cluster.

El término “técnica del codo” proviene del hecho de que cuando se traza la SSE con respecto a los diferentes valores de K, la gráfica resultante a menudo tiene una forma de “codo”, donde la SSE disminuye rápidamente para los primeros valores de K, pero luego se nivelan. En tales condiciones, el valor de K ubicado en el codo es el mejor valor para K, ya que hay rendimientos rápidamente disminuidos después de este valor.

Clustering K-Medias por Lotes

A medida que los conjuntos de datos crecen en tamaño, el tiempo de cálculo también crece. El clustering K-medias básico puede tardar mucho en completarse cuando se ejecuta en conjuntos de datos masivos, y como resultado, se han realizado ajustes al clustering K-medias para permitir reducir los costos espaciales y temporales del algoritmo.

El clustering K-medias por lotes es una variante del clustering K-medias donde el tamaño del conjunto de datos que se considera está limitado. El clustering K-medias normal opera en el conjunto de datos completo/lote a la vez, mientras que el clustering K-medias por lotes divide el conjunto de datos en subconjuntos. Los lotes se muestrean aleatoriamente del conjunto de datos completo y para cada nueva iteración se selecciona y se utiliza una nueva muestra aleatoria para actualizar la posición de los centroides.

En el clustering K-medias por lotes, los clusters se actualizan con una combinación de los valores del lote y una tasa de aprendizaje. La tasa de aprendizaje disminuye con las iteraciones, y es el inverso del número de puntos de datos colocados en un cluster específico. El efecto de reducir la tasa de aprendizaje es que el impacto de los nuevos datos se reduce y se logra la convergencia cuando, después de varias iteraciones, no hay cambios en los clusters.

Los resultados de los estudios sobre la efectividad del clustering K-medias por lotes sugieren que puede reducir con éxito el tiempo de cálculo con un ligero compromiso en la calidad del cluster.

Aplicaciones del Clustering K-Medias

El clustering K-medias se puede utilizar de manera segura en cualquier situación en la que los puntos de datos se puedan segmentar en grupos/clases distintos. A continuación, se presentan algunos ejemplos de casos de uso comunes para el clustering K-medias.

El clustering K-medias se podría aplicar a la clasificación de documentos, agrupando documentos en función de características como temas, etiquetas, uso de palabras, metadatos y otras características de los documentos. También se podría utilizar para clasificar a los usuarios como bots o no bots en función de patrones de actividad como publicaciones y comentarios. El clustering K-medias también se puede utilizar para poner a las personas en grupos en función de los niveles de preocupación al monitorear su salud, en función de características como comorbilidades, edad, historial de paciente, etc.

El clustering K-medias también se puede utilizar para tareas más abiertas como la creación de sistemas de recomendación. Los usuarios de un sistema como Netflix se pueden agrupar en función de patrones de visualización y recomendar contenido similar. El clustering K-medias se podría utilizar para tareas de detección de anomalías, resaltando posibles instancias de fraude o artículos defectuosos.