Prétraitement

Notre approche est de considérer chaque page du wiki indépendamment des autres pages. En d'autres termes, nous considérons le wiki comme une collection de documents où chaque page est un document. Nous cherchons donc à caractériser chacune des pages pour pouvoir ensuite les comparer les unes aux autres.

Le wiki étant publié en (X)HTML, la première étape consiste à extraire du (X)HTML le contenu d'intérêt : l'essence du document. Ceci se fait assez facilement en considérant le contenu de <div class="content"></div> et en supprimant tous les tags en son sein. Nous ne conservons pas pour le moment d'information de mise en forme, uniquement le contenu textuel.

Une fois cette étape de nettoyage effectuée, nous nous intéressons à la dimension lexicale du document.

Traitement lexical

Pour cette première expérimentation, nous allons uniquement nous concentrer sur la dimension lexicale du document, ie les mots qui le composent. Les mots ne participent pas tous autant au sens du texte. On différenciera les mots outils des mots clés. Les mots clés portent le sens du texte, il s'agit notamment des verbes, noms, ... les mots outils quant à eux permettent aux mots clés de collaborer entre eux afin de faire émerger le sens dans une forme syntaxiquement correcte.

Nous choisissons de sélectionner uniquement les noms communs et les verbes conjugués à l'aide d'un étiqueteur morphosyntaxique. Un étiqueteur morphosyntaxique est un outil permettant d'affecter à chaque mot son rôle grammatical (nom, verbe, adjectif, ...). Ce type d'outil va nous permettre de filtrer parmis tous les mots du texte, seulement ceux qui participent fortement au sens.

Au travers de tous les mots que nous allons ramener, certains seront graphiquement différent tout en étant sémantiquement identique (ce qui signifie qu'ils ont le même sens). Ceci est dû au fait que le français est une langue flexionnelle ...

Une langue flexionnelle est, en typologie morphologique, une langue dans laquelle les lemmes (« mots ») changent de forme selon leur rapport grammatical aux autres lemmes (Source: Wikipédia).

Ainsi, les mots cheval et chevaux portent exactement le même sens mais sont graphiquement distincts. Ils ont été construits à partir du même lemme. Le lemme est la forme graphique canonique des mots, c'est la forme graphique que vous utilisez lorsque vous faites une recherche dans le dictionnaire par exemple. Nous devons ramener les mots collectés à leur lemme afin de les comparer entre eux de manière judicieuse. Pour ce faire, nous utilisons un lemmatiseur, ie un outil qui calcule le lemme des mots.

Un lemmatiseur renverra cheval pour les mots cheval et chevaux, de même il renverra être pour les mots es, sommes ou encore sera. Nous sommes ainsi en mesure de rassembler les mots graphiquement distincts qui correspondent au même lemme. Il nous serait encore possible de faire mieux si l'on regroupait les mots qui ont des lemmes différents mais qui ont des sens proches, comme les synonymes. Cependant ce genre d'opération est plus complexe car elle nécessite des ressources lexicales importantes, telles qu'un WordNet par exemple.

En ce qui concerne la solution technique, nous utilisons l'étiqueteur morphosyntaxique et lemmatiseur : TreeTagger. Cet outil est utilisable librement dans un contexte non commerciale, j'en ai packagé une version pour Ubuntu que vous pouvez installer en ajoutant le dépôt suivant :

deb http://dl.fabienpoulard.info/distr/ubuntu hardy lina

... puis en installant le paquet pour la langue de votre choix, par exemple : ttg-french. Merci de bien respecter la licence lors de votre utilisation, cet outil n'est pas un logiciel libre !

Apprentissage non-supervisé

Nous cherchons à regrouper les pages qui partagent un lexique proche, en d'autres termes, les pages qui utilisent le même vocabulaire. Nous faisons l'hypothèse que les pages qui utilisent le même vocabulaire traitent du même thème et méritent donc d'être regroupées.

Pour le moment, nous avons, pour chaque page du wiki, les vingts lemmes les plus utilisés dans la page. Ces vingts lemmes classés par fréquence décroissante forment un vecteur de mot caractéristique de la page. Nous allons regrouper les vecteurs les plus proches d'un point de vue lexical entre eux. Pour celà, nous avons besoin de pouvoir calculer la distance entre deux vecteurs : nous avons besoin d'une métrique.

Il existe de nombreuses métriques disponibles pour comparer des vecteurs de symboles. Une liste non exhaustive est fournie par la bibliothèque SimMetrics. Nous allons nous intéresser au coefficient de Dice, métrique couramment utilisée en TAL pour comparer des vecteurs de mots. Elle est très naïve et ne donne pas de très bons résultats, notamment lorsque les pages partagent globalement le même lexique. Elle a toutefois l'avantage d'être facile à comprendre et à calculer.

Le coefficient de Dice se calcule à partir de deux vecteurs de symboles. On compare le nombre de symboles en commun et on le pondère par le nombre total de mots dans les vecteurs. Soient les vecteurs V1 et V2 : Dice(V1, V2) = (2*Termes communs) / (Nombre de termes dans V1 + Nombre de termes dans V2). L'animation ci-dessous (nécessite le support des PNG animés) montre étape par étape le calcul du coefficient de Dice sur deux vecteurs de symboles :

Calcul du coefficient de Dice

A l'aide du coefficient de Dice, nous allons pouvoir mesurer la distance entre les vecteurs de chaque page du wiki. Ceci nous permet de positionner chaque page par rapport aux autres pages. Nous allons alors regrouper les pages qui sont les plus proches les unes des autres, car nous pensons qu'elles partagent le même thème. Ce regroupement va être effectué par la méthode des K moyennes. Une exécution possible de l'algorithme des K-moyennes est illustrée ci-dessous :

Composition des clusters par l'algorithme des K-moyennes

Résultats

En résumé, nous avons caractérisé les différentes pages d'un wiki selon leurs lexique majoritaire (les 20 lemmes les plus fréquents très exactement). Nous avons ensuite mesuré la distance entre chaque page en utilisant le coefficient de Dice afin de pouvoir agréger sous forme de clusters les dites pages du wiki. L'hypothèse est que les clusters rassemblent les pages du wiki traitant d'un même thème, le cluster correspondant alors à une catégorie du wiki.

Il ne manquerait plus qu'un petit outil pour visualiser tout ça... mais pour le moment je n'ai rien qui me permettrait de visionner élégamment ce nuage de pages :S Si vous avez des pointeurs, n'hésitez pas !