Mesures de performance de classifieurs

Cours évaluation des classifieurs, tutoriel & guide de travaux pratiques en pdf.

Méthodologies de comparaison de classifieurs

Il existe, en pratique, plusieurs méthodologies pour tenter de répondre à la question : quel est la meilleure méthode pour la catégorisation de textes ?

Différentes approches sur le même corpus

La première solution consiste à comparer différentes méthodes mises en œuvre par différents auteurs sur le même corpus, néanmoins, du point de vue pratique, comme le confirme Radwan JALAM dans (Jalam, 2003), on est confronté à pas mal de problèmes, parmi lesquels :

Même corpus avec des découpages différents

Les différents auteurs n’utilisent pas exactement le même découpage du corpus, par exemple pour Reuters seulement, il y a plus de six versions différentes, qui se distinguent par le nombre de leurs classes et la répartition des documents sur le corpus d’apprentissage et le corpus de test. Pour Reuters-21578 qui est souvent utilisé, (Joachims, 1998), (Schapire & all, 1998), (Yang & Liu, 1999) considèrent 90 catégories, (Dumais & all, 1998) en considèrent 118, d’autres travaillent carrément sur Reuters-top10 comme dans (Turenne, 2000) ou (Denoyer, 2004) ou (Yvon, 2006), qui trient les dix meilleurs catégories (Mini corpus utilisé dans nos expérimentations). De plus, la plupart des auteurs considèrent 3299 documents sur la base de test, mais (Yang & Liu, 1999) en considèrent uniquement 3019 en supprimant tous les documents de la base de test qui n’appartiennent à aucune catégorie. Finalement, ces légères différences de découpage rendent difficiles les comparaisons à travers ces publications.

Les différentes techniques de représentation de textes

Les différentes alternatives offertes, pour le choix de descripteurs, afin de coder un texte, ainsi que les diverses méthodes de réduction de dimensionnalité utilisées par les différents auteurs peuvent embrouiller la comparaison de deux classifieurs s’exerçant sur le même corpus.

Les différentes mesures utilisées pour l’évaluation

Les mesures de performance utilisées dans les différentes expérimentations ne sont pas les mêmes (une description de quelques mesures est présentée dans la section suivante), ainsi les différents critères de performance peuvent être estimés de différentes façons empêchant une comparaison efficace entre les classifieurs.

Différentes approches par le même auteur

Une autre approche, plus crédible de point de vue scientifique, souvent proposée est l’utilisation de plusieurs méthodes par le même auteur, et automatiquement le corpus, le découpage de ce dernier, les techniques de codage, et les mesures de performance sont semblables pour toutes les méthodes. (Yang & Liu, 1999) comparent ainsi les kPPv, les SVM, les réseaux de neurones, et d’autres approches.
(Dumais & all, 1998) proposent également plusieurs comparaisons en mettant en opposition Les SVM, l’algorithme de Rocchio, les arbres de décision, et les réseaux bayesiens.

Difficultés approuvées pour juger les capacités d’une méthode

Les comparaisons présentées évaluent plus les compétences des auteurs dans l’exploitation des différentes approches de l’état de l’art les méthodes, plus que les capacités des méthodes elles-mêmes.
Le problème vient du fait que toutes ces méthodes sont délicates à mettre en œuvre et leurs performances dépendent fortement de leurs différentes utilisations.
Par exemple, l’implémentation des machines à vecteurs supports proposées par (Dumais & all, 1998) obtient nettement de meilleurs résultats que celle proposée par (Joachims, 1998).
Les réseaux de neurones testés par (Yang & Liu, 1999) sont des perceptrons multi-couches avec une couche cachée comportant 64 neurones, 1000 descripteurs en entrées et 90 neurones de sorties correspondant aux 90 catégories ; ils considèrent un seul réseau pour l’ensemble des catégories comportant plus de 64000 poids. Il n’est pas surprenant, dans ces conditions, que les performances obtenues ne soient pas très bonnes.
Il reste aussi difficile d’extrapoler les performances sur d’autres corpus et applications. Les résultats sont extrêmement dépendants du type des textes et des classes (en particulier de leur nombre). Il n’existe pas, à l’heure actuelle d’analyse de la performance des algorithmes en fonction des spécificités des corpus.
Ces différentes remarques prouvent que le succès d’une méthode dépend d’un ensemble de paramètres et certaines conditions non liées seulement, aux algorithmes d’apprentissage eux mêmes, mais aussi aux différents choix opérés pendant tout le processus, et qui peuvent intervenir et influencer les résultats obtenus. Par conséquent, il est extrêmement difficile de tirer des conclusions définitives sur une approche.

TREC

Il nous semble que la conférence TREC (Décrite en annexe) est une bonne solution pour comparer différentes méthodes, car chaque participant propose des solutions qu’il connaît bien avec des algorithmes dont il a pu tester l’efficacité. Le corpus est évidemment identique pour tout le monde, ainsi que les méthodes d’évaluation et la répétition annuelle de cette conférence permet de juger les approches sur le long terme.
De plus la conférence TREC a l’avantage de proposer un état de l’art à un instant donné contrairement aux comparaisons faites à partir des publications pour lesquelles le décalage dans le temps peut rendre certaines conclusions obsolètes.

Mesures de performance de classifieurs

Classification déterministe à deux classes

Nous considérons ici un problème simple de classification pour lequel nous nous intéressons à une classe unique C et nous voulons évaluer un système qui nous indique si un document peut être associé ou non à cette classe C. Ce problème est un problème de classification à deux classes (C et non C noté ¬ C). Si on peut maitriser ce problème simple, on pourra fusionner par la suite, les mesures de performance de plusieurs systèmes bi-classes afin d’obtenir une mesure de la performance d’un classifieur multi-classes.

Matrice de contingence

Pour évaluer un système de classification de ce type, nous utilisons un corpus étiqueté de documents (corpus d’apprentissage) pour lequel on connaît la vraie catégorie de chaque document, et le résultat obtenu par le classifieur. Pour ce corpus, nous pouvons construire la matrice de contingence pour chaque classe (Voir tableau 4.1), qui fournit 4 informations essentielles :
¬ Vrai Positif (VP) : Le nombre de documents attribués à une catégorie convenablement. (Documents attribués à leurs vraies catégories)
¬ Faux Positif (FP) : Le nombre de documents attribués à une catégorie inconvenablement. (Documents attribués à des mauvaises catégories)
¬ Faux Négatif (FN) : Le nombre de documents inconvenablement non attribués.
(Qui auraient dû être attribués à une catégorie mais qui ne l’ont pas été).
¬ Vrai Négatif(VN) : Le nombre de documents non attribués à une catégorie convenablement (Qui n’ont pas à être attribués à une catégorie, et ne l’ont pas été)
A partir de ce tableau de contingence, la communauté du TALN calcule divers indicateurs de base, eux-mêmes combinés pour donner d’autres mesures.

Précision et Rappel

Certains principes d’évaluation sont utilisés de manière courante dans le domaine de catégorisation de textes. Les performances en termes de classification sont généralement mesurées à partir de deux indicateurs traditionnellement utilisés c’est les mesures de rappel et précision. Initialement elles ont été conçues pour les systèmes de recherche d’information, mais par la suite la communauté de classification de textes les a adoptées.
Formellement, pour chaque classe Ci, on calcule deux probabilités qui peuvent être estimées à partir de la matrice de contingence correspondante, ainsi ces deux mesures peuvent être définies de la manière suivante :
¬ Le rappel étant la proportion de documents correctement classés dans par le système par rapport à tous les documents de la classe Ci.
Rappel (Ci)  Nombre de documents bien classés dans Ci
Nombre de documents de la classe Ci
Le rappel mesure la capacité d’un système de classification à détecter les documents correctement classés. Cependant, un système de classification qui considérerait tous les documents comme pertinents obtiendrait un rappel de 100%. Un rappel fort ou faible n’est pas suffisant pour évaluer les performances d’un système. Pour cela, on définit la précision.
¬ La précision est la proportion de documents correctement classés parmi ceux classés par le système dans Ci .
La précision mesure la capacité d’un système de classification à ne pas classer un document dans une classe, un document qui ne l’est pas. Comme elle peut aussi être interprétée par la probabilité conditionnelle qu’un document choisi aléatoirement dans la classe soit bien classé par le classifieur.
Ces deux indicateurs pris l’un indépendamment de l’autre ne permettent d’évaluer qu’une facette du système de classification : la qualité ou la quantité. Les courbes de précision vs rappel permettent de mieux comprendre le comportement du classifieur, et de visualiser l’évolution de la précision en fonction du rappel pour les 11 niveaux standard [0-0,1-0,2-…-1].