URSA : um framework para agrupamento de dados e validação de resultados

Abstract

Devido ao avanço da tecnologia e da geração contínua de grandes volumes de dados, técnicas mais sofisticadas para extrair informações relevantes desses dados se mostraram necessárias. A técnica de agrupamento de dados (clustering analysis) tem como objetivo separar um conjunto de objetos em grupos, na qual seus elementos possuem características similares entre si. Dessa forma, é possível analisar cada grupo de modo que a compreensão de informações seja mais eficiente. O problema de realizar agrupamentos de dados foi abordado na monografia “Um framework para agrupamento de dados”, de Guilherme Haag Ribacki, em janeiro de 2013. Logo, o presente trabalho tem como objetivo estender este framework, incluindo novas técnicas de similaridade, seleção, agrupamento e validação de resultados, além de ser mais flexível quanto aos tipos de dados suportados, incluindo suporte a arquivos de áudio e de vídeo, além do suporte a documentos de texto. Dentre os novos algoritmos de agrupamento estão as técnicas K-Means, K-Medoids, DBSCAN e aglomerativo hierárquico. Novas técnicas de similaridade e seleção para os novos tipos de dados também foram implementadas. Os algoritmos de agrupamento implementados são executados e seus resultados analisados pelos algoritmos de validação disponíveis no framework, tais como Medida-F (F-Measure), Silhueta (Silhouette), Puridade (Purity) e Entropia (Entropy). São utilizados diferentes conjuntos de dados para a validação dos algoritmos de agrupamento do framework, três conjuntos para arquivos de texto, sendo dois pequenos, com 12 (o mesmo utilizado por Ribacki (2013)) e 13 documentos, respectivamente, e um grande (Reuters-21578 10 categories Apte’ split), com 1.248 documentos, um conjunto de áudio com 30 arquivos e um de vídeo com 21 arquivos. Para os conjuntos pequenos de arquivos de texto e para o conjunto de arquivos de áudio foi possível agrupar corretamente os dados ao se utilizar todos os algoritmos de agrupamento disponíveis no framework. Já o conjunto grande de arquivos de texto e o conjunto de arquivos de vídeo não foram agrupados corretamente. O primeiro devido a problemas inerentes ao próprio conjunto e o segundo devido a presença de metadados com relação fraca ao conteúdo dos arquivos do conjunto.

Due to advancements in technology and the continuous generation of large volumes of data, more sophisticated techniques to extract relevant information from these data were necessary. The clustering analysis technique aims to separate a set of objects into groups, in which its elements have similar characteristics to each other. Thus, it is possible to analyze each group so that comprehension of information is more efficient. The problem of calculating data clusters has been addressed in the monograph "A framework for data clustering", written by Guilherme Haag Ribacki in January 2013. Therefore, the objective of this study is to extend this framework, including new techniques for similarity, selection, data clustering and cluster validity, and is intended to be more flexible in the types of supported data, including support for audio and video files, in addition to the support of text files. Among the new clustering algorithms implemented, we can highlight K-Means, K-Medoids, DBSCAN and an agglomerative hierarchical clustering algorithm. New techniques of similarity and selection techniques for the new types of data were also implemented. The implemented clustering algorithms are executed and their results analyzed by the validation algorithms available in the framework, such as F-Measure, Silhouette, Purity and Entropy. Different data sets for analysis are used to validate the clustering algorithms from the framework, three sets for text files, two of them small, with 12 (the same used by Ribacki (2013)) and 13 documents, respectively, and a large one (Reuters-21578 10 categories Apte’ split), with 1,248 documents, a set for audio with 30 files and one for video with 21 files. For the small sets of text files and for the set of audio files, the clusters were identified correctly when executing all clustering algorithms available in the framework. For the large set of text files and for the set of video files the clusters were not identified correctly. The first one due to problems inherent to the set itself and the second one due to the presence of metadata weakly related to the contents of the files in the set.