Data Mining

Ce document présente un travail dirigé (TD) sur la classification de textes à l'aide de la méthode de Naïve Bayes. Il vise à tester les compétences en traitement automatique du langage, en représentation vectorielle des textes, et en application d'un classifieur probabiliste pour distinguer des emails spam de non-spam.

1. Introduction

Le but de ce TD est de démontrer l’utilisation de la méthode de Naïve Bayes pour la classification de textes. Cette méthode probabiliste permet de prédire la classe d’un texte (spam ou non-spam) à partir de ses caractéristiques textuelles.

2. Le problème et les données

On dispose d’un ensemble de 1000 emails, chacun étiqueté comme spam ou non-spam, provenant du SpamAssassin Public Corpus. L’objectif est de construire un classifieur Naïve Bayes capable de détecter si un nouvel email est un spam ou non.

Voici deux exemples d’emails :

• Email 1 (non-spam) : discussion sur le coût d’hébergement d’un portail web.
• Email 2 (spam) : publicité pour l’achat de Viagra en ligne avec garantie de qualité.

3. Représentation des textes

La première étape consiste à transformer les textes en vecteurs numériques de dimension P, où chaque dimension correspond à un mot du vocabulaire V.

Les étapes sont :

1. Normaliser les textes :
• Extraire les racines des mots (lemmatisation).
• Supprimer les mots non importants (prépositions, articles, pronoms).
2. Construire un vocabulaire V à partir de l’ensemble des textes.
3. Appliquer le modèle sac de mots binaire : chaque texte est représenté par un vecteur binaire indiquant la présence (1) ou l’absence (0) de chaque mot du vocabulaire.

Le vocabulaire V est donné et contient 16 mots (racines) :

best, big, buck, buy, cost, expect, host, http, month, pay, portal, run, satisf, sell, web, www

On applique la normalisation et la représentation binaire aux deux emails exemples :

• Pour l’email 1 (non-spam), on identifie les mots présents parmi les 16 du vocabulaire et on crée un vecteur x1 où chaque composante vaut 1 si le mot est présent, 0 sinon.
• Pour l’email 2 (spam), on fait de même pour obtenir le vecteur x2.

Les vecteurs ne sont pas explicitement fournis dans le document, mais la méthode est claire.

4. Classification de textes avec méthode de Naïve Bayes

a. Construction du classeur Naïve Bayes

On suppose que tous les textes sont déjà transformés en vecteurs x de 16 attributs binaires. Le but est d’estimer les probabilités conditionnelles Pr[xi | y, X] pour chaque mot i et chaque classe y (spam ou non-spam).

On note :

• n(m, y) : nombre de textes de la classe y contenant le mot m.
• n(y) : nombre total de textes de la classe y.

On rappelle les formules :

Pr[xi = 1 | y, X] = n(mi, y) / n(y)
Pr[xi = 0 | y, X] = 1 - Pr[xi = 1 | y, X]

Le travail consiste à compléter un tableau (Table 1) avec ces probabilités conditionnelles pour chaque mot du vocabulaire et chaque classe.

Par exemple, pour le mot "best" (i=1) et la classe non-spam :

• Calculer Pr[x1=1 | y=non-spam, X] = n(best, non-spam) / n(non-spam)
• Calculer Pr[x1=0 | y=non-spam, X] = 1 - Pr[x1=1 | y=non-spam, X]

Il faut faire de même pour tous les mots et pour la classe spam.

Sans données numériques précises, on ne peut pas compléter ce tableau ici.

b. Classification d’un nouvel email

On considère un nouvel email :

Looking forward to your call and I will introduce you to people like yourself who are currently making $10,000 plus per week!

Étapes :

1. Normaliser ce texte (extraction des racines, suppression des mots non importants).
2. Représenter ce texte par un vecteur binaire x selon le vocabulaire V.
3. Remplir les valeurs de x dans le tableau (Table 2) correspondant aux mots du vocabulaire.
4. Utiliser la formule Naïve Bayes :

y = argmax_{y ∈ Y} ( ∏_{i=1}^p Pr[xi | y, X] ) · Pr[y | X]

où Pr[y | X] est la probabilité a priori de la classe y (par exemple proportion de textes dans la classe y dans l’ensemble d’apprentissage).

Pour chaque classe (spam ou non-spam), on calcule le produit des probabilités conditionnelles des mots présents ou absents dans le vecteur x, puis on multiplie par la probabilité a priori de la classe.

La classe qui maximise cette valeur est celle prédite pour le nouvel email.

Sans les valeurs numériques des probabilités conditionnelles et des vecteurs, on ne peut pas effectuer le calcul ici.

Méthode : techniques récompensées et erreurs pénalisées

Ce TD récompense :

• La compréhension claire de la transformation des textes en vecteurs binaires selon un vocabulaire donné.
• L’application rigoureuse des formules de probabilité conditionnelle pour estimer Pr[xi | y, X].
• L’utilisation correcte de la formule Naïve Bayes pour classifier un nouvel exemplaire, en tenant compte des mots présents et absents.
• La présentation détaillée des étapes de calcul, avec des justifications précises.

Les erreurs pénalisées sont :

• Ne pas normaliser correctement les textes avant la vectorisation.
• Oublier de considérer les mots absents dans le calcul des probabilités conditionnelles (Pr[xi=0 | y, X]).
• Confondre les indices des mots dans le vocabulaire ou les classes.
• Ne pas appliquer la formule du produit des probabilités conditionnelles pour toutes les dimensions du vecteur.
• Ne pas utiliser les probabilités a priori Pr[y | X] dans le calcul final.

Enfin, il est important de respecter les conventions données dans l’énoncé, notamment la définition des probabilités conditionnelles et la représentation binaire des textes.