RECUPERAÇÃO DE INFORMAÇÃO MODELOS E APLICAÇÕES

RECUPERAÇÃO DE INFORMAÇÃOMODELOS E APLICAÇÕES

Alessandro Marinho SilvaAndré Pires VieiraDiego Dainese PollaSergio Luis da SilvaWilson Witerkosk

RECUPERAÇÃO DE INFORMAÇÃOMODELOS E APLICAÇÕES

Índice

• Introdução

• Modelos Quantitativos

• Modelos Dinâmicos

• Recuperação de Informação na Web

• Conclusão

RECUPERAÇÃO DE INFORMAÇÃOMODELOS E APLICAÇÕES

INTRODUÇÃO

4

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.

5

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.

6

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 Palavra-Chave ou Busca por Similaridade.

7

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.

8

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.

9

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.

Coleção de

textos

FormaIntermediária

Mineração

Conhecimento

Técnicas deRI

Técnicas deEI

Processo de Mineração de Textos (Correa, 2003)

10

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.

11

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.

12

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.

13

Modelos Quantitativos Modelos Dinâmicos R.I. Na Web Conclusão

Indexação

Estrutura de Arquivo Invertido (Correa, 2003)

Os termos, ou palavras-chave, são extraídos dos textos e ficam armazenados juntamente com as referências para os respectivos documentos.

As buscas usam os índices extraídos dos documentos-texto

para comparações com a consulta do usuário.

14

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.

RECUPERAÇÃO DE INFORMAÇÃOMODELOS E APLICAÇÕES

MODELOS QUANTITATIVOS

16

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.

17

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

18

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).

19

Introdução Modelos Dinâmicos R.I. Na Web Conclusão

Modelo Booleano

(FERNEDA, 2003)

20

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.

21

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:

22

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:

23

Introdução Modelos Dinâmicos R.I. Na Web Conclusão

Modelo Vetorial

Para encontrar o grau de similaridade, calcula-se o co-seno 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.

24

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:

25

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:

26

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%.

27

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.

28

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.

29

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.

30

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 o complemento de Rel, a probabilidade de um documento d ser relevante em relação à expressão de busca é designada por p(Rel|d).

lRe

31

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:

RECUPERAÇÃO DE INFORMAÇÃOMODELOS E APLICAÇÕES

MODELOS DINÂMICOS

33

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.

34

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

35

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.

36

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.

37

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.

38

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).

39

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.

40

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.

41

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%.

42

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.

43

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.

44

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.

45

Introdução Modelos Quantitativos R.I. Na Web Conclusão

Redes Neurais Artificiais

(FERNEDA, 2003)

46

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.

47

Introdução Modelos Quantitativos R.I. Na Web Conclusão

Redes Neurais Artificiais

(FERNEDA, 2003)

Entrada da rede neuralSaída da rede neural

48

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.

49

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.

50

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”.

51

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).

52

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.

RECUPERAÇÃO DE INFORMAÇÃOMODELOS E APLICAÇÕES

Recuperação de Informação na

WEB

54

Introdução Modelos Quantitativos Modelos Dinâmicos Conclusão

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.

Características da Web

55

Introdução Modelos Quantitativos Modelos Dinâmicos Conclusão

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

Características da Web

56

Introdução Modelos Quantitativos Modelos Dinâmicos Conclusão

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.

Métodos de busca

57

Introdução Modelos Quantitativos Modelos Dinâmicos Conclusão

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!

Indexação Manual

58

Introdução Modelos Quantitativos Modelos Dinâmicos Conclusão

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.

Indexação Manual

59

Introdução Modelos Quantitativos Modelos Dinâmicos Conclusão

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.

Indexação Manual

60

Introdução Modelos Quantitativos Modelos Dinâmicos Conclusão

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.

Indexação Automática

61

Introdução Modelos Quantitativos Modelos Dinâmicos Conclusão

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.

Indexação Automática

62

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.

63

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.

64

Introdução Modelos Quantitativos Modelos Dinâmicos Conclusão

Meta-busca

http://www.surfwax.com

Lista de search engines disponíveis, divididos por assunto.

Buscadores escolhidos para integrar a lista personalizada. Pode-se fazer até 3 listas, contendo até 10 buscadores cada.

RECUPERAÇÃO DE INFORMAÇÃOMODELOS E APLICAÇÕES

CONCLUSÃO

66

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.

67

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.

68

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.

69

RECUPERAÇÃO DE INFORMAÇÃOMODELOS E APLICAÇÕES

FIM