Clustering k-means à échelle web

Nous présentons deux modifications de l'algorithme de clustering k-means populaire pour répondre aux exigences extrêmes en matière de latence, de scalabilité et de parcimonie rencontrées dans les applications web destinées aux utilisateurs. Tout d'abord, nous proposons l'utilisation de l'optimisation par mini-lots pour le clustering k-means. Cela réduit le coût de calcul d'ordres de grandeur par rapport à l'algorithme classique par lots tout en offrant des solutions significativement meilleures que la descente de gradient stochastique en ligne. Ensuite, nous atteignons la parcimonie avec la descente de gradient projeté et fournissons une projection rapide ε-précise sur la boule L1. Le code source est disponible gratuitement : http://code.google.com/p/sofia-ml