A busca aproximada por múltiplos padrões similares é um problema encontrado em diversas áreas de pesquisa, tais como biologia computacional, processamento de sinais e recuperação de informação. Na maioria das vezes, padrões não possuem uma correspondência exata e, portanto, buscam-se padrões aproximados, de acordo com um modelo de erro. Em geral, o modelo de erro utiliza uma função de distância para determinar o quanto dois padrões são diferentes. As funções de distância são baseadas em medidas de similaridade, que são classificadas em medidas de similaridade baseadas em distância de edição, medidas de similaridade baseadas em token e medidas de similaridade híbridas. Algumas dessas medidas extraem um vetor de características de todos os termos que constituem o padrão. A similaridade entre os vetores pode ser calculada pela distância entre cossenos ou pela distância euclidiana, por exemplo. Essas medidas apresentam alguns problemas: tornam-se inviáveis conforme o tamanho do padrão aumenta, não realizam a correção ortográfica ou apresentam problemas de normalização. Neste projeto de pesquisa propõe-se uma nova medida de similaridade híbrida que combina TF-IDF Weighting e uma medida de similaridade baseada em distância de edição para estimar a importância de um termo dentro de um padrão na tarefa de busca textual. A medida DGD não descarta completamente os termos que não fazem parte do padrão, mas atribui um peso baseando-se na alta similaridade deste termo com outro que está no padrão e com a média de TF-IDF Weighting do termo na coleção. Alguns experimentos foram conduzidos mostrando o comportamento da medida proposta comparada com as outras existentes na literatura. Tem-se como recomendação geral o limiar de {tf-idf+cosseno, Jaccard, Soft tf-idf} 0,60 e {Jaro, Jaro-Winkler, Monge-Elkan} 0,90 para detecção de padrões similares. A medida de similaridade proposta neste trabalho (DGD+cosseno) apresentou um melhor desempenho quando comparada com tf idf+cosseno e Soft tf-idf na identificação de padrões similares e um melhor desempenho do que as medidas baseadas em distância de edição (Jaro e JaroWinkler) na identificação de padrões não similares. Atuando como classificador, em geral, a medida de similaridade híbrida proposta neste trabalho (DGD+cosseno) apresentou um melhor desempenho (embora não sinificativamente) do que todas as outras medidas de similaridade analisadas, o que se mostra como um resultado promissor. Além disso, é possível concluir que o melhor valor de a ser usado, onde corresponde ao limiar do valor da medida de similaridade secundária baseada em distância de edição entre os termos do padrão, corresponde a 0,875. / Multiple approximate pattern matching is a challenge found in many research areas, such as computational biology, signal processing and information retrieval. Most of the time, a pattern does not have an exact match in the text, and therefore an error model becomes necessary to search for an approximate pattern match. In general, the error model uses a distance function to determine how different two patterns are. Distance functions use similarity measures which can be classified in token-based, edit distance based and hybrid measures. Some of these measures extract a vector of characteristics from all terms in the pattern. Then, the similarity between vectors can be calculated by cosine distance or by euclidean distance, for instance. These measures present some problems: they become infeasible as the size of the pattern increases, do not perform the orthographic correction or present problems of normalization. In this research, we propose a new hybrid similarity metric, named DGD, that combines TF-IDF Weighting and a edit distance based measure to estimate the importance of a term within patterns. The DGD measure doesnt completely rule out terms that are not part of the pattern, but assigns a weight based on the high similarity of this term to another that is in the pattern and with the TF-IDF Weighting mean of the term in the collection. Experiment were conducted showing the soundness of the proposed metric compared to others in the literature. The general recommendation is the threshold of {tf-idf+cosseno, Jaccard, Soft tf-idf} 0.60 and {Jaro, Jaro-Winkler, Monge-Elkan} 0.90 for detection of similar patterns. The similarity measure proposed in this work (DGD + cosine) presented a better performance when compared with tf-idf+cosine and Soft tf-idf in the identification of similar patterns and a better performance than the edit distance based measures (Jaro and Jaro-Winkler) in identifying non-similar patterns. As a classifier, in general, the hybrid similarity measure proposed in this work (DGD+cosine) performed better (although not significantly) than all other similarity measures analyzed, which is shown as a promising result . In addition, it is possible to conclude that the best value of to be used, where is the theshold of the value of the secondary similarity measure based on edit distance between the terms of the pattern, corresponds to 0.875.
| Identifer | oai:union.ndltd.org:usp.br/oai:teses.usp.br:tde-12042019-103622 |
| Date | 07 March 2019 |
| Creators | Dezembro, Denise Gazotto |
| Contributors | Baranauskas, José Augusto |
| Publisher | Biblioteca Digitais de Teses e Dissertações da USP |
| Source Sets | Universidade de São Paulo |
| Language | Portuguese |
| Detected Language | English |
| Type | Dissertação de Mestrado |
| Format | application/pdf |
| Rights | Liberar o conteúdo para acesso público. |
Page generated in 0.0022 seconds