Cours classifieur naif de bayes data mining

Ce document, préparé par le Pr. Ali BERRICHI du Département d'informatique de l'UMBBoumerdes, est destiné aux étudiants universitaires en informatique.

Il offre une exploration approfondie du Classifieur Naïf de Bayes, un algorithme essentiel en apprentissage automatique. Le chapitre couvre les notions suivantes :

Le cadre probabiliste et le théorème de Bayes pour la classification ;
L'hypothèse d'indépendance des attributs et l'estimation des probabilités ;
Les applications concrètes et l'étude des performances de ce classifieur ;
Les méthodes pour gérer les données continues et les défis liés aux probabilités nulles.

Cours Classifieur Naif de Bayes Data mining

Télécharger PDF

Le Classifieur Naïf de Bayes : Principes et Applications

Le classifieur Naïf de Bayes est un algorithme de classification simple mais puissant, basé sur le théorème de Bayes et une hypothèse d'indépendance forte entre les attributs. Il est largement utilisé dans le domaine de l'apprentissage automatique pour sa rapidité et son efficacité, notamment pour des tâches comme la classification de texte.

Classifieur de Bayes : Cadre Probabiliste pour la Classification

Le théorème de Bayes fournit un cadre probabiliste robuste pour aborder les problèmes de classification. Il repose sur la notion de probabilité conditionnelle.

Rappel : Probabilité Conditionnelle

La probabilité conditionnelle de l'événement A sachant l'événement B est donnée par :

P(A|B) = P(A ∩ B) / P(B), où P(B) > 0.

À partir de cette définition, on peut déduire le Théorème de Bayes :

P(A|B) = [P(B|A) * P(A)] / P(B)

Dans ce contexte :

P(Y) : Probabilité a priori d'une classe Y. C'est la probabilité que la classe Y se produise avant de connaître toute information sur les attributs.
P(Y|X) : Probabilité a posteriori d'une classe Y, étant donné un ensemble d'attributs X. C'est la probabilité de la classe Y après avoir observé les attributs.

Le Théorème de Bayes pour la Classification

Pour la classification, nous considérons un ensemble d'attributs (ou caractéristiques) X = (X1, X2, ..., Xd) et une variable aléatoire Y représentant la classe.

L'objectif est d'estimer P(Y|X1, X2, ..., Xd), c'est-à-dire la probabilité qu'une instance appartienne à la classe Y, étant donné ses attributs X1 à Xd. Bien que cette probabilité puisse être estimée directement à partir des données dans des cas simples, cela devient complexe et gourmand en données pour un grand nombre d'attributs (haute dimensionnalité).

Applications des Classifieurs Bayesiens

Les classifieurs Bayesiens sont largement utilisés dans divers domaines :

Classification de texte, comme le filtrage des spams ou l'analyse des sentiments.
Détection d'intrusions ou d'anomalies dans les réseaux informatiques.
Diagnostic médical, en considérant un ensemble de symptômes observés.

Un simple Classifieur Naïf de Bayes (Naïve Bayesian Classifier) peut offrir des performances comparables à celles d'arbres de décision et de réseaux de neurones sélectionnés, surtout sur des ensembles de données de grande taille.

Approche du Classifieur de Bayes

L'approche du Classifieur de Bayes pour la classification suit ces étapes :

Calculer les probabilités a posteriori P(Y | X1, X2, ..., Xd) en utilisant le théorème de Bayes pour chaque classe possible Y.
Appliquer le principe du Maximum a posteriori (MAP) : choisir la classe Y qui maximise P(Y | X1, X2, ..., Xd).
Cette approche est équivalente à choisir la valeur de Y qui maximise P(X1, X2, ..., Xd | Y) * P(Y).

La question clé devient alors : comment estimer P(X1, X2, ..., Xd | Y) ? C'est là que le concept de "naïveté" intervient.

Le Classifieur Naïf de Bayes

Le Classifieur Naïf de Bayes simplifie l'estimation de P(X1, X2, ..., Xd | Y) en posant une hypothèse forte : l'indépendance des attributs Xi étant donné la classe Y. Autrement dit, la valeur d'un attribut n'affecte pas la valeur d'un autre attribut, une fois que la classe est connue.

L'Hypothèse de Naïveté

Selon cette hypothèse :

P(X1, X2, ..., Xd | Yj) = P(X1 | Yj) * P(X2 | Yj) * ... * P(Xd | Yj)

Les probabilités conditionnelles individuelles P(Xi | Yj) peuvent être estimées plus facilement à partir des données d'apprentissage pour toutes les combinaisons d'attributs Xi et de classes Yj.

Ainsi, une nouvelle instance est classifiée dans la classe Yj si le produit P(Yj) * ∏ P(Xi | Yj) est maximal.

Exemple d'Application du Classifieur Naïf de Bayes

Considérons l'ensemble de données suivant pour prédire si un client a remboursé un prêt (Oui/Non) en fonction de sa situation (Possède Maison, État Civil, Revenus) :

ID	Possède Maison	État Civil	Revenus	Remboursé
1	Oui	Célibat.	125	Non
2	Non	Marié	100	Non
3	Non	Célibat.	70	Non
4	Oui	Marié	120	Non
5	Non	Divorcé	95	Oui
6	Non	Marié	60	Non
7	Oui	Divorcé	220	Non
8	Non	Célibat.	85	Oui
9	Non	Marié	75	Non
10	Non	Célibat.	90	Oui

Étant donné une nouvelle instance de test X = (Maison = Non, État civil = Divorcé, Revenus = 120), nous voulons déterminer la classe Y = Remboursé (Oui ou Non).

En utilisant le Classifieur Naïf de Bayes, nous devons estimer les probabilités conditionnelles pour chaque classe. Pour la classe "Oui" et "Non" :

P(X | Remboursé = Oui) = P(Maison = Non | Oui) * P(État civil = Divorcé | Oui) * P(Revenus = 120 | Oui)
P(X | Remboursé = Non) = P(Maison = Non | Non) * P(État civil = Divorcé | Non) * P(Revenus = 120 | Non)

Nous estimons ensuite la probabilité a posteriori P(Remboursé = Oui | X) et P(Remboursé = Non | X) pour déterminer la classe prédite.

Estimation des Probabilités pour Données Continues

Lorsque les attributs sont des données continues (comme les revenus dans l'exemple), il existe deux approches principales pour estimer P(Xi | Yj) :

Discrétisation des Attributs

Cette méthode consiste à découper les valeurs continues en classes ou intervalles. Par exemple, les revenus pourraient être divisés en "faible", "moyen", "élevé". Ensuite :

Les valeurs continues sont remplacées par les classes auxquelles elles appartiennent.
L'attribut change de type continu à type ordinal ou nominal, et l'estimation des probabilités devient similaire à celle des attributs catégoriques.

Estimation de la Densité de Probabilité

Cette approche suppose que l'attribut continu suit une loi de probabilité connue, souvent la loi normale (ou gaussienne). Dans ce cas :

On utilise les données d'apprentissage pour estimer les paramètres de cette loi pour chaque attribut et chaque classe (par exemple, la moyenne et l'écart-type pour une loi normale).
Une fois les paramètres de la loi connus, on peut l'utiliser pour estimer la probabilité conditionnelle P(Xi | Yj).

Estimation des Probabilités à partir des Données avec la Loi Normale

Pour un attribut continu Xi et une classe Yj, si on suppose une distribution normale, la probabilité P(Xi | Yj) peut être calculée avec la fonction de densité de probabilité (PDF) de la loi normale :

P(Xi | Yj) = (1 / (σ_ij * √(2π))) * e^{-(Xi - μ_ij)² / (2 * σ_ij²)}

Où :

μ_ij est la moyenne de l'attribut Xi pour la classe Yj.
σ_ij est l'écart-type de l'attribut Xi pour la classe Yj.

Prenons l'exemple du "Revenu" pour la "Classe=Non" (Remboursé = Non) :

Si Classe=Non (pour les ID 1, 2, 3, 4, 6, 7, 9) :
Les revenus sont : 125, 100, 70, 120, 60, 220, 75.
La moyenne (μ) de ces revenus est : (125 + 100 + 70 + 120 + 60 + 220 + 75) / 7 = 770 / 7 = 110.
La variance (σ²) de ces revenus est environ 2975.

Ces valeurs (moyenne et variance) seraient utilisées pour calculer P(Revenus = 120 | Remboursé = Non) en utilisant la formule de la loi normale.

Étapes Générales d'Estimation des Probabilités

Pour classifier une nouvelle instance avec le Classifieur Naïf de Bayes, les étapes sont les suivantes :

Calculer les probabilités a priori P(Yj) pour chaque classe Yj.
Pour chaque attribut Xi et chaque classe Yj, trouver les probabilités de vraisemblance P(Xi | Yj). Si Xi est continu, utiliser la discrétisation ou l'estimation de densité.
Calculer P(Yj | X) = [P(X | Yj) * P(Yj)] / P(X) où, grâce à l'hypothèse d'indépendance, P(X | Yj) = ∏ P(Xi | Yj). (Note : P(X) est souvent ignoré car c'est un facteur de normalisation constant pour toutes les classes, maximiser P(X | Yj) * P(Yj) est équivalent).
Choisir la classe Yj ayant la plus grande probabilité a posteriori.

Problèmes et Solutions du Classifieur Naïf de Bayes

Le Problème de la Fréquence Nulle (Zero-Frequency Problem)

Un des défis majeurs avec le Classifieur Naïf de Bayes survient si l'une des probabilités conditionnelles P(Xi | Yj) est nulle. Cela peut arriver si une valeur d'attribut Xi n'apparaît jamais avec une classe Yj donnée dans les données d'apprentissage. Dans ce cas, le produit ∏ P(Xi | Yj) devient nul, ce qui annule toute la probabilité a posteriori pour cette classe, indépendamment des autres attributs.

Solutions pour l'Estimation des Probabilités Conditionnelles

Pour éviter le problème de la fréquence nulle, des techniques de lissage sont appliquées :

Lissage de Laplace (ou Additif-1) :

P(Xi | Yj) = (N_ij + 1) / (N_j + c)

Où :
- N_ij : Nombre d'instances ayant la valeur Xi pour l'attribut i dans la classe Yj.
- N_j : Nombre total d'instances dans la classe Yj.
- c : Nombre de valeurs distinctes possibles pour l'attribut Xi.
Ce lissage ajoute une unité à chaque compte, évitant ainsi les probabilités nulles.
M-estimation :

P(Xi | Yj) = (N_ij + m * p) / (N_j + m)

Où :
- m : Paramètre utilisateur (souvent appelé "force de l'a priori").
- p : Probabilité a priori de la valeur Xi (souvent 1 / nombre de valeurs distinctes pour l'attribut).
La m-estimation est une généralisation du lissage de Laplace (quand m = c et p = 1/c).

Conclusion sur le Classifieur Naïf de Bayes

Le Classifieur Naïf de Bayes est apprécié pour ses qualités :

Haute précision et rapidité : Il est souvent très performant et rapide, même sur des ensembles de données volumineux.
Robustesse : Il est robuste face aux valeurs aberrantes (isolées) et gère les valeurs manquantes (ces dernières peuvent être gérées en ignorant l'instance durant le calcul des probabilités, ou en utilisant des techniques d'imputation).
Simplicité : Sa simplicité d'implémentation et de compréhension en fait un bon point de départ pour de nombreux problèmes de classification.

Cependant, sa principale limitation réside dans son hypothèse d'indépendance des attributs. Si cette hypothèse ne tient pas fortement pour certains attributs dans les données réelles, ses performances peuvent être impactées. Dans de tels cas, des techniques plus sophistiquées comme les réseaux bayésiens (Bayesian Belief Networks) peuvent être utilisées, car elles permettent de modéliser explicitement les dépendances entre les attributs.

Foire Aux Questions (FAQ) sur le Classifieur Naïf de Bayes

Qu'est-ce qui rend le classifieur de Bayes "naïf" ?

Le terme "naïf" vient de l'hypothèse simplificatrice mais forte qu'il fait : tous les attributs (caractéristiques) sont indépendants les uns des autres, étant donné la classe. Cela signifie que la présence ou l'absence d'un attribut n'affecte pas la présence ou l'absence d'un autre attribut, une fois que la classe est connue. Bien que cette hypothèse soit rarement vraie dans le monde réel, le classifieur Naïf de Bayes reste étonnamment efficace dans de nombreux cas.

Quand est-il préférable d'utiliser un classifieur Naïf de Bayes ?

Le classifieur Naïf de Bayes est particulièrement efficace et recommandé dans plusieurs situations : lorsqu'il y a de grandes quantités de données d'apprentissage, pour des problèmes de classification de texte (comme le filtrage de spam ou l'analyse de sentiment) où l'indépendance des mots peut être une hypothèse raisonnable, et lorsque la vitesse d'apprentissage et de prédiction est une priorité. Il est aussi un bon modèle de référence en raison de sa simplicité.

Comment le classifieur Naïf de Bayes gère-t-il les attributs numériques ?

Pour les attributs numériques (continus), le classifieur Naïf de Bayes utilise généralement deux méthodes : la discrétisation, où les valeurs numériques sont converties en catégories (par exemple, des intervalles), ou l'estimation de densité de probabilité, où l'on suppose que les valeurs suivent une distribution statistique connue (comme la loi normale) et où l'on estime les paramètres de cette distribution pour chaque classe. L'estimation de densité gaussienne est la plus courante.