K-means versus K-means en línea

K-means es un algoritmo bien conocido para el agrupamiento, pero también existe una variación en línea de dicho algoritmo (K-means en línea). ¿Cuáles son los pros y los contras de estos enfoques y cuándo se deben preferir?

Los medios k en línea (más comúnmente conocidos como medios k secuenciales ) y los medios k tradicionales son muy similares. La diferencia es que k-means en línea le permite actualizar el modelo a medida que se reciben nuevos datos.

Los medios k en línea se deben usar cuando se espera que los datos se reciban uno por uno (o tal vez en fragmentos). Esto le permite actualizar su modelo a medida que obtiene más información al respecto. El inconveniente de este método es que depende del orden en que se reciben los datos ( ref ).

La publicación original de MacQueen k-means (la primera en usar el nombre "kmeans") es un algoritmo en línea.

MacQueen, JB (1967). "Algunos métodos para la clasificación y análisis de observaciones multivariadas". Actas del 5º Simposio de Berkeley sobre Estadística matemática y probabilidad 1. University of California Press. págs. 281–297

Después de asignar cada punto, la media se actualiza gradualmente utilizando una fórmula simple de promedio ponderado (la media anterior se pondera con n, la nueva observación se pondera con 1, si la media tenía n observaciones antes).

Por lo que puedo decir, también estaba destinado a ser un solo paso sobre los datos, aunque puede repetirse trivialmente varias veces para reasignar puntos hasta la convergencia.

MacQueen generalmente toma menos iteraciones que Lloyds para converger si sus datos se barajan (¡porque actualiza la media más rápido!). En los datos ordenados, puede tener problemas. En el lado negativo, requiere más cómputo para cada objeto, por lo que cada iteración lleva un poco más de tiempo (operaciones matemáticas adicionales, obviamente).