Cours approches de classification : Etat de l’art, tutoriel & guide de travaux pratiques en pdf.

L’apprentissage supervisé

Le cadre général de l’apprentissage supervisé consiste, à partir de l’observation d’un ensemble de couple de données de la forme [(x(i), y(i)], (i = 1 —> n), à induire la valeur de y pour de nouvelles valeurs de x. Dans un cadre probabiliste, chaque x(i) représente une observation d’une variable aléatoire X.
Suivant les valeurs de la variable aléatoire Y, deux cas de figures peuvent être distingués : lorsqu’elle prend des valeurs discrètes, on parle de catégorisation, lorsque ses valeurs sont discrètes, de régression.
Le cadre statistique de la catégorisation supervisée considère le problème de l’apprentissage comme celui de l’induction d’une fonction f. Sous l’hypothèse que les observations sont indépendantes et uniformément distribuées selon une loi de probabilité inconnue P, la meilleure fonction (hypothèse) sera celle qui a une espérance de risque minimum (Yvon, 2006).
Ce cadre général est bien connu et plusieurs outils statistiques ont été utilisés dans le domaine pour résoudre ce problème : réseaux de neurones, régression logistique, Formule de Bayes, arbres de décisions, k-plus proche voisins, machines à vecteurs de support (SVMs), boosting, et bien d’autres. Ces modèles se généralisent plus ou moins directement aux situations dans lesquelles Y prend plus de deux valeurs (catégorisation multiclasses).

La catégorisation est un problème de classification supervisée

Pour construire un filtre relatif à une classe donnée, il faut donc disposer de couples (Document, Classe), ces exemples de chaque classe, préalablement étiquetés constituent le corpus d’apprentissage.
On fait appel aux méthodes d’apprentissage supervisées pour ajuster un modèle qui crée une association entre les documents d’entrée et les classes de sortie. Ainsi, par ces méthodes d’apprentissage, il est possible de construire un modèle de classification, à partir de ces exemples connus à priori (Document, Classe). (Jalam, 2003)
Ce qui affirme clairement que la catégorisation de textes est bien un problème de classification supervisée.

Comment classer ?

Classer les documents revient en réalité à déterminer les paramètres de la fonction de classement. Voici l’idée globale de ce qu’on doit faire :
ν Il faut disposer d’un corpus d’apprentissage, qui va servir d’entrée à un algorithme d’apprentissage.
ν On sélectionne un autre corpus qui sert pour l’évaluation (corpus de test)
ν Il faut d’abord déterminer les descripteurs (variables de la fonction)
ν Il faut fournir à l’ordinateur un type de fonctions de classement lui permettant d’associer une catégorie à un texte.
• SVMs
• Naïve Bayes
• Règles de décision
• Arbres de décision
• Réseaux de neurones
• Autres fonctions …
ν On infère, à partir des données, et par des méthodes mathématiques complexes, les paramètres de la fonction de classement utilisé, qui peuvent être :
• Coefficients de l’hyperplan dans les SVMs
• Distributions de probabilité dans les classificateurs probabilistes
• Règles dans les règles de décision
• Conditions et branchements dans les arbres de décision
• Poids dans les réseaux de neurones
• …
ν On se fonde sur la connaissance préalable des bonnes catégories pour les documents du corpus d’apprentissage (apprentissage supervisé).

Différents modèles de classifieurs

Historiquement, différentes générations d’algorithmes de classification automatique de textes se sont succédé. Une part d’amélioration a été apportée par chaque nouvelle génération par rapport aux antécédentes. Parmi les premières, nous trouverons certainement les approches sémantiques dont l’handicap principal résidait dans le coût excessif puisque plusieurs experts sont chargés dans des intervalles de temps importants, pour mettre à jour les plans de classement.
Pour apaiser à ces limitations, plusieurs boites ont conçues et commercialisées des technologies de catégorisation automatique basées sur des approches purement statistiques.
Plusieurs générations de techniques statistiques ont depuis été développées et qui ont confirmé leurs performances en obtenant de meilleurs résultats.
Actuellement, plusieurs approches de catégorisation coexistent. Nous citons parmi les plus utilisées le modèle probabiliste Naïve Bayes, ou les modèles vectoriels de Machine à Vecteur de Support, les k-plus-proches voisins, Rocchio, ainsi que des modèles à base de règles ou d’arbre de décision ou encore des approches fondées sur les réseaux de neurones qui ont été proposées. Chacun de ces modèles possède certains avantages et certains inconvénients. Dans ce qui suit une liste plus ou moins exhaustive des différents modèles et de leur intérêt respectif sera présentée. Une description plus détaillée sera accordée à l’approche naïve bayesienne dans le chapitre 6 qui fera l’objet des modèles de classification dans notre approche proposée.

Machines à Vecteurs Support – SVM

Présentation de l’approche

L’algorithme SVM (Support Vector Machine) est une méthode d’apprentissage supervisée relativement récente introduite pour résoudre un problème de reconnaissance de formes à deux classes (Vapnik, 1995). Le principe de SVM a été proposé par Vapnik à partir de la théorie du risque empirique.
La méthode SVM est un classificateur linéaire utilisant des mesures de distance.
En ce qui concerne son application à la problématique de catégorisation de documents, l’algorithme repose sur une interprétation géométrique simple est l’idée générale est de représenter l’espace des exemples (ici des documents) dans un espace vectoriel où chaque document étant un point dans cet espace et de trouver la meilleure séparation possible de cet espace en deux classes. L’espace de séparation est une surface de décision appelée marge, défini par les points « vecteur support ». Ces points se trouvent au minimum de marge. La marge se présente alors comme la plus courte distance entre un vecteur de support et “son” hyperplan. La marge se définit comme la plus petite distance entre les exemples de chaque classe et la surface séparatrice S :
marge (S)  ∑ min xi∈cj (d(xi ,S)) cj∈C
Ainsi la décision s’appuie sur les SVM pour couper l’espace en deux : d’un côté, ce qui est dans la catégorie, de l’autre côté, ce qui n’y est pas.
l’approche par SVM permet donc de définir, par apprentissage, un hyperplan dans un espace vectoriel qui sépare au mieux les données de l’ensemble d’apprentissage en deux classes, minimisant le risque d’erreur et maximisant la marge entre deux classes. La qualité de l’hyperplan est déterminée par son écart avec les hyperplans parallèles les plus proches des points de chaque classe. Le meilleur hyperplan est celui qui a la marge la plus importante.
SVM a été étendu pour les points ne pouvant être séparées de manière linéaire (par exemple notre cas des vecteurs de documents), en transformant l’espace initial des vecteurs de données à un espace de dimension supérieure dans lequel les points deviennent séparables linéairement. Nous trouvons dans (Joachims, 1998) une application efficace des SVM.
La figure 3.1 montre une telle séparation dans le cas d’une séparation linéaire par un hyperplan.
Figure 3.1: Exemples d’hyperplans séparateurs en dimension deux.
Les vecteurs de support sont encerclés
Dans l’exemple de la figure 3.1, les exemples des deux classes peuvent être séparés par un hyperplan, le problème est dit linéairement séparable. Les deux hyperplans H1 et H2 sont tous les deux des séparateurs acceptables, mais l’hyperplan H1 a une plus grande marge et sera donc préféré. Pour calculer l’hyperplan optimal et donc la marge, seuls les exemples les plus proches de la zone-frontière sont mis à contribution. L’apprentissage consiste à déterminer ces exemples appelés vecteurs de support. Tous les autres peuvent être écartés et n’interviennent plus dans les calculs.
Le problème se traduit mathématiquement en un problème d’optimisation quadratique : trouver l’hyperplan (w,b) (b est la distance à l’origine de l’hyperplan) qui minimise la norme de w sous les contraintes : ∀di , ci (w.di − b) ≤ 1
Avec di le iéme document, de classe ci (+1 ou –1). Si les exemples ne sont pas linéairement séparable, on peut les plonger conceptuellement dans un espace de dimension plus grande (la dimension peut même être infinie) par une fonction de transformation appelée noyau (kernel). Dans cet espace, les exemples seront plus facilement séparables. Une propriété de l’algorithme est qu’il ne requiert pas les coordonnées de chaque exemple mais seulement les produits scalaires de chaque couple d’exemples, qui restent calculable une fois les exemples plongés dans un nouvel espace même de dimension infini.
Si cela ne suffit pas pour rendre les exemples séparables, il est possible d’ajouter encore un terme correctif qui autorise un nombre limité d’exemples à être mal classés. Pendant l’apprentissage, on cherchera à rendre ce terme le plus petit possible. Un paramètre de l’algorithme permet de donner plus ou moins d’importance à ce terme correctif. Dans sa formulation initiale, SVM ne peut gérer que des problèmes bi-classes (des extensions commencent à apparaître pour faire du SVM multi-classe). La méthode la plus commune pour résoudre un problème multi-classe reste de le transformer préalablement en plusieurs sous-problèmes bi-classe.
Cet algorithme est particulièrement bien adapté à la catégorisation de textes car il est capable de gérer des vecteurs de grande dimension. Dans la pratique, les catégories sont quasiment toujours linéairement séparables, il n’est donc pas nécessaire d’employer les méthodes avec des noyaux sophistiqués qui alourdissent inutilement les calculs. SVM a été introduit dans le domaine pour la première fois par Joachims qui a notamment travaillé à rendre SVM compatible avec les données textuelles qui sont caractérisées par de grandes dimensions avec des matrices (documents * termes) très creuses.
Depuis, l’approche a été très souvent réutilisé, par exemple pour la détection de courriers électroniques non sollicités ou pour la classification de dépêches.

Critiques de l’approche

Actuellement, l’algorithme SVM semble tres Prometteuse et considéré parmi les plus performants pour la catégorisation en raison de sa modélisation simpliste et rapide à calculer par une machine étant donné que SVM est un Classificateur linéaire qui correspond à une équation polynomiale de degré p :
a1x x+a1y y+a1z z pour la catégorie C1
a2x x+a2y y+a2z z pour la catégorie C2
Seulement elle introduit des concepts complexes peu adaptés aux corpus de grandes tailles non fixes, sans oublier de rappeler de son faible pouvoir descriptif puisque les coefficients ne sont pas interprétables intuitivement par des humains.

Rocchio

Présentation de l’approche

La méthode Rocchio parue dans (Rocchio, 1971), est un classifieur linéaire basée sur le calcul des mesures de distance, il fait partie des premières techniques de classification supervisée. Plusieurs améliorations se sont apportés sur le modèle mais la définition présentée ici est celle de la version initiale.
Dans la phase d’apprentissage de la méthode, les représentations vectorielles, vont permettre le codage de chaque catégorie par un vecteur dont lequel figure tout les termes générés avec leur nombre d’occurrence. Le processus représente donc les classes par des profils prototypiques correspondants à des vecteurs dans un espace vectoriel similaire aux documents. Ces profils sont donc des listes de termes pondérés générées pendant l’apprentissage de même pour les vecteurs correspondants aux textes qui sont aussi générés durant cette phase. Le profil d’une catégorie doit contenir tous les termes qui caractèrisent cette catégorie par rapport aux autres.
Bien évidemment, le vecteur d’une classe sera calculé ici uniquement en fonction des documents du jeu d’apprentissage. Pour construire les profils, il est nécessaire d’utiliser une méthode de sélection et réduction de termes.
Chaque terme du corpus représente une dimension de l’espace et le codage des vecteurs se fait soit par une fonction booléenne soit par une fonction du nombre d’occurrences d’un terme dans le document. Plusieurs pondérations des termes se présentent, la plus utilisée est TFIDF.
Dans la phase de classification, il s’agit de comparer le profil (vecteur) du nouveau document à classer à tous les profils des classes déjà calculés dans l’étape d’apprentissage.
Cette comparaison équivaut au calcul d’une fonction de similarité ou de distance entre les vecteurs représentant les classes et le vecteur correspondant au nouveau document. Elle permet d’ordonner les classes en fonction de leur distance du document. Par conséquent, le principe de catégorisation Rocchio se résume à assigner le document à la classe dont la distance euclidienne entre le vecteur du document et le vecteur de la classe est la plus courte.

Critiques de l’approche

Rocchio est caractérisée par sa modélisation simpliste et rapide à calculer par une machine et malgré l’ancienneté et la simplicité du modèle, la méthode a confirmé par ses performances qui sont concurrentielles à celles obtenues par d’autres techniques plus sophistiquées, avec un gain de temps d’apprentissage pour une machine très considérable.
Plusieurs auteurs dans leurs travaux ont démontré la résistance de Rocchio au bruit : même avec 50% des exemples bruités, les performances sont assurées. Les différentes expérimentations basées cette approche ont donné aussi de très bons résultats sur les tâches de routage (filtre anti-spams par exemple). (Vinot & Yvon, 2002).
En revanche, l’inconvénient principal de la méthode reste sa faiblesse d’expressivité et son pouvoir descriptif très réduit qui fait du modèle une fonction de décision non interprétable intuitivement par les humains.

Méthode du centroïde

Présentation de l’approche

L’algorithme du centre de gravite ou « centroïde » est une variante de l’algorithme Rocchio bien connu dans le domaine, c’est une méthode géométrique utilisant les mesures de distance pour classer les documents.
La phase d’apprentissage consiste à calculer un centroïde pour représenter les classes. Le vecteur centroïde d’une catégorie sera représenté par la moyenne des vecteurs des textes qu’elle contient, qui correspond au barycentre des différents textes préalablement assignés à cette classe. La méthode du centroïde calcule la distance entre les centres de gravité (au sens géométrique) des catégories.
La catégorisation d’un nouveau document se fait par le calcul de similarité entre les vecteurs centroïdes des catégories et le vecteur du nouveau document. La catégorie du centroïde le plus proche est attribuée dans le cas de classification multi-classes disjointes sinon des scores sont calculés pour les classes puis un seuillage est utilisé pour choisir les classes à attribuer.