Animint

  Anime & manga

 
 
“Animint traite des dessins animés japonais et du manga. Outre ce blog, le site comporte plusieurs milliers de pages de texte illustré.”

Filtre naïf de Bayes en Php

Par le :: Webmastering

mangas

Notre problématique

Notre annuaire de sites francophones  présente toujours un petit souci au niveau des inscriptions via le formulaire de soumission. De plus en plus d’outils automatiques de soumission permettent à un webmestre lambda d’inscrire son site à une flopée d’annuaires, sans s’occuper de savoir si son inscription est pertinente ou pas. Ce n’est pas ce genre d’outils qui améliore le référencement, et même au contraire, cela peut pourrir vos scores si vous inscrivez votre site dans un mauvais annuaire. La problématique du référencement pourra faire l’objet d’un autre billet mais ce n’est pas le sujet abordé ici.

En pratique, nous nous retrouvons avec des soumissions aussi rocambolesques que de la charcuterie auvergnate trucmuche ou que de l’agence marocaine de voyages bidule. Autant d’entrées qui finissent directement au panier mais qui sont casse-pieds à traiter à la longue, étant donnée que nous effectuons une vérification manuelle pour valider chaque site.

Les stratégies possibles

Diverses stratégies s’offrent à nous pour palier au problème. La première est de bloquer les inscriptions automatiques en travaillant sur le formulaire proprement dit. Pendant une période, nous avons ajouté une image dont il fallait copier les caractères affichés dans un champ pour valider le formulaire. Nous pouvions aussi user du code javascript pour transformer le formulaire en un item estampillé Web 2.0 très à la mode. D’un autre côté, ces actions ne vont pas dans le sens d’un site privilégiant l’accessibilité et freinent les utilisateurs dont nous attendons les sites web. De plus, les agents de soumission automatique sont de plus en plus intelligents et rien ne garantie que ces obstacles restent longtemps efficaces. Sur ce point, le formulaire a été retravaillé pour freiner les robots basiques de soumission tout en restant transparent pour un utilisateur humain, sans qu’il ait une contrainte au niveau de l’activation du Javascript et des cookies dans son navigateur web.

En fait, nous nous sommes plutôt penchés sur le vrai problème, que le site soit soumis par un humain ou par un programme, c’est-à-dire rejeter les entrées hors sujets, donc plutôt à s’intéresser au contenu soumis qu’à la façon dont il est soumis. La solution consiste à ajouter un filtre anti-spam, de la même façon qu’il en existe pour le courrier électronique. Un outil comme spam-assassin, largement utilisé et reconnu pour son efficacité, s’appuie en gros sur deux types d’algorithme : Le premier gère des règles précises concernant le format du mail, les entêtes, l’encodage utilisé, etc. De là découle une première note pour le mail traité. Le second type de traitement, basé sur le théorème de Bayes, calcule la probabilité que le contenu du mail soit un spam, proprement dit. Le savant dosage des deux méthodes aboutit à déterminer si le mail est oui ou non un spam. Un tel outil n’est pas directement adaptable sur notre problème de soumission de liens. Tout d’abord pour des questions techniques mais également pour des questions logiques :   A supposer que nous arrivons à définir des règles quant à la validité d’une inscription, elles n’ont rien à voir avec celles gouvernant la bonne syntaxe d’un mail électronique. De même, il y a spam et spam. Spam assassin aura une approche neutre quant à un mail en anglais tandis que nous, nous rejetons une soumission en anglais dans 100% des cas, vue que notre site est francophone. Par ailleurs, nous recensons les boutiques de vente en ligne de manga alors que dans un mail, un message commercial a de fortes chances d’être rejeté. Ici, ce ne sera pas forcément le cas. La base de connaissance ne peut pas être la même.

Cette base de connaissance est basée sur des mots. Dans le passé, les filtres se focalisaient sur des listes blanches et noires, qui suivant la liste où le mot d’un texte était trouvé, le texte était estampillé bon ou spam. Cette approche est très réductrice même si elle peut être un bon complément dans notre cas. Si nous sommes quasiment sûrs de rejeter une entrée avec le mot hardcore, il n’en est pas de même avec le mot boutique : boutique manga aura des chances de passer, contrairement à boutique de lingerie. Il faut raisonner en terme de probabilités. Le filtre s’appuie en fait sur la probabilité pour qu’un mot fasse partie du vocabulaire de spam ou non spam pour en déduire la probabilité du texte en entier quant à son statut de spam ou non spam.

Ed de Cowboy Bebop

Les équations

C’est là où le théorème de Bayes intervient : Il nous dit que la probabilité d’avoir du spam quand nous voyons les mots M1, M2, M3, etc. est égale à la probabilité d’observer du spam dans l’absolu multiplié par la probabilité de voir les mots M1, M2, M3, etc.  dans un texte de spam, le tout divisé par la probabilité de voir les mots M1, M2, M3 dans un texte, quoiqu’il soit.

P(S | M1, M2, M3, …) = P (S) * P (M1, M2, M3, … | S) / P (M1, M2, M3, …)

Nous considérons que les probabilités pour chaque mot, qu’il fasse partie du vocabulaire spam, lorsque nous les observons dans la nature, sont décorellées. Ceci est faux dans l’absolu, étant donnée la richesse de notre langue et les associations de mots, mais cela nous permet d’écrire, avec cette vision naïve :

P (M1, M2, M3, …| S) = P (M1 | S) * P (M2 | S) * P (M3 | S) …
P (M1, M2, M3, …) = P (M1) * P (M2) * P (M3) …

C’est-à-dire que la probabilité de voir apparaître les mots M1, M2, M3 dans un spam, ou dans texte, est égale au produit de la probabilité de chacun de ces mots dans un spam, ou respectivement, dans un texte. Nous notons désormais P (S | D) = P (S | M1, M2, M3, …), M1, M2, M3, … constituant le document D à traiter.

Du coup, la formule devient
P (S | D) = (P (S) * P (M1 | S) * P (M2 | S) * P (M3 | S) …) / (P (M1) * P (M2) * P (M3) …)

Suivant le même principe, nous pouvons remplacer la classe spam, S, par la classe non spam, NS, dans la formule.

P (NS | D) = (P (NS) * P (M1 | NS) * P (M2 | NS) * P (M3 | NS) …)  / (P (M1) * P (M2) * P (M3) …)

Le dénominateur Z = (P (M1) * P (M2) * P (M3) …) est commun aux deux formules et n’a donc pas d’incidence sur la probabilité qu’un texte avec les mots M1, M2, M3,.. soit un spam ou un non spam. L’enlever nous fait juste perdre un coefficient de normalisation de la valeur de P (NS | D) et de P (S | D).

De toute façon, en passant Z à gauche des équations, nous obtenons

Z =  (P (NS) * P (M1 | NS) * P (M2 | NS) * P (M3 | NS) …)  / P (NS | D) = (P (S) * P (M1 | S) * P (M2 | S) * P (M3 | S) …) / P (S | D)

D’où

P (NS | D) / P (S | D) = (P (NS) * P (M1 | NS) * P (M2 | NS) * P (M3 | NS) …) / (P (S) * P (M1 | S) * P (M2 | S) * P (M3 | S) …)

Les probabilités sont des nombres inférieurs à 1, voire beaucoup inférieur à 1. Si le nombre de mots est élevé, les multiplications ci-dessous peuvent rapidement devenir un problème de traitement au niveau de la machine, qui est limitée en terme de précision. Il est donc judicieux de passer à l’usage du logarithme népérien qui adoucit la profondeur des calculs.

Ln (P (NS | D) / P (N | D)) = Ln (P (NS) / P (S)) + Ln (P (M1 | NS) / P (M1 | S)) + Ln  (P (M2 | NS) / P (M2 | S)) + (P (M3 | NS) / P (M3 | S)) + …

Un document D est un spam si bien entendu

P (NS | D) < P (N | D) 

Donc si :

P (NS | D) / P (N | D) < 1.

Ce qui donne avec le logarithme népérien :

Ln (P (NS | D) / P (N | D)) < 0

Soit finalement si:

Ln (P (NS) / P (S)) + Ln (P (M1 | NS) / P (M1 | S)) + Ln (P (M2 | NS) / P (M2 | S)) + (P (M3 | NS) / P (M3 | S)) + … < 0

L’apprentissage

L’équation obtenue n’a d’utilité que si nous connaissons les valeurs de P (NS),  P(S),  P (M1 | NS), P(M2 | NS), P(M3 | NS), …, P(M1 | S), P(M2 | S), P(M3 | S), …etc.

Ces valeurs sont obtenues par apprentissage. En langage de probabilité, nous faisons des tirages et en déduisons les valeurs suite à l’observation. Pour revenir à quelque chose de moins théorique, l’apprentissage du spam et no spam, par un système, peut être simple.

Nous lui soumettons différents documents en lui signalant s’il s’agit d’un texte que nous classerions spam ou non spam. Il calcule le nombre d’occurrences pour chaque mot, pour chaque classe, spam et non spam, et il en déduit les probabilités d’avoir du spam, d’avoir du non spam, et pour chaque mot, la probabilité qu’un mot soit vu dans un spam ou dans un non spam.

Il faut une base solide pour que les valeurs soient significative et que vous ne preniez pas comme source, des probabilités marginales. Si mes souvenirs sont bons, en pratique, un filtre anti spam pour mail s’appuie sur quatre mille messages.  Cependant, l’apprentissage et l’observation sont imparfaits. Il est peu vraisemblable d’ailleurs que vous puissiez fournir l’intégralité des mots en apprentissage au système. Si un mot est complètement inconnu, il n’est pas pris en compte pour l’équation. Cependant, vous rencontrerez les cas où vous aurez une probabilité pour un mot en classe spam, mais pas en classe non spam, ou bien l’inverse. Supposons que le mot Martinique a été trouvé parmi les spam mais que nous n’avons pas d’occurrence dans les non spam. P (Martinique | NS) = 0 et P (Martinique | S) = 1 dans ce cas. Dans l’absolu, c’est faux, car il se peut qu’il y ait un site manga qui aurait le mot Martinique dans sa description, par exemple. P (Martinique | NS) = 0 vient d’une observation imparfaite et vient plomber notre équation en donnant une valeur moins l'infini, faisant fi des autres facteurs qui auraient pu tirer la valeur dans un sens ou dans l’autre.

Ce qui est sûr en revanche, c’est que P (Martinique | NS) est faible, en tout cas plus faible que les probabilités observées. Dans l’équation, P (Martinique | NS) devient ainsi non nulle. C’est ce que nous appelons dans le jargon, un lissage de Laplace.

L'implémentation en PHP

Il existe quelques exemples sur le net de codage de filtre utilisant l’application naïve du théorème de Bayes. Dans notre cas, nous nous sommes limités à deux classes, spam et non spam mais nous pouvons avoir des applications avec plusieurs classes. Cela a l’inconvénient de compliquer les explications et de nous éloigner de notre but initial, qui est d'effectuer un choix binaire. Des recherches sur les mots clefs naive bayes theorem ou encore bayesian classifier devraient vous rapporter un bon nombre d’explications, généralement en anglais, hélas pour vous, si vous êtes anglophobe.

Un exemple intéressant pour débuter est celui trouvé en français sur le blog d’XHTML.net. Au-delà  du codage des boucles de calcul, son auteur propose une implémentation complète avec formulaire et base de données derrière, avec une approche objet quant à la conception du code concernant les filtres bayesiens.

Mes quelques remarques

En ce qui concerne le code fourni sur XHTML.net

-    Le code est un exercice complet donc comporte une partie de connexion et de gestion de la base de données. Si vous avez déjà une couche d’abstraction pour votre base de données, quelques retouches sont nécessaires.

-    Le filtre prévoit l’utilisation d’une liste de mots à ignorer et ce, à juste titre. Un mot comme ‘site’ dans notre cas, n’a aucune incidence sur la décision de spam ou non spam. Autant ne pas en tenir compte avent de polluer notre base de connaissance avec. L’implémentation se limite à une insertion en dur dans le code, d’un tableau de mot. Il vous faudra coder la gestion de cette liste par la base de données. Rien de bien méchant.

-    Les calculs des probabilités s’effectuent directement en produit, au lieu d’utiliser les logarithmes népériens. Même si une valeur est mise en facteur pour éviter les dépassements de précision, celle-ci n’est pas adaptée dès que vous avez plusieurs mots. Le mieux est sans doute d’insérer des fonctions log, qui transforment ensuite vos produits en sommes et vous donnent une réserve en terme de calculs.

-    P(S)  est déduite dans le code en faisant le rapport du nombre d’occurrence de mots trouvés en spam par le nombre total d’occurrences des mots. Elle n’est pas déduite du rapport du nombre de documents spam par le nombre total de documents.

-    L’outil prend en compte dans les calculs les probabilités d’un mot même s’il n’a été rencontré qu’une fois. Même avec le coefficient de lissage de Laplace, les probabilités sont faussées. Dans notre version pour les liens, nous n’en tenons compte que si le mot a plusieurs occurrences.

-    J’ai des doutes sur la valeur du coefficient choisi pour le lissage de Laplace. Un autre document sur le net proposait une valeur précise, mais visiblement empirique. Il faudrait le retrouver.

Urd et Skuld devant un ordinateur

Discuter de ce billet sur le forum - - Laisser un commentaire »

Cet article vous a plu?

Faites-le connaître ou votez pour cet article sur les sites suivants :

  • anime manga aggregator sama
  • Partager sur del.li.cious
  • Partager sur Facebook
  • Partager sur Google

Commentaires sur ce billet:

  1. Le 05/05/2010 à 10:33
    canasawa a dit

    je cherche un travail complet d'anti spam:conception et implementation

Ajoutez votre commentaire:

Merci de bien vouloir soigner votre orthographe et de proscrire le style SMS.


Le code HTML est affiché comme du texte et les adresses web sont automatiquement transformées.

 

↑ Haut de page