UM ESTUDO COMPUTACIONAL COMPARATIVO ENTRE ALGORITMOS DE AGRUPAMENTO E DE DETECÇÃO DE COMUNIDADES CONSIDERANDO DADOS DA EDUCAÇÃO

Abstract

The general objective of this dissertation is to perform a comparative computational study between three clustering algorithms (k-means, PAM and CLARA) and two Community Detection algorithms (Fast Greedy and Walktrap), considering data from the education area. To analyze the solutions produced by the five algorithms, two indexes associated, respectively, with the relative and external validation criteria were used, be they: Silhouette and Rand. For this, an algorithm was implemented for network construction, which were produced from the real databases in two different ways, that is: through the quartiles of the distances of the objects and the Minimum Generating Tree. Among the main results, we highlight those from the PAM and CLARA algorithms, which when applied to a small and medium-sized database set do not differ in relation to their results, in relation to the Silhouette index. In relation to the Rand index, when comparing the performance of the PAM and CLARA algorithms, compared to the Community Detection algorithms Fast Greedy and Walktrap, it presented greater similarity between the groups formed by the CLARA algorithm and the communities of the Fast Greedy algorithm, than the groups formed by the PAM algorithm and the communities produced by the Fast Greedy algorithm.

Esta dissertação tem por objetivo geral realizar um estudo computacional comparativo entre três algoritmos de agrupamento (k-means, PAM e CLARA) e dois algoritmos de Detecção de Comunidades (Fast Greedy e Walktrap), considerando dados da área da Educação. Para analisar as soluções produzidas pelos cinco algoritmos, foram utilizados dois índices associados, respectivamente, aos critérios de validação relativo e externo, sejam eles: Silhueta e Rand. Para tal, foi implementado um algoritmo para construção de redes, que foram produzidas a partir das bases de dados reais de duas maneiras distintas, a saber: através dos quartis das distâncias dos objetos e da Árvore Geradora Mínima. Dentre os principais resultados, destacam-se aqueles provenientes dos algoritmos PAM e CLARA, que quando aplicados a um conjunto de base de dados de porte pequeno e médio não diferem quanto aos seus resultados, em relação ao índice de Silhueta. Em relação ao índice de Rand, quando é comparado o desempenho dos algoritmos PAM e CLARA, frente aos algoritmos de Detecção de Comunidades: Fast Greedy e Walktrap, apresentou maior similaridade entre os grupos formados pelo algoritmo CLARA e as comunidades do algoritmo Fast Greedy, do que os grupos formados pelo algoritmo PAM e as comunidades produzidas pelo algoritmo Fast Greedy.