Estudo comparativo sobre meta-heurísticas em GPU para clusterização de dados

Abstract

Clustering is a fundamental class of problems with applications in many areas of knowledge, including: bioinformatics, computer vision, data mining, text mining, and web page grouping. Given a set of n objects, clustering aims to automatically group such objects in k groups, usually disjunct, called clusters or groupings using a pre-established similarity measure. Clustering problems in general have high computational complexity and involve a large amount of input data. Thus, the use of parallel architectures such as Graphics Processing Units (GPUs) is interesting alternatives to accelerate the clustering process. In this work, we conducted a comparative study of GPU-accelerated metaheuristics for grouping data. Three population meta-heuristics were implemented in the GPU: Particle Swarm Optimization (PSO), Differential Evolution (DE), and Scatter Search (SS). The implementation of these meta-heuristics was divided into two parts: the independent part of the problem and the dependent part of the problem. The independent part of the problem refers to the selection, replacement, and combination operators for each meta-heuristic, while the dependent part refers to the objective function. The independent part was implemented using the libCudaOptimize framework, and the dependent part was created by transforming the clustering problem into a global optimization problem subject to cash constraints. The proposed meta-heuristics were compared with the best current clustering algorithm C-GRASP-Clu considering the execution time and quality of the solution. The results indicate that the GPU-based PSO (GPU-PSO) obtained the best results in comparison with the other GPU-based metaheuristics and the best method today. Also, our GPU implementation of the objective function obtained an average speedup of 175x over the sequential version. These results demonstrate that a GPU approach to the clustering problem is very promising.