Please enable JavaScript.
Coggle requires JavaScript to display documents.
Clustering - Coggle Diagram
Clustering
Méthodes de Clustering :
- Clustering K-means
- classification hiérarchique
- DBSCAN
la classification hierarchique :
definition :
- La classification hiérarchique est une approche de clustering qui construit une structure
arborescente de clusters, appelée dendrogramme
- La classification hiérarchique est une méthode d'organisationdes éléments en groupes basés sur leurs similitudes
- Elle créeune structure arborescente ou hiérarchique où les éléments sont regroupés en fonction de caractéristiques communes.
- Cette approche permet de représenter les relations de parenténtre les groupes, formant ainsi une structure en niveaux, oùles groupes plus larges englobent des groupes plus
spécifiques.et en plus base cette methode sur le matrice de distance
🔹À quoi sert la classification hiérarchique ?
- Ne nécessite pas de préciser le nombre de groupes
- Met en évidence les relations entre les ensembles de données
- Offre une vue d’ensemble de la structure des données (faire un visulalisation )
Types de classifications hiérarchiques :
Il existe deux types principaux de classifications hiérarchiques : la classification ascendante
(Agglomerative NESting- AGNES) et la classification descendante (DivisiveANAlysis- DIANA).
- La classification ascendante (Agglomerative) « CAH » : commence par considérer chaque élément comme un groupe individuel, puis regroupe progressivement les éléments similaires pour former des groupes plus larges.
- La classification descendante (Divisive) « CDH » : commence par considérer tous les éléments comme un seul groupe, puis divise progressivement ce groupe en sous-groupes spécifiques en fonction des caractéristiques communes
- Dans ce cours nous nous intéressons a la ClassificationAscendante Hiérarchique (CAH)
Principe CAH :
- 1.Initialisation : Chaque point est considérécomme un cluster individuel. Au départ, le
nombre de clusters est égal au nombre de points.
- 2.Calcul des distances : Calculez les distancesentre tous les clusters. Les distances peuvent êtrecalculées de différentes manières, telles que ladistance euclidienne.
- 3.Fusion des clusters : Fusionnez les deux clusters les plus proches en un seul cluster.
- 4.Mise à jour des distances : Les distances entre le nouveau cluster fusionné et les autres clusters sont recalculées, en utilisant la méthode spécifiée, comme la distance min, max, etc.
- 5.Répétition : Répétez les étapes 3 et 4 jusqu'àce qu'il ne reste qu'un seul cluster contenant tousles points, ce qui forme l'arbre hiérarchique complet.
4.3.1. Méthodes d'Agrégation
Lors de l'agglomération, des méthodes d'agrégation sont utilisées pour calculer la similarité
entre les clusters. Voici quelques méthodes courantes :
A. Simple (Single Link) : Utilisez la distance la plus courte entre les paires de points des
clusters.
B. Complète (Complete Link) : Utiliser la distance la plus grande entre les paires de points
des clusters.
C. Moyenne (Average Link) : Utiliser la moyenne des distances entre les paires de points des
clusters.
- cette methods utiliser dans etape de mise ajour distance
- Résultat de CAH : Le résultat principal de la méthode de Classification Ascendante Hiérarchique est un : Dendrogramme, qui montre les relations hiérarchiques entre les Clusters .
- Découpage d’un Dendrogramme : Une fois le Dendrogramme (Arbre) est construit : Ildoit être coupé pour montrer des Clusters (Classes)
Un Principe : Chercher la plus longue ligne verticale, qui ne peut pas etre découpée par une ligne horizontale
- Si les individus d’une même classe sont proches.
- Si les individus de deux classes différentes sont éloignées
- Mathématiquement ça se traduit comme suit :
Variabilité Intra-Classes est petite.
Variabilité Inter-Classes est grande.
Avantages et Inconvénients de la Classification Hiérarchique :
avantage :
- Ne nécessite pas de préciser le nombre de clusters à l'avance.
- Donne une vue d'ensemble des relations entre les clusters.
- Convient aux données où la structure hiérarchique est pertinente
Inconvénients :
- Peut être informatiquement coûteux pour de grandes données.
- Le choix de la méthode d'agrégation peut influencer les résultats.
- Une mauvaise compréhension du dendrogramme peut
conduir a des nterprétations erronées
Clustering K-means :
L'algorithme des k-moyennes est l'une des méthodes de clustering les plus utiliser
Son principe de base est le suivant :
- Les données sont regroupées en k clusters
- Chaque cluster possède un centroïde (centre de gravité).
- Chaque point est associé au centroïde le plus proche.
Algorithme K-means : Initialisation, Affectation, Mise à Jour des Centroide :
- Initialisation : Choisissez aléatoirement K centroïdes, généralement en utilisant des points de données du jeu de données
- Affectation : Pour chaque point de données, calculez la distance par rapport à tous les centroïdes et attribuez le point au cluster du centroïde le plus proche
- Mise à Jour des Centroïdes : Recalculez les nouveaux centroïdes en prenant la moyenne des points de données dans chaque cluster.
- Répétez les étapes 2 et 3 jusqu'à ce qu'il n'y ait plus de changement d'affectation ou jusqu'à atteindre un nombre maximal d'itérations
Choix du Nombre Optimal de Clusters :
Le choix du nombre optimal de clusters (K) est crucial pour le succès du K-means. Plusieurs
méthodes peuvent être utilisées
- Méthode du Coude : Tracez la somme des carrés des distances intra-cluster en fonction du nombre de clusters. L'endroit où cette courbe commence à s'aplatir est le nombre optimal de clusters
- Méthode de Silhouette : Calculez le coefficient de silhouette pour différents nombres de clusters et choisissez celui qui donne la valeur maximale. Le coefficient de silhouette mesure la similarité entre les points d'un cluster par rapport à d'autres clusters
Avantages et Inconvénients du K-means :
Avantages :
- Efficace pour les ensembles de données de grande taille.
- Facile à comprendre et à mettre en œuvre.
- Donne des clusters de forme convexe.
Inconvénients :
- Sensible aux valeurs aberrantes.
- Nécessité de connaître le nombre de clusters à l'avance.
- Donne des clusters de forme sphérique, ce qui peut ne pas être adapté à tous les types de données.
DBSCAN (Regroupement spatial basé sur la densité d'applications avec bruit):
definition :
- DBSCAN est un algorithme de regroupement spatial qui se base sur la densité des points de
données dans l'espace. Il peut identifier des groupes de points qui sont densément connectés, tout en étiquetant les points isolés comme du bruit
- Epsilon (ε) : C'est le rayon défini autour de chaque point. Si au moins "MinPts" points sont présents dans ce rayon (compris le point central), alors ces points sont prévus comme étant dans la même région dense.
- MinPts : C'est le nombre minimum de points requis pour former une région dense. Si un point à au moins "MinPts" voisins dans son rayon ε, il est considéré comme un point de cœur.
- SonPrincipe :
Le voisinage d’un rayon ε donnée doit contenir au moins un nombre minimum de points MinPts.
- Inspiré de l’approche naturelle humaine (Human Natural Clustering)
les terms plus importante :
- Points de cœur (Core) : Ce sont les points qui
ont au moins "MinPts" points dans leur rayon ε.
- Points frontières (Border) : Ce sont les pointsqui ne sont pas des points de cœur-mêmes,
mais qui sont situés eux dans le rayon cœur.ε d'un point de
- Points de bruit (Noise) : Ce sont les points qui
ne sont ni des points de cœur ni des points frontières
Les étapes du DBSCAN
- Choisissez un point de données non visité aléatoirement.
- Si ce point à au moins "MinPts" voisins dans son rayon
groupe (cluster). ε , et il forme un nouveau
- Ajoutez tous les points accessibles (dans le rayon ε) à ce groupe. Cela signifie que si unpoint est un point de cœur, tous les points dans son rayon ε font partie du même groupe.
- Répétez le processus pour chaque point ajouté au groupe.
- Continuez jusqu'à ce que tous les points soient visités.
4.4.2. Avantages et Inconvénients de DBSCAN
Avantages de DBSCAN :
- Capable de détecter des formes de clusters complexes et non linéaires.
- Résistant au bruit et capable de gérer les points aberrants.
- N'exige pas de préciser le nombre de clusters à l'avance.
- Indépendant de l'ordre des données.
- Peut gérer des clusters de densités variables.
Inconvénients de DBSCAN :
- Sensible aux paramètres ε et MinPts.
- Peut-être avoir du mal à détecter des clusters dans des régions de densité uniforme.
- Dépend des métriques de distance.
- Complexité algorithmique supérieure à d'autres méthodes plus simples.
- Peut-être avoir du mal à gérer les clusters de tailles très différentes.
Application de clustering :
La technologie de clustering joue un rôle très important dans de nombreux domaines car elle divise les données en clusters, chacun contenant des éléments similaires et différents des autres clusters.
- detection d 'anomaliee
- Segmentation de Marché
- Traitement de l'image
- Recherche d'Information
Definition :
- clustering et une technique de machine learning ( non supervisee ), largement utilisée dans le domaine de l'exploration de données.le clustering vise à regrouper les données similaires en groupes ou clusters sans aucune étiquette préalable.
- cette technique possible decouvrire des structure impliquees dans le donnees , et en plus releve les information cachee.
Evaluation des clusters :
L'évaluation des clusters est essentielle pour déterminer la qualité des regroupements
obtenus à partir des méthodes de clustering. Les mesures d'évaluation peuvent être classées en indices internes et externes.
- Indices Internes : Cohérence Intra-cluster, Séparation Inter-cluster
Cohérence Intra-cluster : Cette mesure évalue la similarité des points au sein d'un même
cluster. Des valeurs plus faibles indiquant que les points dans un cluster sont plus similaires les uns aux autres.
Séparation Inter-cluster : Cette mesure évalue la distance entre les clusters. Des valeurs plus
élevées indiquent que les clusters sont bien séparés.
- Indice de Silhouette,
- Méthodes de validation interne
- Visualisation
- Stabilité des clusters