Modelo de un Meta Buscador que Realiza Agrupación de Documentos Web, Enriquecido con una Taxonomía, Ontologías e Información del Usuario

Abstract

In pursuing the central theme of this Ph.D. thesis, which is effective web search, the author seeks through synergistic combination, to make the most of the different potentials of thematic indices, traditional web search engines, and meta web search engines, bypassing the weaknesses inherent in each, when they are operating in isolation. A general taxonomy of knowledge, ontologies, and user information (user profile and user feedback) are synergistically combined, together with the clustering of web results in a meta search model that brings up for the user only those results (documents) of greatest relevance, thereby reducing the time spent by users on searches. The proposed model includes five main components. The first component is responsible for supporting the query expansion of the user based on the semantic relationship (extracted from ontologies that are organized in a taxonomic hierarchy) of the terms that each user has stored in their profile. The second component is responsible for search result acquisition from traditional web search engines (Google, Yahoo! and Bing). The third component is responsible for pre-processing documents and generating two representations of them, one based on the vector space model and another based on frequent phrases. The fourth component is responsible for cluster construction and labeling, for which there are three heuristic algorithms that perform clustering based on the vector space representation of the results, and labeling based on frequent phrase representation. The fifth component is responsible for visualization of the resulting clusters, which involves the presentation of search results organized into thematic groups (folders) and updating of the user profile based on the user feedback (relevant or not relevant). The cluster construction and labeling component is supported by three new heuristic algorithms based on the following global search strategies: global-best harmony search, cuckoo search and a genetic algorithm. The K-means algorithm is employed as a local search improvement strategy in each of the algorithms. A new fitness function, called Balanced Bayesian Information Criterion guides the evolution process of these algorithms and is proposed from the genetic programming approach. A hyper-heuristic framework is also presented and used to evaluate a wide set of heuristics that can be used to solve the problem of web result clustering. The evaluation process of the model and the algorithms is based on synthetic data sets (from traditional repositories) and answers provided by a real population of users. The evaluation is supported by traditional validation metrics from the information retrieval field (precision, recall, F-measure, accuracy, and fall-out) and from user satisfaction (utility of each cluster, precision of allocation of documents in each cluster and their order, quality of labels for each cluster, and the Subtopic Search Length under k document sufficiency - SSLk- measure used for assessing the ease with which the users can use the clustering results). The results obtained are compared against results delivered by other state of the art algorithms, among them Bisecting K-means, STC and Lingo.

Resumen. Esta tesis doctoral tiene como tema central la Búsqueda Web. En ésta se aprovecha las potencialidades de los índices temáticos, los buscadores Web tradicionales y los meta buscadores, en un modelo que evita las debilidades que cada uno de ellos tiene por separado, y permite con ello disminuir el tiempo invertido por los usuarios en las búsquedas web. Para lograr esto, se combina sinérgicamente una taxonomía general de conocimiento, ontologías de dominio específico, información del usuario y agrupación de resultados (documentos) web en un modelo de un meta buscador que presenta resultados más relevantes a las necesidades de información de los usuarios y de una forma mejor organizada. El modelo propuesto contempla cinco componentes principales. El primer componente es el encargado de soportar la expansión de la consulta del usuario, basado en la relación semántica (extraída de las ontologías que se organizan en una jerarquía taxonómica) de los términos que cada usuario ha almacenado en su perfil. El segundo componente se encarga de la adquisición de los resultados desde los buscadores web tradicionales (Google, Yahoo! y Bing). El tercer componente es responsable del pre-procesamiento de documentos y genera dos representaciones de los mismos, una basada en el modelo espacio vectorial y otra en frases frecuentes. El cuarto componente se encarga de la construcción de agrupaciones y etiquetado, para lo cual se cuenta con tres algoritmos heurísticos que realizan el agrupamiento basado en la representación espacio vectorial de los resultados y el etiquetado basado en una representación de frases frecuentes. El quinto componente se encarga de la visualización de resultados, lo que implica la presentación de los resultados de la búsqueda organizados en grupos temáticos (carpetas) y la actualización del perfil del usuario basado en la re-alimentación que éste registre sobre los resultados (relevantes o no relevantes). El componente de construcción de agrupaciones y etiquetado se soporta en tres nuevos algoritmos heurísticos basados en las siguientes estrategias de búsqueda global: la mejor búsqueda armónica global, la búsqueda cucú y un algoritmo genético. El algoritmo K-means se usa para optimizar localmente las soluciones en cada uno de los algoritmos. Una nueva función de aptitud denominada Criterio de Información Bayesiano Balanceado orienta el proceso evolutivo de estos algoritmos y fue propuesta desde un enfoque de programación genética. También se presenta el modelo de un entorno híperheurístico que sirve para evaluar un conjunto mucho más amplio de heurísticas que pueden ser usadas para resolver el problema de agrupación de resultados web. El proceso de evaluación del modelo y de los algoritmos se basa en conjuntos de datos sintéticos (de repositorios tradicionales) y en respuestas entregadas por una población real de usuarios. La evaluación se soporta en medidas tradicionales del área de recuperación de información (precisión, recuerdo, medida F, exactitud y fall-out) y de satisfacción de los usuarios (utilidad de cada grupo, organización de los resultados en los grupos, calidad de las etiquetas de los grupos y la medida de longitud de búsqueda de sub tópicos mínima para encontrar k documentos relevantes -SSLk-, usada para evaluar la facilidad con la que los usuarios usan los resultados del agrupamiento). Los resultados obtenidos se comparan con los resultados entregados por otros algoritmos del estado del arte, entre ellos: Bisecting K-means, STC y Lingo.