p AR HASSANE HILALI APPLICA TION DE LA L’EXTRACTION DES R AVRIL 2009 030110265 Premium By marwa7aa OenpanR 2È, 2015 | 157 pages UNIVERSITÉ DIJ QUÉBEC MÉMOIRE PRÉSENTÉ À L’UNIVERSITÉ DU QUÉBEC À TROIS-RIVIÈRES COMME EXIGENCE PARTIELLE DE LA MAÎTRISE EN MATHÉMATIQUES ET INFORMATIQUE APPLIQUÉES p g 57 LLE POUR AXIMALES Université du Québec à Trois-Rivières Service de la bibliothèque Avertissement L’auteur de ce mémoire ou de cette thèse a autorisé l’Université du Québec à Trois-Rivières à diffuser, à des fins non lucratives, une copie de son mémoire ou de sa thèse.
Cette diffusion n’entraîne pas une renonciation de la part de l’auteur à ses droits de propriété intellectuelle, Incluant le droit d’auteur, sur ce memolre ou cette thèse. Notamment, la reproduction ou la publication de classification qui existent, ainsi que les avantages et les inconvénients de chacune d’entre elles. Dans le deuxième chapitre, nous exposons les différentes caractéristiques des règles d’association et les étapes de leur extraction. Nous traitons dans le troisième chapitre d’ un cas particulier des règles d’association que l’on nomme les règles d’association maximales.
Le quatrième t le cinquième chapitre sont consacrés à la présentation du système développé ainsi qu ? l’ interprétation des différents résultats obtenus par l’analyse d’un ensemble de documents. En général, la chaîne de traitement de notre système se déroule en deux phases. La première partie consiste à faire la classification d’ un texte encodé en Unicode. Ensuite, nous utilisons les classes obtenues dans la première partie pour générer un type de règles d’association appelées les règles d’association maximales.
Remerciements Ce mémoire est le résultat d un long travail de trois années de echerche qui m’ ont permis d’exploiter et de découvrir le monde de la lecture et de l’analyse des textes assistés par ordinateur. La rédaction de ce travail de maîtrise n’aurait pas pu voir le jour sans l’ aide et la collaboration d’un grand nombre de personnes, chacun ayant apporté une aide précieuse ? sa finalisation . Tout d’abord, Je désire vivement remerCler M. Ismail Biskri, mon directeur de 2 OF répondre à toutes mes questions. n très grand merci à mes parents toujours présents, par leur soutien et leur encouragement, dans les moments difficiles de la réalisation de ce memoire. J’adresse également mes remerciements à mes meilleurs amis: Yousef Aichour, Zahra Lachgar et Ali Jouki, qui m’ont apporté leur soutien moral pendant ces années d’ études. un énorme remerciement pour mes deux frères adorés, Khalid et Mohammed, qui ont été toujours disponibles pour moi. Enfin, j’adresse mes sincères remerciements aux membres du jury. Je les remercie pour leur patience ainsi que pour leur lecture attentive de ce travail.
Table des matières Résumé „ — Remerciements — . Table des matières — — Liste des tableaux vii Liste des figures Chapitre 1 – Introduction 3 Classification . 5 2. 1 Les premières méthodes de classification 2. 2 Les méthodes de classification supervlsees 2. 2. 1 K plus proches volslns . 2. 2. 2 Les réseaux de neurones 2. 2. 3 Les arbres de décision — — — 2. 2. 4 Les algorithmes génétiques • . 2,2. 5 L’algorithme de NaiVe Bayes — — — . 2. 2. 6 Les machines à support de vecteurs (SVM) . . • 36 2. 3 Les méthodes de classifi cation non supervisées — 2. 3. 1 K-moyen 42 4 12 . 3 29 33 . 41 d’association . 3. 5. 1 Avantages — • 62 3. 5. 2 Inconvénients . Chapitre 4 – Les règles d’association Hierarchical Agglomeratlve Clustering(HAC) . 47 2. 3. 5 Les cartes auto organisatrices de Kohonen (SOM) 49 2. 3. 6 Réseaux de neurones ART, ARTIet Fuzzy 59 63 ART 51 Chapitre 3 – Les règles d’association . 57 3. 1 Introduction 3-2 Définitions . 58 3. 3 Les étapes d’extraction des règles d’association 3. 4 L’ algorithme Apriori . 60 3. 5 Avantages et inconvénients des règles maximales — . S OF d’association maximales 42. 1 Principes de bases des règles d’ association 64 4. Exemple d’ utilisation des règles d’association maximales — — 70 – Conclusion . — . 4. 4 Comptage des règles d’ association 44. 1 Algorithme 2 Chapitre 5 – Système développé 76 5. 1 Introduction — — 5. 2 Architecture du système développé . 5. 3 Fonctionnement du système développé Chapitre 6 – Expérimentations et résultats . Chapitre 7 108 …. 77 . 78 . 93 Bibliographie 111 116 VII Tableau 4. 1 Table des transactions Tableau 6. 1 Calcul du M-Support et de la M-Confiance pour X – 99 . 101 106 . 32 Risque 95 Tableau 6. 2 Calcul du M-Support et de la M-Confiance pour X – Hassan .
Tableau 6. 3 Calcul du M-Support et de la M-Confiance pour X – Informatique Tableau 6. 4 Calcul du M-Support et de la M-Confiance pour X – 104 Tableau 6. Calcul du M-Support et de la M-Confiance pour X – NJy1rl. Viii Figure 1 Distance euclidienne entre X et les deux classes cl et Figure 2. 2 Algorithmes des k plus proches voisins Figure 2. 3 Procédure de construction d’ un arbre de décision — . . Figure 2. 4 Algorithme ID3 . 26 24 Figure 2. 5 Fonctionnement des algorithmes génétiques Figure 2. 6 Calcul de la fréquence d’ un mot dans un ensemble de documents OF points — — • . … 37 Figure 2. Hyperplan optimal avec une marge maximale • 38 Figure 2. 9 Problème de discrimination à deux classes avec une séparatrice non linéaire . 39 Figure 2. 10 Problème de discrimination à deux classes avec une séparatrice linéaire — — — Figure 2. 11 L’ algorithme du K- moyen Figure 2. 12 Algorithme Single- 45 Figure 2. 13 L’algorithme des cartes auto organisatrices de Kohonen — — 50 Figure 3. 1 Algorithme Apriori . Figure 4. 1 Algorithme des règles d’ association maximales . — — . 74 79 Figure 5. 1 Architecture du système Figure 5. 2 Choix du type de segmentation d’ un texte — Figure 5. Propriétés des N- grams 80 Figure 5. 4 Option du lexique des classes 8 OF . 80 Figure 5. 4 Option du lexique des classes Figure 5. Analyse d’ un texte choisi par l’ utilisateur 82 Figure 5. 6 La matrice qui contient les résultats de la segmentation . . 82 Figure 5. 7 Choix d’ un type de nettoyage — — — Figure 5. 8 Nettoyage par fréquence totale Figure 5. 9 Nettoyage par fréquence relative — — . 84 81 . 83 85 Figure 5. 10 Enregistrement des N-grams en format XML . 85 Figure 5. 11 Construction des classes par MATL AB Figure 5. 12 Analyse et affichage des 91 Figure 5. 3 Enregistrement du M-Support et de la M-Confiance en .. 92 Chapitre 1 – Introduction Avec l’avènement de l’informatique et l’ augmentation du nombre e documents électroniques stockés sur des supports électroniques et sur le Web, Il intervention des outils d’analyse et de traitement automatique des textes est devenu plus que nécessaire, pour assister et aider le lecteur à explorer et à dégager des informations pertinentes, qui facilitent la compréhension rapide des cor u 9 OF explorer et à dégager des informations pertinentes, qui facilitent la compréhension rapide des corpus.
Nous présentons dans ce mémoire la classification mathématique des textes dans son application à l’ analyse et l’ extraction des règles d’association aximales. En effet, plusieurs projets de recherche présentent de nombreuses méthodes issues seulement de la classification, mais nous pensons que l’utilisation de la classification jumelée avec les règles d’association maximales comportera plusieurs avantages par rapport à l’utilisation seule de la classification.
Parmi ces avantages, on peut citer par exemple: 1. la détection des dépendances et des corrélations utiles entre les mots des différentes classes de notre corpus. 2. l’ extraction des connaissances cachées, souvent très pertinentes, à partir d’ un grand olume de données. 3. a combinaison des avantages des deux approches, la première, de la classification, où les résultats sont toujours variables selon les paramètres ChOlSlS au début, et la 2 deuxième, des règles d’ association, où tous les algorithmes doivent découvrir, dans la plupart du temps, les mêmes règles d’ association. Notre objectif de recherche consiste à mettre en place une passerelle qUI permet d ‘ intégrer le processus d ‘ extraction des règles d’ association avec celui de la classification textuel et cela, dans I’ obi des avantages des deux IS,’
