Uma abordagem para o problema de clusterização com restrições de capacidade

Abstract

Resumo: Dentre as diversas aplicações do Aprendizado de Máquina, destacam-se os métodos de agrupamento, onde um conjunto de dados é fornecido e o objetivo consiste em particioná-lo em grupos de forma que elementos de mesmo grupo sejam similares entre si e diferentes de elementos de outros grupos. Esses grupos podem ser gerados mediante diversas técnicas, como os m'métodos de agrupamento hierárquico e os baseados em centroides. Porém, os métodos clássicos não abordam problemas onde o número de pontos dos grupos é pré-determinado, ou quando os pontos têm pesos associados e cada grupo tem uma capacidade. Neste trabalho estudamos um método oriundo da adaptação do algoritmo K-means e do método Branch and bound para resolver problemas dessa natureza. Demonstramos que esse método é competitivo com técnicas já conhecidas na literatura, aliando a qualidade dos resultados obtidos com o tempo computacional utilizado na resolução dos problemas.

Abstract: Among the various applications of Machine Learning, clustering methods stand out, where a dataset is provided and the objective is to partition it into groups so that elements of the same group are similar to each other and different from elements of other groups. These groups can be generated using several techniques, such as hierarchical clustering methods and those based on centroids. However, classical methods do not deal with problems where the number of points in groups is predetermined, or when points have associated weights and each group has a capacity. In this work we study a method derived from the adaptation of the K-means algorithm and the Branch and bound method to solve problems of this nature. We demonstrate that this method is competitive with techniques already presented in the literature, combining the quality of the results obtained with the computational time used in solving the problems.