K-means vs K-means en ligne

K-means est un algorithme bien connu pour le clustering, mais il existe également une variante en ligne de cet algorithme (K-means en ligne). Quels sont les avantages et les inconvénients de ces approches et quand devraient-elles être privilégiées?

Les k-means en ligne (plus communément appelés k-means séquentiels ) et les k-means traditionnels sont très similaires. La différence est que k-means en ligne vous permet de mettre à jour le modèle à mesure que de nouvelles données sont reçues.

Les k-means en ligne doivent être utilisés lorsque vous vous attendez à ce que les données soient reçues une par une (ou peut-être par blocs). Cela vous permet de mettre à jour votre modèle à mesure que vous obtenez plus d'informations à ce sujet. L'inconvénient de cette méthode est qu'elle dépend de l'ordre dans lequel les données sont reçues ( ref ).

La publication originale de MacQueen k-means (la première à utiliser le nom "kmeans") est un algorithme en ligne.

MacQueen, JB (1967). «Quelques méthodes pour la classification et l'analyse des observations multivariées». Actes du 5e Symposium de Berkeley sur les statistiques mathématiques et les probabilités 1. University of California Press. pp. 281-297

Après avoir attribué chaque point, la moyenne est mise à jour progressivement à l'aide d'une simple formule moyenne pondérée (l'ancienne moyenne est pondérée avec n, la nouvelle observation est pondérée avec 1, si la moyenne avait n observations auparavant).

Pour autant que je sache, il s'agissait également d'un seul passage sur les données uniquement, bien qu'il puisse être répété de manière triviale plusieurs fois pour réaffecter des points jusqu'à la convergence.

MacQueen prend généralement moins d'itérations que Lloyds pour converger si vos données sont mélangées (car elles mettent à jour la moyenne plus rapidement!). Sur les données commandées, cela peut avoir des problèmes. En revanche, cela nécessite plus de calcul pour chaque objet, donc chaque itération prend un peu plus de temps (opérations mathématiques supplémentaires, évidemment).