Tauller Matos - Recuperação da Informação

Introdução a Recuperação de Informação

Tauller Matos

[email protected]

2

Agenda

O que é Recuperação da Informação Modelos de Recuperação da Informação

Modelo Booleano e Modelo Vetorial Índice Invertido

Stop Word

O porquê da Recuperação Textual A informação na Web tem se expandido com uma

diversidade enorme Usuário está interessado em uma pequena parcela

destas informações Necessidade de uma forma efetiva de acesso Problema / Motivação para a área de Recuperação de

Informação (RI)

3

4

O porquê da Recuperação Textual

OBJETIVO:

Encontrar (de forma eficiente) osmelhores documentos quesatisfaçam a necessidade do usuário.

Características e Conceitos Próprios A unidade de Informação é denominada TERMO

TERMO: string de caracteres Alfanumérico

Registros de dados são tratados como DOCUMENTOS Para a união dos documentos dá-se o nome de COLEÇÃO

As consultas(QUERY) são feitas por um único termo ou por composição de termos (palavra-chave)

5

Características e Conceitos Próprios RI deve de alguma forma “interpretar” o conteúdo

das informações encontradas nos documentos de uma coleção e ordená-los de acordo com um grau de relevância para o usuário. RELEVÂNCIA é a palavra central de um SRI.

RANKING: ordenação do resultado de acordo com a consulta e o grau de relevância para o usuário

6

Recuperação de dados X Recuperação da Informação

Ação R. Dados R. Informação

Objetos Tabelas Documentos

Comparação Exata Aproximada

Dados Estruturados Não Estruturados

Modelo Determinístico Probabilístico

Esp. Consulta Completa Incompleta

7

8

Definição RI

É uma tarefa de encontrar informações relevantes de uma natureza não estruturada, que satisfazem uma necessidade de informação [Manning et al., 2009]

Recuperação de Informação lida com a representação, armazenamento, organização e acesso a itens de informação (documentos).

Problema: caracterização da necessidade de informação do usuário. Considere uma busca na Web

Imagine que o interesse do usuário seja por documentos (páginas) contendo informações sobre times de futebol do Brasil: que tenham convênios com empresas privadas participem de torneios nacionais conter informações sobre a classificação deste time no âmbito

nacional e regional o endereço e telefone de contato

9

10

Modelos de Recuperação de Informação Baseados na comparação de palavra-chave com os

documentos armazenados Diversos modelos existentes

A maioria são de natureza quantitativa baseada em modelos matemáticos (lógica, estatística e teoria dos conjuntos)

11

Modelo Booleano

Baseado na teoria dos conjuntos Simples de implementar e usar, porém de baixo

desempenho Documentos e consultas são representados como

vetores binários de tamanho n (ex.,D={1,0,1,1,1}) Cada posição corresponde a um termo usado na indexação

do documento A representação indica apenas se o termo está ou não

presente no documento

12

Consultas no modelo booleano Consulta: termos conectados por AND, OR e NOT Atlético Atlético AND Mineiro Atlético OR Mineiro Atlético NOT Mineiro

Qual o resultado desta consulta? Não existe a noção de “casamento” parcial com

as condições da consulta Atlético AND Mineiro AND Brasil AND América do Sul

Qual o resultado desta consulta?

13

Modelo Booleano – Observações Importantes Semântica precisa do modelo

O documento é considerado relevante ou não relevante a uma consulta

A quantidade de documentos recuperados pode sofrer uma variação muito grande Exemplo:consulta OR versus And

Não gera informações suficientes para ordenação das consultas

É muito mais utilizado para recuperação de dados do que para recuperação de informação

14

Modelo Booleano

Vantagens Expressividade completa se o usuário souber exatamente o

que quer. É facilmente programável e exato.

Desvantagens Pessoas lidam com conhecimento parcial. Saída pode ser nula, ou haver overload (problema que dá

um falso senso de segurança). Saída não é ordenada

15

Estratégia de Recuperação do Modelo Booleano Lista de palavras da consulta versus Lista de palavras

dos documentos Em grandes coleções essa comparação se torna

computacionalmente cara Vamos a um exemplo: suponha uma coleção com 1 milhão

de documentos e 500.000 termos. Então teremos uma matriz termo-documento: 500.000 X 1.000.000

Uma melhor representação seria gravar somente os termos que ocorrem, ou seja, os valores igual a 1.

16

Exemplo

Busca pelo termo tradicional

17

Doc1

Recuperação de Informação

Doc2

Recuperação de Imagens, recuperação

Doc1


Doc1


Doc1


Presente: Doc1

Doc2


Presente: Doc1 e Doc2

Ok! Fácil né? Agora faça isto para 1 milhão de documentos

Índice Invertido ou Arquivo Invertido Possui 2 partes principais:

Uma estrutura de busca, chamada de vocabulário, contendo todos os termos distintos existentes nos textos indexados

E para cada termo, uma lista invertida que armazena os identificadores dos documentos que contenha o termo, a saber, documentos onde o termo ocorre

18

19

Índice Invertido – Parte um

Doc1


Doc2


Termo DocID

recuperação 1

Doc1


Doc1


de 1

Doc1


informação 1

recuperação 2

de 2

imagens 2

Termo DocID

Doc2


Doc1


Doc2


Doc2


1

de 1

imagens 2

de 2

informação 1

recuperação 1

recuperação 2

2

Termo DocID Freq.Termo

Doc2


recuperação 2 recuperação 2

de 1 1

de 2 1

imagens 2 1

informação 1 1

recuperação 1 1

recuperação 2 2

20

Índice Invertido – Parte dois

Termo DocID Freq.Termo

de 1 1

de 2 1

imagens 2 1

informação 1 1

recuperação 1 1

recuperação 2 2

Termo Freq.Termo lista invertida

de 2 1, 2

imagens 1 2

informação 1 1

recuperação 3 1, 2

Dicionário Lista Invertida

Doc1 = [recuperação, de, informação]Doc2 = [recuperação, de imagens, recuperação]

Coleção

21

Stop Words – Palavras comuns São palavras extremamente comuns e semanticamente

não seletivas Exemplo

Artigos, preposições, conjunções, etc

Geram grandes listas invertidas difíceis de processar Exclusão do dicionário

Regra dos 30 Uma relação de stop words para o português do Brasil é

proposta por [Balinski,2002] Já em [Frakes and Baeza-Yates, 1992] encontra-se a lista da

língua inglesa, juntamente com o algoritmo para detecção destes termos comuns

Peso do Termo Até o momento consideramos apenas a presença ou

ausência do termo no documento Problemas! Número elevado de documentos...

Surge a necessidade de se criar um Ranking dos documentos, no qual os documentos mais similares à consulta apareçam nas primeiras posições

Uma abordagem para construção desse ranking é considerar a importância de um termo no documento com base na frequência com que o termo ocorre no documento e na coleção. Como fazer isto?

22

23

Peso de um Termo no Documento Frequência do termo (tf)

Atribuir um peso igual ao número de ocorrências do termo t no documento d É denotado por tft,d

Problema: Todos os termos presentes na coleção com a mesma frequência são considerados igualmente importantes

Frequência de documentos (df) Número de documentos da coleção que o termo t ocorre

Exemplo

onde cf (Frequência na coleção) e df (frequência de documentos)

24

Termo cf df

Recuperação 15.613 5.976

Seguro 15.600 13

25

Peso do Termo

Frequência Inversa do Documento (IDF)

onde N é o número total de documentos da coleção e dft é o número de vezes que o termo ocorre na coleção

TF reflete características intra-documento IDF dá uma medida de distinções inter-documentos

Abordagem tf-idf

Exemplo 2

onde cf (Frequência na coleção) e df (frequência de documentos)

Suponha que N seja igual = 6000

Cálculo do idft para o termo Recuperação = 0,001

Cálculo do idft para o termo Seguro = 2,664

26

Termo cf df

Recuperação 15.613 5.976

Seguro 15.600 13

Visualização do documento

Neste momento, pode-se observar cada documento como um vetor onde cada índice corresponde a um termo, juntamente com o seu peso dado pela equação idft

Exemplo: Doc1[0.1, 0, 1.8]

27

Doc1


28

Modelos Clássicos - Vetorial

Vetorial Modelo Algébrico Facilidade para calcular a similaridade com eficiência Gera um ordenação dos documentos (ranking) Bom desempenho em coleções genéricas

O resultado é ordenado de acordo com o grau de relevância (similaridade)

No modelo vetorial um documento é recuperado mesmo se ele satisfazer a consulta parcialmente

Modelo Vetorial

Representação gráfica de um documento Doc1 com termos de indexação t1 e t3 , com pesos 0.7 e 0.6, respectivamente

29

Modelo Vetorial

Representação gráfica de um documento tridimensional doc2 com três termos, t1, t2, t3, com pesos 0.6, 0.8, 0.5 respectivamente

30

Modelo Vetorial Os dois documentos são representados em um mesmo

espaço vetorial. É interessante lembrar que, os termos que não estão presentes em um determinado documento recebem peso igual a zero

31

32

Representação de uma expressão de busca em um espaço vetorial

33

Cálculo da Similaridade – Coseno É a correlação entre os vetores que representam a

consulta e as imagens do banco de dados

onde: q é o vetor de termos da consulta d é o vetor de termos do documento Wqi é o peso do termo i da consulta q Wdi é o peso do termo i no documento d

Exemplo

34

Portanto, o grau de similaridade entre o Doc1 e Doc2 é igual a 0.70 ou 70%.

Portanto a expressão eBusca1 possui um grau de similaridade de 67% com o Doc1 e de 94% com o Doc2.

Modelo Vetorial

Vantagens: Facilidade para calcular a similaridade com eficiência Comporta-se bem em coleções genéricas

Desvantagens: Não é considerado o relacionamento existentes entre os

termos

35

Medidas de Avaliação

As 2 medidas mais utilizadas são Precisão e Revocação

Precisão (precision): a quantidade de documentos relevantes recuperados pelo sistema, divididos pelo número total de documentos recuperados.

Exemplo: Recuperou-se 12 documentos e destes 6 apenas foram relevantes, a precisão é de 50%

36

Medidas de Avaliação

Revocação (recall): número de documentos relevantes recuperados pelo sistema dividido pelo número total de documentos relevantes existentes

Exemplo: seguindo o exemplo, caso fossem recuperados 12 documentos e destes 6 apenas fossem relevantes e o total de documentos relevantes da coleção fossem 10 então a revocação seria de 60%

37

Coleção Trec

http://trec.nist.gov/

38

Bibliografia Baeza-Yates, R. A. and Ribeiro Neto, B. A. Modern

Information Retrieval. Addison-Wesley. Essex, UK.1999

Balinski, R. Filtragem de informações no ambiente do direto. Master’s thesis, Universidade Federal do Rio Grande do Sul. (2002)

Frakes, W. B. and Baeza Yates, R. Information Retrieval: Data Structures and Algorithms. Prentice-Hall. 2002

39

Bibliografia

Manning, C., Raghavan, P., and Schütze, H. Introduction to information Retrieval. Cambridge University Press, Cambridge, England. 2009

Link para download http://nlp.stanford.edu/IR-book/information-retrieval-book.html

40

41

Perguntas

Obrigado pela atenção!

Documents

Tauller Matos - Recuperação da Informação