CIn-UFPE1 Mineração da Web Recuperação de Informação Modelos de Recuperação de Documentos Parte 1 Flávia Barros

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


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


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


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


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


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

)()(

)()(


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


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


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


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


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


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:


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


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

Documents

CIn-UFPE1 Mineração da Web Recuperação de Informação Modelos de Recuperação de Documentos Parte 1 Flávia Barros