Recuperación de Información y el modelo de Espacio Vectorial

43 %
57 %
Information about Recuperación de Información y el modelo de Espacio Vectorial

Published on January 19, 2008

Author: alfonsoeromero

Source: slideshare.net

Description

Una introducción muy somera

Recuperación de Información: el Modelo de Espacio Vectorial Alfonso E. Romero Departamento de Ciencias de la Computación e I. A. aeromero@decsai.ugr.es - http://decsai.ugr.es/~aeromero

1. Introducción

Motivación Por qué es importante saber cosas de Recuperación de Información? ● Sapere aude ● Aplicación profesional ● Mueve mucho dinero

¿Qué es eso de la “Recuperación de Información”? Pero, ¿sabe usted que aún cuando hace ya varios meses que mantengo al día el diario [en un fonógrafo], nunca me preocupé de cómo podría encontrar cualquier parte en especial de él que deseara examinar? —Dr. Seward. Drácula, de Bram Stoker, 1897. Alfonso E. Romero – Recuperación de Información: el Modelo de Espacio Vectorial 2006-06-01 4

¿Qué es eso de la “Recuperación de Información”? El avance de la tecnología implica que cada vez hay más información almacenada. Estudiar Recuperación de Información es tratar con métodos con los que un usuario acceda eficientemente a la información, de forma efectiva, según sus necesidades. La Recuperación de Información trata de la representación, almacenamiento, oganización y acceso de ítems de ítems de información Gerard Salton, uno de los padres de la R.I. Alfonso E. Romero – Recuperación de Información: el Modelo de Espacio Vectorial

¿Qué entidades aparecen en la R.I.? Necesidad de Información Wizard Glass (consulta) Información (documentos) - La Torre Oscura IV - “The Wizard” Resultado Usuarios Alfonso E. Romero – Recuperación de Información: el Modelo de Espacio Vectorial

Sistemas de Recuperación de Información El objetivo de los Sistemas de Recuperación de Información (SRI) es, dada una colección de documentos y una consulta formulada por un usuario en un cierto momento, proporcionar el subconjunto de documentos que es más relevante para la consulta del usuario. Funcionamiento de un SRI: 1. El usuario introduce una consulta en el sistema. Esta consulta representa sus necesidades de información. 2. El sistema procesa dicha consulta. Se buscan documentos que, de alguna forma, sean coincidentes con los términos que aparecen en dicha consulta. 3. El sistema muestra los documentos que son coincidentes con la consulta, ordenándolos de mayor a menor relevancia según el valor proporcionado por una función de ranking. Alfonso E. Romero – Recuperación de Información: el Modelo de Espacio Vectorial

Modelos de Recuperación de Información Un Modelo de Recuperación de Información [Baeza] es una cuádrupla (D,Q,F,R(qi,dj)): 1. D es un conjunto formado por la representación de los documentos. 2. Q es un conjunto formado por consultas, es decir la representación de la información que el usuario necesita. 3. F es un marco o modelo de representación de los documentos, las consultas, y las relaciones existentes entre ellos. 4. R(qi,dj) es una función (ranking) que asocia un número real a cada consulta qi de Q y representación del documento dj de D. Alfonso E. Romero – Recuperación de Información: el Modelo de Espacio Vectorial

La representación de documentos (y consultas) ● La representación clásica de documentos: “bag of words”. ● Términos índice independientes unos de otros ● Para cada par término documento (t d ) un peso w(i,j) i, j ● Los documentos se indexan previamente ● Eliminar stopwords y signos de puntuación ● Case Folding ● Stemming ●Se disponen de estructuras (en disco) con documentos procesados, con pesos precalculados y de acceso rápido ● Las estructuras se crean una sola vez (indexación). Alfonso E. Romero – Recuperación de Información: el Modelo de Espacio Vectorial

La representación de documentos (y consultas) II Verde que te quiero verde, verde viento, verdes ramas verde quer verde verde viento verde rama [ (verde, 4), (quer, 1), (viento,1), (rama, 1)] 4 1 1 1 ¡Puedo representar cada documento como una n-tupla (vector n dimensional), donde cada casilla (dimensión) corresponde a cada uno de los n términos de la colección y cada coordenada i (número), al “peso” del término i-ésimo en el documento. Alfonso E. Romero – Recuperación de Información: el Modelo de Espacio Vectorial

2. El Modelo de Espacio Vectorial

Motivación del modelo Según la representación anterior de los documentos, una consulta también puede representarse como un vector (con 0 en los términos que no aparecen en ella, 1 si aparecen). La presencia de objetos (documentos y consultas) en un “espacio” hace preguntarse fácilmente si no hay una cierta forma de medir distancias en dicho espacio y que sea válida para nuestro propósito. Dicha forma debe de cumplir: 1. Quiero que un documento relevante tenga el mayor número de términos coincidentes entre consulta y documento. 2. Un documento respuesta “ideal” a una consulta es el que contiene todos los términos de la búsqueda. 3. Dentro de todos los documentos ideales, preferimos aquellos en los que los términos buscados aparezcan más veces. Alfonso E. Romero – Recuperación de Información: el Modelo de Espacio Vectorial

Descripción del modelo I ● Salton y McGill en el sistema SMART (1971) ● Calculan la similaridad entre la consulta y cada uno de los documentos como el ángulo entre el vector consulta y cada uno de los vectores de los documentos. ● Los documentos más “paralelos” a la consulta serán aquellos que “respondan” mejor a la misma. G. Salton, padre de la R.I. Alfonso E. Romero – Recuperación de Información: el Modelo de Espacio Vectorial

Descripción del modelo II Gráficamente - En el gráfico, d1 “responde” mejor a la consulta que d2. - Las coordenadas con valor distinto de 0 para el vector consulta son muy pocas: sólo tenemos que realizar operaciones para ellas. - La forma de calcular la relevancia está expresada aquí (ángulo entre dos vectores): n      〈 q , di 〉   ∑ j=1 w j, q⋅w j, i R  q , di =cos q , di = = ∣q∣ ∣d i∣ ⋅ n n w j,q⋅∑ j=1 w2 i 2 ∑ j=1 j, Alfonso E. Romero – Recuperación de Información: el Modelo de Espacio Vectorial

Esquema de pesos ¿Cómo medir la importancia de un término en un documento? 1. A mayor frecuencia de un término en un documento, mayor importancia. Problema, documentos extensos. Normalizar: ni , j tf i , j = maxk n k , j 2. Los términos más infrecuentes en la colección son más importantes, pues discriminan antes. Definimos la “rareza” de un término como su frecuencia inversa documental, o idf: N idf i=log Ni 3. Defino el peso de un término i en un documento j como el producto de ambos términos (esquema TF x IDF): w i , j = tf i , j⋅idf i Alfonso E. Romero – Recuperación de Información: el Modelo de Espacio Vectorial

Análisis crítico del modelo + Recuperación “ordenada” (si un documento se devuelve antes que otro, es más relevante). + Acoplamiento “parcial” (el documento más relevante no tiene por qué contener todos los términos de la consulta). Incluso, no tendria por qué haber ningún documento así, aunque hubiera documentos relevantes. + Comparado con otros modelos de recuperación funciona bastante bien (difícil de superar). - El esquema TF x IDF es intuitivo (pero no formal) - Asume independencia de los términos (bag of words). Alfonso E. Romero – Recuperación de Información: el Modelo de Espacio Vectorial

3. Implementando el modelo

Introducción a la implementación de un SRI ●Una colección de documentos (p. ej. páginas web) no está preparada para realizar directamente operaciones de R.I. ● Por ejemplo: encontrar la lista de páginas que contengan: “Fernando”, “Alonso”, “McLaren”, “Hamilton” ● No es lógico pensar que la búsqueda se haga linealmente. Las colecciones actuales de documentos tienen GBs (¡o TBs!). Con las tasas de transferencia actuales, despreciando el tiempo de cómputo, y suponiendo que los datos son secuenciales, en una colección de 10 GB habría que hacer varias búsquedas de 10 segundos (y en la realidad sería bastante más). ●Necesitamos crear estructuras persistentes que permitan acceder eficientemente a los datos ya procesados. Alfonso E. Romero – Recuperación de Información: el Modelo de Espacio Vectorial

Estructuras de Datos: el índice invertido ● Similar al índice terminológico de un libro. ● Para cada término, tenemos la lista de (páginas) identificadores de documentos, en los que aparece. (también puede dar la lista de pesos de cada término en cada documento). ● Se construye una sóla vez, durante el proceso llamado indexación. ● Obviamente, el índice puede no caber en memoria (tiene un tamaño del mismo orden que el de la colección), por lo que se divide en dos partes: - Vocabulario: que contiene la lista de términos - Ocurrencias: que es una tabla con las listas de documentos (y los pesos). ● Cada entrada en el vocabulario contiene la dirección en disco donde se encuentra su ocurrencia. Así, el vocabulario se puede mantener en memoria (10 MB por cada 300 MB de colección) Alfonso E. Romero – Recuperación de Información: el Modelo de Espacio Vectorial

Construcción de índices invertidos ●La construcción del índice, al no caber en memoria, no es sencilla. Normalmente, se realiza en dos pasos: 1. Obtención (a disco) de las tuplas (t, d, f(t,d), w(t,d)) (todas con el mismo d para cada documento). Estarán ordenados por d. 2. Utilizando un algoritmo de ordenación externa, ordenar por t. 3. Una vez ordenado el archivo de tuplas, ir leyendo todas las tuplas de un mismo t y crear la ocurrencia correspondiente. ● Obviamente, se puede añadir información sobre la posición de las palabras en el texto (para hacer consultas por proximidad; con “comillas”). ● Por otra parte, el vocabulario debe permitir búsqueda O(1) por identificador, y O(log n), por cadena (n el número de términos). ●Una buena referencia para los algoritmos de indexación (y en general, las estructuras de datos es el libro Managing Gigabytes). Alfonso E. Romero – Recuperación de Información: el Modelo de Espacio Vectorial

Implementación del algoritmo de recuperación Algoritmo: 1. A = {} (array asociativo de identificadores de doc.) 2. Para cada término t de la consulta Obtener la dirección de su ocurrencia L(t) Leer la ocurrencia L(t) de disco Para cada par (d, wd,t) en L(t) Si A[d] ∉A, iniciar A[d] a 0 y añadirlo al conjunto A A[d] = A[d] + wd,t 3. Para cada A[d] de A, normalizar A[d] = A[d] / Wd 4. Devolver al usuario los r mejores documentos Alfonso E. Romero – Recuperación de Información: el Modelo de Espacio Vectorial

4. Para saber más...

Libros http://www.dcs.gla.ac.uk/Keith/Preface.html ¡GRATIS! Alfonso E. Romero – Recuperación de Información: el Modelo de Espacio Vectorial

Más libros Alfonso E. Romero – Recuperación de Información: el Modelo de Espacio Vectorial

FIN Gracias por vuestra atención (¿preguntas, consultas, sugerencias?)

Add a comment

Related presentations

Related pages

rivendel.org

Recuperar información con el Modelo de Espacio Vectorial . ... La recuperación de información es el proceso ... y una necesidad de información ...
Read more

Modelo de espacio vectorial - Wikipedia, la enciclopedia libre

En el área de recuperación de información normalmente ... y el valor asignado a cada ... mediante el modelo espacio vectorial se pueden explotar ...
Read more

Modelo de Espacio Vectorial - MODELOS DE RECUPERACION DE ...

Modelo de Espacio Vectorial. En el modelo de espacio vectorial, los documentos y las búsquedas se interpretan ... modelo, recuperación de información, ...
Read more

Modelo Espacio Vectorial - ResearchGate

En el modelo Espacio Vectorial, ... el sistema SMART de recuperación de información. ... Léxica Mediante Información Contextual y el Modelo del ...
Read more

Recuperación de Información | Sistemas de Información y ...

Conocer acerca Recuperación de Información y ... Información y el modelo de Espacio Vectorial. ... Información y el modelo de Espacio
Read more

Diseño de un motor de recuperación de la información para ...

... motor de recuperación de información, basado en el modelo ... basados en el modelo del espacio vectorial fue ... y modo. Modelo vectorial: ...
Read more

Recuperación de Información y el modelo de Espacio Vectorial

Una introducción muy somera. Toggle navigation. BUSINESS; EDUCATION; TECHNOLOGY; TRAVEL; MORE TOPICS; Sign up
Read more

MODELOS DE RECUPERACIÓN DE INFORMACIÓN

En el modelo de espacio vectorial, ... Ontología sobre economía y recuperación de información. Ontología sobre economía y recuperación de información;
Read more

Modelo vectorial - Modelos de recuperación de información

El modelo vectorial es un modelo de recuperación de información ... en un espacio n ... y probabilístico, el modelo vectorial es ...
Read more