Gruparea ierarhică
În domeniul IT și mai precis în domeniul analizei și al clasificării automate a datelor , noțiunea de grupare ierarhică acoperă diferite metode de grupare și este clasificată în două familii principale: metode „de jos în sus” și „descendenți”.
Clasificare ierarhică descendentă
Așa-numitele metode „de sus în jos” pornesc de la o soluție generală la una mai specifică. Metodele din această categorie încep cu un singur cluster care le conține pe toate și sunt apoi împărțite în fiecare etapă conform unui criteriu până când se obține un set de clustere diferite.
Clasificare ierarhică ascendentă (CAH)
Spre deosebire de așa-numitele metode „de sus în jos”, clasificarea ierarhică ascendentă se numește „de jos în sus” deoarece începe de la o situație în care toți indivizii sunt singuri într-o clasă, apoi sunt adunați în clase din ce în ce mai mari. Calificatorul ierarhic provine din faptul că produce o ierarhie H , setul de clase la toate etapele algoritmului, care verifică următoarele proprietăți:
-
Ω∈H{\ displaystyle \ Omega \ în H}
: în partea de sus a ierarhiei, când ne grupăm astfel încât să obținem o singură clasă, toți indivizii sunt grupați;
-
∀ω∈Ω,{ω}∈H{\ displaystyle \ forall \ omega \ in \ Omega, \ {\ omega \} \ in H}
: în partea de jos a ierarhiei, toți indivizii sunt singuri;
-
∀(h,h′)∈H2,h∩h′=∅{\ displaystyle \ forall (h, h ') \ în H ^ {2}, h \ cap h' = \ emptyset}
sau sau : dacă luăm în considerare două clase ale grupării, atunci fie ele nu au niciun individ în comun, fie una este inclusă în cealaltă.h⊂h′{\ displaystyle h \ subset h '}
h′⊂h{\ displaystyle h '\ subset h}![h '\ subset h](https://wikimedia.org/api/rest_v1/media/math/render/svg/b3881f89d580894390dedafb7480ff8fbe8bfaad)
Este o metodă de clasificare automată utilizată în analiza datelor ; dintr-un set de n indivizi, scopul său este de a distribui acești indivizi într-un anumit număr de clase.
Ω{\ displaystyle \ Omega}![\Omega](https://wikimedia.org/api/rest_v1/media/math/render/svg/24b0d5ca6f381068d756f6337c08e0af9d1eeb6f)
Metoda presupune că avem o măsură de diferență între indivizi; în cazul punctelor situate într-un spațiu euclidian , putem folosi distanța ca măsură a diferenței. Se va remarca diferența dintre indivizii x și y .
deusseum(X,y){\ displaystyle dissim (x, y)}![disim (x, y)](https://wikimedia.org/api/rest_v1/media/math/render/svg/133950f0ccc8b3ffe7e8350180b42468f854ea52)
Algoritm
Principiu
Inițial, fiecare individ formează o clasă, adică n clase. Încercăm să reducem numărul de clase la , acest lucru se face iterativ. La fiecare pas, două clase sunt combinate, reducând astfel numărul de clase. Cele două clase alese pentru a fi combinate sunt cele care sunt cele mai apropiate, cu alte cuvinte, cele a căror diferență între ele este minimă, această valoare de diferențiere se numește indicele de agregare . Pe măsură ce sunt adunați mai întâi cei mai apropiați indivizi, prima iterație are un indice de agregare scăzut, dar va crește de la iterație la iterație.
nubvs.llasses<nu{\ displaystyle nb_ {classes} <n}![nb_ {clase} <n](https://wikimedia.org/api/rest_v1/media/math/render/svg/c22b2e95d19282b4fd1063561c45dc69f8b5de66)
Măsurarea diferențierii între clase
Disimilaritatea a două clase conținând fiecare un individ este definită pur și simplu de diferența dintre indivizii săi.VS1={X},VS2={y}{\ displaystyle C_ {1} = \ {x \}, C_ {2} = \ {y \}}
deusseum(VS1,VS2)=deusseum(X,y){\ displaystyle dissim (C_ {1}, C_ {2}) = dissim (x, y)}
Când clasele au mai mulți indivizi, există mai multe criterii care fac posibilă calcularea diferenței. Cele mai simple sunt următoarele:
- Saltul minimă păstrează distanțele minime între indivizi și : ;VS1{\ displaystyle C_ {1}}
VS2{\ displaystyle C_ {2}}
deusseum(VS1,VS2)=minX∈VS1,y∈VS2(deusseum(X,y)){\ displaystyle dissim (C_ {1}, C_ {2}) = \ min _ {x \ în C_ {1}, y \ în C_ {2}} (dissim (x, y))}![dissim (C_1, C_2) = \ min_ {x \ în C_1, y \ în C_2} (dissim (x, y))](https://wikimedia.org/api/rest_v1/media/math/render/svg/e2512317296c60dc821bd5219d7cdf640168b631)
- Maximă Saltul este disimilaritatea între indivizi și cel mai îndepărtat: ;VS1{\ displaystyle C_ {1}}
VS2{\ displaystyle C_ {2}}
deusseum(VS1,VS2)=maxX∈VS1,y∈VS2(deusseum(X,y)){\ displaystyle dissim (C_ {1}, C_ {2}) = \ max _ {x \ în C_ {1}, y \ în C_ {2}} (dissim (x, y))}![dissim (C_1, C_2) = \ max_ {x \ în C_1, y \ în C_2} (dissim (x, y))](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce6833c995b466a95b7c5ce8cfcf3e6e1622f302)
- Link - ul mediu este de a calcula distanța medie dintre indivizi și : ;VS1{\ displaystyle C_ {1}}
VS2{\ displaystyle C_ {2}}
deusseum(VS1,VS2)=moyenunueX∈VS1,y∈VS2(deusseum(X,y)){\ displaystyle dissim (C_ {1}, C_ {2}) = average_ {x \ in C_ {1}, y \ in C_ {2}} (dissim (x, y))}![dissim (C_1, C_2) = average_ {x \ in C_1, y \ in C_2} (dissim (x, y))](https://wikimedia.org/api/rest_v1/media/math/render/svg/08ff76846e5b47bf4540288357b1a68a40efd218)
- Distanța Ward urmărește să maximizeze inerția dintre clase: cu și numerele celor două clase și centrele lor de greutate respective.deusseum(VS1,VS2)=nu1∗nu2nu1+nu2deusseum(G1,G2){\ displaystyle dissim (C_ {1}, C_ {2}) = {\ frac {n_ {1} * n_ {2}} {n_ {1} + n_ {2}}} dissim (G_ {1}, G_ {2})}
nu1{\ displaystyle n_ {1}}
nu2{\ displaystyle n_ {2}}
G1{\ displaystyle G_ {1}}
G2{\ displaystyle G_ {2}}![G_2](https://wikimedia.org/api/rest_v1/media/math/render/svg/645011b0c6933a02f5f7d84624f78220d747427e)
Implementarea pseudo-codului
Intrări:
- indivizi: lista indivizilor
- nbClasses: numărul de clase pe care dorim să le obținem în cele din urmă
Ieșire :
- clase: lista claselor inițial goale, o clasă este văzută ca o listă de indivizi
Pour i=1 à individus.longueur Faire
classes.ajouter(nouvelle classe(individu[i]));
Fin Pour
Tant Que classes.longueur > nbClasses Faire
// Calcul des dissimilarités entre classes dans une matrice triangulaire supérieure
matDissim = nouvelle matrice(classes.longueur,classes.longueur);
Pour i=1 à classes.longueur Faire
Pour j=i+1 à classes.longueur Faire
matDissim[i][j] = dissim(classes[i],classes[j]);
Fin Pour
Fin Pour
// Recherche du minimum des dissimilarités
Soit (i,j) tel que matDissim[i][j] = min(matDissim[k][l]) avec 1<=k<=classes.longueur et k+1<=l<=classes.longueur;
// Fusion de classes[i] et classes[j]
Pour tout element dans classes[j] Faire
classes[i].ajouter(element);
Fin pour
supprimer(classes[j]);
Fin Tant Que
Dendrogramă
O dendrogramă este reprezentarea grafică a unei clasificări ierarhice ascendente; Este adesea prezentat ca un copac binar ale cărui frunze sunt indivizii aliniați pe axa x. Când două clase sau doi indivizi se întâlnesc cu indicele de agregare , linii verticale sunt trasate din abscisa celor două clase la ordonată , apoi sunt conectate printr-un segment orizontal. Dintr-un indice de agregare , putem trage o linie de ordonate care arată o clasificare pe dendrogramă.
Versiunile mai complexe ale arborelui de clasificare pot ajuta la construirea unui arboresc de decizie .
τ{\ displaystyle \ tau}
τ{\ displaystyle \ tau}
τ{\ displaystyle \ tau}
τ{\ displaystyle \ tau}![\ tau](https://wikimedia.org/api/rest_v1/media/math/render/svg/38a7dcde9730ef0853809fefc18d88771f95206c)
Vezi și tu
Articole similare
linkuri externe
Bibliografie
Note și referințe
-
(în) Gabor Székely J. și Maria L. Rizzo, „ Hierarchical clustering via Joint Between-Within Distances: Extending's Minimum Variance Method. ” , Jurnalul de clasificare , vol. 22, n o 2Septembrie 2005, p. 151-183 ( DOI 10.1007 / s00357-005-0012-9 )
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">