[fr] Description des algorithmes

Julien Barnier

2021-10-06

L’objectif de ce document est de décrire les algorithmes utilisés pour les classifications dans rainette, et de comparer notamment avec l’implémentation d’Iramuteq (dans sa version 0.7-alpha2). Aucune comparaison n’a pu être faite avec Alceste car il s’agit d’un logiciel commercial et propriétaire.

À noter que l’implémentation de rainette repose 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 segments de texte (unités de contexte élémentaires, uce), éventuellement regroupés en unités de contexte (uc) s’ils ne comportent pas suffisamment de formes différentes (selon la valeur de l’argument min_segment_size passé à rainette), et les termes. Cette matrice est une matrice binaire de présence/absence du terme dans le document, et non une matrice d’effectifs.

On a donc un tableau de ce type :

##     partir un jour sans retour
## uc1      1  1    0    1      0
## uc2      0  1    1    0      1
## uc3      1  1    1    0      1
## uc4      0  1    0    1      1

Division maximisant le Khi2

On souhaite diviser ce tableau de départ en maximisant la valeur du Khi2 obtenue lorsqu’on regroupe les lignes en deux classes. Par exemple, dans le tableau ci-dessus, si on regroupe uc1 avec uc2 et uc3 avec uc4, on obtient le tableau suivant :

##      partir un jour sans retour
## [1,]      1  2    1    1      1
## [2,]      1  2    1    1      2

On peut calculer le Khi2 de ce tableau (qui vaut en l’occurrence 0.2579365). Dans un cas aussi simple, on peut effectuer tous les regroupements d’uc possible et déterminer lequel correspond au Khi2 maximal, mais avec des données réelles cela prendrait trop de temps.

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

On obtient donc deux nouveaux tableaux correspondant au regroupement des lignes en vue de la maximisation du Khi2 du tableau regroupé.

Sélection des termes

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

Parmi les deux tableaux finaux obtenus après séparation et sélection des termes, on recommence l’algorithme sur le tableau le plus gros, celui 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_members).

En procédant de cette manière k fois, on obtient une CDH en k groupes, et un dendrogramme correspondant (la hauteur du dendrogramme étant la valeur maximale du Khi2 trouvée au moment du split).

Différences avec Iramuteq

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

Dans rainette, min_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_members : on doit procéder à des regroupements manuels si nécessaire.

Algorithme de double classification

La double classification consiste à effectuer deux classifications simples, mais avec des tailles d’uc différentes (valeurs distinctes de min_segment_size). L’idée est alors de “croiser” les résultats de ces deux CDH pour déterminer des classes plus “robustes”.

Calcul des classes croisées

Dans ce qui suit on considère, pour les deux CDH, toutes les classes obtenues pour chaque niveau de k. Pour une CDH avec k = 5, on a donc un total de 14 classes dans chaque CDH.

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

À noter que le croisement systématique de toutes les classes entraîne beaucoup de “doublons”, c’est-à-dire de classes croisées avec exactement les mêmes membres. Ceux-ci ne sont évidemment pas conservés.

L’étape suivante consiste à sélectionner les ensembles de classes croisées correspondant à la meilleure partition de l’ensemble des documents, c’est-à-dire qu’on va considérer tous les ensembles de classes croisées n’ayant aucun document en commun, et qu’on va chercher parmi toutes ces partitions la partition “optimale”.

La procédure à suivre décrite dans les articles cités dans les références n’est pas très claire, on s’est donc pour la suite surtout inspiré du code d’Iramuteq.

Sélection des classes croisées

Pour diminuer le nombre de partitions à examiner, on commence par sélectionner certaines classes croisées :

Calcul des partitions

Le calcul des partitions s’effectue de manière récursive à partir des classes croisées conservées à l’étape précédente :

Sélection des partitions optimales

Une fois toutes les partitions déterminées, on calcule pour chacune d’elle deux critères :

Au final, on conserve pour chaque valeur de k (donc pour les partitions en 2, 3…max_k classes) les partitions ayant soit la taille totale maximale, soit le Khi2 total maximal (on a donc une ou deux partitions pour chaque k).

Différences avec Iramuteq

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 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 deux meilleures partitions selon les critères de la taille ou du Khi2 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. Une différence majeure 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 “centres mobiles”. 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 cependant disponible pour rattacher les points non affectés à une des classes via une méthode du type k-nearest neighbours.

Références