« TangoBot » : différence entre les versions
(Annulation des modifications 37651 de Orthobot (discussion)) |
|||
| (25 versions intermédiaires par 5 utilisateurs non affichées) | |||
| Ligne 1 : | Ligne 1 : | ||
== Résumé des fonctionnalités == | == Résumé des fonctionnalités == | ||
Ce bot permet de supprimer les entrées redondantes sur une page. | Ce bot permet de supprimer les entrées redondantes sur une page. | ||
== Description technique == | == Description technique == | ||
Pour pouvoir éliminer les entrées redondantes, il faut les comparer chacune les unes aux autres et estimer leur similarité. | |||
Avant de comparer les phrases il faut les "nettoyer". | |||
*Supprimer tout caractère spécial ou signe de ponctuation. | |||
*Mettre tous les caractères en minuscule. | |||
Séparer les mots et en filtrer certains. | |||
*Les mots commençant par "http" sont des sources et il est préférable de les ignorer car ce ne sont pas des mots et n'aide pas à comparer le sens de la phrase. | |||
*Les "stopwords", ("Mot vide") ('au', 'ce', 'du', 'étais', 'le' 'la', 'il', 'je', 'nous',...) sont des mots tellement communs qu'il est inutile de les prendre en compte, car il apparaissent avec une fréquence semblables dans n'importe quel texte. Ils n'aident pas à distinguer un texte par rapport à un autre et n'apporterait que de l'information inutile en plus. Par conséquent ils sont ignorés. | |||
Et les modifier pour en avoir plus en commun. | |||
*"Stemming", ("Racinisation") est un procédé de transformation des flexions en leur radical ou racine. Ce qui permet de lier par exemple les mots ''continuait'', ''continuerai'' et ''continuant'' qui ont comme racine commune continu. L'algorithme de Porter est utilisée dans ce cas plutôt qu'un dictionnaire. | |||
On applique ensuite le '''TF-IDF''' (Term Frequency-Inverse Document Frequency) qui est une méthode qui permet de d'évaluer l'importance d'un mot dans un texte. | |||
L'idée du "term frequency" est juste le nombre d'occurrences dans un fichier sur le nombre d'occurrences totals dans tous les fichiers | |||
tf(i,i) = n(i,i)/sum(n(k,i)) | |||
La fréquence inverse vise à donner plus de poids au terme moins fréquent qui peuvent aider à mieux différencier un texte d'un autre. | |||
idf(i) = log{(abs(D)/abs(dj tq ti appartient à dj)} | |||
ou D est le nombre total de documents dans le corpus | |||
et le dénominateur le nombre de document ou le terme ti apparaît | |||
Le poids s'obtient en multipliant les deux mesures: | |||
tfidf(i,j) = tf(i,j) * idf(i) | |||
Le poids augmente proportionnellement au nombre d'occurrences du terme dans le texte. | |||
On peut donc utiliser cette pondération pour décrire les différents textes dans un modèle vectoriel ou chaque document est représenté par un vecteur. Sous forme vectoriel il est très facile de calculer la similarité entre deux vecteurs (deux textes) par la similarité cosinus. | |||
Le produit scalaire de deux vecteurs A et B donne: | |||
||A|| * ||B|| * cos(theta) | |||
on peut donc déterminer l'angle theta et comme cos(theta) est compris entre -1 et 1 on peut évaluer le degré de similarité. | |||
De 1 (identique) à -1 totalement opposées. Dans ce cas les vecteurs tf-idf sont toujours positif donc le degré de similarité est entre 0 (nulle) et 1. | |||
Le degré de similarité à partir du quelle on considère que deux entrées sont les mêmes peut être estimé à partir de la moyenne des "cosine similarities" ainsi que de la "standard deviation" mais dans ce cas de figure nous avons trouvé que le TangoBot donnait de meilleurs résultats en considérant les valeurs > 0.5 (seuil fixe) comme suffisantes pour considérer l'égalité. | |||
Une fois que le degré de similarité entre chaque document est établis le choix de quelle version des entrées dupliquées il faut garder se fait sur le nombre d'hyperliens dans l'entrées. Les entrées les plus complètes seront toujours gardées. | |||
== Exemples == | == Exemples == | ||
Pour une page de test ou les exemples ci-dessous ont été traversés par le [[TangoBot]] voir: [http://wikipast.epfl.ch/wikipast/index.php/TangoBotTest TANGOBOT TEST PAGE] | |||
1) Si le TangoBot compare deux phrases identiques : | 1) Si le TangoBot compare deux phrases identiques : | ||
| Ligne 18 : | Ligne 67 : | ||
*"[[1828.05.08]] / [[Genève]]. [[Henri Dunant]] est né. [http://letemps.archives.world/page/GDL_1978_04_20/5/%22Henri%20Dunant%22] | [http://letemps.archives.world/page/GDL_1985_10_26/14/%22Henry%20Dunant%22]." | *"[[1828.05.08]] / [[Genève]]. [[Henri Dunant]] est né. [http://letemps.archives.world/page/GDL_1978_04_20/5/%22Henri%20Dunant%22] | [http://letemps.archives.world/page/GDL_1985_10_26/14/%22Henry%20Dunant%22]." | ||
*Ici, le TangoBot voit qu'il y a [[Henri Dunant]] dans les 2 phrases et que le nom est associé à "[[Naissance]]" et "né". Il établit donc un lien entre les 2 phrases et remarque qu'elles sont fortement similaires. Il décide donc de garder la première. | *Ici, le TangoBot voit qu'il y a [[Henri Dunant]] dans les 2 phrases et que le nom est associé à "[[Naissance]]" et "né". Il établit donc un lien entre les 2 phrases et remarque qu'elles sont fortement similaires. Il décide donc de garder la première. | ||
== Evaluation des performances == | |||
Le TangoBot traite les erreurs dans le format des entrées en les ignorant, les considérant comme du simple texte et respecte donc leur ordre dans le document. Le TangoBot est tolérant. | |||
Le TangoBot devient utile quand beaucoup de différents bots applique leurs tâches en s'ignorant les uns les autres et par conséquent crée des entrées dupliquées. Le TangoBot réunit il ne divise pas. | |||
Le bot utilise des algorithmes qui calcule des similarités en se basant presque que sur les entrées de base, cela permet de gagner en performance même si on perd en précision comparé à des mesures de similarité linguistique qui vont utiliser de grand dictionnaires. | |||
Le seuil utilisé pour considérer une entrée comme égale à une autre est fixe (0.5) dans ce cas. Idéalement il faudrait déterminer statistiquement quelle valeur est la meilleure ou encore en étudiant la distribution des scores de similarité. | |||
Dans certains cas une entrée dupliquée est intentionnel, une option est désormais possible pour l'indiquer: <dup>. Ces faux positifs peuvent donc être évités en ajoutant cette balise à la fin. | |||
Le bot pourrait être utilisé pour signaler les documents redondants sur Wikipast au lieu de juste les entrées. | |||
Temps d'execution pour toutes les pages environ 3 minutes. (Le temps de 3 minutes est pour la première execution une fois les dupliqués détectés l'algorithme ne va pas repasser dessus et va donc évaluer seulement les changements, par conséquent le temps d'execution ne dépassera pas les 30 secondes après la première execution à moins d'une création massive de nouvelles entrées par un autre bot) | |||
La majorité des entrées dupliquées détectées sont générées par d'autres bots. (95%) | |||
Peu de cas d'entrées sémantiquement identique. (<5%) | |||
Quelques cas de faux positifs. (<5%) | |||
=== Scheduling === | |||
Etant donné que la majorité des entrées dupliquées sont crées par des bots, il est logique de faire tourner le TangoBot après leur passage. | |||
Une fois par jour convient très bien par rapport aux autres scheduling des bots. | |||
== Le tango == | == Le tango == | ||
(Fonctionnalité historique) [deprecated] | |||
Comme le TangoBot est un grand amateur de musiques de salon, il souhaite après chaque execution, vous faire partager sa passion. Il devrait donc mettre un player ou un lien youtube en bas de la page qu'il a vérifié afin que vous puissiez écouter un bout de son morceaux préféré. | Comme le TangoBot est un grand amateur de musiques de salon, il souhaite après chaque execution, vous faire partager sa passion. Il devrait donc mettre un player ou un lien youtube en bas de la page qu'il a vérifié afin que vous puissiez écouter un bout de son morceaux préféré. | ||
== Code == | == Code == | ||
[https://github.com/cavEpfl/TangoBot/ Code accessible sur Github] | [https://github.com/cavEpfl/TangoBot/ Code accessible sur Github] | ||
== Sources == | |||
[http://www.cis.drexel.edu/faculty/thu/research-papers/dawak-547.pdf Summary and Performance comparisons of different algorithms] | |||
[http://scikit-learn.org/stable/modules/feature_extraction.html scikit library] | |||
[[TangoBot BioPathBot]] | |||
Dernière version du 30 mai 2017 à 11:36
Résumé des fonctionnalités
Ce bot permet de supprimer les entrées redondantes sur une page.
Description technique
Pour pouvoir éliminer les entrées redondantes, il faut les comparer chacune les unes aux autres et estimer leur similarité.
Avant de comparer les phrases il faut les "nettoyer".
- Supprimer tout caractère spécial ou signe de ponctuation.
- Mettre tous les caractères en minuscule.
Séparer les mots et en filtrer certains.
- Les mots commençant par "http" sont des sources et il est préférable de les ignorer car ce ne sont pas des mots et n'aide pas à comparer le sens de la phrase.
- Les "stopwords", ("Mot vide") ('au', 'ce', 'du', 'étais', 'le' 'la', 'il', 'je', 'nous',...) sont des mots tellement communs qu'il est inutile de les prendre en compte, car il apparaissent avec une fréquence semblables dans n'importe quel texte. Ils n'aident pas à distinguer un texte par rapport à un autre et n'apporterait que de l'information inutile en plus. Par conséquent ils sont ignorés.
Et les modifier pour en avoir plus en commun.
- "Stemming", ("Racinisation") est un procédé de transformation des flexions en leur radical ou racine. Ce qui permet de lier par exemple les mots continuait, continuerai et continuant qui ont comme racine commune continu. L'algorithme de Porter est utilisée dans ce cas plutôt qu'un dictionnaire.
On applique ensuite le TF-IDF (Term Frequency-Inverse Document Frequency) qui est une méthode qui permet de d'évaluer l'importance d'un mot dans un texte.
L'idée du "term frequency" est juste le nombre d'occurrences dans un fichier sur le nombre d'occurrences totals dans tous les fichiers
tf(i,i) = n(i,i)/sum(n(k,i))
La fréquence inverse vise à donner plus de poids au terme moins fréquent qui peuvent aider à mieux différencier un texte d'un autre.
idf(i) = log{(abs(D)/abs(dj tq ti appartient à dj)} ou D est le nombre total de documents dans le corpus et le dénominateur le nombre de document ou le terme ti apparaît
Le poids s'obtient en multipliant les deux mesures: tfidf(i,j) = tf(i,j) * idf(i)
Le poids augmente proportionnellement au nombre d'occurrences du terme dans le texte.
On peut donc utiliser cette pondération pour décrire les différents textes dans un modèle vectoriel ou chaque document est représenté par un vecteur. Sous forme vectoriel il est très facile de calculer la similarité entre deux vecteurs (deux textes) par la similarité cosinus. Le produit scalaire de deux vecteurs A et B donne:
||A|| * ||B|| * cos(theta)
on peut donc déterminer l'angle theta et comme cos(theta) est compris entre -1 et 1 on peut évaluer le degré de similarité.
De 1 (identique) à -1 totalement opposées. Dans ce cas les vecteurs tf-idf sont toujours positif donc le degré de similarité est entre 0 (nulle) et 1.
Le degré de similarité à partir du quelle on considère que deux entrées sont les mêmes peut être estimé à partir de la moyenne des "cosine similarities" ainsi que de la "standard deviation" mais dans ce cas de figure nous avons trouvé que le TangoBot donnait de meilleurs résultats en considérant les valeurs > 0.5 (seuil fixe) comme suffisantes pour considérer l'égalité.
Une fois que le degré de similarité entre chaque document est établis le choix de quelle version des entrées dupliquées il faut garder se fait sur le nombre d'hyperliens dans l'entrées. Les entrées les plus complètes seront toujours gardées.
Exemples
Pour une page de test ou les exemples ci-dessous ont été traversés par le TangoBot voir: TANGOBOT TEST PAGE
1) Si le TangoBot compare deux phrases identiques :
- "1828.05.08 / Genève. Naissance de Henri Dunant. [1] | [2]." est présente deux fois dans la même page. Alors le TangoBot remarquera directement que les mêmes phrases possèdent les mêmes mots aux mêmes endroits. Il décidera donc d'en supprimer une des deux.
2) Si le TangoBot compare deux phrases contenant les mêmes mots-clés mais pas identiques :
- "1828.05.08 / Genève. Naissance de Henri Dunant. [3] | [4]."
- "1828.05.08 / Genève. Un médecin donne Naissance à Henri Dunant. [5] | [6]."
- Dans ce cas particulier, le TangoBot remarque que les mots clés des 2 phrases sont identiques. Alors le TangoBot ne garde que la première des deux phrases.
3) Si le TangoBot compare deux phrases similaires :
- "1828.05.08 / Genève. Naissance de Henri Dunant. [7] | [8]."
- "1828.05.08 / Genève. Henri Dunant est né. [9] | [10]."
- Ici, le TangoBot voit qu'il y a Henri Dunant dans les 2 phrases et que le nom est associé à "Naissance" et "né". Il établit donc un lien entre les 2 phrases et remarque qu'elles sont fortement similaires. Il décide donc de garder la première.
Evaluation des performances
Le TangoBot traite les erreurs dans le format des entrées en les ignorant, les considérant comme du simple texte et respecte donc leur ordre dans le document. Le TangoBot est tolérant.
Le TangoBot devient utile quand beaucoup de différents bots applique leurs tâches en s'ignorant les uns les autres et par conséquent crée des entrées dupliquées. Le TangoBot réunit il ne divise pas.
Le bot utilise des algorithmes qui calcule des similarités en se basant presque que sur les entrées de base, cela permet de gagner en performance même si on perd en précision comparé à des mesures de similarité linguistique qui vont utiliser de grand dictionnaires.
Le seuil utilisé pour considérer une entrée comme égale à une autre est fixe (0.5) dans ce cas. Idéalement il faudrait déterminer statistiquement quelle valeur est la meilleure ou encore en étudiant la distribution des scores de similarité.
Dans certains cas une entrée dupliquée est intentionnel, une option est désormais possible pour l'indiquer: <dup>. Ces faux positifs peuvent donc être évités en ajoutant cette balise à la fin.
Le bot pourrait être utilisé pour signaler les documents redondants sur Wikipast au lieu de juste les entrées.
Temps d'execution pour toutes les pages environ 3 minutes. (Le temps de 3 minutes est pour la première execution une fois les dupliqués détectés l'algorithme ne va pas repasser dessus et va donc évaluer seulement les changements, par conséquent le temps d'execution ne dépassera pas les 30 secondes après la première execution à moins d'une création massive de nouvelles entrées par un autre bot)
La majorité des entrées dupliquées détectées sont générées par d'autres bots. (95%) Peu de cas d'entrées sémantiquement identique. (<5%) Quelques cas de faux positifs. (<5%)
Scheduling
Etant donné que la majorité des entrées dupliquées sont crées par des bots, il est logique de faire tourner le TangoBot après leur passage. Une fois par jour convient très bien par rapport aux autres scheduling des bots.
Le tango
(Fonctionnalité historique) [deprecated] Comme le TangoBot est un grand amateur de musiques de salon, il souhaite après chaque execution, vous faire partager sa passion. Il devrait donc mettre un player ou un lien youtube en bas de la page qu'il a vérifié afin que vous puissiez écouter un bout de son morceaux préféré.