[fr] Description des algorithmes

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 effectue une analyse factorielle des correspondances de la matrice termes-documents, et on ordonne les documents selon leur coordonnée sur le premier axe de cette AFC.
• on regroupe tour à tour les documents entre eux selon cet ordonnancement : d’abord le point avec la coordonnée la plus basse vs tous les autres, puis les deux points avec les coordonnées les plus basses vs tous les autres, etc. On calcule à chaque fois le χ² correspondant et on conserve au final le regroupement qui le maximise.
• à partir de ce regroupement, on effectue une réaffectation des documents : on change tour à tour chaque document de classe, et on regarde si cela fait augmenter le χ². Si c’est le cas on conserve cette nouvelle affectation.
• on recommence cette opération de réaffectation jusqu’à ce qu’elle ne permette plus d’augmenter la valeur du χ².

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 :

• on regarde la fréquence de chaque terme, et on supprime les termes qui apparaissent moins de 3 fois (cette valeur est modifiable via l’argument tsj de rainette()).
• on compare également l’effectif observé de chaque terme avec l’effectif attendu sous l’hypothèse d’indépendance de la répartition du terme entre les deux groupes, et on en déduit un coefficient de contingence pour ce terme. Si ce coefficient de contingence est supérieur à 0.3, on ne conserve le terme que dans le tableau dans lequel il est surreprésenté (le seuil de 0.3 est modifiable via l’argument cc_test de rainette()).

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).

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” :

• pour chaque classe croisée, on calcule l’effectif du croisement, c’est à dire le nombre de documents présents dans les deux classes.
• à partir de cet effectif, de l’effectif de chaque classe et du nombre total de documents, on peut créer un tableau croisé d’appartenance aux deux classes : on calcule alors le χ² de ce tableau, qui représente une mesure de “l’association” entre les deux classes.
• si deux classes croisées différentes comportent les mêmes documents, on ne conserve que l’une d’entre elles.
• si une classe croisée comporte un effectif inférieur à la valeur de l’argument min_members de rainette2(), elle n’est pas conservée.
• si une classe croisée comporte un χ² d’association inférieur à la valeur de l’argument min_chi2 de rainette2(), elle n’est pas conservée.

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

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.

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

• si on fait une analyse “full” (full = TRUE), on sélectionne celle ayant la somme de χ² d’association la plus forte, et celle ayant l’effectif total le plus élevé.
• si on fait une analyse “classique” (full = FALSE), on sélectionne uniquement celle ayant la somme de χ² d’association la plus forte (on ne peut pas utiliser l’effectif total comme critère de sélection dans ce cas-là).

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

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

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.

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.