web search engine UIC
1.0.0
Projet final pour CS 582 Cours de récupération d'informations à l'Université de l'Illinois à Chicago
Pour exécuter le programme à partir du terminal, utilisez simplement la commande:
python main.py
Un rapport est fourni pour mieux expliquer les fonctionnalités et l'interface utilisateur du moteur de recherche, veuillez vous référer à:
report.pdf
Ce document est un rapport pour le projet final de la recherche d'informations CS 582 à l'Université de l'Illinois à Chicago. Le projet consistait à créer un moteur de recherche Web pour le domaine UIC à partir de zéro. Le logiciel a été construit modulaire, à partir de la rampe Web, passant par le prétraitement des pages, l'indexation et enfin l'ajout d'une interface utilisateur graphique. De plus, un composant «intelligent» personnalisé inventé par nous était un requis.
J'ai décidé d'expérimenter l'optimisation des moteurs de recherche en utilisant l'expansion de la requête basée sur une approche de rétroaction pseudo-réévolution qui essaie de retirer un contexte large de la requête de l'utilisateur, je l'ai appelé le contexte de la pseudo-relance ( CPRF ). Cela aurait dû ajouter principalement deux types d'améliorations au moteur de recherche:
Ne concentrez pas tous les résultats uniquement sur les mots de la requête, mais y compris le contenu diversifié et connexe à l'ensemble de pages récupéré.
L'élargissement du nombre total de résultats, y compris les pages Web qui ne contiennent aucun des mots présents dans la requête, mais peuvent toujours intéresser l'utilisateur depuis le traitement du même sujet.
Une implémentation de rang de page est également intégrée et peut être activée ou désactivée de l'interface utilisateur de l'application. Plus de détails sur les deux composants intelligents peuvent être trouvés plus tard dans ce document.
Le référentiel contenant le logiciel est accessible via GitHub à:
https://github.com/mirkomantovani/web-search-engine-uic
Le logiciel est écrit dans Python3 dans une mode de programmation orientée objet pour le rendre facilement extensible pour l'avenir. Afin de faciliter le téléchargement et le test du code sans avoir à effectuer un rampage et un prétraitement des pages étendues et longues, l'ensemble de données contenant 10000 pages rampé à partir du domaine UIC: https://www.uic.edu/, et les pages pré-procédés et les fichiers nécessaires, les documents inversés, les scores TF-IDF Les URL) sont incluses dans le référentiel. De cette façon, en clonant le référentiel, le main.py peut être exécuté et en moins d'une seconde, le moteur de recherche est prêt à obtenir des requêtes en entrée. Cependant, les scripts pour exécuter le rampage et le prétraitement sont également inclus et expliqués dans les sous-sections suivantes avec tous les autres composants.
Le compromis Web peut être effectué en exécutant le script multithreded_crawling.py , le rampage se produit en parallèle en utilisant le module de file d'attente pour accéder aux ressources de manière synchronisée, le nombre de threads peut être modifié en modifiant le thread_number constant global dans le même script, qui est de 20 par défaut, cependant, le temps de mise en bouteille principale pour moi était la vitesse de téléchargement Internet et le temps de réparation ou le temps de réparation ou autre chose.
Le rampage commence par le sous-domaine UIC CS: https://www.cs.uic.edu/ spécifié dans le script multithread_crawling.py .
L'approvisionnement se déroule avec une stratégie de largeur d'abord, chaque page est désactivée, téléchargée et analysée à l'aide de la bibliothèque HTMLParser , ses liens sont extraits et vérifiés pour appartenir au domaine UIC, puis ajouté à la file d'attente FIFO s'il est dans un format approprié. Une liste noire de tous les mauvais formats a été dérivée par moi tout en voyant les résultats que j'obtenais dans le rampage et il consiste à ces 18 formats: ".docx", ".doc", ".avi", ".mp4", ".jpg", ".jpeg", ".png", ".gif", ".pdf", ".gz", ".rar", ". ".tgz", ".zip", ".exe", ".js", ".css", ".ppt". Un délai d'expiration de 10 secondes est spécifié comme le temps maximum pour télécharger une page avant de fermer la connexion et de passer à la page suivante.
Les URL sont également modifiées après leur extrait, chaque HTTP initial devient un HTTPS, tous les liens réduits à la fin sont éliminés, les chaînes de requête sont supprimées et également les liens intra-page exprimés par le symbole de hachage (#) sont également en ordre de ne pas laisser le Crawler croire différents. De plus, la manipulation des liens où une balise <a> est ouverte et une autre balise est ouverte à l'intérieur avant de fermer HREF terminée en divisant le lien sur l'ouverture d'une autre balise «<» dans la chaîne.
Pendant le rampage, deux dictionnaires, URL du code et du code de l'URL sont constamment enregistrés sur le disque pour être utilisés plus tard, le code d'une page Web est le numéro de la page téléchargée dans l'ordre chronologique.
Le prétraitement des pages rampé peut être exécuté à partir du script run_preprocessing.py , vous pouvez également spécifier le nombre de pages à considérer et le nombre maximum d'itérations de rang de page en modifiant les constantes correspondantes page_Rank_max_iter et n_pages.
Pendant le prétraitement, un objet CustomTokenzer du script Preprocess.py est utilisé. Chaque page est prétraitée en obtenant d'abord le texte brut dans toutes les balises sauf <Script> et <style>. Pour cette étape, j'ai décidé d'utiliser une bibliothèque très rapide: SelectOlax , qui est une API Python pour utiliser le modeste moteur écrit en C. cpython fournirait bien sûr au moins un ordre de grandeur moins en temps de calcul en ce qui concerne tous les cases HTML écrites en pur pur. La page est ensuite tokenisée, les jetons sont tirés à l'aide du PorterStremmer par NLTK , les mots d'arrêt sont éliminés en utilisant la liste des mots d'arrêt fournis dans les mots d'arrêt de fichier.txt, les chiffres sont supprimés et les mots plus courts que 3 lettres ne sont pas pris en compte.
Dans le prétraitement, l'index inversé est construit et le TF-IDF de chaque paire Word-Doc est calculé et stocké dans l'index inversé. Un graphique Web dirigé ( Graph.py ) est également créé et alimente la mise en œuvre du rang de page dans page_rank.py . Tous les fichiers nécessaires ultérieurement pour répondre à la requête sont ensuite enregistrés sous forme de fichiers binaires.
Le temps total pris pour le prétraitement et la convergence de Page_Rank pour 10000 pages était d'environ 236 secondes, le temps d'exécution du rang de page n'était que d'environ 11 secondes.
Le script Main.py contient le point d'accès au moteur de recherche. Lorsque le programme est démarré, un objet CustomTokenzer est créé pour tokenize les requêtes, un objet TFidFranker est instancié afin de classer les documents en fonction des requêtes.
Lorsque les documents sont classés en fonction de la requête d'un utilisateur, un maximum de 100 documents est pris en compte, cette constante peut être modifiée dans main.py : max_results_to_consider, d'autres paramètres personnalisables sont le nombre de résultats à afficher à un moment des résultats_per_page, le nombre de pages à utiliser: n_pages.
L'interface utilisateur est graphique et implémentée à l'aide du package Python: EasyGui. L'interface graphique est un module extensible, CustomGui.py qui contient les principales API pour les fonctionnalités de base du programme.
Lorsque le programme démarre, l'utilisateur est interrogé les paramètres de base, s'il souhaite utiliser le rang de page et le contexte de la réévolution du contexte ou non. Après cela, le menu principal apparaît. Le menu principal affiche les paramètres actuels du moteur de recherche et certains boutons pour les actions principales qui peuvent être effectuées. Les paramètres peuvent être modifiés dynamiquement au moment de l'exécution en choisissant le bouton approprié dans le menu principal. Les deux autres choix sont les suivants: quitter le programme et exécuter une requête. Si l'utilisateur appuie sur le bouton pour créer une nouvelle requête, une nouvelle fenêtre apparaît et l'utilisateur est invité à insérer une nouvelle requête. Lorsqu'il clique correctement, la requête est prétraitée, et les documents sont classés et les 10 premiers documents (variable du programme) sont affichés avec les informations sur la requête prétraitée et éventuellement les jetons élargis si les commentaires de la pseudo-relance sont allumés. L'utilisateur peut désormais double-cliquer sur un résultat pour ouvrir la page sur un nouvel onglet sur le navigateur par défaut de son système ou peut appuyer récursivement sur «Afficher plus de résultats» à la fin de la liste pour afficher 10 résultats supplémentaires. De plus, si les commentaires de la pseudo-réévolution sont désactivés, l'utilisateur a également la possibilité de relancer la même requête avec l'extension.
Après avoir exécuté une requête et décidé d'annuler ou d'ouvrir un résultat, l'utilisateur est invité au menu principal où il peut modifier le paramètre et / ou exécuter une nouvelle requête ou la même avec des paramètres différents pour comparer les résultats avec celui précédemment obtenu.
Les principaux défis que j'ai rencontrés lors du développement de ce projet sont:
Initialement, il était vraiment difficile de choisir le type de composant intelligent à concevoir. Je n'ai aucune expérience dans ce type d'application et penser à des améliorations sans avoir de démo à tester est tellement difficile.
Pendant la partie d'implémentation, j'ai passé beaucoup de temps à apprendre les bibliothèques et les constructions Python que je ne connaissais pas encore, comme les threads, comment implémenter ou faire du grattage Web pour obtenir les liens d'une page HTML. Une autre chose que j'ai dû apprendre de zéro était de savoir comment créer une interface graphique en python.
Une chose ennuyeuse était le fait que j'ai dû ramper 10000 pages plus d'une fois, car j'ai trouvé dans les pages différents et mauvais formats. En fin de compte, la liste complète des formats que j'ai dû à la liste noire avait une taille de 18 et il comprenait ".docx", ".doc", ".avi", ".mp4", ".jpg", ".jpeg", ".png", ".gif", ".pdf", ".gz", ".rar", ".tar", ".tgz", ". ".exe", ".js", ".css", ".ppt".
Une chose très difficile a été le réglage des hyperparamètres et l'intégration du rang de page pour classer les documents. Le paramètre « E » pour décider de l'importance à donner aux jetons de la requête étendue est la plus difficile à régler car vous ne pouvez pas connaître les performances moyennes de votre moteur de recherche si vous n'avez pas de données étiquetées (documents pertinents pour chaque requête). De plus, la pertinence de la requête est subjective, vous ne savez jamais ce qu'une personne veut récupérer, et vous ne pouvez que deviner en fonction de la requête. J'ai décidé que l' E devrait être au maximum de 0,5 et à la fin, je l'ai réglé autour de 0,1 à 0,2, vous ne voulez pas biaiser la requête en accordant beaucoup à des mots qui ne sont pas dactylographiés par l'utilisateur.
Le schéma de pondération que j'ai utilisé était le simple TF-IDF de mots dans des documents car il s'est avéré être l'un des plus efficaces en ce qui concerne les moteurs de recherche Web et explique l'importance des mots dans chaque document de la bonne manière. Je n'ai même pas pensé à essayer une autre mesure simplement parce que ce n'était pas le but de ce projet et cela semblait bien fonctionner.
La mesure de similitude utilisée pour classer les documents était la similitude du cosinus . J'ai implémenté à partir de la similitude du produit interne et de passer à cela ne serait qu'une question de modification d'une ligne de code. Je pense que la similitude du cosinus est préférable à utiliser car elle prend en considération la longueur du document et la longueur de la requête. Il est plus complexe, et cela fonctionne généralement assez bien dans la pratique dans ce type d'applications, donc le choix de la mesure de similitude n'était pas vraiment un problème, je savais juste que la similitude du cosinus était la bonne.
J'ai fait une évaluation de la précision à 10 (uniquement en considérant les 10 premiers résultats récupérés) pour des requêtes aléatoires et diverses que j'ai proposées. Voici les résultats:
Query: «thèse de conseiller», le premier résultat a été https://grad.uic.edu/electronic-thesisdissertation-faqs et je pense que tous les résultats étaient liés à la thèse et aux choses corrélées, je donnerai une précision: p = 1.0 à cette requête.
Query: «Career Fair», le premier résultat a été https://ecc.uic.edu/career-faires et je pense que tous les résultats étaient quelque peu pertinents pour les salons de carrière, les services de carrière, les événements et l'emploi, je donnerai une précision: P = 1.0 à cette question.
Requête: «Assistanat de recherche», le premier résultat a été http://grad.uic.edu/assistanthips et je pense que tous sauf que le dernier était lié à l'assistanat, étant le RA, TA ou GA, simplement parce que le domaine UIC n'a pas de page spécifique pour RA, donc je donnerai une précision: p = 0,9 à cette question.
Query: «Stages and Jobs», le premier résultat a été https://careerservices.uic.edu/students/internhips et cette fois seulement 6 pages Web étaient pertinentes, cependant, celles qui n'étaient pas encore liées à la carrière et à l'emploi. Je vais donner une précision: p = 0,6 à cette requête.
Query: «Student Center East Address», le premier résultat a été https://fimweb.fim.uic.edu/buildingsdata.aspx, cette requête est plus spécifique et complexe et en fait uniquement à partir de 4 résultats que nous sommes en fait en mesure d'extraire l'adresse du bâtiment, tous les autres résultats, cependant, parlaient de l'étudiant Centre East, ce qui n'est toujours pas si mauvais. Je vais donner une précision: p = 0,4 à cette requête.
Avec une précision moyenne de 0,78 , et le fait que chaque requête a retourné au moins un résultat pertinent, je pense que les résultats sont discrets.
Le premier intelligent avec lequel j'ai expérimenté était un rang de page simple et simple. Pendant le prétraitement des pages, les liens sont extraits et en fonction des connexions de liens, un graphique mondial est créé. L'implémentation du rang de page était telle qu'elle a créé un composant fortement connecté avec l'ensemble du graphique, ce qui signifie que de chaque nœud, il est possible d'accéder à un autre nœud du graphique avec une probabilité non nul. Avec cette interprétation, il n'y a aucune possibilité qu'un marcheur aléatoire se retrouve coincé dans une page.
Les rangs de la page étaient un peu difficiles à intégrer dans la notation des documents pour les classer. Au début, j'ai essayé de faire une combinaison linéaire de similitudes et de rangs de pages en cosinus et de voir comment cela fonctionnait et c'était assez mauvais parce que si le poids du rang de page était trop que la page d'accueil et d'autres pages faisant autorité apparaîtraient toujours dans les résultats. Au lieu de cela, si le poids se penchait davantage vers la similitude du cosinus, le rang de page n'aurait aucun effet.
La deuxième tentative a produit de très bons résultats. Je viens de prendre les 100 premiers résultats uniquement en utilisant et jeté tous les autres et je les ai considérés comme non pertinents. Ensuite, j'ai fait la combinaison linéaire avec le rang de page. Cette fois, cela a fonctionné parce que c'était juste une permutation différente des documents déjà pertinents, et par exemple, la page d'accueil et d'autres documents faisant autorité sont déjà rejetés à ce stade.
Je pense que le but du rang de page dans ce type d'application a été atteint, j'ai pu biaiser une recherche normale pour considérer des pages plus pertinentes plus pertinentes afin que l'utilisateur soit plus susceptible de trouver de bonnes sources d'informations fiables en plus des résultats qui sont très similaires à ce qu'il tape dans sa requête.
Le contexte de la rétroaction du conted-relevant ( CPRF ) J'ai eu cette idée de mon principe et de mon composant intelligent personnalisé près d'un mois à partir de l'implémentation réelle. Quand je mettrais en œuvre, je n'étais pas sûr que cela aurait fonctionné comme prévu et j'avais vraiment peur de faire tout cela pour rien.
Quand je pensais au type de composant intelligent qu'un moteur de recherche Web pourrait avoir, j'ai pensé que ce serait bien si nous pouvions deviner le contexte de la requête utilisateur et lui donner en plus de ce qu'il demande spécifiquement, certains résultats qui sont très liés à ce qu'il a recherché. Une simple expansion de requête statique basée sur des synonymes aurait été trop simple et n'aurait pas été en mesure de capturer des contenus liés mais qui ont un sémantique différent.
Cependant, le point de départ doit toujours être la requête de l'utilisateur, car il n'y a rien d'autre que cela initialement. J'ai vraiment aimé l'idée de la façon dont les commentaires de pseudo-relance ont pu vous permettre de reformuler votre requête de manière autonome. Bien sûr, un commentaire de pertinence explicite lorsque l'utilisateur est demandé quels autres mots il voudrait inclure dans sa question serait probablement mieux, mais en même temps, il pourrait être ennuyeux pour lui d'avoir à répondre à certaines questions lors de la recherche. Une rétroaction de pseudo-relance semble un moyen plus approprié et facile d'exécuter en arrière-plan une requête plus complexe dont l'utilisateur n'est même pas au courant.
Pour extraire certains mots qui pourraient exprimer le contexte de la requête formulée, j'ai décidé d'utiliser des informations intrinsèques que les documents initialement récupérés ont. En particulier, je pense que les mots avec le TF-IDF le plus élevé dans un document pourraient représenter le sujet de ce document, et ce qu'il se différencie des autres, car TF-IDF est élevé lorsque le mot n'est pas contenu dans de nombreux documents, mais il est récurrent dans ce document.
Le processus pour extraire les mots contextuels est le suivant: D'après les documents classés, je prends des documents numéro_docs_expansion, que j'ai définis sur 30 mais pourraient être modifiés dans pseudo_relevance_feedback.py. , pour chaque document, je prends les jetons avec TF-IDF le plus élevé (Number_Top_ToKens constant) et pour chaque jeton distinct en eux, je résume tous les TF-IDF de ce mot de chaque document si le mot est présent. À la fin, je classe les jetons et les mots les plus classés sont les mots courants de chaque document récupéré qui représente le contexte de la requête. Je renvoie ensuite le jeu N expansé (constant numéro_expansion_tokens), auquel les jetons de requête de l'original sont soustraits afin de ne pas avoir de répétitions et de donner trop d'importance à ces mots.
Les jetons étendus recevront un poids de différence, moins que les mots originaux de la requête, cet e_const peut être modifié dans le script statistics.py .
Sur la base des requêtes que j'ai essayées de penser que le composant intelligent donne vraiment quelques améliorations dans certains cas.
Les premiers grands résultats qui fonctionnent toujours est la possibilité d'élargir les ensembles de documents récupérés, en fait, si seulement quelques documents contiennent un mot dans la requête, le moteur de recherche simple ne récupérerait que ces quelques documents. Au lieu de cela, avec le composant intelligent CPRF , les ensembles de résultats seront beaucoup plus importants et pourraient toujours conduire à un ensemble récupéré dont la taille est plus de 100 documents.
Un autre résultat positif que j'ai remarqué dans certaines requêtes est qu'il trouve en fait ce que je cherchais comme premier résultat tandis que le moteur de recherche simple ne le trouve même pas dans les dix premiers résultats. Un exemple de cela peut être observé en recherchant des «cours d'informatique» , ce que je voulais trouver est une liste de tous les cours principaux offerts par le département d'informatique de l'UIC. Il s'agit du premier résultat récupéré par le moteur lorsque le composant intelligent est actif. Au lieu de cela, sans l'activer, cette page n'est pas dans les premiers résultats.
Enfin, j'ai essayé de rechercher la «récupération des informations» , le moteur de recherche sans CPRF était très mauvais, le premier résultat est une page de recherche pour les départements de l'UIC, c'est probablement aussi parce qu'il n'y a pas de page de récupération d'informations dans le domaine UIC ou qu'elle n'est tout simplement pas incluse dans le domaine. Cependant, avec le composant intelligent sur, de nombreuses pages Web liées à cela ont été trouvées, 2 des mots étendus étaient «Cornelia Caragea», le professeur qui enseigne ce cours, de sorte que de nombreuses pages étaient en effet liées à ses publications et à son travail dans la récupération de l'information, il s'agit également d'une très bonne propriété du moteur de recherche. Dans le cas où des résultats très pertinents ne peuvent pas être trouvés, il est toujours en mesure de trouver les meilleurs résultats possibles sur les choses connexes.
Comme expliqué dans 5.3, lorsque j'ai fait la comparaison entre le moteur de recherche en simple et en utilisant le composant intelligent, je pense que les résultats produits étaient assez bons et j'ai obtenu ce que j'attendais quand j'y pensais. Les bonnes choses résumées que j'ai remarquées en la testant étaient:
La possibilité de trouver beaucoup plus de résultats même lorsque la requête d'origine ne produit qu'un tas de sites Web.
La capacité de trouver ce que je cherchais réellement comme premier résultat, par exemple dans les requêtes «cours d'informatique» , comme je l'ai expliqué au paragraphe 5.3.
La très belle propriété de la récupération de contenu discret même lorsque le corpus ne contient pas de pages qui sont très pertinentes pour la requête et peut-être ce que l'utilisateur recherche, je l'ai remarqué pour la requête «Recueil d'informations» comme expliqué au paragraphe 5.3.
Une façon qui m'a montré que cela produisait les résultats corrects était le fait que dans le top 10 des mots en expansion représentant le contexte, certains mots appartenant à la requête de l'utilisateur étaient présents. Cela montre comment la méthode est efficacement capable de capturer le sujet et il n'y a pas d'autre moyen de décrire les autres mots dans cet ensemble, sinon comme des mots appartenant au même contexte que ceux de la requête originale.
Parler du rang de page à la place. Je pense qu'il fait son travail, mais cela ne change pas trop le classement dans la façon dont j'ai mis en œuvre, c'est juste un moyen de biaiser les résultats pour préférer les pages plus faisant autorité s'il y en a.
C'est sûr que l'une des choses qui doivent être traitées à partir d'ici est le réglage des hyperparamètres. C'est la chose la plus difficile à faire principalement en raison du manque de données étiquetées. Je ne peux pas savoir quelle valeur d'un paramètre fonctionne mieux si je ne peux pas évaluer la précision des requêtes, et pour les régler automatiquement, il devrait y avoir beaucoup de données déjà étiquetées.
