K-means com Seleção Automática de K via Dunn-SkeVa em GPU

• Wilson G. N. Junior UFG
• Wellington S. Martins UFG
• André C. P. L. F. de Carvalho USP

DOI: https://doi.org/10.5753/wperformance.2026.23906

Resumo

A escolha do número ideal de clusters K é um problema central no algoritmo K-means. O Índice de Dunn (DI) é uma métrica clássica para avaliar a qualidade de agrupamentos, mas seu custo quadrático O(N²) inviabiliza sua aplicação em grandes volumes de dados. Neste trabalho, propomos uma implementação paralela em GPU do Índice de Dunn utilizando amostragem SkeVa, que reduz significativamente o custo computacional dessa métrica. A solução é então integrada ao K-means em um pipeline para seleção automática do melhor K de forma eficiente. Em experimentos conseguimos speedups de 42.5× a 92.0× em relação à versão serial com cálculo exato.

Referências

Aloise, D., Deshpande, A., Hansen, P., and Popat, P. (2009). Np-hardness of euclidean sum-of-squares clustering. Machine learning, 75(2):245–248.

Arthur, D. and Vassilvitskii, S. (2007). k-means++: The advantages of careful seeding. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1027–1035. Society for Industrial and Applied Mathematics.

Bueno, W., Silva, O., Nacif, J. A., and Ferreira, R. (2024). Implementação paralela de múltiplos K-means em GPU. In Simpósio em Sistemas Computacionais de Alto Desempenho (SSCAD).

Davies, D. L. and Bouldin, D. W. (1979). A cluster separation measure. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1(2):224–227.

Dunn, J. C. (1974). Well-separated clusters and optimal fuzzy partitions. Journal of Cybernetics, 4(1):95–104.

Grün, E. S., Martins, W. S., and Franco, R. (2024). Acelerando o cálculo do índice dunn de validação de agrupamento. In Anais do Simpósio em Sistemas Computacionais de Alto Desempenho (SSCAD), pages 1–3. SBC.

He, G., Vialle, S., and Baboulin, M. (2022). Parallel and accurate k-means algorithm on CPU-GPU architectures for spectral clustering. Concurrency and Computation: Practice and Experience, 34(14):e6621.

Ikotun, A. M., Habyarimana, F., and Ezugwu, A. E. (2025). Cluster validity indices for automatic clustering: A comprehensive review. Heliyon, 11(2):e41953.

Jain, A. K. (2010). Data clustering: 50 years beyond K-means. Pattern Recognition Letters, 31(8):651–666.

Junior, W. G. N. and Martins, W. S. (2026). Uso de GPUs na validação de agrupamentos com amostragem SkeVa. In Escola Regional de Alto Desempenho do Centro-Oeste (ERAD-CO). SBC.

Koklu, M. and Ozkan, I. A. (2020). Multiclass classification of dry beans using computer vision and machine learning techniques. Computers and Electronics in Agriculture, 174:105507.

MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. In Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, volume 1, pages 281–297.

Ncir, C.-E. B., Hamza, A., and Bouaguel, W. (2021). Parallel and scalable Dunn index for the validation of big data clusters. Parallel Computing, 102:102751.

RAPIDS Development Team (2018). RAPIDS: Collection of libraries for end to end GPU data science. [link].

Rousseeuw, P. J. (1987). Silhouettes: A graphical aid to the interpretation and validation of cluster analysis. Journal of Computational and Applied Mathematics, 20:53–65.

Saitta, S., Raphael, B., and Smith, I. F. C. (2007). A comprehensive validity index for clustering. Intelligent Data Analysis, 11(6):529–548.

Traganitis, P. A., Slavakis, K., and Giannakis, G. B. (2015). Sketch and validate for big data clustering. IEEE Journal of Selected Topics in Signal Processing, 9(4):678–690.

Volkov, V. (2010). Better performance at lower occupancy. In GPU Technology Conference (GTC), volume 10, page 16.