RECUPERAÇÃO DE INFORMAÇÃO
MODELOS E APLICAÇÕES
Alessandro Marinho Silva
André Pires Vieira
Diego Dainese Polla
Sergio Luis da Silva
Wilson Witerkosk
RECUPERAÇÃO DE INFORMAÇÃO
MODELOS E APLICAÇÕES
Índice
• Introdução
• Modelos Quantitativos
• Modelos Dinâmicos
• Recuperação de Informação na Web
• Conclusão
RECUPERAÇÃO DE INFORMAÇÃO
MODELOS E APLICAÇÕES
INTRODUÇÃO
Modelos Quantitativos Modelos Dinâmicos R.I. Na Web Conclusão
Recuperação de Informação
Recuperação da informação significa a operação pela
qual se seleciona documentos, sobre tópicos específicos,
a partir do acervo, em função da demanda do usuário.
O processo de recuperação de informação consiste em
identificar, no conjunto de documentos(corpus) de um
sistema, quais atendem à necessidade de informação do
usuário.
4
Modelos Quantitativos Modelos Dinâmicos R.I. Na Web Conclusão
Sistemas de Recuperação de Informação
Os Sistemas de Recuperação de Informação (SRI’s)
surgiram da necessidade de se extrair informações em
bases de dados não estruturadas, tais como grandes
coleções de documentos textuais e bibliográficos.
Os SRI’s necessitam de técnicas que agilizam o
armazenamento e acesso aos dados.
5
Modelos Quantitativos Modelos Dinâmicos R.I. Na Web Conclusão
Sistemas de Recuperação de Informação
A recuperação de informação é feita a partir de uma
entrada do usuário, ou seja, uma consulta para que os
documentos relevantes sejam encontrados.
Os SRI’s geralmente se baseiam em Busca por PalavraChave ou Busca por Similaridade.
6
Modelos Quantitativos Modelos Dinâmicos R.I. Na Web Conclusão
Recuperação de Informação x Mineração de Texto
A informatização de diversas áreas trouxe como conseqüência
um grande volume de informações sendo armazenadas em
bancos de dados.
Algumas áreas surgiram para o tratamento de informações
textuais, como a Recuperação de Informação e a Mineração
de Textos.
Ambas utilizam técnicas avançadas para explorar uma grande
coleção de dados textuais desestruturados, mas tem propósitos
diferentes.
7
Modelos Quantitativos Modelos Dinâmicos R.I. Na Web Conclusão
Recuperação de Informação x Mineração de Texto
Recuperação de Informação é uma tecnologia utilizada
para buscar documentos, focalizando nos dados
relacionados a algum tópico específico.
A Mineração de Textos, também conhecida como
Descoberta de Conhecimento em Textos (KDT), visa
encontrar padrões e tendências em um conjunto de
documentos, realizar classificação de documentos, ou
ainda comparar documentos.
8
Modelos Quantitativos Modelos Dinâmicos R.I. Na Web Conclusão
Recuperação de Informação x Mineração de Texto
Em uma das etapas da Mineração de Textos, utiliza-se
técnicas de R.I.
Técnicas de
RI
Forma
Intermediária
Coleção
de
textos
Mineração
Conheciment
o
Técnicas de
EI
Processo de Mineração de Textos (Correa, 2003)
9
Modelos Quantitativos Modelos Dinâmicos R.I. Na Web Conclusão
Recuperação de Informação x Mineração de Texto
Por se tratar de documentos textuais desestruturados, é
necessário um sistema que filtre o conjunto de documentos e
indexe as palavras-chave encontradas, as quais identificam o
conteúdo dos textos.
Essa técnica é chamada de indexação.
10
Modelos Quantitativos Modelos Dinâmicos R.I. Na Web Conclusão
Indexação
Processo pelo qual as palavras contidas nos textos são
armazenadas em uma estrutura de índice para viabilizar a
pesquisa de documentos através das palavras que eles
contêm.
11
Modelos Quantitativos Modelos Dinâmicos R.I. Na Web Conclusão
Indexação
Índices invertidos são criados para possibilitar melhoras
significativas no desempenho e na funcionalidade da busca.
A figura a seguir mostra a utilização de arquivos invertidos
para o armazenamento dos termos que identificam os
documentos.
12
Modelos Quantitativos Modelos Dinâmicos R.I. Na Web Conclusão
Indexação
Os termos,
As buscas
ou palavras-chave,
usam os índices
são
extraídos
extraídos
dosdos
documentos-texto
textos e ficam
armazenados
para comparações
juntamente
com a com
consulta
as
referências para
do usuário.
os respectivos
documentos.
Estrutura de Arquivo Invertido (Correa, 2003)
13
Modelos Quantitativos Modelos Dinâmicos R.I. Na Web Conclusão
Indexação
Algumas etapas que constituem o processo de indexação:
Análise léxica: etapa para converter uma cadeia de caracteres
em uma cadeia de palavras.
Remoção de Stop-Words: esta fase tem por objetivo filtrar e
retirar as palavras que ocorrem na maioria dos documentos,
como artigos, preposições, conjunções e pronomes.
Stemming: remove todas as variações (plurais, gerúndios,
sufixos) de uma palavra, permanecendo apenas a raiz da
palavra.
14
RECUPERAÇÃO DE INFORMAÇÃO
MODELOS E APLICAÇÕES
MODELOS
QUANTITATIVOS
Introdução
Modelos Dinâmicos R.I. Na Web Conclusão
Modelos Quantitativos
A grande maioria dos modelos de RI é de natureza
quantitativa: baseados em disciplinas como a lógica, a
estatística e a teoria dos conjuntos.
Talvez a principal tarefa para os sistemas de RI seja
decidir a importância de um termo para a descrição do
conteúdo de um documento.
16
Introdução
Modelos Dinâmicos R.I. Na Web Conclusão
Modelos Quantitativos
Os modelos de recuperação quantitativos, aqui
abordados, são:
•Modelo Booleano
•Modelo Vetorial
•Modelo Probabilístico
17
Introdução
Modelos Dinâmicos R.I. Na Web Conclusão
Modelo Booleano
Baseado na lógica booleana.
Considera uma consulta como uma expressão
booleana convencional formada com os conectivos
lógicos AND, OR e NOT.
Sua estratégia de recuperação é baseada no critério
de decisão binária.
É de vital importância para sistemas de banco de
dados (SQL).
18
Introdução
Modelos Dinâmicos R.I. Na Web Conclusão
Modelo Booleano
(FERNEDA, 2003)
19
Introdução
Modelos Dinâmicos R.I. Na Web Conclusão
Modelo Vetorial
Associa pesos aos termos de indexação e aos termos da expressão
de busca.
O resultado da utilização destes pesos é a ordenação dos
documentos pelo grau de similaridade em relação à expressão de
busca.
Cada elemento do vetor é normalizado para assumir valores entre 0
e 1.
Para o cálculo do peso é considerado o n° de vezes que o
termo aparece no documento e o n° de vezes que o termo
aparece no corpus de documentos.
20
Introdução
Modelos Dinâmicos R.I. Na Web Conclusão
Modelo Vetorial
A representação gráfica de dois documentos: DOC1, com termos de
indexação t1 e t3, com pesos 0.3 e 0.5, e DOC2 com termos de indexação
t1, t2 e t3, com pesos 0.5, 0.4 e 0.3, dá-se:
21
Introdução
Modelos Dinâmicos R.I. Na Web Conclusão
Modelo Vetorial
Se utilizarmos uma expressão de busca eBUSCA=(0.2,0.35,0.1), juntamente
com os documentos DOC1 e DOC2, em um espaço vetorial formado pelos
termos t1, t2 e t3, teremos a representação gráfica a seguir:
22
Introdução
Modelos Dinâmicos R.I. Na Web Conclusão
Modelo Vetorial
Para encontrar o grau de similaridade, calcula-se o coseno do ângulo entre documentos ou entre consultas e
documentos:
Onde wi,x é o peso do i-ésimo elemento do vetor x e wi,y
é o peso do i-ésimo elemento do vetor y.
23
Introdução
Modelos Dinâmicos R.I. Na Web Conclusão
Modelo Vetorial
Assim, o grau de similaridade entre o documento DOC1
e o documento DOC2 é calculado:
24
Introdução
Modelos Dinâmicos R.I. Na Web Conclusão
Modelo Vetorial
Portanto, o grau de similaridade entre estes dois documentos
é de 73%. Utilizando-se a mesma fórmula é possível
encontrar o grau de similaridade entre a expressão eBUSCA
com cada um dos documentos DOC1 e DOC2:
25
Introdução
Modelos Dinâmicos R.I. Na Web Conclusão
Modelo Vetorial
A expressão eBUSCA possui um grau de similaridade de 45%
com o documento DOC1 e de 92% com o documento DOC2.
É possível restringir a quantidade de documentos recuperados
definindo um limite mínimo para o valor de similaridade.
Um limite de 0.5, indica que uma expressão de busca obterá
como resultado apenas os documentos cujo valor de
similaridade for superior a 50%.
26
Introdução
Modelos Dinâmicos R.I. Na Web Conclusão
Modelo Probabilístico
O Modelo Probabilístico representa o processo de
recuperação de informação sob um ponto de vista
probabilístico, ou seja, calcula a probabilidade de que o
documento seja relevante para a consulta.
27
Introdução
Modelos Dinâmicos R.I. Na Web Conclusão
Modelo Probabilístico
Dada uma expressão de busca, podem-se dividir os N
documentos de um corpus em quatro subconjuntos:
• o conjunto dos documentos relevantes (Rel)
• o conjunto dos documentos recuperados (Rec)
• o conjunto dos documentos relevantes e recuperados (RR) e
• o conjunto dos documentos não relevantes e não recuperados.
28
Introdução
Modelos Dinâmicos R.I. Na Web Conclusão
Modelo Probabilístico
O resultado ideal de uma busca é o conjunto que contenham
todos e apenas os documentos relevantes para o usuário, isto é,
todo o conjunto Rel.
29
Introdução
Modelos Dinâmicos R.I. Na Web Conclusão
Modelo Probabilístico
Após obter os resultados da primeira busca, é possível melhorar
os resultados através de interações com o usuário.
Seja Rel o conjunto de documentos relevantes, e Re l o
complemento de Rel, a probabilidade de um documento d ser
relevante em relação à expressão de busca é designada por
p(Rel|d).
30
Introdução
Modelos Dinâmicos R.I. Na Web Conclusão
Modelo Probabilístico
A similaridade (sim) de um documento d em relação à expressão
de busca eBUSCA é definida como:
31
RECUPERAÇÃO DE INFORMAÇÃO
MODELOS E APLICAÇÕES
MODELOS
DINÂMICOS
Introdução Modelos Quantitativos
R.I. Na Web Conclusão
Modelos Dinâmicos
Representam um enfoque diferenciado em relação aos
modelos quantitativos.
Dá ao conjunto de usuários uma participação ativa na
representação dos documentos.
Seu uso se restringe a pequenos grupos de usuários com
interesses comuns.
33
Introdução Modelos Quantitativos
R.I. Na Web Conclusão
Modelos Dinâmicos
Apresentaremos três tipos conhecidos de modelos
dinâmicos:
•Sistemas Especialistas
•Redes Neurais Articifiais
•Algoritmos Genéticos
34
Introdução Modelos Quantitativos
R.I. Na Web Conclusão
Sistemas Especialistas
É um sistema computacional que procura representar o
conhecimento de um especialista humano em um domínio
particular, de maneira a auxiliar nas tomadas de decisões e
resolução de problemas relacionados a esse domínio.
Parte do princípio de que a inteligência não é apenas
raciocínio, mas também memória, ou seja, é possuir grande
quantidade de informação sobre determinado assunto.
35
Introdução Modelos Quantitativos
R.I. Na Web Conclusão
Sistemas Especialistas
São sistemas baseados em conhecimento.
Servem como consultores na tomada de
decisões em áreas restritas.
Permitem representar o conhecimento heurístico
na forma de regras obtidas através da
experiência e intuição de especialistas de uma
área específica.
36
Introdução Modelos Quantitativos
R.I. Na Web Conclusão
Sistemas Especialistas
A recuperação de informação é um processo cuja
eficiência depende grande parte do conhecimento sobre
o assunto.
Há dois exemplos de sistemas que utilizam
procedimentos típicos dos sistemas especialistas na
recuperação de informação.
37
Introdução Modelos Quantitativos
R.I. Na Web Conclusão
Sistemas Especialistas
Sistema IOTA
Desenvolvido no Laboratoire Génie Informatique de
Grenoble.
O processo de construção automática da base de
conhecimento é realizado através da identificação dos
principais conceitos contidos nos textos do conjunto de
documentos (corpus).
38
Introdução Modelos Quantitativos
R.I. Na Web Conclusão
Sistemas Especialistas
Sistema IOTA
Esses conceitos são identificados utilizando-se cálculos
estatísticos de co-ocorrência de pares de palavras.
Se duas palavras aparecerem próximas em vários
documentos do corpus então elas possuem um certo
relacionamento.
39
Introdução Modelos Quantitativos
R.I. Na Web Conclusão
Sistemas Especialistas
Sistema RUBRIC
Rule-Basic Retrieval of Information by Computer
O usuário é capaz de construir sua própria base de
conhecimento sobre um determinado assunto através da
especificação e organização de conceitos na forma de
uma rede de frames.
40
Introdução Modelos Quantitativos
R.I. Na Web Conclusão
Sistemas Especialistas
Sistema RUBRIC
Para cada conceito (frame) o usuário define um conjunto de
regras do tipo se...então que caracteriza o conceito.
Ex:
Se “recuperação” e “informação” então “recuperação de
informação” (0.5)
Aparecendo as palavras”recuperação” e “informação” no mesmo
documento, a probabilidade de se tratar de “recuperação de
informação” é de 50%.
41
Introdução Modelos Quantitativos
R.I. Na Web Conclusão
Redes Neurais Artificiais
A busca por um modelo artificial que simule o funcionamento
das células do cérebro data dos anos 40.
Nos anos 80 o entusiasmo nas pesquisas aumentou devido
a avanços metodológicos importantes e também graças aos
avanços da ciência da computação.
42
Introdução Modelos Quantitativos
R.I. Na Web Conclusão
Redes Neurais Artificiais
Uma das propriedades mais importantes de uma rede neural
é a capacidade de aprender através de exemplos e fazer
inferências sobre o que aprendeu, melhorando
gradativamente o seu desempenho.
43
Introdução Modelos Quantitativos
R.I. Na Web Conclusão
Redes Neurais Artificiais
De uma forma simplificada, uma rede neural artificial pode
ser vista como um grafo onde os nós são os neurônios e as
ligações fazem a função das sinapses.
44
Introdução Modelos Quantitativos
R.I. Na Web Conclusão
Redes Neurais Artificiais
(FERNEDA, 2003)
45
Introdução Modelos Quantitativos
R.I. Na Web Conclusão
Redes Neurais Artificiais
Uma tarefa comum para um sistema de recuperação de
informação é pesquisar documentos relevantes que
satisfazem uma determinada expressão de busca através
dos termos de indexação.
Essa organização pode ser comparada a uma estrutura de
uma rede neural.
46
Introdução Modelos Quantitativos
R.I. Na Web Conclusão
Redes Neurais Artificiais
Entrada da rede neural
Saída da rede
neural
(FERNEDA, 2003)
47
Introdução Modelos Quantitativos
R.I. Na Web Conclusão
Algoritmos Genéticos
É um processo repetitivo que mantém uma população de
“indivíduos” que representam as possíveis soluções para um
determinado problema.
A cada geração os indivíduos da população passam por uma
avaliação de sua capacidade em oferecer uma solução
satisfatória para o problema.
Essa avaliação é feita por uma função de adaptação ou
função de fitness.
48
Introdução Modelos Quantitativos
R.I. Na Web Conclusão
Algoritmos Genéticos
De acordo com essa avaliação alguns indivíduos,
selecionados de acordo com uma regra probabilística,
passam por um processo de reprodução, gerando uma nova
população de possíveis soluções.
Pressupõe-se que a população vá gradativamente ficando
mais apta para solucionar o problema.
49
Introdução Modelos Quantitativos
R.I. Na Web Conclusão
Algoritmos Genéticos
A aplicação dos algoritmos genéticos na recuperação de
informação representa um novo modelo para todo o
processo de recuperação.
As representações dos documentos podem ser vistas como
um tipo de um “código genético”.
50
Introdução Modelos Quantitativos
R.I. Na Web Conclusão
Algoritmos Genéticos
Nesse código genético um cromossomo é representado por
um vetor binário onde cada elemento armazena o valor 0 ou
1 (presença ou ausência de um determinado termo na
representação do documento).
51
Introdução Modelos Quantitativos
R.I. Na Web Conclusão
Algoritmos Genéticos
A aplicação dos algoritmos genéticos na recuperação de
informação se apresenta somente como uma possibilidade,
uma proposição para futuras implementações de sistemas
com características evolutivas.
52
RECUPERAÇÃO DE INFORMAÇÃO
MODELOS E APLICAÇÕES
Recuperação de
Informação na
WEB
Introdução Modelos Quantitativos Modelos Dinâmicos
Conclusão
Características da Web
A web é hoje considerada como a maior fonte de
informação das principais formas de conhecimento.
Nunca na história da humanidade tanta informação foi
produzida.
O seu uso intensivo, aliado ao crescimento exponencial,
vem mudando diversos aspectos da sociedade
contemporânea.
54
Introdução Modelos Quantitativos Modelos Dinâmicos
Conclusão
Características da Web
Alguns dados:
•A cada dois anos, cada habitante do planeta produz 800 MB de
informação digital
•De 2000 para 2003, o número de informações novas cresceu
30%.
•Todos os habitantes do planeta geraram informação digital nova
suficiente para lotar 500 mil bibliotecas do congresso nacional dos
EUA, a maior do mundo. Isso são 5 petabytes, ou seja, 5 bilhões
de gigabytes de dados!
Como achar qualquer informação nessa montanha de dados?
fonte: http://noticias.uol.com.br/mundodigital
55
Introdução Modelos Quantitativos Modelos Dinâmicos
Conclusão
Métodos de busca
Os search engines, ou mecanismos de busca, são as
ferramentas indicadas para o trabalho.
Em um acervo extremamente grande e dinâmico como o da
Web é essencial a indexação constante de suas páginas.
Para isso temos a indexação manual e a indexação
automática.
56
Introdução Modelos Quantitativos Modelos Dinâmicos
Conclusão
Indexação Manual
Usuários cadastram sua página e associam-na a uma ou mais
categorias (podendo sugerir uma nova categoria para a sua página).
Cada categoria é uma página Web formada por um conjunto de links
para as páginas relacionadas àquela categoria.
Os funcionários do site de busca fazem a análise da URL cadastrada,
podendo alterar a classificação.
O mais conhecido search engine que utiliza a indexação manual é o
Yahoo!
57
Introdução Modelos Quantitativos Modelos Dinâmicos
Conclusão
Indexação Manual
Vantagens
• Se a busca do usuário estiver relacionada diretamente a
uma categoria existente, é esperada uma alta precisão na
busca.
• Uma página encontrada, que foi indexada por esse método,
normalmente possui links para outras páginas relevantes
sobre o mesmo assunto.
58
Introdução Modelos Quantitativos Modelos Dinâmicos
Conclusão
Indexação Manual
Desvantagens
•Depende do cadastramento voluntário de páginas, isso reduz
a cobertura da busca.
•A procura por um assunto que não se enquadra em qualquer
categoria existente, torna da busca ineficiente.
59
Introdução Modelos Quantitativos Modelos Dinâmicos
Conclusão
Indexação Automática
Utiliza programas chamados spiders.
Um spider encontra páginas que podem ser cadastradas
seguindo os links de páginas que já estão no banco de dados
do buscador.
Depois de encontradas, as páginas são passadas para outro
software para a indexação, que identifica texto, links, e outros
conteúdos na página e arquiva esses dados no banco do
buscador.
60
Introdução Modelos Quantitativos Modelos Dinâmicos
Conclusão
Indexação Automática
Se uma página nunca foi "linkada" a qualquer outra, os
spiders não podem encontrá-la.
Por produzir milhares de resultados, exige o uso de alguns
truques para tornar a pesquisa mais rápida e precisa.
Google e Altavista são os mais conhecidos buscadores que
utilizam a indexação automática.
61
Introdução Modelos Quantitativos Modelos Dinâmicos
Conclusão
Meta-busca
Metabuscadores não possuem Banco de Dados
próprios.
Retornam o resultado proveniente da combinação de
outros mecanismos de busca, como Google, Yahoo!
Search, MSN Search, Ask Jeeves e vários outros.
62
Introdução Modelos Quantitativos Modelos Dinâmicos
Conclusão
Meta-busca
Metabuscadores são muito eficientes na localização de
temas muito específicos e difíceis de localizar.
Se a busca é simples, vale mais usar um mecanismo de
busca comum, pois os metabuscadores podem produzir
um amontoado de informação que servirá mais para
confundir do que para ajudar.
Alguns metabuscadores: WebCrawler, MetaCrawler,
SurfWax, Vivísimo.
63
Introdução Modelos Quantitativos Modelos Dinâmicos
Conclusão
Meta-busca
Buscadores escolhidos para integrar
a lista personalizada. Pode-se fazer
até 3 listas, contendo até 10
buscadores cada.
Lista de search engines disponíveis,
divididos por assunto.
64
http://www.surfwax.com
RECUPERAÇÃO DE INFORMAÇÃO
MODELOS E APLICAÇÕES
CONCLUSÃO
Introdução
Modelos Quantitativos
Modelos Dinâmicos R.I. Na Web
Conclusão
Com a “explosão da informação” e a urgência no tratamento
da crescente produção de informação, o computador foi a
solução mais direta.
A natural vocação dos computadores pelo processamento
matemático justifica a predominância dos modelos
quantitativos de recuperação de informação.
66
Introdução
Modelos Quantitativos
Modelos Dinâmicos R.I. Na Web
Conclusão
Os modelos dinâmicos rompem a rigidez imposta pelos
modelos quantitativos através da participação de usuários na
representação dos documentos.
Os trabalhos práticos disponíveis na literatura apresentam
somente testes utilizando um ambiente controlado, com um
conjunto de documentos reduzidos.
O desempenho computacional dos modelos dinâmicos em
situações reais ainda é uma incógnita.
67
Introdução
Modelos Quantitativos
Modelos Dinâmicos R.I. Na Web
Conclusão
Recuperar informação implica operar seletivamente um
estoque de informação, o que envolve processos cognitivos
que dificilmente podem ser formalizados através de um
algoritmo.
Mesmo que um modelo computacional de recuperação da
informação tenha como base algum tipo de vocabulário e
organização lógica, a equiparação dos significados
supostamente implícitos depende de uma análise intelectual.
68
RECUPERAÇÃO DE INFORMAÇÃO
MODELOS E APLICAÇÕES
FIM
69