Classification

Avertissement : en Français, le mot classification a deux significations. Il désigne :
             *  Soit ce que nous appelons dans ce document "classification non supervisée",
             *  Soit ce qui est décrit dans le texte ci-dessous, et qui est parfois appelé "classement", ou "classification supervisée".

Les observations sont souvent regroupées naturellement en groupes, ou "classes". Par exemple :

• Une famille de symptômes est associée à une pathologie, et une autre série de symptômes à une autre pathologie.
• Certaines caractéristiques sociologiques sont associées à un comportement d'achat, alors que d'autres sont associées à un autre comportement d'achat..
• Certains ensembles de pixels sont reconnus comme représentant le chiffre "3", alors que d'autres ensembles de pixels sont reconnus comme représentant le choffre "5" (Reconnaissance des formes).
• Une famille de signaux radar est associée à un certain modèle d'avion, alors qu'une autre famille est caractéristique d'un autre modèle d'avion.

Dans une table de données, la classe à laquelle l'observation appartient est représentée par une variable nominale, dont les modalités sont les noms des classes. Une observation de la table est dite "étiquetée" par le nom de la classe à laquelle elle appartient. L'exemple ci-dessous est une représentation (outrageusement simplifiée) d'une table de l'historique commercial d'une société de crédit à la consommation. Chaque client est décrit par un certain nombre d'attributs (ou variables). La dernière colonne décrit l'issue du processus de remboursement du prêt, sans incident , ou avec incident. Nous n'avons donc ici que deux classes (une situation très fréquente) :

• Remboursement sans incident (Etiquette "O"),
• Incident de remboursement (Etiquette "N").

Ultérieurement, de nouvelles observations sans étiquette de classe seront collectées. Dans l'exemple ci-dessus, un nouveau candidat à un prêt remplira un questionnaire qui se traduira dans la table par :

La Classification est l'action de prévoir à laquelle des deux classes ("O" ou "N") la nouvelle observation appartiendra lorsque cette appartenance  pourra être établie (ici, à l'issue de la période de remboursement). Elle cherche à répondre à la question "Supposons que nous accordions le prêt à ce candidat. Remboursera-t-il le prêt sans incident ?".

Pöur répondre à la question, les valeurs mesurées des attributs du candidat seront entrées dans un modèle de classification (ou classifieur), qui produira une prédiction d'appartenance de l'observation à l'une ou l'autre classe. Le classifieur est un jeu d'équations ou de règles logiques construit à partir des données déjà étiquetées disponibles de la base de données (ensemble d'apprentissage).

Un classifieur est un modèle prédictif. Comme tous les modèles prédictifs, on attend de lui qu'il remplisse deux rôles :

1. Accomplir la prédiction. A cette fin, le classifieur considère que le jeu d'attributs retenus (les prédicteurs) contient implicitement l'information nécessaire pour reconstruire la variable à prédire (l'étiquette de classe). Il extrait alors de la masse considérable d'information présente dans la table (et en grande partie non pertinente) cette petite fraction relative l'étiquette de classe.
2. Mettre en évidence certaines structures des données, et plus particulièrement les quelques prédicteurs qui sont les plus importants pour une bonne qualité de prédiction. Dans l'exemple ci-dessus, la société de crédit serait intéressée par l'identification de quelques caractéristiques (parmi des centaines possibles) des candidats qui sont particulièrement efficaces pour prédire l'issue, favorable ou non, du processus de remboursement.

---------------------

En plus des difficultés propres à toute modélisation (), la Classification rencontre au moins deux difficultés qui lui sont propres :

1. En général, les classes se chevauchent.
2. Les classes peuvent avoir des formes arbitrairement complexes dans l'espace des prédicteurs.

Exminons ces deux points un peu plus en détail.

Chevauchement des classes

        Les classes (et pas seulement les données disponibles) se chevauchent le plus souvent. Ceci veut dire que deux observations (déjà étiquetées ou non) dont les attributs ont des valeurs identiques peuvent appartenir à des classes différentes. Par exemple, de deux automobilistes ayant des profils mesurés identiques (sexe, âge, revenu, nombre d'enfants, kilométrage annuel etc...), l'un peut avoir acheté le modèle A, alors que l'autre a acheté le modèle B.

En raison de ce chevauchement, un classifieur délivrant des verdicts tranchés ("La nouvelle observation appartient à la classe C_i") est condamné à commettre des erreurs, quels que soient les soins et l'expertise avec lesquels il a été construit. En fait, les classifieurs énoncent le plus souvent un verdict plus nuancé, qui s'exprime en termes de probabilités (estimées). Etant donnée une nouvelle observation x, le verdict sera :

• La probabilité (estimée) pour que x appartienne à la classe C_i est P(i), i = 1, 2, ..., n , où n est la nombre de classes.

La Classification est donc une activité probabiliste par nature. Les nombres P(i) sont appelées les probabilités a posteriori des différentes classes pour l'observation x. Dans un contexte plus technique, elles sont notées P{C_i , x}. Cette notation s'énonce "Probabilité pour qu'une observation appartienne à la classe C_i, sachant que ses attributs sont décrits par le vecteur x".

Frontières de classes

        Malgré l'incertitude causée par la nature probabiliste de la Classification, l'analyste devra finalement trancher, et affecter toute nouvelle observation à une classe unique. Ceci implique qu'à tout point de l'espace des attributs est attachée une étiquette de classe. Tous les points portant la même étiquette forment une région de décision.

La forme de la frontière entre deux régions de décision est déterminée par :

• Les données disponibles lors de la construction du classifieur,
• et le choix de l'algorithme utilisé pour construire le classifieur à partir de l'ensemble d'apprentissage.

Dans cette illustration, toutes les observations situées au-dessus de la ligne bleue seront affectées à la classe C₁, alors que toutes les observations situées sous cette ligne seront affectées à la classe C₂. Ainsi, pour qu'un classifieur donne de bons résultats (nous revenons sur cette notion plus bas), les frontières entre régions de décision doivent pouvoir prendre des formes complexes.

---------------------

La Décision Bayésienne

        Une fois les probabilités a posteriori P{C_i , x} estimées par le classifieur, il paraît naturel d'affecter une nouvelle observation à la classe ayant la probabilité la plus élevée.

Donc, en fait, le classifieur n'effectue pas la classification (affectation à une classe) à proprement parler. Cette affectation est faite sur la base de règles d'affectation concoctées par l'analyste à partir des probabilités a posteriori calculées par le classifieur.

Cette attitude est justifiée par le résultat suivant.

Définir la qualité d'un classifieur repose sur ce qui est attendu exactement de la part du processus de classification. Ceci ne dépend pas du mécanisme interne de la modélisation, mais plutôt de l'objectif que l'analyste cherche à atteindre. Cet objectif est le plus souvent exprimé en termes de minimisation d'une quantité reliée à la classification. Dans ce Glossaire, nous n'aborderons que le plus simple de ces objectifs :

• Minimiser le nombre d'erreurs d'affectation sur de nouvelles observations (donc non étiquetées).

La théorie de la Décision Bayésienne établit que la stratégie qui consiste à affecter une nouvelle observation à la classe ayant la plus grande probabilité a posteriori est optimale, c'est à dire génère un plus petit nombre d'erreurs que toute autre stratégie.

Ce résultat peut être généralisé à une situation d'un grand intérêt pratique. Une erreur d'affectation est toujours coûteuse, mais toutes les erreurs n'ont pas le même coût : certaines peuvent être relativement inoffensives, alors que d'autres peuvent avoir des conséquences dramatiques. L'objectif de l'analyste est alors non pas de minimiser le nombre d'erreurs d'affectation, mais de minimiser le coût moyen de ces erreurs. La théorie de la Décision Bayésienne résoud également cette question.

Estimer les probabilités a posteriori

        Donc, en théorie, le cadre bayésien résoud complètement le problème de la Classification, pour peu que les P(i) puissent être calculées, ou pour le moins estimées. Il y a deux grandes approches de l'estimation des probabilités a posteriori :

Méthodes indirectes

            Le théorème de Bayes fournit un moyen de calculer les probabilités a posteriori P(i) si :

• Les probabilités a priori des classes sont connues (ou peuvent être estimées),
• Les densités de probabilité à l'intérieur de chacune des classes peuvent être estimées (ces densités de probabilités s'appellent les densités de probabilité conditionnelles). Cette estimation est l'objectif des techniques dites "d'estimation de densité de probabilité". Souvent, une forme analytique particulière de ces densités est postulée, et l'estimation se ramène alors à celle des valeurs d'un petit nombre de paramètres à partir des données, en espérant que le résultat obtenu ne soit pas trop éloigné des densités de probabilité réelles. C'est par exemple l'approche prise par la forme de base de l'Analyse Discriminante, qui suppose que les classes sont toutes multinormales et de matrices de covariances identiques.

Méthodes directes

            L'estimation raisonnablement précise de densités de probabilité est, dans le cas général, difficile, voire hasardeuse. Le théorème de Bayes nous dit que les probabilités a posteriori peuvent être estimées en ayant recours aux densités de probabilité conditionnelles, mais il ne dit pas que c'est la seule façon de les obtenir. En fait, on montre (et il est assez intuitif) qu'une régression parfaite sur les indicatrices de classes a pour résultat justement les probabilités P(i).

Ainsi, plusieurs techniques évitent la phase d'estimation des denstiés de probabilités conditionnelles, et estiment directement les probabilités a posteriori en effectuant une sorte de régression sur les indicatrices de classe. C'est par exemple le cas des Réseaux de Neurones. La Régression Logistique est également une technique directe de Classification par régression sur les indicatrices de classe.

Fonctions Discriminantes

        Nous sommes donc maintenant convaincus qu'estimer les probabilités a posteriori P{C_i , x}est une bonne approche pour de nombreux problèmes de classification. Cependant, cette estimation peut être difficile en pratique, et le cadre strict de la Décision bayésienne peut être assoupli pour rendre le problème plus accessible.

Une façon simple de procéder est de considérer l'estimation des P(i) comme la solution idéale, mais de se satisfaire d'une solution moins ambitieuse de la façon suivante :

• Pour chaque classe C_i, une fonction g_i(.) est élaborée.
• Pour toute nouvelle observation x, tous les g_i(x) sont calculés.
• L'observation est affectée à celle des classes dont la g_i(x) a la plus grande valeur.

Les g_i(x) sont appelées des fonction discriminantes. Si elles sont bien conçues, leurs valeurs ne seront pas trop éloignées des vraies probabilités a posteriori P{C_i , x}, et le classifieurs fonctionnera de façon satisfaisante. Il y a autant de fonctions discriminantes que de classes, et chaque classe a sa fonction discriminante. Les frontières entre régions de décisions sont définies par l'ensemble des équations g_i(x) = g_j(x)  (i  j).  

Lorsqu'il n'y a que deux classes C₁ and C₂,  on ne définit qu'une seule fonction discriminante  g(x) ajustée de façon que :
   * x soit affectée à C₁ si g(x) > 0,
   * x soit affectée à C₂ si g(x)  0,

L'avantage de cette approche est qu'elle procure une grande souplesse dans le choix :

• De la forme analytique des fonctions discriminantes,
• De la façon dont les valeurs des paramètres des g_i(x) seront calculés (sans référence aux densités de probabilité).

Les calculs sont alors simples, et les résultats interprétables, souvent au prix d'une perte de précision acceptable.

Les fonction discriminantes sont souvent choisies linéaires (in x), ce qui conduit à des régions de décision convexes et des frontières linéaires par morceaux.

Mais elles peuvent également être quadratiques, ou même prendre des formes analytiques plus complexes.

Les paramètres des fonctions discriminantes sont ajustés de façon à minimiser un critère choisi par l'analyste :

• Rarement le nombre d'erreurs de classification (p. ex. le Percepton "de base"),
• Le plus souvent, une quantité dont on espère qu'elle est fortement associée au taux de mauvaise classification. C'est par exemple le cas des méthodes de "moindre erreur quadratique moyenne". Des nombres sont attachés aux observations de façon appropriée, et on demande au modèle de prédire ces nombres avec la plus petite erreur quadratique possible. Cette approche, comme les méthodes de régression sur les indicatrices de classes, recodent les modalités des classes sous forme numérique, et une certaine forme de régression est alors opérée sur ces codes numériques.

Accepter une augmentation du taux d'erreur en échange de rapidité, simplicité et interprétabilité des modèles est une attitude poussée à l'extrême dans les Arbres de Décision : les fonctions discriminantes sont alors construites récursivement, une variable à la fois. Il sont rapides et interprétables, et par là même très populaires, malgré un relatif manque de précision dans leurs prédictions.

---------------

Les nombreuses techniques de Classification sont nées le plus souvent de la nécessité de résoudre des problèmes pratiques issus de domaines très variés. De ce fait, il est courant de les voir décrites individuellement sans que l'accent soit mis sur leurs rapports avec les autres techniques (avec lesquelles elles sont en concurrence), ou sur leur positionnement dans le cadre général de la Classification. Dans ce Glossaire, nous essayerons, autant que faire se peut, de maintenir une vue unifiée de la Classification, et de décrire les techniques au vue du cadre général esquissé dans cette page.