Agrupamento hierárquico
No campo das TI , e mais precisamente no campo da análise e classificação automática de dados , a noção de agrupamento hierárquico abrange diferentes métodos de agrupamento e é categorizada em duas famílias principais: métodos 'bottom-up' e 'descendentes'.
Classificação hierárquica descendente
Os métodos chamados "de cima para baixo" partem de uma solução geral para outra mais específica. Os métodos nesta categoria começam com um único cluster contendo todos eles e são então divididos em cada estágio de acordo com um critério até que um conjunto de diferentes clusters seja obtido.
Classificação hierárquica ascendente (CAH)
Ao contrário dos chamados métodos "top-down", a classificação hierárquica ascendente é chamada "bottom-up" porque parte de uma situação em que todos os indivíduos estão sozinhos em uma classe, depois são reunidos em classes cada vez maiores. O qualificador hierárquico vem do fato de produzir uma hierarquia H , o conjunto de classes em todas as etapas do algoritmo, que verifica as seguintes propriedades:
-
Ω∈H{\ displaystyle \ Omega \ in H} : no topo da hierarquia, quando nos agrupamos para obter uma única classe, todos os indivíduos são agrupados;
-
∀ω∈Ω,{ω}∈H{\ displaystyle \ forall \ omega \ in \ Omega, \ {\ omega \} \ in H} : na base da hierarquia, todos os indivíduos estão sozinhos;
-
∀(h,h′)∈H2,h∩h′=∅{\ displaystyle \ forall (h, h ') \ in H ^ {2}, h \ cap h' = \ emptyset}ou ou : se considerarmos duas classes do agrupamento, então ou elas não têm nenhum indivíduo em comum, ou uma está incluída na outra.h⊂h′{\ displaystyle h \ subset h '}h′⊂h{\ displaystyle h '\ subset h}
É um método de classificação automática usado na análise de dados ; a partir de um conjunto de n indivíduos, seu objetivo é distribuir esses indivíduos em um determinado número de classes.
Ω{\ displaystyle \ Omega}
O método assume que temos uma medida de dissimilaridade entre os indivíduos; no caso de pontos localizados em um espaço euclidiano , podemos usar a distância como medida de dissimilaridade. A dissimilaridade entre indivíduos x e y vai ser notado .
deusseum(x,y){\ displaystyle dissim (x, y)}
Algoritmo
Princípio
Inicialmente, cada indivíduo forma uma classe, ou seja, n classes. Tentamos reduzir o número de classes para , isso é feito iterativamente. A cada etapa, duas classes são mescladas, reduzindo o número de classes. As duas classes escolhidas para serem mescladas são aquelas que mais se aproximam, ou seja, aquelas cuja dessemelhança entre elas é mínima, esse valor de dissimilaridade é denominado índice de agregação . Como os indivíduos mais próximos são reunidos primeiro, a primeira iteração tem um índice de agregação baixo, mas aumentará de iteração em iteração.
nãobvseunosses<não{\ displaystyle nb_ {classes} <n}
Medição de dissimilaridade interclasse
A dissimilaridade de duas classes, cada uma contendo um indivíduo, é definida simplesmente pela dessemelhança entre seus indivíduos.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)}
Quando as classes têm vários indivíduos, existem vários critérios que permitem calcular a dissimilaridade. Os mais simples são os seguintes:
- O salto mínimo retém as distâncias mínimas entre os indivíduos e : ;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 \ in C_ {1}, y \ in C_ {2}} (dissim (x, y))}
- O salto máxima é a dissimilaridade entre os indivíduos e o mais distante: ;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 \ in C_ {1}, y \ in C_ {2}} (dissim (x, y))}
- A ligação média é calcular a distância média entre os indivíduos e : ;VS1{\ displaystyle C_ {1}}VS2{\ displaystyle C_ {2}}deusseum(VS1,VS2)=moyenãonãoex∈VS1,y∈VS2(deusseum(x,y)){\ displaystyle dissim (C_ {1}, C_ {2}) = average_ {x \ in C_ {1}, y \ in C_ {2}} (dissim (x, y))}
- A distância de Ward visa maximizar a inércia entre classes: com e os números das duas classes, e seus respectivos centros de gravidade.deusseum(VS1,VS2)=não1∗não2não1+não2deusseum(G1,G2){\ displaystyle dissim (C_ {1}, C_ {2}) = {\ frac {n_ {1} * n_ {2}} {n_ {1} + n_ {2}}} dissim (G_ {1}, G_ {2})}não1{\ displaystyle n_ {1}}não2{\ displaystyle n_ {2}}G1{\ displaystyle G_ {1}}G2{\ displaystyle G_ {2}}
Implementação de pseudo-código
Inscrições:
- indivíduos: lista de indivíduos
- nbClasses: número de classes que, em última análise, queremos obter
Saída :
- classes: lista de classes inicialmente vazia, uma classe é vista como uma lista de indivíduos
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
Dendrograma
Um dendrograma é a representação gráfica de uma classificação hierárquica ascendente; Freqüentemente, aparece como uma árvore binária cujas folhas são os indivíduos alinhados no eixo x. Quando duas classes ou dois indivíduos se encontram com o índice de agregação , as linhas verticais são traçadas da abscissa das duas classes para a ordenada , então elas são conectadas por um segmento horizontal. A partir de um índice de agregação , podemos traçar uma linha de ordenadas que mostra uma classificação no dendrograma.
Versões mais complexas de uma árvore de classificação podem potencialmente ajudar a construir uma árvore de decisão .
τ{\ displaystyle \ tau}τ{\ displaystyle \ tau}τ{\ displaystyle \ tau}τ{\ displaystyle \ tau}
Veja também
Artigos relacionados
links externos
Bibliografia
Notas e referências
-
(in) Gabor Székely J. e Maria L. Rizzo, " Hierarchical clustering via Joint Between-Within Distances: Extending Ward's Minimum Variance Method. ” , Journal of Classification , vol. 22, n o 2Setembro de 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;">