Classification naïve bayésienne

Type	Algorithme, classification bayésienne (en)
Nommé en référence à	Thomas Bayes
Aspect de	Apprentissage automatique, science des données

La classification naïve bayésienne est un type de classification bayésienne probabiliste simple basée sur le théorème de Bayes avec une forte indépendance (dite naïve) des hypothèses. Elle met en œuvre un classifieur bayésien naïf, ou classifieur naïf de Bayes, appartenant à la famille des classifieurs linéaires.

Un terme plus approprié pour le modèle probabiliste sous-jacent pourrait être « modèle à caractéristiques statistiquement indépendantes ».

En termes simples, un classifieur bayésien naïf suppose que l'existence d'une caractéristique pour une classe, est indépendante de l'existence d'autres caractéristiques. Un fruit peut être considéré comme une pomme s'il est rouge, arrondi, et fait une dizaine de centimètres. Même si ces caractéristiques sont liées dans la réalité, un classifieur bayésien naïf déterminera que le fruit est une pomme en considérant indépendamment ces caractéristiques de couleur, de forme et de taille.

Selon la nature de chaque modèle probabiliste, les classifieurs bayésiens naïfs peuvent être entraînés efficacement dans un contexte d'apprentissage supervisé. Dans beaucoup d'applications pratiques, l'estimation des paramètres pour les modèles bayésiens naïfs repose sur le maximum de vraisemblance. Autrement dit, il est possible de travailler avec le modèle bayésien naïf sans se préoccuper de probabilité bayésienne ou utiliser les méthodes bayésiennes.

Malgré leur modèle de conception « naïf » et ses hypothèses de base extrêmement simplistes, les classifieurs bayésiens naïfs ont fait preuve d'une efficacité plus que suffisante dans beaucoup de situations réelles complexes. En 2004, un article a montré qu'il existe des raisons théoriques derrière cette efficacité inattendue^[1]. Toutefois, une autre étude de 2006 montre que des approches plus récentes (arbres renforcés, forêts aléatoires) permettent d'obtenir de meilleurs résultats^[2].

L'avantage du classifieur bayésien naïf est qu'il requiert relativement peu de données d'entraînement pour estimer les paramètres nécessaires à la classification, à savoir moyennes et variances des différentes variables. En effet, l'hypothèse d'indépendance des variables permet de se contenter de la variance de chacune d'entre elles pour chaque classe, sans avoir à calculer de matrice de covariance.

Modèle bayésien naïf

Le modèle probabiliste pour un classifieur est le modèle conditionnel

p(C\vert F_{1},\dots ,F_{n})\,

où $C$ est une variable de classe dépendante dont les instances ou classes sont peu nombreuses, conditionnée par plusieurs variables caractéristiques $F 1,..., F n$ .

Lorsque le nombre de caractéristiques $n$ est grand, ou lorsque ces caractéristiques peuvent prendre un grand nombre de valeurs, baser ce modèle sur des tableaux de probabilités devient impossible. Par conséquent, nous le dérivons pour qu'il soit plus facilement soluble.

À l'aide du théorème de Bayes, nous écrivons

p(C\vert F_{1},\dots ,F_{n})={\frac {p(C)\ p(F_{1},\dots ,F_{n}\vert C)}{p(F_{1},\dots ,F_{n})}}.\,

En langage courant, cela signifie :

{\mbox{postérieure}}={\frac {{\mbox{antérieure}}\times {\mbox{vraisemblance}}}{\mbox{évidence}}}.\,

(voir les réseaux bayésiens)

En pratique, seul le numérateur nous intéresse, puisque le dénominateur ne dépend pas de $C$ et les valeurs des caractéristiques $F i$ sont données. Le dénominateur est donc en réalité constant. Le numérateur est soumis à la loi de probabilité à plusieurs variables et peut être factorisé de la façon suivante, en utilisant plusieurs fois la définition de la probabilité conditionnelle :

\ \ p(C)\ p(F_{1},\dots ,F_{n}\vert C)

=p(C)\ p(F_{1}\vert C)\ p(F_{2},\dots ,F_{n}\vert C,F_{1})

=p(C)\ p(F_{1}\vert C)\ p(F_{2}\vert C,F_{1})\ p(F_{3},\dots ,F_{n}\vert C,F_{1},F_{2})

=p(C)\ p(F_{1}\vert C)\ p(F_{2}\vert C,F_{1})\ p(F_{3}\vert C,F_{1},F_{2})\ p(F_{4},\dots ,F_{n}\vert C,F_{1},F_{2},F_{3})

=p(C)\ p(F_{1}\vert C)\ p(F_{2}\vert C,F_{1})\ p(F_{3}\vert C,F_{1},F_{2})\ \cdots \ p(F_{n}\vert C,F_{1},F_{2},F_{3},\dots ,F_{n-1}).

C'est là que nous faisons intervenir l'hypothèse naïve : si chaque $F i$ est indépendant des autres caractéristiques $F j \neq i$ , conditionnellement à $C$ alors

p(F_{i}\vert C,F_{j})=p(F_{i}\vert C)\,

pour tout $j \neq i$ , par conséquent la probabilité conditionnelle peut s'écrire

p(F_{1},\dots ,F_{n}\vert C)=p(F_{1}\vert C)\ p(F_{2}\vert C)\ p(F_{3}\vert C)\ \cdots \ p(F_{n}\vert C)=\prod _{i=1}^{n}p(F_{i}\vert C).

Par conséquent, en tenant compte de l'hypothèse d'indépendance ci-dessus, la probabilité conditionnelle de la variable de classe $C$ peut être exprimée par

p(C\vert F_{1},\dots ,F_{n})={\frac {1}{Z}}p(C)\prod _{i=1}^{n}p(F_{i}\vert C)

où $Z$ (appelé « évidence ») est un facteur d'échelle qui dépend uniquement de $F 1,..., F n$ , à savoir une constante dans la mesure où les valeurs des variables caractéristiques sont connues.

Les modèles probabilistes ainsi décrits sont plus faciles à manipuler, puisqu'ils peuvent être factorisés par l'antérieure $p (C)$ (probabilité a priori de $C$ ) et les lois de probabilité indépendantes $p (F i | C)$ . S'il existe $k$ classes pour $C$ et si le modèle pour chaque fonction $p (F i | C = c)$ peut être exprimé selon $r$ paramètres, alors le modèle bayésien naïf correspondant dépend de $(k - 1) + nrk$ paramètres. En effet, pour $C = c$ et un $i$ donné, $p (F i | C)$ nécessite $r$ paramètres, donc $nr$ paramètres pour tous les $F{ind$ , et $nrk$ paramètres pour toutes les classes $C = c$ . Reste à déterminer les paramètres $p(C=c)$ . On peut en fixer (k − 1), sachant que $\sum _{c}p(C=c)=1$ .

Dans la pratique, on observe souvent des modèles où $k = 2$ (classification binaire) et $r = 1$ (les caractéristiques sont alors des variables de Bernoulli). Dans ce cas, le nombre total de paramètres du modèle bayésien naïf ainsi décrit est de $2 n +1$ , avec $n$ le nombre de caractéristiques binaires utilisées pour la classification.

Estimation de la valeur des paramètres

Tous les paramètres du modèle (probabilités a priori des classes et lois de probabilités associées aux différentes caractéristiques) peuvent faire l'objet d'une approximation par rapport aux fréquences relatives des classes et caractéristiques dans l'ensemble des données d'entraînement. Il s'agit d'une estimation du maximum de vraisemblance des probabilités. Les probabilités a priori des classes peuvent par exemple être calculées en se basant sur l'hypothèse que les classes sont équiprobables (i.e chaque antérieure = 1 / (nombre de classes)), ou bien en estimant chaque probabilité de classe sur la base de l'ensemble des données d'entraînement (i.e antérieure de $C$ = (nombre d'échantillons de $C$ ) / (nombre d'échantillons total)). Pour estimer les paramètres d'une loi de probabilité relative à une caractéristique précise, il est nécessaire de présupposer le type de la loi en question ; sinon, il faut générer des modèles non-paramétriques pour les caractéristiques appartenant à l'ensemble de données d'entraînement^[3]. Lorsque l'on travaille avec des caractéristiques qui sont des variables aléatoires continues, on suppose généralement que les lois de probabilités correspondantes sont des lois normales, dont on estimera l'espérance et la variance.

L'espérance $μ$ se calcule avec

\mu ={\frac {1}{N}}\sum _{i=1}^{N}x_{i}

,

où $N$ est le nombre d'échantillons et $x i$ est la valeur d'un échantillon donné.

La variance $σ 2$ se calcule avec

\sigma ^{2}={\frac {1}{(N-1)}}\sum _{i=1}^{N}\left(x_{i}-\mu \right)^{2}\,

.

Si, pour une certaine classe, une certaine caractéristique ne prend jamais une valeur donnée dans l'ensemble de données d'entraînement, alors l'estimation de probabilité basée sur la fréquence aura pour valeur zéro. Cela pose un problème puisque l'on aboutit à l'apparition d'un facteur nul lorsque les probabilités sont multipliées. Par conséquent, on corrige les estimations de probabilités avec des probabilités fixées à l'avance.

Construire un classifieur à partir du modèle de probabilités

Jusqu'à présent nous avons établi le modèle à caractéristiques indépendantes, à savoir le modèle de probabilités bayésien naïf. Le classifieur bayésien naïf couple ce modèle avec une règle de décision. Une règle couramment employée consiste à choisir l'hypothèse la plus probable. Il s'agit de la règle du maximum a posteriori ou MAP. Le classifieur correspondant à cette règle est la fonction $classifieur$ suivante :

\mathrm {classifieur} (f_{1},\dots ,f_{n})={\underset {c}{\operatorname {argmax} }}\ p(C=c)\displaystyle \prod _{i=1}^{n}p(F_{i}=f_{i}\vert C=c).

Analyse

Malgré les hypothèses d'indépendance relativement simplistes, le classifieur bayésien naïf a plusieurs propriétés qui le rendent très pratique dans les cas réels. En particulier, la dissociation des lois de probabilités conditionnelles de classe entre les différentes caractéristiques aboutit au fait que chaque loi de probabilité peut être estimée indépendamment en tant que loi de probabilité à une dimension. Cela permet d'éviter nombre de problèmes venant du fléau de la dimension, par exemple le besoin de disposer d'ensembles de données d'entraînement dont la quantité augmente exponentiellement avec le nombre de caractéristiques. Comme tous les classifieurs probabilistes utilisant la règle de décision du maximum a posteriori, il classifie correctement du moment que la classe adéquate est plus probable que toutes les autres. Par conséquent les probabilités de classe n'ont pas à être estimées de façon très précises. Le classifieur dans l'ensemble est suffisamment robuste pour ne pas tenir compte de sérieux défauts dans son modèle de base de probabilités naïves.

Exemples

Classification des sexes

On cherche à classifier chaque personne en tant qu'individu du sexe masculin ou féminin, selon les caractéristiques mesurées. Les caractéristiques comprennent la taille, le poids, et la pointure.

Entraînement

On dispose de l'ensemble de données d'entraînement suivant :

Sexe	Taille (cm)	Poids (kg)	Pointure (cm)
masculin	182	81.6	30
masculin	180	86.2	28
masculin	170	77.1	30
masculin	180	74.8	25
féminin	152	45.4	15
féminin	168	68.0	20
féminin	165	59.0	18
féminin	175	68.0	23

Le classifieur créé à partir de ces données d'entraînement, utilisant une hypothèse de distribution Gaussienne pour les lois de probabilités des caractéristiques, est le suivant :

Sexe	Espérance (taille)	Variance (taille)	Espérance (poids)	Variance (poids)	Espérance (pointure)	Variance (pointure)
masculin	178	2.9333×10¹	79.92	2.5476×10¹	28.25	5.5833×10⁰
féminin	165	9.2666×10¹	60.1	1.1404×10²	19.00	1.1333×10¹

On suppose pour des raisons pratiques que les classes sont équiprobables, à savoir $P (masculin) = P (féminin) = 0,5$ (selon le contexte, cette hypothèse peut être inappropriée). Si l'on détermine $P (C)$ d'après la fréquence des échantillons par classe dans l'ensemble de données d'entraînement, on aboutit au même résultat.

Test

On veut classifier l'échantillon suivant en tant que masculin ou féminin :

Sexe	Taille (cm)	Poids (kg)	Pointure (cm)
inconnu	183	59	20

On veut déterminer quelle probabilité postérieure est la plus grande, celle que l'échantillon soit de sexe masculin, ou celle qu'il soit de sexe féminin.

P_{p}({\mbox{masculin}})=P({\mbox{masculin}})P({\mbox{taille}}|{\mbox{masculin}})P({\mbox{poids}}|{\mbox{masculin}})P({\mbox{pointure}}|{\mbox{masculin}})/{\mbox{évidence}}

P_{p}({\mbox{féminin}})=P({\mbox{féminin}})P({\mbox{taille}}|{\mbox{féminin}})P({\mbox{poids}}|{\mbox{féminin}})P({\mbox{pointure}}|{\mbox{féminin}})/{\mbox{évidence}}

Le terme évidence (également appelé constante de normalisation) peut être calculé car la somme des postérieures vaut 1.

{\mbox{évidence}}=P({\mbox{masculin}})P({\mbox{taille}}|{\mbox{masculin}})P({\mbox{poids}}|{\mbox{masculin}})P({\mbox{pointure}}|{\mbox{masculin}})+P({\mbox{féminin}})P({\mbox{taille}}|{\mbox{féminin}})P({\mbox{poids}}|{\mbox{féminin}})P({\mbox{pointure}}|{\mbox{féminin}})

Toutefois, on peut ignorer ce terme puisqu'il s'agit d'une constante positive (une probabilité est toujours positive).

On peut à présent déterminer le sexe de l'échantillon avec :

f_{k,j}(x)={1 \over {\sqrt {2\pi \sigma _{k,j}^{2}}}}\exp \left({-1 \over 2\sigma _{k,j}^{2}}(x-\mu _{k,j})^{2}\right)

pour une variable $j$ dans le groupe $k$ .

Pour la variable taille (t) dans le groupe masculin (m) on a donc :

P(\mathrm {taille} |\mathrm {masculin} )=f_{t,m}(x)={1 \over {\sqrt {2\pi \times 2,9333\times 10^{1}}}}\exp \left({-1 \over 2\times 2.9333\times 10^{1}}(183-178)^{2}\right)\approx 4.8102\times 10^{-2}

On réalise ce calcul pour chacune des variables et des groupes :

P(masculin) = 0.5

P(taille|masculin) = 4.8102^e-02

P(poids|masculin) = 1.4646^e-05

P(pointure|masculin) = 3.8052^e-4

P_p (masculin) = 1.3404^e-10

P(féminin) = 0.5

P(taille|féminin) = 7.2146^e-3

P(poids|féminin) = 3.7160^e-2

P(pointure|féminin) = 1.1338^e-1

P_p(féminin) = 1.5200^e-05

Comme la postérieure féminin est supérieure à la postérieure masculin, l'échantillon est plus probablement de sexe féminin.

Classification et catégorisation de documents

Voici un exemple de classification bayésienne naïve appliquée au problème de la classification et catégorisation de documents. On souhaite ici classifier des documents par leur contenu, par exemple des E-mails en spam et non-spam. On imagine que les documents proviennent d'un certain nombre de classes de documents, lesquelles peuvent être définies comme des ensembles de mots dans lesquels la probabilité (indépendante) que le $i$ ^e mot d'un document donné soit présent dans un document de la classe $C$ peut s'écrire :

p(w_{i}\vert C)\,

(Pour cette opération, nous simplifions l'hypothèse en supposant que les mots sont distribués au hasard dans le document, donc qu'ils ne dépendent ni de la longueur du document, ni de leur position respective à l'intérieur du document relativement à d'autres mots, ou autre contexte du document.)

On écrit donc la probabilité d'un document D, étant donné une classe C,

p(D\vert C)=\prod _{i}p(w_{i}\vert C)\,

Quelle est la probabilité qu'un document D appartienne à une classe donnée C ? En d'autres termes, quelle est la valeur de $p (C | D)$ ?

Par définition,

p(D\vert C)={p(D\cap C) \over p(C)}

et

p(C\vert D)={p(D\cap C) \over p(D)}

Le théorème de Bayes nous permet d'inférer la probabilité en termes de vraisemblance.

p(C\vert D)={p(C) \over p(D)}\,p(D\vert C)

Si on suppose qu'il n'existe que deux classes mutuellement exclusives, S et ¬S (e.g. spam et non-spam), telles que chaque élément (email) appartienne soit à l'une, soit à l'autre,

p(D\vert S)=\prod _{i}p(w_{i}\vert S)\,

et

p(D\vert \neg S)=\prod _{i}p(w_{i}\vert \neg S)\,

En utilisant le résultat bayésien ci-dessus, on peut écrire :

p(S\vert D)={p(S) \over p(D)}\,\prod _{i}p(w_{i}\vert S)

p(\neg S\vert D)={p(\neg S) \over p(D)}\,\prod _{i}p(w_{i}\vert \neg S)

En divisant les deux équations, on obtient :

{p(S\vert D) \over p(\neg S\vert D)}={p(S)\,\prod _{i}p(w_{i}\vert S) \over p(\neg S)\,\prod _{i}p(w_{i}\vert \neg S)}

qui peut être factorisée de nouveau en :

{p(S\vert D) \over p(\neg S\vert D)}={p(S) \over p(\neg S)}\,\prod _{i}{p(w_{i}\vert S) \over p(w_{i}\vert \neg S)}

Par conséquent, le rapport de probabilités p(S | D) / p(¬S | D) peut être exprimé comme une série de rapports de vraisemblance. La probabilité p(S | D) elle-même peut être inférée facilement avec log (p(S | D) / p(¬S | D)) puisqu'on observe que p(S | D) + p(¬S | D) = 1.

En utilisant les logarithmes de chacun de ces rapports, on obtient :

\ln {p(S\vert D) \over p(\neg S\vert D)}=\ln {p(S) \over p(\neg S)}+\sum _{i}\ln {p(w_{i}\vert S) \over p(w_{i}\vert \neg S)}

(Cette technique de rapport de vraisemblance est une technique courante en statistiques. Dans le cas de deux solutions mutuellement exclusives (comme l'exemple ci-dessus), la conversion d'un rapport de vraisemblance en une probabilité prend la forme d'une sigmoïde. Voir logit pour plus de détails.)

Le document peut donc être classifié comme suit : il s'agit de spam si $p(S\vert D)>p(\neg S\vert D)$ (i.e. si $\ln {p(S\vert D) \over p(\neg S\vert D)}>0$ ), sinon il s'agit de courrier normal.

Notes et références

↑ Harry Zhang "The Optimality of Naive Bayes". Conférence FLAIRS2004. (disponible en ligne en Anglais: PDF)
↑ Caruana, R. and Niculescu-Mizil, A.: "An empirical comparison of supervised learning algorithms". Proceedings of the 23rd international conference on Machine learning, 2006. (disponible en ligne en Anglais PDF)
↑ George H. John and Pat Langley (1995). Estimating Continuous Distributions in Bayesian Classifiers. Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence. p. 338-345. Morgan Kaufmann, San Mateo.

Voir aussi

Bibliographie

Domingos, Pedro & Michael Pazzani (1997) "On the optimality of the simple Bayesian classifier under zero-one loss". Machine Learning, 29:103–137. (also online at CiteSeer: [1])
Rish, Irina. (2001). "An empirical study of the naive Bayes classifier". IJCAI 2001 Workshop on Empirical Methods in Artificial Intelligence. (available online: PDF, PostScript)
Hand, DJ, & Yu, K. (2001). "Idiot's Bayes - not so stupid after all?" International Statistical Review. Vol 69 part 3, pages 385-399. ISSN 0306-7734.
Webb, G. I., J. Boughton, and Z. Wang (2005). Not So Naive Bayes: Aggregating One-Dependence Estimators. Machine Learning 58(1). Netherlands: Springer, pages 5-24.
Mozina M, Demsar J, Kattan M, & Zupan B. (2004). "Nomograms for Visualization of Naive Bayesian Classifier". In Proc. of PKDD-2004, pages 337-348. (available online: PDF)
Maron, M. E. (1961). "Automatic Indexing: An Experimental Inquiry." Journal of the ACM (JACM) 8(3):404–417. (available online: PDF)
Minsky, M. (1961). "Steps toward Artificial Intelligence." Proceedings of the IRE 49(1):8-30.
McCallum, A. and Nigam K. "A Comparison of Event Models for Naive Bayes Text Classification". In AAAI/ICML-98 Workshop on Learning for Text Categorization, p. 41–48. Technical Report WS-98-05. AAAI Press. 1998. (available online: PDF)
Rennie J, Shih L, Teevan J, and Karger D. Tackling The Poor Assumptions of Naive Bayes Classifiers. In Proceedings of the Twentieth International Conference on Machine Learning (ICML). 2003. (available online: PDF)

Articles connexes

Classifieur AODE
Filtrage bayésien du spam (liée aux techniques bayésiennes de filtrage du spam)
Réseau bayésien
Classification bayésienne naïve aléatoire
Classifieur linéaire
Inférence bayésienne
Boosting
Logique floue
Régression logistique
Probabilités d'appartenance à une classe
Réseau de neurones artificiel
Analyse prédictive
Perceptron
Machine à vecteurs de support

Liens externes

Tests de performance de classifieurs bayésiens

Logiciels :

IMSL Collection d'algorithmes mathématiques et statistiques en C/C++, Fortran, Java and C#/.NET. Les routines de data mining dans les IMSL comportent un classifieur bayésien naïf.
Winnow content recommendation Classifieur bayésien naïf open source fonctionnant avec de petits ensembles de données d'entraînement. Haute performance, C, Unix.

Portail des probabilités et de la statistique

[1] Harry Zhang "The Optimality of Naive Bayes". Conférence FLAIRS2004. (disponible en ligne en Anglais: PDF)

[2] Caruana, R. and Niculescu-Mizil, A.: "An empirical comparison of supervised learning algorithms". Proceedings of the 23rd international conference on Machine learning, 2006. (disponible en ligne en Anglais PDF)

[3] George H. John and Pat Langley (1995). Estimating Continuous Distributions in Bayesian Classifiers. Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence. p. 338-345. Morgan Kaufmann, San Mateo.

[1]

[2]

[3]