K-means vs. K-means en línea

Question

K-means es un algoritmo bien conocido para la agrupación, pero también hay una variación en línea de dicho algoritmo (K-medios en línea). ¿Cuáles son los pros y los contras de estos enfoques, y cuando debe preferirse cada uno?

Answer 1

k-medias en línea (más comúnmente conocido como secuenciales k-medias ) yk tradicional -medios son muy similares. La diferencia es que en línea de k-medias le permite actualizar el modelo como se reciben nuevos datos.

línea de k-medias se debe utilizar cuando se espera que los datos que se recibirá uno por uno (o tal vez en trozos). Esto le permite actualizar su modelo a medida que más información al respecto. El inconveniente de este método es que es dependiente de la orden en el que se reciben los datos ( ref ).

Answer 2

El MacQueen original de kmeans publicación (el primero en utilizar las "kmeans" nombre) es un algoritmo en línea.

MacQueen, J. B. (1967). "Algunos métodos de clasificación y análisis de las observaciones multivariantes". Actas del 5º Simposio de Berkeley en Estadística Matemática y Probabilidad 1. University of California Press. pp. 281-297

Después de asignar cada punto, la media se forma incremental actualiza usando un simple ponderado promedio fórmula (edad media se pondera con n, la nueva observación se pondera con 1, si la media tenía n observaciones antes).

Por lo que yo puedo decir, que también estaba destinado a ser una sola pasada sobre sólo los datos, aunque puede ser trivialmente repitió varias veces a puntos Reasignar hasta la convergencia.

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