CIn-UFPE 1
Mineração da WebRecuperação de Informação
Modelos de Recuperação de Documentos
Parte 1
Flávia Barros
CIn-UFPE
2
Roteiro
Resumo da aula passada
Tarefas de Recuperação de Informação
Modelos de Recuperação de Documentos Modelo Booleano Modelo Espaço Vetorial
CIn-UFPE
3Relembrando…
Sistemas de Recuperação de Informação
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 BD,
e sua posterior recuperação para responder a consulta do usuário
Etapas principais: Preparação dos documentos Indexação dos documentos Busca (casamento com a consulta do usuário) Ordenação dos documentos recuperados
Obs.: Inicialmente, vamos tratar apenas documentos textuais
Sistemas de RI: Criação da base de índices
Base de docs. ou
Web
Gerenciador do BDIndexação
Preparação dos documentos
Base deindices
Representação do documento
(visão lógica)
Arquivo de índices invertido
Documentos
Sistemas de RI: Consulta à Base de índices
Busca e recuperação
Ordenação
Preparação da consulta
Interface do usuário
Base deíndices
Indices-docsrecuperados
consulta
Índices-docsordenados
Necessidade do usuário
CIn-UFPE
6
Aula de hoje...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: Adhoc Filtragem
Browsing
TAREFA
DO
uSUÁRIO
Modelos Clássicos
Booleano Espaço vetorial Probabilista
Teoria dos conjuntos
Fuzzy Booleano estendido
Probabilista
Redes de inferência Redes de crença
Algebraico
ES generalizado Semântica LatenteRedes Neurais
Browsing
Plano Estruturado Hipertextual
CIn-UFPE
8Tarefa 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
CIn-UFPE
9Tarefa do usuárioRecuperação com filtragem
Recupera documentos considerando o perfil do usuário e a consulta
Base de documentos
Perfil do usuário 1
Docs para usuário 1
Docs para usuário 2
Perfil do usuário 2
CIn-UFPE
10
Representação do DocumentoVisão Lógica
Cada documento da base 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
CIn-UFPE
12
Modelos Clássicos de Recuperação de Documentos
Veremos inicialmente os seguintes modelos: Modelo Booleano Modelo Espaço Vetorial Modelos Probabilistas
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
CIn-UFPE
13Modelos Clássicos Conceitos Básicos
Considere uma base qualquer de documentos
Cada documento na base é representado por um conjunto de n termos (ou palavras isoladas) k1, k2,...,kn
Esses termos são escolhidos a partir da base de documentos completa cada base terá seu conjunto de termos
representativos
CIn-UFPE
14Modelos Clássicos Conceitos Básicos
Cada documento (dj) é representado por termos da base associados a pesos d1 = k1 (w1), k2 (w2),..., kn (wn)
Peso Importância da palavra para descrever o
documento Quando o termo não aparece no
documento, o peso associado é zero
Cada modelo de recuperação define pesos de uma maneira diferente
CIn-UFPE
15Modelos Clássicos Conceitos Básicos
As consultas podem ser representadas pelo mesmo conjunto de termos da base Alguns modelos permitem associar
pesos aos termos da consulta
CIn-UFPE
16Modelo BooleanoRepresentação do documento
Dado o conjunto de termos representativos para a base em questão K = {k1, k2,...,kn}
Os documentos são 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 A representação indica apenas se o termo está
ou não presente no documento e.g., d1 = {1,1,0}
documento d1 contém os termos k1 e k2, e não contém o termo k3
CIn-UFPE
17
Modelo BooleanoRepresentação da consulta
Consulta: Termos conectados por AND, OR e/ou NOT Exemplo: k1 AND (k2 OR not k3)
A consulta é transformada em uma fórmula normal disjuntiva (DNF) objetivo: facilitar o casamento entre documento
e consulta Exemplo acima: (1,1,1) OR (1,1,0) OR (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
CIn-UFPE
18Modelo BooleanoRelevância
Relevância “binária”: O documento é considerado relevante sse seu
“casamento” com a consulta é verdadeiro Não é possível ordenar os documentos recuperados
Exemplo de consulta
Consultak1 k2 k3
Consultak1 k2 k3
Documentos apresentados ao usuário
K1 k2
k3
Base de Documentos
CIn-UFPE
19
Modelo Booleano
Vantagens Modelo simples baseado em teoria bem
fundamentada Fácil de implementar
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
Em conseqüência, este modelo geralmente retorna ou poucos documentos, ou documentos demais a depender da consulta
CIn-UFPE
20
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
CIn-UFPE
21
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
CIn-UFPE
22Modelo Espaço Vetorial
Representação do documento e da consulta
Dado o conjunto de termos representativos para a base em questão K = {k1, k2,...,kn}
cada termo de K é 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íadas SidneyBrasil Olimpíadas 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íadas 0.3Sidney 0.3
Brasil 0.5Olimpíadas 0.3Sidney 0.2
Representação de q
Representação de d
CIn-UFPE
23
Modelo Espaço Vetorial Relevâ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()
CIn-UFPE
24
Modelo Espaço Vetorial Relevâ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
CIn-UFPE
25
Modelo Espaço Vetorial Relevância
Existem diversas outras medidas de (dis)similaridade que podem ser usadas neste modelo
Medidas de Similaridade Calculam a similaridade entre objetos
Medidas de Dissimilaridade Calculam a dissimilaridade entre objetos
CIn-UFPE
26
Medidas de Similaridade
Co-seno
Exemplo:
n
iki
n
iki
n
ikiki
yx
yxsim
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
CIn-UFPE
27
n
iki
n
iki
n
ikiki
yyxx
yyxx
sim
1
2
1
2
1
)()(
)()(
Medidas de Similaridade
Coeficiente de Pearson
Jaccard
Dice
Inclusão
n
ikiki
n
iki
n
iki
n
ikiki
yxyx
yxsim
11
2
1
2
1
)()()()(
)()(
n
iki
n
iki
n
ikiki
yx
yxsim
1
2
1
2
1
)()(5.0
)()(
n
iki
n
ikiki
x
yxsim
1
2
1
)(
)()(
CIn-UFPE
28
Medidas de Similaridade
Sobreposição
Sorensen
Spearman
onde n é o número máximo de termos dos documentos considerados
n
iki
n
iki
n
ikiki
yx
yxsim
1
2
1
2
1
)(,)(min
)()(
n
iki
n
iki
n
ikiki
yx
yx
sim
11
1
),min(
200
1
6
12
1
2
nn
yx
sim
n
ikiki
CIn-UFPE
29
Medidas de Dissimilaridade
Calculam a dissimilaridade entre objetos
Podem ser transformadas em uma medida de similaridade normalizada pela fórmula:
dissimsim
1
1
CIn-UFPE
30
Medidas de Dissimilaridade
Distância Euclidiana
Exemplo:
n
ikiki yxdissim
1
2
37.0)3.03.0()2.01.0()1.04.0()4.02.0( 2222 dissim
73.037.01
1
sim
CIn-UFPE
31
Medidas de Dissimilaridade
Canberra
Distância de Chord
Bray-Curtis
Distância Taxonômica
n
in
iki
ki
n
iki
ki
y
y
x
xdissim
1
2
1
2
1
2 )()(
n
iki
n
iki
n
ikiki
yx
yxabsdissim
11
1
)(
n
ikiki
n
iki
n
iki yxyxdissim
11
2
1
2 )()(2
n
i kiki
kiki
yx
yxabsdissim
1
)(
CIn-UFPE
32
Modelo Espaço Vetorial Cá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
CIn-UFPE
33
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 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
CIn-UFPE
34
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 da base 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
Nni
idfi= log
Inverso da freqüência do termonos documentos da base
freqi,j
maxl freql,j
tfi,j=Freqüência (normalizada) do termo no documento
CIn-UFPE
35
Modelo Espaço Vetorial Cálculo dos Pesos com TF-IDF
wi,j = tfi,j x idfi
freqi,j
maxl freql,j
wi,j = Nni
x log
CIn-UFPE
36
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
freqi
,jmaxl
freql,j
fi,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
CIn-UFPE
37
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 Vetorial Cálculo dos Pesos com TF-IDF
Nni
X log0.5 freqi,q
maxl freql,q
wi,j = 0.5 +
CIn-UFPE
38Exemplo 1 Espaço Vetorial usando Co-seno
k1 k2 k3 q dj d1 1 0 1 2 d2 1 0 0 1 d3 0 1 1 2 d4 1 0 0 1 d5 1 1 1 3 d6 1 1 0 2 d7 0 1 0 1 q 1 1 1
d1
d2
d3d4 d5
d6d7
k1k2
k3
CIn-UFPE
39
k1 k2 k3 q dj d1 1 0 1 4 d2 1 0 0 1 d3 0 1 1 5 d4 1 0 0 1 d5 1 1 1 6 d6 1 1 0 3 d7 0 1 0 2 q 1 2 3
d1
d2
d3d4 d5
d6d7
k1k2
k3
Exemplo 2 Espaço Vetorial usando Co-seno
CIn-UFPE
40
k1 k2 k3 q dj d1 2 0 1 5 d2 1 0 0 1 d3 0 1 3 11 d4 2 0 0 2 d5 1 2 4 17 d6 1 2 0 5 d7 0 5 0 10 q 1 2 3
d1
d2
d3d4 d5
d6d7
k1k2
k3
Exemplo 3 Espaço Vetorial usandoCo-seno
CIn-UFPE
41
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: 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
CIn-UFPE
42
Próxima Aula
Modelos de RI baseados em teoria dos conjuntos Objetivo: possibilitar casamento parcial
e ordenação dos documentos recuperados Modelo booleano estendido Modelos difusos (fuzzy sets)
Modelo Algébrico Semântica Latente
Modelo probabilista