Upload
leila-castilho-caminha
View
214
Download
0
Embed Size (px)
Citation preview
Sistemas de Recuperação da
Informação
UNIVERSIDADE FEDERAL DE CAMPINA GRANDECENTRO DE ENGENHARIA ELÉTRICA E INFORMÁTICA
DEPARTAMENTO DE SISTEMAS E COMPUTAÇÃO
Prof. Ulrich Schiel
Sistemas de Recuperação da Informação
ROTEIRO
1. INTRODUÇÃO
2. TÓPICOS DA RECUPERAÇÃO DA INFORMAÇÃO2.1. Estruturas de arquivos2.2. Indexação2.3. Consultas
Sistemas de Recuperação da Informação
3. INDEXAÇÃO DE INFORMAÇÃO3.1 Filtragem3.2 Análise léxica3.3 Stoplist3.4 Stemming ou truncagem3.5 Construção de thesaurus3.6 Indexação
1. ARMAZENAMENTO DE INFORMAÇÃO4.1. Arquivos invertidos4.2. Arquivos de assinatura4.3. Retângulos ótimos
Sistemas de Recuperação da Informação
5. CONSULTAS5.1 modelo booleano5.2 modelo vetorial5.3 .modelo probabilístico5.4 .modelos alternativos
1. DOCUMENTOS MULTIMÍDIA
1. EXTRAÇÃO DA INFORMAÇÃO
1. MINERAÇÃO DE TEXTOS
9. BIBLIOTECAS DIGITAIS E A WEB
Sistemas de Recuperação da Informação
LIVROS TEXTO
R. Baeza-Yates e B. Ribeiro-Neto “Modern Information Retrieval”, Addison-Wesley, 1999
M.-F. Moens “Information Extraction: Algorithms and Prospects in a Retrieval Context” Springer Verlag, 2006.
S. Weiss, N. Indurkhya, T. Zhang e F. Damerau“Text Mining: Predictive Methods for Analyzing Unstructured Information” Springer Verlag, 2005
BIBLIOGRAFIA
Sistemas de Recuperação da Informação
OUTROS C.D. Manning, P.Raghavan and H.Schütze, Introduction to Information Retrieval,
Cambridge University Press. 2007. Download em: "http://www-csli.stanford.edu/~schuetze/information-retrieval-book.html
W. B. Frakes, R. Baeza-Yates “Information Retrieval: Data Structures and Algorithms”, Prentice Hall, 1992
W. Y.Arms, “Digital Libraries”, MIT Press, 2000
INTRODUÇÃO
Dados estruturados X dados (semi-)estruturados
INTRODUÇÃO
SBC
SGBD
SRI
pequenainferênciaregra
granderecuperação(determinística)
registro
granderecuperação(probabilística)
browsing
documento
TAMANHOOPERAÇÃOOBJETOS
INTRODUÇÃO
• Cobertura = #Ra/#R
Uma consulta Uma base de documentos
coleção
Documentos relevantes (R) Documentos recuperados (A)
Documentos relevantes recuperados (Ra)
• Precisão = #Ra/#A
INTRODUÇÃO
• Alfabeto
• Palavras
• Termos
• Conceitos
• Documentos
Objetos dos SRI
INTRODUÇÃO
Alfabeto
romano A,B,C,.. a,b,c,..acentuação
hebraico Aleph Beith
árabeSamaku = “smk” (سمك) , (peixe)
�� َِآ ⇐ ب ا ت ك ٌب un b ā t i k /kitābun/ ‘um livro’
INTRODUÇÃO
Alfabeto
romano A,B,C,.. a,b,c,..acentuação
hebraico Aleph Beith
árabeSamaku = “smk” (سمك) , (peixe)
grego Α α (alfa), Β β (beta), Γ γ (gamma), Δ δ (delta)
INTRODUÇÃO
Alfabeto
Japonês nihongo
日本語 .
Hànyǔ, Chinês(monosilábica)
华语 /華語 中文 ,
Huáyǔ
INTRODUÇÃO
Palavras-É uma seqüência de caracteres terminadaPor um branco ou um sinal (. , ; : ‘ “ -)
Mr. O’Neill thinks that the boys’ stories about Chile’s capital aren’t amusing.
neilloneillo’neillo’ neillo neill ?
aren’tarentare n’taren t are not?
Dever-se-ia mantê-la.
mantê lamantê-lamanter ela
Guarda-chuvaGuarda chuvaGuarda-chuva
INTRODUÇÃO
Palavras -É uma seqüência de caracteres terminadapor um branco ou um sinal
Quais caracteres? • letras !
• só letras ?
B12OS/2MP3W3C
• começando por letra? 3D3FN
• outros símbolos? C++INGRES*
• excluir números, tabelas, figuras, etc.• considerar gowords
INTRODUÇÃO
Palavras
Maiúsculas e minúsculas? Palavra e palavraGeomedia GeoMedia GEOMEDIA
acentuação acentuação ~ acentuacaopelo ~ pêlo ?
siglas OCL = Object Constraint Language
Organisation Communiste Libertaire
INTRODUÇÃO
Termos
Cada palavra é um termo
Termos compostos bancos de dados
Guarda-chuva
1, 2 ou 3 termos?
banco de dados distribuído ? termos
Pesquisa sobre o anarquismo
Recherches sur l’anarchism
Anarchismusforschung
bancos dados
INTRODUÇÃO
Conceitos
Sinonímia Efetuar ~ fazer ~ cumprir ~ executar ~ realizar
Synset = classe de equivalência de sinônimos
Termo representativo = 1 elemento do Synset
INTRODUÇÃO
Conceitos
Grosso:1. volumoso (livro grosso)2. áspero (mãos grossas)3. pastoso (caldo grosso)4. grosseiro (mal-educado)
Homonímia
Banco:1. instituição financeira (negócios e finanças)2. objeto para sentar (mobília)3. conjugação do verbo bancar ()4. repositório (Informática)
INTRODUÇÃO
Termo+Significado+Contexto
Conceito
INTRODUÇÃO
Thesaurus
Termo
hipernímia
Termo
Termo
TermosinonímiaTermo
hiponímia
Termo
meronímia
relacionadoTermo
INTRODUÇÃO
Thesaurus
Termo
hipernímia
Fiat Uno
Veículo
CarrosinonímiaAutomóvel
hiponímia
meronímia
Frota
Motor
meronímia
relacionado
motorista
trânsitorodoviadirigir
INTRODUÇÃO
Documentos
• O que é um documento?
• Um arquivo eletrônico• Um hipertexto• Uma enciclopédia• Um e-mail com anexos• Um artigo em Anais• Os anais
INTRODUÇÃO
Documentos
• Qual o formato?• Qual o alfabeto?• Qual o idioma?
• doc, pdf, doc, txt• Romano, Chinês, árabe• Português, ...
INTRODUÇÃO
Processo da Recuperação da informação
INTRODUÇÃO
Processo da recuperação da informação
Docu-mento
extração
stoplist radicais
Banco de
Dados
associação
texto palavrasextração
usuário
palavras
radicais
consulta palavras radicais radicais
Lista dedocumentos
operadoresBooleanos
listaordenada ranking
TÓPICOS DA RECUPERAÇÃO DA INFORMAÇÃO
Indexação
Estruturas de arquivos
Recuperação
TÓPICOS DA RECUPERAÇÃO DA INFORMAÇÃO
Estruturas de arquivos
OPÇÕES:• Arquivo de índices
• Arquivos invertidos• hashing• Retângulos ótimos
• Texto puro• Pesquisa em texto
• Arquivos assinatura
• Árvores Patrícia (sufixos)• Também para tabelas, etc.
• Grafos (redes semânticas, ontologias,.)
TÓPICOS DA RECUPERAÇÃO DA INFORMAÇÃO
Consultas e recuperação
• Modelos baseados em teoria dos conjuntos• Booleano e Booleano extendido• Conjuntos Fuzzy
• Modelos algébricos• Vetorial básico e generalizado• Contextual• Redes Neurais
• Modelos probabilísticos• básico• Redes Bayesianas
TÓPICOS DA RECUPERAÇÃO DA INFORMAÇÃO
Consultas e recuperação
• Modelos de Browsing• Browsing plano• Browsing com diretórios• Hipertextos
• Modelos sobre textos estruturadosConsideram a estrutura do documento (itálico, negrito, figuras, proximidades)• Listas disjuntas (Capítulos, seções, parágrafos)• proximidades
INDEXAÇÃO DA INFORMAÇÃO
1. Filtragem2. Análise léxica3. Stoplist4. Truncagem (stemming)5. Construção do thesaurus6. Indexação
INDEXAÇÃO DA INFORMAÇÃO
1. Filtragem
• Conversão para um formato padrão• Remover macros do editor• Remover símbolos especiais• Hipertextos
• doc, rtf, pdf, ps, tex, ... • html• xml & etc (rdf, dc, xmlschema, owl,..).
INDEXAÇÃO DA INFORMAÇÃO
‘Semi-estruturado’EXEMPLO
{\rtf1\ansi\ansicpg1252\uc1\}{\*\generator Microsoft Word 10.0.2627;}{\info{\title Semi-}{\author Ulrich Schiel}{\operator Ulrich Schiel} Semi}{\insrsid3955129\charrsid8669994 -}{\insrsid8669994\charrsid8669994 e}{\insrsid3955129 struturado\par }}
Rtf:
INDEXAÇÃO DA INFORMAÇÃO
‘Semi-estruturado’EXEMPLO html:
<html xmlns:o="urn:schemas-microsoft-com:office:office"xmlns:w="urn:schemas-microsoft-com:office:word"xmlns="http://www.w3.org/TR/REC-html40">
<head><title>Semi-estruturado</title><!--[if gte mso 9]><xml> <w:WordDocument> <w:Zoom>150</w:Zoom> <w:GrammarState>Clean</w:GrammarState> <w:HyphenationZone>21</w:HyphenationZone> <w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel> </w:WordDocument></xml><![endif]--><style>
<!-- /* Style Definitions */ p.MsoNormal, li.MsoNormal, page Section1
.......;}div.Section1
{page:Section1;}--></style><!--[if gte mso 10]><style> /* Style Definitions */ .......</style><![endif]--></head><div class=Section1><p class=MsoNormal><b>Semi</b>-estruturado</p></div></body></html>
INDEXAÇÃO DA INFORMAÇÃO
‘Semi-estruturado’EXEMPLO
Em pdf
INDEXAÇÃO DA INFORMAÇÃO
1. Filtragem – análise léxica
• Conversão para um formato padrão• Remover macros do editor• Remover não-palavras• Remover maiúsculas/minúsculas• Remover acentuação
INDEXAÇÃO DA INFORMAÇÃO
Stopwords
StopwordsPalavras mais frequentes
• Critérios:• Classificação gramatical (artigos, determinantes,
pronomes, numerais, advérbios, preposições)• Palavras mais frequentes
INDEXAÇÃO DA INFORMAÇÃO
Stopwords
• Problemas• Termos compostos• Frases:• Siglas• Especiais
“banco de dados” “banco” “dados”“ser ou não ser” “ser”OCL Object Constraint LanguageB12, 3D, 007 B12, tridimensional,
James Bond
• Solução• Dicionários de termos compostos, frases, siglas e
de ‘gowords’
INDEXAÇÃO DA INFORMAÇÃO
Stopwords
• Como remover stopwords de forma eficiente?
• Após a análise léxica
• Junto com a análise léxica
INDEXAÇÃO DA INFORMAÇÃO
Stopwords
• Considere uma lista SW&CW contendo stopwords e palavras compostas1. Ler, sequencialmente, o documento de entrada até delimitar uma palavra p.
(considerar regras básicas de construção de palavras e exceções (gowords))1. se (p ocorre em SW&CW) OU (é o início de um termo composto em SW&CW)
se p é o início de um termo composto em SW&CWentão avançar no documento para verificar se é o composto se for o composto
então gravar o termo composto na saída, voltar para 1. senão manter a primeira palavra e voltar para 1.
senão desconsiderar esta palavra e voltar para 1.1. senão gravar a palavra identificada na saída e voltar para 1.
• Algoritmo de filtragem:
INDEXAÇÃO DA INFORMAÇÃO
Filtragem - Exercício
Baseado no texto a seguir, construir:• regras de identificação de palavras• uma tabela de gowords• uma tabela de stopwords• uma tabela de palavras compostas
Acompanhar o algoritmo de filtragem e mostrar o resultado
INDEXAÇÃO DA INFORMAÇÃO
Filtragem - Exercício
Term-frequency (tf) é uma medida que utiliza o número de ocorrências do termo tj no documento di. Porém quando termos com alta freqüência aparecem na maioria dos documentos da coleção eles não fornecem informação útil para diferenciar documentos. A medida inverse document frequency (idf) favorece termos que aparecem em poucos documentos da coleção. Tal medida varia inversamente ao número x de documentos que contem o termo tj em uma coleção de documentos e é definida como log (n/x). Baseado nessas duas medidas de freqüência pode-se definir a medida tfidf, combinando-as, como mostra a tabela a seguir:
INDEXAÇÃO DA INFORMAÇÃO
Stemming (normalização/truncagem)
• Processo de remover variantes morfológicas aumentando a abrangência de um termo
• Variantes de escrita, erros normalização• variações de número e gênero, conjugações de verbos
lemmatization/normalização• Definição de radicais Stemming
OPÇÕES:• Truncar os termos• Expandir a consulta
INDEXAÇÃO DA INFORMAÇÃO
Stemming (normalização/truncagem)
OPÇÕES:
Regras genéricas
Processos individuais (com dicionários, análise gramatical, etc.)
• Substituir• *s *• *aria *• *eiro *• *mento *
• Substituir• casa, verbo casar• casa, substantivo casa• casamento casa (??)• (ing) theses thesis (??)
INDEXAÇÃO DA INFORMAÇÃO
Stemming (normalização/truncagem)
• Normalização (lemmatization)• Verbos conjugados infinitivo
• substantivos para o singular masculino
• Variantes, erros dicionário, análise sintática
“Se tu casas comigo nossas casas serão vendidase teremos uma cama de casal”.c
“você casar casa ser vender ter cama casal”.
INDEXAÇÃO DA INFORMAÇÃO
Stemming (normalização/truncagem)
• Algoritmos de Truncagem (stemming)
• Algoritmo de Porter
• Tabela explícita engenhengenhengenh
engenhariaengenhoengenheiro
RadicalTermo
INDEXAÇÃO DA INFORMAÇÃO
Stemming (normalização/truncagem)
• Algoritmos de Truncagem (stemming)
• Tabela explícita engenhengenhengenh
engenhariaengenhoengenheiro
RadicalTermo
INDEXAÇÃO DA INFORMAÇÃO
Stemming (normalização/truncagem)
• Algoritmos de Truncagem (stemming)
• Variedade de sucessores
“Se tu casas comigo, nossas casas serão vendidase teremos uma cama de casal”
v(c) = 2 v(ca) = 2v(cas) = 1v(casa) = 2
INDEXAÇÃO DA INFORMAÇÃO
Stemming (normalização/truncagem)
• Truncagem (stemming)• Remover sufixos baseado em regras pré-estabelecidas
• Calcular a medida m do radical segundo
• Seja C uma sequência de consoantes da palavra• Seja V uma sequência de vogais da palavra, • Então m é determinado por [C][(VC)m[V]
Exemplosm=0 la, cham=1 lar, casa m=2 chavem=3 largar, Brasil
INDEXAÇÃO DA INFORMAÇÃO
Stemming (normalização/truncagem)
• Truncagem (stemming)• Remover sufixos baseado em regras pré-estabelecidas
• Substituir
• (m>1) *s *• (m>0) *aria *• (m>0) *eiro *• (m>1) *mento *• (m>1) *ar *a
• Exemplos• casas casas• padaria pad• padeiro pad• casamento casa• casar casa
INDEXAÇÃO DA INFORMAÇÃO
Stemming (normalização/truncagem)
• Truncagem (stemming)
• Remover sufixos baseado em regras pré-estabelecidas
“você casa casa ser vender ter cama casa”.
“você casar casa ser vender ter cama casal”.
INDEXAÇÃO DA INFORMAÇÃO
Stemming (normalização/radicalização)
Desambiguação
“você casa casa ser vender ter cama casa”.
Par composto por marido e mulhersubstantivocasa-
Unir-se pelo casamentoverbocasa-
moradiasubstantivocasa
significadoClass. Gram.Termo
Desambiguação por dicionário: dicionário
INDEXAÇÃO DA INFORMAÇÃO
Indexação semântica - conceitos
Desambiguação por dicionário:
Termos ContextoConceito
Significado
INDEXAÇÃO DA INFORMAÇÃO
Indexação semântica - conceitos
• Vetor de todos conceitos – V = <c1,..cn>
• Cada termo t é instanciado neste vetor, com Vt=<t1,..tn>:• Para cada conceito cj em V:
• tj é positivo se é relacionado a cj
• tj é zero se não é relacionado a cj
• tj é negativo se contradiz cj
INDEXAÇÃO DA INFORMAÇÃO
Indexação semântica - conceitos
Desambiguação: Análise Semântica Latente (LSA):
Descobre o contexto de palavras analisando matrizes termo X documento
INDEXAÇÃO DA INFORMAÇÃO
Indexação semântica - LSA
ElefanteComputadorTelefone
AutomóvelMotoristaVeículoChassis
carro
MadeiraAsfaltoÁrvore
HospitalEnfermeiraTratamentoPacienteMedicamento
médico
Palavras com baixa relevância
Retorno de alta relevância
Palavra da pesquisa
INDEXAÇÃO DA INFORMAÇÃO
Indexação semântica - LSA
• http://www.intelliwise.com/reports/info2004.pdf (em português)• http://lsa.colorado.edu/papers/dp1.LSAintro.pdf
Fontes:Análise Semântica Latente (LSA) - Fontes:
INDEXAÇÃO DA INFORMAÇÃO
PonderaçãoCálculo da importância de um termo em um documento
tf = freq (k,D) (freqüência do termo k no documento D)
idf = log (N / nk) (inverse document frequency), onde N
é o número de termos na coleção e nk número de vezes que o termo ocorre na coleção.
tfidf = freq (k,S) log (N / nk) (inverse document frequency), é o peso do termo k no documento D
INDEXAÇÃO DA INFORMAÇÃO
PonderaçãoCálculo da importância de um termo em um documento –
considerando o tamanho dos documentos
INDEXAÇÃO DA INFORMAÇÃO
Ponderação EXEMPLO:
um novo documento contém as palavras
–‘petróleo’ 4 vezes–‘Brasil’ 8 vezes– ‘ refinaria’ 10 vezes
na base de 2048 as palavras ocorrem:–‘petróleo’ 128 vezes–‘Brasil’ 16 vezes– ‘ refinaria’ 1024 vezes
teríamos os cálculos:Vetor com tf : <‘petróleo’: 4, ‘Brasil’: 8, ‘ refinaria’: 10>
cálculo com tfitf (‘petróleo’)= 4*log(2048/128) = 4*1,2 = 4,8tfitf (‘Brasil’)= 8*log(2048/16) = 8*2,1 = 16,87tfitf (‘refinaria’)= 10*log(2048/1024) = 10*0,3 = 3
Logo temos o vetor <4.8, 16.87, 3>
INDEXAÇÃO DA INFORMAÇÃO
Ponderação
EXTENSÕES:
• tfidf não leva em consideração– a distribuição do item nos outros documentos – ponderação por sinal– a importância do termo no todo – valor de discriminação
• DISCRIMi = SimMédiai – SimMédia SimMédia = similaridade média dos termos da base SimMédiai = similaridade média dos termos da base retirando i
• peso(ki) = tfi * DISCRIMi
INDEXAÇÃO DA INFORMAÇÃO
Ponderação
PROBLEMAS COM O CÁLCULO DE PESOS:Mudanças na base de documentos alteram os valores
SOLUÇÕES• desconsiderar as mudanças e refazer os cálculos periódicamente• refazer os cálculos após um fator de mudanças ser alcançado• usar fórmulas que desconsideram a base de documentos
INDEXAÇÃO DA INFORMAÇÃO
Inclusão no Thesaurus (tesauro)
INDEXAÇÃO DA INFORMAÇÃO
Inclusão no Thesaurus (tesauro)
INDEXAÇÃO DA INFORMAÇÃO
Inclusão no Thesaurus (tesauro)
• EXEMPLOComputational linguisticsBroader Terms
LinguisticsNarrower Terms
Machine TranslationRelated Terms
Automatic IndexingComputer ScienceLanguage ProcessingLinguistic TheoryMathematical LinguisticsMathematical LogicProgramming LanguagesSemanticsStatisticsStructural Analysis (Linguistics)Word Frequency
Thesaurus ERIC Descriptors
INDEXAÇÃO DA INFORMAÇÃO
Inclusão no Thesaurus (tesauro)
• Cada nó do thesaurus representa um CONCEITO• Dado um termo deve-se encontrar o conceito adequado
SOLUÇÃO• um dicionário: Termo Conceito
PROBLEMA: Homônimos
SOLUÇÃO• um dicionário: Termo X contexto X significado Conceito
INDEXAÇÃO DA INFORMAÇÃO
Thesaurus – relações entre os termos •Relações Hierarquicas – é-um
subclasse (Automóvel Veículo) instância (João da Silva Pessoa)
•Relação Hierarquicas – parte-de (meronímia) agregado (Motor Automóvel) conjunto (Estudante Turma)
•Relação Horizontais sinonímia (Carro Automóvel) antonímia (Empregado Desempregado) relacionado (Carro motorista estrada)
INDEXAÇÃO DA INFORMAÇÃO
Inclusão no Thesaurus (tesauro)
• NORMALIZAÇÃO do vocabulário - – formas nominativas– poucos adjetivos– questões de maiúsculas, notações, abreviações, acentuação, etc
• CONSTRUÇÃO - – manual
• (definir domínio, definir estrutura, coletar termos, incluir termos, ‘inverter’ estrutura criando ordem alfabética)
– automática (one shot ou incremental)– semi-automática
INDEXAÇÃO DA INFORMAÇÃO
Thesaurus
• Construção Automática de um Thesaurus
Construção automática baseada em termos compostos:
Banco de Dados
Banco de Dados TemporalBanco de Dados Espacial
Banco de Dados Espaço-temporal
INDEXAÇÃO DA INFORMAÇÃO
Thesaurus
• Construção Automática de um Thesaurus
Construção automática baseada em frequências:
T1 com f(t1) = n
T2 com f(t2) = n1 <n0
T3 com f(t3) = n2 < n1
Níveis deFrequência
0
1
2
INDEXAÇÃO DA INFORMAÇÃO
Thesaurus
Construção automática de thesauri:
• análise de co-ocorrências para formar termos compostos.– usa LSA ou outra técnica para encontrar palavras relacionadas
• espaço de conceitos–FILTRAGEM: Extrair todos termos de uma coleção de documentos de um domínio. usar dicionários, stop-words, stemming e criaçao de termos compostos baseado em termos adjacentes– ANÁLISE DE CO-OCORRÊNCIAS:– Associações baseadas em modelos cognitivos de redes de conceitos do usuário
INDEXAÇÃO DA INFORMAÇÃO
Thesaurus Construção automática de thesauri:
• Redes Bayesianas– è criado um grafo dirigido acíclico modelando situações de causa e efeito
EXEMPLO– “Quando a família sai de casa acendo a luz da varanda e deixo o cachorro solto no jardim. O cachorro no jardim nota quando alguém está no portão. Quando ouço alguém no portão, vou até lá.
família sai
luz acesa
cachorro fora
alguém no portão
vou ao portão
ESTRUTURAS DE ARQUIVOS
Thesaurus retangular de relações termo X documento
SIM
INDEXAÇÃO DA INFORMAÇÃO
Thesaurus Construção manual de thesauri:
• definir o domínio• definir atributos dos objetos a serem indexados (título, resumo, índice, etc.)
• definir relacionamentos (sinonímia, proximidade, termlos relacionados, termos compostos, hierarquias, etc.
• aplicar algoritmo de indexação e clustering
KWIC+KWAC+KWOC `banco de dados`• KWOC: palavra-chave fora de contexto (banco: assento)
• KWIC: palavra-chave no contexto (banco: repositório)
• KWAC: palavra-chave e contexto (banco: banco de dados)