Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

République Algérienne Démocratique et Populaire Ministère de l’Enseignement Sup

République Algérienne Démocratique et Populaire Ministère de l’Enseignement Supérieur et de la Recherche Scientifique Ecole Nationale Polytechnique Département de Génie Electronique PROJET DE FIN D’ETUDE EN VUE DE L’OBTENTION DU DIPLOME D’INGENIEUR D’ETAT EN GENIE ELECTRONIQUE Présenté par: Mr KRIZOU Hocine Thème Proposé et Encadré par : Mr. LARBES Cherif et Mr. ALLALI Ali Soutenu le : 12/10/2011, devant le jury composé de : Promotion 2011 Les techniques SVD et traitement d'images dans la recherche intelligente d'informations en indexation sémantique latente Président: Examinateur: Promoteurs: Mr. HADDADI Mourad Mr. AIT CHEIKH M Salah Mr. LARBES Cherif Mr. ALLALI Ali REMERCIEMENTS Je tiens à exprimer ma reconnaissance à Mr. LARBES pour son encadrement et Mr. ALLALI, pour avoir Co-encadré mes travaux. Je les remercie pour leur disponibilité, leur écoute et leurs conseils, qui m’ont été toujours précieux, leur confiance, leur investissement scientifique et humain qui ont été essentiels à la réalisation de ce travail. Je remercie Mr. HADDADI Mourad et Mr.AIT CHEIKH M Salah, je leur en suis reconnaissant d’avoir accepté de faire partie du jury de mon projet de fin d’étude. Je souhaite aussi remercier tous les enseignants de l’Ecole Nationale Polytechnique, pour les connaissances qu’ils m’ont transmis, leur disponibilité et leurs efforts. J’ai sûrement oublié de remercier beaucoup d’autres personnes méritantes, des personnes qui m’ont offert leur amitié, qui m’ont ouvert leur cœur, qui m’ont ouvert leur porte, qu’elles trouvent ici l’expression de ma profonde gratitude et de mon amitié la plus sincère. DÉDICACES Je dédie ce modeste travail à mon père, ma mère, ainsi qu’à mon frère et ma sœur qui m’ont tant soutenu et aidé tout au long de mon parcours et sans qui je n’en serais pas là. A mes amis qui m’ont tant supporté, spécialement, Khaldoun et Fellah. A tous mes camarades et amis de notre chère école avec qui j’ai passé de bons moments et appris beaucoup de choses. A tous ceux qui ont contribué de près ou de loin à mon travail. A tous ceux que je n’ai pas cités et qui sont présents dans mes pensées. RESUME L’objet des systèmes de recherche d’informations est de faciliter l’accès à un ensemble de documents, afin de permettre à l’utilisateur de retrouver ceux qui sont pertinents, c'est-à- dire ceux dont le contenu correspond le mieux à son besoin en information. La qualité des résultats de la recherche se mesure en comparant les réponses du système avec les réponses idéales que l'utilisateur espère recevoir. Plus les réponses du système correspondent à celles que l'utilisateur espère, plus le système est jugé performant. Les premiers systèmes permettaient d’effectuer des recherches booléennes, c’est à dire, des recherches ou seule la présence ou l’absence d’un terme de la requête dans un texte permet de le sélectionner. Il a fallu attendre la fin des années 60, pour que l’on applique le modèle vectoriel aux problématiques de la recherche d’information. Dans ces deux modèles, seule la présence, l’absence, ou la fréquence des mots dans le texte est porteuse d’information. D’autres systèmes de recherche d’information adoptent cette approche dans la modélisation des données textuelles et dans le calcul de la similarité entre documents ou par rapport à une requête. Plusieurs améliorations des systèmes de recherche d’information utilisent les relations sémantiques qui existent entre les termes dans un document. LSI (Latent Semantic Indexing), par exemple réalise ceci à travers des méthodes d’analyse qui mesurent la cooccurrence entre deux termes dans un même contexte pour créer des liens sémantiques entre les termes dans un processus de chaines lexicales. Dans ce travail, nous étudierons la technique de LSI, du prétraitement de la base de données jusqu'à l’application d’algorithme de décomposition et la conception d’un moteur de recherche basé sur cette technique. La contribution clé du travail présenté dans ce projet est le développement d'une approche hybride et efficace de LSI pour une utilisation plus performante dans la recherche d’information, basé sur l'utilisation de techniques de traitement d'image en tandem avec les composants existants. ABSTRACT The object of information retrieval systems is to make easy the access to documents and to allow a user to find those that are appropriate. The quality of the results of research is measured by comparing the answers of the system with the ideal answers that the user hopes to find. The system is competitive when its answers correspond to those that the user hopes. The first retrieval systems performing Boolean researches, in other words, researches in which only the presence or the absence of a term of a request in a text allow choosing it. It was necessary to wait for the end of the sixties to apply the vector model in information retrieval. In these two models, alone presence, absence, or frequency of words in the text is holder of information. Several Information Retrieval Systems adopt a flat approach in the modeling of data and in the counting of similarity between documents or in comparison with a request. Several improvements in information retrieval systems use the semantic relationships which exist between terms in a document. LSI (Latent Semantic Indexing), for example achieves this through analytical methods that measure co-occurrence between two terms in the same context to create semantic links between terms in a process of lexical chains. In this work, we study the technique of LSI, the pretreatment of the database to the application of decomposition algorithm and design of a search engine based on this technique. A key contribution of the work presented in this project is the development of a hybrid and efficient approach to LSI for effective use in IR, based on the use of image processing techniques in tandem with the existing components. ﻣﻠﺧﺹ ﺍﻟﻐﺮﺽ ﻣﻦ ﻧﻈﻢ ﺍﺳﺘﺮﺟﺎﻉ ﺍﻟﻤﻌﻠﻮﻣﺎﺕ ﻫﻮ ﺗﺴﻬﻴﻞ ﺍﻟﻮﺻﻮﻝ ﺇﻟﻰ ﻣﺠﻤﻮﻋﺔ ﻣﻦ ﺍﻟﻮﺛﺎﺋﻖ ﺍﻟﺘﻲ ﺗﻤﻜﻦ ﺍﻟﻤﺴﺘ ﺨﺪﻡ ﻣﻦ ﺍﻟﻌﺜﻮﺭ ﻋﻠﻰ ﺗﻠﻚ ﺫﺍﺕ ﺍﻟﺼﻠﺔ . ﻭﻳﺘﻢ ﻗﻴﺎﺱ ﺟﻮﺩﺓ ﻧﺘﺎﺋﺞ ﺍﻟﺒﺤﻮﺙ ﺑﻤﻘﺎﺭﻧﺔ ﺭﺩﻭﺩ ﺍﻟﻨﻈﺎﻡ ﻣﻊ ﺍﻷﺟﻮﺑﺔ ﺍﻟﻤﺜﺎﻟﻴﺔ ﺍﻟﺘﻲ ﺍﻟﻤﺴﺘﺨﺪﻡ ﻳﺘﻮﻗﻊ ﺍﻟﺤﺼﻮﻝ ﻋﻠﻴﻬﺎ. ﺍﻟﻨﻈﺎﻡ ﺫﺍﺕ ﺍﺳﺘﺠﺎﺑﺎﺕ ﺃﻛﺜﺮ ﺗﺘﻄﺎﺑﻖ ﻣﻊ ﺗﻠﻚ ﺍﻟﺘﻲ ﻳﻘﻮﻡ ﺍﻟﻤﺴﺘﺨﺪﻡ ﺑﺘﻮﻗﻌﻬﺎ ، ﻳﻌﺘﺒﺮ ﻧﻈﺎﻡ ﺃﻛﺜﺮ ﻛﻔﺎءﺓ . ،ﺃﻭﻝ ﺍﻷﻧﻈﻤﺔ ﺳﻤﺤﺖ ﺑﺘﻨﻔﻴﺬ ﻋﻤﻠﻴﺎﺕ ﺍﻟﺒﺤﺚ ﺍﻟﻤﻨﻄﻘﻴﺔ ﺃﻱ ﺍﻟﺒﺤﻮﺙ ﺃﻳﻦ ﻓﻘﻂ ﻭﺟﻮﺩ ﺃﻭ ﻋﺪﻡ ﻭﺟﻮﺩ ﻣﺼﻄﻠﺢ ﺍﻻﺳﺘﻌﻼﻡ ﻓﻲ ﻧﺺ ﻳﻤﻜﻦ ﺗﺤﺪﻳﺪﻩ ﺇﻻ . ﺣﺘﻰ ﻭﻗﺖ ﻣﺘﺄﺧﺮ ﻣﻦ 60 ،، ﺣﻴﺚ ﺗﻢ ﺗﻄﺒﻴﻖ ﻧﻤﻮﺫﺝ ﻣﺘﺠﻪ ﻟﻤﺸﺎﻛﻞ ﺍﺳﺘﺮﺟﺎﻉ ﺍﻟﻤﻌﻠﻮﻣﺎﺕ. ﻓﻲ ﻛﻼ ﺍﻟﻨﻤﻮﺫﺟﻴﻦ ﺇﻻ ﻭﺟﻮﺩ، ﻏﻴﺎﺏ، ﺃﻭ ﺗﻜﺮﺍﺭ ﺍﻟﻜﻠﻤﺎﺕ ﻓﻲ ﺍﻟﻨﺺ ﻳﺤﻤﻞ ﺍﻟﻤﻌﻠﻮﻣﺎﺕ . ﻏﻴﺮﻫﺎ ﻣﻦ ﻧﻈﻢ ﺍﺳﺘﺮﺟﺎﻉ ﺍﻟﻤﻌﻠﻮﻣﺎﺕ ﺗﻌﺘﻤﺪ ﻋﻦ ﻫﺬﺍ ﺍﻟﻤﻨﻬﺞ ﻓﻲ ﻧﻤﺬﺟﺔ ﺍﻟﻨﺼﻮﺹ ﻭﺣﺴﺎﺏ ﺍﻟﺘﺸﺎﺑﻪ ﺑﻴﻦ ﺍﻟﻤﺴﺘﻨﺪﺍﺕ ﺃﻭ ﻣﻊ ﺍﺳﺘﻌﻼﻡ . ﺍﻟﻌﺪﻳﺪ ﻣﻦ ﺍﻟﺘﺤﺴﻴﻨﺎﺕ ﻓﻲ ﻧﻈﻢ ﺍﺳﺘﺮﺟﺎﻉ ﺍﻟﻤﻌﻠﻮﻣﺎﺕ ﺗﺴﺘﺨﺪﻡ ﺍﻟﻌﻼﻗﺎﺕ ﺍﻟﺪﻻﻟﻴﺔ ﺑﻴﻦ ﺍﻟﻤﺼﻄﻠﺤﺎﺕ ﺍﻟﻮﺍﺭﺩﺓ ﻓﻲ ﺍﻟﻮﺛﻴﻘﺔ LSI. ﻋﻠﻰ ﺳﺒﻴﻞ ﺍﻟﻤﺜﺎﻝ ﻳﺤﻘﻖ ﺫﻟﻚ ﻣﻦ ﺧﻼﻝ ﺍﻷﺳﺎﻟﻴﺐ ﺍﻟﺘﺤﻠﻴﻠﻴﺔ ﺍﻟﺘﻲ ﺗﻘﻴﺲ ﺍﻟﻤﺸﺘﺮﻙ ﺑﻴﻦ ﻣﺼﻄﻠﺤﻴﻦ ﻓﻲ ﺍﻟﺴﻴﺎﻕ ﻧﻔﺴﻪ ﻟﺨﻠﻖ ﺭﻭﺍﺑﻂ ﺑﻴﻦ ﺍﻟﻤﺼﻄﻠﺤﺎﺕ ﻓﻲ ﻋﻤﻠﻴﺔ ﺍﻟﺴﻼﺳﻞ ﺍﻟﻤﻌﺠﻤﻴ ﺔ. ﻓﻲ ﻫﺬﺍ ﺍﻟﻌﻤﻞ، ﻧﺪﺭﺱ ﺗﻘﻨﻴﺔLSI ، ﻣﻦ ﻣﻌﺎﻟﺠﺔ ﻗﺎﻋﺪﺓ ﺍﻟﺒﻴﺎﻧﺎﺕ ﺇﻟﻰ ﺗﻄﺒﻴﻖ ﺧﻮﺍﺭﺯﻣﻴﺔ ﺍﻟﺘﺤﻠﻞ ﻭﺗﺼﻤﻴﻢ ﻣﺤﺮﻙ ﺑﺤﺚ ﻋﻠﻰ ﺃﺳﺎﺱ ﻫﺬﻩ ﺍﻟﺘﻘﻨﻴﺔ. ﻣﺴﺎﻫﻤﺔ ﺭﺋﻴﺴﻴﺔ ﻣﻦ ﺍﻷﻋﻤﺎﻝ ﺍﻟﺘﻲ ﻋﺮﺿﺖ ﻓﻲ ﻫﺬﺍ ﺍﻟﻤﺸﺮﻭﻉ ﻫﻲ ﺗﻄﻮﻳﺮ ﻧﻬﺞ ﺍﻟﻬﺠﻴﻦ ﻭﻻﺳﺘﺨﺪﺍﻣﻬﺎ ﻓﻲ ﺍﺳﺘﺮﺟﺎﻉ ﺍﻟﻤﻌﻠﻮﻣﺎﺕ ﺍﻷﻛﺜﺮ ﻛﻔﺎءﺓ، ﻋﻠﻰ ﺃﺳﺎﺱ ﺍﺳﺘﺨﺪﺍﻡ ﺗﻘﻨﻴﺎﺕ ﻣﻌﺎﻟﺠﺔ ﺍﻟﺼﻮﺭ ﺟﻨﺒﺎ ﺇﻟﻰ ﺟﻨﺐ ﻣﻊ ﺍﻟﻤﻜﻮﻧﺎﺕ ﺍﻟﻘﺎﺋﻤﺔ . SOMMAIRE SOMMAIRE Chapitre I Recherche d’information : Concepts de base I.1 Introduction……………………………………………………………………………………………..5 I.2 Un survol de l’histoire de la Recherche d’Information …………………………………………….…..5 I.3 La naissance de la recherche d’information………………………………………………………….…9 I.4 Ère Internet……………………………………………………………………..………………….…..10 I.5 Généralités sur les Systèmes de Recherche d’Information(SRI)… …………………………………..10 I.5.1 Définition………………………………………………………………………………………...10 I.5.2 Concepts clés de la recherche d’information…………………………………………………..11 I.5.2.1 La collection de documents……………………….………………………………………..12 I.5.2.2 Le document…………………………………………………………………………….….13 I.5.2.3 Les langages d’interrogation……………………………………………………………….13 I.5.2.4 La représentation des documents et des requêtes (indexation ou analyse). ……………….14 I.5.2.5 L’appariement requête-document………………………………………………………….15 I.5.2.6 La notion de ‘besoin’ dans la recherche d’information….…………………………………16 I.6 Evaluation des performances des systèmes de recherche d’information…...…………………………16 I.6.1 La notion de pertinence…………………………………………………………………………..17 I.6.2 Les mesures de Précision/Rappel………………………………………………………………..18 I.6.3 Autres mesures de performance………………………………………………………………….22 I.7 Améliorations techniques……………..……………………………………………………………….23 I.8 Conclusion……………………………………………………………………………………………..23 Chapitre II Indexation sémantique latente II.1 Introduction……………………………………………………………………………………..……24 II.2 Introduction à VSM (Vector Space Model) ………………………………………………….……...26 II.3 Bruit lexicologique…………………………………………………………………………….……..30 II.4 Algorithmes de LSI…………………………………………………………………………….….…31 II.4.1 Prétraitement……………………………………………………………………………………31 II.4.2 Décomposition de Matrice……………………………………………………………………...35 II.5 Application de la LSI ………………………………………………………………………………...38 II.6 Conclusion……………………………………………………………………………………….…...41 Chapitre III Les ondelettes de Haar III.1 Introduction………………………………………………………………………………………….44 III.2 La Transformée en Ondelettes………………………………………………………………………44 III.2.1 Définition……………………………………………………………………………………...46 III.2.2 L’Ondelette de Haar…………………………………………………………………………...46 III.2.3 Exemple de calcul………………………………………………………………………….…47 III.2.4 Le débruitage……………………………………………………………………………….…50 III.3 Étude proposée……………………………………………………………………………………...52 SOMMAIRE III.4 Conclusion…………………………………………………………………………………………..53 Chapitre IV Étude expérimentale et analyse des résultats IV.1 Introduction………………………………………………………………………………………….53 IV.2 Les composants du système LSI…………………………………………………………………….53 IV.2.1 Description de la base de données………………………………………………………….…54 IV.2.2 Description de prétraitement de documents………………………………………………..….55 IV.2.4 Vecteur requête……………………………………………………………………………..…57 IV.2.5 Implémentations des algorithmes de décomposition matricielle………………………….…..58 IV.2.6 Méthodologie des métriques…………………………………………………………………..61 IV.2.7 Métriques utilisés……………………………………………………………………………...62 IV.3 Analyse du bruit lexicale et des mesures en recherche d'information intelligente……………..…...62 IV.3.1 Méthodologie proposée pour la mesure de bruit lexicale……………………………………..64 IV.4 Approche empirique…………………………………………………………………………………68 IV.5 Interface graphique………………………………………………………………………………….73 IV.6 Conclusion………………………………………………………………………………………......75 Liste des tableaux Tableau 1 : Exemple de valeurs rappel-précision…………………………………………………..20 Tableau 2 : Valeurs utilisés pour la courbe rappel-précision……………………………………….21 Tableau 3 : Transformée de Haar du signal S………………………………………………………49 Tableau 4: Ensemble des documents de la base de données Memo [6] ……………………………56 Tableau 5: TDM pour l'exemple Mémos [6] ………………………………………………………57 Tableau 6: Chaque colonne représente un document……………………………………………….61 Liste des figures Figure 1 : Le processus de recherche d’information……..………………………………………....12 Figure 2 : Exemple de rappel et de précision pour une requête…………………………………….19 Figure 3 : uploads/Science et Technologie/krizou-hocine.pdf