Raggruppamento gerarchico
Nel campo IT , e più precisamente nel campo dell'analisi e della classificazione automatica dei dati , la nozione di raggruppamento gerarchico copre diversi metodi di clustering ed è classificata in due famiglie principali: metodi "dal basso verso l'alto" e "discendenti".
Classificazione gerarchica discendente
I cosiddetti metodi "top-down" partono da una soluzione generale a una più specifica. I metodi di questa categoria iniziano con un singolo cluster che li contiene tutti e vengono poi suddivisi in ciascuna fase secondo un criterio fino ad ottenere un insieme di cluster diversi.
Classificazione gerarchica ascendente (CAH)
A differenza dei metodi cosiddetti "top-down", la classificazione gerarchica ascendente è detta "bottom-up" perché parte da una situazione in cui tutti gli individui sono soli in una classe, quindi vengono raccolti in classi sempre più grandi. Il qualificatore gerarchico deriva dal fatto che produce una gerarchia H , l'insieme di classi in tutte le fasi dell'algoritmo, che verifica le seguenti proprietà:
-
Ω∈H{\ displaystyle \ Omega \ in H} : al vertice della gerarchia, quando si raggruppa in modo da ottenere un'unica classe, vengono raggruppati tutti gli individui;
-
∀ω∈Ω,{ω}∈H{\ displaystyle \ forall \ omega \ in \ Omega, \ {\ omega \} \ in H} : in fondo alla gerarchia, tutti gli individui sono soli;
-
∀(h,h′)∈H2,h∩h′=∅{\ displaystyle \ forall (h, h ') \ in H ^ {2}, h \ cap h' = \ emptyset}oppure oppure : se consideriamo due classi del raggruppamento, allora o non hanno alcun individuo in comune, oppure una è inclusa nell'altra.h⊂h′{\ displaystyle h \ subset h '}h′⊂h{\ displaystyle h '\ subset h}
È un metodo di classificazione automatico utilizzato nell'analisi dei dati ; da un insieme di n individui, il suo obiettivo è distribuire questi individui in un certo numero di classi.
Ω{\ displaystyle \ Omega}
Il metodo presuppone che abbiamo una misura della dissomiglianza tra gli individui; nel caso di punti situati in uno spazio euclideo , possiamo usare la distanza come misura della dissomiglianza. Si noterà la dissomiglianza tra gli individui x e y .
dioSSiom(X,y){\ displaystyle dissim (x, y)}
Algoritmo
Principio
Inizialmente, ogni individuo forma una classe, cioè n classi. Cerchiamo di ridurre il numero di classi a , questo viene fatto iterativamente. Ad ogni passaggio, due classi vengono unite, riducendo così il numero di classi. Le due classi scelte per essere unite sono quelle più vicine, in altre parole, quelle la cui dissomiglianza tra loro è minima, questo valore di dissomiglianza è chiamato indice di aggregazione . Quando gli individui più vicini vengono raccolti per primi, la prima iterazione ha un indice di aggregazione basso, ma crescerà da iterazione a iterazione.
nonbvslaSSeS<non{\ displaystyle nb_ {classes} <n}
Misurazione della dissomiglianza tra le classi
La dissomiglianza di due classi contenenti ciascuna un individuo è definita semplicemente dalla dissomiglianza tra i suoi individui.VS1={X},VS2={y}{\ displaystyle C_ {1} = \ {x \}, C_ {2} = \ {y \}}dioSSiom(VS1,VS2)=dioSSiom(X,y){\ displaystyle dissim (C_ {1}, C_ {2}) = dissim (x, y)}
Quando le classi hanno più individui, ci sono più criteri che consentono di calcolare la dissomiglianza. I più semplici sono i seguenti:
- Il salto minima mantiene le distanze minime tra gli individui e : ;VS1{\ displaystyle C_ {1}}VS2{\ displaystyle C_ {2}}dioSSiom(VS1,VS2)=minX∈VS1,y∈VS2(dioSSiom(X,y)){\ displaystyle dissim (C_ {1}, C_ {2}) = \ min _ {x \ in C_ {1}, y \ in C_ {2}} (dissim (x, y))}
- Il salto massimo è la diversità tra gli individui e il più lontano: ;VS1{\ displaystyle C_ {1}}VS2{\ displaystyle C_ {2}}dioSSiom(VS1,VS2)=maxX∈VS1,y∈VS2(dioSSiom(X,y)){\ displaystyle dissim (C_ {1}, C_ {2}) = \ max _ {x \ in C_ {1}, y \ in C_ {2}} (dissim (x, y))}
- Il legame media è quello di calcolare la distanza media tra gli individui e : ;VS1{\ displaystyle C_ {1}}VS2{\ displaystyle C_ {2}}dioSSiom(VS1,VS2)=moyenonnoneX∈VS1,y∈VS2(dioSSiom(X,y)){\ displaystyle dissim (C_ {1}, C_ {2}) = average_ {x \ in C_ {1}, y \ in C_ {2}} (dissim (x, y))}
- La distanza Ward mira a massimizzare l'inerzia tra le classi: con e i numeri delle due classi e dei rispettivi centri di gravità.dioSSiom(VS1,VS2)=non1∗non2non1+non2dioSSiom(G1,G2){\ displaystyle dissim (C_ {1}, C_ {2}) = {\ frac {n_ {1} * n_ {2}} {n_ {1} + n_ {2}}} dissim (G_ {1}, G_ {2})}non1{\ displaystyle n_ {1}}non2{\ displaystyle n_ {2}}G1{\ displaystyle G_ {1}}G2{\ displaystyle G_ {2}}
Implementazione di pseudo-codice
Inserimenti:
- individui: elenco di individui
- nbClasses: numero di classi che alla fine vogliamo ottenere
Uscita :
- classi: elenco di classi inizialmente vuoto, una classe è vista come un elenco di individui
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
Dendrogramma
Un dendrogramma è la rappresentazione grafica di una classificazione gerarchica ascendente; Viene spesso presentato come un albero binario le cui foglie sono gli individui allineati sull'asse x. Quando due classi o due individui si incontrano con l'indice di aggregazione , le linee verticali vengono tracciate dall'ascissa delle due classi all'ordinata , quindi sono collegate da un segmento orizzontale. Da un indice di aggregazione , possiamo tracciare una linea di ordinate che mostra una classificazione sul dendrogramma.
Versioni più complesse dell'albero di classificazione possono potenzialmente aiutare a costruire un albero decisionale .
τ{\ displaystyle \ tau}τ{\ displaystyle \ tau}τ{\ displaystyle \ tau}τ{\ displaystyle \ tau}
Vedi anche
Articoli Correlati
link esterno
Bibliografia
Note e riferimenti
-
(in) Gabor Székely J. e Maria L. Rizzo, " Raggruppamento gerarchico tramite distanze inter-interne congiunte: estensione del metodo di varianza minima di Ward. " , Journal of Classification , vol. 22, n o 2Settembre 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;">