« TangoBot » : différence entre les versions
(Wikipastbot update) |
|||
| Ligne 1 : | Ligne 1 : | ||
== Résumé des fonctionnalités == | == Résumé des <span style="color:red">fonctionnalités</span> (correction(s): <span style="color:green">fonctionnalité | ||
</span>) == | |||
Ce bot permet de supprimer les entrées redondantes sur une page. | Ce bot permet de supprimer les entrées redondantes sur une page. | ||
| Ligne 13 : | Ligne 14 : | ||
Séparer les mots et en filtrer certains. | 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 mots commençant par "<span style="color:red">http</span> (correction(s): <span style="color:green"> | ||
*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. | </span>)" 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 "<span style="color:red">stopwords</span> (correction(s): <span style="color:green"> | |||
</span>)", ("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. | Et les modifier pour en avoir plus en commun. | ||
| Ligne 21 : | Ligne 24 : | ||
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. | 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 | L'idée du "<span style="color:red">term</span> (correction(s): <span style="color:green">terme, tem, perm, ter, team | ||
</span>) <span style="color:red">frequency</span> (correction(s): <span style="color:green"> | |||
</span>)" est juste le nombre d'occurrences dans un fichier sur le nombre d'occurrences <span style="color:red">totals</span> (correction(s): <span style="color:green">totale, totales, total | |||
</span>) dans tous les fichiers | |||
tf(i,i) = n(i,i)/sum(n(k,i)) | <span style="color:red">tf</span> (correction(s): <span style="color:green">taf, t, if, te, ta, té, tif, tu, tuf, f, t', to | ||
</span>)(i,i) = n(i,i)/<span style="color:red">sum</span> (correction(s): <span style="color:green">sui, suc, sut, sub, hum, sué, sur, su, sua, sue, sus, sumo, sud | |||
</span>)(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. | 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)} | <span style="color:red">idf</span> (correction(s): <span style="color:green">if, ide | ||
</span>)(i) = <span style="color:red">log</span> (correction(s): <span style="color:green">loi, los, lot, logo, lof, logé, lob, long, loge | |||
</span>){(<span style="color:red">abs</span> (correction(s): <span style="color:green">ans, rabs, abc, cabs, ais, dabs, abus, ars, as | |||
</span>)(D)/<span style="color:red">abs</span> (correction(s): <span style="color:green">ans, rabs, abc, cabs, ais, dabs, abus, ars, as | |||
</span>)(<span style="color:red">dj</span> (correction(s): <span style="color:green">d, dû, da, dé, du, d', do, dc, j, de, dm | |||
</span>) <span style="color:red">tq</span> (correction(s): <span style="color:green">t, te, ta, té, tu, q, t', to | |||
</span>) <span style="color:red">ti</span> (correction(s): <span style="color:green">pi, bi, tin, mi, si, ri, ci, li, t, té, tu, t', ni, gi, hi, tic, ta, toi, tri, tir, fi, ai, te, tif, i, to | |||
</span>) appartient à <span style="color:red">dj</span> (correction(s): <span style="color:green">d, dû, da, dé, du, d', do, dc, j, de, dm | |||
</span>))} | |||
ou D est le nombre total de documents dans le corpus | 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 | et le dénominateur le nombre de document ou le terme <span style="color:red">ti</span> (correction(s): <span style="color:green">pi, bi, tin, mi, si, ri, ci, li, t, té, tu, t', ni, gi, hi, tic, ta, toi, tri, tir, fi, ai, te, tif, i, to | ||
</span>) apparaît | |||
Le poids s'obtient en multipliant les deux mesures: | Le poids s'obtient en multipliant les deux mesures: | ||
tfidf(i,j) = tf(i,j) * idf(i) | <span style="color:red">tfidf</span> (correction(s): <span style="color:green"> | ||
</span>)(i,j) = <span style="color:red">tf</span> (correction(s): <span style="color:green">taf, t, if, te, ta, té, tif, tu, tuf, f, t', to | |||
</span>)(i,j) * <span style="color:red">idf</span> (correction(s): <span style="color:green">if, ide | |||
</span>)(i) | |||
Le poids augmente proportionnellement au nombre d'occurrences du terme dans le texte. | Le poids augmente proportionnellement au nombre d'occurrences du terme dans le texte. | ||
| Ligne 39 : | Ligne 59 : | ||
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. | 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: | Le produit scalaire de deux vecteurs A et B donne: | ||
||A|| * ||B|| * cos(theta) | ||A|| * ||B|| * <span style="color:red">cos</span> (correction(s): <span style="color:green">ces, co, cis, cors, nos, cor, cosy, com, cas, cop, coi, coq, cou, col, vos, cops, coqs, con, los, clos, dos, cous, mos, cois, cob, cons, cols, os, tos | ||
</span>)(<span style="color:red">theta</span> (correction(s): <span style="color:green">thêta | |||
</span>)) | |||
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é. | on peut donc déterminer l'angle <span style="color:red">theta</span> (correction(s): <span style="color:green">thêta | ||
</span>) et comme <span style="color:red">cos</span> (correction(s): <span style="color:green">ces, co, cis, cors, nos, cor, cosy, com, cas, cop, coi, coq, cou, col, vos, cops, coqs, con, los, clos, dos, cous, mos, cois, cob, cons, cols, os, tos | |||
</span>)(<span style="color:red">theta</span> (correction(s): <span style="color:green">thêta | |||
</span>)) 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. | De 1 (identique) à -1 totalement opposées. Dans ce cas les vecteurs <span style="color:red">tf</span> (correction(s): <span style="color:green">taf, t, if, te, ta, té, tif, tu, tuf, f, t', to | ||
</span>)-<span style="color:red">idf</span> (correction(s): <span style="color:green">if, ide | |||
</span>) 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é. | 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 "<span style="color:red">cosine</span> (correction(s): <span style="color:green">couine, cousine, copine, éosine | ||
</span>) <span style="color:red">similarities</span> (correction(s): <span style="color:green"> | |||
</span>)" ainsi que de la "standard <span style="color:red">deviation</span> (correction(s): <span style="color:green">déviation | |||
</span>)" 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. | Une fois que le degré de similarité entre chaque document est établis le choix de quelle version des entrées <span style="color:red">dupliquées</span> (correction(s): <span style="color:green">dupliqués | ||
</span>) il faut garder se fait sur le nombre d'<span style="color:red">hyperliens</span> (correction(s): <span style="color:green"> | |||
</span>) 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] | Pour une page de test ou les exemples ci-dessous ont été traversés par le [[TangoBot]] voir: [<span style="color:red">http</span> (correction(s): <span style="color:green"> | ||
</span>)://<span style="color:red">wikipast</span> (correction(s): <span style="color:green"> | |||
</span>).epfl.ch/<span style="color:red">wikipast</span> (correction(s): <span style="color:green"> | |||
</span>)/index.php/TangoBotTest TANGOBOT TEST PAGE] | |||
1) Si le TangoBot compare deux phrases identiques : | 1) Si le TangoBot compare deux phrases identiques : | ||
*"[[1828.05.08]] / [[Genève]]. [[Naissance]] de [[Henri Dunant]]. [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]." 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. | *"[[1828.05.08]] / [[Genève]]. [[Naissance]] de [[Henri Dunant]]. [<span style="color:red">http</span> (correction(s): <span style="color:green"> | ||
</span>)://letemps.archives.world/page/GDL_1978_04_20/5/%22Henri%20Dunant%22] | [<span style="color:red">http</span> (correction(s): <span style="color:green"> | |||
</span>)://letemps.archives.world/page/GDL_1985_10_26/14/%22Henry%20Dunant%22]." 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 : | 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]]. [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]]. [[Naissance]] de [[Henri Dunant]]. [<span style="color:red">http</span> (correction(s): <span style="color:green"> | ||
*"[[1828.05.08]] / [[Genève]]. Un médecin donne [[Naissance]] à [[Henri Dunant]]. [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]." | </span>)://letemps.archives.world/page/GDL_1978_04_20/5/%22Henri%20Dunant%22] | [<span style="color:red">http</span> (correction(s): <span style="color:green"> | ||
</span>)://letemps.archives.world/page/GDL_1985_10_26/14/%22Henry%20Dunant%22]." | |||
*"[[1828.05.08]] / [[Genève]]. Un médecin donne [[Naissance]] à [[Henri Dunant]]. [<span style="color:red">http</span> (correction(s): <span style="color:green"> | |||
</span>)://letemps.archives.world/page/GDL_1978_04_20/5/%22Henri%20Dunant%22] | [<span style="color:red">http</span> (correction(s): <span style="color:green"> | |||
</span>)://letemps.archives.world/page/GDL_1985_10_26/14/%22Henry%20Dunant%22]." | |||
*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. | *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 : | 3) Si le TangoBot compare deux phrases similaires : | ||
*"[[1828.05.08]] / [[Genève]]. [[Naissance]] de [[Henri Dunant]]. [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]]. [[Naissance]] de [[Henri Dunant]]. [<span style="color:red">http</span> (correction(s): <span style="color:green"> | ||
*"[[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]." | </span>)://letemps.archives.world/page/GDL_1978_04_20/5/%22Henri%20Dunant%22] | [<span style="color:red">http</span> (correction(s): <span style="color:green"> | ||
</span>)://letemps.archives.world/page/GDL_1985_10_26/14/%22Henry%20Dunant%22]." | |||
*"[[1828.05.08]] / [[Genève]]. [[Henri Dunant]] est né. [<span style="color:red">http</span> (correction(s): <span style="color:green"> | |||
</span>)://letemps.archives.world/page/GDL_1978_04_20/5/%22Henri%20Dunant%22] | [<span style="color:red">http</span> (correction(s): <span style="color:green"> | |||
</span>)://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. | ||
| Ligne 71 : | Ligne 116 : | ||
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 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 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 <span style="color:red">dupliquées</span> (correction(s): <span style="color:green">dupliqués | ||
</span>). 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 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. | ||
| Ligne 77 : | Ligne 123 : | ||
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é. | 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. | Dans certains cas une entrée <span style="color:red">dupliquée</span> (correction(s): <span style="color:green">dupliqués, dupliqué | ||
</span>) 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. | 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) | Temps d'<span style="color:red">execution</span> (correction(s): <span style="color:green">exécution | ||
</span>) pour toutes les pages environ 3 minutes. (Le temps de 3 minutes est pour la première <span style="color:red">execution</span> (correction(s): <span style="color:green">exécution | |||
</span>) 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'<span style="color:red">execution</span> (correction(s): <span style="color:green">exécution | |||
</span>) ne dépassera pas les 30 secondes après la première <span style="color:red">execution</span> (correction(s): <span style="color:green">exécution | |||
</span>) à 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%) | La majorité des entrées <span style="color:red">dupliquées</span> (correction(s): <span style="color:green">dupliqués | ||
Peu de cas d'entrées sémantiquement identique. (<5%) | </span>) détectées sont <span style="color:red">générées</span> (correction(s): <span style="color:green">vénérées, générés, générée | ||
</span>) par d'autres bots. (95%) | |||
Peu de cas d'entrées <span style="color:red">sémantiquement</span> (correction(s): <span style="color:green"> | |||
</span>) identique. (<5%) | |||
Quelques cas de faux positifs. (<5%) | Quelques cas de faux positifs. (<5%) | ||
=== Scheduling === | === 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. | Etant donné que la majorité des entrées <span style="color:red">dupliquées</span> (correction(s): <span style="color:green">dupliqués | ||
</span>) 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. | Une fois par jour convient très bien par rapport aux autres scheduling des bots. | ||
== Le tango == | == Le tango == | ||
(Fonctionnalité historique) [deprecated] | (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 <span style="color:red">execution</span> (correction(s): <span style="color:green">exécution | ||
</span>), 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 == | ||
| Ligne 100 : | Ligne 156 : | ||
== Sources == | == Sources == | ||
[http://www.cis.drexel.edu/faculty/thu/research-papers/dawak-547.pdf Summary and Performance comparisons of different algorithms] | [<span style="color:red">http</span> (correction(s): <span style="color:green"> | ||
</span>)://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] | [<span style="color:red">http</span> (correction(s): <span style="color:green"> | ||
</span>)://scikit-learn.org/stable/modules/feature_extraction.html scikit library] | |||
[[TangoBot BioPathBot]] | [[TangoBot BioPathBot]] | ||
Version du 30 mai 2017 à 08:05
== Résumé des fonctionnalités (correction(s): fonctionnalité
) ==
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 (correction(s):
)" 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 (correction(s):
)", ("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 (correction(s): terme, tem, perm, ter, team ) frequency (correction(s): )" est juste le nombre d'occurrences dans un fichier sur le nombre d'occurrences totals (correction(s): totale, totales, total ) dans tous les fichiers
tf (correction(s): taf, t, if, te, ta, té, tif, tu, tuf, f, t', to )(i,i) = n(i,i)/sum (correction(s): sui, suc, sut, sub, hum, sué, sur, su, sua, sue, sus, sumo, sud )(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 (correction(s): if, ide )(i) = log (correction(s): loi, los, lot, logo, lof, logé, lob, long, loge ){(abs (correction(s): ans, rabs, abc, cabs, ais, dabs, abus, ars, as )(D)/abs (correction(s): ans, rabs, abc, cabs, ais, dabs, abus, ars, as )(dj (correction(s): d, dû, da, dé, du, d', do, dc, j, de, dm ) tq (correction(s): t, te, ta, té, tu, q, t', to ) ti (correction(s): pi, bi, tin, mi, si, ri, ci, li, t, té, tu, t', ni, gi, hi, tic, ta, toi, tri, tir, fi, ai, te, tif, i, to ) appartient à dj (correction(s): d, dû, da, dé, du, d', do, dc, j, de, dm ))} ou D est le nombre total de documents dans le corpus et le dénominateur le nombre de document ou le terme ti (correction(s): pi, bi, tin, mi, si, ri, ci, li, t, té, tu, t', ni, gi, hi, tic, ta, toi, tri, tir, fi, ai, te, tif, i, to ) apparaît
Le poids s'obtient en multipliant les deux mesures: tfidf (correction(s): )(i,j) = tf (correction(s): taf, t, if, te, ta, té, tif, tu, tuf, f, t', to )(i,j) * idf (correction(s): if, ide )(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 (correction(s): ces, co, cis, cors, nos, cor, cosy, com, cas, cop, coi, coq, cou, col, vos, cops, coqs, con, los, clos, dos, cous, mos, cois, cob, cons, cols, os, tos
)(theta (correction(s): thêta ))
on peut donc déterminer l'angle theta (correction(s): thêta ) et comme cos (correction(s): ces, co, cis, cors, nos, cor, cosy, com, cas, cop, coi, coq, cou, col, vos, cops, coqs, con, los, clos, dos, cous, mos, cois, cob, cons, cols, os, tos )(theta (correction(s): thêta )) 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 (correction(s): taf, t, if, te, ta, té, tif, tu, tuf, f, t', to )-idf (correction(s): if, ide ) 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 (correction(s): couine, cousine, copine, éosine ) similarities (correction(s): )" ainsi que de la "standard deviation (correction(s): déviation )" 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 (correction(s): dupliqués ) il faut garder se fait sur le nombre d'hyperliens (correction(s): ) 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: [http (correction(s): )://wikipast (correction(s): ).epfl.ch/wikipast (correction(s): )/index.php/TangoBotTest TANGOBOT TEST PAGE]
1) Si le TangoBot compare deux phrases identiques :
- "1828.05.08 / Genève. Naissance de Henri Dunant. [http (correction(s):
)://letemps.archives.world/page/GDL_1978_04_20/5/%22Henri%20Dunant%22] | [http (correction(s): )://letemps.archives.world/page/GDL_1985_10_26/14/%22Henry%20Dunant%22]." 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. [http (correction(s):
)://letemps.archives.world/page/GDL_1978_04_20/5/%22Henri%20Dunant%22] | [http (correction(s): )://letemps.archives.world/page/GDL_1985_10_26/14/%22Henry%20Dunant%22]."
- "1828.05.08 / Genève. Un médecin donne Naissance à Henri Dunant. [http (correction(s):
)://letemps.archives.world/page/GDL_1978_04_20/5/%22Henri%20Dunant%22] | [http (correction(s): )://letemps.archives.world/page/GDL_1985_10_26/14/%22Henry%20Dunant%22]."
- 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. [http (correction(s):
)://letemps.archives.world/page/GDL_1978_04_20/5/%22Henri%20Dunant%22] | [http (correction(s): )://letemps.archives.world/page/GDL_1985_10_26/14/%22Henry%20Dunant%22]."
- "1828.05.08 / Genève. Henri Dunant est né. [http (correction(s):
)://letemps.archives.world/page/GDL_1978_04_20/5/%22Henri%20Dunant%22] | [http (correction(s): )://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.
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 (correction(s): dupliqués ). 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 (correction(s): dupliqués, dupliqué ) 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 (correction(s): exécution ) pour toutes les pages environ 3 minutes. (Le temps de 3 minutes est pour la première execution (correction(s): exécution ) 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 (correction(s): exécution ) ne dépassera pas les 30 secondes après la première execution (correction(s): exécution ) à moins d'une création massive de nouvelles entrées par un autre bot)
La majorité des entrées dupliquées (correction(s): dupliqués ) détectées sont générées (correction(s): vénérées, générés, générée ) par d'autres bots. (95%) Peu de cas d'entrées sémantiquement (correction(s): ) identique. (<5%) Quelques cas de faux positifs. (<5%)
Scheduling
Etant donné que la majorité des entrées dupliquées (correction(s): dupliqués ) 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 (correction(s): exécution ), 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
Sources
[http (correction(s): )://www.cis.drexel.edu/faculty/thu/research-papers/dawak-547.pdf Summary and Performance comparisons of different algorithms]
[http (correction(s): )://scikit-learn.org/stable/modules/feature_extraction.html scikit library]