Neuf algorithmes de clustering pour explorer l'apprentissage automatique non supervisé

Aujourd'hui, je souhaite partager avec vous les méthodes courantes de regroupement d'apprentissage non supervisé dans l'apprentissage automatique

Dans l'apprentissage non supervisé, nos données ne portent aucune étiquette, donc ce que nous devons faire dans l'apprentissage non supervisé est de Cette série de données non étiquetées est entrée dans l'algorithme, puis l'algorithme est autorisé à trouver certaines structures implicites dans les données Grâce aux données de la figure ci-dessous, une structure qui peut être trouvée est que les points de l'ensemble de données peuvent être divisés en deux ensembles de points distincts. .(clusters), l'algorithme qui peut encercler ces clusters (cluster) est appelé algorithme de clustering.

Application de l'algorithme de clustering

• Segmentation du marché : regroupez les informations client dans la base de données en fonction du marché, afin de réaliser des ventes séparées ou une amélioration du service selon différents marchés.
• Analyse des réseaux sociaux : Trouvez un groupe proche en envoyant par email les personnes les plus fréquemment contactées et leurs contacts les plus fréquents.
• Organiser des clusters informatiques : dans les centres de données, les clusters informatiques fonctionnent souvent ensemble et peuvent être utilisés pour réorganiser les ressources, réorganiser les réseaux, optimiser les centres de données et communiquer des données.
• Comprendre la composition de la Voie Lactée : utilisez ces informations pour en apprendre davantage sur l'astronomie.

L'objectif de l'analyse groupée est de diviser les observations en groupes (« clusters ») de sorte que les différences par paires entre les observations attribuées au même cluster ont tendance à être plus petites que les différences entre les observations de différents clusters. Les algorithmes de clustering sont divisés en trois types différents : les algorithmes combinatoires, la modélisation hybride et la recherche de modèles. Plusieurs algorithmes de clustering courants sont : DBSCAN

OPTIQUE BOULEAU

• K-means
• L'algorithme K-means est l'une des méthodes de clustering les plus populaires actuellement.
• K-means a été proposé par Stuart Lloyd des Bell Labs en 1957. Il était à l'origine utilisé pour la modulation par impulsions codées. Ce n'est qu'en 1982 que l'algorithme a été annoncé au public. En 1965, Edward W. Forgy a publié le même algorithme, c'est pourquoi K-Means est parfois appelé Lloyd-Forgy.
• Les problèmes de clustering nécessitent généralement le traitement d'un ensemble d'ensembles de données non étiquetés et nécessitent un algorithme pour diviser automatiquement ces données en sous-ensembles ou clusters étroitement liés. Actuellement, l'algorithme de clustering le plus populaire et le plus utilisé est l'algorithme K-means
• Compréhension intuitive de l'algorithme K-means :

Supposons qu'il existe un ensemble de données non étiquetées (à gauche dans la figure ci-dessus), et nous Si vous souhaitez le diviser en deux clusters, exécutez maintenant l'algorithme K-means. L'opération spécifique est la suivante :

La première étape consiste à générer aléatoirement deux points (car vous souhaitez regrouper). les données en deux catégories) (à droite de l'image ci-dessus), ces deux points sont appelés centroïdes de cluster.

La deuxième étape consiste à effectuer la boucle interne de l'algorithme K-means. L'algorithme K-means est un algorithme itératif qui fait deux choses : la première est l'affectation de cluster et la seconde est le déplacement du centroïde.

La première étape de la boucle interne consiste à effectuer une affectation de cluster, c'est-à-dire de parcourir chaque échantillon, puis d'attribuer chaque point à différents centres de cluster en fonction de la distance entre chaque point et le centre du cluster (à partir de qui), qui dans ce cas consiste à parcourir l'ensemble de données et à colorer chaque point en rouge ou en bleu.

La deuxième étape de la boucle interne consiste à déplacer le centre du cluster afin que les centres du cluster rouge et bleu se déplacent vers la position moyenne des points auxquels ils appartiennent

Faites tous les points selon le nouveau centre du cluster Nouveau les affectations de cluster sont effectuées en fonction de la distance, et ce processus est répété jusqu'à ce que la position du centre du cluster ne change plus avec l'itération et que la couleur du point ne change plus. À l’heure actuelle, on peut dire que K-means a terminé l’agrégation. Cet algorithme fait un très bon travail en trouvant deux clusters dans les données

• Avantages de l'algorithme K-Means :

  Simple et facile à comprendre, vitesse de calcul rapide et adapté aux ensembles de données à grande échelle.

  Inconvénients :

  • Par exemple, la capacité de traitement des clusters non sphériques est faible, elle est facilement affectée par la sélection du centre de cluster initial et le nombre de clusters K doit être spécifié à l'avance.
  • De plus, lorsqu'il y a du bruit ou des valeurs aberrantes entre les points de données, l'algorithme K-Means peut les attribuer aux mauvais clusters.

  Clustering hiérarchique

  Le clustering hiérarchique est l'opération de regroupement d'ensembles d'échantillons selon un certain niveau. Le niveau ici fait en fait référence à la définition d'une certaine distance

  Le but ultime du clustering est de réduire le nombre de classifications, son comportement est donc similaire au processus du dendrogramme consistant à s'approcher progressivement du nœud feuille au nœud racine. Ce type de comportement est également appelé « ascendant »

  Plus communément, le clustering hiérarchique considère plusieurs clusters initialisés comme des nœuds d'arborescence. À chaque étape d'itération, deux clusters similaires sont fusionnés en un nouveau grand cluster. ce processus est répété jusqu'à ce qu'il ne reste finalement qu'un seul cluster (nœud racine).

  Les stratégies de clustering hiérarchique sont divisées en deux paradigmes de base : l'agrégation (de bas en haut) et la division (de haut en bas).

  Le contraire du clustering hiérarchique est le clustering divisif, également connu sous le nom de DIANA (Divise Analysis), dont le processus de comportement est "top-down"

  Les résultats de l'algorithme K-means dépendent du cluster choisi pour rechercher Attribution du nombre de classes et configuration de départ. En revanche, les méthodes de clustering hiérarchique ne nécessitent pas une telle spécification. Au lieu de cela, ils exigent que l'utilisateur spécifie une mesure de dissimilarité entre des groupes (disjoints) d'observations basée sur la dissimilarité par paire entre les deux ensembles d'observations. Comme leur nom l'indique, les méthodes de clustering hiérarchique produisent une représentation hiérarchique dans laquelle les clusters de chaque niveau sont créés en fusionnant les clusters du niveau inférieur suivant. Au niveau le plus bas, chaque cluster contient une observation. Au plus haut niveau, un seul cluster contient toutes les données

  Avantages :

  • La similarité des distances et des règles est facile à définir et comporte peu de restrictions 
  • Pas besoin de prédéterminer le nombre de clusters ;
  • peut découvrir la relation hiérarchique des classes
  • peut être regroupée dans d'autres formes;

  Inconvénients :

  • La complexité de calcul est trop élevée
  • Les valeurs singulières peuvent également avoir un impact important
  • L'algorithme est susceptible de se regrouper en chaînes ;

  Agglomerative Clustering

  Le contenu réécrit est le suivant : Le clustering aggloméré est un algorithme de clustering ascendant qui traite chaque point de données comme un cluster initial et le fusionne progressivement. Ils forment des clusters plus grands jusqu'à ce que la condition d'arrêt soit remplie. Dans cet algorithme, chaque point de données est initialement traité comme un cluster distinct, puis les clusters sont progressivement fusionnés jusqu'à ce que tous les points de données soient fusionnés en un seul grand cluster

  Avantages :

  • Convient à différentes formes et tailles clusters, et il n’est pas nécessaire de spécifier le nombre de clusters à l’avance.
  • L'algorithme peut également générer une hiérarchie de clustering pour une analyse et une visualisation faciles.

  Inconvénients :

  • La complexité informatique est élevée, en particulier lors du traitement d'ensembles de données à grande échelle, elle nécessite beaucoup de ressources informatiques et d'espace de stockage.
  • Cet algorithme est également sensible à la sélection des clusters initiaux, ce qui peut conduire à des résultats de clustering différents.

  Propagation d'affinité

  Contenu modifié : L'algorithme de propagation d'affinité (AP) est généralement traduit par algorithme de propagation d'affinité ou algorithme de propagation de proximité

  La propagation d'affinité est un algorithme de clustering basé sur la théorie des graphes, qui vise à identifier des "exemplaires". " (points représentatifs) et "clusters" (clusters) dans les données. Contrairement aux algorithmes de clustering traditionnels tels que K-Means, Affinity Propagation n'a pas besoin de spécifier le nombre de clusters à l'avance, ni d'initialiser de manière aléatoire les centres de cluster. Au lieu de cela, il obtient le résultat final du clustering en calculant la similarité entre les points de données.

  Avantages :

  • Il n'est pas nécessaire de spécifier le nombre de familles de cluster finales
  • Les points de données existants sont utilisés comme centre de cluster final au lieu de générer un nouveau centre de cluster.
  • Le modèle n'est pas sensible à la valeur initiale des données.
  • Il n'y a aucune exigence concernant la symétrie des données initiales de la matrice de similarité.
  • Par rapport à la méthode de clustering k-centers, l'erreur quadratique du résultat est plus petite.

  Inconvénients :

  • Cet algorithme a une grande complexité de calcul et nécessite beaucoup d'espace de stockage et de ressources informatiques
  • a de faibles capacités de traitement pour les points de bruit et les valeurs aberrantes ;

  Mean Shift Clustering

  Le clustering par décalage est un algorithme de clustering non paramétrique basé sur la densité. Son idée de base est de trouver l'emplacement avec la densité de points de données la plus élevée (appelée « maximum local » ou « pic »). , pour identifier les clusters dans les données. Le cœur de cet algorithme est d'estimer la densité locale de chaque point de données et d'utiliser les résultats de l'estimation de la densité pour calculer la direction et la distance du mouvement du point de données.

  Avantages :

  • Pas besoin pour spécifier le nombre de clusters, et il donne également de bons résultats pour les clusters aux formes complexes.
  • L'algorithme est également capable de gérer efficacement les données bruitées.

  Inconvénients :

  • La complexité informatique est élevée, en particulier lors du traitement d'ensembles de données à grande échelle, qui nécessitent une grande quantité de ressources informatiques et d'espace de stockage
  • Cet algorithme nécessite également une configuration initiale ; paramètres La sélection est relativement sensible et nécessite un ajustement et une optimisation des paramètres.

  Bisecting K-Means

  Bisecting K-Means est un algorithme de clustering hiérarchique basé sur l'algorithme K-Means. Son idée de base est de diviser tous les points de données en un cluster, puis de diviser le cluster en deux sous-clusters. , appliquez l'algorithme K-Means à chaque sous-cluster séparément et répétez ce processus jusqu'à ce que le nombre prédéterminé de clusters soit atteint.

  L'algorithme traite d'abord tous les points de données comme un cluster initial, puis applique l'algorithme K-Means au cluster, divise le cluster en deux sous-clusters et calcule la somme des erreurs quadratiques (SSE) pour chaque sous-cluster. grappe. Ensuite, le sous-groupe avec la plus grande somme d'erreurs quadratiques est sélectionné et divisé à nouveau en deux sous-groupes, et ce processus est répété jusqu'à ce que le nombre prédéterminé de groupes soit atteint.

  Avantages :

  • a une précision et une stabilité élevées, peut gérer efficacement des ensembles de données à grande échelle et n'a pas besoin de spécifier le nombre initial de clusters.
  • L'algorithme est également capable de générer une hiérarchie de clustering pour une analyse et une visualisation faciles.

  Inconvénients :

  • La complexité informatique est élevée, en particulier lors du traitement d'ensembles de données à grande échelle, elle nécessite beaucoup de ressources informatiques et d'espace de stockage.
  • De plus, cet algorithme est également sensible à la sélection des clusters initiaux, ce qui peut conduire à des résultats de clustering différents.

  DBSCAN

  L'algorithme de clustering spatial basé sur la densité DBSCAN (Density-Based Spatial Clustering of Applications with Noise) est une méthode de clustering typique avec bruit

  La méthode de densité ne dépend pas des caractéristiques de distance, mais dépend sur la densité. Par conséquent, il peut surmonter le problème selon lequel les algorithmes basés sur la distance ne peuvent trouver que des clusters « sphériques ». L'idée centrale de l'algorithme DBSCAN est la suivante : pour un point de données donné, si sa densité atteint un certain seuil, il appartient à un cluster. ; sinon, c'est considéré comme un point de bruit.

  Avantages :

  • Ce type d'algorithme peut surmonter les défauts des algorithmes basés sur la distance qui ne peuvent trouver que des clusters « circulaires » (convexes)
  • peuvent trouver des clusters de n'importe quelle forme et sont insensibles à ; données bruitées ;
  • Pas besoin de spécifier le nombre de classes de cluster 
  • Il n'y a que deux paramètres dans l'algorithme, le rayon de balayage (eps) et le nombre minimum de points inclus (min_samples).

  Inconvénients :

  • Complexité informatique, sans aucune optimisation, la complexité temporelle de l'algorithme est O(N^{2}), généralement R-tree, k-d tree, ball peuvent être utilisés ;
  • index d'arbre pour accélérer les calculs et réduire la complexité temporelle de l'algorithme à O(Nlog(N));
  • est grandement affecté par l'eps. Lorsque la densité de distribution des données dans une classe est inégale, lorsque eps est petit, le cluster avec une faible densité sera divisé en plusieurs clusters avec des propriétés similaires ; lorsque eps est grand, les clusters plus proches et plus denses seront fusionnés en un seul cluster. Dans le cas de données de grande dimension, la sélection des eps est plus difficile en raison de la malédiction de la dimensionnalité
  • repose sur la sélection de la formule de distance. En raison de la malédiction de la dimensionnalité, la métrique de distance n'est pas importante ;
  • ne convient pas à la différence de concentration de l'ensemble de données. Très grande, car il est difficile de sélectionner l'eps et la métrique.

  OPTICS

  OPTICS (Ordering Points To Identity the Clustering Structure) est un algorithme de clustering basé sur la densité qui peut déterminer automatiquement le nombre de clusters, peut également découvrir des clusters de n'importe quelle forme et gérer des données bruyantes

  L'idée principale de l'algorithme OPTICS est de calculer la distance entre un point de données donné et d'autres points pour déterminer son accessibilité en termes de densité et construire une carte de distance basée sur la densité. Ensuite, en scannant cette carte de distance, le nombre de clusters est automatiquement déterminé et chaque cluster est divisé.

  Avantages :

  • Capable de déterminer automatiquement le nombre de clusters et de gérer des clusters de n'importe quelle forme, et capable pour gérer efficacement les données bruitées.
  • L'algorithme est également capable de générer une hiérarchie de clustering pour une analyse et une visualisation faciles.

  Inconvénients :

  • La complexité informatique est élevée, en particulier lors du traitement d'ensembles de données à grande échelle, elle nécessite une grande quantité de ressources informatiques et d'espace de stockage.
  • Cet algorithme peut entraîner de mauvais résultats de clustering pour les ensembles de données présentant de grandes différences de densité.

  BIRCH

  BIRCH (Balanced Iterative Reduction and Hierarchical Clustering) est un algorithme de clustering basé sur le clustering hiérarchique qui peut gérer efficacement des ensembles de données à grande échelle et obtenir de bons résultats pour les clusters de toute forme. L'idée centrale du L'algorithme BIRCH consiste à réduire progressivement la taille des données grâce à un regroupement hiérarchique de l'ensemble de données, et enfin à obtenir la structure du cluster. L'algorithme BIRCH utilise une structure de type arbre B appelée arbre CF, qui peut rapidement insérer et supprimer des sous-clusters et peut être automatiquement équilibrée pour garantir la qualité et l'efficacité des clusters

  Avantages :

  Peut traiter rapidement des ensembles de données à grande échelle et donne de bons résultats pour les clusters de formes arbitraires.

  • Cet algorithme a également une bonne tolérance aux pannes pour les données bruyantes et les valeurs aberrantes.
  • Inconvénients :

  Pour les ensembles de données avec de grandes différences de densité, cela peut conduire à de mauvais résultats de clustering

  • L'effet sur les ensembles de données de grande dimension n'est pas non plus aussi bon que celui des autres algorithmes ; .

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!