• 15 hours
  • Hard

Free online content available in this course.

course.header.alt.is_video

course.header.alt.is_certifying

Got it!

Last updated on 2/1/19

Partitionnez vos données avec l’algorithme du k-means

Log in or subscribe for free to enjoy all this course has to offer!

Partitionnez vos données avec l'algorithme du k-means

Supposons maintenant que, plutôt que d'explorer tous les nombres de clusters possibles de 1 (contenant tous les points) à n (contenant chacun un seul point), nous nous fixons à l'avance le nombre K de clusters. En pratique, on pourra ainsi se contenter d'explorer une fourchette de valeurs de K, qui sera déterminée en fonction des besoins de nos applications. Dans le cas de la segmentation de marché, on commencera en général par s'intéresser à une segmentation grossière, avec peu de clusters (dans ce cas, des groupes de clients aux profils similaires), quitte à la raffiner ultérieurement. Si l'on analyse de larges banques de données de photographies, que l'on espère pouvoir regrouper par sujets, le nombre de clusters voulus peut être bien plus élevés.

Nous avons établi dans les chapitres précédents que de minimiser la variance intra-clusters$\(V = \sum_{k} \frac{1}{|C_k|} \sum_{{x} \in \mathcal{C}_k} ||x - \mu_k||^2\)$ permet de définir des clusters homogènes. Étant donné K, nous allons donc chercher à répartir les points $\(x_1, x_2, \dots, x_n\)$ en K groupes $\(C_1, C_2, \dots, C_K\)$ de telle sorte que $\(\sum_{k=1}^K \frac{1}{|C_k|} \sum_{{x} \in \mathcal{C}_k} ||x - (\frac{1}{|C_k|} \sum_{{x} \in \mathcal{C}_k} x)||^2\)$ soit minimale. C'est le problème que la méthode dite du k-means cherche à résoudre.

Algorithme de Lloyd

Il n'est pas possible de résoudre ce problème de manière exacte. Nous sommes donc obligés d'utiliser une heuristique.

Dans le chapitre précédent, nous avons utilisé le clustering de Ward ; cependant, il a tendance à être coûteux en temps de calcul. Le clustering de Ward  partitionne les données de manière hiérarchique, mais nous avons dit ici nous intéresser à une unique partition en K clusters.

L'algorithme de Lloyd procède de la façon suivante. On commence par choisir aléatoirement K centroïdes parmi nos observations. On associe ensuite chaque point au centroïde dont il est le plus proche, formant ainsi K clusters. On peut maintenant recalculer le centroïde de chaque cluster (son barycentre), et recommencer l'opération jusqu'à ce que l'algorithme converge.

Il s'agit d'une stratégie gloutonne. L'algorithme converge en général très rapidement, mais peut tomber dans un minimum local. Pour cette raison, il peut être utile de le relancer plusieurs fois et d'évaluer la variance intra-cluster pour chacune de ces répétitions.

Dansscikit-learn, le k-means est implémenté danscluster.KMeans. Par défaut, l'algorithme est répété 10 fois (paramètren_init).

Forme des clusters du k-means

Dans le résultat du k-means, les points appartenant à un cluster C_k sont plus proche du centroïde $\(\mu_k \)$ que de n'importe quel autre centroïde. Cela implique que l'algorithme du k-means partitionne l'espace selon une tessellation de Voronoi. En particulier, cela implique aussi que les clusters obtenus sont convexes. On ne peut donc pas, avec l'algorithme du k-means, obtenir de cluster en forme de croissant de lune, d'anneau, etc.

Tesselation de Voronoi en 5 cellules. Chaque disque représente un centroïde
Tesselation de Voronoi en 5 cellules. Chaque disque représente un centroïde

Dansscikit-learn, le kernel k-means est implémenté danscluster.KernelKMeans

k-means++

Un des inconvénients du k-means est que l'initialisation se fait aléatoirement. L'algorithme n'est donc pas déterministe, et on peut obtenir des résultats différents en le faisant tourner plusieurs fois. Et certains de ces résultats peuvent être très mauvais, c'est-à-dire très éloignés de la solution optimale que l'on obtiendrait si l'on pouvait résoudre exactement notre problème de minimisation de variance intra-cluster !

On peut voir ça sur un exemple simple :

Initialisé avec les deux étoiles, le k-means (K=2) va créer deux clusters horizontaux.
Initialisé avec les deux étoiles, le k-means (K=2) va créer deux clusters horizontaux.

Si on applique le k-means, initialisé avec les 2 étoiles oranges, aux 4 points bleus, les deux clusters initiaux seront {(0, 0), (2, 0)} et {(0, 0.2), (2, 0.2)} et ne bougeront pas. Cependant, la variance intra-cluster du clustering {(0, 0), (0, 0.2)}, {(2, 0), (2, 0.2)} est bien plus faible et ce serait donc un résultat plus désirable.

Pour éviter ce problème, on peut utiliser la variante k-means++ du k-means. Dans cette variante, au lieu d'initialiser les clusters au hasard, on va créer les centroïdes initiaux de sorte à les « éparpiller » le plus possible dans les données. Plus précisément, on choisit un premier centroïde aléatoirement parmi les points du jeu de données. Puis on calcule la distance D entre ce centroïde et chacun des autres points.

On choisit ensuite un deuxième centroïde de telle sorte qu'un point x a une probabilité d'être choisi proportionnelle à $\(D(x)^2\)$ , et donc d'autant plus grande que x est loin du premier centroïde. On répète cette opération (calcul de la distance D au k-ième centroïde puis utilisation de cette distance pour sélectioner le (k+1)-ème) jusqu'à avoir K centroïdes. On applique ensuite le k-means avec cette initialisation.

Dansscikit-learn, l'initialisation par défaut d'une instance decluster.KMeansse fait avec kmeans++ (paramètreinit).

Résumé

  • L'algorithme du k-means permet de rechercher efficacement une partition des données dont la variance intra-cluster est minimale

  • Cependant il s'agit d'une approche heuristique qui peut retourner un minimum local plutôt que global

  • L'initialisation kmeans++ ainsi que des répétitions multiples permettent de mitiger ce problème

Example of certificate of achievement
Example of certificate of achievement