Notes de Cours : Data Mining

Séance 04, 30 Septembre 2013

Prof. Chiraz Ben Abdelkader, ENSI

Plan: Classification Supervisée et Méthodes Simples (Partie II)

0) Révision : la classification supervisée, l’approche Bayésienne, méthode OneR

1) Méthode OneR avec attributs numériques

2) Méthode de Naïve Bayes

3) Application : classification de textes

4) TD/TP : application sur la base de données « jouer tennis »

5) TD/TP : classification de textes avec méthode de Naïve Bayes

Références :

(Disponibles sur mon Google Drive, sous le dossier « Références & Ressources »)

1) Notes de cours en Français : Prof. Philippe Preux, Chapitre 2 & Chapitre 4

2) Livre en Anglais : “Data Mining, Practical ML tools and techniques”, Chapitre 4 p. 85-98

1) Méthode OneR avec des attributs numériques

On a discuté la méthode OneR tout en supposant des attributs de type nominal. En cas

ou le problème contient des attributs numériques, on doit tout d’abord les convertir a

un type nominal qui consiste à un ensemble d’intervalles disjoints. Par exemple,

supposons que dans la base de données « Jouer Tennis », l’attribut Température est un

attribut numérique. On peut le convertir à un type nominal de la façon suivante :

Valeur numérique (C)

T > 32

10 <= T <= 32

T < 10

Valeur nominale

Chaude

Tiède

Fraiche

2) Méthode de Naïve Bayes

a. Introduction

Cette méthode est identique à l’approche Bayésienne générale qu’on a introduit au-

dessus, sauf qu’elle suppose que les attributs sont tous indépendants (c’est-à-dire

statistiquement non-corrélés), ce qui fait que les probabilités conditionnelles

deviennent beaucoup plus faciles à estimer.

b. Règle de Bayes

 Une des Théorèmes basiques et fondamentales de Probabilité qui dit que, si

l’on a trois évènements aléatoires quelconques A, B, et C, alors :

Pr [A|B,C] = Pr[B|A,C] . Pr[A|C] / Pr[B|C]

 Revenons maintenant à notre problème de classification supervisée, et

considérons un exemplaire quelconque prit au hasard. Ainsi on peut définir les

évènements aléatoires suivants :

A : la classe de cet exemplaire est y

B : les valeurs des attributs de cet exemplaire sont x

C : on a un échantillon d’apprentissage dans l’ensemble X

 Donc on peut écrire maintenant :

Pr[y | x,X] = Pr[x | y,X] . Pr[y | X] / Pr[x | X]

 Pr[x | y,X] . Pr[y |X]

 ( i=1..p Pr[xi|y,X] ) . Pr[y|X]

selon la règle de Bayes

puisque y ne dépend pas de Pr[x | X]

puisque les attributs sont indépendants



Pour résumer, étant donné des données x, on prédit sa classe y par :

y = argmaxyY [ Pr[y | x,X] ]

= argmaxyY ( i=1..p Pr[xi | y,X] ) . Pr[y | X]

(1)

 On appelle cette méthode de classification supervisée un classeur Naïve

Bayes.



Pour construire un classeur Naïve Bayes, on a que d’estimer toutes les

probabilités conditionnelles Pr[y |X] et Pr[xi|y,X] : pour tous les attributs xi , et

pour toutes les classes yY.

c. Estimation des Probabilités Pr[y | X]

Cette probabilité représente la proportion des exemplaires de X qui

appartiennent à la classe y. Donc on l’estime par la proportion n(y) / n, ou

n(y) = nombre d’exemplaires dans X appartenant à la classe y

n = nombre total des exemplaires.

d. Estimation des Probabilités Pr[xi|y,X]

 Attributs nominaux : On estime Pr[xi|y,X]  n(xi,y) / n(y) , ou :

n(xi,y) = nombre d’exemplaires dans X appartenant à la classe y et pour

lesquels le ieme attribut prend la valeur xi

n(y) = nombre d’exemplaires dans X appartenant à la classe y

 Attributs numériques : On estime Pr[xi|y,X] en supposant que la distribution de

2) , ou i et i sont respectivement la

xi étant donné y est normale : xi  (i,i

moyenne et l’écart-type de xi, qui peuvent être estimés à partir des exemplaires

de X qui appartiennent à la classe y. On a donc :















2







e. Que faire si l’un des probabilités Pr[xi|y,X] = 0 ?

Parfois on obtient n(xi,y) = 0 pour un ou plusieurs attributs xi. Dans ce cas, la

valeur calculée de Pr[xi|y,X], et ensuite celle de Pr[y|x,X] seront aussi égales à

zéro ! Donc c’est comme si un seul zéro a « le pouvoir de veto » pendant

l’évaluation de Pr[y|x,X] ; les valeurs des probabilités conditionnelles des autres

attributs sont ignorées. Pour éviter cette situation, tout simplement on

incrémente par 1 les valeurs de n(xi,y) pour tout xi et tout y, ensuite on recalcule

les probabilités.

3) Application : Classification de Textes

a. Présentation du problème

Il s’agit d’un problème de classification supervisée, ou les exemplaires consistent

en des textes qu’on souhaite classifier à deux ou plusieurs classes (catégories).

Exemples :

o Détection de spam : Les textes sont des emails et les classes sont { spam,

non-spam}

o Classification de pages Web par apport a un sujet X: les textes sont des

pages Web, et les classes sont { traite_sujet_X, ne_traite_pas_sujet_X }

o Classification de page Web: les textes sont des pages Web et les classes sont

{ actualités, sport, les arts, technologie, … }

b. Représentation d’un texte en « Sacs de Mots »

Les textes doivent être mis sous une forme convenable à être traités par les

méthodes de classification supervisée. Donc il faut extraire d’un texte un

ensemble fixe d’attributs qui caractérisent bien le texte.

Une des représentations de textes les plus fréquemment utilisée est celle de

sacs de mots. Dans cette représentation, un texte est caractérisé par

l’occurrence ou non d’un ensemble fixe de mots, qu’on appelle un vocabulaire.



Soit V = { m1, m2, … , mp } un ensemble finit de p mots ; c’est le

vocabulaire du problème.

Etant donne un texte t, on définit le ieme attribut de t par:











sinon

c. Classeur Naïve Bayes

Une fois on a définit la représentation du texte, on utilise la méthode Naïve

Bayes comme on l’a déjà défini au-dessus. Donc, étant donne un texte t, on

extrait l’ensemble de ses attributs x, puis on prédit sa classe y comme suit :

y = argmaxyY ( i=1..p Pr[xi | y,X] ) . Pr[y | X]

Rappelons que, dans ce cas, xi a seulement deux valeurs possibles, 1 et 0, qui

représentent l’occurrence et non-occurrence du ieme mot du vocabulaire dans t.

Donc, pour la construction d’un classeur Naïve Bayes pour ce problème, on

estime chacun des probabilités conditionnelles Pr[xi| y,X] comme suit :

Pr[xi = 1 | y,X] = probabilité d’observer le ieme mot dans un texte de classe y

 n(mi,y) / n(y)

ou n(mi,y) : nombre d’occurrences du ieme mot dans des textes de classe y

n(y) : nombre de textes du classe y

Pr[xi = 0 | y,X] = 1 - Pr[xi = 1 | y,X]

Puis, étant donne un nouvel texte quelconque, on prédit sa classe en

appliquant la formule du classeur Naïve Bayes (Equation (1) au-dessus).

Data Mining Course Notes

Data Mining Course Notes