Recuperação de Informações
Estéfane George M. de Lacerda
Agentes na Web
• Agentes tem surgido na web de várias maneiras
– Busca
– Filtram e recuperam Informações
– Agentes notificadores
– Suporte ao Comércio
– Chat
– Outros...
Agentes na Web
• Os mais populares Agentes na Web tem sido usado
em sistemas de recuperação de informações na
web
A Web
• Informação não estruturada
• 400 a 500 milhões de documentos (Jul, 1998,
IEEE internet computer).
• Duplica de tamanho a cada 4 meses
• Multilíngue
• Ambígua
Caos para se buscar
informações
Tipos de sistemas de Busca na Internet
• Sistemas que usam Diretórios (Yahoo e Magellan)
– Catalagos organizados hierarquicamente.
• Sistemas que automatizam a organização das
informações na Web. (Altavista, Lycos,
WebCrawler, HotBot, Excite).
– Robôs ou spiders que exploram a web em
busca de páginas.
– A principal tecnologia desses sistemas provém
da área de Recuperação de informação.
Introdução a Recuperação de Informação
•
•
•
•
•
•
Full text scanning (KMP, Boyer e Moore etc...)
Arquivos de assinatura
Inversão
Indexação
Modelo Booleano
Modelo do Espaço Vetorial
Inversão
Coleção de Documentos
ID doc1
Good tutorial
on Java
ID doc2
Java tutorial
ID doc3
Sun´s Java
Site
Índice invertido
good
tutorial
doc1
doc1,doc2
on
java
sun
doc1
doc1,doc2.doc3
doc3
site
doc3
Preparação do documento p/ Indexação
• Análise léxica
• Stop list : palavras que não são úteis para
recuperação de informações (e.g. palavras
comuns, preposição, artigos, etc..)
• Stemming: processo de remover prefixos e sufixos
das palavras do documento
Term
engineering
engineered
engineer
Stem
engineer
engineer
engineer
Modelo Booleano
• A query é uma expressão com AND, OR e NOT
• O documento é relevante se o resultado da query
é verdadeiro.
• Tem baixo desempenho e não é possivel ranking
de documentos relevantes.
Modelo do Espaço Vetorial
• Documentos e query são representados por um
vetor com n dimensões, onde n é o numero de
termos diferentes na coleção de documentos.
Achar documentos é comparar o vetor de
documentos com o vetor query do usuário
Modelo do Espaço Vetorial
termos
good
tutorial
on
java
sun
site
doc1
w11
w12
w13
w14
0
0
vetores
doc2
doc3
0
w22
0
0
0
0
w24
0
0
w34
w35
w36
0 : Indica ausência do termo
wit : Peso que indica a importância do termo
query
0
0
0
w4
0
0
Atribuição de pesos
• Term Frequency x Inverse Document Frequency
(TF x IDF)
wij = fd,t log(N/fi)
N é o número total de documentos
ft é o número de docs que contém o termo t
fd,t : número de ocorrências do termo t no doc i
• Esta função atribui altos pesos para palavras raras,
pois são melhores discriminantes.
Ranking de documentos
• Os documento mais relevantes são retornados ao
usuário de acordo com a similaridade entre vetor
query e vetor documento
• Medida de similaridade R é dado pelo produto
interno entre vetor query Q com vetor documento
D (cosine similarity):
R = Q•D
Medidas de desempenho
Recall: total de documentos relevantes retornados
dividido pelo número total dos relevantes.
Precision: documentos relevantes retornados
dividido pelo número total de retornados
Todos os Documentos
Documentos Relevantes
Documentos Retornados
Relevantes Retornados
Medidas de desempenho
• Note que maximizar apenas uma medida
isoladamente é fácil:
– retornando 1 doc tem-se máximo precision, mas
péssimo recall
– retornando todos docs tem-se máximo recall,
mas péssimo precision
• Portanto, o sistema deve maximizar ambos recall e
precision simultaneamente
Relevance Feedback
• Processo de refinar resultados de uma recuperação
de informações.
• O usuário indica quais dos documentos retornados
são os mais relevantes.
• O sistema busca novos documentos com base
naqueles documentos indicados pelo usuário.
• O processo é repetido conforme desejado.
Outras técnicas
•
•
•
•
Clusterização de documentos
Machine learning
Redes Neurais
Processamento de Linguagem natural
Estudo de caso: o WebCrawler
wwwlib
agents
Search
engine
Internet
Query
server
database
Componentes do software do Webcrawler
Estudo de caso: o WebCrawler
• Search engine
– Começa com um conjunto de HTML´s e usa
suas URL´s para recuperar novos documentos.
– Atravessa a web usando busca em largura no
grafo formado pelos links entre documentos
– Indexa no mínimo um documento por servidor
Estudo de caso: o WebCrawler
• Agents
– São eles que realmente recuperam as páginas da
web quando solicitados pelo sistema.
• Database
– Prepara documento (Análise léxica, stop-list,
stremming, determina pesos usando TF.IDF,
indexação)
– Os índices são atualizados semanalmente
Estudo de caso: o WebCrawler
• Query server
– Suporta operadores AND, OR e NOT e frases
– Usa o modelo do espaço vetorial
– Efetua o ranking dos documentos com base na
similaridade com o vetor query
– Apresenta os documentos mais relevantes com
um resumo e um score de relevância
Estudo de caso: o WebCrawler
Conclusão
• A necessidade crescente de organizar informações
na WEB.
• Usuários não sabem elaborar a “query”, acham
complicados, com muitas possibilidades e sem
nenhuma orientação.
• Tempo de resposta ainda é lento.
• Técnicas IA são cada vez mais necessárias na
Web.
Bibliografia
• Willian B. Frakes e Ricardo Baeza-Yates Information
Retrieval: Data Structures & Algorithms,, Prentice Hall,
1992.
• Gudivada, V. N. et al. Information retrieval on the world
wide web. IEEE Internet Computing, Oct, 1997.
• Etzioni, O; Weld, D. S. Intelligent Agents on the Internet:
Fact, Fiction, and Forecast, IEEE Expert, Aug., 1995.
• Pinkerton. B. Finding What people want. Experiences with
webcrawler. Proc. Second. Int´L www conf., 1994.
(http://www.ncsa.uiuc.edu/SDG/IT94/Proceedings/Searchi
ng/pinkerton/WebCrawler.html)
• Oard D. W. The State of the Art in Text Filtering,,
University of Maryland, 1997.
Referências - Links
• http://almond.srv.cs.cmu.edu/afs/cs/user/katia/ww
w/katia-home.html
• http://www.cs.umbc.edu/agents/
• http://wwwkr.org/~chitos/ir_and_robot/indexing.html