web search engine UIC
1.0.0
Projeto final para CS 582 Curso de recuperação de informações na Universidade de Illinois em Chicago
Para executar o programa do terminal, basta usar o comando:
python main.py
Um relatório é fornecido para explicar melhor as funcionalidades e a interface do usuário do mecanismo de pesquisa, consulte:
Relatório.pdf
Este documento é um relatório para o projeto final do CS 582 Recuperação de informações na Universidade de Illinois em Chicago. O projeto consistia na criação de um mecanismo de pesquisa na web para o domínio UIC do zero. O software foi construído modularmente, começando a partir da web rastejando, passando pelo pré -processamento de páginas, indexando e finalmente adicionando uma interface gráfica do usuário. Além disso, um componente "inteligente" personalizado inventado por nós era um requisito.
Decidi experimentar a otimização do mecanismo de pesquisa usando a expansão da consulta com base em uma abordagem de feedback de pseudo-relevância que tenta obter um contexto amplo da consulta do usuário, chamei de contexto de feedback de pseudo-relevância ( CPRF ). Isso deveria ter adicionado principalmente dois tipos de melhorias ao mecanismo de pesquisa:
Não concentre todos os resultados apenas nas palavras na consulta, mas incluindo conteúdo diverso e relacionado ao conjunto de páginas recuperadas.
Expandindo o número total de resultados, incluindo páginas da Web que não contêm nenhuma das palavras presentes na consulta, mas ainda podem ser de interesse do usuário desde que tratem o mesmo tópico.
Uma implementação de classificação de página também é integrada e pode ser ativada ou desativada na interface do usuário do aplicativo. Mais detalhes sobre os dois componentes inteligentes podem ser encontrados posteriormente neste documento.
O repositório que contém o software pode ser acessado através do GitHub em:
https://github.com/mirkomantovani/web-search-engine-uic
O software é escrito no Python3 de maneira a programação orientada a objetos para torná-lo facilmente extensível para o futuro. In order to make it easy to download and test the code without having to perform an extensive and time-consuming crawling and page preprocessing, the dataset containing 10000 pages crawled from the UIC domain: https://www.uic.edu/, and the preprocessed pages and needed files generated (Inverted Index, TF-IDF scores, Page Ranks, Document lengths, documents' tokens, URLs) estão incluídos no repositório. Dessa forma, clonando o repositório, o main.py pode ser executado e em menos de um segundo o mecanismo de pesquisa está pronto para obter consultas na entrada. No entanto, os scripts para executar o rastreamento e o pré -processamento também são incluídos e explicados nas subseções a seguir com todos os outros componentes.
The web crawling can be done by executing the script multithreaded_crawling.py , the crawling happens in parallel by using the Queue module to access the resources in a synchronized way, the number of threads can be changed by modifying the global constant THREAD_NUMBER in the same script, which is 20 by default, however, the main bottleneck in crawling for me was the internet download speed and not the parsing time or anything else.
O rastreamento começa no subdomínio UIC CS: https://www.cs.uic.edu/ especificado no script multithreaded_crawling.py .
O rastreamento acontece com uma estratégia de largura, todas as páginas são desqueidas, baixadas e analisadas usando a biblioteca HTMLPARSER , seus links são extraídos e verificados para pertencer ao domínio UIC e depois adicionados à fila FIFO se estiver em um formato apropriado. A blacklist of all bad formats was derived by me while seeing the results that I was getting in the crawling and it consists in this 18 formats: ".docx", ".doc", ".avi", ".mp4", ".jpg", ".jpeg", ".png", ".gif", ".pdf", ".gz", ".rar", ".tar", ".tgz", ".zip", ".exe", ".js", ".css", ".ppt". Um tempo limite de 10 segundos é especificado como o tempo máximo para baixar uma página antes de fechar a conexão e passar para a próxima página.
Os URLs também são modificados após serem extraídos, todo HTTP inicial se torna um HTTPS, todos os corados no final são eliminados, as cordas de consulta são removidas e também os links intra-página expressos por hash símbolo (#) também são removidos para não deixar que os risões acreditem que mais páginas com um hash. Além disso, o manuseio de links onde uma tag <a> é aberta e outra tag é aberta dentro antes de fechar o HREF, dividindo o link na abertura de outra tag "<" na string.
Durante o rastreamento, dois dicionários, o URL do código e o código da URL são constantemente salvos no disco a ser usado posteriormente, o código de uma página da web é o número da página baixada em ordem cronológica.
O pré -processamento das páginas rastejadas pode ser executado no script run_preprocessing.py , você também pode especificar o número de páginas a serem consideradas e o número máximo de iterações da página da página alterando as constantes correspondentes Page_Rank_Max_iter e N_Pages.
Durante o pré -processamento, um objeto CustomTokenizer do script preprocess.py é usado. Cada página é pré -processada pela primeira vez obtendo o texto simples em todas as tags, exceto <cript> e <yoy>. Para esta etapa, decidi usar uma biblioteca muito rápida: o Selectolax , que é uma API do Python para usar o mecanismo modesto escrito em C. cpython, obviamente, forneceria pelo menos uma ordem de magnitude menos no tempo computacional em relação a quaisquer parses HTML escritas em Python puro. A página é então tokenizada, os tokens são provocados usando o PortersTemMer pelo NLTK , as palavras de parada são eliminadas usando a lista de palavras de parada fornecidas no arquivo Stopwords.txt , os dígitos são removidos e as palavras mais curtas que 3 letras não são consideradas.
No pré-processamento, o índice invertido é construído e o TF-IDF de cada par de palavras-doc é calculado e armazenado no índice invertido. Um gráfico da web direcionado ( graf.py ) também é criado e alimentar para a implementação da classificação da página em page_rank.py . Todos os arquivos necessários mais tarde para responder à consulta são salvos como arquivos binários.
O tempo total gasto para a convergência de pré -processamento e Page_Rank para 10000 páginas foi de aproximadamente 236 segundos, o tempo de execução da classificação da página foi de apenas 11 segundos.
O script main.py contém o ponto de acesso ao mecanismo de pesquisa. Quando o programa é iniciado, um objeto CustomTokenizer é criado para tokenizar as consultas, um objeto TFIDFRANKER é instanciado para classificar os documentos com base nas consultas.
Quando os documentos são classificados com base na consulta de um usuário, um máximo de 100 documentos é considerado, essa constante pode ser alterada em main.py : max_results_to_consider, outros parâmetros personalizáveis são o número de resultados a serem exibidos em um tempo Results_per_Page, o número de páginas a serem usadas: n_pages.
A interface do usuário é gráfica e implementada usando o pacote Python: easygui. A GUI é um módulo extensível, CustomGui.py, que contém as principais APIs para as funcionalidades básicas do programa.
Quando o programa inicia, o usuário é solicitado às configurações básicas, se ele deseja usar a classificação da página e o contexto de feedback de pseudo-relevância ou não. Depois disso, o menu principal é exibido. O menu principal mostra as configurações atuais do mecanismo de pesquisa e alguns botões para as principais ações que podem ser executadas. As configurações podem ser alteradas dinamicamente no tempo de execução escolhendo o botão apropriado no menu principal. As outras duas opções são: desistir do programa e executar uma consulta. Se o usuário pressionar o botão para criar uma nova consulta, uma nova janela será exibida e o usuário será solicitado a inserir uma nova consulta. Quando ele clica bem, a consulta é pré-processada e os documentos são classificados e os 10 primeiros documentos (variáveis no programa) são exibidos juntamente com as informações sobre a consulta pré-processada e possivelmente os tokens expandidos se o feedback da pseudo-relevância estiver ligado. O usuário agora pode clicar duas vezes em um resultado para abrir a página em uma nova guia no navegador padrão de seu sistema ou pode pressionar recursivamente "Mostrar mais resultados" no final da lista para mostrar mais 10 resultados. Além disso, se o feedback da pseudo-relevância estiver desativado, o usuário também terá a possibilidade de executar novamente a mesma consulta com a expansão.
Depois de executar uma consulta e decidir cancelar ou abrir um resultado, o usuário é solicitado ao menu principal, onde ele pode alterar a configuração e/ou executar uma nova consulta ou a mesma com configurações diferentes para comparar os resultados com os obtidos anteriormente.
Os principais desafios que experimentei durante o desenvolvimento deste projeto são:
Inicialmente, era realmente difícil escolher que tipo de componente inteligente projetar. Não tenho experiência nesse tipo de aplicativo e pensar em melhorias sem ter uma demonstração para testar é tão difícil.
Durante a parte da implementação, passei muito tempo aprendendo sobre bibliotecas e construções do Python que ainda não conhecia, como threads, como implementar ou fazer raspagem na Web para obter os links de uma página HTML. Outra coisa que tive que aprender do zero foi como criar uma GUI em Python.
Uma coisa irritante era o fato de eu ter que rastejar 10000 páginas mais de uma vez, porque encontrei nas páginas vários e errados formatos. No final, toda a lista de formatos que eu tive que a lista negra tinha um tamanho de 18 e incluía ".docx", ".doc", ".avi", ".mp4", ".jpg", ".jpegz", ".gif .gif .gif .s. ".exe", ".js", ".css", ".ppt".
Uma coisa muito desafiadora foi o ajuste dos hiperparâmetros e a integração da Page Rank para classificar documentos. O parâmetro " E " para decidir quanta importância é dar aos tokens da consulta estendida é a mais difícil de ajustar, porque você não pode conhecer o desempenho médio do seu mecanismo de pesquisa se não tiver dados rotulados (documentos relevantes para cada consulta). Além disso, a relevância da consulta é subjetiva, você nunca sabe o que uma pessoa deseja recuperar e só pode adivinhar com base na consulta. Decidi que o E deveria ser no máximo 0,5 e, no final, eu o defina em torno de 0,1-0.2, você não deseja influenciar a consulta, dando muita importância a palavras que não são digitadas pelo usuário.
O esquema de ponderação que eu usei foi o simples TF-IDF das palavras em documentos, pois provou ser um dos mais eficazes quando se trata de mecanismos de pesquisa na web e explica a importância das palavras em cada documento da maneira correta. Eu nem pensei em tentar outra medida apenas porque não era o objetivo deste projeto e isso parecia funcionar bem.
A medida de similaridade usada para classificar documentos foi a similaridade de cosseno . Eu implementei a partir da semelhança interna do produto e a mudança para isso seria apenas uma questão de alterar uma linha de código. Eu acho que a similaridade de cosseno é melhor usar, porque leva em consideração o comprimento do documento e o comprimento da consulta. É mais complexo e geralmente funciona muito bem na prática nesse tipo de aplicação, portanto, escolher a medida de similaridade não era realmente um problema, eu apenas sabia que a similaridade de cosseno era a certa.
Fiz uma avaliação da precisão em 10 (considerando apenas os 10 primeiros resultados recuperados) para algumas consultas aleatórias e diversas que eu criei. Aqui estão os resultados:
Consulta: “Tese de consultor”, o primeiro resultado foi https://grad.uic.edu/electronic-thesedisSertation-daqs e acho que todos os resultados foram relacionados à tese e às coisas correlacionadas, darei uma precisão: P = 1,0 a esta consulta.
Consulta: “Feira de Carreira”, o primeiro resultado foi https://ecc.uic.edu/career-dairs e acho que todos os resultados foram um pouco relevantes para feiras de carreira, serviços de carreira, eventos e emprego, darei uma precisão: p = 1.0 a esta consulta.
Consulta: “Assistência de Pesquisa”, o primeiro resultado foi http://grad.uic.edu/assistantships e acho que tudo, exceto o último, foi relacionado a assistentes, sendo RA, TA ou GA, apenas porque o domínio UIC não tem uma página específica para RA, por isso darei uma Precision: P = 0,9 a esse query.
Consulta: “Estágios e empregos”, o primeiro resultado foi https://careerservices.uic.edu/students/interships e, desta vez, apenas 6 páginas da web eram relevantes, no entanto, as que não estavam ainda estão relacionadas à carreira e emprego. Vou dar uma precisão: P = 0,6 a esta consulta.
Consulta: “Endereço do East Student Center East”, o primeiro resultado foi https://fimweb.fim.uic.edu/buildingsdata.aspx, esta consulta é mais específica e complexa e, de fato, apenas de 4 resultados, na verdade, não é capaz de extrair o endereço do edifício, todos os outros resultados, no entanto, foram sobre o centro do leste do aluno, o que ainda não existe. Vou dar uma precisão: p = 0,4 a esta consulta.
Com uma precisão média de 0,78 e o fato de que toda consulta retornou pelo menos um resultado relevante, acho que os resultados são discretos.
O primeiro inteligente que eu experimentei foi claro e simples. Durante o pré -processamento das páginas, os links são extraídos e com base nas conexões de link que um gráfico mundial é criado. A implementação do Page Rank foi tal que criou um componente fortemente conectado com todo o gráfico, o que significa que, de cada nó, é possível chegar a outro nó do gráfico com uma probabilidade não nula. Com essa interpretação, não há possibilidade de que um andador aleatório fique preso em uma página.
As fileiras da página foram um pouco difíceis de integrar na pontuação dos documentos para classificá -los. No começo, tentei fazer apenas uma combinação linear de similaridade de cosseno e classificações de página e ver como funcionou e foi muito ruim, porque se o peso da classificação da página fosse demais do que a página inicial e outras páginas autoritárias sempre apareceriam nos resultados. Em vez disso, se o peso estivesse se inclinando mais para a similaridade do cosseno, a Page Rank não teria nenhum efeito.
A segunda tentativa produziu bons resultados. Basicamente, acabei de receber os primeiros 100 resultados apenas usando e descartei todos os outros e os considerei não relevantes. Então eu fiz a combinação linear com a classificação da página. Desta vez, funcionou porque era apenas uma permutação diferente dos documentos já relevantes e, por exemplo, a página inicial e outros documentos autoritários já foram descartados neste momento.
Penso que o objetivo da classificação da página nesse tipo de aplicativo foi alcançado, pude influenciar uma pesquisa normal para considerar páginas mais relevantes, para que o usuário tenha mais chances de encontrar fontes de informação boas e confiáveis, além dos resultados que são muito semelhantes ao que ele digita em sua consulta.
O contexto Pseudo-re-relevância ( CPRF ) tive essa idéia do meu princípio e do componente inteligente personalizado a quase um mês a partir da implementação real. Quando eu estava implementando, não tinha certeza de que teria funcionado como o esperado e estava realmente assustado por não estar fazendo tudo isso por nada.
Quando eu estava pensando em que tipo de componente inteligente um mecanismo de pesquisa da web poderia ter, pensei que seria bom se pudéssemos adivinhar o contexto da consulta do usuário e dar a ele além do que ele está pedindo especificamente, alguns resultados que estão muito relacionados ao que ele procurou. Uma expansão simples de consulta estática baseada em sinônimos teria sido muito simples e não seria capaz de capturar conteúdos relacionados, mas com uma semântica diferente.
No entanto, o ponto de partida sempre deve ser a consulta do usuário, pois não há mais nada, exceto isso inicialmente. Eu realmente gostei da idéia de como o feedback da pseudo-relevância foi capaz de permitir que você reformule sua consulta de maneira autônoma. É claro que um feedback explícito de relevância quando o usuário é questionado sobre quais outras palavras ele gostaria de incluir em sua consulta provavelmente seria melhor, mas ao mesmo tempo poderia ser irritante para ele ter que responder a algumas perguntas enquanto procura. Um feedback de pseudo-relevância parece uma maneira mais apropriada e fácil de executar em segundo plano, algumas consultas mais complexas que o usuário nem está ciente.
Para extrair algumas palavras que poderiam expressar o contexto da consulta formulada, decidi usar algumas informações intrínsecas que os documentos recuperados inicialmente possuem. Em particular, acho que as palavras com maior TF-IDF em um documento podem representar o tópico desse documento e o que ele se diferencia dos outros, porque o TF-IDF é alto quando a palavra não está contida em muitos documentos, mas é recorrente nesse documento.
O processo para extrair as palavras de contexto é o seguinte: A partir dos documentos classificados, tomo documentos number_docs_expansion, que eu defini para 30, mas poderia ser alterado em pseudo_relevance_feedback.py. , para cada documento, pego os tokens com o mais alto TF-IDF (constante número_top_tokens) e para cada token distinto neles soma todo o TF-IDF desta palavra de cada documento, se a palavra estiver presente. No final, classifiquei os tokens e as palavras mais bem classificadas são as palavras comuns de cada documento recuperado que representam o contexto da consulta. Em seguida, retorno o conjunto de palavras expandidas (número constante_expansion_tokens), ao qual os tokens de consulta do original são subtraídos para não ter repetições e dar muita importância a essas palavras.
Os tokens expandidos terão uma diferença de peso, menor que as palavras originais na consulta, este e_const pode ser alterado no script statistics.py .
Com base nas consultas que tentei achar que o componente inteligente realmente oferece algumas melhorias em alguns casos.
Os primeiros grandes resultados que funcionam sempre é a capacidade de expandir os conjuntos de documentos recuperados; de fato, se apenas alguns documentos contiverem alguma das palavras na consulta, o mecanismo de pesquisa simples recuperaria apenas esses poucos documentos. Em vez disso, com o componente inteligente da CPRF , os conjuntos de resultados serão muito maiores e poderiam sempre levar a um conjunto recuperado cujo tamanho é mais de 100 documentos.
Outro resultado positivo que notei em algumas consultas é que ele realmente encontra o que eu estava procurando como primeiro resultado, enquanto o mecanismo de pesquisa simples nem o encontra nos dez melhores resultados. Um exemplo disso pode ser observado pesquisando “cursos de ciência da computação” , o que eu queria encontrar é uma lista de todos os cursos principais oferecidos pelo Departamento de Ciência da Computação da UIC. Este é o primeiro resultado recuperado pelo motor quando o componente inteligente está ativo. Em vez disso, sem ativá -lo, essa página não está nos primeiros resultados.
Por fim, tentei procurar "recuperação de informações" , o mecanismo de pesquisa sem CPRF foi muito ruim, o primeiro resultado é uma página de pesquisa para os departamentos da UIC, isso também é provavelmente porque não há página para recuperação de informações no domínio UIC ou simplesmente não está incluído no domínio. No entanto, com o componente inteligente, muitas páginas da web relacionadas a isso foram encontradas, duas das palavras estendidas foram "Cornelia Caragea", a professora que está ensinando esse curso, tantas páginas foram realmente relacionadas a suas publicações e seu trabalho na recuperação de informações, essa também é uma propriedade muito boa do mecanismo de busca. Caso resultados muito relevantes não possam ser encontrados, ele ainda é capaz de encontrar os melhores resultados possíveis sobre coisas relacionadas.
Conforme explicado em 5.3, quando fiz a comparação entre o mecanismo de pesquisa simples e o uso do componente inteligente, acho que os resultados produzidos foram muito bons e recebi o que esperava quando estava pensando sobre isso. As coisas boas resumidas que notei testando foram:
A capacidade de encontrar muitos outros resultados, mesmo quando a consulta original produz apenas um monte de sites.
A capacidade de encontrar o que eu estava realmente procurando como primeiros resultados, por exemplo, nas consultas "cursos de ciência da computação" , como expliquei no parágrafo 5.3.
A propriedade muito agradável de recuperar conteúdo discreto, mesmo quando o corpus não contém páginas que são muito relevantes para a consulta e, possivelmente, o que o usuário está procurando, notei isso para a consulta "Recuperação de informações", conforme explicado no parágrafo 5.3.
Uma maneira que me mostrou que isso estava produzindo os resultados corretos foi o fato de que nas 10 principais palavras em expansão representando o contexto, algumas palavras pertencentes à consulta do usuário estavam presentes. Isso mostra como o método é efetivamente capaz de capturar o tópico e não há outra maneira de descrever as outras palavras nesse conjunto, se não como palavras pertencentes ao mesmo contexto que as da consulta original.
Falando sobre a classificação da página. Eu acho que faz o seu trabalho, mas não altera muito a classificação da maneira que eu implementei, é apenas uma maneira de influenciar os resultados para preferir páginas mais autorizadas, se houver.
Com certeza, uma das coisas que deve ser abordada daqui são os hiperparâmetros ajustando. É a coisa mais difícil de fazer principalmente devido à falta de dados rotulados. Não sei saber qual valor de um parâmetro funciona melhor se não puder avaliar a precisão das consultas e, para ajustá -lo automaticamente, deve haver muitos dados já rotulados.
