Balanced k-means revisited

1.   Introduction

The clustering problem is to partition objects into separate groups (called clusters) so that objects within one cluster are more similar to each other than objects in different clusters ^[1]. Since the middle of the 20th century, thousands of algorithms addressing the clustering problem have been published ^[2].

One of the most popular clustering algorithms is the $k$-means algorithm ^[2,3]. It was first proposed by ^[4] and ^[5]. This clustering algorithm aims to build $k$ disjoint clusters such that the sum of squared distances between the data points and their representatives is minimized. The representatives, called centroids, are determined by the mean of the data points belonging to a cluster. As a distance function, the Euclidean distance is used. The number of clusters $k$ has to be set by the user.

Formally, if we have a data set consisting of $n$ data points $x_1$, $x_2$, $\dots$, $x_n$, the task is to group these data points into $k$ clusters such that the sum squared error ($\mathrm{SSE}$)

is minimized, where $p_j$ denotes the set of data points assigned to the $j^\mathrm{th}$ cluster and $c_j$ is the centroid of the $j^\mathrm{th}$ cluster. This problem is NP-hard even for two clusters ^[6]. The $k$-means algorithm is a heuristic for this problem.

The algorithm itself starts by initializing the centroid locations. This is followed by an assignment and update steps which are iterated until a convergence criterion is met. During the initialization, $k$ cluster centroids are randomly selected from all data points. In the assignment step, each data point is assigned to the cluster whose centroid is closest. Formally, the assignment step can be written as

In the update step, the centroids are updated by the mean of the data points assigned to the cluster. Formally,

where $|p_j|$ denotes the number of data points assigned to the $j^\mathrm{th}$ cluster. The assignment and update steps are repeated until the centroids do not change anymore.

This algorithm is a heuristic not necessarily returning a global optimum ^[7]. Nevertheless, it returns a local optimum with respect to the $\mathrm{SSE}$: the assignment step minimizes the $\mathrm{SSE}$ for a given set of centroids, while the update step minimizes the $\mathrm{SSE}$ for a given partition ^[7,8]. The running time of one iteration is linear in the number of data points $n$ ^[9].

Among the advantages of this algorithm are its simplicity, time complexity, and usability in a large area of subjects ^[9,10]. However, despite its popularity, it also involves some drawbacks like the strong dependence on the initial choice of the cluster centroids ^[10,11] or its limitation to hyperspherical shaped clusters ^[12]. Another drawback, on which we focus in this paper, is its inability to control the number of objects contained in each cluster. Especially in high dimensional space and if many clusters are desired, often very small clusters seem to appear even if the data itself has a balanced distribution ^[13].

In this paper, we refer to a balanced clustering as a clustering that distributes the data points evenly between the clusters. More formally, to incorporate situations in which the number of data points $n$ is not divisible by the number of clusters $k$, a balanced clustering requires that every cluster contains either $\left\lfloor \frac{n}{k} \right\rfloor$ or $\left\lceil \frac{n}{k} \right\rceil$ data points.

In general, balanced clustering is a two-objective optimization problem pursuing two goals that contradict each other: On the one hand, the $\mathrm{SSE}$ should be minimized, and on the other hand, the difference in cluster sizes should be minimized. If we were just interested in minimizing the $\mathrm{SSE}$, we could apply an ordinary clustering algorithm like $k$-means, and if we were only interested in balancing, we could simply divide the data points randomly into clusters of the same size ^[7,10]. Figure 1 demonstrates the case where minimizing the $\mathrm{SSE}$ with and without a balance constraint results in a different optimal clustering result.

To optimize both aims, there exist two different approaches, hard-balanced, also called balance-constrained, and soft-balanced, also called balance-driven, clustering. Both approaches differ in the way they assess the two objectives. Hard-balanced clustering strictly requires cluster size balance, whereas the minimization of the $\mathrm{SSE}$ serves as a secondary criterion. Soft-balanced clustering considers the balance of the cluster sizes as an aim but not as a mandatory requirement. It intends to find a compromise between the two goals, e.g., by weighting them or by using a heuristic which minimizes the $\mathrm{SSE}$ but indirectly creates more balanced clusters than the standard $k$-means algorithm ^[7,8].

In this paper, we propose a balanced clustering algorithm based on the $k$-means algorithm. Its main principle is an increasing penalty term, which is added to the assignment function of the $k$-means algorithm and favors objects to be assigned to smaller clusters. Because of the increasing penalty term, the resulting balance degree of a clustering is not determined by a rather non-intuitive parameter, but by the point of termination of the algorithm. In this way, the desired balance degree can be specified precisely. However, even if the algorithm has found a clustering with the desired balance degree, it may still be possible to improve the quality of the clustering ($\mathrm{SSE}$) by iterating the algorithm further while keeping the last penalty term fixed.

There are many applications for clustering that rely on a balanced distribution of the objects, i.e., a distribution in which every cluster contains exactly or approximately the same number of objects. Balanced clustering can be used in the division step of divide-and-conquer algorithms to provide equal-sized partitions ^[7]. In load balancing algorithms, balanced clustering can help to avoid unbalanced energy consumption in networking ^[8,14,15] or to balance the workload of salesmen in the multiple traveling salesmen problem ^[16]. In the clustering of documents, articles or photos. Also, in the creation of domain-specific ontologies, balanced clustering can improve the resulting hierarchies by generating a more balanced view of the objects to facilitate navigation and browsing ^[17]. In retail chains, balanced clustering can be used to segment customers into equal-sized groups to spend the same amount of marketing resources on each segment or to group similar products into categories of specified sizes to match units of shelf or floor space ^[17]. Cost function leading to more balanced cluster sizes was used in ^[18] to allow manual investigation of the content of the diagnosis clusters.

A fast $\mathcal{O}(N^{1.5})$ time divide-and-conquer algorithm for planar minimum spanning tree (MST) in ^[19] assumed that the points are distributed equally among the clusters. However, this assumption does not hold if there is even a single large cluster, and the time complexity of the algorithm grows to $\mathcal{O}(N^{2})$. This can be easily avoided using a more balanced clustering algorithm where the worst-case behavior (with one very large cluster) is avoided. For MST, the quality of the clustering is not important as it is merely used as a tool to split the dataset in a meaningful way.

Another example is a clustering-based TSP algorithm ^[20], which normally requires $\mathcal{O}(N\log(N))$ but has the worst-case complexity $\mathcal{O}(N^{2})$ in the same situation when one cluster is very large (rest containing only one node).

The rest of the paper is organized as follows. We begin in Section 2 by summarizing the related work. In Section 3 we present the proposed algorithm. After demonstrating its main principle on a small exemplary data set, we focus on the magnitude of the penalty term and its computation. Further, we briefly consider its termination criterion and time complexity. Section 6 shows the results. We compare the proposed method to the regularized $k$-means algorithm by ^[8] and the balanced $k$-means algorithm by ^[7] on several data sets.

2.   Balanced clustering

We next review the existing approaches for balanced clustering. Approaches for hard-balanced clustering are reviewed in Section 2.1 and for soft-balanced clustering in Section 2.2, respectively.

2.1.   Hard-balanced clustering

A popular approach to face this problem is to formulate the assignment step of the standard $k$-means algorithm as an optimization problem satisfying balance constraints and solve it by linear programming. The constrained $k$-means algorithm proposed by ^[13] follows this approach and ensures clusters of given minimum sizes by solving a minimum cost flow problem. Depending on the chosen minimum cluster sizes, this algorithm can also be used for soft-balanced clustering. The time complexity of the assignment step is $\mathcal{O}(k^{3.5}n^{3.5})$, which makes the algorithm much slower than the standard $k$-means algorithm and reduces its scalability, especially for large data sets ^[7].

The balanced $k$-means algorithm proposed by ^[7] solves the assignment step of $k$-means by the Hungarian algorithm. This reduces the time complexity of the assignment step compared to the previous method to $\mathcal{O}(n^3)$, but is still too slow for large data sets.

Another hard-balanced clustering algorithm formulating the assignment step of the standard $k$-means algorithm as a linear programming problem is the algorithm proposed by ^[21]. They claimed that the average time complexity of their algorithm is only $\mathcal{O}(mn^{1.65})$ to $\mathcal{O}(mn^{1.7})$ ($m$ denotes the number of iterations), which improves the running time remarkably compared to the above-mentioned algorithms.

An even faster algorithm was proposed by ^[22]. This algorithm does not follow the iterative structure of the $k$-means algorithm but transforms the balanced clustering problem directly into a linear programming problem by using a heuristic function. However, this algorithm cannot keep up with the quality of the clustering achieved by the other algorithms ^[21].

A further method following the linear programming approach is regularized $k$-means by ^[8]. It extends the previous models by adding a balance regularization term to the objective function that can be adapted according to the requirements. Thus, depending on the chosen regularization term, this algorithm can also be used for soft-balanced clustering.

Some further proposed algorithms for hard-balanced clustering follow different approaches. For example, the neural gas clustering algorithm is adapted by ^[23] to handle given cluster sizes. Conic optimization is used by ^[24], which also allows to provide bounds on the suboptimality of the given solution. The fuzzy $c$-means algorithm is applied by ^[25] before using the resulting partial belongings and the given size constraints to finally assign the data points to the clusters. A basic variable neighborhood search heuristic following the less is more approach was proposed by ^[6]. This heuristic performs a local descent method to explore neighbors, which are obtained by swapping points from different clusters in the current optimal solution. Recently, ^[26] proposed a memetic algorithm combining a crossover operator to generate offspring and a responsive threshold search alternating between two different search procedures to optimize the solution locally. A greedy randomized adaptive search procedure combined with a strategic oscillation approach to alternate between feasible and infeasible solutions is used by ^[27].

2.2.   Soft-balanced clustering

A popular approach for the soft-balanced clustering problem is the use of a multiplicative or additive bias in the assignment function of the standard $k$-means algorithm. First, Banerjee and Ghosh ^[28] proposed to use the frequency-sensitive competitive learning method. Competitive units, clusters competing for data points, are penalized in proportion to the frequency of their winning, aiming at making all units participate. Banerjee and Ghosh ^[28] applied this method by introducing a multiplicative bias term in the objective function of the standard $k$-means algorithm, which weights the distance between a data point and a centroid depending on the number of data points already assigned to the cluster. In this way, smaller clusters are favored in the assignment step.

They also provided a theoretical background for their approach. The $k$-means algorithm implicitly assumes that the overall distribution of the data points can be decomposed into a mixture of isotropic Gaussians with a uniform prior. Banerjee and Ghosh ^[28] followed the idea to shrink the Gaussians in proportion to the number of data points that have been assigned to them by dividing the covariance matrix of each cluster by the number of data points assigned to it. Maximizing the log-likelihood of a data point with respect to this framework leads to the multiplicative bias ^[12,28].

A similar approach was presented by ^[29]. They also adapted the assumption that a data point is distributed according to a mixture of isotropic Gaussians with uniform prior. But instead of changing the shape of the clusters by shrinking the Gaussians, they adjusted their prior probabilities such that they decrease exponentially in the number of data points assigned to them. Thus, the more data points a Gaussian contains, the lower its prior probability becomes. Maximizing the log-likelihood of a data point with respect to this framework results in an additive bias. Liu et al. ^[30] complemented their work by providing the objective function and adding a theoretical analysis with respect to convergence and bounds in terms of bicriteria approximation.

Further algorithms use the least square linear regression method combined with a balance constraint that aims at minimizing the variance of the cluster sizes ^[14,31]. The least square regression error is minimized in each iteration such that the accuracy of the estimated hyperplanes, which partition the data into clusters, improves step by step.

Li et al. ^[32] proposed an algorithm following the approach of the exclusive lasso. This method models a situation in which variables within the same group compete with each other ^[33]. They computed the exclusive lasso of the cluster indicator matrix, which equals the sum of the squared cluster sizes, and used it as a balance constraint by adding it as a bias to the objective function of the standard $k$-means algorithm.

A more generalized method, that can deal with different balance structures (cardinality, variance, and density), was proposed by ^[34]. In the assignment step of the standard $k$-means algorithm, a multiplicative weight is added as a bias and additionally, a balancing phase is introduced after each update step. In this phase, points are shifted from clusters with the largest weights to clusters with the lowest weights. The weights are updated after each iteration and their computation depends on the chosen balance structure.

A completely different approach, proposed by ^[17], introduced a stepwise working soft-balanced clustering algorithm, that provides, even though it is soft-balanced, some balance guarantees in the form of minimum cluster sizes. First, a representative subset of the data points is sampled from the data, which then is clustered by an existing clustering algorithm. Since the amount of sampled points is small compared to the size of the data set, a slightly more complex algorithm can be chosen. Afterwards, the remaining points are distributed to the existing clusters respecting the balance constraints, and finally, refinements are made to further minimize the objective function.

Lin et al. ^[35] proposed an algorithm called $\tau$-balanced clustering. The variable $\tau$ denotes the maximal difference between the sizes of any two clusters and can be determined by the user. By setting this variable to one, a hard-balanced clustering algorithm is obtained. In the assignment step, a data point is assigned to the cluster whose centroid is closest if the size restrictions are not violated. Otherwise, it replaces a data point already assigned to the cluster if that point is farther from the centroid than the point that has to be assigned, else the cluster with the next nearest centroid is considered. After every data point is assigned to a cluster, the cluster centroids are updated according to the standard $k$-means algorithm. The algorithm terminates when the cluster centroids converge. Malinen and Fränti ^[36] recently showed that also agglomerative clustering leads to more balanced clustering than SSE if the cost function calculates all pairwise distances.

3.   Proposed method

We modify the standard k-means algorithm in such way that it not only considers the squared distances to the cluster centroids but also takes the cluster sizes into account. Our approach is to add a penalty term to the objective function of the standard $k$-means algorithm, which depends on the number of data points already assigned to a cluster. Thus, we want to create a new objective function in the shape of

The penalty term of a cluster has to increase with the number of data points contained in that cluster. In this way, clusters containing few data points are favoured to get more points, and clusters containing many points are disfavoured. Thus, the clustering becomes more balanced. An easy example of a penalty term satisfying this property is the function that just returns the size of a cluster, $\mathit{penalty}(j) = n_j$, where $n_j$ denotes the number of data points already assigned to the $j^{th}$ cluster. However, this function does not take into account the scale between the $\mathrm{SSE}$ and the number of data points. If the penalty term returns constant zero, the optimization of Equation 2 reduces to the minimization of the $\mathrm{SSE}$, hence to the same problem that the standard $k$-means algorithm is facing.

The addition of a penalty term to the assignment function of the standard $k$-means algorithm follows the approach of ^[29] and ^[30]. The crucial point, in which we deviate from their method, is the determination of the penalty term. An appropriate value of the penalty term is essential for the algorithm in order to produce reasonable results, but it strongly depends on the given data set.

3.1.   Increasing penalty term

We address this problem by introducing an increasing penalty term. The idea is to start with a clustering produced by the standard $k$-means algorithm that yields a reasonably good clustering quality in minimizing the $\mathrm{SSE}$, and use a gradually increasing penalty term to shift the focus towards the balance. Figure 2 illustrates this intended behaviour. The initial solution contains two clearly separated clusters. When the penalty term is increased once, only the point $x_1$ joins the cluster on the right. After subsequent increases in the penalty term, also points $x_2$, $x_3$ and $x_4$ join the rightmost cluster. In this way, the balance quality increases while the clustering quality decreases. The algorithm terminates as soon as the desired balance requirement is met.

Following this approach, we further avoid using a non-intuitive parameter that determines the trade-off between the clustering and the balance quality like many soft-balanced clustering algorithms do ^[8,29,32]. Instead, the balance degree is determined by the time of termination, for which a criterion in form of a balance requirement can be given (see Section 5.2 for different ways to measure the balance quality). Thus, if, for example, a user wishes to reach a certain maximum difference between the smallest and the largest cluster, the algorithm will continue until such a clustering is reached. Therefore, this approach represents a very intuitive way of defining the trade-off between clustering and balance performance.

Formally, we seek a penalty term contingent on both cluster size and the number of iterations. Therefore, we introduce the function $\mathit{scale}$, a strictly increasing function depending on the number of iterations, and define

As the value of the function $\mathit{scale}$ becomes steadily larger with the number of iterations, the influence of the cluster sizes increases relative to the error term $\mathrm{SSE}$ in each iteration. By introducing the dependency of the penalty term on the number of iterations, the objective function also becomes dependent on the number of iterations.

3.2.   Scaling the penalty term

One of the easiest ways to define the function $\mathit{scale}$ consists of choosing it as a classical function like a logarithmic, linear, quadratic, or exponential function. However, the problem with using one of these functions is the uniqueness of each data set. Using an increasing penalty term does not mean that we no longer have to be concerned about the appropriate magnitude of the penalty term.

If the penalty term is too small, it takes a very long time to reach a balanced clustering. On the other hand, if the term becomes too large too fast, overlapping clusters are produced. This can be seen as follows: In Figure 2, in the optimum case in one iteration the penalty term is large enough such that point $x_1$ changes to the smaller cluster on the right, but the term is not large enough to make the points $x_2$, $x_3$ and $x_4$ change to the cluster on the right. In the next iteration, the penalty term increases such that also the points $x_2$ and $x_3$ change to the cluster on the right, but still the penalty term is not large enough to make point $x_4$ change to the cluster on the right. In the next iteration, the penalty term further increases such that now also point $x_4$ changes to the cluster on the right. However, if the penalty term increases too fast, for example, if points $x_1$ and $x_4$ can change to the cluster on the right in the same iteration for the first time, it can happen that $x_4$ changes to the cluster on the right, but $x_1$ does not. Then, overlapping clusters are formed.

Therefore, the size and growth of the penalty term are critical, and due to the uniqueness of each data set, one data set may require a smaller penalty term, while other data sets need larger penalties and the required growth of the penalties can also differ.

Thus, we take a slightly more complicated approach than using a classical function, but also a more effective approach. The main principle is that progress in producing a more balanced clustering out of an unbalanced one happens only when a data point changes from a larger to a smaller cluster. Thus, the value of $\mathit{scale}$ should be large enough to make a data point change from a larger to a smaller cluster. At the same time, it should not be chosen too large to preserve a good clustering quality, since a rapidly increasing penalty term tends to lead to overlapping clusters.

This seems to be a high demand for the value of $\mathit{scale}$, but indeed, during one iteration of the algorithm, we can compute the minimum value of the penalty term for the next iteration that is necessary to make at least one data point change to a smaller cluster.

Let us start simple: We assume that we are in iteration $\mathit{iter}$ in the assignment phase of data point $x_i$ and its old cluster is denoted by ${j_ \mathit{old}}$. Then, data point $x_i$ is able to change to cluster ${j_ \mathit{new}}$ containing less data points, $n_{j_ \mathit{new}} < n_{j_ \mathit{old}}$, only if

Note that the last equivalence relies on our assumption

First, if inequality 3 holds, data point $x_i$ can change to cluster ${j_ \mathit{new}}$. This does not imply that $x_i$ will indeed change to cluster ${j_ \mathit{new}}$, because there can be another cluster that leads to an even smaller cost term. However, point $x_i$ will change its cluster.

On the other hand, if inequality 3 does not hold, data point $x_i$ will not change to cluster ${j_ \mathit{new}}$ during this iteration. Now the left-hand side of the inequality becomes interesting: It describes the value of $\mathit{scale}$ which is at least necessary to enable the change of data point $x_i$ from cluster ${j_ \mathit{old}}$ to cluster ${j_ \mathit{new}}$. In other words, if we choose $\mathit{scale}( \mathit{iter} + 1)$ as this value, data point $x_i$ will be able to change to cluster ${j_ \mathit{new}}$ during the next iteration (assuming that there are no changes in the assignments and locations of the clusters ${j_ \mathit{old}}$ and ${j_ \mathit{new}}$ until the assignment phase of $x_i$ in the next iteration). We denote this minimum value that is necessary to enable the change of data point $x_i$ from its old cluster ${j_ \mathit{old}}$ to cluster ${j_ \mathit{new}}$, by $\mathit{scale}( \mathit{iter}, i, j_ \mathit{new})$ and define it, based on inequality 3, as

where $\varepsilon$ is a very small number $> 0$ (to account for the inequality in 3), ${j_ \mathit{old}}$ denotes the old cluster of $x_i$, and the cluster assignments and centroid locations at the time of the assignment phase of data point $x_i$ during iteration $\mathit{iter}$ are used.

During the iteration over all data points and clusters, we save the minimum of all these values which are larger than the current value $\mathit{scale}( \mathit{iter})$ and denote it by $\mathit{scale}_{ \mathit{min}}( \mathit{iter})$, i.e.,

We only consider values of $\mathit{scale}( \mathit{iter}, i, j_ \mathit{new})$ which are larger than the current value $\mathit{scale}( \mathit{iter})$, used in the penalty term in this iteration, because if $\mathit{scale}( \mathit{iter}+1)$, the value that will be used in the next iteration, is smaller than the current one, it enables data points which already changed from a larger to a smaller cluster to change back to the larger cluster again. In this case, we take a step backward concerning our aim to balance the cluster sizes.

The value $\mathit{scale}_{ \mathit{min}}( \mathit{iter})$ is the minimum value that is needed for $\mathit{scale}$ in the next iteration to make a data point change from a larger to a smaller cluster, hence, it is the value we are looking for. Therefore, we require

3.3.   Increasing penalty factor f

Perhaps one expected an equality instead of an inequality in 9. The problem of using the equality is that the closer we choose the value of $\mathit{scale}( \mathit{iter}+1)$ to the value of $\mathit{scale}_{ \mathit{min}}( \mathit{iter})$, the fewer data points will change their clusters during iteration $\mathit{iter}+1$. In other words, if we choose $\mathit{scale}( \mathit{iter}+1)$ exactly as $\mathit{scale}_{ \mathit{min}}( \mathit{iter})$, in many iterations only one data point will change from a larger to a smaller cluster. This is not that bad if the cluster sizes are almost balanced and there are only a few data points left that have to change the clusters to obtain a balanced clustering, but if the cluster sizes are far from being balanced, then the algorithm takes a lot of iterations until a balanced clustering is reached.

On the other hand, if $\mathit{scale}( \mathit{iter}+1)$ is chosen much larger than $\mathit{scale}_{ \mathit{min}}( \mathit{iter})$, a lot of data points are able to change their clusters during the iteration $\mathit{iter}+1$, and the probability that wrong data points are assigned to the smaller clusters, such that overlapping clusters are produced, increases. Thus, the choice of the relation between $\mathit{scale}(iter+1)$ and $\mathit{scale}_{ \mathit{min}}( \mathit{iter})$ seems to be critical, and this decision indeed results in a trade-off between the clustering quality and the running time. For now, we deal with this problem by introducing the increasing penalty factor $f$ and define

3.4.   Partly remaining fraction c

In the standard $k$-means algorithm, the cluster sizes do not need to be known during the assignment step of a data point because they are not necessary for the computation of the cost of assigning a data point to a cluster. However, if we include a penalty term as indicated in Equation 2, we have to know the cluster sizes during the assignment of a data point.

The calculation of the cluster sizes itself is quite simple, but the crucial question is when to update the cluster sizes. This could take place after every complete iteration of the algorithm, after the assignment phase of every data point, or before and after the assignment phase of every data point (in the sense of removing a data point from its cluster before its assignment starts). Indeed, none of these approaches is really good, each has its shortcomings, like producing oscillating or overlapping clusters. The most promising approach, which we chose, is the following. A data point is removed partially from its old cluster before its assignment and only after its new assignment it is removed completely from its old cluster and added to its new cluster. In this way, during the assignment of a data point, the point only partially belongs to its old cluster. To define partially, we introduce the constant $c$ with $0 < c < 1$, which we refer to as the partly remaining fraction of a data point.

4.   Algorithm BKM+

The proposed algorithm is presented in Algorithm 1. We call it balanced $k$-means revisited (BKM+).

In each iteration of the algorithm, each data point is assigned to the cluster $j$ which minimizes the cost term $||x_i - c_j ||^2 + p_ \mathit{now} \cdot n_j$. In this process, the data point is first partly removed from its old cluster, see function RemovePoint, and afterward added to its new cluster and completely removed from its old cluster, see function AddPoint. Directly after the computation of the cost term, the variable $p_{ \mathit{next}, i}$, corresponding to $\min_{j_{ \mathit{new}} \in \{1, \dots, k\}} \{ \mathit{scale}( \mathit{iter}, i, j_ \mathit{new}) \}$, is computed using the function PenaltyNext, which implements Equation 7. If this number is a candidate for $p_{ \mathit{next}}$, its value is taken. After all data points are assigned, the penalty term $p_ \mathit{now}$ is set for the following iteration by multiplying $p_ \mathit{next}$ by the increasing penalty factor $f$. Afterward, the assignments of the data points start again. The algorithm terminates as soon as the largest cluster is at most $\Delta n_{ \mathit{max}}$ data points larger than the smallest cluster.

4.1.   Optimization of parameters c and f

The algorithm contains two parameters that have to be determined: The partly remaining fraction $c$ for defining the fraction of a data point that belongs to its old cluster during its assignment, and the increasing penalty factor $f$, which determines the factor by which the minimum penalty that is necessary in the next iteration to make a data point change to a smaller cluster is multiplied.

For $c$, a value between $0.15$ and $0.20$ is reasonable in every situation. The choice of $f$ is a trade-off between the clustering quality and the running time: if the focus is on the clustering quality, $f$ should be chosen as $1.01$ or smaller, whereas if the running time is critical, setting $f$ to $1.05$ or $1.10$ is the better choice. A compromise is to choose $f$ as a function depending on the number of iterations. In the beginning, $f$ can be chosen larger to ensure a fast progress of the penalty term, while in the end $f$ should be chosen smaller to avoid a negative influence on the clustering quality. For example, we can define a function $f_ \mathit{iter}$, whose value is $1.10$ in the first iteration and $1.01$ starting from the $101^{\mathrm{st}}$ iteration, and between these iterations, we linearly interpolate the values. Table 1 summarizes the recommended ranges and the default values for $c$ and $f$.

4.2.   Application of the standard $k$-means algorithm

Until now, we applied the standard $k$-means algorithm at the beginning of the algorithm to obtain a clustering as a starting point since the computation of the penalty term relies on the cluster sizes. However, this raises the question of whether it is necessary to apply the standard $k$-means algorithm until its termination.

After the initialization of the cluster centroids, one iteration of the standard $k$-means algorithm is necessary to assign the data points to the clusters and another iteration is necessary to compute the starting value of $\mathit{scale}$. Since an iteration of the standard $k$-means algorithm corresponds to an iteration of our algorithm when setting $\mathit{scale} = 0$, we can perform two iterations of the standard $k$-means algorithm in the beginning by defining $\mathit{scale}(0) = \mathit{scale}(1) = 0$. Afterward, we can compute the values of $\mathit{scale}( \mathit{iter})$ based on the values of $\mathit{scale}_{ \mathit{min}}( \mathit{iter} - 1)$ like we defined in Equations 7, 8 and 10. There are no meaningful differences in the clustering quality if the standard $k$-means algorithm is applied for only two iterations in the beginning, but the running time is significantly faster.

4.3.   Computation of the function $\text{scale}$

We introduced the function $\mathit{scale}$, which returns the minimum value of the penalty term that is necessary to make at least one data point change its cluster multiplied by the increasing penalty factor $f$. To compute its value for the iteration $\mathit{iter} +1$, we have to compute the values $\mathit{scale}( \mathit{iter}, i, j)$ for all $n \cdot k$ combinations of data points and clusters.

However, the use of the function $\mathit{scale}$ does not require computing the cost of the assignment and the value of $\mathit{scale}( \mathit{iter}, i, j)$ for every of the $n \cdot k$ combinations of data points and clusters as it may look in Algorithm 1. The information contained in these values is different, but it is not independent. One possibility to reduce the number of calculations is to always compute $\mathit{scale}( \mathit{iter}, i, j)$ and compare it to the value of $\mathit{scale}(iter)$. By the result of this comparison, we know whether data point $x_i$ could move to cluster $j$ and only in this case do we have to compute the cost of assigning $x_i$ to $j$.

4.4.   Termination criterion

In Algorithm 1, we used $\Delta n_{ \mathit{max}}$, the maximum difference in cluster sizes, as the termination criterion. Since the desired balance degree is application dependent, we keep the termination criterion as user input, but in a generalized way: instead of the maximum difference in cluster sizes, an arbitrary balance criterion can be selected, e.g., the standard deviation in cluster sizes ($\mathrm{SDCS}$) or the normalized entropy ($\mathrm{N}_\mathrm{entro}$) (for an explanation of these measures see Section 5.2).

In some situations, it can be advantageous to continue running the algorithm even if the balance criterion is already met and to return the clustering with the best clustering quality satisfying this criterion. This approach requires saving the best clustering reached so far, but it can help to improve the clustering quality. Especially if the data set is not well known (in the sense that the balance of the clustering producing the minimum $\mathrm{SSE}$ on the data set is not approximately known), this approach prevents a resulting clustering from being optimizable in both the clustering and the balance quality. Additionally, the current penalty term can be kept for the next iteration if the current clustering already meets the balance criterion and its $\mathrm{SSE}$ is the lowest found so far satisfying this criterion.

4.5.   Time complexity

The running time of the algorithm depends on the number of iterations and the running time per iteration.

In the first part of each iteration, the iteration over all $n$ data points and $k$ clusters dominates. Its complexity is $\mathcal{O}(nk)$. In the second part of each iteration, the dominating operation is the iteration over the clusters to compute the balance measure which takes $\mathcal{O}(k)$. If the $\mathrm{SSE}$ is computed or the current assignments are saved, the time complexity for the second part increases to $\mathcal{O}(n)$. However, independent of computing the $\mathrm{SSE}$ or saving the assignments in the second part of each iteration, the complexity of the first part dominates. Therefore, the complexity of one iteration of the algorithm is $\mathcal{O}(nk)$.

The number of iterations is difficult to predict. It primarily depends on the chosen data set and termination criterion, but also on the increasing penalty factor $f$. For example, to reach a balance clustering, on the data set $\mathsf{wine}$ (for properties and references of the mentioned data sets see Section 5) the algorithm takes about $15$ iterations setting $c = 0.15$ and $f = 1.01$, on the data set $\mathsf{S3}$ it takes about $90$ iterations setting $c = 0.1$ and $f$ to the function $f_ \mathit{iter}$, on the data set $\mathsf{A3}$ it takes about $180$ iterations setting $c = 0.2$ and $f$ to the function $f_ \mathit{iter}$, on the data set $\mathsf{unbalance}$ it takes about $400$ iterations setting $c = 0.01$ and $f = 1.01$, and on the data set $\mathsf{birch1}$ it takes about $600$ iterations setting $c = 0.15$ and $f$ to the function $f_ \mathit{iter}$.

Nevertheless, the algorithm is several orders of magnitude faster than BKM, which requires $\mathcal{O}(N^3)$ just for the assignment step whereas BKM+ requires $\mathcal{O}(INk)$ for the entire algorithm. Here $I$ is the number of iterations which varies from $I=15$ to 800 with our datasets. The longest iterated is Birch1 having parameters $I=800$, $N=100, 000$, and $k=100$. This corresponds to $8 \cdot 10^{9}$ steps whereas the BKM assignment step alone would require $100, 000^3 = 10^{15}$ steps. The difference is huge.

4.6.   Point swap post-processing

For some datasets in the hard balance case, the BKM+ algorithm produces an suboptimal clustering with slightly overlapping partitions (see Figure 4). To further improve results in these cases, we use a post-processing method (Algorithm 2) to iteratively swap points between partitions. We denote this method as BKM++.

The swap-based optimization is run for all possible pairs of clusters. In the case of cluster partitions $A, B$, we measure how much would the SSE change ($\Delta_{x \rightarrow B}$) if we switched a point $x \in A$ to cluster $B$. If $\Delta_{x \rightarrow B} < 0$, then SSE would improve, but the partitions would also become more unbalanced. Therefore, to keep the partitions balanced, we would also need to find a point $y \in B$ that could be swapped to $A$ so that $\Delta = \Delta_{x \rightarrow B} + \Delta_{y \rightarrow A} > 0$ to keep the partitions balanced while improving the cost function.

We use a greedy strategy to select the points $x$ and $y$ in a way that maximizes $\Delta$. The points in $A$ are sorted based on $\Delta_{x \rightarrow B}$ and similarly for cluster $B$. We then pick the first points (with the largest $\Delta_{x \rightarrow B}$ and $\Delta_{y \rightarrow A}$) from clusters $A$ and $B$. If, for those points, $\Delta > 0$, we make the switch. This is repeated for the next points in the clusters as long as $\Delta > 0$.

After all possible SSE improving swaps have been done for clusters $A$, $B$, the centroids for those clusters are recalculated. This same operation is performed for all possible pairs of clusters. After processing all possible pairs of clusters, the centroid locations have changed, and repeating this same process for another iteration may be able to further improve the cost function. The post-processing process can be iterated as long as it successfully finds swaps that improve the SSE. However, we noticed that typically most of the improvement comes in the first 3 iterations. We therefore run the postprocessing for a maximum 10 iterations, although in most cases it converges earlier.

The point swap post-processing method has a low time complexity. The operation for one pair of clusters needs to sort the N/k points in both clusters, which makes it $\mathcal{O}((N/k)\log(N/k))$. This is repeated for all of the $\mathcal{O}(k^2)$ pairs of clusters. The time complexity of one iteration is therefore $\mathcal{O}(k^2(N/k)\log(N/k)) = \mathcal{O}(kN\log(N/k))$, which is very close to one iteration of $k$-means $\mathcal{O}(kN)$.

5.   Experimental setup

The balanced clustering algorithms we chose for comparison are regularized $k$-means (RKM) proposed by ^[8] and balanced $k$-means (BKM) by ^[7]. RKM is an algorithm that can be used for both soft- and hard-balanced clustering depending on the selected balance regularization term, while BKM is solely a hard-balanced clustering algorithm. Another method considered for comparison was $\tau$-balanced clustering by ^[35]. Unfortunately, the publicly available implementation was incomplete.

For our method, we use the proposed algorithm with all the mentioned optimizations. The partly remaining fraction $c$ is set to $0.15$ and for the increasing penalty factor $f$ the function $f_ \mathit{iter}$ is used. The algorithm is implemented in C++^*.

^*The source code of BKM+ can be found at https://cs.uef.fi/ml/software and https://github.com/uef-machine-learning/Balanced_k-Means_Revisited.

The source codes of BKM^† and RKM^‡ are publicly available. BKM is implemented in MATLAB and RKM is implemented in C++. BKM could be made somewhat faster if re-implemented in C++, but since the algorithm has $\mathcal{O}(n^3)$ time complexity, the running time will be very slow regardless of the implementation. For both algorithms, we used the default settings, unless specified otherwise. As a platform, Intel Core i5-7300U 2.60GHz processor with 8GB memory was used for the experiments on soft-balanced clustering, and Intel Xeon Gold 6212U 2.40GHz processor with 754GB memory for the hard-balanced clustering. No parallel processing was used.

^†The source code of BKM can be found at https://cs.uef.fi/ml/software

^‡The source code of RKM can be found at https://github.com/zhu-he/regularized-k-means

In the experiments we considered the artificial data sets $\mathsf{S1}$-$\mathsf{S4}$, $\mathsf{A1}$-$\mathsf{A3}$, $\mathsf{birch1}$, $\mathsf{birch2}$, $\mathsf{unbalance}$ and $\mathsf{dim32}$ ^[37,38,39] and the real-world data sets $\mathsf{vowel}$ $\mathsf{recognition}$, $\mathsf{iris}$, $\mathsf{user}$ $\mathsf{knowledge}$, $\mathsf{wine}$, $\mathsf{ionosphere}$, $\mathsf{libra}$ and $\mathsf{multiple}$ $\mathsf{features}$ from the UCI machine learning repository ^[40,41]. Detailed information on the data sets is shown in the first column of Table 2. The first number under the name of a data set denotes its size, the second number is its dimension and the third number refers to the number of clusters sought in the data set.

5.1.   Clustering quality

There are many ways to assess the quality of a clustering ^[38]. We use the sum of squares error function ($\mathrm{SSE}$), defined in Equation 1, as an internal evaluation criterion, and the normalized mutual information ($\mathrm{NMI}$) as an external criterion ^[31,42,43]. The $\mathrm{NMI}$ of a labeling with $k$ different labels and a clustering with $k$ clusters is defined as

where $n_h$ denotes the number of objects in class $h$, $n_l$ refers to the number of objects assigned to cluster $l$, $n_{h, l}$ defines the number of objects that are in class $h$ as well as assigned to cluster $l$, and $n$ denotes the total number of objects. A value of one means a perfect match between the labeling and the clustering, whereas a value close to zero indicates a random partitioning ^[31].

5.2.   Balance

A popular and intuitive approach to measure the balancing behavior of a clustering algorithm is the standard deviation in cluster sizes ($\mathrm{SDCS}$). Let $n_j$ denote the size of the $j^\mathrm{th}$ cluster and $k$ the number of clusters, then the $\mathrm{SDCS}$ is defined as

The smaller the standard deviation becomes the better the balance. A value of zero implies a perfectly balanced clustering (note that if $n$ is not divisible by $k$, a value of zero will never be reached) ^{[12,17,25,28,34]}.

Another way to measure the balance of a clustering is to consider the entropy of the distribution of the cluster sizes. To simplify comparisons, we again consider a normalized version of the entropy, which is formally defined as

A normalized entropy of one implies a perfectly balanced clustering, while a value of zero represents an extremely unbalanced clustering (again, the divisibility of $n$ by $k$ must be taken into account) ^[14,30,31].

In addition to these measures that give a review of the overall distribution of the cluster sizes, it can be useful to know whether a clustering contains extremely small clusters. To check this undesirable behavior, the minimum cluster size can be considered ^[12,17,28].

6.   Results

We next present the experimental results. We consider the hard-balanced version of the proposed algorithm in Section 6.1 and the soft-balanced version in Section 6.2. The results are discussed in Section 7.

6.1.   Hard-balanced clustering

We start by comparing the hard-balanced version of the proposed algorithm to BKM and the hard-balanced version of RKM.

The proposed method has two variants, one with the point swap post processing (BKM++) and one without (BKM+). To get fully balanced clusters, we set the termination criterion of the proposed method to a maximum difference of one in the cluster sizes. BKM is a hard-balanced clustering algorithm by definition. To get a hard-balanced version of RKM we choose the regularization term for hard-balanced clustering proposed by the authors ^[8].

We run each algorithm $100$ times on each data set and report the mean sum of squared errors ($\mathrm{SSE}$) and normalized mutual information ($\mathrm{NMI}$) as well as the average running time. Since the resulting clustering depends on the initialization of the clusters and, in the case of the proposed method, also on the order of the data points in the data set, every algorithm starts with the same initial assignments and orders of the data set. The results are shown in Table 2.

The results of all three methods are quite similar both regarding to $\mathrm{SSE}$ and $\mathrm{NMI}$. Especially in the case of the artificial data sets, the results are almost identical, both in mean and best run. Overall, RKM leads to slightly lower $\mathrm{SSE}$ values, but the difference is not significant. The main difference in performance is in the running time, in which both RKM and BKM+ are an order of magnitude faster than BKM. For example, the data sets $\mathsf{birch1}$ and $\mathsf{birch2}$ require $>$ 12 hours by BKM whereas RKM and BKM+ require only 1-2 minutes. The proposed algorithm BKM+ appears to be slightly faster than RKM if clusters are more overlapping, see data sets $\mathsf{S1}$-$\mathsf{S4}$.

The results of BKM+ are visualized for selected datasets in Figures 3, 4 and 5. Our first observation is that the use of variable balance constraint actually improves results also compared to standard $k$-means. The datasets A3 and B1 cannot be successfully clustered by $k$-means even if repeated 100 times or using better initialization (Maxmin or $k$-means++) ^[11]. However, BKM+ can reach the correct clustering because the balance constraint makes the algorithm a stochastic variant of $k$-means, which helps to overcome local minima.

The two most demanding datasets for BKM+ are Santa ^[44] and Unbalanced; both are characterized by variable-size clusters. The Santa dataset (see Figure 4 and Table 2) contains 1.4 million points representing house coordinates in Finland. {BKM+ algorithm finds approximately the correct clustering but there are minor degradation at the cluster borders (SSE 3.745e+15). These errors are fixed by using the post-processing algorithm BKM++ (SSE 3.653e+15) which yields also slightly better results than RKM (SSE 3.683e+15).}

For the Santa dataset (Figure 4), the proposed method has better time and memory efficiency compared to RKM. It took only 19% of the processing time required by RKM, and the memory footprint was only 8% compared to RKM (125MB vs. 1, 403MB).

BKM++ could significantly ($>$0.5%) improve the SSE results of BKM+ in case of 8 of the 19 datasets. BKM++ results were almost identical to RKM results. There were only three cases where SSE result of RKM differed more than 0.1% compared to BKM++. For two of these cases BKM++ had a smaller SSE ($\mathsf{santa}$ -0.8%, $\mathsf{libra}$ -1.2%, $\mathsf{S2}$ +0.1%).

The worst-case for the BKM+ algorithm is the unbalance dataset (Figure 5) with a very unbalanced distribution of the points into three dense (2000) and five sparse (100) well-separated clusters. Forcing a balance should create clusters of size 812 or 813 so that the sparse ones would be merged into one cluster and taking about 312 more points from the rightmost dense cluster. The dense clusters would be split accordingly.

The results are shown in Figure 5. The start point is a typical (sub-optimal) $k$-means solution, which starts to evolve as expected by increasing the sparse part of the data. However, once the sparse cluster starts to conquer points from the dense area, the clustering starts to break, resulting in sub-optimal results. If the algorithm continued to reach complete balance, the MSE would increase to $1.87 \cdot 10^{13}$. However, the BKM++ post-processing algorithm can fix also these errors, resulting in an average SSE of $1.70 \cdot 10^{13}$ (Table 2), which is also equal to the results of the RKM algorithm.

6.2.   Soft-balanced clustering

Next, we compare the soft-balanced version of the proposed algorithm to the soft-balanced version of RKM. For the comparison of the balance, we use three different balance measures, the standard deviation in cluster sizes ($\mathrm{SDCS}$), the normalized entropy ($\mathrm{N}_\mathrm{entro}$), and the minimum cluster size (for a definition of these measures see Section 5.2).

According to the balance measure, we set the termination criterion of the proposed method as described in Section 4.4 to a maximum value of $\mathrm{SDCS}$, a minimum value of $\mathrm{N}_\mathrm{entro}$ or a minimum value of the minimum cluster size. To obtain clusterings of different balance degrees, we vary these values. RKM optimizes the balance using a regularization term including a balance parameter $\lambda$. Depending on the balance measure that has to be optimized, the authors propose different regularization terms ^[8]. We use the regularization term corresponding to the chosen balance measure and vary the parameter $\lambda$. As in the hard-balanced case, we run each algorithm $100$ times with all balance settings on each data set using the same initializations. The mean of the $\mathrm{SSE}$, the balance measure and the running time were reported.

Figures 6 and 7 show the results for the data sets $\mathsf{S2}$ and $\mathsf{S4}$. The plots on the left side show the results as a function of the balance measure (x-axis) and the $\mathrm{SSE}$ (y-axis), whereas the plots on the right side show the results as a function of the balance measure (x-axis) and the running time (y-axis). The $\mathrm{SSE}$-results of the two methods are almost identical between RKM and BKM+ when the balance is given high emphasis and is measured by $\mathrm{SDCS}$ or $\mathrm{N}_\mathrm{entro}$. RKM provides slightly better results if the balance is measured by the minimum cluster size.

When the focus is more on the clustering quality instead of the balance quality, BKM+ is more stable and provides better $\mathrm{SSE}$-results while the results of RKM start to deteriorate. The difference in running time becomes also significant and favors BKM+. Its running time is almost constant regardless of whether the focus is on high clustering quality or balance quality. The processing time of RKM becomes significantly higher when the focus is shifted towards the clustering quality.

The results for the three real-world data sets $\mathsf{user}$ $\mathsf{knowledge}$, $\mathsf{vowel}$ $\mathsf{recognition}$ and $\mathsf{ionosphere}$ are summarized in Figures 8, 9 and 10. The results are mostly consistent with that of the artificial data sets. When the focus is on the balance their results are almost identical. However, when the focus shifts towards optimizing the clustering quality, BKM+ produces better clusterings. $\mathsf{Ionosphere}$ is an exception where RKM provides better results in $\mathrm{SSE}$ for most parts of the scale. Also, the speed advantage of BKM+ almost disappears with this data set due to its higher dimension.

Finally, the main results are summarized in Table 2 by fixing $\mathrm{N}_\mathrm{entro}$ to be about $0.999$. At this point, BKM+ provides slightly lower $\mathrm{SSE}$-values ($0.63%$ on average) with a faster running time ($77.46%$ on average).

6.3.   Impact of the parameters

The Algorithm 1 requires setting two tuning parameters, the partly remaining fraction $c$, which determines the fraction of a data point that belongs to its old cluster during its assignment, and the increasing penalty factor $f$ by which the minimum penalty that is necessary in the next iteration in order to make a data point change to a smaller cluster is multiplied. To analyse the impact of these parameters we applied the algorithm to data sets $\mathsf{S1}$, $\mathsf{A3}$ and $\mathsf{wine}$.

The results (Figures 11-13) show that the recommended values for $f$ ($1.01-1.10$) and $c$ ($0.15$) work well for all tested datasets and that the algorithm is not very sensitive for the selection of these parameters. Setting $f$ to a smaller value can improve the MSE of the result with the cost of an increase in processing time.

7.   Discussion

A problem that arises when RKM is used with $\mathrm{SDCS}$ or $\mathrm{N}_\mathrm{entro}$ is the difficulty of finding an appropriate value for the balance parameter $\lambda$ since it is not possible to predict the resulting balance quality. The recommended range of values given by the authors ^[8] only fits some data sets. Most data sets require significantly higher values for $\lambda$ and then the only way to find a suitable range is by trial-and-error. Besides, RKM tends to produce clusterings that are optimizable with respect to both the clustering and the balance quality if $\lambda$ is chosen too small.

In this sense, BKM+ is much easier to handle because the resulting balance degree does not depend on a parameter $\lambda$, but only on the point in time at which the algorithm stops increasing the penalty term. A clustering of a desired balance degree can easily be obtained by using the balance criterion as the termination criterion.

The experimental results also allows us to draw conclusions about the beneficial application of the proposed algorithm. First, the algorithm cannot compete with the other clustering algorithms in terms of the clustering quality when the focus is set on balance. It is not made for this because whenever the last clusters are resolved by shifting data points from larger to smaller clusters, there are always overlapping clusters. Therefore, it is not advisable to use this algorithm as a hard-balanced clustering algorithm even though this is possible.

However, the proposed algorithm has its strengths when it comes to soft-balanced clustering. Especially when the resulting clustering should match a certain balance requirement or the data set is not well-known in terms of its balance behavior (in the sense that its balance in the case of an optimal clustering is unknown), this algorithm is much easier to handle than an algorithm using a balance parameter $\lambda$. Moreover, in the soft-balanced case, it also has a shorter running time on most data sets. Therefore, it is advisable to use the proposed algorithm as a soft-balanced clustering algorithm, particularly when a specific balance criterion has to be achieved or the data set is rather unknown in terms of its balance behavior.

The algorithm provides a good trade-off between cluster size balance and clustering quality. However, the algorithm should not be iterated so far that the distances would not matter anymore. Otherwise, it is possible to get a perfectly balanced clustering solution while having some less meaningful clusters. The assignments from the previous iterations will keep the solution mostly meaningful but the case with the Unbalance dataset shows that the result is not perfect if iterated too long. Other $k$-means-based balance-constrained clustering algorithms are likely to have the same problem. In this regard, there is still room for further improvement. Swap-based algorithms have been previously used to overcome such problems of $k$-means. For example, problems of classical $k$-means mostly disappeared by using random swap ^[45], clustering graphs by M-algorithm ^[46] and clustering sets by k-swaps algorithm ^[47]. The same approach might be worth considering for the balanced $k$-means as well. This is a point of future research.

The calculation of the scale parameter may not be the most elegant, but it at least guarantees convergence. If no point moves in one iteration the function guarantees that at least one point will move in the next iteration. In each iteration, the objective function is locally optimized for the given balance, but the balance requirement keeps increasing during the iterations.

The main difference to other balanced-drive algorithms is that we provide explicit balance requirement, which is set beforehand. We have an adaptive objective function that keeps changing toward the final (predefined) balance. Other algorithms use indirect parameters without knowing the final balance beforehand. It will be known only after the algorithm completes and we have no direct control of it. In our algorithm, we set the desired balance explicitly as the termination criterion.

8.   Conclusions

We presented a balanced clustering algorithm based on the $k$-means algorithm which can be used for both soft-balanced and hard-balanced clustering. The main principle of the algorithm is an increasing penalty term, that is added to the assignment function of the standard $k$-means algorithm. The penalty term of a cluster is the larger the more data points a cluster contains. This way, smaller clusters are favored when assigning the data points.

The main difference to similar methods following the approach of an additive bias in the assignment function of the standard $k$-means algorithm is the way the size of the penalty term is determined. While other algorithms use a constant factor by which the size of a cluster is multiplied to obtain the penalty term of the cluster ^[29,30], the proposed method uses a factor that increases with each iteration. Further, this factor is not defined by an explicit function but is computed anew in each iteration of the algorithm based on the current assignments and locations of the cluster centroids. We justified this additional computational effort by the individuality of each data set.

When used as a soft-balanced clustering algorithm, a characteristic of the proposed algorithm resulting from the increasing penalty term is the way how the trade-off between the clustering and the balance quality is determined. Instead of using a rather non-intuitive parameter $\lambda$ like many other soft-balanced clustering algorithms do ^[8,29,32], the resulting balance degree only depends on the point of termination. Therefore, in contrast to other soft-balanced clustering algorithms, this approach enables an explicit specification of the trade-off between clustering and balance performance.

In the experimental results, we compared the proposed method to the regularized $k$-means algorithm (RKM) ^[8] and the balanced $k$-means algorithm (BKM) ^[7]. When testing the hard-balanced version of the proposed algorithm, the results were equal to both RKM and BKM in terms of the clustering quality. Regarding the running time, the proposed algorithm is somewhat faster than RKM and several orders of magnitude faster than BKM. For the largest dataset of 1.4 million points, it took only 19% of processing time compared to RKM and 8% of memory footprint.

In the soft-balanced case, no algorithm is always superior to the other one. In general, the proposed algorithm returns the better clusterings if the focus is primarily on optimizing the clustering quality, and RKM returns the better clusterings if the focus is shifted towards the balance quality. In terms of the running time, the proposed algorithm takes less time on almost all data sets.

Moreover, the already mentioned advantage of the proposed algorithm is that the trade-off between the clustering and the balance quality depends on the point of termination instead of a balance parameter $\lambda$ can also be seen in practice. When applying RKM, which uses this parameter to determine the resulting balance degree, there is always a risk of choosing $\lambda$ too small and obtaining a clustering that is still optimizable with respect to both the balance and the clustering quality. This situation does not occur when using the proposed algorithm, since the algorithm can always be continued to ensure that no following clustering is better than the returned one in terms of both the clustering and the balance performance.

Use of AI tools declaration

The author(s) declare(s) that they have not used Artificial Intelligence (AI) tools in the creation of this article.

Conflict of interest

The authors declare that there is no conflict of interest in this paper.