Aula03 RI Modelo Vetorial

Prévia do material em texto

1
Recuperação de Informação
Modelos de Recuperação de Documentos
Modelo Espaço Vetorial
Renato Fernandes Corrêa
2Modelo Espaço Vetorial
Representação do documento
Associa pesos positivos não-binários aos termos 
nos documentos
Os documentos são representados como vetores 
onde os termos são eixos que definem o espaço 
vetorial multidimensional de termos.
Olimpíada
Brasil
Sidney
d0.2
0.5
0.3
Documento d :
Brasil em Sidney 2000
O Brasil não foi bem no 
quadra das medalhas da 
Olimpíada de Sidney 2000 ...
Brasil 0.5
Olimpíada 0.3
Sidney 0.2
Representação de d
3Modelo Espaço Vetorial
Representação da consulta
A expressão de busca consiste de palavras 
separadas por espaço em branco
Associa pesos positivos não-binários aos termos 
na expressão de busca
A consulta é representada como vetor onde os 
termos são eixos que definem o espaço vetorial 
multidimensional de termos.
Olimpíada
Brasil
Sidney
d0.2
0.50.3
q
Brasil Olimpíada SidneyConsulta q : Brasil 0.4
Olimpíada 0.3
Sidney 0.3
Representação de q
4
Modelo Espaço Vetorial
Representação do documento e da consulta
Dado o conjunto de termos representativos para o 
corpus em questão V = {t1, t2, t3, ...,tn}
 cada termo é um eixo de um espaço vetorial
Consultas (q) e documentos (d) são representados 
como vetores nesse espaço n-dimensional de termos
Olimpíada
Brasil
Sidney
d0.2
0.50.3
q
Brasil 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.4
Olimpíada 0.3
Sidney 0.3
Brasil 0.5
Olimpíada 0.3
Sidney 0.2
Representação de q
Representação de d
5Modelo Espaço Vetorial
Representação do documento e da consulta
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)
Essa escolha depende de quem 
constrói o SRI, e não do modelo 
Espaço Vetorial
6
Modelo Espaço Vetorial
Função de Busca
O modelo ordena os documentos recuperados 
de acordo com sua similaridade em relação à 
consulta
Similaridade pode ser medida pelo cosseno do 
ângulo entre q e d
 Existem outras medidas de similaridade usadas com 
o modelo EV, porém o cosseno é a mais usada
K2
K1 d
q

Similaridade(q,d) = cos()
7
Este modelo pode utilizar diferentes 
fórmulas para calcular a medida de 
similaridade entre consulta e documentos
Cosseno (mais usado)
Jaccard, Coeficiente de Pearson, 
etc...
Essa escolha depende de quem 
constrói o SRI, e não do modelo 
Espaço Vetorial
Modelo Espaço Vetorial
Função de Busca
8Modelo Espaço Vetorial
Função de Busca
A associação de pesos positivos não-binários aos 
termos nos documentos e na expressão de busca 
juntamente com o cálculo de uma função 
similaridade entre os vetores permite o 
casamento parcial entre consulta e documento
 Os 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 ou sem ordem significativa.
9
Similaridade pode ser medida pelo 
cosseno do ângulo entre q e d
 função inversamente relacionada ao 
ângulo entre os documentos 
Quanto menor é o ângulo entre os 
documentos, maior o cosseno 
E maior é a similaridade entre d e q
 Varia entre 0 e 1
 Independe do tamanho do vetor
Considera apenas sua direção
Modelo Espaço Vetorial
Função de Busca
10
Função de Busca
Cosseno
Exemplo:







n
i
i
n
i
i
n
i
ii
dq
dq
sim
1
2
1
2
1
)()(
)(
   
97.0
36.0
35.0
38.034.0
35.0
(0.2) (0.3) (0.5)(0.3) (0.3) (0.4)
.200.3 .300.3 .500.4
222222





sim
dq
dq
sim 




Olimpíada
Brasil
Sidney
d0.2
0.5
0.3 -
q
Brasil 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.4
Olimpíada 0.3
Sidney 0.3
Brasil 0.5
Olimpíada 0.3
Sidney 0.2
Representação de q
Representação de d
0.3 -
11
Função de Busca
0.35 .200.3 .300.3 .500.4 dq

dq
dq
dqdqsim 



 ),cos(),(
Brasil 0.4
Olimpíada 0.3
Sidney 0.3
Brasil 0.5
Olimpíada 0.3
Sidney 0.2
Representação de q
Representação de d
Brasil Olimpíada Sidney Norma q  dj Cos
d 0,5 0,3 0,2 0,62 0,35 0,97
q 0,4 0,3 0,3 0,58
58.034.0(0.3) (0.3) (0.4) 222 q

97.0
36.0
35.0
58.062.0
35.0
cos 





dq
dq


62.038.0(0.2) (0.3) (0.5) 222 d

Exemplo 1 
Espaço Vetorial usando Cosseno 
com pesos binários
t1 t2 t3 Norma q  dj Cos
d1 1 0 1 1,41 2 0,82
d2 1 0 0 1,00 1 0,58
d3 0 1 1 1,41 2 0,82
d4 1 0 0 1,00 1 0,58
d5 1 1 1 1,73 3 1,00
d6 1 1 0 1,41 2 0,82
d7 0 1 0 1,00 1 0,58
q 1 1 1 1,73
Consulta q: t1 t2 t3
Modelo Booleano só permite retornar como resultado: 
d5 (todos os termos); ou todos os documentos sem ordem (qualquer dos termos).
Resultado: d5, [d1, d3, d6], [d2, d4, d7]
d1
d2
d3d4
d5
d6
d7
t1
t2
t3
Exemplo 2 
Espaço Vetorial usando cosseno, usando 
frequência de ocorrência como peso das palavras
t1 t2 t3 Norma q  dj Cos
d1 2 0 1 2,24 3 0,77
d2 1 0 0 1,00 1 0,58
d3 0 1 3 3,16 4 0,73
d4 2 0 0 2,00 2 0,58
d5 1 2 4 4,58 7 0,88
d6 1 2 0 2,24 3 0,77
d7 0 5 0 5,00 5 0,58
q 1 1 1 1,73
Consulta q: t1 t2 t3
Pesos calculados pelo próprio sistema de RI
Resultado: d5, [d1, d6], d3, [d2, d4,d7]
14
Modelo Espaço Vetorial
Cálculo dos Pesos
Uma possibilidade é utilizar como peso a 
frequência de ocorrência do termo (TF) no 
documento e na consulta
“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 2
desonesto 1
soubesse 1
vantagem 1
seria 1
menos 1
desonestidade 1
socrates 1
Operações de Texto
Representação
Doc : www.filosofia.com Doc : www.filosofia.com
Doc : www.filosofia.com
15
Modelo Espaço Vetorial
Cá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 nos 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 varia entre zero e 
um e tenta balancear esses dois fatores
16
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 Vetorial
Cálculo dos Pesos com TF-IDF
N
ni
idfi= log
Inverso da freqüência do termo
nos documentos do corpus
freqi,j
maxl freql,j
tfi,j=
Freqüência (normalizada) 
do termo no documento
17
Exemplo de TF
 freqi,j: freqüência do termo ki no documento dj
 maxl freql,j = 2
Modelo Espaço Vetorial
Cálculo dos Pesos com TF-IDF
honesto 2 – 1.0
desonesto 1 – 0.5
soubesse 1 – 0.5
vantagem 1 – 0.5
seria 1 – 0.5
menos 1 – 0.5
desonestidade 1 – 0.5
socrates 1 – 0.5
Termo freq - tf
freqi,j
maxl freql,j
tfi,j=
Por exemplo:
tfhonesto,j= 1.0 
18
Exemplo de IDF
 ni: freqüência do termo ki na coleção 
N: número de documentos na coleção
 Suponha:
 que a palavra honesto apareça em seis documentos na 
coleção
 que a coleção tenha 32 documentos no total
Modelo Espaço Vetorial
Cálculo dos Pesos com TF-IDF
32
6
idfhonesto= log = 0.73
N
ni
idfi= log
19
Modelo Espaço Vetorial
Cálculo dos Pesos com TF-IDF
wi,j = tfi,j x idfi
freqi,j
maxl freql,j
wi,j =
N
ni
x log
Para o exemplo:
whonesto,j = tfhonesto,j x idfhonesto = 1.0 X 0.73 = 0.73
20
Definição do peso nos documentos:
 wi,j: peso associado ao termo ti no documento dj
 wi,j = tfi,j X idfi
Para definição dos pesos dos termos nas 
consultas, Baeza-Yates e Ribeiro-Neto sugerem:
Modelo Espaço Vetorial
Cálculo dos Pesos com TF-IDF
N
ni
X log
0.5 freqi,q
maxl freql,q
wi,j = 0.5 + 
21
Modelo Espaço Vetorial
Vantagens
 Permite casamento parcial dos documentos com a 
consulta
 Ordena documentos de acordo com o grau de 
similaridade com a consulta
 Consultas e documentos são representados de forma 
homogênea pelo sistema
Desvantagens:
 Assim como o modelo booleano assume independência 
entre os termos usados na indexação
 q1: professor ; q2: professores
 Resultados das consultas q1 e q2 são diferentes
 É menos intuitivo que o modelo booleano.
Mecanismos de Busca na Web
22
Todos adotam uma variação do modelo 
espaço vetorial 
Google
 https://www.google.com.br/about/company/history/
 http://www.google.com/intl/pt-BR/insidesearch/
 http://www.google.com/intl/pt-BR/insidesearch/howsearchworks/crawling-
indexing.html
 http://static.googleusercontent.com/media/www.google.com/pt-BR//intl/pt-
BR/insidesearch/howsearchworks/assets/searchInfographic.pdf
Bing
Yahoo
23
Exercícios
1) Construa a lista de documentos retornados 
utilizando o modelo espaço vetorial para o exemplo 2 
para as consulta: t1 t2
2) Faça o cálculo dos pesos das palavras utilizando o 
método TF-IDF para os documentos e consulta do 
exemplo 2. Calcule o cosseno e descreva a ordem 
dos resultados retornados pela busca.
Exercícios
3) Acesse o Google Acadêmico:
https://scholar.google.com.br/
 Recuperar documentos que possua o termo indexação 
automática em algum dos campos descritivos dos artigos ou no 
texto completo. Então, observe e descreva como está ordenado os 
resultados da busca.
24
Resolução
t1 t2 t3 Norma q  dj Cos
d1 2 0 1 2,24 2 0,63
d2 1 0 0 1,00 1 0,71
d3 0 1 3 3,16 1 0,22
d4 2 0 0 2,00 2 0,71
d5 1 2 4 4,58 3 0,46
d6 1 2 0 2,24 3 0,95
d7 0 5 0 5,00 5 0,71
q 1 1 0 1,41
Pesos dos termos na consulta calculados pelo Sistema de RI
Resultado: d6, [d2,d4,d7], d1,d5,d3
1) Consulta: t1 t2
Resolução
2) Primeiro Passo – cálculo de TF e IDF
26
TF t1 t2 t3
d1 1,00 0,00 0,50
d2 1,00 0,00 0,00
d3 0,00 0,33 1,00
d4 1,00 0,00 0,00
d5 0,25 0,50 1,00
d6 0,50 1,00 0,00
d7 0,00 1,00 0,00
q 1,00 1,00 1,00
t1 t2 t3
IDF 0,15 0,24 0,37
t1 t2 t3
d1 2 0 1
d2 1 0 0
d3 0 1 3
d4 2 0 0
d5 1 2 4
d6 1 2 0
d7 0 5 0
q 1 1 1
Resolução
2) Segundo Passo – Calculo do TFIDF
27
TFIDF t1 t2 t3
d1 0,15 0,00 0,18
d2 0,15 0,00 0,00
d3 0,00 0,08 0,37
d4 0,15 0,00 0,00
d5 0,04 0,12 0,37
d6 0,07 0,24 0,00
d7 0,00 0,24 0,00
q 0,15 0,24 0,37
TF t1 t2 t3
d1 1,00 0,00 0,50
d2 1,00 0,00 0,00
d3 0,00 0,33 1,00
d4 1,00 0,00 0,00
d5 0,25 0,50 1,00
d6 0,50 1,00 0,00
d7 0,00 1,00 0,00
q 1,00 1,00 1,00
t1 t2 t3
IDF 0,15 0,24 0,37
Resolução
2) Terceiro Passo – Cálculo do Cosseno 
Resultado: d5,d3,d1,d6,d7,[d2,d4]
28
TFIDF t1 t2 t3 Norma q  dj Cos
d1 0,15 0,00 0,18 0,23 0,09 0,82
d2 0,15 0,00 0,00 0,15 0,02 0,31
d3 0,00 0,08 0,37 0,38 0,16 0,89
d4 0,15 0,00 0,00 0,15 0,02 0,31
d5 0,04 0,12 0,37 0,39 0,17 0,94
d6 0,07 0,24 0,00 0,25 0,07 0,59
d7 0,00 0,24 0,00 0,24 0,06 0,52
q 0,15 0,24 0,37 0,46
Resolução
3) Google Acadêmico:
Busca por: indexação automática
29
Referências
FERNEDA, E. Introdução aos Modelos 
Computacionais de Recuperação de 
Informação. Rio de Janeiro: Editora Ciência 
Moderna
Ltda. 2012.
30