Explorez vos données avec des algorithmes non supervisés

15 heures
Difficile

Licence

Ce cours est visible gratuitement en ligne.

course.header.alt.is_video

course.header.alt.is_certifying

J'ai tout compris !

Mis à jour le 08/01/2024

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

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 fixions à 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 sujet, le nombre de clusters voulus peut être bien plus élevé.

Nous avons établi dans les chapitres précédents que minimiser la variance intracluster $$$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 intracluster pour chacune de ces répétitions.

Dans scikit-learn , le k-means est implémenté dans cluster.KMeans . Par défaut, l'algorithme est répété 10 fois (paramètre n_init ).

Forme des clusters du k-means

Dans le résultat du k-means, les points appartenant à un cluster C_k sont plus proches 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 Voronoï. En particulier, cela implique aussi que les clusters obtenus soient 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 Voronoï en 5 cellules. Chaque disque représente un centroïde

On peut pallier cette limitation grâce au k-means à noyau, ou kernel k-means, en anglais. N'hésitez pas à vous rafraîchir la mémoire sur les noyaux dans le chapitre 2 de la partie 2 de ce cours !

Supposons que l'on envoie les données dans un espace de redescription $$$\mathcal{H}$$$ grâce à une application $$$\phi$$$ . On peut appliquer l'algorithme du k-means aux données transformées $$$\{\phi(x_1), \dots, \phi(x_n)\} $$$ en ne faisant apparaître les $$$\phi(x_i) $$$ que dans des produits scalaires $$$\langle \phi(x_i), \phi(x_j) \rangle$$$ , que l'on peut donc remplacer par le noyau correspondant à $$$\phi$$$ , $$$\kappa(x_i, x_j)$$$ . Par définition, $$$\kappa $$$ associe $$$\langle \phi(u) \phi(v) \rangle$$$ à (u, v).

En effet, à chaque itération du k-means, nous avons besoin de connaître la distance entre tous les points du jeu de données et les K centroïdes, c'est-à-dire pour tout x et pour tout $$$k=1, \dots, K,$$$ $$$||x - \frac{1}{|C_k|} \sum_{u \in C_k} u||$$$ . Si l'on envoie les points x dans un espace de redescription $$$\mathcal{H} $$$ grâce à une application $$$\phi,$$$ et que l'on applique l'algorithme du k-means dans cet espace de redescription, on aura donc besoin d'être capable de calculer, pour tout x et pour tout k, la quantité :

$$$||\phi(x) - \frac{1}{|C_k|} \sum_{u \in C_k} \phi(u)||$$$

= $$$\langle \phi(x)$$$ - $$$\frac{1}{|C_k|} \sum_{u \in C_k} \phi(u), \phi(x)$$$ - $$$\frac{1}{|C_k|} \sum_{u \in C_k} \phi(u) \rangle_{\mathcal{H}}$$$

= $$$\langle \phi(x), \phi(x) \rangle_{\mathcal{H}} - 2 \frac{1}{|C_k|} \sum_{u \in C_k} \langle \phi(u), \phi(x) \rangle_{\mathcal{H}} + \frac{1}{|C_k|^2} \sum_{u \in C_k} \langle \phi(u), \phi(u) \rangle$$$

Cette quantité peut donc s'écrire :

$$$\kappa(x, x)$$$ - 2 $$$\frac{1}{|C_k|} \sum_{u \in C_k} \kappa(x, u)$$$ +

$$$\frac{1}{|C_k|^2} \sum_{u \in C_k} \kappa(u, u)$$$

Le kernel trick s'applique donc.

Dans scikit-learn , le kernel k-means est implémenté dans cluster.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 intracluster !

On peut voir ça sur un exemple simple :

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 intracluster 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.

Dans scikit-learn , l'initialisation par défaut d'une instance de cluster.KMeansse fait avec kmeans++ (paramètre init ).

Résumé

L'algorithme du k-means permet de rechercher efficacement une partition des données dont la variance intracluster 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.