web search engine UIC
1.0.0
Proyecto final para CS 582 Curso de recuperación de información en la Universidad de Illinois en Chicago
Para ejecutar el programa desde el terminal, solo use el comando:
python main.py
Se proporciona un informe para explicar mejor las funcionalidades y la interfaz de usuario del motor de búsqueda, consulte:
informar.pdf
Este documento es un informe para el proyecto final de recuperación de información CS 582 en la Universidad de Illinois en Chicago. El proyecto consistió en construir un motor de búsqueda web para el dominio UIC desde cero. El software se construyó modularmente, comenzando desde el rastreo web, pasando por el preprocesamiento de las páginas, indexando y finalmente agregando una interfaz gráfica de usuario. Además, un componente "inteligente" personalizado inventado por nosotros fue un requisito.
Decidí experimentar en la optimización de motores de búsqueda mediante el uso de la expansión de la consulta basada en un enfoque de retroalimentación de pseudo-relevancia que intenta obtener un contexto amplio de la consulta del usuario, lo llamé contextualidad de pseudo-retroalimentación de pseudo-relevancia ( CPRF ). Esto debería haber agregado principalmente dos tipos de mejoras al motor de búsqueda:
No concentre todos los resultados solo en las palabras en la consulta, sino que incluye contenido diverso y relacionado con el conjunto de páginas recuperado.
Ampliar el número total de resultados, incluidas las páginas web que no contienen ninguna de las palabras presentes en la consulta, pero aún pueden ser de interés para el usuario, ya que trata el mismo tema.
Una implementación de rango de página también está integrada y se puede activar o desactivar la interfaz de usuario de la aplicación. Más detalles sobre ambos componentes inteligentes se pueden encontrar más adelante en este documento.
Se puede acceder al repositorio que contiene el software a través de GitHub en:
https://github.com/mirkomantovani/web-search-ingine-uic
El software está escrito en Python3 en una moda de programación orientada a objetos para que sea fácilmente extensible para el futuro. Para facilitar la descarga y probar el código sin tener que realizar un rastreo extenso y llevo en el tiempo, el preprocesamiento de la página, el conjunto de datos que contiene 10000 páginas rastreadas desde el dominio UIC: https://wwww.uic.edu/, y las páginas preprocesadas y las páginas preprocesadas y los archivos necesarios generados (inverso inverpidos, tf-didf sfors, rango de la página, rango de documento, documentos, documentos, documentos, documentos, documentos, documentos, toquios de documento, Tokens ToKens 'ToKens ToKens' ToKENS ', Tokens ToKens', Tokens, toquios, Tokens ToKens 'ToKENS', Tokens, Tokens, Tokens ToTkens 'ToKENS' ToKENS 'TOTKENS' TOTKENS 'TOTKENS' TOTKEN Las URL) están incluidas en el repositorio. De esta manera, clonando el repositorio, el m de main.py se puede ejecutar y en menos de un segundo, el motor de búsqueda está listo para obtener consultas en la entrada. Sin embargo, los scripts para ejecutar el rastreo y el preprocesamiento también se incluyen y explican en las siguientes subsecciones con todos los demás componentes.
El rastreo web se puede hacer ejecutando el script multithithreaded_crawling.py , el rastreo ocurre en paralelo mediante el uso del módulo de cola para acceder a los recursos de manera sincronizada, el número de subprocesos se puede cambiar modificando el tiempo constante global en el mismo tiempo en el mismo script, que es 20 de manera predeterminada, sin embargo, el chequeo principal en el tiempo de coba de la coba de Internet y no es el tiempo parsante o no cualquier otro.
El rastreo comienza desde el subdominio CS UIC: https://www.cs.uic.edu/ especificado en el script multithreaded_crawling.py .
El rastreo ocurre con una estrategia de amplitud, cada página se deja, descarga y analiza utilizando la biblioteca HTMLParser , sus enlaces se extraen y se verifica para pertenecer al dominio UIC, luego se agrega a la cola FIFO si está en un formato apropiado. Una lista negra de todos los formatos malos fue derivada por mí mientras veía los resultados que estaba obteniendo en el rastreo y consiste en estos 18 formatos: ".Docx", ".doc", ".Avi", ".mp4", ".jpg", ".jpeg", ".png", ".gif", ".pdf", ".Gz" .Gz. ".tgz", ".zip", ".exe", ".js", ".css", ".ppt". Se especifica un tiempo de espera de 10 segundos como el tiempo máximo para descargar una página antes de cerrar la conexión y pasar a la página siguiente.
Las URL también se modifican después de extraer, cada HTTP inicial se convierte en un HTTPS, se eliminan todas las cortadas al final, las cadenas de consulta se eliminan y también las enlaces intra-páginas expresados por el símbolo de hash (#) también están para no dejar que el Cutler crea que más páginas con un símbolo de INPAGE diferente son diferentes urentos y por lo tanto, por lo tanto, también se eliminan las páginas diferentes. Además, el manejo de enlaces donde se abre una etiqueta <a> y se abre otra etiqueta dentro antes de cerrar href se realizó dividiendo el enlace en la apertura de otra etiqueta "<" en la cadena.
Durante el rastreo, dos diccionarios, URL del código y el código de la URL se guardan constantemente en el disco para ser utilizado más adelante, el código de una página web es el número de la página descargada en orden cronológico.
El preprocesamiento de las páginas rastreadas se puede ejecutar desde el script run_preprocessing.py , allí también puede especificar el número de páginas a considerar y el número máximo de iteraciones de rango de página cambiando las constantes correspondientes Page_Rank_Max_iter y N_Pages.
Durante el preprocesamiento, se utiliza un objeto CustomTokenizer del script Preprocess.py . Cada página se preprocesa primero recibiendo el texto sin formato en todas las etiquetas excepto <Script> y <Syle>. Para este paso, decidí usar una biblioteca muy rápida: Selectolax , que es una API de Python para usar el motor modesto escrito en C. Cpython, por supuesto, proporcionaría al menos un orden de magnitud menos en el tiempo computacional con respecto a cualquier analizador HTML escrito en Python puro. La página se tokeniza, los tokens se vadían utilizando el Porterstemmer por NLTK , las palabras de parada se eliminan utilizando la lista de palabras de parada proporcionadas en las palabras de parada del archivo.
En el preprocesamiento se construye el índice invertido y el TF-IDF de cada par de palabras de palabras se calcula y almacena en el índice invertido. También se crea un gráfico web dirigido ( gráfico ) y se alimenta a la implementación del rango de página en page_rank.py . Todos los archivos necesarios más tarde para responder a la consulta se guardan como archivos binarios.
El tiempo total tomado para el preprocesamiento y la convergencia Page_Rank para 10000 páginas fue de aproximadamente 236 segundos, el tiempo de ejecución de rango de página fue de solo unos 11 segundos.
El script Main.py contiene el punto de acceso al motor de búsqueda. Cuando se inicia el programa, se crea un objeto CustomTokenizer para tokenizar las consultas, se instancia un objeto tfidfranker para clasificar los documentos basados en las consultas.
Cuando los documentos se clasifican en función de la consulta de un usuario, se considera un máximo de 100 documentos, esta constante puede cambiarse en main.py : max_results_to_consider, otros parámetros personalizables son el número de resultados que se muestran en un momento resultados_per_page, el número de páginas para usar: n_pages.
La interfaz de usuario es gráfica e implementada utilizando el paquete Python: EasyGui. La GUI es un módulo extensible, CustomGui.py que contiene las API principales para las funcionalidades básicas del programa.
Cuando se inicia el programa, se le pregunta al usuario la configuración básica, ya sea que quiera usar el rango de página y los comentarios de pseudo-relevancia del contexto o no. Después de eso aparece el menú principal. El menú principal muestra la configuración actual del motor de búsqueda y algunos botones para las acciones principales que se pueden realizar. La configuración se puede cambiar dinámicamente en tiempo de ejecución eligiendo el botón apropiado en el menú principal. Las otras dos opciones son: dejar el programa y ejecutar una consulta. Si el usuario presiona el botón para crear una nueva consulta, aparece una nueva ventana y se le solicita al usuario que inserte una nueva consulta. Cuando hace clic bien, la consulta está preprocesada y los documentos están clasificados y los primeros 10 documentos (variables en el programa) se muestran junto con la información sobre la consulta preprocesada y posiblemente los tokens expandidos si la retroalimentación de pseudo-relevancia está activada. El usuario ahora puede hacer doble clic en un resultado para abrir la página en una nueva pestaña en el navegador predeterminado de su sistema o puede presionar recursivamente en "Mostrar más resultados" al final de la lista para mostrar 10 resultados más. Además, si la retroalimentación de pseudo-relevancia está desactivada, el usuario también tiene la posibilidad de volver a ejecutar la misma consulta con la expansión.
Después de ejecutar una consulta y decidió cancelar o abrir un resultado, se le indica al usuario al menú principal donde puede cambiar la configuración y/o ejecutar una nueva consulta o la misma con diferentes configuraciones para comparar los resultados con el obtenido previamente.
Los principales desafíos que he experimentado durante el desarrollo de este proyecto son:
Inicialmente fue realmente difícil elegir qué tipo de componente inteligente diseñar. No tengo experiencia en este tipo de aplicación y pensar en mejoras sin tener una demostración para probar es muy difícil.
Durante la parte de implementación, pasé mucho tiempo aprendiendo sobre las bibliotecas y construcciones de Python que aún no conocía, como hilos, cómo implementar o hacer raspado web para sacar los enlaces de una página HTML. Otra cosa que tenía que aprender desde cero era cómo crear una GUI en Python.
Una cosa molesta fue el hecho de que tuve que rastrear 10000 páginas más de una vez, porque encontré en las páginas varios formatos e incorrectos. Al final, toda la lista de formatos que tuve que la lista negra tenía un tamaño de 18 e incluía ".docx", ".doc", ".Avi", ".mp4", ".jpg", ".jpeg", ".png", ".gif", ".pdf", ".gz", ".Rar", ".tar", ".Tgz". ".exe", ".js", ".css", ".ppt".
Una cosa muy desafiante fue el ajuste de los hiperparámetros y la integración del rango de página para clasificar los documentos. El parámetro " E " para decidir cuánta importancia dar a los tokens de la consulta extendida es el más difícil de ajustar porque no puede conocer las actuaciones promedio de su motor de búsqueda si no tiene datos etiquetados (documentos relevantes para cada consulta). Además, la relevancia de la consulta es subjetiva, nunca se sabe lo que una persona quiere recuperar, y solo puede adivinar según la consulta. Decidí que el E debería ser como máximo 0.5 y al final lo configuré alrededor de 0.1-0.2, no desea sesgar la consulta mucho dando mucha importancia a las palabras que no escriben el usuario.
El esquema de ponderación que utilicé fue el simple TF-IDF de las palabras en los documentos, ya que se ha demostrado que es uno de los más efectivos cuando se trata de motores de búsqueda web y explica la importancia de las palabras en cada documento de la manera correcta. Ni siquiera pensé en intentar otra medida solo porque no era el propósito de este proyecto y esto parecía funcionar bien.
La medida de similitud utilizada para clasificar los documentos fue la similitud de coseno . Implementé a partir de la similitud interna del producto y cambiar a eso sería solo una cuestión de cambiar una línea de código. Creo que es mejor usar la similitud de coseno porque tiene en cuenta la longitud del documento y la longitud de la consulta. Es más complejo, y generalmente funciona bastante bien en la práctica en este tipo de aplicaciones, por lo que elegir la medida de similitud no era realmente un problema, solo sabía que la similitud de coseno era la correcta.
Hice una evaluación de la precisión en 10 (solo considerando los primeros 10 resultados recuperados) para algunas consultas aleatorias y diversas que se me ocurrió. Aquí están los resultados:
Consulta: "Tesis del asesor", el primer resultado fue https://grad.uic.edu/electronic-thesisdissertation-faqs y creo que todos los resultados estaban relacionados con tesis y cosas correlacionadas, daré una precisión: p = 1.0 a esta consulta.
Consulta: "Feria de carrera", el primer resultado fue https://ecc.uic.edu/career-fairs y creo que todos los resultados fueron algo relevantes para ferias de carrera, servicios profesionales, eventos y empleo, daré una precisión: P = 1.0 a esta consulta.
Consulta: "Asistencia de investigación", el primer resultado fue http://grad.uic.edu/assistantships y creo que todos, excepto el último, estaban relacionados con las asistentes, siendo RA, ta o Ga, solo porque el dominio UIC no tiene una página específica para RA, por lo que daré una precisión: P = 0.9 a esta consulta.
Consulta: "Pasantías y trabajos", el primer resultado fue https://careerservices.uic.edu/students/internships y esta vez solo 6 páginas web fueron relevantes, sin embargo, las que aún no estaban relacionadas con la carrera y el empleo. Daré una precisión: P = 0.6 a esta consulta.
Consulta: "Dirección del Centro Este de Estudiantes", el primer resultado fue https://fimweb.fim.uic.edu/buildingsdata.aspx, esta consulta es más específica y compleja y, de hecho, de 4 resultados, en realidad podemos extraer la dirección del edificio, todos los otros resultados, sin embargo, estaban hablando sobre el centro de estudiantes este, lo que aún no es tan malo. Daré una precisión: P = 0.4 a esta consulta.
Con una precisión promedio de 0.78 , y el hecho de que cada consulta devolvió al menos un resultado relevante, creo que los resultados son discretos.
El primer inteligente con el que experimenté fue un rango de página simple y simple. Durante el preprocesamiento de las páginas, los enlaces se extraen y se basan en las conexiones de enlace se crea un gráfico mundial. La implementación del rango de página fue tal que creó un componente fuertemente conectado con todo el gráfico, lo que significa que desde cada nodo es posible llegar a otro nodo del gráfico con una probabilidad no nula. Con esta interpretación no hay posibilidad de que un caminante aleatorio se atasque en una página.
Los rangos de la página eran un poco difíciles de integrar en la puntuación de documentos para clasificarlos. Al principio, traté de hacer una combinación lineal de similitud de coseno y rangos de página y ver cómo funcionaba y era bastante malo porque si el peso del rango de página era demasiado, la página de inicio y otras páginas autorizadas siempre aparecían en los resultados. En cambio, si el peso se inclinara más hacia la similitud del coseno, el rango de página no tendría ningún efecto.
El segundo intento produjo resultados bastante buenos. Básicamente, solo tomé los primeros 100 resultados solo usando y descarté a todos los demás y los consideré no relevantes. Luego hice la combinación lineal con Page Rank. Esta vez funcionó porque era solo una permutación diferente de los documentos ya relevantes y, por ejemplo, la página de inicio y otros documentos autorizados ya están descartados en este momento.
Creo que se logró el propósito del rango de página en este tipo de aplicación, pude sesgar una búsqueda normal para considerar páginas más relevantes más autorizadas para que el usuario tenga más probabilidades de encontrar fuentes de información buenas y confiables, además de los resultados que son muy similares a los que él escribe en su consulta.
El contexto de la pseudo-retroalimentación de pseudo-relevancia ( CPRF ) se me ocurrió esta idea de mi principio y componente inteligente personalizado casi un mes desde la implementación real. Cuando me estaba implementando, no estaba seguro de que hubiera funcionado como se esperaba y tenía mucho miedo de estar haciendo todo eso por nada.
Cuando estaba pensando en qué tipo de componente inteligente podría tener un motor de búsqueda web, pensé que sería bueno si pudiéramos adivinar el contexto de la consulta del usuario y darle además de lo que está pidiendo específicamente, algunos resultados que están muy relacionados con lo que buscó. Una expansión de consulta estática simple basada en sinónimos habría sido demasiado simple y no habría sido capaz de capturar contenidos relacionados pero que tengan una semántica diferente.
Sin embargo, el punto de partida siempre tiene que ser la consulta del usuario, ya que no hay nada más excepto eso inicialmente. Realmente me gustó la idea de cómo la retroalimentación de pseudo-relevancia pudo permitirle reformular su consulta de manera autónoma. Por supuesto, una retroalimentación de relevancia explícita cuando se le pregunta al usuario qué otras palabras desearía incluir en su consulta probablemente sería mejor, pero al mismo tiempo podría ser molesto para él tener que responder a algunas preguntas mientras buscaba. Una retroalimentación de pseudo-relevancia parece una manera más apropiada y fácil de ejecutar en segundo plano una consulta más compleja que el usuario ni siquiera está al tanto.
Para extraer algunas palabras que podrían expresar el contexto de la consulta formulada, decidí usar información intrínseca que tienen los documentos inicialmente recuperados. En particular, creo que las palabras con TF-IDF más alta en un documento podrían representar el tema de ese documento, y lo que diferencia de los demás, porque TF-IDF es alto cuando la palabra no está contenida en muchos documentos, pero es recurrente en ese documento.
El proceso para extraer las palabras de contexto es el siguiente: desde los documentos clasificados tomo documentos numeros_docs_expansion, que establecí en 30 pero podría cambiarse en pseudo_relevance_feedback.py. , para cada documento tomo los tokens con el más alto TF-IDF (constante número_top_tokens) y para cada token distinto en ellas, sumo todo el TF-IDF de esta palabra de cada documento si la palabra está presente. Al final, clasifico los tokens y las palabras mejor clasificadas son las palabras comunes de cada documento recuperado que representan el contexto de la consulta. Luego devuelve el conjunto de palabras n ampliadas (número constante_expansion_tokens), al que se restan los tokens de consulta del original para no tener repeticiones y dar demasiada importancia a esas palabras.
Los tokens ampliados tendrán un peso de diferencia, menos que las palabras originales en la consulta, este E_Const se puede cambiar en el script STATISTICS.PY .
Basado en las consultas que intenté pensar que el componente inteligente realmente ofrece algunas mejoras en algunos casos.
Los primeros grandes resultados que funciona siempre es la capacidad de expandir los conjuntos de documentos recuperados, de hecho, si solo unos pocos documentos contienen alguno de la palabra en la consulta, el motor de búsqueda simple solo recuperaría esos pocos documentos. En cambio, con el componente inteligente CPRF , los conjuntos de resultados serán mucho más grandes y posiblemente siempre conducirán a un conjunto recuperado cuyo tamaño es más de 100 documentos.
Otro resultado positivo que noté en algunas consultas es que en realidad encuentra lo que estaba buscando como primer resultado, mientras que el simple motor de búsqueda ni siquiera lo encuentra en los diez resultados principales. Se puede observar un ejemplo de esto buscando "cursos de informática" , lo que quería encontrar es una lista de todos los cursos principales ofrecidos por el Departamento de Ciencias de la Computación en UIC. Este es el primer resultado recuperado por el motor cuando el componente inteligente está activo. En cambio, sin activarlo, esa página no está en los primeros resultados.
Por último, intenté buscar "recuperación de información" , el motor de búsqueda sin CPRF fue muy malo, el primer resultado es una página de búsqueda para los departamentos de UIC, esto también es probablemente porque no hay una página para la recuperación de información en el dominio UIC o simplemente no está incluido en el dominio. Sin embargo, con el componente inteligente, se encontraron muchas páginas web relacionadas con esto, 2 de las palabras extendidas fueron "Cornelia caragea", la profesora que enseña este curso, por lo que muchas páginas estaban relacionadas con sus publicaciones y su trabajo en recuperación de información, esta también es una muy buena propiedad del motor de búsqueda. En caso de que no se puedan encontrar resultados muy relevantes, todavía puede encontrar los mejores resultados posibles sobre las cosas relacionadas.
Como se explicó en 5.3 cuando hice la comparación entre el motor de búsqueda simple y el uso del componente inteligente, creo que los resultados producidos fueron bastante buenos y obtuve lo que esperaba cuando estaba pensando en esto. Las cosas buenas resumidas que noté al probarlo fueron:
La capacidad de encontrar muchos más resultados incluso cuando la consulta original genera solo un montón de sitios web.
La capacidad de encontrar lo que realmente estaba buscando como primer resultado, por ejemplo, en las consultas "cursos de informática" , como expliqué en el párrafo 5.3.
La muy buena propiedad de recuperar contenido discreto, incluso cuando el corpus no contiene páginas que son muy relevantes para la consulta y posiblemente lo que el usuario está buscando, noté esto para la consulta "recuperación de información" como se explica en el párrafo 5.3.
Una forma que me mostró que esto estaba produciendo los resultados correctos fue el hecho de que en las 10 palabras principales en expansión que representan el contexto, algunas palabras pertenecientes a la consulta del usuario estaban presentes. Esto muestra cómo el método es efectivamente capaz de capturar el tema y no hay otra forma de describir las otras palabras en ese conjunto si no como palabras que pertenecen al mismo contexto que las de la consulta original.
Hablando de rango de página en su lugar. Creo que hace su trabajo, pero no cambia las clasificaciones demasiado en la forma en que implementé, es solo una forma de sesgar los resultados para preferir páginas más autorizadas si las hay.
Seguro que una de las cosas que debe abordarse desde aquí es el ajuste de los hiperparámetros. Es lo más difícil de hacer principalmente debido a la falta de datos etiquetados. No puedo saber qué valor de un parámetro funciona mejor si no puedo evaluar la precisión de las consultas, y para ajustarlo automáticamente, debería haber muchos datos ya etiquetados.
