¿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 poder 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 basado en qué punto de referencia es el más cercano. Mientras que esa es una definición rápida para el clustering K-medias, tomémonos un tiempo para profundizar 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 poco de tiempo para definir el clustering en general.

Los clusters son solo grupos de artículos, y el clustering es solo poner artículos en esos grupos. En el sentido de la ciencia de datos, los algoritmos de clustering apuntan a hacer dos cosas:

• Asegurarse de que todos los puntos de datos en un cluster sean tan similares entre sí como sea posible.
• Asegurarse de que todos los puntos de datos en clusters diferentes sean tan disímiles entre sí como sea posible.

Los algoritmos de clustering agrupan artículos juntos basado en 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 exclusivamente. 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 a un conjunto de datos.

Clustering K-Medias

El clustering K-medias es uno de los tipos de algoritmos de clustering más antiguos y comúnmente utilizados, y opera basado en la cuantización de vectores. Hay un punto en el espacio elegido como origen, y luego se dibujan vectores desde el origen a 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.
• Basado en estos centroides, asignar cada punto a un cluster específico.
• Calcular las distancias desde cada punto a los centroides, y asignar puntos a los clusters donde la distancia desde el centroide es la 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 termina 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 gratuita 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 intercambiar hacia atrás y hacia adelante 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 dado, y luego se asignan los puntos a la clase del centroide. Foto: Weston.pace a través de Wikimedia Commons, Licencia de documentación gratuita 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 vuelven a asignar. 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 el paso 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/ el 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 el error cuadrático suma, para determinar qué valores de K dan los mejores resultados. El error cuadrático suma 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 el error cuadrático suma con respecto a los diferentes valores de K, la línea resultante a menudo tiene una forma de “codo”, donde el error cuadrático suma 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 Mini-Lote

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 tiempo 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 mini-lote 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/batch completo de una vez, mientras que el clustering K-medias mini-lote divide el conjunto de datos en subconjuntos. Los mini-lotes se muestran aleatoriamente del conjunto de datos completo y para cada nueva iteración se selecciona una nueva muestra aleatoria y se utiliza para actualizar la posición de los centroides.

En el clustering K-medias mini-lote, los clusters se actualizan con una combinación de los valores mini-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 mini-lote 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 con seguridad en cualquier situación en la que los puntos de datos se puedan segmentar en grupos/clases distintos. Aquí hay 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 según características como temas, etiquetas, uso de palabras, metadatos y otras características del documento. También se podría utilizar para clasificar a los usuarios como bots o no bots según patrones de actividad como publicaciones y comentarios. El clustering K-medias también se puede utilizar para poner a las personas en grupos según los niveles de preocupación al monitorear su salud, según características como comorbilidades, edad, historial del 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 juntos según patrones de visualización y se les puede 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.