Projeto X-Finder Agents
Recuperação e indexação de páginas
especializadas na Web
DI - UFPE

Introdução à Recuperação de informação

Detalhamento do projeto
1
Motivação: “morrendo ignorante em um
mar de informação”
 Objetivo: Encontrar (de forma eficiente) os melhores
documentos que satisfaçam a consulta do usuário
DI - UFPE
2
Medidas: Recall e Precisão
 Cobertura (Recall)
• total de documentos relevantes retornados dividido
pelo número total dos relevantes.
 Precisão:
• documentos relevantes retornados dividido pelo
número total de retornados
Todos os Documentos
Documentos Relevantes
Documentos Retornados
Relevantes Retornados
Recuperação de informação
 Sistemas de indexação por palavras-chave
• consulta: palavras-chave e expressões booleanas
• retorna uma grande quantidade de documentos
irrelevantes mas é robusto e abrangente
• Exemplos: AltaVista, Radix, HotBot, Lycos, ...
 Sistemas de indexação manual por ontologias
• consulta: palavras-chave e navegação
• classificação mais precisa porém estática e menos
abrangente
• Exemplos: Yahoo!, Cadê, ...
DI - UFPE
4
Recuperação de informação
 Solução intermediária:
• automatização da classificação humana
• processamento de linguagem natural + conhecimento
 Inviável, porque a Web é
• Enorme
• Não-estruturada
• Conteúdo variado
• Ambígua
• Multilíngue
DI - UFPE
5
Estrutura Geral de um Sistema IR
Critérios do
Usuário
Filtragem
Documentos
“Interessantes”
Busca
Doc. 1
...
Indexar
Doc. N
Stop-List
Base de Dados
Estruturada
Busca e Recuperação de Informação
Usuário
Browser
Search Engine
Consulta
Resposta
Servidor de
Consultas
Base de
Índices
)--(
Web
Robô
Indexing Engine
Busca
Exemplos: Radix, AltaVista, Lycos, Excite, ...
DI - UFPE
7
Representação do Documento
 Dado um documento, identificar os conceitos que
descrevem o seu conteúdo e quão bem eles o
descrevem.
 Pesos das Palavras como indicação de
relevância:
• Freqüência relativa da palavra no texto (centroide)
• Freqüência da palavra em relação a outros
documentos (TFIDF)
• Colocação da palavra na estrutura do documento
(título, início, negrito,...)
 Palavras com maiores pesos são selecionadas
formando um vetor de representação.
Exemplo de Representação
Brincadeira
O rato roeu a roupa
do rei de Roma.
brincadeira, t, m, n, i
rato, 1
roeu, 1
roupa, 1
rei, 2
roma, 2, m
brincadeira, 90
rato, 70
roeu, 70
roupa, 70
roma, 65
rei, 60
centroide
brincadeira, 90
rato, 70
roeu, 70
roupa, 70
rei, 60
roma, 65
Representação
Vetorial do
Documento
Estrutura de Arquivos p/ IR
 Arquivos Invertidos
WORD: Bem-vindo
http://www.ufpe.br
ID: 543
URL: http://www.ufpe.br
Bem-vindo!
UFPE
URLs: 455227,...
ID: 455227
Words: 543, 987
WORD: UFPE
ID: 987
Arquivo Direto
 Arquivos de Assinatura
 Árvores e arrays PAT
URLs: 455227,...
Arquivo Invertido
Indexing
 Análise Léxica
• Converter uma cadeia de caracteres em uma cadeia
de palavras/tokens. (/, -, 0-9,...)
 Stop-list
• Palavras comuns são retiradas da indexação.
 String searching
• String matching exato e aproximado (KMP, BoyerMoore,...), busca por sinônimos,...
 Indexação Distribuída, Base compartilhada:
• Divisão por: Localização Geográfica, Rede,
Conteúdo,..
Indexing
 Stemming
• possibilitar variações morfológicas dos termos durante
o casamento.
 Ontologias
Term
engineering
engineered
engineer
Stem
engineer
engineer
engineer
• para aumentar precisão e cobertura.
Futebol
Campeonato Brasileiro
Palmeiras
CBF
Categorização de Documentos
 Objetivos:
• Facilitar a busca automática e browsing dos
documentos.
 Técnicas podem ser divididas em:
• Booleana
• Probabilística
• Vetorial
 Utilizam:
• Aprendizado de máquina (processos de inferência)
• Engenharia de conhecimento (definição de uma BC)
Detalhamento do Projeto
DI - UFPE
14
X-Finder Agents
 Andamento
• A cada novo assunto pertinente* apresentado, será
proposta 1 tarefa cujo resultado será posteriormente
avaliado em uma aula de laboratório
• Teremos 3 tarefas ao todo (3 etapas do projeto),
segundo o cronograma de aulas da página do curso
 Grupos
• 4 grupos de 4 alunos
* o que não é pertinente será cobrado em uma lista de exercícios
DI - UFPE
15
Páginas Especializadas
 Páginas especializadas: estrutura na Web
• apesar da aparência caótica, a Web pode ser vista como
um aglomerado de classes particulares de páginas
• estas páginas especializadas tem em comum
características sintáticas e semânticas
 Exemplos
• chamadas de trabalho (cfp), faq, hotéis, pessoais, lista de
artigos, restaurantes, classificados, cinemas, ...
 Contexto
• estas páginas podem servir para contextualizar as
consultas
– ex. “amplificador de áudio” .... cfp, faq, loja, artigo, ....
DI - UFPE
16
arquitetura: meta busca
ex. receita
ex. excite palavra-chave
Mec.
Busca
Agente
Pós-filtragem
Índices
html
Mec.
Busca
para
KB classificação
html
palavra-chave
ex. sobremesa
DI - UFPE
17
Objetivo
 Projeto básico (para todos)
•
Implementar um conjunto de agentes capazes de
recuperar e indexar páginas especializadas
 Extensões eventuais (escolher uma se for o caso)
(a) prover extração de informação
(b) testar algoritmos de aprendizagem
(c) estender a busca com as palavras mais comuns (ex.
bolo, carnes, ...)
(d) introduzir conectores lógicos e ontologias para
consulta a posteriori
(e) notificação personalizada
DI - UFPE
18
Etapa 1
 Fase Preliminar Manual
• Identificação das palavras-chave a serem usadas nos
mecanismos gerais de busca
– ex. “conference”, “symposium” e “call for papers” para
o caso das páginas de chamadas de trabalho
– ex. “receitas”, “ingredientes” para o caso de receitas
culinárias
• Formação de um corpus etiquetado (à mão) de
páginas para teste, (mínimo de 200 páginas!)
– ex. BD (ou equivalente): url, classe, arquivo html
– tanto exemplo positivo quanto negativo
DI - UFPE
19
Etapa 2
 Montar as base de regras
• Identificar possíveis regras de classificação
– Se a palavra “paper” aparece no título e existem n
parágrafos com .... Então é um “call for papers”
• Implementar as regras de classificação
– Reutilizaruma classe manipuladora de arquivos html
(www.cin.ufpe.br/~compint/aulas-IAS/programas/PaginaWWW.java)
– utilizar Jeops, Jess ou Clips
• Efetuar testes com o corpus medindo
– precisão
– cobertura
– F-measure = (cobertura * precisão) / 2(cobertura + precisão)
DI - UFPE
20
Regras com fator de certeza
 Regras com fator de certeza
• Se xx e yy Então zz com n% de chances
 É possível combinar evidências quando regras
disparam com a mesma conclusão
• probab-atualizada = probab-nova * (1 - probab-antiga)
– para o Jeops, implementa no objeto a evidência
acumulada...
DI - UFPE
21
Etapa 3
 Fase de Automatização Indutiva (alternativa)
• Representação dos exemplos de aprendizagem
– “enxugar” o texto (stop-list), inclusive tirando tags
– escolher as palavras mais pertinentes (TFIDF)
– compor o vetor de representação
• Escolher 1 ou 2 algoritmos de aprendizagem (ID3,
RN, Bayes, etc.)
– codificar os exemplos
– rodar os algoritmos e obter os resultados (matriz
binária de confusão)
 Fase de avaliação dos métodos de classificação
• dedutivo x indutivo: discutir resultados!
DI - UFPE
22
Categorização de Textos
 Representação do texto
 Construção indutiva de categorizadores
Representação Inicial
Texto
inicial
Conhecimento
Adicional
Categorização
DI - UFPE
Indução
Redutor de Dimensão
ou
Seleção de Características
Representação
Final
23
Etapas
 Fase de Implementação do Protótipo
• Automatização consulta a mecanismos de busca
– Reutilizar/programar as classes para acesso aos
mecanismos de busca
• Identificação da estrutura da página de resposta do
mecanismo de busca para extração dos links
– ex. terceira linha, depois de um <LI>...
• Automatização extração de links das respostas
– Reutilizar/programar uma classe manipuladora de
arquivos html
• Automatização da atualização e indexação periódica
da base de índices
DI - UFPE
24
Técnicas de IR
 Centroide
• freqüência das palavras no texto
 Term Frequency-Inverse Document Frequency
(TFIDF):
• atribui pesos às palavras de um documento.
• TF(w): freqüência da palavra w (número de vezes que w
aparece no documento.
• DF(w): freqüência de documentos com a palavra w
(número de documentos em que a palavra ocorre).
 D 

TFIDF( )  TF ( )  log

DF
(

)


D = número total de documentos.
DI - UFPE
25
Etapa 4
 Tendo feito o classificador
• criar base de índices com as páginas pertencentes à
classe desejada (stop-list, arquivos invertidos, ...)
– fazer inicialmente com as páginas do corpus
• prover interface par consulta (ex. bolo, carnes, ...)
• automatizar busca na Web de maneira alimentar a
base de índices automática e periodicamente
DI - UFPE
26
Etapa 5 (opcional)
 Se der tempo, dividir os grupos para estender o
trabalho em umas das seguintes direções
(a) prover extração de informação
(b) testar algoritmos de aprendizagem
(c) estender a busca com as palavras mais comuns (ex.
bolo, carnes, ...)
(d) introduzir conectores lógicos e ontologias para
consulta a posteriori
(e) notificação personalizada
DI - UFPE
27
Referências
 Internet Categorization and Search: A Self-Organizing Approach,
Hsinchun Chen, University of Arizona, 1996.
 Learning from Hotlists and Coldlists: Towards a WWW
information filtering and seeking agent, Michael Pazzani,
University of California.
 The State of the Art in Text Filtering, Douglas W. Oard, University
of Maryland, 1997.
 BRight: a Distributed System for Web Information Indexing and
Searching, Pedro Falcão & Silvio Meira, Universidade Federal de
Pernambuco.
 Na Architecture for Information Agents, Donald P McKay,
University of Maryland.
 Cooperating Agents for Information Retrieval, Craig A. Knoblock,
University of Southern California
Referências
 Ontologies for Enhancing Web Searches' Precision and Recall,
Flávia A. Barros, Pedro F. Gonçalves, Universidade Federal de
Pernambuco.
 Information Retrieval: Data Structures & Algorithms, Willian B.
Frakes e Ricardo Baeza-Yates, Prentice Hall, 1992. !!!!!
 Filtragem e Recomendação de Documentos na Web. Uma
Abordage Usando Java, José Abelardo Sánchez Cardoza,
Universidade Federal de Pernambuco, 1998.
Referências - Links
• Universidade de Maryland
http://www.cs.umbc.edu/abir/
http://www.cs.umbc.edu/agents/
• Intelligent Software Agents
http://www.sics.se/ps/abc/survey.html
• MIT Media Lab
http://lcs.www.media.mit.edu/groups/agents/resources.
• Sycara’s Page
http://almond.srv.cs.cmu.edu/afs/cs/user/katia/www/katia-home.html
• Sasdwedish Institute of Computer Science
http://www.dsv.su.se/~fk/if_Doc/IntFilter.html