[fr] Description des algorithmes

Julien Barnier

2022-02-18

L’objectif de ce document est de décrire les algorithmes utilisés pour les classifications dans rainette et leur implémentation. À noter que cette implémentation s’est appuyée sur deux éléments principaux :

Algorithme de classification simple

Matrice de départ

La classification simple est une classification descendante hiérarchique (CDH).

Le tableau de départ est la matrice termes-documents croisant les documents du corpus et les termes qui les composent. Cette matrice est une matrice binaire de présence/absence du terme dans le document, et non une matrice d’occurrences.

On a donc un tableau de ce type :

##      partir un jour sans retour
## doc1      1  1    0    1      0
## doc2      0  1    1    0      1
## doc3      1  1    1    0      1
## doc4      0  1    0    1      1

À noter que si les documents sont des segments obtenus avec split_segments(), les segments trop courts d’un même document peuvent être regroupés entre eux au moment de la classification pour atteindre la taille minimale indiquée par l’argument min_segment_size de rainette().

Division maximisant le Khi2

On souhaite diviser cette matrice termes-documents en deux groupes de documents aussi “différents” que possible. La méthode Reinert consiste à sélectionner le regroupement qui maximise la statistique du χ² du tableau regroupé.

Par exemple, dans le tableau ci-dessus, si on regroupe doc1 avec doc2 et doc3 avec doc4, on obtient le tableau suivant :

##             partir un jour sans retour
## doc1 + doc2      1  2    1    1      1
## doc3 + doc4      1  2    1    1      2

On peut calculer la valeur du χ² de ce tableau. Cette statistique est un indicateur de la “distance” entre les deux groupes de documents en ce qui concerne la distribution des termes : plus la valeur du χ² du tableau regroupé est élevée et plus les deux groupes sont différents, plus elle est faible et plus ils se ressemblent.

Dans un cas aussi simple, on peut effectuer tous les regroupements de documents possibles et déterminer lequel correspond au χ² maximal, mais avec des données réelles la complexité augmente trop rapidement.

On opère donc de la manière suivante :

On obtient donc au final deux groupes de documents et deux matrices termes-documents correspondantes.

Sélection des termes

L’étape suivante consiste en une sélection des termes dans chacun des deux tableaux pour les prochaines itérations :

Classification descendante hiérarchique

Les étapes précédentes permettent de scinder un corpus en deux groupes. Pour obtenir une hiérarchie de classes, on commence par scinder le corpus entier, puis on recommence de la même manière avec le groupe obtenu comportant le plus de documents (sauf si le tableau en question est trop petit pour calculer une AFC, ou si son effectif est inférieur à l’argument min_split_members de rainette()).

En procédant de cette manière k - 1 fois, on obtient une classification descendante hiérarchique (CDH) en k groupes, et le dendrogramme correspondant (la hauteur des branches du dendrogramme étant la valeur maximale du χ² trouvée au moment du split).

Algorithme de classification double

La classification double s’applique à un corpus découpé en segments. L’objectif est d’obtenir des classes plus robustes en croisant les résultats de deux classifications simples calculées avec des tailles minimales de segments différentes.

La classification double consiste donc à effectuer deux classifications simples avec des valeurs distinctes de min_segment_size. On obtient donc deux dendrogrammes différents qui déterminent des classes ici numérotées de 1 à 6 :

Calcul des classes croisées

La première étape consiste à croiser les classes des deux CDH :

On prend chaque classe de la première CDH, et on la croise avec chaque classe de la seconde (y compris si les classes ne sont pas de même niveau k). On appelle la nouvelle classe obtenue une “classe croisée” :

Classe croisée Effectif χ² d’association
11 25 41.2
12 102 30.1
13 59 87.3
14 41 94.0
15 0 -
16 13 6.2
21 0 -
66 5 3.1

Une fois ces classes croisées définies, deux type d’analyse sont possibles.

Analyse “full”

La première, dite analyse “full” (argument full = TRUE de rainette2()), conserve pour la suite toutes les classes croisées dont l’effectif est supérieur à zéro (si celles-ci n’ont pas déjà été filtrées à l’étape précédente). Dans l’exemple ci-dessus, on conserverait donc :

Classe croisée Effectif χ² d’association
11 25 41.2
12 102 30.1
13 59 87.3
14 41 94.0
16 13 6.2
66 5 3.1

Analyse “classique”

La seconde, dite analyse “classique” (argument full = FALSE de rainette2()) ne conserve une classes croisée que si les deux groupes croisés sont mutuellement les plus associés. Ainsi, si on considère la classe croisée issue du croisement du groupe x et du groupe y, on ne conserve cette classe que si y est le groupe ayant le χ² d’association maximal avec x, et si en même temps x est le groupe ayant le χ² d’association maximal avec y.

Dans ce cas le nombre de classes croisées considérées est beaucoup plus réduit :

Classe croisée Effectif χ² d’association
14 41 94.0
33 18 70.1
46 21 58.2
65 25 61.0

Calcul et sélection des partitions optimales

L’étape suivante consiste à déterminer, à partir des classes croisées calculées précédemment, toutes les partitions possibles de nos documents en 2, 3, 4… classes croisées. Plus précisément, on essaie de déterminer tous les groupes de 2, 3, 4… classes croisées qui n’ont aucun élément en commun.

On commence par déterminer les partitions de taille 2, c’est-à-dire tous les ensembles de deux classes croisées n’ayant aucun élément commun. On calcule pour chaque partition son effectif total et la somme de ses χ² d’association.

Partition Effectif total Somme des χ² d’association
11 23 47 62.3
14 35 36 51.0
24 16 29 38.2
12 53 143 68.7

On sélectionne parmi ces partitions celles qui sont considérées comme les “meilleures”, c’est-à-dire :

Partition Effectif total Somme des χ² d’association
12 53 143 68.7
34 26 86 98.0

On fait de même pour les partitions de taille 3 : on détermine les différentes partitions possibles et on conserve les meilleures.

Partition Effectif total Somme des χ² d’association
12 53 25
189 91.3
34 26 53 113 108.1

Et on continue pour les partitions de 4 classes croisées, etc.

Partition Effectif total Somme des χ² d’association
34265315
223 114.7

On répète l’opération jusqu’à atteindre la valeur de l’argument max_k de rainette2(), ou bien lorsqu’il n’y a aucune partition possible au niveau considéré.

Résultat

On obtient donc au final, pour chaque valeur de k de 2 à max_k, une sélection de partitions de classes croisées considérées comme “optimales”, soit selon le critère de la somme de leur χ² d’association, soit selon celui de leur effectif total. Ces classes croisées constituent de nouveaux groupes potentiellement plus “robustes” que ceux mis en évidence par les deux CDH simples.

À noter que cette opération peut faire qu’un grand nombre de documents n’appartiennent à aucun des nouveaux groupes. rainette propose de réaffecter ces documents aux nouveaux groupes via une méthode rapide de type k-nearest neighbours, mais ceci n’est pas forcément conseillé dans la mesure où on perdrait la “robustesse” qui est justement l’objectif de la double classification.

Différences avec Iramuteq

Classification simple

L’implémentation de l’algorithme dans rainette se différencie de celle d’Iramuteq surtout dans la gestion du paramètre min_split_members (le nombre minimal de documents dans une classe).

Dans rainette, min_split_members est uniquement utilisé au moment du choix du tableau suivant à splitter : si aucun tableau n’a un effectif supérieur à ce paramètre, l’algorithme s’arrête même si on n’a pas atteint la valeur souhaitée de k.

Dans Iramuteq, l’algorithme se répète k fois dans tous les cas, et il procède à la fin à un regroupement des classes dont l’effectif est inférieur à l’effectif minimal souhaité. Ce regroupement s’effectue en fusionnant ces classes en “remontant” le dendrogramme.

L’avantage de l’implémentation dans rainette est qu’on ne “casse” pas la logique du dendrogramme, et qu’on obtient donc comme résultat un arbre complet, qu’on peut couper à la hauteur souhaitée : on peut donc explorer la classification en 2, 3 … k groupes. L’inconvénient est qu’on n’a pas d’assurance de n’avoir aucune classe avec un effectif inférieur à min_split_members : on doit procéder à des regroupements manuels si nécessaire.

Classification double

La méthode proposée par Iramuteq correspond plutôt à la méthode “full” de ce document : après avoir déterminé les classes croisées, on conserve toutes celles ayant un effectif et une valeur de χ² d’association suffisants.

L’algorithme reste très proche de celui d’Iramuteq jusqu’à l’étape de la sélection de partition optimale. Ici on procède à une recherche exhaustive des partitions à partir des classes croisées sélectionnées (ce qui peut occasionner des calculs potentiellement très longs si min_members est faible et max_k élevé), tandis qu’Iramuteq procède autrement.

Au niveau des résultats, Iramuteq ne renvoie qu’une seule partition qu’il juge optimale, tandis que rainette retourne pour chaque valeur de k les meilleures partitions selon les critères de la taille ou du χ² maximum.

Différences avec la “méthode Reinert”

Le mode de détermination des partitions optimales ne nous a pas semblé très détaillé dans les articles cités en références, il ne nous est donc pas vraiment possible de comparer avec l’implémentation de rainette. A priori la méthode présentée par Max Reinert correspond à la méthode dite “classique” présentée dans ce document : après le calcul des classes croisées on ne conserve que celles dont les deux groupes croisés sont les plus associés mutuellement.

Une différence importante réside dans le fait que dans les articles cités, une fois la partition optimale déterminée, celle-ci est utilisée comme point de départ pour une affectation des documents aux classes via une méthode de type “nuées dynamiques”. Ceci permet notamment de réaffecter des points qui ne feraient pas partie des classes croisées de la partition retenue.

Cette réaffectation par centre mobile n’est pas implémentée dans rainette (et elle ne semble pas l’être non plus dans Iramuteq). Il faut donc être vigilant au nombre et à la proportion de documents non affectés (valeur de classe à NA) à l’issue d’une classification double, car celui-ci peut être élevé. Une fonction rainette2_complete_groups() est disponible pour rattacher les points non affectés à une des classes via une méthode du type k-nearest neighbours, mais son utilisation n’est pas forcément conseillée.

Références