Métodos de agrupamento com restrições de capacidade

Abstract

Resumo: Neste texto, apresentamos uma revisão de conceitos acerca dos métodos de agrupamento, com maior foco nos baseados em centroides. Para além das abordagens clássicas, apresentamos variações que podem ser úteis em algumas aplicações práticas, como a definição a priori do número de pontos de cada grupo e métodos que lidam com essas restrições. Abordamos uma formulação mais geral para o problema de agrupamento com restrições, onde cada ponto tem um peso associado e a soma dos pesos dos pontos que compõem cada grupo é estabelecida previamente. Tratamos este pro­blema sob as perspectivas fuzzy e não fuzzy. Por fim, apresentamos testes numéricos que atestam a competitividade de nossos métodos ante os clássicos nos casos comparáveis.

Abstract: In this work, we present a review of concepts about clustering methods, with focus on centroid-based methods. In addition to the classic approaches, we present the constraints that may be useful in some practical applications, such as the a priori definition of the number of points in each group, and methods that deal with these constraints. We approach a more general formulation to the constrained clustering problem, where each point has an associated weight, and the sum of the weights of the points that make up each group is established a priori. We approach this problem from a nonfuzzy and fuzzy perspective. Finally, we present numerical tests that show the competitiveness of our methods compared to the classics in comparable cases.