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 d'exemples. 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. Nous allons arbitrairement les séparer en deux groupes. Les méthodes de nature probabiliste ou statistique et les méthodes issues de l'intelligence artificielle. 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éduree 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 ``boite 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.
Les applications sont nombreuses et concernent des domaines très variés. 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 chaines 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 par tout utilisateur dans l'entreprise. Les outils que nous présentons font partie de ce que l'on appelle les outils de ``datamining'' ou ``fouille de données''. Ce terme désigne (dans une définition large) l'extraction de connaissance à partir de données provenant de sources diverses et hétérogènes (documents texte, hypertexte, fichiers structurés, bases de données, ...). Pour notre part, nous nous limitons à l'extraction de connaissance à partir de fichiers structurés. Il s'agira d'extraire, par exemple, un profil client des informations mémorisées le concernant. Ces outils comencent à être disponibles sur le marché. Ils sont, pour la plupart, basés sur des techniques d'arbres de décision ou de réseaux de neurones, techniques qui seront présentées dans ce cours. Citons, parmi d'autres, quelques applications et leur domaine :
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 [1], C4.5 (amélioration de ID3) développé par Quinlan [13]. 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.