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
Modelo Espaço Vetorial
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
Modelo Espaço VetorialRelevância
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
Modelo Espaço VetorialRelevância
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
Modelo Espaço VetorialCálculo dos Pesos com TF-IDF
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
Modelo Espaço VetorialCálculo dos Pesos com TF-IDF
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:
Modelo Espaço VetorialCálculo dos Pesos com TF-IDF
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
k1 k2 k3 Norma q •••• dj Cosd1 1 0 1 1,41 4 0,76d2 1 0 0 1,00 1 0,27d3 0 1 1 1,41 5 0,94d4 1 0 0 1,00 1 0,27d5 1 1 1 1,73 6 0,93d6 1 1 0 1,41 3 0,57d7 0 1 0 1,00 2 0,53
q 1 2 3 3,74
d1
d2
d3d4 d5
d6d7
k1k2
k3
Exemplo 3 Espaço Vetorial usandoCo-seno
k1 k2 k3 Norma q •••• dj Cosd1 2 0 1 2,24 5 0,60d2 1 0 0 1,00 1 0,27d3 0 1 3 3,16 11 0,93d4 2 0 0 2,00 2 0,27d5 1 2 4 4,58 17 0,99d6 1 2 0 2,24 5 0,60d7 0 5 0 5,00 10 0,53
q 1 2 3 3,74
40
Modelo Espaço Vetorial
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.