Soutenance mémoire
Télécharger le fichier pdf d’un mémoire de fin d’études
Le site web du réseau de surveillance sentinelle
Grâce à un site web mis en place en 2014, ces centres hospitaliers peuvent effectuer journa-lièrement un envoi de données vers une base de données de l’IPM. Ce site web a été développé au sein de l’IPM avec le framework web python appelé « Django ». Il a été conçu identique-ment à la version physique des registres qui sont détenus par les hôpitaux. Ainsi, ce site permet de recueillir des informations concernant les personnes admis dans les hôpitaux du réseau de surveillance. Parmi ces informations figurent les motifs et les diagnostics d’entrées des patients qui sont exprimés en texte libre.
Figure 1.1 – Page d’accueil du site web du réseau de surveillance sentinelle
Figure 1.2 – Page d’enregistrement des informations concernant les patients
La classification automatique de textes
Généralités
La classification automatique de textes (CT) est l’attribution automatique d’une ou plusieurs classes (catégories) prédéfinies ou non à un texte (document). Elle est une branche du Text Mi-ning provenant de la combinaison de l’Apprentissage Automatique (AA) et de la Recherche d’Information (RI). La CT est un domaine qui attire l’attention de nombreux chercheurs parce que la quantité des documents au format numérique ne cesse de s’accroître. De ce fait, l’explo-ration des informations qu’ils renferment devient une tâche très pénible et fastidieuse sans une technique de classification optimale.
Les algorithmes utilisés en CT sont appelés classifieurs. Ce sont eux qui vont déterminer les classes dans lesquelles les documents appartiennent. Mathématiquement, soient C un ensemble de classes et D un ensemble de documents, un classifieur est une fonction f telle que :
Il existe deux approches de classification automatique de textes. D’une part, il y a la classi-fication supervisée et d’autre part la classification non supervisée. La différence entre ces deux approches réside dans la définition des classes. Pour la classificaton supervisée, les classes sont définies préalablement par des experts humains. Quant à la classification non supervisée, ce sont les classifieurs qui déterminent les classes.
Le processus de classification de textes
Une classification de textes se fait généralement en deux phases :
la phase d’apprentissage : elle a pour objectif de donner des informations au classifieur afin que ce dernier puisse établir des règles pour classifier des documents. Au cours de cette phase, un ensemble de documents appelé corpus d’apprentissage va être utilisé pour avoir ces informations. la phase de classification : c’est au cours de cette phase que le classifieur va effectuer la classication des documents en se servant des règles qu’il avait établies.
Indexation des documents
L’indexation des documents consiste à extraire les termes ou les composantes textuelles qui reflètent au mieux leurs contenus et à évaluer l’importance de l’information qu’elles contiennent. Ces composantes textuelles sont appelées descripteurs et elles peuvent être des caractères, des mots, des phrases, des paragraphes . L’indexation d’un document se fait en deux étapes : la sélection des descripteurs : un procédé par élimination des éléments dont les informa-tions qu’ils renferment ne permettent pas de discriminer le document. Ces éléments sont appelés stopwords. Une liste de ces derniers est élaborée préalablement, ainsi les éléments qui n’y figurent pas sont retenus pour représenter le document la pondération des descripteurs : assignation d’une quantité numérique, appelée poids, à chaque descripteur pour mesurer l’importance de l’information qu’il peut apporter concer-nant le document dans lequel il apparaît.
Systèmes de pondérations des termes
La RI offre plusieurs techniques pour définir le poids d’un terme. Quelques-unes de ces techniques sont décrites ci-dessous :
Binary weighting(Bw) : c’est la plus simple façon de définir le poids d’un terme. Pour un document d, le poids Bw(i; d) d’un terme i est égal à 1 s’il apparaît dans d sinon 0.
Term frequency(Tf ) : ce système de pondération est une fonction de l’occurrence des termes dans les documents. Soit un document d, la plus simple manière de définir le poids du terme i relativement à d avec ce système de pondération est : T f(i; d) = Occ(i; d) (1.1) où Occ(i; d) désigne le nombre d’occurrence du terme i dans d.
Un terme est considéré comme important pour un document s’il y apparaît plusieurs fois. Term frequency – Inverse document frequency (Tf.Idf ) [Salton and Buckley, 1988] : cette technique définit le poids d’un terme dans un document selon son apparition dans ce dernier et aussi dans tous les documents du corpus d’apprentissage. Etant donné un document d, le poids Tf.Idf d’un terme i peut se calculer par la formule ci-dessous : T f:Idf(i; d) = Occ(i; d) log10 N (1.2) ni où N et ni désigne respectivement le nombre de document dans le corpus d’apprentissage et le nombre de documents dans lesquels le terme i apparaît. Plus la valeur de T f:Idf(i; d) est élevée, plus le terme i a beaucoup d’importance dans le document d.
Likey [Paukkeri and Honkela, 2010] : soit d un document, le poids d’un terme i avec ce système de pondération est donné par la formule suivante :
likey(i; d) = Occ(i; d) (1.3)
Occcorpus(i)
où Occcorpus(i) est le nombre d’occurrences du terme i dans le corpus d’apprentissage. Plus cette valeur est faible, plus le terme i offre une information importante à propos du document d.
Représentation des documents
Les classifieurs ne sont pas capables de réaliser directement des traitements sur des chaînes de caractères. Les documents nécessitent d’être représentés sous une autre forme adaptée aux classifieurs. La manière la plus utilisée dans la littérature est la représentation vectorielle [Salton, 1971]. Elle consiste à projeter les documents dans un espace vectoriel dont la dimen-sion est égale au nombre de descripteurs. Chacun de ces derniers va correspondre à un vecteur de base de l’espace vectoriel. De ce fait, un document di va être transformé en un vecteur (wdi;t1 ; wdi;t2 ; :::; wdi;tv )T où wdi;tj et v désignent respectivement le poids du descritpeur tj dans di et le cardinal de l’ensemble formé par tous les descripteurs obtenus après l’indexation des documents du corpus d’apprentissage.
Les classifieurs
Actuellement, il existe un bon nombre de classifieurs grâce à la multiplication des recherches concernant la classification automatique de textes. Il est à noter que la plupart des classifieurs sont issus de l’AA avant d’être adaptés à la classification de textes. Les classifieurs font tou-jours l’objet d’une perpétuelle amélioration puisque la quantité de données textuelles ne cesse d’augmenter mais aussi pour avoir des meilleurs résultats. À l’origine, certains d’entre eux a été fait pour une classification binaire, c’est à dire dans le cas où le nombre de classes est seulement deux. Cependant grâce aux diverses recherches, ces derniers peuvent être appliqués dans le cas où le nombre de classes est supérieur à deux, c’est à dire pour une classification multi-classe. Les classifieurs décrits dans les paragraphes suivants figurent parmi les plus utilisés dans la littérature :
Le classifieur k-nearest neighbor (knn) :
Le classifieur knn est un des premiers algorithmes utilisés pour la reconnaissance de forme. Cet algorithme est aussi utilisé dans d’autres domaines. En effet, il a été appliqué pour la détérmination des métastases ganglionnaires dans le cancer gastrique [Li et al., 2012], pour la prédiction des cours boursiers [Imandous and Bolandraftar, 2013]. Ce classifieur a été utilisé pour la première fois en CT en vue d’une classification des articles de journaux [Masand et al., 1992]. Il peut être employé pour une clasification binaire ainsi que pour une classification multi-classe. Son principe est de sélectionner les k documents du corpus d’apprentissage qui sont les plus similaires au document à classifier. Ce dernier aura comme classe celle qui est la plus représentée par les k documents sélectionnés.
Le classifieur naive Bayes (NB) :
Le classifeur NB se base sur le théorème de Bayes. Il peut être utilisé dans le cas d’une classification binaire mais aussi dans le cas d’une classification multi-classe. Ce classifieur est simple à implémenter et aussi efficace dans ses applications telle que la détection des courriers électroniques indésirables [Androutsopoulos et al., 2000]. Cet algorithme a été aussi utilisé dans le domaine de la médecine pour la classification de données médicales [Al-Aidaroos et al., 2012]. L’idée principale de ce classifieur est de déterminer la proba-bilité d’appartenance du nouveau document à une classe en se servant du théorème de Bayes et en supposant que les termes sont indépendants deux à deux. La classe qui sera attribuée au nouveau document est celle qui aurra la plus forte probabilité.
Le classifieur support vector machine (SVM) :
Le classifieur SVM a été conçu à l’origine pour une classification binaire mais des tech-niques ont été développées afin de l’utiliser dans le cas d’une classification multi-classe [Weston and Watkins, 1998]. Plusieurs problèmes ont fait l’objet de champ d’application de ce classifieur comme la prédiction du cancer du sein [Huang et al., 2017], la classi-fication d’images [Vanitha and Venmathi, 2011], la détection des contenus racistes sur l’internet [Vinot et al., 2003]. Cet algorithme est classé parmi les plus performants en CT [Joachims, 1998], il s’appuie sur une interprétation géométrique simple. Son principe est de trouver un hyperplan séparant au mieux les documents selon leurs classes. Cela en garantissant que la marge entre cet hyperplan et les documents qui sont les plus proches de lui soit la plus grande possible. Le nouveau document aurra la même classe que les documents qui se trouvent dans la même région que lui.
L’évaluation de la performance des classifieurs
En général, la performance d’un classifieur est mesurée par son efficacité à prendre des bonnes décisions de classification. Pour cela, il faut faire des tests sur un ensemble de docu-ments qui sont déjà classifiés par des experts humains. Cet ensemble de document est appelé corpus de test. Actuellement,il n’existe pas encore d’indicateur universel pour affirmer qu’un tel classifieur est plus ou moins performant que les autres. En effet, la qualité du résultat fourni par un classifieur est relative au corpus utilisé pour l’évaluation , de plus cela dépend aussi de son implémentation et même des juges humains. Toutefois, plusieurs mesures de performance existent et elles se basent sur la matrice de confusion. Les mesures qui sont les plus utilisées dans la littérature sont définies dans les sections suivantes.
La matrice de confusion
La matrice de confusion est la base des mesures utilisées pour l’évaluation de la performance d’un classifieur. À chaque classe ci representée dans le corpus de test, une matrice de confusion est définie comme suit :
Table 1.1 – Matrice de confusion d’une classe ci T Pi(True Positive) désigne le nombre de documents du corpus de test classifiés correcte-ment dans la classe ci par le classifieur F Pi(False Positive) désigne le nombre de documents du corpus de test classifiés à tort dans ci par le classifieur F Ni(False Negative) désigne le nombre de documents du corpus de test appartenant à la classe ci mais qui ne sont pas convenablement classifiés par le classifieur T Ni(True Negative) désigne le nombre de documents du corpus de test qui n’ont pas ci pour classe mais que le classifieur a identifié comme tel.
Le rappel et la précision
Soient dx un document du corpus d’apprentissage et ci une classe qui y est représentée. La précision (ci) est la probabilité que si dx est classifié dans la classe ci, cette décision est correcte [Sebastiani, 2001]. Quant au rappel (ci), il est défini comme la probabilité que si le document dx doit être classifié dans la classe ci, cette décision est prise[Sebastiani, 2001]. En d’autres termes, le rappel (ci) et la précision (ci) sont respectivement la proportion de documents correctement assignés à ci parmi tous les documents de classe ci et la proportion de documents attribués convenablement à ci parmi tous ceux qui ont été classifiés. Le rappel (ci) et la précision (ci) sont estimés à l’aide des formules suivantes [Sokolova and Lapalme, 2009] : Leurs valeurs varient entre 0 et 1.
Le rappel macro-moyenne et la précision macro-moyenne
Le rappel macro-moyenne M et la précision macro-moyenne M correspondent respective-ment aux moyennes arithmétiques des rappels et des précisions des classes .
Définitions
Définition 1.5.1. Un algorithme est une suite d’instructions ayant pour objet de résoudre un problème donné.
À partir d’une ou plusieurs données qui lui sont fournies initialement, les instructions qui composent l’algorithme sont exécutées afin d’obtenir un résultat. Les données initiales sont appelées données d’entrée et le résultat est dit donnée de sortie.
Définition 1.5.2. La complexité ou le coût d’un algorithme est le nombre d’opérations élémen-taires nécessaires qu’il doit faire en fonction la taille des données d’entrée pour produire un résultat.
Pour évaluer la complexité d’un algorithme, deux éléments sont à considérés : le stockage des données et le temps de calcul. Durant l’exécution d’un algorithme, il y a des données qui ont besoin d’être stockées. Compte tenu de la capacité des ordinateurs actuels, le stockage des données peut ne pas être considérée pour l’évaluation de la complexité de l’algorithme.
Dans le cadre de ce travail, seul le temps de calcul sera considéré pour l’évaluation de la complexité des algorithmes.
Le temps de calcul
Le temps de calcul d’un algorithme dépend en général du nombre d’opérations fondamentales ou élémentaires et de la taille des données d’entrée.
La taille des données d’entrée
Selon la nature du problème, les données d’entrée peuvent être des nombres, des mots, des tableaux, des matrices, des polynômes …. Généralement, ce sont les dimensions significatives qui sont définies comme taille des données d’entrée.
Exemple 1.6.1. Dans le cas d’une addition de deux matrices, la taille des données est fonction du nombre de colonnes et de lignes. Pour la recherche d’un caractère dans un mot, c’est la longueur du mot qui sera choisie comme taille de la données d’entrée.
Les opérations élémentaires
Le fait qu’une opération soit considérée comme élémentaire dépend de la nature du problème à résoudre. Il est supposé que la durée de l’exécution de chaque opération élémentaire est la même. En général, les opérations élémentaires sont la multiplication de deux nombres, l’addition de deux nombres, la division de deux nombres, l’affection de donnée, la lecture de donnée et la comparaison de deux nombres. Dès fois, d’autres opérations sont jugées comme élémentaires selon le problème.
La détermination de la complexité d’un algorithme revient alors à trouver le nombres d’opé-ration élémentaires. Parfois, trouver le nombre exacte d’opérations élémentaires est très diffi-ciles. De ce fait, il est préférable de déterminer son comportement asymptotique dans le pire des cas (c’est à dire le nombre d’opérations qui peuvent être réalisées par l’algorithme).
La notation O et terminologie
Définition 1.7.1. Soient f et g deux fonctions de N vers R+. f(n) = O(g(n)) ou f(n) est O(g(n)) lorsqu’il existe un entier n0 2 N et une constante réel strictement positive c telles que : f(n) c g(n) pour tout n supérieur ou égale à n0.
Exemple 1.7.1. La fonction f : n 2 N ! R+ définie par f(n) = 2n2 2 est en O(n2). En effet pour n 1, 4n2 f(n) = 4n2 2n2 2 = 2n2 2. Comme la fonction x ! x2 est croissante sur R+ et que N R+, n2 > 1. D’où 2n2 > 2 pour tout n > 0. Ce qui signifie que f(n) 4n2, lorsque n 1. Par définition, f(n) est en O(n2).
Si n 2 N désigne la taille de donnée d’un algorithme A, h étant une fonction positive de l’entier n et que le nombre d’opérations élémentaires de cet algorithme est en O(h(n)), la complexité de A est dit en O(h(n)). Le tableau 1.3 montre les différentes catégories de complexité des algorithmes.
|
Table des matières
Introduction
1 Généralités
1.1 Le réseau de surveillance sentinelle hospitalier
1.2 La classification statistique internationale des maladies et des problèmes de santé connexes
1.3 Le site web du réseau de surveillance sentinelle
1.4 La classification automatique de textes
1.4.1 Généralités
1.4.2 Le processus de classification de textes
1.4.3 Les classifieurs
1.4.4 L’évaluation de la performance des classifieurs
1.5 Définitions
1.6 Le temps de calcul
1.6.1 La taille des données d’entrée
1.6.2 Les opérations élémentaires
1.7 La notation O et terminologie
2 Matériels et méthodes
2.1 Présentation des outils d’implémentation
2.1.1 Le langage Python
2.1.2 Le framework Django
2.2 Le processus de codification des motifs d’hospitalisation
2.2.1 La substitution de mots
2.2.2 L’uniformisation de caractères
2.2.3 La vectorisation
2.2.4 La codification
2.3 Les classifieurs utilisés pour la codification des motifs d’hospitalisation
2.3.1 La codification avec le classifieur k-nearest neighbor
2.3.2 La codification avec le classifieur Naive Bayes
2.3.3 La codification avec Elasticsearch
3 Expérimentations et résultats
3.1 Les corpus de test
3.2 Les tests de performance
3.3 Résultats obtenus sans substitution de mots
3.4 Résultats obtenus avec substitution de mots
3.5 Codification des motifs d’hospitalisation mal orthographiés
3.6 Temps d’exécution
4 Discussion
Conclusion
A Les algorithmes : prodscal et puissance I
A.1 L’algorithme prodscal
A.2 L’algorithme puissance
B Implémentations des algorithmes avec Python III
Télécharger le rapport complet
