UNIVERSIDADE FEDERAL DE CAMPINA GRANDE CENTRO DE ENGENHARIA ELÉTRICA E INFORMÁTICA DEPARTAMENTO DE SISTEMAS E COMPUTAÇÃO Sistemas de Recuperação da Informação Prof. Ulrich Schiel Sistemas de Recuperação da Informação ROTEIRO 1. INTRODUÇÃO 2. TÓPICOS DA RECUPERAÇÃO DA INFORMAÇÃO 2.1. Estruturas de arquivos 2.2. Indexação 2.3. Consultas Sistemas de Recuperação da Informação 3. INDEXAÇÃO DE INFORMAÇÃO 3.1 Filtragem 3.2 Análise léxica 3.3 Stoplist 3.4 Stemming ou truncagem 3.5 Construção de thesaurus 3.6 Indexação 1. ARMAZENAMENTO DE INFORMAÇÃO 4.1. Arquivos invertidos 4.2. Arquivos de assinatura 4.3. Retângulos ótimos Sistemas de Recuperação da Informação 5. CONSULTAS 5.1 modelo booleano 5.2 modelo vetorial 5.3 .modelo probabilístico 5.4 .modelos alternativos 1. DOCUMENTOS MULTIMÍDIA 1. EXTRAÇÃO DA INFORMAÇÃO 1. MINERAÇÃO DE TEXTOS 9. BIBLIOTECAS DIGITAIS E A WEB Sistemas de Recuperação da Informação BIBLIOGRAFIA LIVROS TEXTO R. Baeza-Yates e B. Ribeiro-Neto “Modern Information Retrieval”, Addison-Wesley, 1999 M.-F. Moens “Information Extraction: Algorithms and Prospects in a Retrieval Context” Springer Verlag, 2006. S. Weiss, N. Indurkhya, T. Zhang e F. Damerau “Text Mining: Predictive Methods for Analyzing Unstructured Information” Springer Verlag, 2005 Sistemas de Recuperação da Informação OUTROS C.D. Manning, P.Raghavan and H.Schütze, Introduction to Information Retrieval, Cambridge University Press. 2007. Download em: "http://www-csli.stanford.edu/~schuetze/information-retrieval-book.html W. B. Frakes, R. Baeza-Yates “Information Retrieval: Data Structures and Algorithms”, Prentice Hall, 1992 W. Y.Arms, “Digital Libraries”, MIT Press, 2000 INTRODUÇÃO INTRODUÇÃO Dados estruturados X dados (semi-)estruturados SRI OBJETOS OPERAÇÃO TAMANHO documento recuperação grande (probabilística) SGBD registro browsing recuperação grande (determinística) SBC regra inferência pequena INTRODUÇÃO Uma consulta Uma base de documentos coleção Documentos relevantes (R) Documentos recuperados (A) Documentos relevantes recuperados (Ra) • Cobertura = #Ra/#R • Precisão = #Ra/#A INTRODUÇÃO • Alfabeto • Palavras Objetos dos SRI • Termos • Conceitos • Documentos INTRODUÇÃO Alfabeto romano A,B,C,.. a,b,c,.. acentuação hebraico árabe Aleph Beith Samaku = “smk” ( )سمك, (peixe) َِبٌ ك ت ا ب ⇐ آ un b ā t i k /kitābun/ ‘um livro’ INTRODUÇÃO Alfabeto romano hebraico árabe grego A,B,C,.. a,b,c,.. acentuação Aleph Beith Samaku = “smk” ( )سمك, (peixe) Α α (alfa), Β β (beta), Γ γ (gamma), Δ δ (delta) INTRODUÇÃO Alfabeto Japonês Chinês (monosilábica) 日 本 語. nihongo Hànyǔ, 华 语/ 華 語 Huáyǔ 中 文, INTRODUÇÃO Palavras -É uma seqüência de caracteres terminada Por um branco ou um sinal (. , ; : ‘ “ -) Mr. O’Neill thinks that the boys’ stories about Chile’s capital aren’t amusing. Dever-se-ia mantê-la. Guarda-chuva neill oneill o’neill o’ neill o neill ? aren’t arent are n’t aren t are not? mantê la mantê-la manter ela Guarda chuva Guarda-chuva INTRODUÇÃO Palavras Quais caracteres? -É uma seqüência de caracteres terminada por um branco ou um sinal • letras ! • só letras ? B12 OS/2 MP3 W3C • começando por letra? 3D 3FN • outros símbolos? C++ INGRES* • excluir números, tabelas, figuras, etc. • considerar gowords INTRODUÇÃO Palavras Maiúsculas e minúsculas? acentuação siglas Palavra e palavra Geomedia GeoMedia GEOMEDIA acentuação ~ acentuacao pelo ~ pêlo ? OCL = Object Constraint Language Organisation Communiste Libertaire INTRODUÇÃO Termos Guarda-chuva Cada palavra é um termo Termos compostos bancos de dados 1, 2 ou 3 termos? bancos dados banco de dados distribuído Pesquisa sobre o anarquismo Recherches sur l’anarchism ? termos Anarchismusforschung INTRODUÇÃO Conceitos Sinonímia Efetuar ~ fazer ~ cumprir ~ executar ~ realizar Synset = classe de equivalência de sinônimos Termo representativo = 1 elemento do Synset INTRODUÇÃO Conceitos Homonímia Grosso: 1. volumoso (livro grosso) 2. áspero (mãos grossas) 3. pastoso (caldo grosso) 4. grosseiro (mal-educado) Banco: 1. instituição financeira (negócios e finanças) 2. objeto para sentar (mobília) 3. conjugação do verbo bancar () 4. repositório (Informática) INTRODUÇÃO Termo+Significado+Contexto Conceito INTRODUÇÃO Thesaurus Termo hipernímia Termo relacionado Termo sinonímia Termo meronímia hiponímia Termo Termo INTRODUÇÃO Thesaurus Veículo Frota hipernímia motorista trânsito rodovia relacionado dirigir meronímia Termo Automóvel sinonímia meronímia hiponímia Motor Fiat Uno Carro INTRODUÇÃO Documentos • O que é um documento? • • • • • • Um arquivo eletrônico Um hipertexto Uma enciclopédia Um e-mail com anexos Um artigo em Anais Os anais INTRODUÇÃO Documentos • Qual o formato? • Qual o alfabeto? • Qual o idioma? • doc, pdf, doc, txt • Romano, Chinês, árabe • Português, ... INTRODUÇÃO Processo da Recuperação da informação INTRODUÇÃO Processo da recuperação da informação Docu- texto mento extração palavras stoplist palavras radicais radicais associação consulta usuário extração lista ordenada palavras ranking radicais Lista de documentos radicais operadores Booleanos Banco de Dados TÓPICOS DA RECUPERAÇÃO DA INFORMAÇÃO Indexação Estruturas de arquivos Recuperação TÓPICOS DA RECUPERAÇÃO DA INFORMAÇÃO • Estruturas de arquivos • OPÇÕES: Texto puro • Pesquisa em texto Arquivo de índices • Arquivos invertidos • hashing • Retângulos ótimos • • • Arquivos assinatura Árvores Patrícia (sufixos) • Também para tabelas, etc. Grafos (redes semânticas, ontologias,.) TÓPICOS DA RECUPERAÇÃO DA INFORMAÇÃO Consultas e recuperação • Modelos baseados em teoria dos conjuntos • Booleano e Booleano extendido • Conjuntos Fuzzy • Modelos algébricos • Vetorial básico e generalizado • Contextual • Redes Neurais • Modelos probabilísticos • básico • Redes Bayesianas TÓPICOS DA RECUPERAÇÃO DA INFORMAÇÃO Consultas e recuperação • Modelos sobre textos estruturados Consideram a estrutura do documento (itálico, negrito, figuras, proximidades) • • Listas disjuntas (Capítulos, seções, parágrafos) proximidades • Modelos de Browsing • Browsing plano • Browsing com diretórios • Hipertextos INDEXAÇÃO DA INFORMAÇÃO 1. 2. 3. 4. 5. 6. Filtragem Análise léxica Stoplist Truncagem (stemming) Construção do thesaurus Indexação INDEXAÇÃO DA INFORMAÇÃO 1. Filtragem • Conversão para um formato padrão • Remover macros do editor • Remover símbolos especiais • Hipertextos • doc, rtf, pdf, ps, tex, ... • html • xml & etc (rdf, dc, xmlschema, owl,..). INDEXAÇÃO DA INFORMAÇÃO EXEMPLO ‘Semi-estruturado’ Rtf: {\rtf1\ansi\ansicpg1252\uc1\} {\*\generator Microsoft Word 10.0.2627;}{\info{\title Semi}{\author Ulrich Schiel} {\operator Ulrich Schiel} Semi}{\insrsid3955129\charrsid8669994 }{\insrsid8669994\charrsid8669994 e}{ \insrsid3955129 struturado \par }} INDEXAÇÃO DA INFORMAÇÃO EXEMPLO html: <html xmlns:o="urn:schemas-microsoftcom:office:office" xmlns:w="urn:schemas-microsoftcom:office:word" xmlns="http://www.w3.org/TR/REC-html40"> <head> <title>Semi-estruturado</title> <!--[if gte mso 9]><xml> <w:WordDocument> <w:Zoom>150</w:Zoom> <w:GrammarState>Clean</w:GrammarState> <w:HyphenationZone>21</w:HyphenationZone > <w:BrowserLevel>MicrosoftInternetExplorer4< /w:BrowserLevel> </w:WordDocument> </xml><![endif]--> <style> ‘Semi-estruturado’ <!-/* Style Definitions */ p.MsoNormal, li.MsoNormal, page Section1 .......;} div.Section1 {page:Section1;} --> </style> <!--[if gte mso 10]> <style> /* Style Definitions */ ....... </style> <![endif]--> </head> <div class=Section1> <p class=MsoNormal><b>Semi</b>estruturado</p> </div> </body> </html> INDEXAÇÃO DA INFORMAÇÃO ‘Semi-estruturado’ EXEMPLO Em pdf INDEXAÇÃO DA INFORMAÇÃO 1. Filtragem – análise léxica • Conversão para um formato padrão • Remover macros do editor • Remover não-palavras • Remover maiúsculas/minúsculas • Remover acentuação INDEXAÇÃO DA INFORMAÇÃO Stopwords • Critérios: • Classificação gramatical (artigos, determinantes, pronomes, numerais, advérbios, preposições) • Palavras mais frequentes Stopwords Palavras mais frequentes INDEXAÇÃO DA INFORMAÇÃO Stopwords • Problemas • Termos compostos • Frases: • Siglas • Especiais • “banco de dados” “banco” “dados” “ser ou não ser” “ser” OCL Object Constraint Language B12, 3D, 007 B12, tridimensional, James Bond Solução • Dicionários de termos compostos, frases, siglas e de ‘gowords’ INDEXAÇÃO DA INFORMAÇÃO Stopwords • Como remover stopwords de forma eficiente? • Após a análise léxica • Junto com a análise léxica INDEXAÇÃO DA INFORMAÇÃO Stopwords • • Algoritmo de filtragem: Considere uma lista SW&CW contendo stopwords e palavras compostas 1. Ler, sequencialmente, o documento de entrada até delimitar uma palavra p. (considerar regras básicas de construção de palavras e exceções (gowords)) 1. se (p ocorre em SW&CW) OU (é o início de um termo composto em SW&CW) se p é o início de um termo composto em SW&CW então avançar no documento para verificar se é o composto se for o composto então gravar o termo composto na saída, voltar para 1. senão manter a primeira palavra e voltar para 1. senão desconsiderar esta palavra e voltar para 1. 1. senão gravar a palavra identificada na saída e voltar para 1. INDEXAÇÃO DA INFORMAÇÃO Filtragem - Exercício Baseado no texto a seguir, construir: • regras de identificação de palavras • uma tabela de gowords • uma tabela de stopwords • uma tabela de palavras compostas Acompanhar o algoritmo de filtragem e mostrar o resultado INDEXAÇÃO DA INFORMAÇÃO Filtragem - Exercício Term-frequency (tf) é uma medida que utiliza o número de ocorrências do termo tj no documento di. Porém quando termos com alta freqüência aparecem na maioria dos documentos da coleção eles não fornecem informação útil para diferenciar documentos. A medida inverse document frequency (idf) favorece termos que aparecem em poucos documentos da coleção. Tal medida varia inversamente ao número x de documentos que contem o termo tj em uma coleção de documentos e é definida como log (n/x). Baseado nessas duas medidas de freqüência pode-se definir a medida tfidf, combinando-as, como mostra a tabela a seguir: INDEXAÇÃO DA INFORMAÇÃO Stemming (normalização/truncagem) OPÇÕES: • Truncar os termos • Expandir a consulta • Processo de remover variantes morfológicas aumentando a abrangência de um termo • • • Variantes de escrita, erros normalização variações de número e gênero, conjugações de verbos lemmatization/normalização Definição de radicais Stemming INDEXAÇÃO DA INFORMAÇÃO Stemming (normalização/truncagem) OPÇÕES: • Regras genéricas Processos individuais (com dicionários, análise gramatical, etc.) • Substituir • *s * • *aria * • *eiro * • *mento * Substituir • casa, verbo casar • casa, substantivo casa • casamento casa (??) • (ing) theses thesis (??) INDEXAÇÃO DA INFORMAÇÃO Stemming (normalização/truncagem) • Normalização (lemmatization) • Verbos conjugados infinitivo • substantivos para o singular masculino • Variantes, erros dicionário, análise sintática “Se tu casas comigo nossas casas serão vendidas e teremos uma cama de casal”.c “você casar casa ser vender ter cama casal”. INDEXAÇÃO DA INFORMAÇÃO Stemming (normalização/truncagem) • Algoritmos de Truncagem (stemming) • Tabela explícita • Algoritmo de Porter Termo Radical engenharia engenho engenheiro engenh engenh engenh INDEXAÇÃO DA INFORMAÇÃO Stemming (normalização/truncagem) • Algoritmos de Truncagem (stemming) • Tabela explícita Termo Radical engenharia engenho engenheiro engenh engenh engenh INDEXAÇÃO DA INFORMAÇÃO Stemming (normalização/truncagem) • Algoritmos de Truncagem (stemming) • Variedade de sucessores “Se tu casas comigo, nossas casas serão vendidas e teremos uma cama de casal” v(c) = 2 v(ca) = 2 v(cas) = 1 v(casa) = 2 INDEXAÇÃO DA INFORMAÇÃO Stemming (normalização/truncagem) • Truncagem (stemming) • • Remover sufixos baseado em regras pré-estabelecidas Calcular a medida m do radical segundo • Seja C uma sequência de consoantes da palavra • Seja V uma sequência de vogais da palavra, • Então m é determinado por [C][(VC)m[V] Exemplos m=0 la, cha m=1 lar, casa m=2 chave m=3 largar, Brasil INDEXAÇÃO DA INFORMAÇÃO Stemming (normalização/truncagem) • Truncagem (stemming) • • Remover sufixos baseado em regras pré-estabelecidas Substituir • (m>1) *s * • (m>0) *aria * • (m>0) *eiro * • (m>1) *mento * • (m>1) *ar *a • Exemplos • casas casas • padaria pad • padeiro pad • casamento casa • casar casa INDEXAÇÃO DA INFORMAÇÃO Stemming (normalização/truncagem) • Truncagem (stemming) • Remover sufixos baseado em regras pré-estabelecidas “você casar casa ser vender ter cama casal”. “você casa casa ser vender ter cama casa”. INDEXAÇÃO DA INFORMAÇÃO Stemming (normalização/radicalização) Desambiguação “você casa casa ser vender ter cama casa”. Desambiguação por dicionário: dicionário Term Class. Gram. o casa substantivo significado casa- verbo Unir-se pelo casamento casa- substantivo Par composto por marido e mulher moradia INDEXAÇÃO DA INFORMAÇÃO Indexação semântica - conceitos Desambiguação por dicionário: Termos Conceito Significado Contexto INDEXAÇÃO DA INFORMAÇÃO Indexação semântica - conceitos • Vetor de todos conceitos – V = <c1,..cn> • Cada termo t é instanciado neste vetor, com Vt=<t1,..tn>: • Para cada conceito cj em V: • tj é positivo se é relacionado a cj • tj é zero se não é relacionado a cj • tj é negativo se contradiz cj INDEXAÇÃO DA INFORMAÇÃO Indexação semântica - conceitos Desambiguação: Análise Semântica Latente (LSA): Descobre o contexto de palavras analisando matrizes termo X documento INDEXAÇÃO DA INFORMAÇÃO Indexação semântica - LSA Palavra da pesquisa Retorno de alta relevância Palavras com baixa relevância médico Hospital Enfermeira Tratamento Paciente Medicamento Madeira Asfalto Árvore carro Automóvel Motorista Veículo Chassis Elefante Computador Telefone INDEXAÇÃO DA INFORMAÇÃO Indexação semântica - LSA Análise Semântica Latente (LSA) - Fontes: Fontes: • http://www.intelliwise.com/reports/info2004.pdf (em português) • http://lsa.colorado.edu/papers/dp1.LSAintro.pdf INDEXAÇÃO DA INFORMAÇÃO Ponderação Cálculo da importância de um termo em um documento tf = freq (k,D) (freqüência do termo k no documento D) idf = log (N / nk) (inverse document frequency), onde N é o número de termos na coleção e nk número de vezes que o termo ocorre na coleção. tfidf = freq (k,S) log (N / nk) (inverse document frequency), é o peso do termo k no documento D INDEXAÇÃO DA INFORMAÇÃO Ponderação Cálculo da importância de um termo em um documento – considerando o tamanho dos documentos INDEXAÇÃO DA INFORMAÇÃO Ponderação um novo documento contém as palavras EXEMPLO: na base de 2048 as palavras ocorrem: –‘petróleo’ 128 vezes –‘petróleo’ 4 vezes –‘Brasil’ 16 vezes –‘Brasil’ 8 vezes – ‘ refinaria’ 1024 vezes – ‘ refinaria’ 10 vezes teríamos os cálculos: Vetor com tf : <‘petróleo’: 4, ‘Brasil’: 8, ‘ refinaria’: 10> cálculo com tfitf (‘petróleo’)= 4*log(2048/128) = 4*1,2 = 4,8 tfitf (‘Brasil’)= 8*log(2048/16) = 8*2,1 = 16,87 tfitf (‘refinaria’)= 10*log(2048/1024) = 10*0,3 = 3 Logo temos o vetor <4.8, 16.87, 3> INDEXAÇÃO DA INFORMAÇÃO Ponderação EXTENSÕES: • tfidf não leva em consideração – a distribuição do item nos outros documentos – ponderação por sinal – a importância do termo no todo – valor de discriminação • DISCRIMi = SimMédiai – SimMédia SimMédia = similaridade média dos termos da base SimMédiai = similaridade média dos termos da base retirando i • peso(ki) = tfi * DISCRIMi INDEXAÇÃO DA INFORMAÇÃO Ponderação PROBLEMAS COM O CÁLCULO DE PESOS: Mudanças na base de documentos alteram os valores SOLUÇÕES • desconsiderar as mudanças e refazer os cálculos periódicamente • refazer os cálculos após um fator de mudanças ser alcançado • usar fórmulas que desconsideram a base de documentos INDEXAÇÃO DA INFORMAÇÃO Inclusão no Thesaurus (tesauro) INDEXAÇÃO DA INFORMAÇÃO Inclusão no Thesaurus (tesauro) INDEXAÇÃO DA INFORMAÇÃO Inclusão no Thesaurus (tesauro) • EXEMPLO Thesaurus ERIC Descriptors Computational linguistics Broader Terms Linguistics Narrower Terms Machine Translation Related Terms Automatic Indexing Computer Science Language Processing Linguistic Theory Mathematical Linguistics Mathematical Logic Programming Languages Semantics Statistics Structural Analysis (Linguistics) Word Frequency INDEXAÇÃO DA INFORMAÇÃO Inclusão no Thesaurus (tesauro) • Cada nó do thesaurus representa um CONCEITO • Dado um termo deve-se encontrar o conceito adequado SOLUÇÃO • um dicionário: Termo Conceito PROBLEMA: Homônimos SOLUÇÃO • um dicionário: Termo X contexto X significado Conceito INDEXAÇÃO DA INFORMAÇÃO Thesaurus – relações entre os termos •Relações Hierarquicas – é-um subclasse (Automóvel Veículo) instância (João da Silva Pessoa) •Relação Hierarquicas – parte-de (meronímia) agregado (Motor Automóvel) conjunto (Estudante Turma) •Relação Horizontais sinonímia (Carro Automóvel) antonímia (Empregado Desempregado) relacionado (Carro motorista estrada) INDEXAÇÃO DA INFORMAÇÃO Inclusão no Thesaurus (tesauro) • NORMALIZAÇÃO do vocabulário – formas nominativas – poucos adjetivos – questões de maiúsculas, notações, abreviações, acentuação, etc • CONSTRUÇÃO – manual • (definir domínio, definir estrutura, coletar termos, incluir termos, ‘inverter’ estrutura criando ordem alfabética) – automática (one shot ou incremental) – semi-automática INDEXAÇÃO DA INFORMAÇÃO Thesaurus • Construção Automática de um Thesaurus Construção automática baseada em termos compostos: Banco de Dados Banco de Dados Espacial Banco de Dados Temporal Banco de Dados Espaço-temporal INDEXAÇÃO DA INFORMAÇÃO Thesaurus • Construção Automática de um Thesaurus Construção automática baseada em frequências: Níveis de Frequência T1 com f(t1) = n T2 com f(t2) = n1 <n0 T3 com f(t3) = n2 < n1 0 1 2 INDEXAÇÃO DA INFORMAÇÃO Thesaurus Construção automática de thesauri: • análise de co-ocorrências para formar termos compostos. – usa LSA ou outra técnica para encontrar palavras relacionadas • espaço de conceitos –FILTRAGEM: Extrair todos termos de uma coleção de documentos de um domínio. usar dicionários, stop-words, stemming e criaçao de termos compostos baseado em termos adjacentes – ANÁLISE DE CO-OCORRÊNCIAS: – Associações baseadas em modelos cognitivos de redes de conceitos do usuário INDEXAÇÃO DA INFORMAÇÃO Thesaurus Construção automática de thesauri: • Redes Bayesianas – è criado um grafo dirigido acíclico modelando situações de causa e efeito EXEMPLO – “Quando a família sai de casa acendo a luz da varanda e deixo o cachorro solto no jardim. O cachorro no jardim nota quando alguém está no portão. Quando ouço alguém no portão, vou até lá. cachorro fora vou ao portão família sai luz acesa alguém no portão ESTRUTURAS DE ARQUIVOS Thesaurus retangular de relações termo X documento SIM INDEXAÇÃO DA INFORMAÇÃO Thesaurus Construção manual de thesauri: • definir o domínio • definir atributos dos objetos a serem indexados (título, resumo, índice, etc.) • definir relacionamentos (sinonímia, proximidade, termlos relacionados, termos compostos, hierarquias, etc. • aplicar algoritmo de indexação e clustering KWIC+KWAC+KWOC `banco de dados` • KWOC: palavra-chave fora de contexto (banco: assento) • KWIC: palavra-chave no contexto (banco: repositório) • KWAC: palavra-chave e contexto (banco: banco de dados)