Explicabilidade para Kmeans com árvores de decisão em GPU
Resumo
Algoritmos não supervisionados como o K-means agrupam dados, mas não fornecem explicabilidade, o que dificulta a análise humana em decisões críticas. Embora árvores de decisão como as do algoritmo ExGreedy permitam explicitar esses agrupamentos, o custo computacional permanece um gargalo em larga escala. Este artigo propõe uma implementação híbrida CPU/GPU para acelerar o ExGreedy. Mostra-se que, além da complexidade teórica, otimizações em nível de código e reestruturação algorítmica são essenciais. Na versão sequencial aprimorada, os nós filhos herdam a ordenação pré-filtrada dos nós pais. Em seguida, adaptou-se a execução transferindo tarefas repetitivas e independentes para um pré-processamento global na GPU. Experimentos em sete conjuntos de dados confirmaram a corretude dos resultados e alcançaram ganhos de desempenho entre 3,18× e 8,58× em dados de média e grande escala, superando a sobrecarga da inicialização da GPU observada em conjuntos de dados menores.
Referências
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), pages 37–48. SBC.
Cheng, J., Grossman, M., and McKercher, T. (2014). Professional CUDA c programming. John Wiley & Sons.
Costa, V. G. and Pedreira, C. E. (2023). Recent advances in decision trees: an updated survey. Artificial Intelligence Review, 56(5):4765–4800.
Ezugwu, A. E., Ikotun, A. M., Oyelade, O. O., Abualigah, L., Agushaka, J. O., Eke, C. I., and Akinyelu, A. A. (2022). A comprehensive survey of clustering algorithms: State-of-the-art machine learning applications, taxonomy, challenges, and future research prospects. Engineering Applications of Artificial Intelligence, 110:104743.
Ferreira, R., Magalhães, S. V. G. d., and Nacif, J. A. M. (2019). Métricas e números: Desmistificando a programação de alto desempenho em GPU. In Menotti, R. and Galante, G., editors, Minicursos do WSCAD 2019, chapter 1. Sociedade Brasileira de Computação, Porto Alegre.
Ferreira, R. d. S. (2025). Mais produtividade com LLMs, engenharia de prompt, aprendizado de máquina e GPUs. In Cordeiro, D. and Bianchini, C. P., editors, Minicursos do SSCAD 2025, chapter 1. Sociedade Brasileira de Computação, Porto Alegre.
Freitas, I. C. (2025a). Datasets k-means explicável. [link]. Acessado em: 7 out. 2026.
Freitas, I. C. (2025b). Explicabilidade k-means utilizando cuda. [link]. Acessado em: 7 out. 2026.
Frost, N., Moshkovitz, M., and Rashtchian, C. (2020). Exkmc: Expanding explainable k-means clustering. arXiv preprint arXiv:2006.02399.
Gabidolla, M. and Carreira-Perpiñán, M. Á. (2022). Optimal interpretable clustering using oblique decision trees. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 400–410.
He, Q., Zhang, F., Bian, G., and Zhang, W. (2025). Optimization of maximum parallel k-means algorithm based on gpu cluster. Cluster Computing, 28(8):489.
Hu, L., Jiang, M., Dong, J., Liu, X., and He, Z. (2026). Interpretable clustering: A survey. ACM Computing Surveys, 58(8):1–21.
Hu, L., Jiang, M., Liu, X., and He, Z. (2025). Significance-based decision tree for interpretable categorical data clustering. Information Sciences, 690:121588.
Laber, E., Murtinho, L., and Oliveira, F. (2023). Shallow decision trees for explainable k-means clustering. Pattern Recognition, 137:109239.
Laber, E. S. and Murtinho, L. (2021). On the price of explainability for some clustering problems. In International Conference on Machine Learning, pages 5915–5925. PMLR.
Leiserson, C. E., Thompson, N. C., Emer, J. S., Kuszmaul, B. C., Lampson, B. W., Sanchez, D., and Schardl, T. B. (2020). There’s plenty of room at the top: What will drive computer performance after moore’s law? Science, 368(6495):eaam9744.
Li, Y., Zhao, K., Chu, X., and Liu, J. (2013). Speeding up k-means algorithm by gpus. Journal of Computer and System Sciences, 79(2):216–229.
MacQueen, J. (1967). Multivariate observations. In Proceedings ofthe 5th Berkeley symposium on mathematical statisticsand probability, volume 1, pages 281–297. University of California press Oakland, CA, USA.
Merrill, D. and NVIDIA Corporation (2025). CUB: CUDA UnBound. [link]. Biblioteca de primitivas paralelas de alto desempenho para CUDA. Acessado em: 7 out. 2026.
Moshkovitz, M., Dasgupta, S., Rashtchian, C., and Frost, N. (2020). Explainable k-means and k-medians clustering. In International conference on machine learning, pages 7055–7065. PMLR.
Murtinho, L. S. (2025). Clustering under constraints: explainability via decision trees and separability with minimum size. PhD thesis, Pontifícia Universidade Católica do Rio de Janeiro (PUC-Rio), Rio de Janeiro, Brasil.
Owens, J. D., Houston, M., Luebke, D., Green, S., Stone, J. E., and Phillips, J. C. (2008). Gpu computing. Proceedings of the IEEE, 96(5):879–899.
Pan, Z. and Mishra, P. (2022). Hardware acceleration of explainable machine learning. In 2022 Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 1127–1130. IEEE.
Penha, J., Silva, A., Barros, O., Moreira, I., Nacif, J., and Ferreira, R. (2023). Avaliação de estilos de código para Árvores de decisão em gpu com microbenchmarks. In Anais do XXIV Simpósio em Sistemas Computacionais de Alto Desempenho, pages 277–288, Porto Alegre, RS, Brasil. SBC.
Penha, J. C., Bragança, L., Coelho, K., Canesche, M., Silva, J., Comarela, G., Nacif, J. A. M., and Ferreira, R. (2018). A gpu/fpga-based k-means clustering using a parameterized code generator. In 2018 Symposium on High Performance Computing Systems (WSCAD), pages 61–69. IEEE.
Perkel, J. M. (2018). Why jupyter is data scientists’ computational notebook of choice. Nature, 563(7732):145–147.
Rudin, C. (2019). Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature machine intelligence, 1(5):206–215.
Cheng, J., Grossman, M., and McKercher, T. (2014). Professional CUDA c programming. John Wiley & Sons.
Costa, V. G. and Pedreira, C. E. (2023). Recent advances in decision trees: an updated survey. Artificial Intelligence Review, 56(5):4765–4800.
Ezugwu, A. E., Ikotun, A. M., Oyelade, O. O., Abualigah, L., Agushaka, J. O., Eke, C. I., and Akinyelu, A. A. (2022). A comprehensive survey of clustering algorithms: State-of-the-art machine learning applications, taxonomy, challenges, and future research prospects. Engineering Applications of Artificial Intelligence, 110:104743.
Ferreira, R., Magalhães, S. V. G. d., and Nacif, J. A. M. (2019). Métricas e números: Desmistificando a programação de alto desempenho em GPU. In Menotti, R. and Galante, G., editors, Minicursos do WSCAD 2019, chapter 1. Sociedade Brasileira de Computação, Porto Alegre.
Ferreira, R. d. S. (2025). Mais produtividade com LLMs, engenharia de prompt, aprendizado de máquina e GPUs. In Cordeiro, D. and Bianchini, C. P., editors, Minicursos do SSCAD 2025, chapter 1. Sociedade Brasileira de Computação, Porto Alegre.
Freitas, I. C. (2025a). Datasets k-means explicável. [link]. Acessado em: 7 out. 2026.
Freitas, I. C. (2025b). Explicabilidade k-means utilizando cuda. [link]. Acessado em: 7 out. 2026.
Frost, N., Moshkovitz, M., and Rashtchian, C. (2020). Exkmc: Expanding explainable k-means clustering. arXiv preprint arXiv:2006.02399.
Gabidolla, M. and Carreira-Perpiñán, M. Á. (2022). Optimal interpretable clustering using oblique decision trees. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 400–410.
He, Q., Zhang, F., Bian, G., and Zhang, W. (2025). Optimization of maximum parallel k-means algorithm based on gpu cluster. Cluster Computing, 28(8):489.
Hu, L., Jiang, M., Dong, J., Liu, X., and He, Z. (2026). Interpretable clustering: A survey. ACM Computing Surveys, 58(8):1–21.
Hu, L., Jiang, M., Liu, X., and He, Z. (2025). Significance-based decision tree for interpretable categorical data clustering. Information Sciences, 690:121588.
Laber, E., Murtinho, L., and Oliveira, F. (2023). Shallow decision trees for explainable k-means clustering. Pattern Recognition, 137:109239.
Laber, E. S. and Murtinho, L. (2021). On the price of explainability for some clustering problems. In International Conference on Machine Learning, pages 5915–5925. PMLR.
Leiserson, C. E., Thompson, N. C., Emer, J. S., Kuszmaul, B. C., Lampson, B. W., Sanchez, D., and Schardl, T. B. (2020). There’s plenty of room at the top: What will drive computer performance after moore’s law? Science, 368(6495):eaam9744.
Li, Y., Zhao, K., Chu, X., and Liu, J. (2013). Speeding up k-means algorithm by gpus. Journal of Computer and System Sciences, 79(2):216–229.
MacQueen, J. (1967). Multivariate observations. In Proceedings ofthe 5th Berkeley symposium on mathematical statisticsand probability, volume 1, pages 281–297. University of California press Oakland, CA, USA.
Merrill, D. and NVIDIA Corporation (2025). CUB: CUDA UnBound. [link]. Biblioteca de primitivas paralelas de alto desempenho para CUDA. Acessado em: 7 out. 2026.
Moshkovitz, M., Dasgupta, S., Rashtchian, C., and Frost, N. (2020). Explainable k-means and k-medians clustering. In International conference on machine learning, pages 7055–7065. PMLR.
Murtinho, L. S. (2025). Clustering under constraints: explainability via decision trees and separability with minimum size. PhD thesis, Pontifícia Universidade Católica do Rio de Janeiro (PUC-Rio), Rio de Janeiro, Brasil.
Owens, J. D., Houston, M., Luebke, D., Green, S., Stone, J. E., and Phillips, J. C. (2008). Gpu computing. Proceedings of the IEEE, 96(5):879–899.
Pan, Z. and Mishra, P. (2022). Hardware acceleration of explainable machine learning. In 2022 Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 1127–1130. IEEE.
Penha, J., Silva, A., Barros, O., Moreira, I., Nacif, J., and Ferreira, R. (2023). Avaliação de estilos de código para Árvores de decisão em gpu com microbenchmarks. In Anais do XXIV Simpósio em Sistemas Computacionais de Alto Desempenho, pages 277–288, Porto Alegre, RS, Brasil. SBC.
Penha, J. C., Bragança, L., Coelho, K., Canesche, M., Silva, J., Comarela, G., Nacif, J. A. M., and Ferreira, R. (2018). A gpu/fpga-based k-means clustering using a parameterized code generator. In 2018 Symposium on High Performance Computing Systems (WSCAD), pages 61–69. IEEE.
Perkel, J. M. (2018). Why jupyter is data scientists’ computational notebook of choice. Nature, 563(7732):145–147.
Rudin, C. (2019). Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature machine intelligence, 1(5):206–215.
Publicado
03/11/2026
Como Citar
FREITAS, Isabela de Castro; PEREIRA, Pedro Henrique Coura; BARROS, Olavo; NACIF, José A. M.; FERREIRA, Ricardo.
Explicabilidade para Kmeans com árvores de decisão em GPU. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 27. , 2026, Natal/RN.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 301-314.
DOI: https://doi.org/10.5753/sscad.2026.34934.
