Fuzzy clustering with capacity constraints: Algorithm, convergence analysis and numerical experiments

doi:10.1016/j.eswa.2024.125191

2024-12-01

PRE

Lucas Garcia Pedroso

Ademir A. Ribeiro *

DOI：10.1016/j.eswa.2024.125191

原文链接

原文求助

摘要

En 中文

In this paper we study the fuzzy clustering problem with capacity constraints. Despite of the fact that the fuzzy clustering approach is widely encountered in the literature, the inclusion of capacity constraints is recent and has several practical applications. We propose a general formulation of the clustering problem, where each point has an associated weight and the sum of the weights of the points that compose each group is established a priori. We discuss existence of solutions of the involved problems, providing a mathematical foundation for the established formulas. Besides, we propose a practical algorithm for solving this problem and present its convergence analysis. This algorithm follows an alternate minimization scheme, wherein a given iteration addresses the problem first in terms of the probabilities of each point x(j) belonging to each cluster i, denoted as u(ij), finding subsequently the position of the centroids, c(t), i = 1, ..., g, j = 1,...,n. This procedure is K-means-like, with the distinction that, as a point does not exclusively belong to a group, the computation of u(tj) requires optimization techniques. In our case, this involves solving a linear system derived from the Karush-Kuhn-Tucker (KKT) conditions. With the aim of validating our algorithm, we present numerical tests with synthetic and real-world data to demonstrate its performance for the given problems. Since the proposal successfully solved these numerical tests within a reasonable computational time, it can be considered a valuable resource for addressing real-world applications.

Keyword:

Data clustering

Constrained clustering

Fuzzy C-means

Capacity constraints

Fuzzy clustering

Clustering algorithm