Algorithmes de clustering

Les ensembles de données de machine learning peuvent contenir des millions d'exemples, mais tous les algorithmes de clustering ne sont pas évolutifs de manière efficace. De nombreux algorithmes de clustering calculent la similarité entre toutes les paires d'exemples, ce qui signifie que leur temps d'exécution augmente comme le carré du nombre d'exemples $n$, désigné par $O(n^2)$ dans la notation de complexité.Les algorithmes $O(n^2)$ ne sont pas pratiques pour les ensembles de données contenant des millions d'exemples.

L'algorithme k-moyennes a une complexité de $O(n)$, ce qui signifie que l'algorithme évolue de manière linéaire avec $n$. C'est l'algorithme qui sera au centre de ce cours.

Types de clustering

Pour obtenir une liste exhaustive des différentes approches de clustering, consultez A Comprehensive Survey of Clustering Algorithms (Une étude approfondie des algorithmes de clustering) par Xu, D. et Tian, Y. Ann. Données. Sci. (2015) 2: 165. Chaque approche est la plus adaptée à une distribution de données particulière. Ce cours présente brièvement quatre approches courantes.

Clustering basé sur centroïde

Le centroïde d'un cluster correspond à la moyenne arithmétique de tous les points du cluster. Le clustering basé sur le centroïde organise les données en clusters non hiérarchiques. Les algorithmes de clustering basés sur le centroïde sont efficaces, mais sensibles aux conditions initiales et aux valeurs aberrantes. Parmi ces méthodes, k-moyennes est la plus utilisée. Les utilisateurs doivent définir le nombre de centroides, k, et cette méthode fonctionne bien avec les clusters de taille à peu près égale.

Figure 1: Exemple de clustering basé sur centroïde.

Clustering basé sur la densité

Le clustering basé sur la densité relie les zones contiguës à forte densité d'exemples en clusters. Cela permet de découvrir un nombre illimité de clusters de toutes formes. Les valeurs aberrantes ne sont pas attribuées à des clusters. Ces algorithmes ont du mal à gérer les clusters de densité différente et les données à dimensions élevées.

Figure 2: Exemple de clustering basé sur la densité.

Clustering basé sur la distribution

Cette approche de clustering suppose que les données sont composées de distributions probabilistes, telles que les distributions gaussiennes. Dans la figure 3, l'algorithme basé sur la distribution regroupe les données en trois distributions gaussiennes. À mesure que la distance par rapport au centre de la distribution augmente, la probabilité qu'un point appartienne à la distribution diminue. Les bandes indiquent cette diminution de probabilité. Lorsque vous ne vous sentez pas à l'aise à supposer une distribution sous-jacente particulière des données, vous devez utiliser un algorithme différent.

Figure 3: Exemple de clustering basé sur la distribution.

Clustering hiérarchique

Le clustering hiérarchique crée un arbre de clusters. Sans surprise, le clustering hiérarchique est bien adapté aux données hiérarchiques, telles que les taxonomies. Pour en savoir plus, consultez l'article Comparison of 61 Sequenced Escherichia coli Genomes (Comparaison de 61 génomes Escherichia coli séquencés) d'Oksana Lukjancenko, Trudy Wassenaar et Dave Ussery. Vous pouvez choisir n'importe quel nombre de clusters en coupant l'arborescence au bon niveau.

Figure 4: Exemple d'arborescence hiérarchique regroupant des animaux.

Termes clés

• Algorithme k-moyennes
• centroïde
• Distributions gaussiennes