¿Qué es la agrupación en clústeres de K-Means?

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

La respuesta corta es que el agrupamiento de K-medias funciona por creando un punto de referencia (un centroide) para un número deseado de clases, y luego asignación de puntos de datos a grupos de clases según el punto de referencia más cercano. Si bien esa es una definición rápida para el agrupamiento de K-means, tomemos un tiempo para profundizar en el agrupamiento de K-means y obtener una mejor intuición de cómo funciona.

Definición de agrupamiento

Antes de examinar los algoritmos exactos utilizados para llevar a cabo el agrupamiento de K-medias, tomemos un poco de tiempo para definir el agrupamiento en general.

Los clústeres son solo grupos de elementos, y la agrupación en clústeres solo coloca elementos en esos grupos. En el sentido de la ciencia de datos, algoritmos de agrupamiento objetivo de hacer dos cosas:

• Asegúrese de que todos los puntos de datos en un clúster sean lo más similares posible entre sí.
• Asegúrese de que todos los puntos de datos en diferentes clústeres sean lo más diferentes posible entre sí.

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

Agrupamiento de medias K

K-Means Clustering es uno de los tipos de algoritmos de agrupamiento más antiguos y más utilizados, y funciona en base a cuantización vectorial. 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 agrupamiento de K-medias se puede dividir en cinco pasos diferentes:

• Coloque todas las instancias en subconjuntos, donde el número de subconjuntos es igual a K.
• Encuentre el punto medio/centroide de las particiones de clúster recién creadas.
• Según estos centroides, asigne cada punto a un grupo específico.
• Calcule las distancias desde cada punto a los centroides y asigne puntos a los grupos donde la distancia desde el centroide sea la mínima.
• Después de que los puntos hayan sido asignados a los conglomerados, encuentre el nuevo centroide de los conglomerados.

Los pasos anteriores se repiten hasta que finaliza 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 GNU (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_1.svg)

Alternativamente, después de colocar los centroides, podemos concebir el agrupamiento de K-medias como un intercambio 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 el centroide más cercano a un punto dado, y luego los puntos se asignan a la clase de ese centroide. Foto: Weston.pace vía Wikimedia Commons, Licencia GNU Free Doc (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_2.svg)

En la fase de etiquetado de puntos de datos, a cada punto de datos se le asigna una etiqueta que lo ubica en el grupo perteneciente al centroide más cercano. El centroide más cercano generalmente se determina utilizando la distancia euclidiana al cuadrado, aunque se pueden usar otras métricas de distancia, como la distancia de Manhattan, el coseno y la distancia de Jaccard, según el tipo de datos que se introducen en el algoritmo de agrupación.

En el tercer paso, el centroide se mueve al promedio de todos los puntos de datos. Luego se reasignan las clases. 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, el centroide se calcula encontrando la distancia media entre todos los puntos de datos contenidos actualmente dentro de un grupo.

Cómo elegir el valor correcto para "K"

Teniendo en cuenta que el agrupamiento de K-means es un algoritmo no supervisado y la cantidad de clases no se conoce de antemano, ¿cómo decide la cantidad adecuada de clases/el valor correcto para K?

Una técnica para seleccionar el valor K correcto se llama "la tecnica del codo”. La técnica del codo consiste en ejecutar un algoritmo de agrupamiento de K-medias para un rango de diferentes valores de K y usar una métrica de precisión, generalmente la Suma del error cuadrático, para determinar qué valores de K dan los mejores resultados. La suma del error cuadrático se determina calculando la distancia media entre el centroide de un grupo y los puntos de datos en ese grupo.

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

Agrupación de medias K de minilotes

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

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

En la agrupación en clústeres de K-Means de minilotes, los clústeres se actualizan con una combinación de valores de minilotes y una tasa de aprendizaje. La tasa de aprendizaje disminuye con las iteraciones y es inversa a la cantidad de puntos de datos colocados en un grupo específico. El efecto de reducir la tasa de aprendizaje es que se reduce el impacto de los nuevos datos y se logra la convergencia cuando, después de varias iteraciones, no hay cambios en los clústeres.

Los resultados de los estudios sobre la eficacia del agrupamiento de medias K de minilotes sugieren que puede reducir con éxito el tiempo de cálculo con una ligera compensación en la calidad del agrupamiento.

Aplicaciones de la agrupación en clústeres de K-Means

La agrupación en clústeres de K-medias se puede utilizar de forma segura en cualquier situación en la que los puntos de datos se puedan segmentar en distintos grupos/clases. Estos son algunos ejemplos de casos de uso comunes para la agrupación en clústeres de K-mean.

La agrupación en clústeres de K-means podría aplicarse 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 del documento. También podría usarse para clasificar a los usuarios como bots o no bots según los patrones de actividad, como publicaciones y comentarios. La agrupación de K-means también se puede utilizar para agrupar a las personas según los niveles de preocupación al monitorear su salud, según características como comorbilidades, edad, historial del paciente, etc.

La agrupación en clústeres de K-means 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 según los patrones de visualización y el contenido similar recomendado. La agrupación en clústeres de K-means podría usarse para tareas de detección de anomalías, destacando posibles instancias de fraude o artículos defectuosos.