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 (ou "individus") 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 chiffre "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édire à 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.

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

Chevauchement des classes et classification probabiliste

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 mesurés 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, budget 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é par nature probabiliste. 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 se lit "Probabilité pour que l'observation appartienne à la classe C_i, sachant que ses attributs sont décrits par le vecteur x", et P{C_i | x} est appelée la "probabilité de C_i conditionellement à x".

Toute nouvelle observation appartient de fait à une certaine classe : l'expression "probabilité d'appartenance à une classe" est donc un abus de langage (universellement accepté). L'évènement authentiquement probabiliste est le caractère correct ou incorrect de l'affectation de l'observation à une classe : P{C_i | x} et la probabilité pour que l'affectation à la classe C_i soit correcte, et est donc la proportion des nouvelles observations ayant x comme vecteur d'attributs et qui appartiennent effectivement à la classe C_i.

Régions de décision et fonctions discriminantes

Forme des régions de décision

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 (le prêt est accordé ou bien est refusé). Ceci implique que le classifieur attache à tout point de l'espace des attributs une étiquette de classe. Tous les points portant la même étiquette forment une région de décision.

Dans cette illustration, toutes les observations situées au-dessus de la ligne bleue (la fontière de décision) 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 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,
• Le choix fait par l'analyste du type de modèle de classification à construire,
• Le choix des réglages de l'algorithme utilisé pour construire ce classifieur à partir de l'ensemble d'apprentissage.

Fonctions discriminantes

Bien que se présentant sous des formes très diverses selon le type de modèle de classification, le processus par lequel les régions de décision sont définies est toujours fondamentalement le même :

• 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. 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,

Cette approche 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.

Les fonction discriminantes sont souvent choisies linéaires (en 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"),
• Plus souvent une quantité dont on espère qu'elle est fortement associée au taux de mauvaise classification, par exemple :

            * Une quantité définie sur la base d'arguments heuristiques, comme le critère du Discriminant Linéaire de Fisher.

            * 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 (modèles de classification dits "de moindre erreur quadratique moyenne").

            * La vraisemblance de l'échantillon, comme le font la Régression Logistique ou les Réseaux de Neurones. Ces techniques 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.

La Décision Bayésienne

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 toute observation à la classe ayant la plus grande probabilité a posteriori (supposée connue) est optimale, c'est à dire génère un plus petit nombre d'erreurs d'affectation 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.

Dans une perspective de minimisation du taux d'erreur de classification, on souhaite donc que les valeurs des fonctions discriminantes g_i(x) soient aussi proches que possible des vraies (et inconnues) probabilités a posteriori P{C_i | x}. Une fois ces probabilités estimées par le classifieur, une nouvelle observation est affectée à la classe ayant la probabilité a posteriori estimée la plus élevée.

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 existe 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 :

    1) Les probabilités a priori des classes sont connues (ou peuvent être estimées),

    2) 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 adoptée par l'Analyse Discriminante, qui suppose que les classes sont toutes multinormales : l'estimation des densités conditionnelles revient alors à estimer les coefficients des matrices de covariance des diverses classes. Pour cette raison, on dit que l'Analyse Discriminante est une technique paramétrique.

        - Lorsqu'aucune densité simple à modéliser ne paraît convenir, on peut, en désespoir de cause, procéder une estimation non paramétrique des densités conditionnelles, par exemple par une méthode de k-premiers voisins ou par des Arbres de Décision.

Ces techniques, conceptuellement simples, faciles à mettre en œuvre et aux résultats aisément interprétables, souffrent cependant de performances souvent médiocres en raison de leur forte variance (voir "compromis biais-variance"). De plus, leurs paramètres (même les techniques dites "non paramétriques" ont des paramètres !) ne suivent en général pas de distribution identifiable, et il n'est donc pas possible de leur affecter des intervalles de confiance, ou de procéder à des tests portant sur leur nullité éventuelle.

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 densités de probabilité 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 ainsi que procèdent les Réseaux de Neurones. La Régression Logistique est également une technique directe de Classification par régression sur les indicatrices de classe.

___________________________________

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 vu du cadre général esquissé dans cette page.

____________________________________________________________

Voir aussi :