Aula 02 - Recuperação da Informação / Modelos de Sistemas de Recuperação

1

Recuperação de Informação

Modelos de Recuperação de Documentos

Renato Fernandes Corrêa

22

Sistemas de RI

Um sistema automático para RI pode ser visto como� a parte do sistema de informação responsável pelo

armazenamento ordenado dos documentos em um banco de dados,

� e sua posterior recuperação� para responder a consulta do usuário.

Etapas principais na construção:� Aquisição (seleção) dos documentos� Preparação dos documentos� Indexação dos documentos

� Armazenamento

� Recuperação� Busca (casamento com a consulta do usuário)� Ordenação dos documentos recuperados

33

Etapa 1: Aquisição (seleção) de Documentos

Manual para sistemas gerais de RI� Por exemplo, sistemas de bibliotecas

Automática para sistemas na Web� Uso de crawlers, spiders ou robots

� Programas que navegam pela Web e fazem download das páginas para um servidor

� Partem de um conjunto inicial de links� Executam busca em largura ou em profundidade

� Robot do Google� Executa em várias máquinas em paralelo� Indexou 26 Milhões de páginas em 8 dias

44

Etapa 2: Preparação dos Documentos

Objetivo� Criar uma representação computacional do documento

seguindo alguma visão lógica do documento

Tarefas� Operações sobre o texto� Criação da representação

Exemplo: bag-of-words

“Se o desonesto soubesse a vantagem de ser honesto, ele seria honesto ao menos por desonestidade.”

Sócrates

Doc original

desonesto / soubesse /vantagem / honesto /seria / honesto /menos/desonestidade/socrates

honesto 2desonesto 1soubesse 1vantagem 1seria 1menos 1desonestidade 1socrates 1

Operações de TextoRepresentação

Doc : www.filosofia.com Doc : www.filosofia.comDoc : www.filosofia.com

55

Etapa 3: Indexação dos Documentos

Construção da base de índices

Objetivo:� facilitar busca dos documentos no repositório digital

Opção mais simples: � Varrer o texto completo

� Busca seqüencial on-line� Eficaz para textos pequenos ou muito voláteis

Para bases maiores: � Indexar os documentos a partir das palavras-chaves

� Índices invertidos� Vetores e árvores de sufixos� Arquivos de assinatura

6

IndexaçãoÉ o processo de atribuir termos ou códigos de indexação a um registro ou documento, termos ou códigos esses que serão úteis na recuperação do documento ou do registro.

A atribuição dos termos de indexação pode ser feito automaticamente ou pelo homem. � Os termos de indexação podem ser extraído de uma lista-

padrão (vocabulário controlado) ou um tesauro instalado no computador com base na ocorrência de palavras contidas no documento.

� Uma outra alternativa será a indexação feita pelo homem com base no julgamento subjetivo que fazem acerca do conteúdo do documento.

7

IndexaçãoOs termos podem ser extraído de uma lista controlada ou poderão ser livres de controle.� Vocabulário controlado (gera índices)� Termos livres (gera índices)

8

Etapa 4: ArmazenamentoOs sistemas de recuperação da informação utilizam o próprio computador para armazenar (através das bases de dados) tanto os arquivos de documentos quanto os arquivos de índices.

99

Etapa 5: Recuperação/Busca

Seleção dos links dos documentos da base que satisfazem uma consulta

Consultas simples� Recuperam links dos documentos onde a palavra

ocorre pelo menos uma vez

Consultas compostas (booleanas) � Recuperam links dos documentos onde cada palavra

da consulta ocorre pelo menos uma vez � Combina as listas de documentos recuperados de

acordo com o operador booleano da consulta

10

CIn-UFPE

10

Etapa 5: Recuperação/Ordenação

Ordena os links dos documentos recuperados de acordo com sua relevância em relação à Consulta

Relevância é difícil de medir� Mede-se a similaridade entre cada documento e a consulta

Modelo Booleano� O documento é relevante ou não, não permite ordenar.

Modelo Espaço Vetorial� Similaridade é proporcional ao co-seno do ângulo entre o

vetor que representa o documento e o vetor da consulta� Tende a retornar documentos pequenos

Google� Proximidade das palavras da Consulta no documento� Tamanho da fonte, texto de links, ...� PageRank

11

Modelos de Recuperação de Informação

Existe uma distinção entre:� A tarefa do usuário

� Recuperação ou browsing� A visão lógica dos documentos

� sua representação no sistema � O modelo de recuperação de informação

� Clássico ou estruturado

Obs.: � as figuras que se seguem foram copiadas dos slides do prof. Berthier Ribeiro-Neto, na sua homepage

Tarefas e Modelos de Recuperação de Informação

Listas não-sobrepostasNós proximais

Modelos Estruturados

Recuperação: AdhocFiltragem

Browsing

TAREFA

DO

uSUÁRIO

Modelos Clássicos

BooleanoEspaço vetorialProbabilista

Teoria dos conjuntos

FuzzyBooleano estendido

Probabilista

Redes de inferênciaRedes de crença

Algebrico

E. V. generalizadoSemântica Latente

Redes Neurais

Browsing

PlanoEstruturadoHipertextual

13Tarefa do usuárioRecuperação ad-hoc

Recupera os mesmos documentos para todos os usuários que digitarem as mesmas consultas (queries)

Coleção de

documentos

Q2

Q3

Q1

Q4Q5

14Tarefa do usuárioRecuperação com filtragem

Recupera documentos considerando o perfil do usuário como consulta

Base de documentos (Corpus)

Perfil do usuário 1

Docs para usuário 1

Docs para usuário 2

Perfil do usuário 2

15

Representação do DocumentoVisão Lógica

Cada documento do corpus pode ser representado por:� um conjunto de termos (ou palavras) que melhor representam seus tópicos� geralmente, substantivos e verbos

� seu texto completo� todos os termos que aparecem no documento, incluindo artigos, preposições,...

� seu texto completo + estrutura � títulos, fonte (negrito, itálico), hiperlinks...

Quadro Geral

Termos

Texto

completo

Texto completo +

Estrutura

Recuperação

Modelos Clássicos

Modelos Clássicos

Modelo Estruturado

Browsing

Plano

Plano

Hipertexto

Estruturado Hipertexto

Visão Lógica dos documentos

17

Modelos Clássicos de Recuperação de Documentos

Modelos baseados em teoria dos conjuntos� Modelo Booleano � Modelo booleano estendido� Modelo fuzzy

Modelos algébricos� Modelo Espaço Vetorial� Variantes do modelo espaço vetorial

� Espaço vetorial generalizado� Semântica Latente

� Redes Neurais

Modelos Probabilistas

18

Modelos Clássicos de Recuperação de Documentos

Veremos os seguintes modelos:� Modelo Booleano � Modelo Espaço Vetorial

Para cada modelo, veremos:� A representação do documento � A representação da consulta� A noção de relevância dos documentos em relação à consulta utilizada na recuperação� pode ser binária (sim/não) ou ordenada� depende do modelo de recuperação utilizado

19Modelo BooleanoRepresentação do documento

Dado o conjunto de termos representativos para o corpus em questão (Vocabulário do Sistema)� V = {t1, t2,...,tn}

Os documentos são representados como conjunto de termos de indexação, sendo tais conjuntos representados como vetores de pesos binários de tamanho n� Cada posição no vetor corresponde a um termo usado

na indexação dos documentos da base� Cada valor indica apenas se determinado termo está

ou não presente no documento

Por exemplo: d1 = {1,1,0} � documento d1 contém os termos t1 e t2, e não contém o

termo t3

20

Modelo BooleanoRepresentação da consulta

Consulta: � Termos conectados por AND, OR e/ou NOT � Exemplo: t1 AND (t2 OR not t3)

A consulta é transformada, para facilitar o casamento entre documento e consulta, em vetores (componentes) que a tornam verdadeira� Exemplo acima: (1,1,1) , (1,1,0) ,(1,0,0)

Documento casa com a consulta se ele casa com algum dos componentes da consulta� O documento d1 = {1,1,0} casa com a consulta

21Modelo BooleanoRelevância

Relevância “binária”:� O documento é considerado relevante se e somente

se seu “casamento” com a consulta é verdadeiro� Não é possível ordenar os documentos recuperados

Exemplo de consulta

Consultat1 AND t2 AND t3

Documentos apresentados ao usuário

t1 t2

t3

Base de Documentos

22

Modelo Booleano

Vantagens� Modelo simples baseado em teoria bem fundamentada� Fácil de entender e implementar em computador

Desvantagens� Não permite casamento parcial entre consulta e

documento� Não permite ordenação dos documentos recuperados� A necessidade de informação do usuário deve ser

expressa em termos de uma expressão booleana� Nem todo usuário é capaz disso

� Este modelo geralmente retorna ou poucos documentos, ou documentos demais � a depender da consulta

23

Modelo Espaço Vetorial

Associa pesos positivos não-binários aos termos

Isso permite casamento “parcial” entre consulta e documento� Esses pesos são usados para calcular um “grau de similaridade” entre consulta e documento

O usuário recebe um conjunto ordenado de documentos como resposta à sua consulta� Mais interessante do que apenas uma lista desordenada de documentos

24


Este modelo pode utilizar diferentes fórmulas para:� Calcular os pesos dos vetores

� Freqüência de ocorrência do termo no documento� TF-IDF (mais usado)

� Calcular a medida de similaridade entre consulta e documentos� Co-seno (mais usado)� Jaccard, Coeficiente de Pearson, etc...

Essa escolha depende de quem constrói o sistema, e não do modelo EV

25

Modelo Espaço VetorialRepresentação do documento e da consulta

Dado o conjunto de termos representativos para o corpus em questão V = {t1, t2,...,tn}� cada termo de t é um eixo de um espaço vetorial

Consultas (q) e documentos (d) são representados como vetores nesse espaço n-dimensional

Olimpíadas

Brasil

Sidney

d0.2

0.50.3

qBrasil Olimpíada SidneyBrasil Olimpíada SidneyConsulta q :

Documento d :

Brasil em Sidney 2000

O Brasil não foi bem no quadra

das medalhas da Olimpíada de

Sidney 2000 ...

Brasil 0.4Olimpíada 0.3Sidney 0.3

Brasil 0.5Olimpíada 0.3Sidney 0.2

Representação de q

Representação de d

26

Modelo Espaço VetorialRelevância

O modelo ordena os documentos recuperados de acordo com sua similaridade em relação à consulta

Similaridade pode ser medida pelo co-seno do ângulo entre q e d� Existem outras medidas de similaridade usadas com o

modelo EV, porém o co-seno é a mais usada

K2

K1 d

qΘ

Similaridade(q,d) = cos(Θ)

27


Similaridade pode ser medida pelo co-seno do ângulo entre q e d� função inversamente relacionada ao ângulo entre os

documentos � Quanto menor é o ângulo entre os documentos, maior o co-

seno � E maior é a similaridade entre d e q

� Varia entre 0 e 1� Independe do tamanho do vetor

� Considera apenas sua direção

28


Existem diversas outras medidas de (dis)similaridade que podem ser usadas neste modelo� veja dissertação de Frederico B. Fernandes na BDTD-UFPE.

Medidas de Similaridade� Calculam a similaridade entre objetos

Medidas de Dissimilaridade � Calculam a dissimilaridade entre objetos

29

Medidas de Similaridade

Co-seno

Exemplo:

∑∑

∑

==

=

⋅

⋅

=n

i

ki

n

i

ki

n

i

kiki

yx

yx

sim

1

2

1

2

1

)()(

)(

( )83.0

(0.3) (0.2) (0.1) (0.4)(0.3) (0.1) (0.4) (0.2)

.30.30 .200.1 .100.4 .400.2

22222

222

=

+++⋅

+++

⋅+⋅+⋅+⋅=sim

BrasilOlimpíadas

Sidney

d2

d1Prata

yx

yxsim rr

rr⋅

=

30

Medidas de Similaridade

∑∑∑

∑

===

=

⋅−+

⋅

=n

i

kiki

n

i

ki

n

i

ki

n

i

kiki

yxyx

yx

sim

11

2

1

2

1

)()()()(

)()(

Jaccard

31

Modelo Espaço VetorialCálculo dos Pesos

Peso = freqüência de ocorrência do termo no documento

“Se o desonesto soubesse a vantagem de ser honesto, ele seria honesto ao menos por desonestidade.”

Sócrates

Doc original

desonesto / soubesse /vantagem / honesto /seria / honesto /menos/desonestidade/socrates

honesto 2desonesto 1soubesse 1vantagem 1seria 1menos 1desonestidade 1socrates 1

Operações de TextoRepresentação

Doc : www.filosofia.com Doc : www.filosofia.comDoc : www.filosofia.com

32

Modelo Espaço VetorialCálculo dos Pesos

Método TF-IDF leva em consideração� Freqüência do termo no documento

� Term Frequency (TF)

� Quanto maior, mais relevante é o termo para descrever o documento

� Inverso da freqüência do termo entre os documentos da coleção� Inverse Document Frequency (IDF)

� Termo que aparece em muitos documentos não é útil para distinguir relevância

Peso associado ao termo tenta balancear esses dois fatores

33

Definições� dj: documento; ki:termo � freqi,j: freqüência do termo ki no documento dj

� ni: número de documentos que contêm termo ki

� N: número total de documentos do corpus� maxl freql,j : a freqüência do termo mais freqüente no

documento

TF:

IDF:

Modelo Espaço VetorialCálculo dos Pesos com TF-IDF

Nni

idfi= log

Inverso da freqüência do termonos documentos do corpus

freqi,j

maxl freql,jtfi,j=

Freqüência (normalizada) do termo no documento

34


wi,j = tfi,j x idfi

freqi,j

maxl freql,jwi,j = N

nix log

35

Exemplo de TF� freqi,j: freqüência do termo ki no documento dj

� maxl freql,j = 2


freqi,j

maxl freql,jfi,j=

honesto 2 – 1.0desonesto 1 – 0.5soubesse 1 – 0.5vantagem 1 – 0.5seria 1 – 0.5menos 1 – 0.5desonestidade 1 – 0.5socrates 1 – 0.5

Termo freq - f

36

Definição do peso nos documentos:� wi,j: peso associado ao termo ki no documento dj

� wi,j = tfi,j X idfi

Para definição dos pesos dos termos nas consultas, Berthier sugere:


Nni

X log0.5 freqi,q

maxl freql,qwi,j = 0.5 +

Exemplo 1 Espaço Vetorial usando Co-seno

d1

d2

d3d4 d5

d6d7

k1k2

k3

k1 k2 k3 Norma q •••• dj Cosd1 1 0 1 1,41 2 0,82d2 1 0 0 1,00 1 0,58d3 0 1 1 1,41 2 0,82d4 1 0 0 1,00 1 0,58d5 1 1 1 1,73 3 1,00d6 1 1 0 1,41 2 0,82d7 0 1 0 1,00 1 0,58

q 1 1 1 1,73

Modelo Booleano só retorna como resultado d5!

d1

d2

d3d4 d5

d6d7

k1k2

k3

Exemplo 2 Espaço Vetorial usando Co-seno


q 1 2 3 3,74

d1

d2

d3d4 d5

d6d7

k1k2

k3

Exemplo 3 Espaço Vetorial usandoCo-seno


q 1 2 3 3,74

40


Vantagens� Pesos não-binários associados a termos permitem

casamento parcial dos documentos com a consulta� Co-seno ordena documentos de acordo com o grau de

similaridade com a consulta

Desvantagens:� Assim como o modelo booleano assume independência

entre os termos usados na indexação� q1 = redes neurais artificiais� q2 = redes neurais � Resultados das consultas q1 e q2 são diferentes

� É menos intuitivo que o modelo booleano.

Technology

Aula 02 - Recuperação da Informação / Modelos de Sistemas de Recuperação