Complexité de l’algorithme d’apprentissage

Complexité de l’algorithme d’apprentissage

Classification bi-classe et multi-classes

La classification bi-classe
La classification bi-classe correspond au filtrage. C’est une problématique pour laquelle le système de classification répond à la question : « Le texte appartient-il à la catégorie C ou non (i.e. ou à sa catégorie complémentaire ØC ? » (Par exemple, un document est il autorisé aux enfants ou non).
Cependant quand il s’agit d’effectuer une classification multi-classe qui permet de transmettre le document vers le ou les catégories(s) le(s) plus approprié(s), on parle alors de routage. Cette classification muti-classes, selon le cas, peut être disjointes ou non.

La classification multi-classes disjointes
La classification multi-classes disjointes est le contexte de classification en un nombre de classes supérieur à un et pour lequel un texte est attribué à une et une seule classe. Un système de classification multi-classes disjointes répond à la question « A quelle classe (au singulier) appartient le document ? ».

La classification multi-classes
Dans un système de classification multi-classes, on peut associer un texte à une ou plusieurs classes voire à aucune classe. Le système répond donc à la question : « A quelles classes (au pluriel) appartient le document ? ». C’est le cas le plus général de la classification. Il correspond par exemple à la problématique de classification du corpus Reuters étudié ici dans ce mémoire.

Catégorisation déterministe et floue

Catégorisation déterministe
Le but des classifications précédentes est d’avoir une réponse définitive pour chaque texte (oui ou non, le texte T appartient à la catégorie C) ; qu’on peut qualifier par classification déterministe. Plusieurs fonctions de classement sont utilisées, parmi lesquelles : les règles de décisions, les arbres de décision, SVM.

 Catégorisation floue ou le ranking
Contrairement aux cas précédents, on peut également souhaiter dans certains cas d’avoir simplement une évaluation des classes les plus adéquates -dans l’ordre- pour y classer le texte. Ce qu’on peut appeler par classification floue ou ranking.
Ce type de classification va permettre à l’utilisateur d’être plus indulgent si le texte est « proche » du thème que si le texte n’a absolument rien à voir avec celui-ci dans le cas ou ceذ dernier est incorrectement attribué à la classe.
Le ranking est une problématique de classification dans laquelle le système, au lieu d’associer un texte à une classe catégoriquement, il ordonne les classes par ordre de pertinence pour un texte donné.
Les méthodes qui évaluent une distance d’un texte à une catégorie permettent facilement ce type de classement de même pour les approches qui estiment des probabilités d’appartenance d’un texte à une classe.
Ludovic DENOYER dans (Denoyer, 2004) donne quelques exemples d’applications dans lesquelles ce système de classification est sollicité :
– Le ranking de pages Web pour une thématique définie par un internaute.
– Le filtrage avec un rajustement de seuil de tolérance, le seuil étant ajusté par rapport aux scores de ranking.
– Proposer à un utilisateur un classement d’experts compétents pour évaluer un projet.
Dans ce cas spécifique, une fonction de score est définie de la manière suivante :
SCORE : D×C [0,1]
Cette fonction nous renseigne sur le degré d’appartenance d’un texte à une classe donnée. Ainsi, plus SCORE(d,c) est proche de 1, plus le document d est proche à être attribué à la classe c et inversement, plus cette valeur est proche de 0, plus le document est loin d’être attribué à la classe. Le calcul de cette fonction de score nous permet alors d’organiser les classes dans l’ordre pour y classer le texte et donc de savoir par exemple quelle est la classe la plus probable à être sélectionnée par rapport aux autres.
Pratiquement, tous les algorithmes de classification calculent un score entre un texte et une classe. C’est le cas de toutes les approches probabilistes, particulièrement le classifieur Naïve Bayes. Toutefois, ces systèmes peuvent être aussi utilisés pour la classification déterministe.
Dans ce cas, il est fondamental d’adopter une stratégie transformant la fonction de score en une fonction de décision. Pour cela, la stratégie habituelle consiste à utiliser un seuil LC tel que :
si SCORE (d, c) > Lc alors D (d,c) = vrai
sinon D (d,c) = faux

Objectifs et intérêts

Les intérêts des méthodes de classification sont multiples, il peut s’agir d’améliorer les performances des moteurs de recherche documentaire ou aussi classer les documents en fonction de leurs références communes à d’autres documents pour faire apparaître les liens qui les unissent.
Nous pouvons citer six applications typiques qui sont :

• Le classement automatique de différents communiqués de presse, ou messages sur des forums en différentes matières (« Les actualités de la région », « la bourse »,« culture », etc..), (Exemple : Une boite propose un système de tri d’informations dans des flots de dépêches d’agence de presse AFP ou Reuters etc.. ou pages web. Chaque matin les nouvelles importantes sont faxées à différentes entreprises).
• Indexation automatique sur des catégories d’index de bibliothèques : aide à la classification thématique des différentes rédactions dans une bibliothèque.
• La gestion de bases documentaires (mémoire d’entreprise). Ce système peut être utilisé pour présenter l’information à l’utilisateur selon des catégories thématiques, ce qui facilite la navigation.
• Sauvegarde automatique de fichiers dans des répertoires.
• Les filtres internet en général, et en particulier les filtres anti-spams.
• Le classement automatique des emails, et particulièrement la redirection automatique de courriers des clients et fournisseurs en fonction de leur contenu vers les personnes compétentes dans une entreprise (Service commercial, livraison, service après vente, approvisionnements, etc..) ou vers des répertoires prédéfinis dans un outil de  messagerie, ou encore le tri de courriers électroniques dans différentes boîtes aux lettres personnelles et possibilité d’envoi de réponses automatiques.

Classification de textes et Text Mining

Le Text Mining est une technique permettant d’automatiser le traitement de gros volumes de contenus texte pour en extraire les principales tendances et répertorier de manière statistique les différents sujets évoqués ainsi découvrir des connaissances et des relations à partir des documents disponibles.
L’outil de Text Mining va générer de l’information sur le contenu du document. Cette information n’était pas présente, ou implicite, dans le document sous sa forme initiale, elle va être rajoutée, et donc enrichir le document. Les besoins en Text Mining peuvent être :
– Recherche d’information
– Correction orthographique/grammaticale
– Traduction automatique
– Résumé automatique
– Question/réponse (interfaces en langage naturel)
– La veille technologique
Et notamment
– La Classification automatique des documents
Toutes ces applications sont étroitement liées.

Classification de textes et Recherche d’informations

Dans la section suivante, nous allons rappeler les définitions de la recherche d’informations et la catégorisation de textes et essayer de positionner l’un par rapport à l’autre.
– La recherche d’informations (RI), aussi appelée recherche documentaire (RD), est la problématique la plus ancienne de ce domaine, elle consiste à trouver, dans une importante base de documents, les documents pertinents correspondant à des requêtes qui peuvent être de différentes natures (liste de mots clefs, langage naturel, langage spécifique comme le SQL par
exemple etc.).
La RI correspond à la tâche classique d’interrogation par des requêtes, aujourd’hui démocratisée par le Web avec des moteurs tels que Google ou Altavista ou encore la recherche informatisée de documents dans de sources bibliothécaires. Beaucoup de modèles ont été développés et continuent aujourd’hui de l’être, ces modèles peuvent être ensemblistes, algébriques, statistiques (Miller & all, 1999).
La recherche d’informations est généralement effectuée en indexant préalablement tous les documents de la base selon les mots qu’ils contiennent ; la recherche consiste à trouver, le plus rapidement possible, les documents ayant des mots communs avec la requête de l’utilisateur.
– La catégorisation de textes, consiste à trouver dans un flux de documents, ceux qui sont relatifs à un sujet défini par avance. L’une des applications consiste à fournir à un utilisateur, en temps réel, toutes les informations importantes pour l’exercice de son métier. Dans ce cas, l’utilisateur n’exprime pas son intérêt par une requête, mais par un ensemble de documents pertinents. Cet ensemble de documents pertinents définit ce que l’on appelle, un thème ou une catégorie.
La recherche d’information se différencie de la classification ou la catégorisation par le très grand nombre de réponses possibles, qui peut être infini. L’application classique serait la réponse d’un moteur de recherche ou d’intelligence artificielle à une demande. La distinction entre ces deux disciplines peut être simplifiée de la manière suivante : dans le premier cas, la base de documents est fixe et l’interrogation est variable, alors que, dans le deuxième cas, la source de documents est variable et l’interrogation est fixe.
Dans la pratique, la catégorisation de textes bénéficie de deux avantages par rapport à la recherche d’information : la stabilité dans le temps de la classe sélectionnée et la quantité réduite de documents à traiter dans le temps. La stabilité de la classe laisse le temps de construire des modèles performants permettant de rechercher la façon dont l’information est
codée dans un texte. Le fait de traiter les textes un à un, au lieu de s’attaquer à une base importante de textes, est moins pénalisante pour un système moins performant, et rend possible l’utilisation de modèles plus complexes.
SALTON recommandait, à la fin des années 60, le regroupement des documents des corpus pour permettre une recherche d’information plus rapide en ne calculant plus les distances entre la requête et chaque document mais seulement entre la requête et chaque classe : « Clearly in practice it is not possible to match each analysed document with each analysed search request because the time consumed by such operation would be excessive » (Salton,1968).
Une autre étude menée par (Bellot, 2002) montre que la classification automatique permet d’améliorer l’efficacité des systèmes de recherche. Un système de recherche documentaire, comme on a vu précédemment, donne, en réponse à une requête, une liste de documents. La liste des documents trouvés est souvent si longue que les utilisateurs ne peuvent l’examiner entièrement et laissent de côté certains documents pertinents mal classés. L’étude a démontré qu’une classification automatique des seuls documents retrouvés permet d’améliorer la qualité de la recherche documentaire.

Table des matières

Introduction
1- Problématique et contexte du mémoire
2- Contribution
3- Organisation du mémoire
Chapitre 1 – Classification automatique de textes
1.1- Introduction
1.2- Pourquoi automatiser la classification ?
1.3- Historique de la Catégorisation de textes
1.4- Les systèmes de classification et vocabulaire utilisé
1.4.1- Catégorisation (Supervisé)
1.4.2- Clustering (Non supervisé)
1.5- Définition de la Catégorisation de textes
1.6- La notion de classe pour les systèmes de classification
1.7- Les différents contextes de classification
1.7.1- Classification bi-classe et multi-classes
1.7.1.1- La classification bi-classe
1.7.1.2- La classification multi-classes disjointes
1.7.1.3- La classification multi-classes
1.7.2- Catégorisation déterministe et floue
1.7.2.1- Catégorisation déterministe
1.7.2.2- Catégorisation floue ou le ranking
1.8- Objectifs et intérêts
1.9- Classification de textes et Text Mining
1.10- Classification de textes et Recherche d’informations
1.11- Démarche à suivre pour la catégorisation de textes .
1.12- Problèmes de la catégorisation de textes
1.12.1- Redondance(Synonymie)
1.12.2- Polysémie (Ambiguïté)
1.12.3- L’homographie
1.12.4- La graphie
1.12.5- Les variations morphologiques
1.12.6- Les mots composés
Table des matières
1.12.7- Présence-Absence de termes
1.12.8- Complexité de l’algorithme d’apprentissage
1.12.9- Sur-apprentissage
1.12.10- Subjectivité de la décision
1.13- Conclusion
Chapitre 2 – Codage des textes : Etat de l’art
2.1- Introduction
2.2- Le texte
2.3- Prétraitements
2.3.1- La segmentation
2.3.2- Suppression des mots fréquents ou élimination des ”Mots Outils”
2.3.3- Suppression des mots rares
2.3.4- Le traitement morphologique
2.3.5- Le traitement syntaxique
2.3.6- Le traitement sémantique
2.4- Définition de descripteurs
2.4.1- Représentation en « sac de mots » « bag of words »
2.4.2- Représentation des textes par des collocations
2.4.3- Représentation des textes par des phrases
2.4.4- Représentation des textes avec des racines lexicales (stemming)
2.4.5- Représentation des textes avec des lemmes (lemmatisation)
2.4.6- Représentation des textes avec la méthode des n-grammes
2.4.7- Représentation des textes par des combinaisons de termes
2.4.8- Représentation des textes basée sur les concepts
2.5- Sélection de descripteurs
2.5.1- Besoin de la sélection de descripteurs
2.5.2- Le nombre de descripteurs conservés
2.5.3- Les méthodes de sélection de descripteurs
2.5.3.1- Principales méthodes
2.5.3.2- Inconvénient commun (Association de termes)
2.5.3.2- Autres approches
2.5.4- Sélection des termes par rapport la classe ou tout le corpus
2.6- Pondération ou calcul de poids
2.6.1- Le modèle vectoriel
2.6.1.1- Représentation binaire
2.6.1.2- Représentation fréquentielle
2.6.1.3- Représentation fréquentielle normalisée
2.6.1.4- Vecteur TF-IDF
2.6.2- Le modèle probabiliste
2.6.3- Représentation séquentielle
2.7- Conclusion
Chapitre 3 – Approches de classification : Etat de l’art
3.1- Introduction
3.1.1- L’apprentissage automatique
3.1.2- L’apprentissage supervisé
3.1.3- La catégorisation est un problème de classification supervisée
3.1.4- Comment classer ?
3.2- Différents modèles de classifieurs
3.2.1- Machines à Vecteurs Support – SVM
3.2.1.1- Présentation de l’approche
3.2.1.2- Critiques de l’approche
3.2.2- Rocchio
3.2.2.1- Présentation de l’approche
3.2.2.2- Critiques de l’approche
3.2.3- Méthode du centroïde
3.2.3.1- Présentation de l’approche
3.2.3.2- Critiques de l’approche
3.2.4- K plus proches voisins – kPPV
3.2.4.1- Présentation de l’approche
3.2.4.2- Critiques de l’approche
3.2.5- Arbres de décision
3.2.5.1- Présentation de l’approche
3.2.5.2- Architecture d’un arbre de décision
3.2.5.3- Algorithme de construction
3.2.5.4- L’entropie et le gain d’information
3.2.5.5- Évaluation des arbres de décision
3.2.6- Les approches neuronales
3.2.6.1- Présentation de l’approche
3.2.6.2- Le perceptron
3.2.6.3- Autres réseaux à couches
3.2.6.4- Classification à base des réseaux de neurones
3.2.6.5- Critiques de l’approche
3.2.7- Naïve Bayes
3.2.7.1- Description de l’approche
3.2.7.2- Critiques de l’approche
3.2.8- Les méthodes mixtes et Boosting
3.2.8.1- Présentation de l’approche
3.2.8.2- Evaluation de l’approche
3.2.9- Autres méthodes
3.3- Mesures de similarité et formules pour calcul de distance
3.3.1- Calcul de distance
3.3.1.1- Définition de la distance
3.3.1.2- Variantes de distance
3.3.2- Mesures de similarité
3.3.2.1- Cosinus
3.3.2.2- Kullback&Liebler (la mesure d’entropie relative)
3.3.2.3- Synthèse sur les mesures de similarité
3.4- Conclusion
Chapitre 4 – Evaluation des classifieurs
4.1- Introduction
4.2- Méthodologies de comparaison de classifieurs
4.2.1- Différentes approches sur le même corpus
4.2.1.1- Même corpus avec des découpages différents
4.2.1.2- Les différentes techniques de représentation de textes
4.2.1.3- Les différentes mesures utilisées pour l’évaluation
4.2.2- Différentes approches par le même auteur
4.2.3- Difficultés approuvées pour juger les capacités d’une méthode
4.2.4- TREC
4.3- Mesures de performance de classifieurs
4.3.1- Classification déterministe à deux classes
4.3.1.1- Matrice de contingence
4.3.1.2- Précision et Rappel
4.3.1.3- Bruit et silence
4.3.1.4- Taux de succès et taux d’erreur
4.3.1.5- Taux de chute et la spécificité
4.3.1.6- L’overlap et la généralité
4.3.1.7- F-measure
4.3.2- Classification déterministe à plusieurs classes
4.3.2.1- Matrice de contingence globale
4.3.2.2- La micro-moyenne
4.3.2.3- La macro-moyenne
4.3.2.4- Une mesure issue de TREC : l’utilité
4.3.3- Classification floue ou Ranking
4.4- Autres critères de comparaison de classifieurs
4.5- Conclusion
Chapitre 5 – Les Systèmes Multi-Agents
5.1- Introduction
5.1.1- Historique
5.1.2- Pourquoi distribuer l’intelligence?
5.1.3- Qu’est que l’intelligence artificielle distribuée (IAD) ?
5.1.4- Le monde est ouvert
5.1.5- Domaines d’intérêts
5.2- Concepts de base
5.2.1- Agent
5.2.1.1- Définitions
5.2.1.2- Des Objets aux Agents
5.2.2- Système Multi-Agents
5.2.2.1- Qu’est-ce qu’un système multi-agents ?
5.2.2.2- Utilité des systèmes multi-agents
5.2.2.3- Un premier exemple
5.2.2.4- Vue intuitive d’un Agent dans un SMA
5.2.2.5- Variables globales et locales et les SMA
5.2.2.6- Niveaux d’organisation
5.2.3- Propriétés d’un agent intelligent
5.2.3.1- Autonomie
5.2.3.2- Réactivité
5.2.3.3- Proactivité
5.2.3.4- Adaptabilité
5.2.3.5- Sociabilité
5.2.3.6- Apprentissage
5.2.3.7- Sécurité
5.2.4- Propriétés des systèmes multi-agents
5.2.4.1- Interactions entre agents
5.2.4.2- Coopération
5.2.4.3- Coordination
5.2.4.4- La compétition
5.2.4.5- Délégation
5.2.4.6- Communication
5.2.4.7- Une Recherche de Compromis
5.3- Les différents modèles d’agents (Architecture)
5.3.1- Les agents réactifs
5.3.1.1- Agents à réflexes simples
5.3.1.2- Agents conservant une trace du monde
5.3.2- Les agents délibératifs
5.3.2.1- Agents ayant des buts
5.3.2.2- Agents utilisant une fonction d’utilité
5.3.2.3- Le modèle BDI
5.3.3- Les agents hybrides
5.4- Apprentissage des agents et des SMA
5.4.1- Apprentissage des Agents
5.4.1.1- Définitions et Différentes formes d’apprentissage
5.4.1.2- Apprentissage des agents
5.4.1.2- L’apprentissage par renforcement
5.4.2- Apprentissage des SMA
5.5- Méthodologies de conception d’un SMA
5.5.1- Problématique
5.5.2- Méthodologie
5.5.2.1- Phase d’analyse
5.5.2.2- Phase de conception
5.5.2.3- Les étapes de réalisation d’un SMA
5.5.3- Plates-formes de développement
5.6- Conclusion
Chapitre 6 – Classification Automatique des textes Approche Orientée Agent
6.1- Introduction
6.2- Description générale de l’approche
6.3- Motivations
6.3.1- Codage en n-grammes
6.3.2- Pondération des termes
6.3.3- Naïve Bayes
6.3.3.1- Probabilité conditionnelle
6.3.3.2- Théorème de Bayes
6.3.3.3- Inférence bayésienne
6.3.3.4- La classification naïve bayesienne
6.3.3.5- Maximum A Posteriori (MAP) et Maximum de vraisemblance (ML)
6.3.3.6- Le modèle multivarié de Bernoulli
6.3.3.7- Le modèle multinomial
6.3.3.8- Description de l’algorithme
6.3.3.8- Avantages de la méthode adoptée (Naïve Bayes Classifier)
6.3.4- Mesures de performances utilisées pour l’évaluation
6.3.5- Les Systèmes Multi-Agents
6.4- Base de texte utilisée pour l’évaluation
6.4.1- Présentation générale du corpus Reuters
6.4.2- Historique
6.4.3- Evolution du corpus
6.4.4- Définition des catégories du corpus Reuters-21578-ApteMod
6.4.5- Reuters21578-ModeApté[10]
6.5- Applications opérationnelles
6.5.1- Environnement de développement
6.5.2- Approche non distribuée
6.5.2.1- Démarche à suivre
6.5.2.2- Résultats expérimentaux
6.5.3- Approche distribuée
6.5.3.1- Démarche à suivre
6.5.3.2- Résultats expérimentaux
6.5.4- Comparaison des résultats
6.5.4.1- Comparaison des résultats obtenus aves différentes valeurs de N (N-gram)
6.5.4.2- Comparaison des résultats d’autres algorithmes
6.5.4.3- Comparaison des approches Mono et Multi-Agents
6.5.4.4- Comparaison des approches non distribuées avec notre approche SMA
6.6- Discussion
6.6.1- L’influence du N dans les résultats de l’approche
6.6.2- L’influence du nombre d’agents dans les résultats de classification
6.6.3- L’apport de la distribution de classification
6.7- Conclusion
Conclusion générale
1- Conclusion générale
2- Perspectives
Annexes
Annexe 1 : La conférence TREC
Annexe 2 : Algorithme MNB (Microsoft Naive Bayes)
Annexe 2 : Ditto-The donkey
Bibliographie

Télécharger le rapport complet