12 décembre 2007

tag cloud + tag tree = nuage arboré (1)

Vous avez déjà travaillé avec deux objets, pour vous rendre compte que combinés ils fonctionnaient vachement mieux ? C'est la vraie révélation du dernier article de Jean Véronis sur Aixtal !
Après lecture de son blog ou du mien, vous êtes convaincus qu'un nuage de mots dont la taille (et la couleur, j'apprécie beaucoup les teintes rouges, oranges, et bleues du Nébuloscope, introduites en partie chez TagCloud) reflète la fréquence, c'est très utile pour donner un aperçu rapide d'un texte ou d'un corpus. Vous êtes tout autant convaincus qu'un arbre phylogénétique peut donner un aperçu rapide de relations entre des mots-clés. Et quand on mixe les deux ? Je cite : "c'est marrant les arbres... ils peuvent nous raconter des histoires". Et voilà, un nouvel outil de visualisation d'histoires !

Dans l'exemple dédié à Laurence Ferrari, ce sont les résultats Wikio qui sont "passsés à la moulinette". Mais de la même façon qu'on peut effectuer un nuage de mots depuis un simple texte (avec TagCloudBuilder et une échelle de coloriage logarithmique bien sûr !), j'ai l'impression qu'un nuage arboré (tree-cloud pour nos amis anglophones) est encore un meilleur moyen d'avoir un aperçu rapide d'un texte. L'ordre alphabétique complètement artificiel des tags dans le nuage est remplacé par une disposition hiérarchique intuitive et informatrice !

Alors maintenant, quelle distance entre mots choisir pour reconstituer l'arbre, sur un simple texte ? J'ai fait l'essai suivant : pour chaque paire de mots, leur distance mutuelle est égale au log du nombre de mots minimal qui les sépare. J'avais déjà tenté de commencer à justifier théoriquement l'introduction du log pour certaines reconstructions "phylogénétiques" (la seconde partie du billet est toujours dans les cartons), là je l'introduis a priori seulement pour éviter quelques trop longues branches. J'ai prévu de tester quelques améliorations de cette idée : nombre de mots moyen séparant la paire de mots, éventuellement seulement sur les occurences les plus rapprochées de la paire...

Je garde ces préoccupations pour un éventuel billet suivant, et je livre un exemple d'application de ce principe, tiré du premier texte de longueur convenable que j'avais sous la main, une interview en anglais de Tom Sharpe. L'heure tardive ne me permet pas de mixer arbre et nuage de mots, les voici donc, à mixer mentalement (pour le moment) :
Pour la construction de l'arbre, j'ai gardé seulement les mots présents plus de 3 fois, et contrairement au nuage de mots, n'ai pas enlevé les mots très présents peu porteurs de sens (I, the, to, l'antidico quoi...), qui ne gènent pourtant pas vraiment dans l'arbre (is, of, in, the, he arrivent au niveau du centre).

Le choix de la distance conduit à certains rapprochement un peu artificiels, toutefois la plupart des sous-arbres ont un sens. Soit constitués justement de mots de l'antidico, donc à négliger, soit reflétant les principaux thèmes de l'article. En particulier le sujet général apparaît dans le sous-arbre {village,where,Tom,Sharpe}. Afficher le contexte au passage de la souris sur une feuille ou un sous-arbre serait donc particulièrement intéressant.

Du travail en perspective, donc. A suivre sur ce blog... et sur treecloud.org !

Les fichiers sources des images ci-dessus : fichier Nexus de l'arbre phylogénétique, mots et occurences, mots et occurences avec anti-dico manuel, nuage de mots de TagCloudBuilder, programme de construction de la matrice de distance format Nexus et source Delphi peu commenté pour l'instant.

8 commentaires:

Jean Véronis a dit…

Très intéressante discussion, Philippe. Oui, c'est exactement ça: un mix entre les nuages et les arbres. Je n'ai pas ajouté d'information de couleur dans l'arbre parce que je trouve que c'est trop. La redondance aide dans les nuages, mais on n'y a qu'une info. Ici on a en deux : la fréquence et la cooccurence. Une variation de couleur redondante avec la seule fréquence me semble difficile à lire.

Mon idée est de lui faire porter une autre information, je te le donne en primeur, parce que je n'ai pas encore posté là-dessus : la fraîcheur de l'info. Le plus vif correspondra aux dernières news, le plus pastels aux plus anciennes. J'ai fait des essais c'est très parlant (mais il me reste quelques réglages, notamment d'échelle: fait-on du log dans le temps? etc.).

En passant: les couleurs du Nébuloscope n'étaient pas inspirées de Yahoo mais de TagClouds. J'ai toutefois ajouté un niveau maximal, le rouge, qui n'était pas présent dans les couleurs initiales et qui me paraît important pour une lecture instantanée du "topic". J'ai aussi ajouté (mais je ne le fais apparaître que sur certains nuages) un niveau 0, qui est un gris minuscule à peine lisible (histoire de signaler : ne vous fatiguez pas à lire, mais il y a encore plein d'autres mots).

Par ailleurs, oui, on peut faire ça sur n'importe quel texte. C'est ce que je fais sur les discours politiques par exemple. J'ai un poste en préparation, que je n'ai jamais eu le temps de finir, sur l'arbre du travail chez Ségo et chez Sarko.

Petite remarque sur la cooccurrence, et le calcul d'une distance entre deux mots présents dans un texte. On peut utiliser une fonction qui reflète cette distance, mais j'ai fait des tonnes d'essais et c'est inutilement compliqué. J'utilise une bonne vieille fenêtre de x mots (ça dépend de la taille globale du corpus et ce qu'on veut visualiser, généralement 10 à 30. Ce qui éclaircit par contre drôlement la forêt, c'est l'élimination des mots-outils (articles, prépositions, etc.) qui polluent pas mal la situation sur tes exemples.

Au fait, ce nuage dynamique des coocurrences de mots dans une fenêtre, c'est déjà exactement ce que je faisais avec la fonction Voisins dans Discours 2007.

Exemple:

Travail (Ségo)
Travail (Sarko)


Un grand merci pour ta réaction passionnante !

Philippe a dit…

Merci pour toutes ces petits secrets de fabrication (je corrige dans le billet l'info sur la source des couleurs) ! Effectivement l'idée de cooccurence dans une fenêtre glissante semble bien meilleure.

Pour l'antidico effectivement il est nécessaire, je voulais juste voir où s'inséraient dans l'arbre ces mots "inutiles" en utilisant ma distance.

J'ai hâte de voir tes futures productions en tout cas. Je commence à rêver de parcourir l'actualité en cliquant sur un mot-clé d'un nuage arboré, ce qui ouvrirait le nuage arboré de ce mot-clé, etc...

Jean Véronis a dit…

En fait, ce qui freine le développement de tels outils c'est la disponibilité et la coopération des moteurs. Pour le Chronologue et le Nébuloscope, j'avais eu la chance de pouvoir travailler avec Dir (qui est mort depuis, hélas). Pour Wikio, ce serait extrêmement simple de mettre ce genre d'outil (ou tout bonnement des nuages interactifs façon Nébuloscope) en ligne. Quelques jours de boulot et de réglage tout au plus. Mais il faut pour cela une API du côté du moteur, qui permette de récupérer un nombre important de résultats d'un coup (et non 1à à la fois), sinon c'est impraticable en temps réel.

Bref, c'est rarement la priorité chez les moteurs. Par exemple, je n'ai pour l'instant pas trouvé de remplaçant à Dir pour faire fonctionner le Nébuloscope et le Chronologue.

CédricG a dit…

Excellent vos discussions. Webmestre d'un forum et passionné par l'organisation de la connaissance je me pose la question d'appliquer des techniques dérivées de ce que vous présentez sur les messages postés par les membres, afin d'exprimer de manière automatisée une information pertinente si possible.

Merci à tous les deux en tout cas!

Philippe a dit…

@cédricg : tu t'y connais un peu en programmation PHP+SQL ? Parce qu'il serait alors tout à fait possible d'interagir avec ta base de données pour récupérer les posts et faire passer ces moulinettes derrière. Je peux te détailler les algos si tu veux les recoder en PHP... D'ailleurs je ferai peut-être un post de synthèse sur le sujet, une fois que j'aurai fini de programmer toute la chaîne en Delphi (il reste la partie création et dessin de l'arbre).

CédricG a dit…

Oui, c'est même mon métier, et accessoirement ma passion.
En fait j'ai commencé à développer un forum pour remplacer mon vieux phpBB simplement parce qu'il est trop galère à modifier et que je tiens à l'adapter.
Pour y mettre un modèle de donnée, un wiki interne, des tags autour desquels les messages et les pages wiki seraient regroupés, et ainsi de suite.
Au premier niveau ce genre d'analyse me semble pouvoir donner (peut être au prix de gros calculs) une indexation plus pertinente que les méthodes classiques.
Au second niveau, c'est un arbre de connaissance qui m'intéresse.

CédricG a dit…

Oups, cliqué un peu vite (ça m'apprendra à saisir d'abord le CAPTCHA).

Si en effet tu peux détailler quelques uns des algos je serais vivement intéressé par leur étude. Merci!

Philippe a dit…

Quelques réflexions sur les algos. Déjà tu as besoin d'une structure de données qui te permette de stocker une liste de mots, avec pour chaque mot un truc associé (un entier, une liste...). Elle doit permettre un accès rapide à chaque mot. Cette structure, c'est si je me souviens bien un HashSet en Java, un dictionnaire en Python, en Delphi je l'ai programmé par un arbre où chaque arête est étiquetée par une lettre, la racine indique le début du mot et les feuilles la fin du mot. En PHP, je n'ai aucune idée sur la structure à utiliser pour faire ça...

Cette structure de données va permettre de stocker : pour chaque mot du texte fourni en entrée son nombre d'occurences ou bien la liste de ses occurences. Elle permettra aussi de stocker la "stoplist".

Etape 1 (éventuelle) : remplacer tous les signes de ponctuation du texte en entrée par des espaces

Etape 2 : pour chaque mot, séparé par des espaces, l'insérer s'il n'existe pas encore dans le dico, et qu'il n'existe pas dans la stoplist incrémenter son nombre d'occurences, ou ajouter à sa liste d'occurences sa position dans le texte (1 pour le premier mot, etc...).

Etape 3 : récupérer une liste de mots les plus fréquents. A toi de voir si tu choisis de fixer un seuil sur le nombre d'occurences, ou bien si tu choisis de garder les k=100 par exemple plus fréquents.

Etape 4 : construire le nuage de mots. Pour cela il faut affecter une taille à chacun des k mots plus fréquents, càd un entier de 1 à 10. La formule que j'utilise et qui marche bien, c'est avec un log, en notant nbmin le nombre d'occurences de celui des k mots qui apparaît le moins, et nbmax le nombre max d'occurences : entierinférieur(1+9,99999*
(log(nboccurences)-log(nbmin))/
(log(nbmax)-log(nbmin))).

Etape 4 : construction de la matrice des distances entre mots. Là encore ça dépend de la distance utilisée, voir discussion ci-dessus.

Etape 5 : construction de l'arbre à partir de la matrice des distances. Méthode UPGMA ou Neighbor-Joining (cf wikipedia).

Etape 6 : dessin de l'arbre, je détaillerai quand je l'aurai implémenté, même si l'algorithme EqualAngle est simple, il n'est apparemment pas disponible sur internet et nécessite une bonne demi-page de baratin.

Etape 7 : placement des étiquettes (où on peut, à proximité de la feuille associée, en gros) et coloriage, en utilisant les couleurs et tailles du nuage de tags.