Organización de resultados de búsqueda mediante análisis formal de conceptos

Resum

En este trabajo se presenta una aproximación para la organización de resultados de búsqueda mediante Análisis Formal de Conceptos (AFC), aplicable a escenarios de Recuperación de Información (RI) tales como la búsqueda web. Este trabajo aborda cuatro aspectos principales: La definición de un modelo de clustering basado en AFC. La aplicación de esta teoría presenta las ventajas de permitir herencia múltiple sobre los clusters obtenidos y de realizar la descripción de los mismos de manera automática. Además, incluimos la noción de nodo de información con el fin de obtener estructuras de clustering que consideren una aproximación basada en un Universo Abierto para los documentos agrupados La definición de una metodología orientada a la aplicación del modelo sobre escenarios de RI reales. Para cada uno de los procesos involucrados en la construcción del clustering proponemos una serie de alternativas. Debemos destacar el uso de n-gramas para la descripción de los clusters, el uso de un algoritmo balanceado en el proceso de selección de descriptores para minimizar la población de documentos en el cluster raíz o la aplicación de Latent Semantic Indexing (LSI) para detectar relaciones descriptor-documento no explícitas. La definición de paradigmas para la visualización e interacción sobre las estructuras de clustering. El uso de retículos para representar la información agrupada complica el proceso de visualización ya que los paradigmas habitualmente utilizados para representar estructuras de clustering no resultan adecuados. En este trabajo se presentan dos aproximaciones al problema de la visualización cuya característica principal es la de explotar la estructura intrínseca de los retículos obtenidos. La visualización basada en retículos toma como punto de partida los diagramas de Hasse pero reduce el número de clusters visualizados por el usuario en cada momento. De este modo, únicamente se muestran aquellos clusters que, por ser más próximos al cluster que se está inspeccionando, podrían resultar útiles para refinarlo o generalizarlo. En segundo lugar, se propone una visualización basada en directorios web que, aprovechando un paradigma sobradamente conocido por los usuarios, permite mapear la estructura de un retículo de manera sencilla. La definición de un conjunto de medidas de evaluación orientadas a evaluar automaticamente la calidad, en una tarea de RI, de un sistema de clustering basado en retículos. Estas medidas están basadas en los conceptos de área de navegación mínima (MBA) y de coste cognitivo. El primero representa el conjunto mínimo de clusters y enlaces que el usuario debe recorrer para acceder a toda la información relevante recuperada. El coste cognitivo permite introducir en las medidas de evaluación una estimación del esfuerzo que el usuario debe realizar para considerar como relevante un determinado item (un cluster o un documento) en base a su descripci ón. El factor de destilación (DF) únicamente tiene en cuenta el coste cognitivo asociado a la exploración de los documentos y, por lo tanto, no refleja el esfuerzo asociado a explorar el clustering. Esta medida informa acerca del grado de mejora de precisión del retículo con respecto a la lista ordenada de documentos. La calidad del clustering (CQ), sin embargo, extiende la medida anterior al incluir el coste cognitivo asociado a considerar las descripciones de los clusters, lo que permite evaluar de manera mucho más precisa la influencia de la estructura de clustering en el proceso de RI. Finalmente, y con el objeto de demostrar la viabilidad de nuestra propuesta, así como de las medidas de evaluación, hemos desarrollado cuatro prototipos de los que tres de ellos han sido evaluados automáticamente. Los tres prototipos realizan el proceso de clustering sobre la colección de noticias EFE94. Esta colección ha sido utilizada en distintas campañas CLEF (Cross Language Evaluation Forum) y dispone de un amplio conjunto consultas con juicios de relevancia asignados manualmente por expertos. Debemos destacar que, en todos los experimentos realizados, los resultados obtenidos generaron estructuras de clustering cuyos valores de calidad (que mejoraban notablemente la precisión inicial de la lista de documentos recuperada) justificaban la realización del proceso de clustering. El primero de los prototipos describe los clusters utilizando unigramas y lleva a cabo su selección mediante las aproximaciones tf-idf y terminológica. Debemos destacar como resultado relevante que el hecho de aumentar el número de descriptores no mejora proporcionalmente la calidad del clustering. En el segundo prototipo experimenta con sintagmas terminológicos para describir los clusters y utiliza un algoritmo balanceado como estrategia de selección. Como resultados destacables debemos remarcar la mejora sustancial del algoritmo de selección balanceado frente al algoritmo terminol ógico (204.3% para la medida DF), así como capacidad para concentrar una gran cantidad de documentos no relevantes en el cluster raíz. El tercer prototipo utiliza n-gramas para describir los clusters y aplica la estrategia de selección balanceada. Los resultados obtenidos demuestran que la aplicación de LSI mejora la calidad del clustering, aunque no de manera significativa (un 9.5% con respecto a la misma aproximación sin considerar LSI). El uso de snippets, por otro lado, disminuye levemente la calidad de las estructuras de clustering generadas, aunque su capacidad para agrupar correctamente la información relevante (mejora la precisión con respecto a la lista inicial de documentos en un factor 3;48) nos permite concluir que es una aproximación adecuada. De hecho, este resultado permite mostrar la validez de toda nuestra propuesta para ser implementada en sistemas on-line que obtengan los resultados de búsqueda de sistemas comerciales, generando de manera efectiva las estructuras de clustering. El sistema Jbraindead, presentado como prototipo final de este trabajo, lo demuestra.