Upload
diogo-benica
View
229
Download
1
Embed Size (px)
DESCRIPTION
Apresentação do trabalho de conclusão de curso sore recuperação de informação apresentado em Dezembro de 2012.
Citation preview
Análise dos Modelos de Recuperação de Informação
Diogo Benicá Pereira
Faculdade Campo Limpo Paulista 01Dez/2012
Trabalho para Conclusão de Curso | Orientador: André Marcos da SilvaFaculdade Campo Limpo Paulista
Faculdade Campo Limpo Paulista 02Dez/2012
qual o problema?Muita informação!Não é fácil encontrar um dado relevante no meio de tanta informação.
Faculdade Campo Limpo Paulista 03Dez/2012
qual a solução?Sistemas de Recuperaçãode InformaçãoPara a tarefa de buscar informação relevante dentro de um conjunto de documentos.
Documentos Necessidade
IndexaçãoEspecificação
da Consulta
ÍndicesRepresentação
dos Documentos Consultas
Recuperação
Lista de Documentos
Perda de Informação
documentos
o que é IR?
Faculdade Campo Limpo Paulista 04Dez/2012
Informa;on Retrieval
Encontrar material de natureza não-‐estruturada que saQsfaz uma informação requerida a parQr de
grandes coleções.“ “- Mainning
Faculdade Campo Limpo Paulista 05Dez/2012
o que é um documento?Um documento pode ser qualquer unidadeUm texto inteiro, um capítulo, um parágrago, etc.
A escolha depende do resultado desejado
Lorem����������� ������������������ ipsum����������� ������������������ dolor����������� ������������������ sit����������� ������������������ amet,����������� ������������������ consectetur����������� ������������������ adipisicing����������� ������������������ elit,����������� ������������������ sed����������� ������������������ do����������� ������������������ eiusmod����������� ������������������ tempor.
incididunt����������� ������������������ ut����������� ������������������ labore����������� ������������������ et����������� ������������������ dolore����������� ������������������ magna����������� ������������������ aliqua.����������� ������������������ Ut����������� ������������������ enim����������� ������������������ ad����������� ������������������ minim����������� ������������������ veniam,����������� ������������������ quis����������� ������������������ nostrud����������� ������������������ exercitation����������� ������������������ ullamco.����������� ������������������ Laboris����������� ������������������ nisi����������� ������������������ ut����������� ������������������ aliquip����������� ������������������ ex����������� ������������������ ea����������� ������������������ commodo����������� ������������������ consequat.����������� ������������������ Duis����������� ������������������ aute����������� ������������������ irure����������� ������������������ dolor����������� ������������������ in����������� ������������������ reprehenderit����������� ������������������ in����������� ������������������ voluptate����������� ������������������ velit����������� ������������������ esse����������� ������������������ cillum����������� ������������������ dolore����������� ������������������ eu����������� ������������������ fugiat����������� ������������������ nulla����������� ������������������ pariatur.
Excepteur����������� ������������������ sint����������� ������������������ occaecat����������� ������������������ cupidatat
Lorem����������� ������������������ ipsum����������� ������������������ dolor����������� ������������������ sit����������� ������������������ amet,����������� ������������������ consectetur����������� ������������������ adipisicing����������� ������������������ elit,����������� ������������������ sed����������� ������������������ do����������� ������������������ eiusmod����������� ������������������ tempor.
incididunt����������� ������������������ ut����������� ������������������ labore����������� ������������������ et����������� ������������������ dolore����������� ������������������ magna����������� ������������������ aliqua.����������� ������������������ Ut����������� ������������������ enim����������� ������������������ ad����������� ������������������ minim����������� ������������������ veniam,����������� ������������������ quis����������� ������������������ nostrud����������� ������������������ exercitation����������� ������������������ ullamco.����������� ������������������ Laboris����������� ������������������ nisi����������� ������������������ ut����������� ������������������ aliquip����������� ������������������ ex����������� ������������������ ea����������� ������������������ commodo����������� ������������������ consequat.����������� ������������������ Duis����������� ������������������ aute����������� ������������������ irure����������� ������������������ dolor����������� ������������������ in����������� ������������������ reprehenderit����������� ������������������ in����������� ������������������ voluptate����������� ������������������ velit����������� ������������������ esse����������� ������������������ cillum����������� ������������������ dolore����������� ������������������ eu����������� ������������������ fugiat����������� ������������������ nulla����������� ������������������ pariatur.
Excepteur����������� ������������������ sint����������� ������������������ occaecat����������� ������������������ cupidatat
Lorem����������� ������������������ ipsum����������� ������������������ dolor����������� ������������������ sit����������� ������������������ amet,����������� ������������������ consectetur����������� ������������������ adipisicing����������� ������������������ elit,����������� ������������������ sed����������� ������������������ do����������� ������������������ eiusmod����������� ������������������ tempor.
incididunt����������� ������������������ ut����������� ������������������ labore����������� ������������������ et����������� ������������������ dolore����������� ������������������ magna����������� ������������������ aliqua.����������� ������������������ Ut����������� ������������������ enim����������� ������������������ ad����������� ������������������ minim����������� ������������������ veniam,����������� ������������������ quis����������� ������������������ nostrud����������� ������������������ exercitation����������� ������������������ ullamco.����������� ������������������ Laboris����������� ������������������ nisi����������� ������������������ ut����������� ������������������ aliquip����������� ������������������ ex����������� ������������������ ea����������� ������������������ commodo����������� ������������������ consequat.����������� ������������������ Duis����������� ������������������ aute����������� ������������������ irure����������� ������������������ dolor����������� ������������������ in����������� ������������������ reprehenderit����������� ������������������ in����������� ������������������ voluptate����������� ������������������ velit����������� ������������������ esse����������� ������������������ cillum����������� ������������������ dolore����������� ������������������ eu����������� ������������������ fugiat����������� ������������������ nulla����������� ������������������ pariatur.
Excepteur����������� ������������������ sint����������� ������������������ occaecat����������� ������������������ cupidatat
Faculdade Campo Limpo Paulista 06Dez/2012
como funciona?Modelos de Recuperação
Modelos quan;ta;vos Modelos dinâmicos
BooleanoVetorialProbabilísQcoBooleano estendidoFuzzy
Sistemas especialistasRedes neuraisAlgoritmos genéQcos
Booleano
Faculdade Campo Limpo Paulista 07Dez/2012
modelo booleanoÁlgebra booleanaSistema para manipular regras e símbolos.
Lógica aristotélicaAQngir conhecimento sem contradição.
Verdadeiro ou Falso
Faculdade Campo Limpo Paulista 08Dez/2012
modelo booleanoExpressões booleanas
termo1 AND (termo2 OR termo3)ex. “Recuperação” AND (“Informação” OR “Texto”)
termo1 n unidades termo2ex. “Recuperação” 5 unidades “Informação”
Faculdade Campo Limpo Paulista 09Dez/2012
como funcionaModelos de Recuperação
Modelos quan;ta;vos Modelos dinâmicos
BooleanoVetorialProbabilísQcoBooleano estendidoFuzzy
Sistemas especialistasRedes neuraisAlgoritmos genéQcos
Vetorial
Faculdade Campo Limpo Paulista 10Dez/2012
modelo vetorialResultados parciaisUso de pesos nos termos para determinar quanto cada documento é semelhante à expressão de busca.
Tudo são vetoresDocumentos e expressões de busca são representados como vetores.
Peso termo1 Peso termo2 Peso termo3 Peso termo4Documento
Faculdade Campo Limpo Paulista 11Dez/2012
como funcionaModelos de Recuperação
Modelos quan;ta;vos Modelos dinâmicos
BooleanoVetorialProbabilísQcoBooleano estendidoFuzzy
Sistemas especialistasRedes neuraisAlgoritmos genéQcosProbabilísQco
Faculdade Campo Limpo Paulista 12Dez/2012
modelo probabilistícoTeoria da probabilidadeExperimentos aleatórios em condições iguais com resultados diferentes.
Probabilidade de um evento
EventoResultados possíveis
16
Faculdade Campo Limpo Paulista 13Dez/2012
como funcionaModelos de Recuperação
Modelos quan;ta;vos Modelos dinâmicos
BooleanoVetorialProbabilísQcoBooleano estendidoFuzzy
Sistemas especialistasRedes neuraisAlgoritmos genéQcos
Booleano estendido
Faculdade Campo Limpo Paulista 14Dez/2012
modelo booleano estendidoUnião do modelo booleano e do vetorialJunta a potencialidade do booleano com a precisão do vetorial.
Operadores com pesosOs operadores (AND e OR) também possuem pesos.
Faculdade Campo Limpo Paulista 15Dez/2012
como funcionaModelos de Recuperação
Modelos quan;ta;vos Modelos dinâmicos
BooleanoVetorialProbabilísQcoBooleano estendidoFuzzy
Sistemas especialistasRedes neuraisAlgoritmos genéQcos
Fuzzy
Faculdade Campo Limpo Paulista 16Dev/2012
modelo fuzzyBaseado na lógica fuzzy
Opera com incerteza e verdade parcialUm elemento tem um grau de perQnência em um conjunto.
Elemento
75%Cidade 1
25%Cidade 2
cidade 1 cidade 2
Faculdade Campo Limpo Paulista 17Dez/2012
como funcionaModelos de Recuperação
Modelos quan;ta;vos Modelos dinâmicos
BooleanoVetorialProbabilísQcoBooleano estendidoFuzzy
Sistemas especialistasRedes neuraisAlgoritmos genéQcos
Sistemas especialistas
Faculdade Campo Limpo Paulista 18Dez/2012
sistemas especialistasEmula a especialização humana em um domínioEntrada de conhecimento a parQr de especialistas.
Regras, inferência e feedbackAtravés de regras <SE -‐> ENTÃO> faz inferência e adquire mais conhecimento através do feedback do usuário.
Faculdade Campo Limpo Paulista 19Dez/2012
como funcionaModelos de Recuperação
Modelos quan;ta;vos Modelos dinâmicos
BooleanoVetorialProbabilísQcoBooleano estendidoFuzzy
Sistemas especialistasRedes neuraisAlgoritmos genéQcosRedes neurais
Faculdade Campo Limpo Paulista 20Dez/2012
redes neuraisSistema modelando os circuitos cerebraisProcura obter um comportamento inteligente.
Vários neurônios formam uma rede neuralCada neurônio tem várias entradas e uma função que transforma em uma saída.
Capacidade de aprender com exemplosMelhora gradual de desempenho através de inferências.
Faculdade Campo Limpo Paulista 21Dez/2012
algoritmos genéticosBaseado na teoria evolucionista de Darwin
Seleção naturalOs algoritmos se “reproduzem” e se adaptam para que cada geração seja melhor em resolver o problema.
Faculdade Campo Limpo Paulista 22Dez/2012
na práticaAnálise dos modelosCriação de protóQpos dos modelos booleano, vetorial e booleano estendido.
ComparaçãoAnálise do tempo de execução, uso de memória e qualidade de resultado.
AmbientePHP 5.3 (executado no terminal).
Faculdade Campo Limpo Paulista 23Dez/2012
na prática (documento)DocumentosCada modelo será testado com 9 diferentes documentos de texto.Os documentos têm aproximadamente 150, 900 e 1800 palavras.
Expressão de buscaPara cada grupo de documentos será aplicada uma expressão de busca com 3 e depois 6 termos. Ex: termo1 AND termo2 OR termo3
termo1 AND (termo2 OR termo3) AND termo4 OR (termo5 AND termo6)
Faculdade Campo Limpo Paulista 24Dez/2012
resultados (Modelo booleano)
0 kb
250 kb
500 kb
750 kb
1000 kb
3 termos 6 termos
947 kb947 kb
681 kb681 kb
458 kb458 kb
150 palavras 900 palavras 1800 palavras
Uso de Memória
0 s
0,00005 s
0,00010 s
0,00014 s
0,00019 s
3 termos 6 termos
0,00019
0,000160,00015
0,000120,00014
0,00009
150 palavras 900 palavras 1800 palavras
Tempo de Execução
Faculdade Campo Limpo Paulista 25Dez/2012
resultados (Modelo vetorial)
0 kb
250 kb
500 kb
750 kb
1000 kb
3 termos 6 termos
967 kb967 kb
697 kb697 kb
465 kb465 kb
150 palavras 900 palavras 1800 palavras
Uso de Memória
0 s
0,00500 s
0,01000 s
0,01500 s
0,02000 s
3 termos 6 termos
0,017750,01753
0,009030,00890
0,002220,00221
150 palavras 900 palavras 1800 palavras
Tempo de Execução
Faculdade Campo Limpo Paulista 26Dez/2012
resultados (Modelo booleano estendido)
0 kb
250 kb
500 kb
750 kb
1000 kb
3 termos 6 termos
967 kb967 kb
697 kb697 kb
465 kb465 kb
150 palavras 900 palavras 1800 palavras
Uso de Memória
0 s
0,00750 s
0,01500 s
0,02250 s
0,03000 s
3 termos 6 termos
0,026810,02676
0,015130,01511
0,003320,00328
150 palavras 900 palavras 1800 palavras
Tempo de Execução
Faculdade Campo Limpo Paulista 27Dez/2012
conclusõesModelo booleano é muito rápido!Seguido do modelo vetorial e depois o modelo booleano estendido.
Modelo booleano estendido tem melhores resultados
Crescimento linear de memória e tempoTodos os modelos apresentaram um crescimento linear em relação ao tamanho dos documento.
(experimento)
Faculdade Campo Limpo Paulista 28Dez/2012
conclusõesModelos quan;ta;vos estão consolidadosPresentes na web e na maioria dos sistemas de recuperação.
Modelos dinâmicos ainda são complexos
Modelos quan;ta;vos não são tolerantes à falhasErros de gramáQca, semânQca e cultura não são levados em conta.
(geral)
Dircil implementação e de domínio específico.
Faculdade Campo Limpo Paulista 29Dez/2012
fim
Faculdade Campo Limpo Paulista 30Dez/2012
?