mardi 10 juin 2014

Transfert réussi !!

Pour des raisons techniques j'ai décidé de faire transférer mon blog professionnel sur Blogspot. Cela ne changera rien à son contenu, vous y trouverez toujours des ressources pour mes cours algorithmique, réseaux neuronaux,  projets étudiants et projets de recherche  ...

Merci aux étudiants : Serre Kevin, Al Hakawati Mouaz et Fabbro Alexis pour leur travail.

dimanche 1 juin 2014

Analyse Sémantique Automatique



Analyse Semantique automatique from Hubert Wassner on Vimeo.


La sémantique est la science qui s'intéresse au sens des mots. C'est un défi majeur des technologies de l'information, tout simplement parce que la notion de sens attaché à un mot est implicite lors de n'importe quelle requête d'un utilisateur. Le problème est qu'informatiquement c'est difficile à gérer. Heureusement, dans de nombreux cas, on peut se satisfaire d'une mesure de distance sémantique. C'est à dire mesurer la similarité de sens de deux mots. Il est possible de mesurer automatiquement ce type de distance. (Cf. L'article original : « Automatic Meaning Discovery using Google » , Paul Vitanyi et Rudi Cilibrasi). Ainsi, pour une liste de mots donnés on peut mesurer les distances qu'ils ont les uns par rapport aux autres, et créer une « carte ». ...
Cette technique nous a déjà permis de générer deux cartes, une cartographie de bloggeurs, et une cartographie d'auteurs. Aujourd'hui nous avons réalisé une cartographie sémantique de métiers, pour le compte de Meteojob (nouveau site d'offres d'emplois). L'objectif est de faire un système de « intelligent » capable de « comprendre » la similarité entre deux intitulés de métier tels que : « marbrier » et « tailleur de pierre ».


Si cet article vous a plus merci de voter (sur le site wikio) en cliquant sur cette icone.

1er TD sur les réseaux neuronaux



L'objectif de ce TD est de faire une première prise en main intuitive de l'utilisation de réseaux neuronaux (simpliste) avec une interface graphique puis une première mise en pratique via un programme en langage C.

Partie 1
Nous allons tout d'abord, utiliser cet applet : http://www.sund.de/netze/applets/BPN/bpn2/ochre.html de manière classique, c'est à dire, ce pour quoi il a été construit : reconnaître les chiffres de 0 à 9.
Dans un deuxième temps (une fois que vous aurez compris ce que ça fait et comment ça marche), vous allez modifier les donnés d'apprentissage pour que le réseau apprenne à reconnaître une croix (x) d'un rond (o). Vous pouvez modifier les données d'apprentissage en cliquant dessus (clic gauche ajoute un point, clic droit en supprime, 'c' remet le digit à 0. Voici les concepts qui seront illustré par cet exercice.
  • Notion d'apprentissage, et de mesure d'erreur via matrice de confusion
  • Notion de de généralisation. (essayer de faire reconnaître différent type de digit)
  • Notion de différent type de variabilité des données. (inter et intra-personnelle)
Partie 2
Nous allons ensuite apprendre à réaliser un apprentissage de réseau de neurone à partir d'un programme en langage C, utilisant une librairie. La librairie que nous allons utiliser FANN , elle est déjà installée dans les salles de TP. Pour commencer avec un exemple de base vous trouverez, presque tout, sur cette page. Une fois que vous aurez réussi à entraîner (et tester) un réseau sur la fonction XOR à 2 entrés, modifiez ces codes de manière a le faire avec un XOR à 3 entrés.
À l'issue de cet exercice vous aurez normalement compris ce qui est nécessaire pour construire un réseau, l'entrainer, et l'utiliser.

Partie 3
(Selon votre vitesse d'avancement , cette partie pourra être repoussée au TD suivant).
Attention : une erreur s'était glissé dans le lien vers les donnés, téléchargez à nouveau les donnés pour être sur d'avoir les bonnes valeurs.
En utilisant la libraire FANN, faites un programme qui détecte des cellules cancéreuse.Voir le contexte de l'étude ici, ainsi que la description des donnés. Vous trouverez les données nécessaire ici. Il y aura bien sûr une discussion pour savoir comment transformer ces données de manières à ce qu'elles soient utilisable par un réseau de neurones. Avec cet exercice vous aurez compris (normalement) la formalisation exigé par l'utilisation de réseaux de neurones.

Conclusion
à l'issue de de ce TD j'espère que avez une idée plus précise de ce qu'est un réseau de neurones par la pratique. Vous aurez peut être l'impression d'avoir tout vu, mais attention c'est une illusion car pour le moment on n'a pas encore réellement aborder les points critiques de cette technique : l'analyse d'erreur. Soyez en sûr les réseaux que nous avons crées ici sont finalement très très imprécis, malgré nos tests. Nous avons sauté un tas d'étapes qui sont primordiales à la création d'un réseau de neurone réellement fonctionnel. Nous verrons cela en cours et dans les TD suivants...

Annexe(s) :

(Le compte Twitter de) Bixenté Lizarazu mis à nu



J'ai testé mon nouvel algorithme sur un échantillonnage de plus de 900 followers du compte Twitter de Bixenté Lizarazu, et j'en ai produit une cartographie. Assez naturellement il y a beaucoup de followers qui sont des fans de foot, mais il y a aussi beaucoup de fans de "peoples". Grâce à cette cartographie on peut on répondre quantitativement à la question : « Bixenté Lizarazu, footballeur ou people ? »...
Dans cet article je me contenterai de décrire les résultats produits sur le compte Twitter de Bixenté Lizarazu. Si vous êtes curieux de la méthode employée, voyez cet autre article qui fait une analyse du compte Twitter de Korben (blogueur geek "connu") et qui explique un peu plus l'algorithme de construction de la carte.

Cliquez sur l'image pour l'agrandir Cliquez ici pour télécharger la carte en PDF 



Première chose étonnante c'est que l'algorithme dispatche les fans de foot sur 5 zones différentes....

"Les Footeux"
Je comprend le sens d'une partie de ce découpage, il y a ceux qui suivent d'abord les journalistes de foot et leur émissions , c'est le plus gros regroupement : 18% (en haut à droite sur la carte).
Voici les lectures caractéristique de ce groupe : PierreMenes CanalFootClub MATUIDIBlaise lequipe MathouxHerve BafGomis kevingameiro9
Puis il y a les 4 zones qui occupent la partie du milieux et inférieure droite de la carte, 3.2% + 9% + 3.9% + 15.1% = 31.2% les lecteurs semblent chercher leur informations directement auprès des comptes Twitter des joueurs.. Voici les lectures caractéristique de ce groupe :

10Ronaldinho DaniAlvesD2 Carles5puyol andresiniesta8 3gerardpique XabiAlonso DiegoForlan7

FCBayern dante_bonfim David_Alaba ToniKroos LGustavo_30 Javi8martinez XS_11official
IAmJermainDefoe premierleague rioferdy5 21LVA usainbolt WayneRooney GNev2
kobebryant KingJames lequipe VincentKompany CP3 hazardeden10 nicolas88batum

C'est peut être pour cette raison que le lectorat est « divisé » en fonction des équipes pour lesquelles ils jouent. Je ne m'y connais pas en foot, je ne peux donc pas tester cette hypothèse. Si vous avez un avis sur la question n'hésitez pas à en faire part via les commentaires. Ou directement via Twitter
Et voici le dernier groupe relié à la thématique foot, les « footeux modérés », ils sont 22.6%. Ils ont en commun ces lectures : PierreMenes gadelmaleh Cyrilhanouna debbouzejamel MichaelYoun dubosc_franck lequipe. En regardant en détail, on voit que c'est des gens intéressés par le foot, mais pas uniquement. Le foot n'est pas l'unique thématique de leur compte.
On arrive donc à total de ~72% de followers du compte de Bixenté Lizarazu qui sont fan de foot, mais alors qui sont les autres ?

Les autres...
« les multisport », (dont Bixenté fait lui même parti), ils représentent 12.1% du total, ils lisent les sujets suivants : lemondefr michel_denisot stephaneguillon Bruce_Toussaint lequipe sebchabal PierreMenes
Les « pur people » 15,9%
La thématique de ces comptes n'est pas uniquement « people » mais, en tout cas c'est l'unique point commun des gens dans ce groupe. L'algorithme a séparé ce groupe en deux, les « peoples » français, et les américains.
10.8 % suivent : EmoireOff JeniferOfficiel KarineFerri Arthur_Officiel LorieOfficiel AudreyLamy amel_bent
5.1% suivent OfficialAdele justinbieber taylorswift13 aliciakeys katyperry jtimberlake CodySimpson
Il est intéressant de remarquer qu'il y a beaucoup de filles dans ces groupes (en tout cas plus que dans le groupe des "footeux").

Conclusion
Assez naturellement une vaste majorité des followers de Bixenté Lizarazu sont des fans de foot, environ 70%, cependant ils sont hétérogènes pour le reste de leur lectures. Le plus intéressant c'est les autres... Un total de 28% qui ne sont pas à proprement parler des fans de foot, en tout cas 15.9% ne sont probablement jamais allé voir un match, et sont clairement plus centré "people" que "footeux".
Pour simplifier, Bixenté Lizarazu, est en partie, vu sur Twitter comme un "people" ou tout du moins 15% des gens qui s'intéressent à lui sur Twitter ne s'intéressent pas du tout au foot.
Annexe(s) :

L'algorithme pagerank comment ça marche ?


Pourquoi est-ce important ? La plupart des gens utilisent des moteurs de recherche pour trouver ce qu'ils cherchent sur internet. Tout site internet se doit donc d'être bien être référencé, sinon il n'aura aucun visiteur. Choisir les bon mots clés est relativement facile, par contre avoir un indice pagerank élevé est plus compliqué. L'indice pagerank est ce qui définit la position dans les page de résultat des moteur de recherche (pour google évidement, mais les autres moteurs utilisent maintenant plus ou moins le même genre d'algorithme). Il est donc très important de bien comprendre le fonctionnement de ce type d'algorithme pour espérer apparaître sur la première page de résultat (la seule lue dans 95% des cas) ou au moins figurer parmi les premiers. Je vous propose dans ce billet d'éclairer le fonctionnement de cet algorithme ainsi qu'un applet Java permettant d'expérimenter ce type d'analyse. Il s'agit bien sur d'une version simplifiée, mais cela permet de comprendre quand même beaucoup de choses...

(Pagerank du blog : PageRank Actuel )
Normalement est apparu une fenêtre contenant la démo' interactive, si ce n'est pas le cas activez Java sur votre navigateur.(Java 1.5)
Pour directement voir la documentation d'utilisation du programme cliquez ici.

Petit historique
Les premiers moteurs (altavista ou yahoo) ne faisaient qu'indexer, c'est à dire trouver toutes les pages contenant le ou les mots clés recherchés. On pouvait retrouver les pages contenant un mot clé donné mais les résultats n'étaient pas triés efficacement. Le nombre de fois où apparaissait le mot clé faisait apparaître la page en haut de la liste de résultat, ce qui n'est pas pertinent. Le nombre de répétions du mot clé n'est pas un critère intéressant car aisément falsifiable. Il faut faire une analyse plus fine du web pour être capable de mesurer automatiquement l'importance de chaque site. Sergey Brin et Lawrence Page, étudiants à standford on trouvé une solution aussi originale que simple : utiliser l'information des liens entre les pages pour mesurer l'importance des sites, et être alors capable de classer correctement les résultat d'une recherche de mots clés. Cet algorithme s'appelle le « pagerank », il est finalement assez simple (niveau deuxième année d'étude supérieure, je le propose d'ailleurs dans mon cours). Sergey et Lawrence ont créé l'entreprise Google qui est alors le meilleur moteur de recherche du web. Google est devenu très rapidement (et sans aucune publicité) un des moteurs les plus influant du web, les autres (yahoo etc...) on rapidement suivit, mais bien sur cette avancé technologique leur à a permis d'être les « first to market » et donc de prendre une longueur d'avance sur la concurrence... Google essaye de garder cet avantage, en proposant toujours de réelles avancées technologiques, et bien sûr en améliorant l'algorithme pagerank qui est devenu un secret industriel aussi bien gardé que la fameuse recette exacte du coca-cola. La version que j'expose ici reste est une approche à la fois simple et instructive pour comprendre les bases du référencement vu que maintenant tous les moteurs de recherche utilisent des variantes de cet algorithme.

Le pagerank, comment ça marche ...
L'algorithme pagerank calcule un indice de popularité associé à chaque page web. C'est cet indice qui est utilisé pour trier le résultat d'une recherche de mot clé. L'indice est définit ainsi : L'indice de popularité d'une page est d'autant plus grand quelle à un grand nombre de pages populaires la référençant (ayant un lien vers elle). Cette définition est autoréférente car pour connaître le l'indice d'une page il faut d'abord connaître l'indice des pages ayant un lien vers elle... Il existe cependant un moyen assez simple d'approcher une valeur numérique de l'indice.
Tout d'abord il faut voir le web comme un graphe. Chaque page est un noeud du graphe, chaque lien entre page est un arc entre deux noeuds.


Un manière commode pour représenter de telles relations est d'utiliser une matrice (= un tableau) : chaque ligne et colonne représentant un noeud (donc un site) et chaque case de la matrice représente la présence d'un lien entre les 2 pages correspondantes.
Voici un exemple de graphe :

Voici la matrice correspondante au graphe ci-dessus.


Site No 0
Site No 1
Site No 2
Site No 3
Site No 0
0
0
0
0
Site No 1
1
0
0
0
Site No 2
1
0
0
0
Site No 3
1
0
1
0
Note : Pour savoir si il y a un lien entre 2 sites A et B, il suffit de regarder le contenu de la case positionné en ligne A et colonne B : 0 signifie qu'il n'y a pas de lien, 1 qu'il y en a un.
Nous allons appeler cette matrice M. On représente la probabilité de présence d'un internaute sur tous les noeuds de notre graphe par un vecteur V. Dire que l'internaute est sur la page « 1 » s'écrit : V = (0 1 0 0). (attention on commence à compter les pages par 0 c'est donc bien la deuxième valeur qui est à 1 dans ce vecteur).
V' = V*M
on obtient un vecteur V' = (1 0 0 0), c'est justement la probabilité de présence de l'internaute sur les pages : après un clic, l'internaute se retrouve forcement sur la page « 0 ». Il a suivit l'unique lien sortant de la page « 1 », allant vers la page « 0 ». On peut alors re-itérer l'opération et multiplier ce vecteur résultat par M pour voir où se situera l'internaute lors du clic suivant, et ainsi de suite...
Si on faisait partir notre internaute de la page « 3 » : V = (0 0 0 1) le produit V par M donne (1 0 1 0), la somme des composante fait alors 2, c'est gênant pour représenter une probabilité de présence... . Dans la mesure où il impossible de savoir quel liens aura le plus de succès on va considérer qu'il ont tous la même probabilité d'être suivit, cela revient à normaliser la matrice (diviser chaque composante par la somme des valeur de la ligne correspondante), le problème est résolut. La matrice devient alors :


Site No 0
Site No 1
Site No 2
Site No 3
Site No 0
0
0
0
0
Site No 1
1
0
0
0
Site No 2
1
0
0
0
Site No 3
1/2
0
1/2
0
Notez que la somme de chaque ligne fait bien 1, et que le produit V * M donne alors V' = (½ 0 ½ 0) et représente alors correctement les probabilités de présence de l'internaute, partant de la page « 3 » et après avoir suivit un lien (« 1clic »). Si on re-itère l'opération , c'est à dire V'*M on obtient (1 0 0 0) au bout du deuxième « clic » de l'internaute. Si on continue on voit bien que le résultat ne changera plus... L'internaute est bloqué sur la page « 0 ». Cela n'est pas très réaliste, on considérera alors que l'internaute repart sur une autre pas, choisie au hasard. Cela revient à ajouter aux pages « cul de sac » des liens vers toutes les autres pages. Du point de vu de la matrice cela revient à trouver les lignes qui n'ont que des 0 et les replacer par des lignes avec 1/3 (dans ce cas précis) dans toutes les cases sauf sur la diagonale (lien d'une page vers elle même). Pourquoi 1/3 ? Tout simplement par ce qu'il y a 4 pages et qu'on considère que l'internaute reprendra son parcours aléatoirement sur n'importe quelle autre page (4(toutes les page) – 1 (celle ou il est actuellement « bloqué ») = 3).
Le processus tel qu'on la définit permet, maintenant, de modélisé raisonnablement un déplacement aléatoire d'internautes sur le réseau de page, modélisé par un graphe. Pour obtenir une vision globale et impartiale de la popularité des pages en fonction des liens qu'elles ont entre elles, il suffit maintenant de supposer que les internautes se répartissent initialement uniformément sur tout le réseau et on les laisse se déplacer jusqu'à ce que leur répartition (le vecteur V) se stabilise au fur et à mesure des itération de multiplication avec M. Dit autrement on commence avec un vecteur V dont toutes les composantes sont égales a 1/N, N étant le nombre total de pages (ou noeuds du graphe). Ensuite on multiplie itérativement V par M jusqu'à ce que le valeur du vecteur V n'évolue plus. On regarde alors la répartition des internautes sur le graphe, cela nous donne l'indice pagerank, plus il est élevé plus il y a d'internautes sur la page, donc plus la page est populaire...
Une recherche se décompose alors en deux étapes :
  • la sélection des pages contenant les mots clés de la requête.
  • Le classement , par ordre décroissant, des pages concernées en fonction de leur valeur de pagerank. Cette valeur aura bien sur été calculée précédemment et n'est pas recalculé à chaque requête.
Ces deux actions combinées font un moteur de recherche plutôt efficace...
On voit que algorithme pagerank (simplifié) est finalement assez simple:
  1. initialisez toutes les composantes de V à 1/N (N étant le nombre de pages ou noeud du graphe)
  2. calculer V'= V*M, (où M est la matrice représentant le graphe)
  3. copier le contenu de V' dans V
  4. reprendre en 2 sauf si les deux vecteurs V et V' sont très proche, dans ce cas l'algorithme est terminé
V ou V' (puisqu'il sont proche la fin de l'algorithme) contiennent les indices pagerank de chaque page. En pratique les valeurs de pagerank sont modifiés pour donner des valeurs entre 0 et 10, pour que cela soit plus « parlant ». Cela n'a que peu d'importance en pratique dans la mesure où on utilise cette valeur uniquement pour la comparaison entre les différents sites concerné par une recherche de mot clé.

Essayez vous même ...

La fenêtre qui s'est ouverte quand vous êtes arrivé sur cette page est une démonstration de cet algorithme réalisé par deux étudiants de deuxième année dans le cadre d'un TP de deuxième année (Vincent GERMAIN & Steevy MONTOUT).
Si vous avez fermée cette fenêtre, cliquez sur le bouton pour recharger la page, elle devrait re-apparaître. (Il faut que Java soit activé sur votre navigateur)
Ce démonstrateur est très simple d'utilisation :
  • Cliquez avec le bouton gauche de la souris, quelque part dans le cadre vide pour créer des noeuds (représentation d'une page web).
  • Faite un « drag&drop » (« glissé déplacé ») pour créer des liens entre les pages
  • appuyez sur bouton gauche de la souris près du noeud de départ
  • déplacez la souris vers le noeud d'arrivé en laissant le bouton enfoncé.
  • Relâchez le bouton près du noeud d'arrivé. Le lien est alors crée.
  • Pour supprimer des noeuds ou liens, faite la même opération que pour la création (clic ou drag&drop) mais avec le bouton de droite.
  • Le bouton du milieu permet de déplacer un noeud.
  • Cliquez sur le bouton «  Pagerank » pour lancer le calcul « pagerank » sur le graphe ainsi constitué.
Le résultat du pagerank est matérialisé en changeant la taille des noeuds et leur couleur : plus le noeud est grand et tend vers le rouge plus ce noeud regroupera des internautes (=plus sont indice pagerank est grand). Plus précisément le site avec le plus grand pagerank est affiché en rouge avec un grand rayon, tous les autres pages auront ,proportionnellement des cercles plus petits et un rouge moins marqué tendant progressivement vers le jaune plus le pagerank sera faible... Les exemples du paragraphe suivant vous aideront à comprendre la signalétique utilisée dans ce démonstrateur.

Quelques exemples d'analyse pagerank
Tout d'abord il est à noter que cette analyse n'est pas aussi intuitive qu'on puisse le penser. Voyez l'exemple de graphe ci-dessous :

Le résultat du pagerank n'est pas si simple à imaginer ...

Et des modifications simples peuvent amener à des résultats difficilement prédictible...

Un seul liens de plus entre 2 noeuds (qui est la seule différence entre les 2 graphes précédents) modifie considérablement le résultat.
Bref tout cela n'est pas si simple mais ce démonstrateur vous permettra quand même de comprendre quelques règles simples pour augmenter le pagerank d'un site...

Conseils pour augmenter le pagerank d'un site ...

Les liens entrants : toujours positifmais à des dégrés variables

Il est inutile de multiplier les liens provenant de sites avec un faible pagerank. Voir la partie droite du graphe ci-dessous, malgré 3 liens entrant, le site de de droite à un pagerank faible...


Un seul lien entrant, provenant d'un site ayant un pagerank élevé, est beaucoup plus efficace : voir l'exemple ci-dessous.

Notez que la page « donnant » le lien (en bas au milieu) ne perd pas vraiment d'indice pagerank (en tout cas proportionnellement aux autres, et c'est cela qui compte).
Ces liens entrant sont d'autant plus intéressant que le nombre de liens sortant de la page d'origine sont peu nombreux.

La page en bas à droite bénéficie moins du lien entrant provenant de la page qui est a sa gauche (par rapport à la figure précédente) car cette page à maintenant plus de liens sortant.

Les liens sortant : positif ou négatif, selon la topologie

Négatif (si si c'est possible...)

Contrairement à ce qui est souvent cru, certain liens sortant peuvent faire baiser l'indice pagerank d'une page, en tout cas d'un point de vue théorique. Voyez l'exemple ci-dessous :

et après l'ajout d'un lien sortant :

La page en bas à droite à perdu une bonne partie de son indice pagerank... Il est à noter qu'il s'agit là d'un cas un peu particulier et qu'en général un lien sortant a peu de chance de réellement faire baiser le pagerank d'une page. Les exemples simplistes des deux figures précédentes sont peu représentatifs de la topologie du réseau des pages web.

Positif

Avant la création du lien :

après : Notez la différence de taille de la page à laquelle on a ajouté un lien sortant. Sont pagerank a bien augmenté, tout simplement parce que ce lien, retourne sur cette page après un court détour. Il est donc bon qu'un site relie bien ses pages entre elle (ce qui evidement en plus rend le parcours de l'internautre (réél) plus pratique. Cependant attention de ne pas en abuser et de ne pas générer une « link farm »

Les « link farm »

Des « link farm »sont parfois artificiellement crées pour accumuler artificiellement du pagerank. Il s'agit de pages reliées entre elles mais qui n'ont aucun liens vers d'autres pages, et aucune page « cul de sac ». Tout internaute (simulé par l'algorithme pagerank) y pénétrant n'en sort pas. Mettre un lien ver une telle page peu grandement faire baisser le pagerank d'une page et de celles qui y amène. Dans le schéma ci-dessous le réseau de gauche est un réseau « normal », celui de droite une « link farm » :
Avant le lien vers la « linkfarm »

après ...

Notez que cette configuration de « link farm » est artificielle (générée par des webmaster peu scrupuleux), pour des pages réelle il y a toujours des liens sortant vers le reste du réseau. Dans l'exemple ci-dessous, un seul lien sortant de la « link farm » retablit la situation.

C'estpourquoi les moteurs de recherche identifient ces sous-réseau particuliers (en remarquant qu'il sont isolé du reste du web) pour les pénaliser.

En résumé

Il est évidement malsain de faire des pages web sans aucun lien sortant ou ne reliant que des pages du même site, car cela forme ce qu'on appelle des « link farm » ce qui est fortement pénalisé par les moteur de recherche (si bien entendu ils s'en rendent compte...). En pratique il n'y a donc pas besoin d'avoir une réelle politique technique de liens sortants si ce n'est que ces liens soient intéressant pour l'internaute. Pour les liens entrant, plus il y en a mieux c'est. Il ne sont cependant pas tous aussi facile à générer et ils n'apportent pas tous le même gain cela dépend du pagerank de la page originaire du lien ainsi que du nombre de lien sortant de cette page.

Quelques exemples
En appliquant ces règles voici le résultat de recherches de mots clés sur google-france. Ces mots clés correspondent à des articles de ce blog, cependant vous pourrez noter que nombre de ces requêtes pourraient assez légitimement ne pas donner ces articles en premier. Il est aussi à noter que, très certainement, une partie du pagerank de ce blog est en partie héritée du site « www.esiea.fr ».
Voici une liste de requêtes sur Google où ce blog est très bien classé alors qu'il existe des pages certainement plus légitimes :
Merci de voter pour cet article, qu'il vous ai plu ... ou non...

Projet 3A en autonomie


Sujet du projet de programmation (3A) en langage C : L'agencement de graphes.
Lisez la suite pour voir une courte vidéo d'introduction au projet.
Voici une vidéo vous présentant la problématique d'agencement de graphes et la solution que je vous propose d'implémenter...

Le sujet est attaché à cet article, ainsi qu'un code de base pour l'affichage graphique ("fenetre.c"), et des exemples de graphes.
Je communiquerai sur cette page les réponses aux questions que vous me poserez par mail. Pensez donc à y revenir de temps en temps , et surtout avant de poser une question ;)
Le plus simple est de l'installer via "apt-get" :
sudo apt-get install libcsfml-dev libgl1-mesa-dev libglu1-mesa-dev
Si vous utilisez les ordinateurw de salle de TP, la librairie est déjà installée, vous n'avez donc rien à faire.
[EDIT] On m'a signalé qu'il y a un problème à l'exécution sur les machines de TP... Il y a apparemment eu des mises à jour, entre mes derniers tests fait avant l'été, et maintenant... Nous travaillons à trouver une solution.
[EDIT #2] Le problème semblerai avoir lieu en salle I12b et E08, mais pas en I22, si vous travaillez à l'école, utilisez la salle I22, et vous n'aurez pas de problèmes... En attendant qu'on résolve le problème et que ça marche dans toutes les salles...
[EDIT #3 fait le 25 octobre] bizarrement certains étudiants m'on rapporté que la ligne de compilation ne marchais pas chez eux. Dans ce cas essayer comme ceci (en mettant le "-lm" à la fin de la ligne). 
gcc -Wall -g fenetre.c -lcsfml-graphics  -o fenetre -lm
J'ai reçu un certain nombre de questions par mail, en voici les réponses :
  • Vous aurez besoin d'ajouter la librairie mathématique (#include ", d'où le "-lm" dans la librairie qui y est associée), mais c'est tout, vous n'utilisez pas d'autres bibliothèque que celles déjà utilisée dans le code de base ("fenetre.c"). Je vous rappelle que je vais devoir corriger un très grand nombre de codes, et je vais donc essayer d'automatiser un certain nombre de tâches, dont la compilation.
  • Une question m'a souvent été demandée sur le poids à associer à chaque noeud. La réponse est dans la formule vous permettant de simuler les forces du ressort correspondant aux liens. Quand vous voulez appliquer la force correspondant au ressort, il vous faut spécifier une masse correspondant aux noeuds. Vous prenez donc la même masse pour tous les noeuds. Cela peut donc être tout à fait une constante du programme, ou une valeur dans la structure représentant les noeuds, c'est comme vous voulez. Cette valeur de masse dépend de la raideur du ressort que vous aurez choisit pour représenter les liens. Si la raideur est importante, vous devez mettre une masse élevée, et si vous mettez une raideur faible, il vaut mieux mettre une masse faible sinon la simulation ne bouge tout simplement pas... C'est à vous de faire des essais et de trouver un compromis qui fonctionne. Comme précisé lors de la présentation, ce principe de simulation ne vous assure pas de trouver une disposition optimale à tous les coups, essayez de trouver des paramètres qui fonctionnent bien, je n'exige pas quelque chose de parfait. Les vidéos (il y en a deuxième en dessous) vous donne un aperçu de ce qui est possible de réaliser (et aussi de certaines imperfections dont il est difficile de se débarrasser.).
  • Si vous désirez aller plus loin que le sujet de base, faites le et envoyez moi la vidéo (sous linux, le logiciel recordMyDesktop fonctionne plutôt bien pour faire cela.) et je publierai vos exploits ici comme ce que m'a envoyé Michel Remise. (Voir la vidéo ci-dessous). Mais pour la notation, rendez moi un code qui suit toutes les recommandations de base, car pour la correction, la plupart des étapes seront automatisées, donc ne cherchez pas à faire quelque chose de différent, ça risque de ne pas passer !
[EDIT #4] fait le 6 novembre. Je repousse la date de rendu du projet au 5 jeudi décembre (minuit au plus tard). Cela pour plusieurs raisons, tout d'abord il y a eu un problème pour faire fonctionner ce programme en salle de TP (cela vous a peut etre fait perdre du temps). J'ai vu aussi un certain nombre d'étudiants ayant un peu de difficulté avec le projet, mais qui faisaient des efforts et qui progressaient. Je pense donc que ce délais supplémentaire sera bénéfique. De plus je vous propose une séance supplémentaire le jeudi 28 novembre, en salle de TP, à laquelle je serai présent pour répondre à vos questions. Cette séance est bien sur facultative (car toute la promo ne rentrera pas dans une seule salle info' ;) ) , seul les étudiants en difficulté sont réellement convié à cette séance.
[EDIT #5] les machines de toutes les salles ont été mises à jour, vous pouvez donc maintenant travailler sur ce projet dans toutes les salles (site de Vésale y compris).
Bon courage et bon travail...

Voici les réalisations de certains étudiants ...
Qui on réalisé bien plus que ce qui était attendu. Un grand bravo pour ces réalisations.
Voici ce qu'à réussi à faire Michel Remise, c'est une suite d'exemple de graphes de plus en plus compliqué, et qui va nettement au delà de mes espérances ;) bravo! Ayez la patience de voir la vidéo jusqu'au bout car les derniers exemples sont très intéressant. Si vous avez aussi envie de pousser


Voici encore un autre travail d'étudiant qui mérite le détour. Vincent Marquet à utilisé le logiciel Baldr (production ESIEA!) qui permet d'étudier les similarité de fichiers, principalement utilisé pour de l'analyse de similarité de code, dans le but de détecter du plagiat en TP. Il a utilisé ce logiciel pour analyser des histoires écrites par Raymond Queneau. Il s'agit de la même histoire mais raconté dans des styles différents. Baldr produit des mesure de distances entres ces histoires, ces distances sont utilisées dans le programme de Vincent pour produire l'agencement d'un graphe illustrant les liens de proximité entre les histoires. Le résultat est surprenant puisqu'on constate qu'un programme (prévu pour de l'analyse de code) est capable de faire de l'analyse littéraire !! 

Si vous avez réalisé, vous aussi, un programme qui va au delà de ce qui était demandé, n'hésitez pas à faire une vidéo, me l'envoyer, et je la publierai ici.

Cartographie de followers



Pourquoi vouloir faire une cartographie ? Le réseau Twitter à cela de particulier que les usagers donnent peu d'information sur eux. Il est donc très difficile de se faire une idée de qui constitue l'audience d'un compte, cela est d'autant plus vrai que le compte possède beaucoup de followers, car on ne peut pas aller tous les voir.


J'ai donc imaginé un outil permettant de faire une cartographie de followers. Pour cela je me base sur les abonnements des gens pour pouvoir créer un indice de similarité. Typiquement, deux personnes ayant (plus ou moins) les mêmes abonnements, se ressemblent. J'analyse ensuite ces données de similarité avec une technique de datamining pour produire une carte.


L'application est naturellement de mieux connaître ses abonnés pour adapter sa communication.... Comme un exemple vaut mieux qu'un long discours, je vais vous montrer ce que donne cette analyse sur le compte «@groupeESIEA » , le compte de l'école pour laquelle je travaille. Il est à noter que ce type d'analyse peut être fait pour n'importe quel compte , même si vous n'en êtes pas propriétaire car la nature même de l'outil Twitter étant le broadcast, la plupart des comptes sont ouverts... 


Cliquez sur l'image pour l'agrandir.

J'ai récupéré l'ensemble des followers du comptes @groupeESIEA, cela fait environ 400 comptes Twitter. J'ai alors regardé quels étaient les autres comptes suivit par ces 400 personnes, cela fait environ 86.000 abonnements différents! Parmi tous ces abonnements, certain ne concernent qu'un très faible nombre de gens et ne sont donc pas un critère pour créer une mesure de similarité. Je réduis donc ce nombre à environ 2000 sujets d'intérêts partagés par les followers du groupe ESIEA. Je représente alors chaque follower par un vecteur de dimension 2000, chaque coordonné correspond à un des 2000 sujets. Pour un follower donné, chaque coordonné est mise à 1 si le follower suit le sujet correspondant, et 0 sinon. Cependant visualiser directement un espace vectoriel de dimension 2000 est impossible. Mais ces vecteurs sont « creux », c'est à dire qu'il sont remplit de beaucoup de 0 et qu'il y a très peu de 1. Cela veux dire qu'en fait on doit pouvoir représenter ces données dans une dimension bien inférieure à 2000, sans perdre trop d'information. La technique de réseaux de neurones de Kohonen (+LINK) appelée aussi « cartes auto-organisatrices » est très adapté à ce genre de problématiques. Je demande donc à cet algorithme de réduire la dimension du problème de 2000,... à simplement deux, je peux alors disposer tous les 400 followers dans un plan, plus précisément dans un tableau à deux dimensions.

Voilà comment se lit une carte de type « Kohonen » :
  • Les followers regroupés dans une même case sont donc jugés comme assez « semblables »
  • Les groupes de followers dans des cases adjacentes sont « voisins », c'est a dire qu'ils n'ont pas forcément beaucoup de choses directement en commun, mais qu'il y a un continuum dans les thématiques qu'ils suivent.
Fort de ces deux informations, et de ma connaissance du compte @groupeESIEA je peux donc identifier les différentes régions de la carte :
  • Le plus gros paquet de followers est naturellement constitué d'étudiants (et d'anciens étudiants) de l'ESIEA. Ce paquet n'est pas uniforme, on identifie des branches. Je suppose que ces branches constituent des sous-groupes dans les étudiants. Par affinités personnelles (ces étudiants se suivent sur twitter entrent eux), mais aussi par centres d'intérêts.
    J'ai par exemple identifié un sous-groupe comme étant des fans de sécurité informatique et de hacking. Voir le groupe entouré en gris sur la carte.
  • On identifie ensuite un tas de petits paquets qui gravitent autour du paquet d'étudiants. J'y ai identifié : des journalistes, des association étudiantes, et des cabinets de recrutements... Assez naturellement ces comptes ne partagent pas grand chose en commun ils sont donc plus éparpillé sur la carte que ne le sont les étudiants.
Ce qui est intéressant grâce à cette cartographie, c'est que j'ai pu voir que près de la moitié des followers du @groupeESIEA sont en fait des institutionnels, c'est à dire , des association, des cabinets de recrutement. Je ne l'aurait pas imaginé avant de disposer de cette carte. Cette étude a été réalisé en utilisant Twitter4J  implémentant l'API twitter  ainsi que du code "maison" pour la paramétrisation et l'algorithme de Kohonen... Si vous êtes un follower du compte @groupeESIEA. n'hésitez pas à vous cherchez dans la carte, et me commenter votre position. D'autres cartes sont en cours de préparation, je vous les présenterai ici et je les annoncerai sur Twitter.
Vous pouvez aussi , m'envoyer vos commentaires sur Twitter.

Annexe(s) :