2.1 – Notations

7Nous notons par l’ensemble des mots du vocabulaire d’une collection de n documents. Nous représentons les mots par

2.2 – Probabilistic latent semantic analysis (PLSA)

8Le modèle PLSA est un modèle probabiliste qui caractérise chaque mot dans un document comme une variable aléatoire générée par un modèle de mélange dont les composantes du mélange sont des distributions multinomiales. Ce modèle associe une variable latente non observée (appelée topic ou composante) ? ? A = {?₁, …, ?_K} à chaque observation correspondant à l’occurrence d’un mot dans un document . Dans ce cas le processus de génération des mots d’une collection donnée suit le schéma graphique suivant (figure 1a) :

• choisir un document d avec une probabilité p(d),
• choisir une variable latente ? d’après sa probabilité conditionnelle p(? | d),
• génerer un mot w suivant la probabilité p(w | ?).

9

2.2.1 – Apprentissage du modèle

10Les paramètres du modèle [2] sont estimés suivant le principe du maximum de vraisemblance en optimisant la fonction :

La variable thématique ? n’étant pas observée, les paramètres du modèle sont estimés suivant la procédure espérance maximisation (EM) (Dempster et al., 1977). L’étape E, consiste à estimer les probabilités a posteriori de la variable latente ?. Et, à l’étape M, on ré-estime de nouveaux paramètres du modèle en maximisant la fonction de log-vraisemblance [3].

Figure 1

Deux modèles graphiques pour le clustering de documents (a) le modèle PLSA (b) notre extension de PLSA

Deux modèles graphiques pour le clustering de documents (a) le modèle PLSA (b) notre extension de PLSA

2.2.2 – Classification non supervisée avec PLSA

11Avec le modèle PLSA, il est également possible de partitionner les documents d’une collection donnée. En effet, la quantité p(? | d) est la probabilité d’observer la thématique ? sachant le document d, et s’interprète naturellement comme la probabilité d’appartenance du document d à la thématique ?. Ainsi, l’algorithme PLSA peut être utilisé comme un algorithme de clustering de documents, où chaque cluster correspond à une thématique. Pour partitionner les documents en clusters, il suffit alors d’attribuer à chaque document la thématique la plus probable :

12

13où les p(?|d) sont connues puisqu’elles sont apprises par le modèle. De la même manière, il est possible d’utiliser PLSA pour le clustering de mots. Pour cela, il suffit d’interpréter p(?|w) comme la probabilité d’appartenance du mot w à la thématique ?. Les probabilités p(? | w) ne sont pas disponibles directement, mais peuvent être exprimées en fonction des paramètres du modèle. Après calculs, nous obtenons :

14

15Nous remarquons que les variables latentes, A, servent dans le modèle PLSA aussi bien à partitionner les documents qu’à trouver les concepts de mots.

2.3 – Apprentissage de concepts de mots avec l’hypothèse

16Nous proposons de trouver les concepts de mots grâce à l’hypothèse

2.3.1 – Algorithme CEM

17Pour trouver les concepts de mots nous utilisons l’algorithme classification-espérance-maximisation (CEM) (Celeux et al., 1992), qui est une version classifiante de l’algorithme EM (Dempster et al., 1977). Chaque mot devient donc un exemple des données et les clusters de mots retrouvés par CEM sont traités comme les concepts de mots.

18Le nombre de clusters de mots K étant choisi et fixé, le partitionnement des mots w du vocabulaire se base sur un modèle probabiliste génératif des mots et l’hypothèse simplificatrice que deux mots différents et sont générés indépendamment par ce modèle génératif.

19Plus formellement, nous supposons que chaque terme w est généré par le modèle de mélanges

20

21où ?_k est l’ensemble de paramètres (appris par l’algorithme) associé au cluster k, ? est l’ensemble de tous les paramètres du modèle et ?_k = p(c = k|?), la probabilité qu’un mot généré aléatoirement appartienne au cluster k.

22La deuxième hypothèse est que chaque terme appartient à un seul et unique cluster. Formellement, nous associons à chaque terme w_j ? V un vecteur indicateur de cluster q_j = {q_hj}_h qui est un vecteur binaire défini par :

23

2.3.2 – Apprentissage de concepts de mots

24L’algorithme CEM détermine les clusters de mots P en cherchant les paramètres ? qui maximisent la log-vraisemblance des données complètes :

25

26Ici, les vecteurs indicateurs de clusters, q, font partie des paramètres du modèle et sont donc appris simultanément avec les paramètres ?. Dans nos expériences, nous avons supposé que les termes étaient générés indépendamment par le mélange de densité [6] où chaque composante du mélange obéit à un modèle Naïve Bayes. Les paramètres ? du modèle sont l’ensemble des probabilités a priori des clusters ?_k = p(c = k) et les probabilités des documents d_i sachant les clusters . Avec ces hypothèses, la probabilité d’un mot w est

27Pour estimer les paramètres ?_k et p_ik qui maximisent la log-vraisemblance, nous dérivons et utilisons les multiplicateurs de Lagrange pour préserver les contraintes et nous obtenons :

28

29Une fois les concepts de mots trouvés, les documents sont alors représentés dans l’espace induit par ces concepts, où chaque nouvelle caractéristique correspond à un cluster de mots et représente le nombre total d’occurrences des mots du cluster présents dans le document.

2.4 – Extension de PLSA (ou PLSA-étendu)

30Dans cette section nous présentons notre extension du modèle PLSA décrit précédemment. Alors qu’avec PLSA les mots ne sont générés que par les thématiques, nous supposons ici que les mots du vocabulaire sont générés conjointement par les clusters de documents et les concepts de mots. Cette supposition peut s’interpréter de la manière suivante : dans une collection il existe des thématiques de documents correspondant aux différents discours présents dans la collection. À l’intérieur de ces thématiques, les documents contiennent des sujets différents. Par exemple une thématique peut être Sport et les différents sujets de cette thématique sont des sujets sportifs parlant de domaines différents. Avec le modèle PLSA, on suppose que tous les documents appartenant à une thématique génèrent de la même façon les mots de cette thématique. Dans cette étude, nous supposons que ces mots sont à la fois générés par le discours latent représenté par la thématique et les différents sujets traités dans cette thématique. Ainsi la différence principale entre notre modèle et le modèle est l’utilisation d’une variable latente supplémentaire y, qui représente les concepts de mots. Le processus génératif correspondant à notre modèle est le suivant :

• choisir un document d suivant p(d),
• générer une thématique ? d’après p(?|d),
• choisir un concept de mots y suivant la probabilité p(y),
• générer un mot w d’après p(w|?, y).

31Avec notre modèle, la probabilité jointe d’observer le document d, le mot w, la thématique ? et le concept de mots y est donnée par

32

33Les hypothèses d’indépendance conditionnelle nous permettent ensuite d’écrire p(y | d,w) = p(y) et p(w|d, ?, y) = p(w|?, y). Finalement la probabilité jointe se simplifie en :

34

35Ainsi la probabilité jointe d’observer le document d et le mot w est

36

37où, est l’ensemble des concepts de mots.

2.4.1 – Apprentissage du modèle

38Nous estimons les paramètres P(d), P(?|d), P(y) and P(w|?, y) de notre modèle en suivant le principe du maximum de vraisemblance en optimisant la fonction de log-vraisemblance [3]. Les variables ? et y n’étant pas observées, nous utilisons l’algorithme EM pour estimer les paramètres de notre modèle (Dempster et al., 1977) Dans l’étape E, nous estimons les probabilités a posteriori des variables cachées ? et y :

39

40Dans l’étape M, nous ré-estimons les paramètres du modèle qui maximisent la log vraisemblance complète des données (equation [3]). Ces estimés sont :

41

42Nous notons que la probabilité p(d) n’intervient pas dans l’étape E et qu’elle peut être éstimée une fois de la façon suivante :

43

44Nous pouvons utiliser notre modèle pour le clustering de documents. Comme avec PLSA, nous interprétons la quantité p(?|d) comme la probabilité que le document d appartienne à la thématique ?. À chaque document est donc attribué le cluster vérifiant :

45

2.4.2 – Relation entre PLSA étendu et FMN

46La factorisation en matrices non négatives (FMN) permet d’approximer une matrice non négative F par un produit de matrices C et H : F ? HC^t. La qualité de l’approximation HC^t est mesurée par des fonctions de divergences de Bregman D(F||HC^t) qui en général sont des fonctions asymétriques. Pour calculer la divergence entre deux matrices nous écrirons simplement . Où X_ij (resp. Y_ij) correspond à l’élément de la ligne i et de la colonne j de la matrice X (resp. Y).

47Comme fonction de divergence, nous avons choisi dans notre travail la divergence de Kullback-Leibler (KL) définie comme :

48

49Dans la suite nous notons par D_KL, cette divergence de Kullback-Leibler. Récemment, (Gaussier et al., 2005) ont montré que l’algorithme du modèle est équivalent aux lois de mise à jour de matrices C et H du modèle au sens de la divergence de Kullback-Leibler (KL) décrite dans (Lee et al., 1999). (Ding et al., 2008) ont aussi montré l’équivalence entre les deux au niveau de la construction du modèle en utilisant les deux propositions suivantes :

50

Proposition 1 La vraisemblance [3] pour le modèle PLSA est identique à la divergence KL ([14]) : .

51

Proposition 2 Le modèle FMN avec les matrices normaliées est equivalent à la factorisation de la probabilité, l’équation [2], i.e. (HC^t)_ij = P(d_i, w_j), ?(i, j).

52Nous étendons ce résultat en montrant que notre extension de PLSA est équivalente à une combinaison linéaire de FMN, ou à une factorisation avec une mixture des éléments non négatifs :

53

Proposition 3 Le modèle PLSA étendu d’après l’équation [8] est équivalent à une combinaison linéaire de modèles FMN.

54

Preuve 1 Nous réécrivons le modèle PLSA étendu à partir de l’équation [8] :

55

56D’après la proposition 2, pour une matrice L1-normalisée F, chacun des termes est equivalent à une FMN (HC^t_l )_ij . De plus, à partir de la proposition 1, la maximisation de la vraisemblence est équivalente à la minimisation de la divergence

57

58À partir de ces deux résultats il s’ensuit que PLSA étendu peut être considéré comme une combinaison linéaire de modèles FMN.

3.1 – Le corpus

60Pour l’évaluation, nous avons construit nos bases à partir de trois collections de documents standard. La première est la collection Reuters [1]. Nous nous sommes intéressés aux 7 classes les plus représentées (acq, crude, earn garin, interest, money, trade) dans cette collection avec un nombre total de 4 335 documents. La deuxième est la collection 20Newsgroups [2] qui est construite à partir de 20 forums différents de discussion Usenet. Nous utilisons 5 groupes parmi eux contenant 16 010 documents au total. La troisième collection est le corpus WebKB [3] (4 universités). Nous avons choisi de travailler dans ce cas sur les 4 classes les plus larges avec un nombre comprenant 4 196 articles. Notre prétraitement consiste à filtrer le texte en enlevant les balises HTML, à convertir les majuscules en minuscules et à enlever les caractères non alphanumériques. Nous filtrons également les mots suivant un anti-dictionnaire anglais [4] ainsi que les mots qui apparaissent dans moins de 3 documents. Le vocabulaire obtenu après ce filtrage est constitué de 6 990 mots pour Reuters, de 38 630 mots pour 20Newsgroups et de 11 170 mots pour le corpus WebKB. Le tableau 1 récapitule les caractéristiques des trois collections.

61Dans nos expériences, nous avons divisé chaque collection en 10 sous-ensembles en préservant dans chacun d’eux les proportions entre les différentes classes. Cette division est nécessaire pour éviter des biais causés par la structure de chaque collection, et pour atténuer les effets des initialisations aléatoires utilisées dans les algorithmes. Pour les résultats expérimentaux, les performances présentées sont ainsi une moyenne de 10 performances obtenues sur chacun des sous-ensembles. Le maintien de la proportion dans chaque sous-ensemble est important, car cela permet de juger si la nouvelle représentation des documents permet de mieux retrouver les petites classes que la représentation initiale dans l’espace des mots.

Tableau 1

Les caractéristiques des collections Reuters, 20Newsgroups et WebKB

Reuters Classe taille pour. % earn 2002 46.2 acq 1080 24.9 money 362 8.4 crude 295 7.0 grain 283 6.5 trade 207 4.8 interest 106 2.4 20Newsgroups Classe taille pour. comp. 4891 30.5 sci. 3951 24.7 rec. 3253 20.3 talk. 3116 19.5 alt. 799 5.0 WebKB Classe taille pour. % student 1641 39.1 faculty 1123 26.8 course 930 22.1 project 504 12.0

Les caractéristiques des collections Reuters, 20Newsgroups et WebKB

3.2 – Mesure d’évaluation

62Afin d’évaluer la pertinence des partitions obtenues, nous devons savoir à quelle classe initiale correspond chaque cluster appris. Pour cela, nous suivons l’approche de (Slonim et al., 2002) et nous attribuons à chaque cluster sa classe majoritaire, c’est-à-dire la classe originale la plus représentée dans chaque cluster de documents. Nous comparons ensuite les performances des différentes méthodes, en calculant des mesures d’évaluation sur les clusters obtenus. Afin d’évaluer les résultats, nous utilisons les trois mesures d’évaluation les plus répandues en clustering de documents à savoir, la micro-moyenne de précision, le rappel, et l’information mutuelle normalisée (IMN).

Précision et Rappel

63Pour chaque classe C_l, nous avons estimé les quantités suivantes :

• ?(C_l) : Le nombre de documents correctement affectés à C_l
• ?(C_l) : Le nombre de documents incorrectement affectés à C_l
• ?(C_l) : Le nombre de documents incorrectement non affectés à C_l

La précision pour une classe est définie comme . Le rappel pour une classe est défini comme . La micro-moyenne des précisions est définie comme suit :

64

65Par définition, il est à noter que les micro-moyennes des précisions et des rappels sont égaux (Slonim et al., 2002) :

66

Information mutuelle normalisée

67Pour l’IMN, nous la calculons en normalisant l’information mutuelle entre deux partitions, l’une correspondant à l’ensemble des vraies classes, et l’autre au partitionnement à évaluer (Strehl et al., 2002). Comme la précision, la valeur de IMN est comprise entre 0 et 1 et elle est égale à 1 quand les deux partitions sont identiques.

68Pour toutes les classes, IMN est estimée en utilisant l’équation suivante :

69

70où n est le nombre total de documents, n_h est le nombre de documents dans le cluster C_h, n_l est le nombre de documents appartenant à la classe l, n_h,l est l’intersection des documents dans le cluster C_h et dans la classe l, et c est le nombre de classes dans la collection, qui est aussi le nombre de clusters dans nos expériences.

3.3 – Résultats

71Les expériences avec des nombres variés de concepts de mots sont nécessaires pour trouver le nombre de concepts donnant le meilleur résultat, et pour vérifier l’influence sur les résultats du nombre de concepts. Pour trouver l’espace de concepts par CEM nous avons varié le nombre de clusters de mots à partir de 10 jusqu’à 80 pour la collection Reuters, et de 10 à 100 pour 20Newsgroups et WebKB. Pour des valeurs plus grandes du nombre de concepts de mots, les partitions obtenues avec l’algorithme CEM comportaient des clusters vides. Nous avons donc considéré avoir atteint les nombres de concepts maximaux pour les trois collections. Pour le clustering de mots par PLSA, nous avons utilisé le même nombre de concepts que CEM. Pour le nouveau modèle, nous avons fait varier le nombre de concepts associé à y empiriquement, en considérant la taille des documents et le nombre des classes.

72Le tableau 2 montre les performances en clustering de l’algorithme CEM lorsque les documents sont représentés dans l’espace sac de mots (algorithme CEM) et dans l’espace de concepts (algorithme C-CEM) sur les trois bases Reuters, 20Newsgroups et WebKB. Sur les trois collections et dans la majorité des cas, les précisions, rappels et micro-moyennes de Précision de l’algorithme C-CEM sont supérieurs à l’algorithme CEM. De plus, le clustering dans l’espace des concepts permet de mieux identifier les classes de taille moyenne dans la collection qui sont totalement phagocytées en partitionnant les documents dans l’espace sac de mots. Ainsi avec la collection Reuters, les rappels de chacune des classes se sont tous améliorés sauf pour la plus grande classe earn. Alors que cette dernière a tendance à absorber les documents des autres classes lorsque nous faisons le clustering dans l’espace des mots, nous constatons que ce phénomène est atténué lorsque le clustering est effectué dans l’espace des concepts. Par exemple, la classe trade, qui n’a jamais été trouvée avant la réduction dimensionnelle, devient visible dans l’espace des concepts. Nous constatons des résultats similaires sur les collections 20Newsgroups et WebKB. Après la réduction dimensionnelle en utilisant les concepts, les trois classes sci., rec. et talk. de 20Newsgroups et les course, faculty et project de WebKB sont mieux extraites, et dans ce cas les améliorations sont plus grandes que dans le cas de Reuters.

Tableau 2

Mesures de précisions et de rappels (moyennées sur 10 sous-bases),micromoyenne de précision et micro-moyenne de rappel obtenues dans l’espace de sac de mots et dans l’espace de concepts par l’algorithme CEM pour un nombre de concept de mots égal à 10

Reuters Précision Rappel CEM C-CEM CEM C-CEM earn 0.77? 0.89 0.93 0.84? acq 0.43? 0.65 0.60? 0.77 money 0.35? 0.41 0.26? 0.48 crude 0.34? 0.46 0.57? 0.48 grain 0.43? 0.52 0.13? 0.54 trade 0 0.37 0 0.22 interest 0 0 0 0 Moyen 0.61? 0.70 0.61? 0.70 WebKB Précision Rappel CEM C-CEM CEM C-CEM student 0.47? 0.72 0.83 0.77? faculty 0.41? 0.55 0.21? 0.64 course 0.58? 0.86 0.36? 0.77 project 0.37? 0.45 0.10? 0.29 Moyen 0.48? 0.68 0.48? 0.68 20Newsgroups Précision Rappel CEM C-CEM CEM C-CEM comp. sci. 0.62? 0.57? 0.76 0.78 0.92 0.37? 0.87? 0.62 rec. 0.60? 0.67 0.72? 0.89 talk. 0.67? 0.84 0.50? 0.78 alt. 0 0 0 0 Moyen 0.62? 0.75 0.62? 0.75

Mesures de précisions et de rappels (moyennées sur 10 sous-bases),micromoyenne de précision et micro-moyenne de rappel obtenues dans l’espace de sac de mots et dans l’espace de concepts par l’algorithme CEM pour un nombre de concept de mots égal à 10

73La figure 2 présente les résultats du clustering de documents sur les bases Reuters, 20Newsgroups et WebKB avec l’algorithme CEM dans l’espace sac de mots et les espaces de concepts induits avec l’hypothèse

Figure 2

Précision moyenne (a) et la moyenne des IMN (b) de l’algorithme du clustering dans l’espace sac de mots (CEM) et l’espace de concepts induit par l’hypothèse (C-CEM) et PLSA (P-CEM)

Précision moyenne (a) et la moyenne des IMN (b) de l’algorithme du clustering dans l’espace sac de mots (CEM) et l’espace de concepts induit par l’hypothèse (C-CEM) et PLSA (P-CEM)

74Dans la figure 3 nous montrons les performances des modèles PLSA et sa variante PLSA-étendu (section 2.4) ainsi que la performance du modèle FMN avec la norme de Fabenius. Nous remarquons que sur les bases Reuters et 20Newsgroups, le modèle PLSA-étendu a de meilleures performances que PLSA, et ceci quel que soit le nombre de concepts choisis. Si on prend le meilleur résultat du modèle PLSA-étendu, l’écart des performances entre ce modèle et le modèle PLSA est approximativement de 7 % sur Reuters et 6 % sur 20Newsgroups. On constate les mêmes conséquences sur les moyennes des IMN. Pour la base WebKB, les performances du modèle PLSA-étendu sont presque toujours meilleures que celles de PLSA (sauf pour un nombre de concepts égal à 10). Ces résultats suggèrent que la réduction de dimension est dépendante de la dimension de départ : au moins 20 concepts de mots sont nécessaires pour obtenir de bonnes performances sur la base WebKB (pour un vocabulaire initial de 11 170 mots), alors que 10 concepts suffisent sur (pour un vocabulaire de 6 990 mots). Cette constatation empirique coïncide avec l’intuition que dans un texte, le nombre de mots a tendance à augmenter avec le nombre de thématiques qui sont abordées. Nous remarquons également qu’il y a un grand écart entre les performances PLSA et FMN avec la norme de Fabenius sur 20Newsgroups et WebKB où les tailles de la dimension de départ sont plus grandes que la taille de la base Reuters. Cette différence peut être due à l’utilisation de la norme quadratique qui n’est pas pertinente dans les grands espaces dimensionnels.

75Nous présentons finalement dans le tableau 3, une comparaison entre les différentes méthodes de clustering. Les résultats présentés dans le premier tableau sont les précisions moyennes sur les 10 sous-ensembles des collections Reuters, 20Newsgroups et WebKB. Nous avons calculé les précisions moyennes pour différentes valeurs de nombre de concepts de mots. La meilleure précision moyenne est la meilleure de ces moyennes. Le deuxième tableau représente les valeurs IMN moyennes ; celles-ci sont calculées pour le nombre de concepts de mots qui correspond à la meilleure précision moyenne. Comme le modèle PLSA n’utilise pas de concepts de mots, nous prenons seulement la précision moyenne et l’IMN moyen sur 10 sous-ensembles pour ce modèle. Pour les meilleures précisions moyennes, les approches C-CEM et PLSA ont obtenu des performances similaires, elles-mêmes supérieures aux autres méthodes dans les trois collections. Les améliorations des deux meilleures méthodes par rapport aux autres dans la collection WebKB sont plus grandes que celles dans la collection Reuters. Pour les IMNs, les deux méthodes C-CEM et PLSA-étendu obtiennent toujours de meilleures performances. Plus précisément la méthode C-CEM est légèrement meilleure que le PLSA-étendu sous la mesure de pour la collection Reuters, et inversement pour les collections 20Newsgroups et WebKB. En résumé, sur les trois collections de documents et pour les deux mesures de performances, nous trouvons que les approches C-CEM et PLSA-étendu ont des performances équivalentes, et sont toutes les deux meilleures que les quatre algorithmes CEM, P-CEM, PLSA et C-PLSA.

Figure 3

Précision moyenne (a) et la moyenne des IMN (b), performances du clustering de documents avec PLSA (?) et PLSA-étendu (?) par rapport aux performances avec C-PLSA (?) et FMN (?)

Précision moyenne (a) et la moyenne des IMN (b), performances du clustering de documents avec PLSA (?) et PLSA-étendu (?) par rapport aux performances avec C-PLSA (?) et FMN (?)

Tableau 3

Meilleure précision moyenne et l’IMN correspondant aux différents algorithmes. Les symboles ? indiquent les cas où les algorithmes ont des performances inférieures à la performance du meilleur algorithme, qui est indiquée est en gras

Measure Collection CEM P-CEM C-CEM PLSA C-PLSA PLSA-étendu Prec. moy. Reuters 20Newsgroups WebKB .61 .62 .48 .68 .69 .60 .70 .75 .68 .64 .71 .61 .69 .71 .65 .71 .77 .68 Reuters .27 .40 .44 .39 .42 .42 IMN 20Newsgroups .36 .40 .53 .49 .49 .54 WebKB .11 .28 .32 .28 .28 .36

Meilleure précision moyenne et l’IMN correspondant aux différents algorithmes. Les symboles ? indiquent les cas où les algorithmes ont des performances inférieures à la performance du meilleur algorithme, qui est indiquée est en gras