Marta Vidal Modenesi
Resumo
Este trabalho propõe o uso de paralelismo para tratar o problema da análise de agrupamentos no processamento de grandes volumes de dados integrando seus dois maiores desafios: o cálculo dos centros de agrupamentos feito pelo algoritmo de particionamento Fuzzy c- means e a seleção do melhor padrão para os dados através da avaliação dos agrupamentos pelo índice de validação de partições PBM. Duas estratégias são propostas: a do paralelismo pela divisão do conjunto de dados e a do paralelismo pela divisão do conjunto de partições. Neste último caso, uma estratégia de balanceamento de carga modelada pelo problema das múltiplas mochilas é acrescentada ao algoritmo para lidar com os diferentes pesos das partições. Sua implementação é feita por uma heurística que incorpora as restrições relativas à análise de agrupamentos ao algoritmo first-fit decreasing. Testes realizados com dados sintéticos e um estudo de caso com dados sísmicos da Petrobras referentes ao campo de óleo e gás de Marlim são apresentados com as análises de eficiência e escalabilidade do algoritmo paralelo de análise de agrupamento Fuzzy c-means em diversos cenários.
Abstract
This work proposes the use of parallelism to deal with the cluster analysis problem in the processing of large volumes of data by the integration of its two major challenges: the clusters calculations done by the Fuzzy c-means algorithm and the selection of the best pattern for the data through the clusters evaluation by the PBM clusters validity index. Two approaches are proposed: parallelism by the data set division and parallelism by the partitions set division. In this last case, a load balance strategy modeled by the multiple knapsacks problem is added to the algorithm to deal with the different weights partitions. Its implementation is made by a heuristic that incorporates the restrictions related to the cluster analysis to the first-fit decreasing algorithm. Tests made with synthetic data and a seismic data case study from Petrobras referring to the Marlim oil and gas field are presented with the Fuzzy c-means cluster analysis parallel algorithm efficiency and scalability analysis over diverse scenarios.
