README.md

In yechchi/Algorithmique: Classification ascendante hiérarchique

Algorithmique

Hierarchical Agglomerative Clusering

El hajam Nawal - Koua Jean-Charles - Yechchi Sif-Eddine

Présentation package :

Dans le cadre de notre cours d'algorithmique, nous avons créer notre propre package R/Rcpp intitulé "Algorithmique". Ce package contient les fonctions suivants : la fonction h_clust, distc, h_clust_Wardet distWard.

L'installation de notre package se fait grâce aux commandes suivantes :

#devtools::install_github("yechchi/Algorithmique")
library(Algorithmique)

Complexité :

La compléxité temporelle théorique de notre fonction h_clust est de O(n3) . La solution amélioré de notre fonction a une complexité temporelle de O(n2log(n))

Principes de la CAH :

L'objectif de la classification ascendante hiérarchique (CAH) est de produire une arborescence qui met en évidence les liens hiérarchiques entre les individus ou entre des groupes d'individus et donc de classer des individus ayant un comportement similaires. Regrouper les individus les plus proches nécessite plusieurs conditions : - une fonction de distance ; - une méthode spécifique de regroupement des individus ;

QUESTION : Comment mesurer la distance entre 2 groupes ?

Choix d’une distance et d’un critère

Les méthodes de clustering de type hiérarchique sont différentes. Elles forment pas à pas des connexions entre individus (pour les méthodes de clustering hiérarchiques ascendantes), et utilisent une matrice de distances entre individus pour trouver le regroupement le plus proche d’un autre.

En pratique, on part de n ensembles qui sont les individus en tant que singletons. La première connexion se fait donc entre les deux individus les plus proches.

Pour débuter la deuxième étape, il faut mettre à jour la matrice des distances en enlevant une case, à cause du regroupement de deux individus. Mais comment calculer la distance d’un ensemble à un autre s’il n’est pas un singleton ? C’est justement un des choix à effectuer au départ : la stratégie d’agrégation. Il y en a de multiples, les plus simples étant de choisir la distance minimale entre les individus des deux groupes (single linkage), maximale (complete linkage) ou bien moyenne (average linkage) ou encore(centroid linkage). (cf. la fonction 'distc')

A la fin de cette deuxième étape, on connecte donc les deux groupes les plus proches. Et ainsi de suite pour les étapes suivantes, jusqu’à connecter les deux derniers groupes qui recouvrent tous les individus.

Les connexions successives se représentent sur un dendrogramme (cf illustration). La distance associée à chaque connexion se trouve sur l’axe y de celui-ci.

L’algorithme se termine bien sûr par le choix de nos clusters. Là encore, le critère n’est pas unique : on peut en vouloir un nombre précis, ou bien fixer un critère de distance inter-classe. On utilise le dendrogramme pour mettre les clusters en évidence.

### Algorithme amélioré: La meilleure façon de faire des groupes d’individus homogènes entre eux et bien différents d’un groupe à l’autre, c’est de minimiser les distances qui séparent les différents individus à l’intérieur d’un groupe tout en maximisant les distances qui séparent les individus appartenant à des groupe différents. C’est ce que fait la méthode de Ward. En effet, la méthode 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 les deux clusters considérés et de barycentres respectifs , la formule d'usage est alors:

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

On utilise le critère d’inertie comme une mesure de la dispersion des individus autour du centre de gravité G de l’ensemble E (inertie totale) ou bien autour du centre de gravité du groupe auquel ils appartiennent (inertie intra-groupe). Plus l’inertie est faible, plus les individus sont ramassés autour du centre de gravité considéré. L’inertie totale de E est constante étant donné que les éléments constituant E ne bougent pas, tandis que l’inertie intra-groupe est variable au sein de chaque groupe à k fixé, suivant les partitions considérées de n éléments parmi k groupes. Le but sera donc de comparer ces différentes inerties intra-groupe pour chaque partition possible et de conserver la partition qui minimise l’inertie intra-groupe dans le maximum de groupes, ce qui équivaut à trouver la configuration des k groupes dans E qui maximise l’inertie inter-groupe (différence entre l’inertie totale et la somme, sur les groupes, des inerties intra-groupes).

Propriété :

Par conséquent, la CAH utilise les distances euclidiennnes et le critère de Ward, qui minimise l’inertie intra-groupe pour constituer des groupes d’individus homogènes entre eux.

Algorithme de la CAH

L’étape initiale de l’algorithme de la CAH consiste à considérer chaque individu de départ comme un groupe à lui tout seul, soit un total de n groupes. Par conséquent les conditions initiales en termes d’inertie sont les suivantes : Iintra = 0 Iinter = Itot

Etape 1, n groupes :

Calculer la matrice de distance euclidienne entre les différents groupes d’observations.

L’algorithme recherche donc les 2 individus les plus proches en terme de distance euclidienne pour former un premier couple, c’est-à-dire ceux dont la distance est minimale. Cela provoque une augmentation de l’inertie intra-groupe (augmentation la plus faible parmi l’ensemble des augmentations possible étant donné que l’algorithme a sélectionné les 2 individus les plus proches). L’algorithme remplace les 2 individus par le couple placé au barycentre des 2 individus qui le compose, le nombre d’individus diminue (n-1).

Etape 2, (n-1) groupes :

L’algorithme recalcule les distances entre tous les individus (n-1) grâce à la méthode de Ward. A nouveau, l’algorithme regroupe les 2 individus les plus proches en formant un nouveau couple ce qui provoque une nouvelle augmentation de l’inertie intra-groupe couplée d’une diminution du nombre d’individus (n-2).

Etape 3, (n-2) groupes :

Le passage d’un niveau de la hiérarchie au suivant consiste à fusionner les deux groupes qui se ressemblent le plus, l’idée générale est de minimiser la variabilité (inertie) intra-groupe et de maximiser la variabilité (inertie) inter-groupe.

Réitération de la procédure…

Etape n, 1 groupe :

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érentes classifications possibles. C’est la dernière étape de l’algorithme, cette fois l’inertie totale est contenue dans l’inertie intra-groupe, il n’existe plus d’inertie inter-groupe.

L’algorithme procède de manière ascendante jusqu’à n’obtenir qu’un seul groupe.

Idée pour l'amélioration de la complexité:

La formule de Lance et Williams permet d’unifier plusieurs méthodes de classification ascendante hiérarchique (CAH). En effet, à l'étape 3, il existe plusieurs techniques de CAH selon la façon dont on définit la dissimilarité entre deux groupes. Cependant, Lance et Williams (Lance et Williams, 1967) ont montré que la majorité d’entre elles pouvaient être généralisées par la formule suivante:

Cela nous permet de mettre à jour les formules des distances:

yechchi/Algorithmique documentation built on Jan. 20, 2021, 12:30 a.m.