Cours classification automatique des textes, tutoriel & guide de travaux pratiques en pdf.

Pondération des termes

Plusieurs options s’offrent à ce stade du processus, certainement la plus utilisée c’est TF-IDF, mais puisque notre objectif c’est chercher plus d’efficacité avec des résultats acceptables, et ne pas alourdir l’algorithme avec des calculs supplémentaires, nous avons choisi d’utiliser, dans l’ensemble de nos expérimentations, la façon la plus simple pour calculer cette pondération à savoir la fréquence du terme dans le document ou dans la catégorie.

Naïve Bayes

Naïve Bayes classifier est le représentant le plus populaire des classifieurs probabilistes et son théorème est au cœur de la problématique de la classification. C’est l’une des méthodes les plus pratiques d’apprentissage, avec les kPPV, Rocchio, les SVM, les arbres de décision, les réseaux de neurones. En revanche si les modèles vectoriels fonctionnent bien, leur fondement est entièrement empirique. Ils sont le résultat de nombreuses années de test. Le modèle probabiliste, au contraire, s’appuie sur une base théorique précise.
Le classifieur bayésien naïf reste un des outils de catégorisation de documents les plus pratiques en raison de ses performances reconnues dans ce domaine, et est aujourd’hui intégré à de nombreux produits commerciaux. Il s’appuie sur un modèle de génération d’un document à partir duquel on peut déduire la ou les classes les plus probables d’appartenance du document. Les paramètres du modèle sont estimés à partir d’un corpus d’apprentissage.
Plusieurs expériences ont démontré les bonnes performances de l’algorithme. L’équipe Microsoft a développé son propre algorithme NB connu par MNB (Microsoft Naïve Bayes) qui est un algorithme de classification fourni par Microsoft SQL Server 2005 Analysis Services (SSAS), conçu pour la modélisation prédictive. (Présenté dans l’annexe MNB).
Le principe qui régit et donne son nom à l’algorithme est très simple. Il indique simplement que les différents attributs (dans le cas du texte, les différents termes présents dans le document) sont considérés comme indépendants. C’est la même hypothèse que pour le modèle vectoriel mais cette fois exprimée explicitement dans le cadre de la théorie probabiliste.
Avant de justifier les raisons qui ont motivé l’adoption de cette méthode dans notre approche proposée, nous avons préférer rappeler quelques définitions nécessaires pour une bonne maîtrise du classifieur Naïve Bayes.
Notons que nous avons repris, dans cette section, quelques définitions proposées dans (www.fr.wikipedia.org)

Probabilité conditionnelle

La notion de probabilité conditionnelle permet de tenir compte dans une estimation d’une information complémentaire. Par exemple, si je tire au hasard une carte d’un jeu, j’estime naturellement à une chance sur quatre la probabilité d’obtenir un cœur ; mais si j’aperçois un reflet rouge sur la table, je corrige mon estimation à une chance sur deux. Cette seconde estimation correspond à la probabilité d’obtenir un cœur sachant que la carte est rouge. Elle est conditionnée par la couleur de la carte ; donc, conditionnelle.
En théorie des probabilités, la probabilité conditionnelle d’un événement A, sachant qu’un autre événement B de probabilité non nulle s’est réalisé est noté P(A / B) défini par :
Le réel P(A / B) se lit « probabilité de A, sachant B ». P(A / B) se note aussi parfois PB(A) Mathématiquement, soient ( , B , P), un espace probabilisé et B un événement de probabilité non nulle. À tout événement A de B, nous associons le nombre noté P(A / B) ou PB(A) défini par:
Nous pourrions vérifier que l’application PB définie par A ◊ PB(A) est une probabilité.
Et P(A/ B)P(A/ B) 1

Théorème de Bayes

Le théorème de Bayes ou le modèle d’indépendance conditionnelle (Naïve Bayes classifier), qui a été proposé par le mathématicien anglais Thomas Bayes (1702-1761), fournit un cadre théorique pour la problématique de la classification. Dans cette approche, tous les paramètres, sont considérés comme des variables aléatoires issues d’une distribution de probabilité.
Le théorème de Bayes est utilisé dans l’inférence statistique pour mettre à jour ou réviser les estimations d’une probabilité ou d’un paramètre quelconque, à partir des observations et des lois de probabilité de ces observations. Il y a une version discrète et une version continue du théorème.
En théorie des probabilités, le théorème de Bayes énonce des probabilités conditionnelles : étant donné deux évènements A et B, le théorème de Bayes permet de déterminer la probabilité de A sachant B, si l’on connaît les probabilités :
• de A ;
• de B ;
• de B sachant A.
Ce théorème élémentaire (originellement nommé « de probabilité des causes ») a des applications considérables.
Pour aboutir au théorème de Bayes, on part d’une des définitions de la probabilité conditionnelle :
en notant la probabilité que A et B aient tous les deux lieu. En divisant de part et d’autre par P(B), on obtient :
Qui donne bien le théorème de Bayes.
Chaque probabilité du théorème de Bayes a une dénomination usuelle.
• P (A) est la probabilité a priori de A, elle est « antérieure » au sens qu’elle précède toute information sur B, P(A) est aussi appelée la probabilité marginale de A.
• De même, P (B) est appelé la probabilité marginale ou a priori des donnés d’apprentissage B.
• P (A/B) est appelée la probabilité a posteriori de A sachant B (ou encore de A sous condition B), elle est « postérieure », au sens qu’elle dépend directement de B.
• P (B/A), pour un B connu, est appelé la fonction de vraisemblance de A (ou encore de B sous condition A)

Inférence bayésienne

On nomme inférence bayésienne la démarche logique permettant de calculer ou actualiser la probabilité d’une hypothèse. Le raisonnement bayésien est appliqué à la prise de décision, on utilise la connaissance des événements pour prédire des événements futurs. Cette démarche est régie par l’utilisation de règles strictes de combinaison des probabilités, desquelles dérive le théorème de Bayes.
Exemple d’inférence bayésienne :
D’où vient ce biscuit ?
(Cet exemple est extrait de l’article anglophone www.wikipedia.en)
Imaginons deux boîtes de biscuits.
L’une, A, comporte 30 biscuits au chocolat et 10 ordinaires.
L’autre, B, en comporte 20 de chaque sorte.
On choisit les yeux fermés une boîte au hasard, puis dans cette boîte un biscuit au hasard. Il se trouve être au chocolat. De quelle boîte a-t-il le plus de chances d’être issu, et avec quelle probabilité ? Intuitivement, on se doute que la boîte A a plus de chances d’être la bonne, mais de combien ?
Notons HA la proposition « le gâteau vient de la boîte A » et HB la proposition « le gâteau vient de la boîte B ». Dans un contexte de classification A et B c’est des classes et D est un document.
Si lorsqu’on a les yeux bandés les boîtes ne se distinguent que par leur nom, nous avons P(HA) = P (HB), et la somme fait 1, puisque nous avons bien choisi une boîte, soit une probabilité de 0,5 pour chaque proposition.
Notons D l’événement désigné par la phrase « le gâteau est au chocolat ». Connaissant le contenu des boîtes, nous savons que :
• P (D / HA) = 30/40 = 0,75
• P (D / HB) = 20/40 = 0,5
La formule de Bayes nous donne donc :
P (HA / D) représente la probabilité d’avoir choisi la boîte A sachant que le gâteau est au chocolat.
Avant de regarder le gâteau, notre probabilité d’avoir choisi la boîte A était P (HA), soit 0,5.
Après l’avoir regardé, nous révisons cette probabilité à P (HA /D), qui sera 0,6. L’observation D « le gâteau est au chocolat » nous a donc apporté une augmentation de 10% sur la probabilité initiale de HA « le gâteau vient de la boîte A ».
Et puisque P (HA /D) + P (HB /D)= 1 (pas d’autre possibilité que d’avoir choisi la boîte A ou la boîte B sachant que le gâteau est au chocolat), la probabilité d’avoir choisi la boîte B sachant que le gâteau est au chocolat est donc de 1 – 0,6 = 0,4.

La classification naïve bayesienne

La classification naïve bayesienne est un type de classification bayesienne probabiliste simple basée sur le théorème de Bayes avec une forte indépendance (dite naïve) des hypothèses.
Définition de l’indépendance :
« Two events A and B are statistically independent if the probability of A is the same value when B occurs, when B does not occur or when nothing is known about the occurrence of B » «Deux événements A et B sont statistiquement indépendants si la probabilité de A est la même lorsque B se réalise, ou lorsque B ne se réalise pas, ou encore quand on ne sait rien sur B »
A et B sont indépendants alors :
Exemple :
Supposons qu’il ya deux événements:
A : Amine enseigne la classe sinon c’est Abderahim
B : Il pleut
Nous remarquons que la météo ne dépend pas et n’as pas d’influence sur lequel des professeurs qui va enseigner la classe.
Cela peut être spécifié très simplement par :
Cette propriété implique les règles suivantes :
• P(¬A/B)=P(¬A)
• P(B / A) = P(B)
• P(B ∩ A) = P(B) P(A)
• P(¬ B ∩ A) = P(¬ B) P(A)
• P(B ∩ ¬ A) = P(B) P(¬A)
• P(¬B∩¬A)=P(¬B)P(¬A)

Maximum A Posteriori (MAP) et Maximum de vraisemblance (ML)

En général, nous cherchons l’hypothèse la plus probable compte tenu des données d’apprentissage :
Maximum A Posteriori (MAP)
hMAP= arg maxP(h/d) où h appartient à H l’espace des hypothèses et d à l’espace des événements
¬ hMAP  arg max P(d/h) P(h) P(d)
P (d) peut être ignoré car il est le même pour toutes les probabilités
¬ hMAP = arg max P(d/h) P(h) Exemple :
Pour une classification bi-classe comme par exemple les filtres anti-spam :
L’espace des hypothèses correspond à l’appartenance aux classes, on notera :
P(ci/di) = arg max P(di/ci) P(ci)
di est un document
c1 correspond à la classe spam
c2 correspond à la classe non spam
P(ci/di) = arg max{ P( di/c1) P(c1) , P(di/c2) P(c2)}
Maximum de vraisemblance (ML)
Si on suppose que les probabilités à priori sont les mêmes pour toutes les classes (exemple des deux boîtes de biscuits) alors on aura :
P(ci) = P(cj)
Une simplification plus poussée nous conduit à :
¬ hML = arg max P (di/ci)
L’estimation des paramètres pour les modèles de Bayes naïf utilise la méthode du maximum de vraisemblance.
Le calcul de P (di/cj) dépend du modèle de génération des exemples. Dans le domaine de classification de textes, les plus populaires sont le modèle multivarié de Bernoulli et le modèle multinomial.

Le modèle multivarié de Bernoulli

Dans le modèle le plus simple, un document est un vecteur binaire de la taille du vocabulaire. Il est généré par tirage aléatoire : chaque terme du vocabulaire peut être présent ou absent avec une certaine probabilité. Seule la présence/absence des termes est utilisée. Leur nombre d’occurrences dans le document n’a pas d’incidence. Le document se représente comme le résultat du tirage de T variables aléatoires indépendantes : t1,….,tv. Pour rendre les formules exploitables, on fait de plus l’hypothèse d’indépendance des termes (hypothèse naïve Bayes).
P(di/cj) se simplifie alors en un produit de probabilités d’occurrences de chaque terme :
Il est possible d’estimer P(tk/cj) à partir des exemples du corpus d’apprentissage. On utilise généralement l’estimateur du maximum de vraisemblance.
Que faire si on retrouve une probabilité nulle P (tj / ci) = 0 ? (Un terme absent de tous les documents d’une classe)
Comme les probabilités de chaque terme sont multipliées, il suffit en effet qu’un seul terme dans un document à classer ne soit présent dans aucun document d’une classe (ce qui arrive souvent dans le domaine du texte où beaucoup de termes apparaissent très rarement) pour que la probabilité que le document appartienne à cette classe soit nulle.
La correction Laplacienne ou le lissage de laplace (laplace smoothing) intervient pour éviter ces probabilités nulles. Le lissage effectué pendant l’estimation, qui consiste à ajouter 1 à chaque terme, est indispensable.
Puisque le nombre de termes de la base d’apprentissage est important, l’ajout de 1 sera négligeable. On parvient alors, dans le cas du lissage de laplace, à :
Pour illustrer le lissage de Laplace : dans une base composée de 750 termes, la probabilité d’un terme absent sera (1+0) / (2+1350) = 0,0007396 au lieu de 0 / 1352 = 0

Le modèle multinomial

Dans le modèle précédent, il n’est pas possible d’utiliser les fréquences des termes dans les documents. Pour prendre en compte cette information supplémentaire, un autre modèle plus complexe a été proposé, et qui a été adopté dans notre approche proposée. Un document est une séquence de mots, chacun étant tiré aléatoirement parmi l’ensemble des mots du vocabulaire. Un document est donc généré par une distribution multinomiale des mots avec autant de tirages que de mots dans le document. Il est ainsi possible de prendre en compte la longueur des documents bien que cela soit rarement fait en pratique. L’hypothèse d’indépendance des termes reste nécessaire.
Les probabilités sont une nouvelle fois estimées à partir des occurrences des exemples du corpus avec l’estimateur du maximum de vraisemblance avec un lissage de laplace :
Tct le nombre d’occurrences du terme t dans tous les documents de la classe c,
Tct’ le nombre d’occurrences de tous les termes y compris t des documents de la classe c. Quant à la classification, l’estimation P(di/cj) est calculée suivant le modèle utilisé en remplaçant les probabilités par leur estimateur et la classe cj ayant la probabilité la plus élevée sera attribuée au document di .

Description de l’algorithme

Il y a plusieurs variantes de l’algorithme NB, voici une description d’une d’entre elles :
1- Préparer les associations (texte, classe d’appartenance) pour tous les documents d’apprentissage.
2- Préparer le document à classifier sous la forme (termes, nombre d’occurrences).
3- Compter pour chaque classe le nombre de documents appartenant a cette classe.
4- Calculer pour chaque classe la probabilité à priori.
5- Calculer de nombre de termes contenus dans une classe et le nombre d’occurrences de chaque terme dans toutes les classes, ce traitement à effectuer sur tous les termes des documents de training.
6- Calculer pour chaque classe la probabilité à posteriori.
7- La classe ayant la probabilité la plus élevée sera attribuée au document.

Avantages de la méthode adoptée (Naïve Bayes Classifier)

Cet algorithme dont le modèle d’apprentissage est très général est utilisé dans de nombreux autres domaines que le texte.
David.D Lewis dans (Lewis, 2004) et Hassane Hilali dans (Hilali, 2009) listent un ensemble d’avantages du classifieur bayésien naïf, parmi lesquelles :
• Algorithme facile et simple à implémenter
• Basée sur une théorie mathématique précise
• Efficacité et rapidité dans l’apprentissage et la classification
• Facile à mettre à jour avec de nouveaux exemples d’apprentissage
• Equivalent à un classifieur linéaire, dans sa rapidité d’application