4a Reunião de Coordenação Regional da BVS grupo de trabalho TI Implementação do método Trigram Phrase Matching para problemas de similaridade de textos Adalberto Tardelli [email protected] Operação de Fontes de Informação BIREME/OPAS/OMS Salvador, 20 de Setembro de 2005 Tardelli, Adalberto O; Anção, Meide S; Packer, Abel L; Sigulem, Daniel. - An implementation of the trigram phrase matching method for text similarity problems. Bos, Lodewijk; Laxminarayan, Swamy; Marsh, Andy. Medical and care compunetics. Amsterdam, IOS Press, 2004. p.43-9 (Studies in Health Technology and Informatics, 103). • An implementation of the trigram phrase matching method for text similarity problems. Stud Health Technol Inform. 2004;103:43-9. PMID: 15747904 [PubMed - indexed for MEDLINE] An implementation of the Trigram Phrase Matching method for text similarity problems Adalberto O. TARDELLI1, Meide S. ANÇÃO2, Abel L. PACKER1, Daniel SIGULEM2 1 Latin American and Caribbean Center for Health Science Information (BIREME/PAHO/WHO), São Paulo, Brazil 2 Health Informatics Department, Federal University of São Paulo (DIS/UNIFESP), São Paulo, Brazil Abstract: The representation of texts by term vectors with element values calculated by a TFIDF method yields to significant results in text similarity problems, such as finding related documents in bibliographic or full-text databases and identifying MeSH concepts from medical texts by lexical approach and also harmonizing journal citation in ISI/SciELO references and normalizing author’s affiliation in MEDLINE. Our work considered “trigrams” as the terms (elements) of a term vector representing a text, according to the Trigram Phrase Matching published by the NLM’s Indexing Initiative and its logarithmic Term Frequency – Inverse Document Frequency method for term weighting. Trigrams are overlapping 3-char strings from a text, extracted by a couple of rules, and a trigram matching method may improve the probability of identifying synonym phrases or similar texts. The matching process was implemented as a simple algorithm, and requires a certain amount of computer resources. An efficiency-focused C-programming was adopted. In addition, some heuristic rules improved the efficiency of the method and made it feasible a regular “find your scientific production in SciELO collection” information service. We describe an implementation of the Trigram Matching method, the software tool we developed and a set of experimental parameters for the above results. • Introdução • Métodos e procedimentos • Resultados • Outras aplicações e considerações • Conclusão • [Referências bibliográficas] 1. Introdução • Sistemas de recuperação de informação para bases de dados compostas por textos representam textos por vetores de termos – lista dos termos do texto – frequência dos termos no texto • Motores de busca de páginas da Internet seguem algum sistema de peso – lista das palavras da página – pesos das palavras da página 1. Introdução • Os sistemas de pesos chamados TFIDF (term frequency - inverse document frequency) combinam dois componentes: – peso local (document weight) » diretamente proporcional à frequência do termo no documento – peso global (collection weight) » inversamente proporcional ao número de documentos da coleção que contêm a palavra 1. Introdução • Aplica-se o mesmo método de representação dos textos à especificação de busca do usuário (user query) – vetor de termos • Compara-se com o conjunto de vetores de termos que representam a coleção de textos – lista ordenada de documentos similares (ranked hit list) à especificação de busca • Analogamente, para uma coleção de documentos e um dado documento dessa coleção, pode-se produzir uma lista ordenada de documentos similares (related documents, related articles, “more pages like this”) 1. Introdução • Tipicamente: – os vetores de termos são normalizados para norma 1 – o co-seno (vector cosine) do ângulo entre dois vetores é utilizado como medida de similaridade entre dois textos • Referência bibliográfica: [1] Salton, Gerard; Buckley, Christopher. Term-weighting Approaches in Automatic Text Retrieval. Information Processing & Management, 1988; 24(5): 513-23. 1. Introdução • No entanto.. é essencial identificar variações de palavras ao longo da coleção de textos para aumentar a performance do modelo vetorial – é complexo identificar plurais, prefixos e outras normalizações de texto (text normalization, word steaming) – ferramentas de normalização de palavras são específicas para um idioma (e nem sempre acessíveis) • Uma alternativa à normalização de textos é considerar trigramas como os termos (elementos do vetor de termos) que representam um texto – trigramas são cadeias de 3 caracteres sobrepostos (overlapping 3-char strings) extraidos de um texto – a maioria dos trigramas são independentes das variações das palavras, aumentando a probabilidade de se identificar frases sinônimas ou similares 1. Introdução • O artigo descreve uma implementação do método Trigram Phrase Matching para recuperação de informação segundo o modelo vetorial, que considera trigramas como os elementos da representação vetorial de: – – – – – dados bibliográficos de artigos de revistas nomes de conceitos da classificação MeSH citações a revistas em referências bibliográficas em SciELO afiliação de autores em MEDLINE e SciELO outras unidades de estudo 1 pesquisador Lattes + cada título de sua produção científica cada autor + título de 1 artigo de SciELO.br 2. Métodos e Procedimentos • A implementação segue as regras de extração de trigramas e o sistema de pesos TF-IDF do método Trigram Phrase Matching publicado pelo projeto Indexing Initiative da NLM – US National Library of Medicine • Referências: [2] Aronson, Alan R. et al. The Indexing Initiative: A Report to the Board of Scientific Counselors of the Lister Hill National Center for Biomedical Communications, 1999. available at http://ii.nlm.nih.gov/resources/BoSC99.pdf [3] Aronson, Alan R. et al. The NLM Indexing Initiative. Proceedings of the AMIA Annual Fall Symposium, 2000: 17-21. available at http://ii.nlm.nih.gov/resources/Indexing_Initiative.pdf 2. Métodos e Procedimentos • Dado um texto, é transformado para minúsculas, dividido em frases e: 1. 2. 3. 4. 5. • K+1 trigramas sobrepostos são produzidos de frases com K+3 caracteres um caracter ‘!’ é anexado ao primeiro trigrama produzido de cada palavra, o qual é contado duplamente a primeira letra de cada palavra também é extraída, e um caracter ‘#’ é anexado um trigrama adicional é produzido para cada duas palavras adjacentes, com suas primeiras letras separadas por um espaço um único “trigrama” é produzido de “frases” com até 3 caracteres DNA sequence selectivity produz: – dna seq equ que uen enc nce sel ele lec ect cti tiv ivi vit ity dna! dna! seq! seq! sel! sel! d# s# s# ds ss 2. Métodos e Procedimentos • Para cada trigrama da coleção é atribuido um peso global onde e • N é o tamanho da coleção (número de textos) nt o número de textos da coleção contendo o trigrama Para cada trigrama é atribuido um peso local onde log(N / nt ) log(1 ft ) f t é a frequência do trigrama no texto • Um dado texto é representado pela representação vetorial normalizada (“comprimento” do vetor igual a 1) e de dimensão igual ao número de trigramas que ocorrem na coleção, com o valor dos elementos calculados pelos respectivos pesos locais multiplicados pelos pesos globais dos trigramas extraidos desse texto • A similaridade entre dois textos varia entre 0 e 1, sendo calculada pelo co-seno do ângulo entre suas representações vetoriais normalizadas – apenas os trigramas que ocorrem em um texto têm coordinadas não-nulas nessa representação vetorial (esparsa) 2. Métodos e Procedimentos • O software que implementa o método Trigram Phrase Matching inclui 2 programas, chamados em linha de comando, escritos em linguagem C portável e com foco na eficiência dos trechos críticos – desenvolvidos como aplicações da biblioteca de funções CISIS para bases de dados no formato CDS/ISIS da UNESCO – CISIS Library and Utility Programs suporta o armazenamento e a manipulação de textos estruturados » » » » » • registros com Leader, Diretório e Área de dados campos de dados de tamanho variável, opcionais e repetitivos (repeatable fields) campos de dados com sub-campos linguagem de extração de dados (format specification) Referência: [4] BIREME. CISIS Library and Utility Programs. http://productos.bvsalud.org/product.php?id=cisis&lang=en 2. Métodos e Procedimentos • O primeiro programa gera as representações vetoriais de um conjunto de documentos de entrada, tipicamente usando as distribuições de trigramas de uma coleção de documentos já processados WTRIG1 documents=<mf1> extract={<tag>|<fmt>} [collection=<mf2>] input parms and collection data from <mf2>.c and <mf2>.n, if provided input text from <mf1>, using field <tag> or format specification <fmt> output a term vector for each input text to <mf1>.v options: maxrf=<max relative frequency for a term> maxtv=<max #terms in a term vector> K=<max #terms> N=<total #docs> [dmfn] [6words] [0.50] [50] [100000] [maxmfn] [] [] 2. Métodos e Procedimentos • O segundo programa gera, para cada documento de entrada, uma lista de documentos similares de uma dada coleção de documentos WTRIG2 documents=<mf1> collection=<mf2> input document term vectors from <mf1>.v input collection term vectors from <mf2>.v output similar collection for each input document to <mf1>.y options: maxrel=<max #related> minsim=<min similarity for related docs> dmfn=<tag> collapse doc.v as field <mf1>.v/<tag> cmfn=<tag> collapse col.v as field <mf2>.v/<tag> [10] [0.7] [] [] 3. Resultados • “Related literature in LILACS database” – • A “related literature” button in LILACS search engine results was implemented[8]. It browses up to 50 related literature in LILACS having a minimum value of 0.30 as similarity, based on the top 100 trigrams from a text formed by the elements: document title, abstract and MeSH/DeCS concepts. The set of term vectors and the related documents from LILACS database is updated weekly in a batch mode processing. Referências: [5] BIREME. LILACS (Latin American and Caribbean Literature on Health Sciences) database. http://www.bireme.br/bvs/I/ibd.htm [8] BIREME. Related documents in LILACS database search engine. http://bases.bireme.br/cgibin/wxislind.exe/iah/online/?IsisScript=iah/iah.xis&base=LILACS&lang=p&form=A [8+] http://bases.bireme.br/cgibin/wxislind.exe/iah/online/?IsisScript=iah/iah.xis&base=LILACS&lang=i&nextAction=lnk&index Search=tw&exprSearch=malaria 3. Resultados • “Identifying medical concepts from LILACS texts by lexical approach” – • in the absence of human assigned subject descriptors in LILACS in-process journal articles, all 1 to 6 adjacent words from the document title and abstract are taken for a Trigram Matching processing against the collection of DeCS concept names and synonyms, considering the language of the journal article. The Subject index in the LILACS search engine[9] includes the MeSH/DeCS concepts assigned by this lexical approach to in-process journal articles. Referências: [6] BIREME. DECS (Descriptors on Health Sciences) vocabulary. http://decs.bvs.br/I/homepagei.htm [9] BIREME. Subject Index in LILACS database search engine. http://bases.bireme.br/cgibin/wxislind.exe/iah/online/?IsisScript=iah/iah.xis&nextAction=lnk&base=LILACS&exprSearch= internet&indexSearch=FE&lang=i 3. Resultados • “Find your scientific production in SciELO collection” – • implemented by comparing a given author’s name (and maybe some article title words) with a collection of texts formed by the author’s name of each SciELO journal article combined with the article title. As result, the XMLformat output provides, by default, the top 10 author-title having similarity of 0.50 or higher with the user query, along with the information for browsing the full-text articles. This service is encapsulated in the LinkServer Project[10]. Referências: [7] BIREME. SciELO Brazil. http://www.scielo.br/scielo.php?lng=en [10] BIREME. The LinkServer project. http://linkserver.bvsalud.org/ [10+] Classificação de produção científica segundo disciplinas de revistas http://serverofi.bireme.br/similar/sercjd.htm/ 4. Outras aplicações e considerações • O método facilita a geração de índices normalizados – Afiliação de autores em MEDLINE [11] (produção científica de instituições, unidades geográficas etc) tabula os nomes das instituições do primeiros autores harmoniza as variações para a forma mais frequente – Títulos das revistas citadas em SciELO (análises bibliométricas/cientométricas) tabula os títulos das revistas citadas harmoniza as variações para ISSN ou para a forma mais frequente • [12,13] Referências: [11] Tess, Beatriz et al. Capítulo Saúde. Indicadores da Atividade Científica, Tecnológica e de Inovação do Estado de São Paulo - 2004; Sao Paulo, Brazil: FAPESP. **Disponível em http://www.fapesp.br/indicadores. [12] Mugnaini, Rogerio et al. Citations Titles Standardization using Information Retrieval Techniques. Proceedings of the 7th International Conference on Textual Data Statistical Analysis, 2004 Mar 10-12; LouvainNeuve, Belgium. vol 2: 824-30. [13] BIREME. Citation reports in SciELO Brazil. http://www.scielo.br/stat_biblio/index.php?lang=en [13+] SciELO.br granted citations to journals. http://serverofi.bireme.br:2424/scielo_selec.htm [11+] SciELO.br international co-authoring page. http://www.scielo.br/stat_biblio/index.php?lang=en&state=16 4. Outras aplicações e considerações • A implementação suporta o “matching” com dados multi-valorados (1 conceito tem nomes em vários idiomas) WTRIG1 (dmfn) gera vetores com identificação da unidade de estudo WTRIG2 (dmfn e/ou cmfn) reconhece o conjunto de representações alternativas da unidade de estudo • Embora útil, a identificação de conceitos médicos por enfoque léxico é um processo lento e requer demasiado espaço de disco WTRIG1 (6words) produz um vetor de termos para cada conjunto de 1 a 6 palavras dos períodos ou frases do texto 5. Conclusões • Considerou-se como significativos os resultados em problemas de similaridade de textos obtidos com a aplicação desta implementação do método Trigram Phrase Matching no contexto das fontes de informação da Biblioteca Virtual de Saúde [14] • A representação de textos por vetores de trigramas, via os programas utilitários WTRIG1 e WTRIG2, foi incorporada à tecnologia de informação empregada na operação regular das fontes de informação da Biblioteca Virtual de Saúde • O método baseia-se em algorítmos simples e requer uma certa quantidade de recursos de computador. A programação em linguagem C focada na eficiência e algumas regras heurísticas aumentaram a eficiência do método, e viabilizaram serviços de informação regulares com textos em Inglês, Espanhol e Português. • O método pode ser aplicado para se atribuir conceitos médicos (descritores de assunto DeCS/MeSH) a textos da área da Saúde, via os descritores atribuídos aos documentos similares das fontes de informação LILACS/MEDLINE. • Referência: [14] BIREME. Virtual Health Library. http://www.bvsalud.org/bvs/I/ihome.htm <obrigado/>