K-means++

Dans l'exploration de données, k -means++^[1],[2] est un algorithme permettant de choisir les valeurs initiales (ou « graines ») pour l'algorithme de clustering k -means. Il a été proposé en 2007 par David Arthur et Sergei Vassilvitskii, comme un algorithme d'approximation pour le problème NP-hard k -means — un moyen d'éviter les clusterings parfois médiocres trouvés par l'algorithme k -means standard. Elle est similaire à la première des trois méthodes d'ensemencement proposées, dans un travail indépendant, en 2006 ^[3] par Rafail Ostrovsky, Yuval Rabani, Leonard Schulman et Chaitanya Swamy. (La distribution de la première graine est différente.)

Le problème k -means consiste à trouver des centres de cluster qui minimisent la variance intra-classe, c'est-à-dire la somme des carrés des distances entre chaque point de données groupé et son centre de cluster (le centre qui lui est le plus proche). Bien que trouver une solution exacte au problème des k -moyennes pour une entrée arbitraire soit NP-difficile^[4], l'approche standard pour trouver une solution approximative (souvent appelée algorithme de Lloyd ou algorithme des k -moyennes) est largement utilisée et trouve fréquemment des solutions raisonnables rapidement.

Cependant, l'algorithme k -means présente au moins deux défauts théoriques majeurs :

• Premièrement, il a été démontré que le temps d’exécution du pire des cas de l’algorithme est super-polynomial dans la taille de l’entrée^[5].
• Deuxièmement, l’approximation trouvée peut être arbitrairement mauvaise par rapport à la fonction objective par rapport au clustering optimal.

L'algorithme k -means++ aborde le deuxième de ces obstacles en spécifiant une procédure pour initialiser les centres de cluster avant de procéder aux itérations d'optimisation k -means standard. Avec l'initialisation k -means++, l'algorithme est assuré de trouver une solution qui est O(log k ) compétitive par rapport à la solution k -means optimale.

Pour illustrer le potentiel de l'algorithme k -means à fonctionner de manière arbitrairement médiocre par rapport à la fonction objective de minimisation de la somme des distances au carré des points de cluster par rapport au centroïde de leurs clusters attribués, considérons l'exemple de quatre points dans ${\displaystyle \mathbb {R} ^{2}}$ qui forment un rectangle aligné sur l'axe dont la largeur est supérieure à sa hauteur.

Si ${\displaystyle k=2}$ et les deux centres de cluster initiaux se situent aux points médians des segments de ligne supérieur et inférieur du rectangle formé par les quatre points de données, l'algorithme k -means converge immédiatement, sans déplacer ces centres de cluster. Par conséquent, les deux points de données inférieurs sont regroupés et les deux points de données formant le haut du rectangle sont regroupés — un regroupement sous-optimal car la largeur du rectangle est supérieure à sa hauteur.

Envisagez maintenant d’étendre le rectangle dans une direction horizontale jusqu’à la largeur souhaitée. L'algorithme k -means standard continuera à regrouper les points de manière sous-optimale, et en augmentant la distance horizontale entre les deux points de données dans chaque cluster, nous pouvons faire en sorte que l'algorithme fonctionne de manière arbitrairement médiocre par rapport à la fonction objective k -means.

L'intuition derrière cette approche est que la répartition des k centres de cluster initiaux est une bonne chose : le premier centre de cluster est choisi uniformément au hasard parmi les points de données qui sont regroupés, après quoi chaque centre de cluster suivant est choisi parmi les points de données restants avec une probabilité proportionnelle à sa distance au carré du centre de cluster existant le plus proche du point.

L'algorithme exact est le suivant :

1. Choisissez un centre uniformément au hasard parmi les points de données.
2. Pour chaque point de données x non encore choisi, calculez D( x ), la distance entre x et le centre le plus proche qui a déjà été choisi.
3. Choisissez un nouveau point de données au hasard comme nouveau centre, en utilisant une distribution de probabilité pondérée où un point x est choisi avec une probabilité proportionnelle à D( x ) ².
4. Répétez les étapes 2 et 3 jusqu’à ce que les centres k aient été choisis.
5. Maintenant que les centres initiaux ont été choisis, procédez à l’aide du clustering k -means standard.

Cette méthode d’ensemencement permet d’améliorer considérablement l’erreur finale des k -moyennes. Bien que la sélection initiale dans l'algorithme prenne plus de temps, la partie k -means elle-même converge très rapidement après cet amorçage et ainsi l'algorithme réduit réellement le temps de calcul. Les auteurs ont testé leur méthode avec des ensembles de données réels et synthétiques et ont obtenu des améliorations de vitesse généralement de 2 fois et, pour certains ensembles de données, des améliorations d'erreur proches de 1 000 fois. Dans ces simulations, la nouvelle méthode a presque toujours obtenu des résultats au moins aussi bons que la méthode k -means classique, tant en termes de vitesse que d'erreur.

De plus, les auteurs calculent un rapport d’approximation pour leur algorithme. L'algorithme k -means++ garantit un rapport d'approximation O(log k ) dans l'espérance (sur le caractère aléatoire de l'algorithme), où ${\displaystyle k}$ est le nombre de clusters utilisés. Ceci est en contraste avec k -means vanille, qui peut générer des clusterings arbitrairement pires que l'optimum^[6]. Une généralisation des performances de k-means++ par rapport à toute distance arbitraire est fournie dans^[7].

L’approche k -means++ a été appliquée depuis sa proposition initiale. Dans une étude de Shindler, qui inclut de nombreux types d'algorithmes de clustering, la méthode est censée surmonter avec succès certains des problèmes associés à d'autres méthodes de définition des centres de clusters initiaux pour le clustering k -means. Lee et al. rapportent une application de k -means++ pour créer un groupe géographique de photographies en fonction des informations de latitude et de longitude attachées aux photos. Une application à la diversification financière est rapportée par Howard et Johansen. D'autres supports de soutien à la méthode et des discussions en cours sont également disponibles en ligne. Étant donné que l'initialisation k-means++ nécessite k passes sur les données, elle ne s'adapte pas très bien aux grands ensembles de données. Bahman Bahmani et al. ont proposé une variante évolutive de k-means++ appelée k-means|| qui fournit les mêmes garanties théoriques tout en étant hautement évolutive.

• Accord.NET (en) contient des implémentations C# pour k -means, k -means++ et k -modes.
• ALGLIB (en) contient des implémentations C++ et C# parallélisées pour k -means et k -means++.
• Apache Commons Math contient k-means++
• Le framework d'exploration de données ELKI contient plusieurs variantes de k-means, y compris k-means++ pour l'amorçage.
• MATLAB dispose d'une implémentation K-Means qui utilise k-means++ par défaut pour l'amorçage.
• OpenCV contient une implémentation C++ et Python K-means (avec une initialisation de graine k-means facultative).
• Orange inclut le widget d'interface utilisateur k-means++ et la prise en charge de l'API
• R inclut k-means, et le package « flexclust » peut faire k-means++
• scikit-learn dispose d'une implémentation K-Means qui utilise k-means++ par défaut.
• Weka contient des clusterings k-means (avec k-means++ en option) et x-means.

• Portail des bases de données