Centroider: Hardware para aceleração do cálculo de atualização dos centróides do algoritmo K-Means

Abstract

Entre diversas técnicas de análise de dados, uma muito popular devido sua eficiência e simplicidade é o algoritmo K-Means, que calcula similaridade entre todos os dados de um conjunto, sem nenhum rótulo, em um número de grupos definidos pelo usuário. Nesse algoritmo, cada grupo possui um centroide que é a representação da média de todos os elementos que compõem o grupo. Isso pode ser muito útil para diversas aplicações, visto que atualmente grandes quantidades de dados são gerados a cada instante e consequentemente isso torna a tarefa de rotulação muito complexa, tornando os algoritmos de agrupamento de dados cada vez mais relevantes. Entretanto, com o constante aumento no volume de informações, cresce também o custo computacional para o processamento desses dados. Sendo assim, este trabalho busca apresentar uma solução em hardware para acelerar o cálculo de atualização dos centroides, cálculo esse conhecidamente custoso por se tratar de computação intensiva. Para isso foi inicialmente desenvolvido o design da arquitetura explorando paralelismo para implementação utilizando uma linguagem de descrição de hardware. Os resultados de simulação mostraram que os parâmetros que influenciam o tempo de resposta desse hardware são a quantidade de elementos do conjunto de dados e a quantidade de grupos, enquanto isso, a quantidade de dimensões dos dados não tem nenhum impacto nessa latência.