Les ensembles de données de machine learning peuvent contenir des millions de exemples, mais tous les algorithmes de clustering n'évoluent pas efficacement. Clustering élevé les algorithmes calculent la similarité entre toutes les paires d'exemples, ce qui signifie que leur temps d'exécution augmente au carré du nombre d'exemples \(n\), représenté par \(O(n^2)\) en notation de complexité. \(O(n^2)\) les algorithmes ne sont pas pour les ensembles de données contenant des millions d'exemples.
L'algorithme k-moyennes a une valeur complexité de \(O(n)\), ce qui signifie que l'algorithme évolue de façon linéaire avec \(n\). Cet algorithme est l'objet de ce cours.
Types de clustering
Pour obtenir la liste exhaustive des différentes approches du clustering, consultez Enquête complète sur les algorithmes de clustering Xu, D. & Tian, Y. Ann. Données. Sci. (2015) 2: 165. Chaque approche est la mieux adaptée une distribution de données particulière. Ce cours présente brièvement quatre approches.
Clustering basé sur le centroïde
Le centroïde d'un cluster est moyenne arithmétique de tous les points dans cluster. Le clustering basé sur Centtroid organise les données dans un ordre non hiérarchique clusters. Les algorithmes de clustering basés sur des centroïdes sont efficaces, mais sensibles les conditions initiales et les anomalies. Parmi elles, k-moyennes est la est largement utilisée. Les utilisateurs doivent définir le nombre de centroïdes, k, et fonctionne bien avec des clusters de taille à peu près égale.
Clustering basé sur la densité
Le clustering basé sur la densité connecte des zones contiguës de densité d'exemple élevée dans clusters. Cela permet la découverte d'un nombre illimité de clusters de n'importe quelle forme. Les anomalies ne sont pas attribuées aux clusters. Ces algorithmes ont des difficultés avec des clusters de différentes densités et des données de dimensions élevées.
Clustering basé sur la distribution
Cette approche de clustering suppose que les données sont composées de distributions, comme Distributions gaussiennes : Dans Figure 3, l'algorithme basé sur la distribution regroupe les données dans trois catégories distributions. À mesure que la distance par rapport au centre de distribution augmente, la probabilité qu'un point appartienne à la distribution diminue. Spectacles de groupes qui diminuent la probabilité. Lorsque vous n'êtes pas à l'aise à l'idée de supposer sous-jacente des données, vous devez utiliser un autre algorithme.
Clustering hiérarchique
Le clustering hiérarchique crée une arborescence de clusters. Le clustering hiérarchique, sans surprise, est bien adapté aux données hiérarchiques, telles que les taxonomies. Voir Comparaison de 61 génomes d'Escherichia coli séquencés par Oksana Lukjancenko, Trudy Wassenaar & Prenons l'exemple de Dave Ussery. Vous pouvez choisir autant de clusters que vous le souhaitez en coupant l'arborescence au niveau approprié.
