Les méthodes de classification ont pour but d'identifier les classes
auxquelles appartiennent des objets à partir de certains traits
descriptifs. Elles s'appliquent à un grand nombre d'activités humaines
et conviennent en particulier au problème de la prise de décision
automatisée. Il s'agira, par exemple, d'établir un diagnostic médical
à partir de la description clinique d'un patient, de donner une
réponse à la demande de prêt bancaire de la part d'un client sur la
base de sa situation personnelle, de déclencher un processus d'alerte
en fonction de signaux reçus par des capteurs. Une première approche
possible pour résoudre ce type de problème est l'approche ``systèmes
experts''. Dans ce cadre, la connaissance d'un expert (ou d'un groupe
d'experts) est décrite sous forme de règles. Cet ensemble de règles
forme un système expert qui est utilisé pour classifier de nouveaux
cas. Cette approche, largement utilisée dans les années 80, dépend
fortement de la capacité à extraire et à formaliser les connaissances
de l'expert. Nous considérons ici une autre approche pour laquelle la
procédure de classification sera extraite automatiquement à partir
d'un ensemble d'exemples. Un exemple consiste en la description d'un
cas avec la classification correspondante. Par exemple, on dispose
d'un historique des prêts accordés avec, pour chaque prêt, la
situation personnelle du demandeur et le résultat du prêt (problèmes
de recouvrement ou non). Un système d'apprentissage doit alors, à
partir de cet ensemble d'exemples, extraire une procédure de
classification qui, au vu de la situation personnelle d'un client,
devra décider de l'attribution du prêt. Il s'agit donc d'induire
une procédure de classification générale à partir d'exemples. Le problème est
donc un problème inductif, il s'agit en effet d'extraire une règle
générale à partir de données observées. La procédure générée devra classifier
correctement les exemples de l'échantillon mais surtout avoir un bon
pouvoir prédictif pour classifier correctement de nouvelles
descriptions.
Les méthodes utilisées par les systèmes d'apprentissage sont très
nombreuses et sont issues de domaines scientifiques variés. Les
méthodes statistiques supposent que les descriptions des objets d'une
même classe se répartissent en respectant une structure spécifique à
la classe. On fait des hypothèses sur les distributions des
descriptions à l'intérieur des classes et les procédures de
classification seront construites à l'aide d'hypothèses probabilistes.
La variété des méthodes viendra de la diversité des hypothèses
possibles. Ces méthodes sont appelées semi-paramétriques. Des méthodes
non paramétriques (sans hypothèse a priori sur les distributions) ont
été également proposées en statistiques. Les méthodes issues de
l'intelligence artificielle sont des méthodes non paramétriques. On
distingue les méthodes symboliques (la procédure de classification
produite peut être écrite sous forme de règles) des méthodes non
symboliques ou adaptatives (la procédure de classification produite
est de type << boîte noire >>). Parmi les méthodes symboliques, les plus
utilisées sont basées sur les arbres de décision. Pour les méthodes
adaptatives, on distingue deux grandes classes : les réseaux de
neurones et les algorithmes génétiques.
L'apprentissage automatique, dans une définition très générale,
consiste en l'élaboration de programmes qui s'améliorent avec
l'expérience. Les applications sont nombreuses et concernent des
domaines très variés. On peut citer, par exemple, la reconnaissance de
formes avec, en particulier, la reconnaissance de la parole et du
texte écrit, le contrôle de processus et le diagnostic de pannes, les
programmes de jeu. Les méthodes d'apprentissage à partir d'exemples
sont très utilisées dans la recherche d'informations dans de grands
ensembles de données. En effet, l'évolution de l'informatique permet
de nos jours de manipuler des ensembles de données de très grande
taille (<< datawarehouse >> ou << entrepôt de données >>). Par exemple,
les chaînes de magasin peuvent mémoriser de grandes quantités de
données concernant les consommateurs et ce qu'ils achètent. Le
développement des technologies Internet et Intranet font que de
nombreuses données issues de sources diverses et dans des formats
variés deviennent accessibles. Le processus de recherche
d'informations dans de grands ensembles de données (KDD : Knowledge
Discovery in Databases) comporte différentes étapes : la
sélection des données (extraction des informations de l'entrepôt) ; la
préparation des données (suppression des doublons, élimination des
données aberrantes, ...) ; le codage des données (normalisation des
données, choix de codage, ...) ; la phase d'extraction proprement dite
appelée fouille de données (Data mining) ; la sortie des résultats. La
phase d'extraction d'information utilise les outils usuels
d'interrogation tels que les requêtes SQL standard et les requêtes
multidimensionnelles, mais aussi, pour l'extraction d'informations
cachées, les algorithmes d'apprentissage à partir d'exemples. Les
algorithmes les plus utilisés sont : les k-plus proches voisins, les
arbres de décision, les systèmes de règles (programmation logique
inductive), les réseaux de neurones et les algorithmes génétiques.
Citons, parmi
d'autres, quelques applications et leur domaine :
-
analyse financière : prévision d'évolution de marchés,
- marketing : établir un profil client, mailing (augmenter les
taux de retour),
- banque : attribution de prêts,
- médecine : aide au diagnostic,
- telecom : détection de fraudes.
Dans le premier chapitre, nous présentons le cadre général de
l'apprentissage à partir d'exemples : les fondements théoriques,
la problématique, et les problèmes liés à l'estimation de la
qualité de la procédure de classification produite par le système.
Dans le second chapitre, nous présentons les arbres de décision et
deux algorithmes d'apprentissage basés sur les arbres de décision
: CART développé par Breiman et al. [BFOS84], C4.5
(amélioration de ID3) développé par Quinlan [Qui93]. Dans
le troisième chapitre, nous présentons les algorithmes
d'apprentissage pour les réseaux de neurones de type perceptron et
de type multicouches. Le quatrième chapitre est constitué
d'exercices simples qui permettent de s'assurer une bonne
compréhension de ce cours. En guise de conclusion, nous donnons
des éléments de comparaison des deux approches présentées.
Enfin, nous tenons à recommander au lecteur de ces notes de cours
les deux ouvrages suivants : tout d'abord, un ouvrage remarquable
en tous points sur l'apprentissage automatique écrit par Tom
Mitchell [Mit97] ainsi qu'un petit livre sur le Data
mining, écrit par Peter Adriaans et Dolf Zantinge, qui présente de
façon claire et synthétique le processus d'extraction
d'information dans les bases de données [AZ96].