SimilarBot

De Wikipast
Sauter à la navigation Sauter à la recherche

SimilarBot a pour but de suggérer des recommandations de personnages similaires au bas de chaque biographie. Pour cela, il tente de rapprocher les personnages qui pourraient être liés en fonction de 4 critères : Lieux, Période de vie, Domaines d'activité et Relations interpersonnelles. Ces personnages peuvent avoir été directement liés au cours de leur vie, où avoir simplement observé un parcours de vie similaire. L'algorithme apporte également une justification à chaque recommandation, qui fournit le critère ayant été le plus décisif pour établir la recommandation. Selon la proximité ayant pu être établie entre un personnage et les autres personnages de Wikipast, le nombre de recommandations peut varier entre 0 et 3.

Code

lien vers le code : [1]

Description des principales fonctions de l'algorithme

Ci-dessous sont listées les principales fonctions de l'algorithme. Elles sont décrites séparément, de manière à permettre de bien comprendre les différentes étapes du cheminement. On peut résumer le fonctionnement de l'algorithme en 4 étapes distinctes :

  1. Data scrapping : MAIN, puis getAcquaintance, getPlaces, getLifespan et getWork
  2. Calcul de la corrélation : computeCorrelation (qui utilise 4 autres fonction spécifiques à chacun des critères)
  3. Classement : ranking
  4. Affichage : MAIN

getAcquaintance

Cette fonction est la plus basique pour déterminer un lien de similitude entre deux personnages du Wikipast, elle se contente de vérifer si un autre des personnages est cité dans la biographie. Pour être utile à notre SimilarBot qui a pour but de suggérer une page en lien il faut que la personne citée dans la biographie ait une page Wikipast à son nom. Pour ce faire le bot parcourt une page biographique et vérifie si une autre des biographies du Wikipast est citée dans cette page il va ensuite l'ajouter à sa liste de connaissance puis la fonction checkAquaintanceReciprocity s'assure que le personnage dont on parcourt la biographie est lui aussi ajouté à la liste de connaissance du nouveau personnage.

Limitation :

  • Comme nous le verrons plus bas, une simple citation suffit pour obtenir un score de 100% à cette catégorie. Il aurait été possible d'affiner cette fonction pour qu'elle repère des rapports interpersonnels plus détaillés (par exemple lien de parenté, couples, époux, collègues, connaissances, etc.). Cependant, au vu du faible nombre de biographies ayant actuellement des liens interpersonnels sur Wikipast, nous n'avons pas retenu cette option.
  • La fonction agit de manière symétrique entre deux personnages. En effet, supposons qu'un personnage s'inspire d'un autre pour son travail, par exemple Nietzsche parle de Socrate dans ses écrits. Cette fonction va dire que Nietzsche et autant lié à Socrate que Socrate est lié à Nietzsche. Intuitivement, ce cas symétrique semble sensé, mais pourtant Socrate n'a jamais rien su de Nietzsche et ne lui a donc jamais fait référence et de plus, Socrate a été cité beaucoup plus souvent de par son antériorité. Ceci est encore plus marqué si la personne qui se base sur Socrate est encore moins connue. Cet effet de symétrie pourrait être facilement réglé en ne regardant que les citations présentes sur la page du personnage et non sur l'ensemble de la base de donnée. Toutefois, le nombre d'entrées par personnage étant limité (autour de 15), cet effet de symétrie est désirable dans l'état actuel du Wikipast car la fonction permet de trouver des liens intéressants entre personnages en cherchant dans toutes les biographies du Wikipast, ce qui ne serait pas forcément le cas en se restreignant juste à l'unique page biographique. Sur le long terme, lorsque la base de donnée sera plus étoffée (p. ex. nombre de personnages comme dans Wikipédia et biographies plus complètes), cette approche pourrait être changée afin de rendre les scores asymétriques et plus révélateurs des liens entre personnages.

getPlaces

Cette fonction sert à miner les informations concernant les lieux associés aux entrées évènements de chaque personnage de Wikipast. Elle crée ensuite, pour chacun des personnages, un objet Python "dictionnaire", contenant le nom de chacun des lieux cité au début des entrées-évènements, et leur fréquence de citation relative (normée).

Exemple :

 * 1926.12.12 / Genève. Naissance du Grand Schtroumpf.
 * 1929.02.06 / Genève. Publication : Le Grand Schtroumpf publie Vivre à Lyon.
 * 1933.07.01 / Lausanne. Election du Grand Schtroumpf au poste de Grand Schtroumpf.
 * 1935.11.22 / -. Publication : Le Grand Schtroumpf publie La salsepareille dans tous ses états.
 * 1939.09.30. Décès du Grand Schtroumpf.

Le programme associera au personnage : Genève : 66.6%, Lausanne : 33.3%. Les entrées où le lieu n'est pas spécifié ne sont pas prises en compte par l'algorithme.

Limitations :

  • Lorsque la syntaxe n'est pas respectée, le programme peut comprendre une suite de lettres, se trouvant à la place normale du lieu, c'est-à-dire après le signe / et entre crochets, comme étant un nom de lieu. Cela n'est pas le cas lorsque la syntaxe est respectée (pas de problème donc dans les entrées-évènements 4 et 5 de l'exemple).
  • Un second problème concerne les éventuels espaces dans les noms de lieux. En effet, un lieu comme Suisse romande ne pourra pas être détecté. Les noms à tirets, par contre, ne sont pas un problème (comme Aix-la-Chapelle)
  • Actuellement, la proximité topographique des lieux n'est pas prise en compte, ainsi, l'algorithme n'accordera pas un seul point de corrélation entre Paris et Versailles, même si ces lieux sont géographiquement proches.
  • Les évolutions toponymiques (Istanbul, Constantinople) ne sont pas prises en compte, de même que les variantes orthographiques d'un même nom de lieu (Biel, Bienne).

getLifespan

Cette fonction récupère les informations concernant l'époque où le personnage a vécu (date de naissance et de décès).

Exemple :

 * 1926.12.12 / Genève. Naissance du Grand Schtroumpf.
 * 1949.02.06 / Genève. Naissance du Petit Schtroumpf, fils du Grand Schtroumpf.
 * 1999.04.01 / Genève. Décès du Grand Schtroumpf.

Le programme comprendra que la durée de vie du Grand Schtroumpf s'étend sur la période [1926,1999].

Limitations :

  • Lorsque ni la date de naissance, ni la date de décès ne sont spécifiées, le programme n'enregistre pas d'informations à propos de la période de vie du personnage.
  • Lorsque la date de naissance est spécifiée, mais pas la date de décès, le programme part du principe que le personnage est toujours vivant, pour autant que la durée de vie que cela implique ne soit pas hors norme (max. 98 ans). Si la durée de vie parait déraisonnable, le programme considère une durée de vie moyenne de 70 ans.
  • Lorsque la date de décès est spécifiée, mais pas la date de naissance, le programme considère la première entrée de la biographie comme début de la période de vie du personnnage.
  • Le programme ne comprend que les entrées liées aux hypermots conventionnels : Naissance, Décès, Mort et Exécution.

getWork

Cherche et repère, dans chaque évènement de la Biographie, une liste de mots clé, en lien avec différents domaines d'activité. Établit ensuite, à l'image de getPlaces, un tableau (dictionnaire Python) qui attribue à chaque domaine d'activité un poids relatif. Actuellement, il existe 15 domaines d'activité principaux : Sport, Arts plastiques, Littérature, Musique, Cinéma, Sciences naturelles, Sciences humaines, Mathématiques, Politique, Philosophie et psychologie, Médecine et santé, Militaire et Affaires. Les catégories d'activités les plus grandes sont divisées en sous-catégories (comme par exemple Politique, Sport, Sciences naturelles).

Exemple :

 * 1932.04.01 / Genève. Publication de Petits théorèmes schtroumpfants par le Grand Schtroumpf.
 * 1933.07.01 / Lausanne. Election du Grand Schtroumpf au poste de Grand Schtroumpf.'.
 * 1935.04.01 / Genève. Publication de Mes meilleures parties d'échecs par le Grand Schtroumpf.

Le programme attribuera les poids suivants à cet extrait

  • 40% Littérature (2 lignes contiennent le mot-clé Publication)
  • 20% Mathématiques (1 ligne contien le mot-clé théorèmes)
  • 20% Politique (1 ligne contient le mot-clé Election, de la sous-catégorie Démocratie)
  • 20% Sport (1 ligne contient le mot-clé échecs, de la sous-catégorie Échecs)

Limitations :

  • Les catégories sont définies directement dans le code Python, ainsi que les mots-clés. Cela limite le nombre de catégories et les capacités de compréhension du programme.
  • L'intention du personnage n'est pas prise en compte. Par exemple, un antimilitariste qui s'expose à des situations de guerre, et dont la biographie contiendra des mots-clé lié à la guerre, pourra être mis en lien avec un général, militaire de carrière.

computeCorrelation

Calcule la corrélation en fonction des 4 critères principaux (Lieux, Période de vie, Domaines d'activité et Relations interpersonnelles). La contribution des 4 critères est identique, à l'exception de de la Période de vie, dont l'importance a été évaluée 20% inférieure à celle des autres catégories.

Le calcul de la corrélation est basé sur les pourcentages de recouvrement.

Exemple du calcul de la corrélation entre deux personnages :

Résultats du data scraping :

 Nom :
 Simone de Beauvoir
 Période :
 de 1908 à 1986
 Lieux :
 Paris : 57.1%
 Chicago : 14.2%
 Joigny : 14.2%
 Tokio : 14.2%
 Poids des principaux domaines d'activité :
 Littérature  : 60.0%
 Politique  : 10.0% (dont 10.0% du sous-domaine Démocratie)
 Philosophie et psychologie  : 10.0% (dont 10.0% du sous-domaine Philosophie)
 Médecine et santé  : 10.0%
 Militaire  : 10.0%
 Connaissances :
 Jean-Paul Sartre
 Nom :
 Jean-Paul Sartre
 Période :
 de 1905 à 1980
 Lieux :
 Paris : 68.7%
 France : 6.25%
 Rome : 6.25%
 Stockholm : 12.5%
 Suisse : 6.25%
 Poids des principaux domaines d'activité :
 Littérature  : 55.5% (dont 11.1% du sous-domaine Littérature romanesque et 33.3% du sous-domaine Essais)
 Cinéma  : 11.1% (dont 11.1% du sous-domaine Télévisuel)
 Politique  : 11.1%
 Philosophie et psychologie  : 11.1% (dont 11.1% du sous-domaine Philosophie)
 Médecine et santé : 11.1%
 Connaissances :
 Simone de Beauvoir
Répartition du poids des différents critères dans le calcul global.

La corrélation de Jean-Paul Sartre pour Simone de Beauvoir est de 75.5% et celle de sione de Beauvoir pour Jean-Paul Sartre est de 76.2%, détaillée comme suit :

  • 100% des 23.3% liés au Relations interpersonnelles (une simple citation suffit pour obtenir un score de 100% à cette catégorie).
  • Durée de vie en commun / Pour Simone de Beauvoir: 72 ans / sur ses 78 ans de vie = 92%; Pour Jean-Paul Sartre : 72 ans / sur ses 75 ans de vie = 96%. Ces pourcentages décrivent la partie des 18.6% liés à la Période de vie.
  • 57.1% des 23.3% liés aux Lieux (un seul lieu en commun : Paris, Simone de Beauvoir y étant liée par 57.1% de ses entrées biographiques et Jean-Paul Sartre par 68.7%. Le pourcentage de recouvrement des Lieux est donc de 57.1%).
  • Sur le même principe que pour les Lieux (c'est à dire par recouvrement des pourcentages des différentes entrées) : 62.6% des 34.9% liés au Domaines d'activité (dont 85% des 23.3% liés au Domaines d'activité principaux et 17% des 11.6% liés aux Domaines d'activité secondaires)

Au final, cela nous donne bien des corrélations de 75.5% et 76.2%, la seule différence étant la durée de vie en commun qui dépend de la durée de vie de chacun des personnages.

Notons que dans le programme, ce calcul est, par soucis de simplicité, effectué par 4 fonctions différentes : computeAcquaintanceCorrelation, computeLifespanCorrelation, computePlaceCorrelation et computeWorkCorrelation. De plus dans le programme les corrélations sont calculées à l'aide de poids (de 0 à 4.3), qui sont convertis en pourcentages dan l'affichage pour faciliter la lecture.

ranking

Cette fonction permet de déterminer pour un personnage les 3 personnages qui lui sont le plus liés. Pour cela on parcourt les scores de corrélation du personnage étudié avec les autres personnages et on retient les trois meilleurs scores en modifiant le classement lorsque les personnages parcourus ont un score supérieur à un des trois classés. A la fin la fonction choisit les personnages à afficher : sur les 3 du classement elle n’affichera uniquement ceux dont le score de corrélation est supérieur à 20% pour la meilleure recommandation du classement. En effet nous considérons comme insignifiantes et peu pertinentes les corrélations inférieures à 20%. Pour les recommandations 2 et 3 l'exigence est augmentée (25% et 30%) afin de justifier le fait d'afficher plusieurs recommandations. Nous considérons que si plusieurs recommandations sont affichées elles se doivent d'être toutes pertinentes.

Exemple de sortie :

 Recommandation(s) automatique(s) pour Simone de Beauvoir
 * Jean-Paul Sartre. Recouvrement : 75.5%. Il semble que les personnages se connaissaient.
 * Jeanne Hersch. Recouvrement : 44.1%. Il semble que les personnages aient tous deux été actifs dans le domaine littéraire.
 * André Breton. Recouvrement : 43.4%. Il semble que les personnages aient tous deux été actifs dans le domaine littéraire.

Analyse des performances

Résultat de l'analyse quantitative des performances de SimilarBot.

Analyse qualitative

  • Le nombre de recommandations proposées dépend de la qualité de la corrélation. Cela permet d'éviter d'afficher trop de recommandations, lorsque ces dernières ne sont que moyennement pertinentes.
  • Le score de recouvrement est systématiquement affiché, ce qui permet de relativiser la qualité de la recommandation auprès de l’utilisateur·trice.

Analyse quantitative

Nous avons effectué une analyse quantitative des performances du bot. À cet effet, une note a été attribuée à toutes les biographies pour lesquelles une recommandation a été formulée. On remarque sur la figure résultante ci-contre qu'une très grande majorité des recommandations sont jugées pertinentes. La plupart des cas où les recommandations sont jugées moyennes ou insuffisantes sont dûs à la faible taille du corpus (76 biographies complètes) ou à une Biographie lacunaire (Lieux absents, dates de naissance et de décès manquantes, etc.). Le bot a fourni des recommandations dans 73 des 76 pages biographiques sur lesquelles il a été déployé. Aucune altération de la page n'a été repérée suite au déploiement.

Performances de calcul

Sur un ordinateur portable avec une processeur moyen, l'algorithme s'exécute en 291 secondes. Sachant qu'un temps intercalaire de 3 secondes a été rajouté volontairement entre le traitement de chaque personnage, pour éviter de surcharger Wikipast, cela correspond à un temps de calcul de 63 secondes, soit 0.8 seconde par personnage. Le calcul de la corrélation entre chaque personnage risque cependant de devenir plus exigeant si le nombre de biographies augmente, car la complexité temporelle de ce calcul est O(n2). Ce temps de calcul reste relativement marginal pour le moment, la tâche la plus lente étant l'affichage sur Wikipast.

Schedueling

Un lancement hebdomadaire du bot paraît suffisant pour mettre à jour les recommandations.

Limitations générales et améliorations

  • L'algorithme utilise une liste de mot-clés écrite à la main: elle est donc restreinte au contexte et à la liste des biographies courante. Une automatisation pourrait être envisagée.
  • Le mots clés n'identifient pas toujours un domaine avec certitude totale, par exemple, une biographie qui contient la mot "cinématique" aura un score non nul pour le domaine du cinéma, bien que la cinématique soit une branche de la physique. Cela à cause du mot-clé cinéma.
  • La précision du bot est limitée par le contenu des biographies, et souvent 15 entrées n'arrivent pas à résumer la vie d'un personnage de manière satisfaisante. Par exemple la page de Mao Zedong et Adolf Hitler ont beaucoup de poids sur "démocratie" simplement parce qu'ils ont été élus, bien qu'il soit clair que la majorité du poids devrait être sur "dictature". En ajoutant le fait que le nombre de biographies est limité, ceci a mené à des choix d'implémentation tels que la fonction getAcquaintance qui parcourt l'ensemble des biographies afin de trouver un lien entre personnages, donnant lieu à des scores symétriques. Dans une version future plus étoffée et complète de Wikipast, ces choix devront être remis en question et au goût du jour afin d'affiner les corrélations.
  • Le calcul de la corrélation est basé sur les pourcentages de recouvrement.
  • Le nombre limité de biographies ne permet pas une quantification précise de l'efficacité du bot.
  • Les critères de similarité ainsi que leurs poids respectifs dans le calcul du score sont une question de convention. Certains choix sont plus justifiés tels que mettre plus d'importance sur le domaine commun d'activité entre deux personnages plutôt que sur le fait qu'ils ont vécu au même moment. Le poid exact sur chaque critère reste néanmoins subjectif et a été ajusté empiriquement, basé sur la cohérence des résultats du bot, afin d'assurer les suggestions les plus sensées. En effet, ce système de score permet à deux personnages d'avoir le même pourcentage de corrélation mais pour des raisons différentes (imaginons Aristote-Socrate pour le lieu, période de vie et philosophie contre Aristote-Galilée pour le domaine scientifique). Le bot proposera alors les 2 personnages, ce qui est un choix d'implémentation dû aux poids et aux catégories de classification.