Nuages de mots artisanaux

J'avais besoin il y a peu de temps d'un programme de construction de nuages de mots à la Nébuloscope pour visualiser les mots les plus fréquents dans des conversations de messagerie instantanée. C'est désormais chose faite avec Freecorp TagCloud Builder.

Ce petit programme gratuit consiste à charger une liste de mots avec leur nombre d'occurences dans un texte, fournie par exemple par l'utilitaire gratuit Dico de Jean Véronis. Après le réglage éventuel de quelques paramètres, le programme fournit une page html contenant le nuage de mots correspondant. J'ai naturellement choisi le style de nuages le plus joli que je connaisse... celui du Nébuloscope bien sûr (le code HTML des résultats du Nébuloscope est librement copiable, ça tombe bien ;)) ! Je trouve d'ailleurs très étonnant le succès des "tags clouds" ayant des styles beaucoup plus ternes, monochromes sur le site del.icio.us par exemple.

Passons un peu à la description des fonctionnalités du programme avant d'évoquer un problème technique. Le résultat du programme Dico appliqué sur un texte est une liste de mots au format texte détaillé ci-dessous :
N'importe quoi sur la première ligne
mot_le_plus_fréquent Nombre_d'occurences
deuxième_mot_le_plus_fréquent Nombre_d'occurences
...
(l'espace entre un mot et son nombre d'occurences étant en fait une tabulation)

Par exemple pour les mots les plus fréquents dans les avis cinéma de Monique Pantel (critique ciné dans l'émission On va se gêner de Laurent Ruquier sur Europe 1) :
Forme Fréquence
FILM 689
BEAU 149
PETIT 144
VOIR 142

Vous devez alors choisir le nombre de mots que vous voulez afficher dans le nuage (100 par défaut) et la largeur du nuage (300 pixels par défaut). D'autre part, les mots seront cliquables, un clic conduit sur une recherche Google de ce mot sur le site de votre choix, que vous pouvez configurer : c'est celui de la Wikipedia par défaut. La page web contenant le nuage est enregistrée par défaut dans le nom de fichier source, suffixé d'un ".html", et son code source s'affiche sur la fenêtre du programme, vous pouvez le copier/coller librement où vous voulez.

Un dernier paramètre est réglable, l'échelle. Ce réglage constitue le principal ennui technique des nuages de mots. Jean Véronis a apparemment réussi à le régler de façon admirable puisque les nuages font toujours bien apparaître en rouge/orange les mots les plus fréquents : ni trop ni pas assez. Il s'agit en effet de choisir à quelles plages de fréquences des mots on associe telle ou telle taille ou couleur dans le nuage. Supposons qu'on veut faire le nuage des 100 mots les plus présents, le plus présent l'étant 90 fois et le moins présent 40 fois. Sachant qu'il y a 10 variations possibles de taille/couleur, une stratégie pourrait consister à découper en 10 parties égales l'intervalle [40,89] des nombres d'occurences des 100 termes les plus présents. On écrirait donc en rouge et gras tous les mots présents entre 85 et 89 fois. En gris tout petit les mots présents entre 40 et 44 fois.

Mais rappelons-nous : les mots dans un texte sont généralement présents selon la loi de Zipf : peu de mots très présents, beaucoup de mots peu présents. D'un autre côté notre nuage doit aussi refléter cet effet, sans l'exagérer. Mais voilà ce qui se passe sur les avis de Monique Pantel si l'on choisit cette solution (image de gauche) :
Il faut donc renforcer un peu le poids des termes peu présents. J'ai donc essayé de considérer non pas les intervalles, mais les intervalles "passés à la racine", ce qui donne l'image de droite. Mieux, mais encore pas ça.

Quand on "passe les intervalles au log", on obtient un résultat à peu près satisfaisant qui montre bien l'enthousiasme de Monique pour certains films :
Ca reste toutefois peu robuste, et je réfléchis donc à une solution alternative, qui découperait l'intervalle des nombres d'occurences de façon "intelligente" par un algorithme de clustering des nombres d'occurences en 10 classes.

Voilà pour finir le nuage des 300 mots les plus fréquents dans les critiques de Monique Pantel de ces deux dernières années grâce à Dico et Freecorp TagCloud Builder !

Croissance quadratique des traductions européennes

Emission très intéressante sur Europe 1 hier, annoncée par Jean Véronis la semaine dernière. En bonus de la discussion sur la cyberlangue qui sera certainement approfondie dans un livre comme évoqué en fin d'émission, le co-animateur Nicolas Delourme évoque à la mi-temps l'explosion des demandes en traduction des institutions de l'Union Européenne (traductions effectuées par la Direction Générale de l'Interprétation) avec l'élargissement, déjà évoqué par exemple dans un article de La Libre de 2003.

Et là les mathématiques sont un poil malmenées. Nicolas Delourme commence par citer les langues actuellement gérées : anglais, allemand, français, italien, espagnol, néerlandais, grec, portugais, sudéois, danois, finnois et depuis l'élargissement de 2004, estonien, hongrois, letton, lituanien, maltais, polonais, slovaque, slovène et tchèque.

Pour calculer le nombre de sens de traductions, c'est simple, on a 20 langues-sources à traduire, et pour chacune 19 possibilités de langue-destination, soit 380 possibilités. Ce qui nous donne, pour n langues, n(n-1) possibilités de sens. Au passage, dommage que les interprètes/traducteurs ne soient apparemment pas parfaitement billingues, ce qui diviserait ce nombre par deux (il faut d'après ce calcul un interprète du français vers l'anglais, et un autre de l'anglais au français). De toute façon la croissance du nombre de sens de traductions en fonction du nombre de langues est quadratique (proportionnel au carré du nombre de langues) et pas exponentiel comme le dit Nicolas Delourme :

"Et comme le nombre de possibilités, pour utiliser un terme qui va plaire à Jean Véronis, comme le nombre de possibilités est exponentiel, à chaque fois que l'on rajoute une langue, la DGT doit aujourd'hui faire face à 380 combinaisons possibles, aussi bien en traduction de texte qu'en interprétation de discours."

Alors évidemment, le terme "exponentiel" est certainement plus parlant que "quadratique" pour évoquer une hausse importante. Mais il faut bien avoir à l'esprit qu'une complexification quadratique (ou même polynomiale) d'un problème par rapport au temps est tout à fait maîtrisable, grâce par exemple à la loi de Moore, qui nous promet que nos moyens de calculs bénéficient d'une croissance exponentielle : les performances sont doublées à peu près tous les 2 ans, les prix divisés par deux dans la même période. Et même plus généralement que cette "loi" qui s'applique typiquement sur le champ restreint du matériel informatique, on attend généralement du chiffre d'affaire d'une entreprise, ou du PNB d'un état, une croissance constante en pourcentage, soit une valeur en hausse exponentielle par rapport au temps.

Ainsi, tant que chaque langue ne donne pas naissance à 2 langues-filles à chaque décennie (ce serait rigolo, que la communauté européenne multiplie le nombre de ses langues par deux en considérant la version SMS de chacune...), le budget nécessaire à la traduction gardera une progression quadratique tout à fait gérable.

Evidemment, l'existence de la loi de Moore ne constitue pas un prétexte pour se dire qu'il est inutile de chercher à faire des économies en étant plus efficace, et le système de langues pivots qui consiste à avoir une traduction en deux temps (3 interprètes pour la langue actuellement parlée, un vers l'anglais, un vers l'allemand et le troisième vers le français, ainsi qu'un interprète d'une de ces trois langues vers chacune des 19 langues) est intéressant dans l'optique d'une économie de moyen (même s'il est nécessaire en pratique pour éviter de rechercher des interprètes du lettonien au portugais...). Mais le résultat du calcul mentionné par Nicolas Delourme est erroné, il compare les 380 possibilités des traductions exhaustives, à 60 dans le cas des langues-pivots (détail sur le travail des "interprètes relayeurs" page 9 de ce document) :

"Ce procédé permet déjà de limiter le nombre d'interprètes à 60 pour un régime complet de traduction. [...] 60 interprètes seulement pour 380 combinaisons possibles."

En fait, il faut pour chacune des 20 langues une traduction vers l'anglais, l'allemand et le français, ce qui donne 60, moins les traductions anglais-anglais, allemand-allemand, et français-français, ce qui fait 57. Et une fois que les traductions dans les trois langues pivot ont été obtenues, il faut les traduire vers seulement 17 langues, ce qui donne 57+17*3=108. De façon plus intelligente, on peut même traduire seulement l'une des 3 langues pivot vers une des 17 autres langues, soit un résultat total de 57+17=74 sens de traduction différents.

Cet exemple est typique d'erreurs que l'on peut faire lors de calculs de probabilités ou de combinatoire qui semblent très simples apparemment, mais qui s'avèrent cacher des cas particuliers ou des répétitions à considérer... Quoi qu'il en soit, ces calculs sont seulement théoriques puisqu'on n'emploie pas exactement un traducteur par sens de traduction comme expliqué dans l'article de La Libre...

McDonald's, MacDo, Mac Donalds, et Voronoï

Je suis allé manger indien cette semaine (en fait c'était il y a 3 semaines. Mais bon, c'est juste une phrase introductive, hein, et on écrit pas, dans un blog, j'ai fait ceci-cela il y a 3 semaines...). Un Indian Maharadja et ses saveurs envoûtantes. Eh oui, Mac Do a encore frappé pour se démarquer un peu de la concurrence, agrémentant ces nouvelles recettes temporaires de petites vidéos publicitaires sur le net.

Mais MacDo ce n'est pas seulement ça. C'est aussi une chaîne qui arrive toujours à se placer dans les coins les plus chics/pratiques de nos villes françaises j'ai récemment profité du délicieux McDonald's du centre-ville narbonnais, ainsi que de celui très pratiquement situé juste en face de la gare à Montpellier). Qui nous impressionne quand on suit le ballet efficace des serveurs. Qui nous enchante avec son wifi gratuit (enfin faut pas pousser, on nous demande gentiment de ranger notre ordi s'il y a trop de monde). Et qui nous surprend avec son coin café dans le resto de l'avenue des Champs Elysées aux prix défiant toute concurrence aux environs.

Avec tant d'avantages, on comprend que connaître en permanence le McDo le plus proche est une nécessité. Surtout à Paris. Voilà donc le diagramme de Voronoï (la précision n'est pas excessive, hein) des restaurants Mc Donald's à Paris (les points rouges) :

Evidemment, comme j'ai été un peu large sur la précision, les distances sont les simples distances à vol d'oiseau, et j'ai utilisé l'applet Java de Paul Chew (ainsi qu'une technique de "décalquage";)). On pourrait s'amuser à le recalculer en utilisant comme distances celles vraiment parcourues à pied à travers les rues de Paris.

J'ai ajouté quelques repères en vert pour situer un peu les restaurants, et les couleurs d'arrière-plan correspondent bien sûr aux arrondissements. J'aurais bien aimé inclure une carte satellite en fond pour en faire une jolie version imprimable utile. Mais pour des raisons de droit d'auteur, je laisse les heureux possesseurs de Microsoft PowerPoint >97 ouvrir ce fichier source du diagramme de Voronoï des McDo, et coller en arrière-plan la bonne carte Google de Paris dont ils auront préalablement fait une copie d'écran, puis la redimensionner un peu pour qu'elle colle au dessin.

Le diagramme a une autre application, prédire où les prochains Mac Donald's risquent d'être implantés à Paris. En effet, il est préférable de les mettre dans des grandes alvéoles de Voronoï, si possible sur une des frontières, ou mieux, à un point où elles sont concourantes. Je prédis donc que McDonald's achètera prochainement les Invalides, le Palais de l'Elysée, la Bibliothèque François Mitterrand...

Pour finir sur Mc Do, une petite remarque sur les formes orthographiques de la marque. Déjà vous remarquez que la société a pris soin de référencer plusieurs formes en les incluant comme mots-clés de sa page d'accueil, comme on peut le voir dans les résultats Google :
McDonald's France, restauration rapide
... plan des restaurants, offres d’emploi, offres de stage, fondation Ronald McDonald, Mac Donald, Mc Donald, McDonald, Mac Donald’s, Mac Donalds, Mc Do ...www.mcdonalds.fr/

Et si on compare les diverses formes (entourées de guillemets bien entendus) par rapport au nombre de résultats dans Google ou Yahoo, ainsi que les résultats limités aux pages françaises, on apprend... que l'abréviation McDo (ou Mc Do, ou Mac Do ou MacDo) est typiquement hexagonale ! Je vous laisse apprécier le joli camembert couronné exécuté dans OpenOffice (mon pauvre Microsoft Office 97 n'arrive pas à le faire, ça...) :

Quand la loi de Zipf atteint le nombre des années...

J'ai étudié le nombre de résultats Yahoo (parce qu'on sait bien que Google pour faire des stats c'est mââl) pour tous les nombres à 4 chiffres entre 1901 et 2006, et la loi de Zipf semble pointer le bout de son nez. En effet le nombre de résultats n(x) semble inversement proportionnel au nombre x recherché. Pour visualiser cela un peu mieux, je trace non pas la courbe de n(x), mais celle de 1 000 000 000/n(x), en pensant obtenir à peu de choses près une droite. Au passage, je ne représente pas les valeurs pour x divisible par 10, puisque ces nombres sont généralement beaucoup plus présents sur le web que leurs voisins, et créent donc du bruit dans les données obtenues (du bruit, étant donné l'utilisation qu'on veut en faire, cf ci-dessous). Voilà le résultat obtenu, avec en violet la droite de régression linéaire de ces points (merci OpenOffice Calc) :

On peut remarquer que globalement, les points sont bien proches de cette droite, à part après 2006. Mais en zoomant un peu plus, on voit que le comportement diffère entre 1995 et 2006. C'est donc plutôt deux segments de droite qui semblent décrire le mieux les valeurs obtenues, entre 1901 et 2006.

Je m'attendais à visualiser plus clairement certaines "années clé", comme 1914, 1918, 1939, 1945... C'est en effet le cas pour 1945 qu'on voit plus bas que prévu (étant plus cité sur le net que 1944 ou 1946), ou 1901 (vive la loi sur les associations !).

Bon, et maintenant, quelle utilité à cette remarque ? Eh bien justement à évaluer la pertinence des résultats chiffrés des moteurs de recherche pour faire des statistiques. Il s'agira tout d'abord de déterminer expérimentalement quelle loi semble la plus correcte (par exemple : il y a forte corrélation entre 1/x et le nombre de pages sur internet contenant le nombre x pour x allant de 1901 à 1994, avec x non divisible par 10). Si ça semble effectivement être le cas sur tous les moteurs, le coefficient de corrélation trouvé permettrait d'évaluer la qualité du moteur pour une utilisation statistique (notamment de calcul de la NGD).