Exécuter l'algorithme de clustering

En machine learning, il arrive que l'on trouve des ensembles de données pouvant contenir des millions d'exemples. Les algorithmes de ML doivent pouvoir s'adapter efficacement à ces ensembles de données volumineux. Toutefois, de nombreux algorithmes de clustering ne sont pas évolutifs, car ils doivent calculer la similarité entre toutes les paires de points. Cela signifie que leur temps d'exécution augmente au carré, car il est exprimé en \(O(n^2)\). Par exemple, les algorithmes de clustering hiérarchique agrégé ou divisif analysent toutes les paires de points et ont des complexités \(O(n^2 log(n))\) et \(O(n^2)\), respectivement.

Ce cours est consacré aux k-moyennes, car il évolue en \(O(nk)\), où \(k\)est le nombre de clusters. En k-moyennes, les points sont regroupés en \(k\) clusters en réduisant la distance entre les points et le centroïde de leur cluster (comme illustré dans la Figure 1 ci-dessous). Le centroïde d'un cluster est la moyenne de tous les points du cluster.

Comme vous le voyez, k-moyennes trouve des clusters à peu près circulaires. Conceptuellement, cela signifie que k-moyennes traite efficacement les données comme étant composées d'un certain nombre de distributions plus ou moins circulaires, et tente de trouver des clusters correspondant à ces distributions. En réalité, les données contiennent des anomalies et peuvent ne pas convenir à un tel modèle.

Avant d'exécuter les k-moyennes, vous devez choisir le nombre de clusters, \(k\). Dans un premier temps, partez du principe de \(k\). Plus tard, nous verrons comment affiner ce nombre.

Algorithme de clustering en k-moyennes

Pour regrouper les données \(k\) en clusters, la technique k-moyennes est la suivante:

Figure 1: k-moyennes au moment de l'initialisation.

Étape 1

L'algorithme choisit de façon aléatoire un centroïde pour chaque cluster. Dans notre exemple, nous choisissons \(k\) 3, et l'algorithme choisit donc aléatoirement 3 centroïdes.

Figure 2: Clusters initiaux

Étape 2

L'algorithme attribue chaque point au centroïde le plus proche pour obtenir \(k\) les clusters initiaux.

Figure 3: Calcul des centroïdes

Étape 3

Pour chaque cluster, l'algorithme recalcule le centroïde en prenant la moyenne de tous les points du cluster. Les modifications apportées aux centroïdes sont représentées dans la figure 3 par des flèches. Étant donné que les centroïdes changent, l'algorithme réaffecte les points au centroïde le plus proche. La figure 4 montre les nouveaux clusters après la réattribution.

Figure 4: Clusters après réattribution

Étape 4

L'algorithme répète le calcul des centroïdes et l'attribution des points jusqu'à ce que les points cessent de changer de cluster. Lorsque vous mettez en cluster des ensembles de données volumineux, vous arrêtez l'algorithme avant d'atteindre la convergence, en utilisant d'autres critères.

Vous n'avez pas besoin de comprendre les mathématiques de k-moyennes pour ce cours. Toutefois, si vous êtes curieux, consultez la démonstration mathématique ci-dessous.

Cliquez sur l'icône Plus pour afficher la démonstration mathématique.

À l'aide d'exemples \(n\) attribués à des clusters, \(k\) réduisez la somme des distances des exemples par rapport à leurs centroïdes. Où :

• \(A_{nk} = 1\) lorsque le \(n\)e exemple est attribué au \(k\)e cluster et 0 dans le cas contraire
• \(\theta_k\) est le centroïde du cluster \(k\)

Nous voulons minimiser l'expression suivante : $$\min_{A,\theta} \sum_{n=1}^N \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n ||^2$$ objet : $$A_{nk} \in \{0,1\} \forall n,k$$ et $$\sum^{K}_{k=1}A_{nk}=1 \forall n$$ Pour réduire l'expression par rapport aux centroïdes du cluster \(\theta_k\), prenez la dérivée par rapport à \(\theta_k\) et e. $$f(\theta) = \sum^{N}_{n=1} \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n||^2$$ $$\frac{\partial f}{\partial \theta_k} = 2 \sum_{n=1}^{N} A_{nk}(\theta_k - x_n) = 0$$ $$\implies \sum_{n=1}^{N} A_{nk}\theta_{k} = \sum^N_{n=1} A_{nk}x_{n}$$ $$\theta_k \sum_{n=1}^{N} A_{nk} = \sum_{n=1}^{N} A_{nk} x_n$$ $$\theta_k = \frac{\sum^N_{n=1} A_{nk} x_n}{\sum^N_{n=1} A_{nk}}$$ Le numérateur est la somme de toutes les distances des centroïdes de l'exemple dans le cluster. Le dénominateur est le nombre d'exemples dans le cluster. Ainsi,\(\theta_k\) correspond au nombre moyen de distances des centroïdes du cluster. C'est ce que nous avons pu constater.

Étant donné que les positions du centroïde sont initialement choisies au hasard, les k-moyennes peuvent renvoyer des résultats très différents lors d'exécutions successives. Pour résoudre ce problème, exécutez des k-moyennes plusieurs fois et choisissez le résultat avec les meilleures métriques. (Nous évoquerons les métriques de qualité dans la suite de ce cours.) Vous aurez besoin d'une version avancée de k-moyennes pour choisir de meilleures positions de centroïdes initiales.

Test : avec ce simulateur de k-moyennes de Stanford, essayez d'exécuter plusieurs k-moyennes pour voir si vous obtenez des résultats différents.

Termes clés :

• centroïde