Un classifieur rapide et économe en puissance de calcul
Qu’est ce qu’un classifieur ?
Un classifieur est un algorithme permettant de définir la classe d’un objet suivant certaines de ses propriétés. Pour bâtir notre classifieur nous avons à notre disposition un ensemble d’objets dont on connait la classe par avance. Ce set d’objet est appelé set d’entrainement.
Par exemple, nous souhaitons classé des textes selon deux classes : écrit scientifique OU écrit romanesque (classification appelée binaire car composée de deux classes). Nous aurons donc à notre disposition un ensemble composé de 20 textes dont 12 classés “écrit romanesque” et les autres classés “écrit scientifique”.
Notre problème va donc consister à classer un nouveau texte en fonction de son contenu dans ces deux classes.
Utilisation de la théorie des probabilités
Notre algorithme aura la lourde tâche de fournir une classe à notre nouveau texte. Notre approche dans le cas de la classification naïve Bayesienne va être probabiliste. Nous allons chercher à déterminer la probabilité que notre objet appartient à la classe “écrit romanesque” à la probabilité que notre écrit appartient à l’autre classe. Nous allons ensuite comparer ces deux probabilités pour sélectionner la plus grande des deux.
Trouver la classe revient donc à calculer deux grandeurs et les comparer. Ce qui si on compare à l’algorithme des K voisins les plus proches (voir l’article ici) est très économe en calculs. Avant d’étudier plus en détail d’algorithme nous nous devons de faire un rappel sur les probabilités conditionnelles, qui constituent le fer de lance de cet algorithme.
Un passage obligé par les probabilités conditionnelles
La probabilité d’un événement A est un nombre variant entre 0 et 1 qui traduit le degrés de chance qu’un évènement A se produise. Plus on s’approche de la valeur 1 plus cet événement aura de chance de se dérouler.
Par exemple si on prend l’événement A “une élection va se dérouler en 2017”. La probabilité de cet événement est de 1 car il s’agit d’un événement certain.
Une probabilité conditionnelle est légèrement plus complète dans le sens où elle intègre dans son calcul un autre évènement. Ainsi une probabilité conditionnelle traduit le degrés de chance qu’un élément se produise sachant qu’un autre évènement s’est produit.
Par exemple, si on prend l’évènement A “réussite d’un test de maths”. L’évènement B “être mathématicien” et l’évènement C “avoir suivi un cursus scolaire littéraire”. Alors la probabilité de A sachant l’évènement B sera plus importante que la probabilité de A sachant l’événement C.
Mathématiquement on note une probabilité conditionnelle de deux façons :
$P_{B}(A) = P(A | B)$La formule des probabilités conditionnelles se calcul ainsi :
$P_{B}(A) = P(A | B) = \frac{P(A \cap B)}{P(B)}$La formule de Bayes
Fonctionnement théorique
Prenons un exemple afin de comprendre de quoi il en retourne. Imaginons un hôpital dans lequel on fait passer un test de dépistage de la tuberculose à certains patients. Les médecins dispose de données permettant d’établir que la fiabilité de ce test est de 90%, c’est à dire que 90% des tests sont fiables (les patients sont vraiment malades), il reste que 10% des tests sont des faux-positifs ou des faux-négatifs (le patient est bien malade mais dispose d’un test lui indiquant le contraire).
La formule de Bayes pourra nous donner la réponse à la question suivante : “sachant que le test de M.X est positif quel est la probabilité que celui-ci ne soit pas malade ?” On cherche donc à remonter dans le temps…
La formule de Bayes est définie ainsi :
$P_{B}(A) = \frac{P_{A}(B).P(A)}{P(B)}$
Si on n’applique la formule à notre exemple on aura :
- A : Ne pas être malade
- B : Avoir un résultat de test positif
Ainsi la probabilité de ne pas être malade sachant qu’on a un test de dépistage positif est le rapport entre la probabilité d’avoir un résultat positif sachant qu’on est malade multiplié par la probabilité de ne pas être malade et la probabilité d’avoir un résultat de test positif.
Application à un problème de classification
On va chercher dans notre cas la probabilité qu’un objet appartient à la classe i sachant qu’il a les propriétés x et y. Soit :
$P_{x,y}(C_i)$
Si on a deux classes (1 et 2) dans notre problème nous allons donc comparer deux grandeurs :
$P_{x,y}(C_1) et P_{x,y}(C_2)$
Dans tous les cas nous devrons isoler des features, des propriétés relatives aux objets que nous souhaitons classer. Si nous souhaitons donc classer un document nous prendons par exemple 1000 propriétés correspondant chacune à la présence ou non d’un mot courant dans le texte.
Pourquoi cet algorithme est-il naïf ?
Nous faisons deux assomptions un peu naïves sur notre données :
- Les features ou les propriétés sont indépendantes les unes des autres. Or c’est rarement le cas, si on prend les classifications de textes la présence d’un mot peut être lié à la présence d’un autre mot !
- On fait aussi le postulat que les features sont d’importances équivalentes dans la tâche de classification, ce qui n’est encore pas vraiment le cas. Pour certains textes la présence d’un mot ou d’un groupe de mot est très signifiant dans leur classe.
Application en NodeJS via le module “bayes”
Nous allons créer un script permettant de classer des phrases selon deux classes : les phrases provenant de romans et ceux d’écrits scientifiques.
Créez un nouveau dossier nommé
bayes_classifier1
$ mkdir bayes_classifier
Placez vous dans ce dossier
1
$ cd bayes_classifier
Initialisez
npm
1 | $ npm init |
- Après avoir répondu à l’ensemble des questions installez le module
bayes
1 | $ npm install bayes --save |
Créez un nouveau fichier
index.js1
$ touch index.js
Dans ce fichier faites un require du module bayes.
1
2var bayes = require('bayes')
var classifier = bayes()Nous allons ensuite entrainer notre modèle pour reconnaître les écrits romanesques (fiction):
1
2
3
4
5
6
7
8
9
10
11
12
13// Make the algorithm learn the training data
// The Great Gatsby
classifier.learn('Il me sourit avec une sorte de complicité - qui allait au-delà de la complicité.', 'fiction')
// 1984 (Orwell)
classifier.learn('Celui qui a le contrôle du passé, disait le slogan du Parti, a le contrôle du futur. Celui qui a le contrôle du présent a le contrôle du passé.', 'fiction')
// Le dernier Jour d'un Condamné (Hugo)
classifier.learn('Maintenant je suis captif. Mon corps est aux fers dans un cachot, mon esprit est en prison dans une idée.','fiction')
// Guerre et Paix (Tolstoï)
classifier.learn('Oui, ils m ont accablé de reproches là-bas, et pour la guerre et pour la paix...','fiction')
// Les Caractères (La Bruyères)
classifier.learn('on n aime qu une seule fois : c est la première ; les amours qui suivent sont moins involontaires.','fiction')
// O.Wilde
classifier.learn("S'aimer soi-même, c'est l'assurance d'une longue histoire d'amour.","fiction")Entrainons le maintenant pour reconnaître des écrits scientifiques (science):
1 | /** |
- Maintenant nous allons tester notre modèle avec deux exemples non classés.
1 |
|
La console affiche :1
2fiction fiction
science science
On a un résultat concordant ! Pour les impatients voici le repo contenant ce morceau de code : https://github.com/maximilienandile/bayes_classifier