Combinações de similaridade semântica e frequência de termos para agrupamento de textos
Arquivos
Data
2017-03-20
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Viçosa
Resumo
Um dos desafios ao se agrupar documentos é encontrar uma boa medida de simila- ridade para documentos de textos, que seja capaz de gerar grupos coesos. Algumas medidas são baseadas no clássico modelo bag of words e consideram apenas o vo- cabulário do documento. Com isso, documentos semanticamente similares podem ser atribuídos a diferentes grupos se eles não compartilham o mesmo vocabulário. Por essa razão, medidas de similaridade semântica que usam conhecimento externo, como um corpus, dicionários ou banco de palavras, têm sido propostas na literatura. Neste trabalho, a medida Frequency Google Tri-grams Measures (FGTM) é proposta para identificar similaridade entre documentos baseado nas frequências dos termos nos documentos e no corpus Google n-grams. A comparação entre as frequências de um termo em um dado par de documentos pode quantificar a importância daquele termo para o assunto dos documentos, assumindo que um termo possui maior rele- vância para um documento se ele ocorre mais vezes. Adicionalmente, as frequências dos termos dos documentos no corpus Google n-grams permitem estimar semanti- camente suas similaridades. Adicionalmente, oito variantes de dois algoritmos de agrupamento são aplicadas a vários conjuntos de dados reais, com o objetivo de avaliar experimentalmente a qualidade dos grupos obtidos com a medida proposta e compará-la com outras medidas do estado da arte. Análises de complexidade computacional das medidas comparadas são apresentadas. Os resultados experi- mentais demonstram que a medida proposta melhora significativamente a qualidade dos agrupamentos de documentos, comprovado por testes estatísticos. Também é mostrado que, combinar resultados de agrupamento obtidos com bag of words e medida semântica obtém melhores resultados que adotar uma medida individualmente. Para finalizar, é feito um estudo sobre heurísticas para estimar o número K de gru- pos em agrupamento de textos. Uma versão modificada da heurística G-means é proposta e comparada com heurísticas da literatura.
One challenge for document clustering consists of finding a proper similarity me- asure for text documents, which enables the generation of cohesive groups. Some measures are based on the classic bag of words model and take into account the vocabulary of the documents solely. In doing so, semantically similar documents may reside in different clusters if they do not share the same vocabulary. For this reason, semantic similarity measures that use external knowledge, such as corpus, dictionaries, or word bases, have been proposed in the literature. In this paper, the Frequency Google Tri-grams Measure (FGTM) is proposed to assess similarity between documents based on the frequencies of terms in the compared documents and Google n-gram corpus. The comparison between the frequencies of a term in a given pair of documents can quantify the importance of that term to the documents’ subjects, assuming that a term is relevant to a document if it occurs multiple times. Additionally, the frequencies of documents’ terms in Google n-gram corpus allows to semantically estimate their similarity. Additionally, eight variants of two clustering algorithms are applied to several real data sets in order to experimentally evalu- ate the quality of the clusters obtained with the proposed measure and compare it with other state-of-the-art measures. Computational complexity analysis of the compared measures are provided. The experimental results demonstrate that the proposed measure improves significantly the quality of document clustering, based on statistical tests. Additionally, we show that combining clustering results obtained with bag of words and semantic measure give better results than adopting a single approach. Finally, a study involving heuristcs to identify the number K of clusters in a document clustering is done. A modified version of the G-means heuristic is proposed and compared to other heuristcs from the literature.
One challenge for document clustering consists of finding a proper similarity me- asure for text documents, which enables the generation of cohesive groups. Some measures are based on the classic bag of words model and take into account the vocabulary of the documents solely. In doing so, semantically similar documents may reside in different clusters if they do not share the same vocabulary. For this reason, semantic similarity measures that use external knowledge, such as corpus, dictionaries, or word bases, have been proposed in the literature. In this paper, the Frequency Google Tri-grams Measure (FGTM) is proposed to assess similarity between documents based on the frequencies of terms in the compared documents and Google n-gram corpus. The comparison between the frequencies of a term in a given pair of documents can quantify the importance of that term to the documents’ subjects, assuming that a term is relevant to a document if it occurs multiple times. Additionally, the frequencies of documents’ terms in Google n-gram corpus allows to semantically estimate their similarity. Additionally, eight variants of two clustering algorithms are applied to several real data sets in order to experimentally evalu- ate the quality of the clusters obtained with the proposed measure and compare it with other state-of-the-art measures. Computational complexity analysis of the compared measures are provided. The experimental results demonstrate that the proposed measure improves significantly the quality of document clustering, based on statistical tests. Additionally, we show that combining clustering results obtained with bag of words and semantic measure give better results than adopting a single approach. Finally, a study involving heuristcs to identify the number K of clusters in a document clustering is done. A modified version of the G-means heuristic is proposed and compared to other heuristcs from the literature.
Descrição
Palavras-chave
Algorítmos, Semântica, Web semântica, Documentos eletrônicos
Citação
SOARES, Victor Hugo Andrade Soares. Combinações de similaridade semântica e frequência de termos para agrupamento de textos. 2017. 103 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Viçosa, Viçosa. 2017.