Présentation de l'analyse de clustering hiérarchique
Avant d'aller de l'avant et de comprendre l'analyse de clustering hiérarchique, essayons d'abord de comprendre ce qu'est un cluster? Et qu'est-ce que l'analyse de cluster? Un cluster est une collection d'objets de données; les points de données d'un cluster sont plus similaires les uns aux autres et différents des points de données de l'autre cluster. L'analyse de cluster est essentiellement un regroupement de ces points de données dans le cluster. Le clustering est un type d'algorithme d'apprentissage automatique non supervisé, où il n'y a aucun ensemble de données étiqueté de formation. Il existe différents types d'analyse de clustering, un de ces types étant le clustering hiérarchique.
Le clustering hiérarchique aidera à créer des clusters dans un ordre / hiérarchie approprié. Exemple: l'exemple quotidien le plus courant que nous voyons est la façon dont nous classons nos fichiers et dossiers dans notre ordinateur par une hiérarchie appropriée.
Types de regroupement hiérarchique
Le regroupement hiérarchique est en outre classé en deux types, à savoir le regroupement agglomératif et le regroupement diviseur (DIANA)
Regroupement agglomératif
Dans ce cas de clustering, la décomposition hiérarchique se fait à l'aide d'une stratégie ascendante où elle commence par créer des (petits) clusters atomiques en ajoutant un objet de données à la fois, puis les fusionne pour former un gros cluster à la fin, où ce cluster remplit toutes les conditions de terminaison. Cette procédure est itérative jusqu'à ce que tous les points de données soient regroupés sous un seul grand cluster.
AGNES (AGglomerative NESting) est un type de cluster agglomératif qui combine les objets de données en un cluster basé sur la similitude. Le résultat de cet algorithme est une structure arborescente appelée Dendrogramme. Ici, il utilise les mesures de distance pour décider quels points de données doivent être combinés avec quel cluster. Fondamentalement, il construit une matrice de distance et vérifie la paire de clusters avec la plus petite distance et les combine.
La figure ci-dessus montre le regroupement d'agglomérations par rapport à la division
En fonction de la façon dont la distance entre chaque groupe est mesurée, nous pouvons avoir 3 méthodes différentes
- Liaison unique : où la distance la plus courte entre les deux points de chaque grappe est définie comme la distance entre les grappes.
- Liaison complète : dans ce cas, nous considérerons la distance la plus longue entre les points de chaque cluster comme la distance entre les clusters.
- Lien moyen: Ici, nous allons prendre la moyenne entre chaque point d'un cluster à chaque autre point de l'autre cluster.
Maintenant, discutons des forces et des faiblesses d'AGNES; cet algorithme a une complexité temporelle d'au moins O (n 2 ), donc il ne fait pas bien dans la mise à l'échelle, et un autre inconvénient majeur est que tout ce qui a été fait ne peut jamais être annulé, c'est-à-dire si nous groupons incorrectement un cluster à un stade antérieur de l'algorithme alors nous ne pourrons pas changer le résultat / le modifier. Mais cet algorithme a aussi un côté positif car il existe de nombreux petits groupes qui se forment, il peut être utile dans le processus de découverte et il produit un ordre des objets qui est très utile pour la visualisation.
Clustering diviseur (DIANA)
Diana est fondamentalement pour l'Analyse Divisive; il s'agit d'un autre type de clustering hiérarchique où, fondamentalement, il fonctionne sur le principe de l'approche descendante (inverse d'AGNES) où l'algorithme commence par former un gros cluster et divise récursivement le cluster le plus différent en deux et continue jusqu'à ce que nous '' Tous les points de données similaires appartiennent à leurs grappes respectives. Ces algorithmes de division aboutissent à des hiérarchies très précises que l'approche agglomérative mais ils sont coûteux en calcul.
La figure ci-dessus montre le processus de regroupement étape par étape
Regroupement hiérarchique multiphase
Pour améliorer la qualité des clusters générés par les techniques de clustering hiérarchiques mentionnées ci-dessus, nous intégrons nos techniques de clustering hiérarchique avec d'autres techniques de clustering; cela s'appelle un clustering multiphase. Les différents types de clustering multiphase sont les suivants:
- BIRCH (réduction et regroupement itératifs équilibrés à l'aide de hiérarchies)
- ROCK (RObust Clustering utilisant des liens)
- CAMÉLÉON
1. Réduction itérative équilibrée et regroupement à l'aide de hiérarchies
Cette méthode est principalement utilisée pour regrouper une grande quantité de données numériques en intégrant notre regroupement hiérarchique / micro à la phase initiale et le regroupement macro / partitionnement itératif à la phase ultérieure. Cette méthode aide à surmonter le problème d'évolutivité auquel nous avons été confrontés dans AGNES et l'incapacité à annuler ce qui a été fait avant l'étape. BIRCH utilise deux concepts importants dans son algorithme
une. Fonction de clustering (aide à résumer le cluster)
CF est défini comme (n- nombre de points de données dans le cluster, la somme linéaire de n points, la somme carrée de n points). Le stockage de la fonctionnalité d'un cluster de cette manière permet d'éviter de stocker des informations détaillées à ce sujet et CF est de nature additive pour différents clusters.
CF 1 + CF 2 =
b. Arborescence des fonctionnalités de clustering (aide à représenter un cluster sous forme de hiérarchie)
L'arbre CF est un arbre équilibré avec un facteur de branchement B (nombre maximal d'enfants) et un seuil T (nombre maximal de sous-grappes pouvant être stockées dans les nœuds feuilles).
L'algorithme fonctionne essentiellement en 2 phases; dans la phase 1, il analyse la base de données et construit une arborescence CF en mémoire et dans la phase 2, il utilise l'algorithme de clustering qui aide à grouper les nœuds terminaux en supprimant les valeurs aberrantes (clusters clairsemés) et regroupe le cluster avec une densité maximale. Le seul et unique inconvénient de cet algorithme est qu'il ne gère que le type de données numérique.
2. Clustering robuste à l'aide de liens
Le lien est défini comme le nombre de voisins communs entre deux objets. L'algorithme ROCK est un type d'algorithme de clustering qui utilise ce concept de lien avec l'ensemble de données catégoriel. Comme nous savons que les algorithmes de regroupement mesurés à distance ne fournissent pas de clusters de haute qualité pour l'ensemble de données catégorique, mais dans le cas de ROCK, il prend également en compte les voisinages des points de données, c'est-à-dire que si deux points de données ont le même voisinage, alors ils sont plus susceptibles d'appartenir au même groupe. L'algorithme construira un graphe clairsemé dans un premier temps en tenant compte de la matrice de similitude avec la notion de voisinage et de seuil de similitude. Dans la deuxième étape, il utilise la technique de regroupement hiérarchique aggloméré sur le graphe clairsemé.
3. Caméléon
Ce type d'algorithme de clustering hiérarchique utilise le concept de modélisation dynamique. Vous vous demandez pourquoi cela s'appelle dynamique? On l'appelle dynamique car il a la capacité de s'adapter automatiquement aux caractéristiques internes du cluster en évaluant la similitude du cluster, c'est-à-dire la qualité de la connexion des points de données au sein d'un cluster et à proximité des clusters. L'un des inconvénients du caméléon est que le coût de traitement est trop élevé (O (n 2 ) pour n objets est la complexité temporelle la plus défavorable).
Source d'image - Google
Conclusion
Dans cet article, nous avons appris ce qu'est un cluster et ce qu'est l'analyse de cluster, les différents types de techniques de clustering hiérarchique leurs avantages et leurs inconvénients. Chacune des techniques dont nous avons discuté a ses propres avantages et inconvénients.Par conséquent, avant de poursuivre avec un algorithme, nous devons comprendre nos données avec une analyse exploratoire appropriée et choisir l'algorithme avec prudence.
Articles recommandés
Ceci est un guide pour l'analyse de clustering hiérarchique. Nous discutons ici de la vue d'ensemble, du clustering agglomératif, du clustering diviseur (DIANA) et du clustering hiérarchique multiphase. Vous pouvez également consulter les articles suivants pour en savoir plus
- Regroupement hiérarchique dans R
- Algorithme de clustering
- clusters
- Méthodes de regroupement
- Clustering dans l'apprentissage automatique
- Regroupement hiérarchique | Clustering Agglomératif & Diviseur