La classification ascendante hiérarchique

add

\bullet Présentation:

La classification ascendante hiérarchique, régulièrement mentionnée sous l’acronyme CAH, fait partie des trois familles d’outil d’analyse non supervisée les plus répandues avec les méthodes de partitionnement et les méthodes à noyaux de densité.

La classification ascendante hiérarchique est particulièrement efficace dans la construction de clusters/groupes d’observations d’une matrice de données à P \geq 1 variable(s) continue(s), \mathbf{X} = (X ^1, \cdots, X ^P), à partir de la structure même des données sans apport informatif d’une variable auxiliaire.

Le clustering, ou l’action de créer des groupes d’observations, ou clusters dans un argo-anglicisme bien souvent utilisé pour simplifier le propos, s’exécute via un algorithme ascendant en définissant deux paramètres,

– une fonction de distance (également appelée fonction de proximité): distance euclidienne, de Manhattan, , de Minkowski, etc

– et une méthode spécifique de regroupement: distance maximale, méthode de Ward, méthode de Mc Quitty, etc

, à partir desquelles la typologie des observations de \mathbf{X} sera construite au travers de partitions emboîtées d’hétérogénéités croissantes d’où sa propriété hiérarchique. Il existe un très grand nombre de méthodes de regroupement et chacune d’elles dispose d’avantages et d’inconvénients.

A noter que la classification ascendante hiérarchique ne requiert aucune condition de validité, cependant l’application de méthodes de transformation des données peut avoir un effet plus ou moins accentué sur les clusters conçus en fin d’algorithme et sont même parfois recommandées avant application.

Enfin, le choix du nombre de clusters se fait en fonction de deux approches:

– soit nous définissons au préalable un nombre de groupes maximales à composer,

– soit en fonction de quatre outils décisionnels que nous présenterons: le R ^2, le pseudo-T ^2, le semi-partiel-R ^2 et le Cubic Clustering Criterion.

Le choix entre ces deux méthodes est purement subjectif et principalement lié au contexte car aucune n’est à considérer comme la meilleure.

\bullet L’algorithme de classification ascendante hiérarchique:

La CAH regroupe un ensemble de techniques construites sur le même principe: le regroupement successif des points par ordre de proximité croissante. L’Algorithme commun est le suivant:

Étape initiale: Considérer autant de classes qu’il y a d’observations et regrouper les deux observations qui sont les plus proches selon la fonction de distance choisie.

Étapes récursives suivantes: Tant qu’il reste une observation isolée (sans groupe) ou au moins deux groupes d’observations à fusionner, pour l’itération t,

—- Calculer la matrice de distance entre les différents groupes d’observations et les observations isolées, selon la fonction de distance choisie et lorsque nous sommes en présence de groupe d’observations, selon la méthode de regroupement choisie.

—- La distance minimale d_t au sein de la matrice de distance calculée à l’étape t indique le regroupement à faire. Il pourra alors s’agir aussi bien de la fusion de deux groupes d’observations comme d’un groupe observations et d’une observation isolée ou deux observations sans groupe. La distance d_t retenue sert enfin à construire l’arbre de classification ascendante hiérarchique.

—- Fin de l’itération t, nous passons à l’itération t+1 en reprenant les deux précédentes étapes.

Étape finale: A ce stade nous sommes dans la situation où il nous reste soit deux groupes d’observations, soit un groupe d’observations et une observation isolée, nous les regroupons pour conclure l’algorithme. Une fois toutes les observations classées, nous disposons de l’arbre de classification ascendante hiérarchique présentant la structure du clustering et permettant de déterminer à quel niveau couper l’arbre pour visualiser les différents classifications possibles en fonction des différentes classes emboîtées.

Bruno Falissard, dans son ouvrage (voir bibliographie), propose l’exemple suivant afin d’illustrer l’algorithme présenté ci-dessus. Soit les cinq observations que nous cherchons à regrouper selon une fonction de proximité triviale.

add1

Appliquons l’algorithme itératif de classification hiérarchique ascendante. Nous commençons donc en supposons que chaque observation est une classe, nous remarquons que la distance la plus petite entre les 4 \times 3 = 12 paires d’observations possibles est celle entre l’observation 2 et 3 (d_1).

add2

Nous les rassemblons donc et formons ainsi le premier regroupement de notre arbre de classification. Maintenant nous mettons à jour la matrice des distances en recalculant les différentes distances et en considérant le regroupement des observations 2,3 comme une entité unique (notée 6).

add3

Nous constatons que, cette fois-ci, la distance minimale est celle entre les observations 4 et 5 (d_2). Évidemment, cette distance est supérieure à d_1, d’où une paire de branche plus haute. Nous passons à l’itération suivante en mettant à jour l’information avec le cluster regroupant les observations 4, 5 (noté 7) à l’instar du cluster noté 6.

add4

La distance minimale est désormais celle entre le cluster noté 6 et l’observation isolée 1. Nous mettons à jour l’arbre de classification avec ce nouveau regroupement (noté 8) et procédons à l’étape finale.

add5.png

L’algorithme a fini de tourner et l’arbre construit permet de retrouver les différents groupes construits.

\bullet Les fonctions distances:

Comme expliquer en introduction, il faut définir au préalable deux paramètres afin d’utiliser une CAH. Nous présentons le premier: la fonction de distance à utiliser pour le calcul de la distance entre deux observations décrites au travers de P variables. Six principales fonctions existent, les voici:

– La distance euclidienne: d(X_{i_1}, X_{i_2}) = \sqrt{\sum_{j = 1} ^P (X_{i_1} ^j - X_{i_2} ^j) ^2}

– La distance maximale: d(X_{i_1}, X_{i_2}) = max_{j \in [1, P]} | X_{i_1} ^j - X_{i_2} ^j |

– La distance de Manhattan: d(X_{i_1}, X_{i_2}) = \sum_{j = 1} ^P | X_{i_1} ^j - X_{i_2} ^j |

– La distance de Canberra: d(X_{i_1}, X_{i_2}) = \sum_{j = 1} ^P \frac{| X_{i_1} ^j - X_{i_2} ^j |}{| X_{i_1} ^j | + | X_{i_2} ^j |}

– La distance de Minkowski (pour q, paramètre à fixer), qui est entre autre une généralisation de la distance euclidienne: d(X_{i_1}, X_{i_2}) = (\sum_{j = 1} ^P (X_{i_1} ^j - X_{i_2} ^j) ^q) ^{\frac{1}{q}}

\bullet Les méthodes de regroupement:

Nous abordons maintenant le second paramètre à déterminer: la méthode de regroupement. Plusieurs méthodes existent pour déterminer la proximité entre deux clusters ou un cluster et une observation isolée, en voici les principales.

La distance moyenne

Origine: Robert Reuven Sokal et Charles Duncan Michener, 1958. Nous pouvons la trouver sous l’appellation de « CAH du saut moyen » ou encore « average linkage ».

L’idée:

La distance moyenne se détermine en calculant toutes les distances possibles entre les observations respectives aux deux groupes étudiés et en déterminant la moyenne de ces distances. Les deux groupes dont la distance moyenne est la plus petite sont ceux qui seront fusionnés pour l’itération en cours.

add

Propriétés: La distance moyenne tend à créer des clusters de faible variance identique. De plus, elle est moins sensible au bruit.

La distance médiane

Origine: John C. Gower, 1961. Nous pouvons la trouver sous l’appellation « median method ».

L’idée:

La distance des médianes se détermine en calculant toutes les distances possibles entre les observations respectives aux deux groupes étudiés et en déterminant la valeur médiane de ces distances. Les deux groupes dont la distance médiane est la plus petite sont ceux qui seront fusionnés pour l’itération en cours.

add

Propriétés: La distance des médianes présentent l’avantage d’être particulièrement robuste aux outliers s’ils sont trop nombreux. Pour le reste, elle demeure l’une des moins populaires et très rarement utilisée lors d’une CAH.

La distance minimale

Origine: K. Florek, J. Lukaszewicz, J. Perkal, S. Zubrzycki, Louis L. McQuitty et P. H. A. Sneath, 1951-1957. Nous pouvons la trouver sous l’appellation de « CAH du saut minimum » ou encore « single linkage ».

L’idée:

La distance minimale consiste à calculer l’ensemble des distances possibles entre les observations respectives aux deux groupes considérés et à en retenir la plus petite. Les deux groupes dont la distance minimale est la plus petite sont ceux qui seront fusionnés pour l’itération en cours.

add1

Propriétés: La distance minimale est plus robuste que son homologue la distance maximale mais présente néanmoins une faiblesse (voir une force si c’est l’objectif visé). Soit la situation de deux classes éloignées et qui peuvent être reliées par un faible nombre d’observations proches les unes des autres et faisant la jonction entre les deux groupes. Dés lors, le regroupement basé sur la distance minimale ne considérera pas trois clusters (les deux groupes séparés et le lot d’observations entre eux) mais un unique cluster.

La distance maximale

Origine: Thorvald Julius Sørensen, 1948. Nous pouvons la trouver sous l’appellation de « CAH du saut maximum » ou critère du diamètre ou encore « complete linkage ».

L’idée:

La distance maximale consiste à calculer l’ensemble des distances possibles entre les observations respectives aux deux groupes considérés et à en retenir la plus grande.  Les deux groupes dont la distance maximale est la plus petite sont ceux qui seront fusionnés pour l’itération en cours.

add1

Propriétés: La distance maximale produit généralement des clusters de diamètres à peu près égaux, cependant elle est fortement influencée par la présence d’outliers. Logique par construction, étant donné le fait qu’elle se base sur la distance maximale entre deux clusters. A l’instar de la distance médiane, la distance maximale est très peu utilisée.

La distance des barycentres

Origine: Robert Reuven Sokal et Charles Duncan Michener, 1958. Nous pouvons la trouver sous l’appellation « centroid method ».

L’idée:

La distance des barycentres se détermine en calculant les barycentres des différents groupes à partir de la moyenne des coordonnées des observations respectives à ces clusters. Les deux groupes dont la distance des barycentres est la plus petite sont ceux qui seront fusionnés pour l’itération en cours.

add1

Propriétés: La distance des barycentres demeure plus robuste aux outliers que les autres méthodes, cependant elle est réputée comme étant moins performante que la méthode de Ward ou encore la distance moyenne.

La distance de Ward

Origine: Joe H. Ward, 1963. Nous pouvons la trouver sous l’appellation de méthode de Ward ou encore « Ward’s minimum-variance method ».

L’idée:

La distance de Ward se base sur la distance au carré entre les barycentres des deux groupes considérés et pondérés par leur effectif respectif. En notant Cl_{k_1}, Cl_{k_2} les deux clusters considérés et de barycentres respectifs G_{k_1}, G_{k_2}, la formule d’usage est alors,

D_{Cl_{k_1},Cl_{k_2}} = \frac{|| G_{k_1} - G_{k_2} || ^2}{\frac{1}{n_{k_1}} + \frac{1}{n_{k_2}}}

Les deux groupes dont la distance de Ward est la plus petite sont ceux qui seront fusionnés pour l’itération en cours.

add1

Propriétés: La distance de Ward est la méthode la plus souvent utilisée car elle a été conçue dans un objectif de maximisation de l’inertie inter-classe et de minimisation de l’inertie intra-classe. Elle aura tendance à produire des clusters de même taille et reste très sensible aux outliers. De plus, contrairement à la distance minimale, elle est très peu efficace face aux classes « étirées ».

La méthode du maximum de vraisemblance

Origine: Warren S. Sarle et M. J. Symons, 1983. Nous pouvons la trouver sous l’appellation de méthode EML (pour Expected Maximun-Likelihood).

L’idée:

La méthode procède au regroupement d’observations par maximisation de la vraisemblance à chaque itération sous les hypothèses de mélange de lois multi-normales, d’égalité des matrices de variances-covariances et de probabilités d’échantillonnage inégales. Le choix du regroupement est donc déterminé au travers de la formule:

D_{Cl_{k_1}, Cl_{k_2}} = n \cdot P \cdot log[1 + \frac{\mathbf{\Sigma_{k_1 \cup k_2}} - \mathbf{\Sigma_{k_1}} - \mathbf{\Sigma_{k_2}}}{\sum_{k = 1} ^K \mathbf{\Sigma_k}}] - \lambda [n_{k_1 \cup k_2} log (n_{k_1 \cup k_2}) - n_{k_1} log (n_{k_1}) - n_{k_2} log (n_{k_2})]

Où,

n désigne le nombre d’observations,

\mathbf{\Sigma_{k_1 \cup k_2}} la matrice de variances-covariances issues du regroupement des clusters Cl_{k_1}, Cl_{k_2},

n_{k_1 \cup k_2} l’effectif obtenu lorsque que nous regroupons les clusters Cl_{k_1}, Cl_{k_2},

– le paramètre \lambda, fixé à 2 par défaut, représente la pénalité à appliquer aux matrices de variances-covariances afin de s’affranchir d’éventuel biais dû aux outliers.

Les deux groupes dont la distance calculées à partir de la méthode EML est la plus petite sont ceux qui seront fusionnés pour l’itération en cours.

add1

Propriétés: La méthode EML est similaire à la méthode de Ward, réputée comme l’une des plus performantes méthodes de classification. Cependant, elle a tendance à créer des groupes de tailles disproportionnées.

La méthode du \beta-flexible

Origine: Godfrey N. Lance et William Thomas Williams, 1967.

L’idée:

La méthode du \beta-flexible se base directement sur la maximisation de l’inertie inter-classe et la minimisation de celle intra-classe au travers de la formule suivante:

D_{Cl_{k_1}, Cl_{k_2} \cup Cl_{k_3}} = (D_{Cl_{k_1}, Cl_{k_2}} + D_{Cl_{k_1}, Cl_{k_3}}) \frac{1 - \beta}{2} + \beta \cdot D_{Cl_{k_2}, Cl_{k_3}}

En général, le paramètre \beta est fixé à -0.25 par défaut. Les distances D_{Cl_{k_1}, Cl_{k_2}} et D_{Cl_{k_1}, Cl_{k_3}} correspondent à celles entre le groupe à fusionner aux deux autres groupes (maximisation de l’inertie inter-groupe) et la distance D_{Cl_{k_2}, Cl_{k_3}} est celle entre les deux groupes déjà construits (minimisation de l’inertie intra-groupe).

Les deux groupes dont la distance calculée à partir de la méthode du \beta-flexible est la plus petite sont ceux qui seront fusionnés pour l’itération en cours.

add1

Propriétés: La méthode du \beta-flexible est optimale dans une approche visant à obtenir les meilleurs critères de classification possibles. Néanmoins, il nécessite un choix sur le paramètre \beta dont l’incidence sur la classification finale reste majeure. Le problème est de taille puisqu’il n’y a pas vraiment d’approche pour déterminer le choix idéal de ce paramètre.

La distance de McQuitty

Origine: Louis L. Mc Quitty, 1966. 

L’idée: La distance de Mc Quitty consiste à calculer la moyenne des moyennes des moyennes des ….. des moyennes des distances entre les observations des deux groupes à fusionner.

Par exemple, soit le cluster regroupant les observations 1,4 au niveau t_1 de la classification puis l’observation 2 avec ce groupe au niveau t_2. Au niveau t_3, La distance entre une observation 5 et le groupe des observations 1, 2, 4 sera la distance entre 5 et 2 additionnée à la somme divisée par deux des distances entre 5 et 1 et 5 et 4, le tout divisé à son tour par deux.

La formule itérative et générale est alors,

D_{Cl_{k_1}, Cl_{k_2} \cup Cl_{k_3}} = \frac{D_{Cl_{k_1}, Cl_{k_2}} + D_{Cl_{k_1}, Cl_{k_3}}}{2}

add.png

Propriétés:  La distance de Mc Quitty se base sur une approche combinatoire des groupes plutôt que sur les observations isolées dans ces groupes.

\bullet Critères décisionnels pour le choix du nombre de clusters optimal:
 
Les algorithmes de classification ne fournissent pas directement le nombre de cluster optimisant la classification. Il faut pour cela s’appuyer sur le contexte ainsi que sur quelques indicateurs que nous présentons ici.
  
En définissant K_t le nombre de groupes à l’itération t du processus de classification, nous avons,
 
– Le R _t ^2, de formule,
 
R_t ^2 = \frac{\mbox{Inertie inter-classe}}{\mbox{Inertie totale}} = \frac{\sum_{i = 1} ^n || X_i - \overline{X} ||  ^2 - \sum_{k = 1} ^{K_t} \sum_{i_k \in Cl_k} || X_{i_k} - \overline{X_{k}} || ^2}{\sum_{i = 1} ^n || X_i - \overline{X} ||  ^2}
  
La formule induit que les observations qui seront encore non regroupées auront un poids nul sur le calcul du R_t ^2 puisque leur coordonnées sont confondues avec leur barycentre. Ainsi, pour le cas initial où une observation équivaut à un groupe, le R ^2 vaudra 1.
 
Le R_t ^2 mesure à quel proportion l’inertie inter-classe est maximal et (par contraposé, puisque égale à 1 - R_t ^2,à quel point l’inertie intra-classe est minimale). Plus le R_t ^2 est proche de 1 et plus cela implique que la classification est bonne. Généralement, le choix se porte sur la cassure de la courbe que nous pouvons tracer à partir des R_t ^2, t \in [1, t_{max}] (cf graphe extrait de l’ouvrage de Stéphane Tufféry et présent en bibliographie).
add
– Le semi-partiel-R_t ^2, de formule,
  
semi-partiel-R_t ^2 = R_{t - 1} ^2 - R_t ^2
  
A noter que lors de l’itération initiale (t = 1), R_1 = 1.
 
Le semi-partiel-R_t ^2 caractérise l’évolution de la chute du R ^2 au cours des différentes itérations de la procédure de classification et notamment la perte d’inertie observéeà chaque regroupement de deux clusters. En général, le choix se porte sur le nombre de classes dont le semi-partiel-R_{t-1} ^2 est faible et le semi-partiel-R_t ^2 est fort, ce qui est symbolisé par un « pic » suivi d’un « creux » lorsque nous traçons la courbe pour t \in [1, t_{max} (cf graphe extrait de l’ouvrage de Stéphane Tufféry et présent en bibliographie).
add
  
– Le pseudo-F_t, de formule,

pseudo-F_t = \frac{\frac{R_t ^2}{K_t - 1}}{\frac{1 - R_t ^2}{n - K_t}}

Le pseudo-F_t mesure le rapport entre l’inertie inter-classe et l’inertie intra-classe. En effet,

\frac{\frac{R_t ^2}{K_t - 1}}{\frac{1 - R_t ^2}{n - K_t}} = \frac{R_t ^2}{1 - R_t ^2} \cdot \frac{n - K_t}{K_t - 1} = \frac{\frac{\mbox{Inertie inter-classe}}{\mbox{Inertie totale}}}{\frac{\mbox{Inertie intra-classe}}{\mbox{Inertie totale}}} \cdot \delta = \frac{\mbox{Inertie inter-classe}}{\mbox{Inertie intra-classe}} \cdot \delta

Plus le rapport est grand et plus cela nous conforte dans le fait que l’inertie inter-classe est maximale et l’inertie intra-classe est minimale et donc que nous sommes en présence d’une bonne classification.

– Le pseudo-T_t ^2 pour le regroupement des clusters Cl_{k_1}, Cl_{k_2}, de formule,

pseudo-T_t ^2 = \frac{\sum_{i \in Cl_{k_1} \cup Cl_{k_2}} || X_i - \overline{X_{Cl_{Cl_1 \cup Cl_2}}} || ^2 - \sum_{i \in Cl_{k_1}} || X_i - \overline{X_{Cl_{k_1}}} || ^2 - \sum_{i \in Cl_{k_2}} || X_i - \overline{X_{Cl_{k_2}}} || ^2}{\frac{\sum_{i \in Cl_{k_1}} || X_i - \overline{X_{Cl_{k_1}}} || ^2 + \sum_{i \in Cl_{k_2}} || X_i - \overline{X_{Cl_{k_2}}} || ^2}{n_{k_1} + n_{k_2} - 2}}

Le pseudo-T_t ^2 ne peut être calculé que pour le regroupement de deux groupes d’observations ou d’un groupe et d’une observation isolée. Il consiste à mesurer l’évolution du barycentre avant et après regroupement des deux classes. En effet, en notant M_k = \sum_{i \in Cl_k} || X_i - \overline{X_{Cl_k}} || ^2, nous avons,

\frac{M_{k_1 \cup k_2} - M_{k_1} - M_{k_2}}{\frac{M_{k_1} + M_{k_2}}{n_{k_1} + n_{k_2} - 2}} = (n_{k_1} + n_{k_2} - 1) \cdot (\frac{M_{k_1 \cup k_2}}{M_{k_1} + M_{k_2}} - 1)

Le pseudo-T_t ^2 vaut 0 si le rapport est égal à 1 soit que les barycentres de Cl_{Cl_{k_1} \cup Cl_{k_2}}, Cl_{k_1}, Cl_{k_2} sont confondus et donc que le regroupement ne permet pas de maximiser l’inertie inter-groupe.

A contratio, plus le pseudo-T_t ^2 est grand et plus la classification est de bonne qualité.

– Le Cubic Criterion Clustering, noté CCC_t:

CCC_t = K_t \cdot log [\frac{1 - E[R_t ^2]}{1 - R_t ^2}] \cdot \frac{\sqrt{\frac{n p ^*}{2}}}{(0.001 + E[R_t ^2]) ^{1.2}}

Pour expliquer les calculs de E[R_t ^2] et p ^*, il convient de détailler directement tout l’algorithme de calcul à appliquer et mélangeant les deux objets. D’abord, il faut savoir que E[R_t ^2] est, par définition, la valeur théorique du R_t ^2 dans le cas d’une distribution uniforme, et sans regroupement, des observations. Nous devons dans un premier temps, déterminer le vecteur\lambda des valeurs propres de la matrice de taille P \times P,

\mathbf{T} = \frac{\mathbf{X ^T} \cdot \mathbf{X}}{n - 1}

Nous devons ensuite calculer le vecteur des pondérations,

c = (\frac{\prod_{j = 1} ^P \sqrt{\lambda_j}}{K_t}) ^{\frac{1}{P}}

, que nous appliquons aux valeurs propres \lambda. Nous obtenons alors le vecteur,

u = \frac{\sqrt{\lambda}}{c}

Ce vecteur est la version initiale de celui à appliquer pour le calcul de E[R_t ^2]. En effet, nous devons appliquer une correction en fonction du nombre de valeurs du vecteur u supérieurs à 1. Cette correction se rapporte directement à P,

p ^* = min(\sharp \lbrace j \in [1, P]; u_j > 1 \rbrace, K - 1) 

Enfin, deux versions du calcul de E[R_t ^2] existent en fonction de la valeur de p ^*. Si p ^* \in ]0, P[, alors nous recalculons le vecteur u avec la nouvelle valeur de c,

c ^* = (\frac{\prod_{j = 1} ^{P ^*} \sqrt{\lambda_j}}{K}) ^{\frac{1}{p ^*}}

, et,

u ^* = \frac{\sqrt{\lambda}}{c ^*}

Nous avons alors,

E[R_t ^2] = 1 - [\frac{\sum_{j = 1} ^{p ^*} \frac{1}{n + u_j} + \sum_{j = p ^* + 1} ^P \frac{u_j ^2}{n + u_j}}{\sum_{j = 1} ^P u_j}] \cdot [\frac{(n - K_t) ^2}{n}] \cdot [1 + \frac{4}{n}]

Dans le cas où p ^* = 0p ^* = p, alors,

E[R_t ^2] = 1 - [\frac{\sum_{j = 1} ^P \frac{1}{n + u_j}}{\sum_{j = 1} ^P u_j}] \cdot [\frac{(n - K_t) ^2}{n}] \cdot [1 + \frac{4}{n}]

En ce qui concerne la lecture du CCC_t,

– Si CCC_t > 2: alors la classification peut être considérée comme bonne,

– Si 0 < CCC_t < 2: alors la classification peut être considérée sans pouvoir confirmer qu’elle soit de qualité,

– Si CCC_t < 0: c’est que nous sommes en présence d’outliers gênants (notamment si CCC_t < -30).

En général, un creux pour k < K classes suivi d’un pic pour k + 1 classes indique une bonne classification pour k+1 classes, surtout si nous avons une croissance ou une décroissance lente à partir de k+2 classes (cf graphe extrait de l’ouvrage de Stéphane Tufféry et présent en bibliographie).

add

Enfin, il convient de ne pas utiliser le Cubic Clustering Criterion pour la méthode de la distance minimale.

\bullet Exemple:

Soit le jeu de données ci-dessous,

add1

La projection des observations nous donne la carte des individus suivante,

add2.png

Construisons la classification ascendante hiérarchique selon les deux paramètres suivants,

– la fonction de distance: distance euclidienne,

– la méthode de regroupement: la distance minimale.

Afin de trouver un compromis entre détail et rapidité des calculs, nous considérerons (., ., \cdots, .) comme le vecteur des éléments à sommer.

\bigstar L’itération initial,

Nous initialisons l’algorithme en calculant la matrice des distances (selon la fonction de distance sélectionnée) et obtenons,

\mathbf{D} = \begin{pmatrix} obs & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 2 & 1.730431 & . & . & . & . & . & . & . & . \\ 3 & 7.306695 & 7.851494 & . & . & . & . & . & . & . \\ 4 & 0.991125 & 1.378891 & 8.214224 & . & . & . & . & . & . \\ 5 & 2.229135 & 2.70852 & 5.190977 & 3.050761 & . & . & . & . & . \\ 6 & 10.860636 & 12.570271 & 10.627881 & 11.603027 & 10.847912 & . & . & . & . \\ 7 & 8.594840 & 10.314997 & 9.309023 & 9.311560 & 8.746753 & 2.311944 & . & . & . \\ 8 & 6.403463 & 8.123649 & 9.287647 & 6.955009 & 7.149683 & 5.065955 & 2.830877 & . & . \\ 9 & 5.463783 & 6.765099 & 11.353934 & 5.386607 & 7.317928 & 9.069772 & 6.941757 & 4.141981 & . \\ 10 & 4.224611 & 5.452226 & 10.553691 & 4.075979 & 6.198213 & 9.640028 & 7.401122 & 4.578377 & 1.327253 \\ \end{pmatrix}

Afin de justifier le tableau \mathbf{D}, prenons le temps de montrer le calcul de la distance entre l’observation 1 et l’observation 2. Nous avons donc,
 
D(X_1, X_2) = \sqrt{(8.1472 - 9.0579) ^2 + (9.2858 - 10.7572) ^2}
 
= \sqrt{0.8293745 + 2.165018}
 
= \sqrt{2.994392}
 
= 1.730431
  
Revenons sur le processus itératif, la distance la plus petite au sein de \mathbf{D} est d(X_1, X_4) = 0.991125, correspondant au premier regroupement pour l’itération initiale de l’algorithme. Nous pouvons construire la première branche du dendogramme,

addbbbbbb.png

Calculons les différentes indicateurs pour l’itération initiale. Nous obtenons,

R_1 ^2 = \frac{\sum_{i = 1} ^9 (3.113284 ^2, 4.837503 ^2, \cdots, 5.482 ^2) - \sum_{k_1 = 1} ^9 (0.4955625 ^2, 0 ^2, 0 ^2, 0.4955625 ^2, 0 ^2, \cdots, 0 ^2)}{\sum_{i = 1} ^9 (3.113284 ^2, 4.837503 ^2, \cdots, 5.482 ^2)}

= \frac{245.9374 - 0.4911644}{245.9374}

= 0.9980029

semi-partiel-R_1 ^2 = 1 - R_1 ^2 = 1 - 0.9980029 = 0.0019971

pseudo-F_1 = \frac{\frac{0.9980029}{9 - 1}}{\frac{1 - 0.9980029}{10 - 9}} = \frac{0.1247504}{0.0019971} = 62.4654

Le pseudo-T_1 ^2 n’étant pas calculable pour cette première itération étant donné qu’il mesure l’évolution de l’inertie lorsque deux groupes de plusieurs observations sont fusionnés. De même pour le CCC_1, dont l’algorithme ne permet pas de retenir la moindre valeur propre.

\bigstar L’itération N° 2,

Nous passons désormais à la seconde itération dont la particularité sera de considérer les observations 1, 4 comme une unique entité et dont la distance sera déterminée en fonction de la méthode choisie. La figure ci-dessous présente ce premier regroupement (intitulé cluster A) et la méthode appliquée pour déterminer les distances à retenir entre les différentes observations et le cluster A.

add3

La distance la plus petite (1.327253, cf \mathbf{D}) est celle entre les observations 9 et 10. Nous procédons donc au regroupement et appellerons ce cluster le B. Nous pouvons donc mettre à jour le dendogramme.

addbbbbbb.png

Calculons les différentes indicateurs pour l’itération 2. Nous obtenons,

R_2 ^2 = \frac{254.9375 - \sum_{k_1 = 1} ^9 (0.4955625 ^2, 0 ^2, 0 ^2, 0.4955625 ^2, 0 ^2, \cdots, 0 ^2, 0.6636267^2,  0.6636267^2)}{254.9375}

= \frac{245.9374 - 1.371965}{245.9374}

= 0.9944215

semi-partiel-R_2 ^2 = R_1 ^2 - R_2 ^2 = 0.9980029 - 0.9944215 = 0.0035814

pseudo-F_2 = \frac{\frac{0.9944215}{8 - 1}}{\frac{1 - 0.9944215}{10 - 8}} = \frac{0.1420602}{0.00278925} = 50.93121

Le pseudo-T_2 ^2 et le CCC_2 n’étant à nouveau pas calculable pour cette seconde itération et pour les même raisons décrites en première.

\bigstar L’itération N° 3,

Passons ensuite à l’itération N° 3. La figure ci-dessous caractérise la procédure suivie pour déterminer le nouveau regroupement à effectuer en fonction des groupes A, B conçus.

add2

La distance minimale (1.378891, cf \mathbf{D}) est cette fois-ci celle entre l’observation 2 et le groupe A. Par conséquent nous l’insérons au groupe et pouvons mettre à jour le dendogramme,

addbbbbbb.png

, et nous pouvons calculer les nouveaux indicateurs pour cette itération.

R_3 ^2 = \frac{254.9375 - \sum_{k_1 = 1} ^9 (0.8200341 ^2, 0.9893395 ^2, 0 ^2, 0.5550719 ^2, 0 ^2, \cdots, 0 ^2, 0.6636267^2,  0.6636267^2)}{254.9375}

= \frac{245.9374 - 2.840154}{245.9374}

= 0.9884517

semi-partiel-R_3 ^2 = R_2 ^2 - R_3 ^2 = 0.9944215 - 0.9884517 = 0.0059698

pseudo-F_3 = \frac{\frac{0.9884517}{7 - 1}}{\frac{1 - 0.9884517}{10 - 7}} = \frac{0.1647419}{0.003849433} = 42.79649

– Bonne nouvelle, nous sommes ici dans le cas du regroupement de deux groupes (celui contenant l’observation 2 et le groupe A issu de la fusion des observations 1, 4). Nous avons donc,

pseudo-T_3 ^2 = \frac{(0.8200341 ^2 + 0.9893395 ^2 + 0.5550719 ^2) - (0.4955625 ^2 + 0.4955625 ^2) - 0 ^2}{\frac{ (0.4955625 ^2 + 0.4955625 ^2) + 0 ^2}{2 + 1 - 2}}

= \frac{1.468189}{0.4911644}

= 2.9892

– Enfin, le CCC_3 n’étant à nouveau pas calculable pour cette troisième itération et pour les même raisons décrites en première et seconde.

\bigstar etc etc,

Nous continuons cet enchainement de calcul jusqu’à l’avant-dernier regroupement. A ce stade nous avons la carte des individus suivantes avec l’application de la méthode visant à déterminer les distances à retenir entre les différentes observations des clusters C et D,

addbbb

La distance minimale (4.141981, cf \mathbf{D}) est celle entre le cluster C et le cluster D. Par conséquent, nous les regroupons pour cette avant-dernière itération et obtenons le dendogramme suivant,

addbbbbbb

Calculons désormais les différents indicateurs,

R_8 ^2

= \frac{254.9375 - \sum_{k_1 = 1} ^9 (3.298928 ^2, 5.019707 ^2, 0 ^2, 3.887283 ^2, 4.314452 ^2, 7.767051 ^2, 5.459712 ^2, 3.104740 ^2, 3.590493 ^2,  3.009369^2)}{254.9375}

= \frac{245.9374 - 191.5287}{245.9374}

= 0.2212299

semi-partiel-R_8 ^2 = R_7 ^2 - R_8 ^2 \approx 0.7504299 - 0.2212299 \approx 0.592

pseudo-F_8 = \frac{\frac{0.2212299}{2 - 1}}{\frac{1-0.2212299}{10 - 2}} = \frac{0.2212299}{0.09734626} = 2.272607

pseudo-T_8 ^2

= \frac{(3.298928 ^2 + 5.019707 ^2 + 3.887283 ^2 + 4.314452 ^2 + 7.767051 ^2 + 5.459712 ^2 + 3.104740 ^2 + 3.590493 ^2 +  3.009369^2) - (2.4495831 ^2 + 0.3422138 ^2 + 2.6248904 ^2) - (1.174442 ^2 + 2.566814 ^2 + 1.254978 ^2 + 3.301218 ^2 + 4.312358 ^2 + 3.054969 ^2)}{\frac{(2.4495831 ^2 + 0.3422138 ^2 + 2.6248904 ^2) + (1.174442 ^2 + 2.566814 ^2 + 1.254978 ^2 + 3.301218 ^2 + 4.312358 ^2 + 3.054969 ^2)}{3 + 6 - 2}}

= \frac{191.5287 - 13.00762 - 48.37013}{\frac{13.00762 + 48.37013}{7}}

= \frac{130.1509}{8.76825}

= 14.84343

– Enfin, le CCC_8 est calculable pour cette itération alors profitons-en!

Donc nous débutons par le calcul de,

\mathbf{T} = \begin{pmatrix} 8.1472 & 9.0579 & \cdots & 9.6489 \\ 9.2858 & 10.7572 &\cdots & 5.3371 \\ \end{pmatrix} \times \begin{pmatrix} 8.1472 & 9.2858 \\ 9.0579 & 10.7572 \\ \cdots & \cdots \\ 5.4688 & 3.4694 \\ 9.5751 & 4.0119 \\ 9.6489 & 5.3371 \\ \end{pmatrix} \times \frac{1}{10 - 1}

= \begin{pmatrix} 55.20539 & 5.85148 \\ 50.85148 & 67.13948 \\ \end{pmatrix}

Nous en déduisons le vecteur de valeurs propres suivants,

\lambda = (112.372813, 9.972056)

 Le calcul de,

c = (\frac{\prod_{j = 1} ^2 \sqrt{\lambda_j}}{2}) ^{\frac{1}{2}} = \sqrt{\frac{10.60064 \times 3.157856}{2}} = 4.09116

, nous permet de calculer le vecteur u,

u = (\frac{10.600604}{4.09116}, \frac{3.157856}{4.09116}) = (2.5910999, 0.7718731)

Maintenant, déterminons le paramètre,

p ^* = min(\sharp \lbrace j \in [1,2]; u_j > 1 \rbrace, 2 - 1) = (1,1) = 1 \in ]0, 2[

Ceci fait, mettons à jour le vecteur u. Nous avons donc,

c ^* = (\frac{\prod_{j = 1} ^1 \sqrt{\lambda_j}}{2}) ^{\frac{1}{1}} = \frac{\sqrt{112.372813}}{2} = 5.300302

, et donc,

u ^* = (\frac{\sqrt{112.372813}}{5.300302},\frac{\sqrt{9.972056}}{5.300302}) = (2,0.595788)

Nous avons ensuite,

E[R_8 ^2] = 1 - [\frac{\sum_{j = 1} ^1 \frac{1}{n + u_j} + \sum_{j = 2} ^2 \frac{u_j ^2}{n + u_j}}{\sum_{j = 1} ^2 u_j}] \cdot [\frac{(10 - 2) ^2}{10}] \cdot [1 + \frac{4}{10}]

= 1 - [\frac{\frac{1}{10 + 2} + \frac{0.5957882}{10 + 0.5957888}}{2 ^2 + 0.595788 ^2}] \times 6.5 \times 1.4

= 1 - (\frac{0.1168338}{4.354963}) \times 6.4 \times 1.4

= 1 - 0.02682773 \times 6.4 \times 1.4

= 1 - 0.3981331

= 0.6018668889

Maintenant que nous avons le p ^* et le E[R_8 ^2], nous pouvons déterminer le CCC_8 à cette itération,

CCC_8 = log[\frac{1 - 0.6018668889}{1 - 0.2212299}] \times \frac{\sqrt{\frac{10 \times 1}{2}}}{(0.001 + 0.6018668889) ^{1.2}}

= log(0.5112332) \times 4.104113

= -2.75357

\bigstar La dernière itération,

Nous concluons cette dernière étape en reliant les deux groupes restant, celui contenant l’observation 3 et celui contenant les observations 1, 2, 4, 5, 6, 7, 8, 9, 10. La distance entre les deux groupes selon la méthode choisie est celle entre l’observation 3 et l’observation 5 du groupe décrit ci-dessus (5.190977, cf \mathbf{D}).

Nous obtenons alors le dendogramme suivant,

addb

\bullet Application informatique:

– Procédure SAS: https://support.sas.com/documentation/cdl/en/statug/63033/HTML/default/viewer.htm#cluster_toc.htm

– Package et fonction R: https://stat.ethz.ch/R-manual/R-devel/library/stats/html/hclust.html

\bullet Bibliographie:

– Comprendre et utiliser les statistiques dans les sciences de la vie de Bruno Falissard

– Data mining et statistique décisionnelle. L’intelligence des données de Stéphane Tufféry

– A Statistical Method for Evaluating Systematic Relationships de Robert  Reuven Sokal et Charles Duncan Michener

– A Method of Establishing Groups of Equal Amplitude in Plant Sociology Based on Similarity of Species Content and Its Application to Analyses of the Vegetation on Danish Commons de Thorvald Julius Sørensen

– Clustering Criteria and Multivariate Normal Mixtures de M. J. Symons

– Cubic Clustering Criterion de Warren S. Sarle

– A General Theory of Classificatory Sorting Strategies. I. Hierarchical Systems de Godfrey N. Lance et William Thomas Williams

– A Comparison of Some Methods of Cluster Analysis de John C. Gower

– Sur la Liaison et la Division des Points d’un Ensemble Fini de K. Florek, J. Lukaszewicz, J. Perkal et S. Zubrzycki

– Taksonomia Wroclawska de K. Florek, J. Lukaszewicz, J. Perkal et S. Zubrzycki

– Elementary Linkage Analysis for Isolating Orthogonal and Oblique Types and Typal Relevancies de Louis L. McQuitty

– The Application of Computers to Taxonomy de P. H. A. Sneath

– Hierarchical Grouping to Optimize an Objective Function de Joe H. Ward

– Similarity Analysis by Reciprocal Pairs for Discrete and Continuous Data de Louis L. McQuitty