Examinons rapidement différents types d'algorithmes de clustering et les circonstances dans lesquelles ils doivent être choisis.
Lorsque vous choisissez un algorithme de clustering, vous devez déterminer si l'algorithme s'adapte à votre ensemble de données. Les ensembles de données du machine learning peuvent contenir des millions d'exemples, mais les algorithmes de clustering ne sont pas tous évolutifs de manière efficace. De nombreux algorithmes de clustering fonctionnent en calculant la similarité entre toutes les paires d'exemples. Cela signifie que leur temps d'exécution augmente en tant que carré du nombre d'exemples \(n\), \(O(n^2)\) en notation de complexité. \(O(n^2)\) Les algorithmes ne sont pas pratiques lorsque le nombre d'exemples est exprimé en millions. Ce cours se concentre sur l'algorithme de k-moyennes, dont la complexité est de \(O(n)\), ce qui signifie qu'il évolue de manière linéaire avec \(n\).
Types de clustering
Il existe plusieurs approches de clustering. Pour obtenir la liste complète, consultez l'article A Complete Survey of Clustering Algorithms (Xu, D. et Tian, Y. Ann. Data. Sci. (2015) 2: 165. Chaque approche est mieux adaptée à une distribution de données particulière. Vous trouverez ci-dessous une brève discussion autour de quatre approches courantes, axées sur le clustering basé sur centroïde à l'aide de k-moyennes.
Clustering basé sur le centroïde
Le clustering basé sur centroïde organise les données en clusters non hiérarchiques, contrairement au clustering hiérarchique défini ci-dessous. Le k-moyennes est l'algorithme de clustering basé sur centroïde le plus largement utilisé. Les algorithmes centroïdes sont efficaces, mais sensibles aux conditions initiales et aux anomalies. Ce cours est axé sur les k-moyennes, car il s'agit d'un algorithme de clustering efficace, simple et efficace.
Clustering basé sur la densité
Le clustering basé sur la densité connecte les zones à forte densité d'exemples dans des clusters. Cela permet des distributions de forme arbitraire, à condition que des zones denses puissent être connectées. Ces algorithmes sont difficiles à traiter avec des données de densités variables et de dimensions élevées. De plus, ces algorithmes n'affectent pas non plus les anomalies des clusters.
Clustering basé sur la distribution
Cette approche de clustering suppose que les données sont composées de distributions, 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 montrent cette baisse de probabilité. Si vous ne connaissez pas le type de distribution de vos données, vous devez utiliser un autre algorithme.
Clustering hiérarchique
Le clustering hiérarchique crée une arborescence de clusters. Il n'est pas surprenant que le clustering hiérarchique soit bien adapté aux données hiérarchiques, telles que les taxonomies. Pour voir un exemple, consultez Comparaison de 61 génomes d'Escherichia coli séquentiels. En outre, un certain nombre de clusters peuvent être choisis en coupant l'arborescence au niveau approprié.
