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/>