1 Introduction↩︎

Anticlustering is an NP-hard combinatorial optimization problem that consists of partitioning a set of objects into equal-sized groups called anticlusters such that the sum of distance weights between pairs of objects in the same anticluster is maximized. This is with the goal of achieving anticlusters whose objects are as dissimilar as possible and thereby representative of the entire set of objects. Achieving diversity within groups is the focus of applications from various fields including operations research ([1]–[8]), management science ([9]), psychology and social sciences ([10], [11]), bioinformatics ([12]), VLSI circuit design ([13], [14]), computer systems and memory management ([15]), and more recently machine learning ([16]).

Several anticlustering variants have been proposed in the literature that differ in a number of ways: how the objects are represented, as nodes in an edge-weighted graph or as feature vectors; how the distance weights are measured, as distance metrics or arbitrary weights; which objective is optimized, the most common objective being maximizing within-anticluster sum of weights, or alternatively maximizing the minimum distance weight between any two objects in the same anticluster; and which alternative constraints are considered, requiring each anticluster’s size to satisfy some lower and upper bounds instead of equal-size anticlusters or additional constraints for the case when objects are associated with categories, that ensure that each anticluster has the same number of objects of a given category.

The anticlustering problem has been studied under the name the balanced \(K\)-cut problem. The balanced \(K\)-cut problem consists of partitioning the nodes of a graph into \(K\) anticlusters each of which has at most \(\left\lceil N/K \right\rceil\) nodes, where \(N\) denotes the number of nodes in the graph. The objective is to minimize the sum of edge weights between the anticlusters (the cut cost). This objective function of the balanced cut problem is the complement of the anticlustering objective, since the weight of the edges in the cut is the total sum of weights of all edges minus the sum of the edge weights inside the anticlusters, which is the objective of the anticlustering problem, and thereby equivalent. The anticlustering problem was also studied under the name maximally diverse grouping problem (MDGP), e.g.@gallego2013tabu.

We focus here on anticlustering in Euclidean spaces, where objects are represented as feature vectors and distance weights are measured using squared Euclidean distances. The objective is to assign an equal number of objects to each anticluster so that the sum of pairwise squared Euclidean distances between objects within anticlusters is maximized. Euclidean anticlustering can be traced back to [17] and is now arguably the most widely-used variant of anticlustering in practice. Euclidean anticlustering is used in psychology and social sciences to create participant groups that are comparable and representative of the entire dataset ([11]). In biomedical research such as high-throughput sequencing, it is used to assign patient DNA and RNA samples to batches to limit batch effects (see [12]). In unsupervised learning, it is used to split datasets into representative subsets to help compute lower bounds for instances of the minimum sum-of-squares clustering problem (see [18]). In supervised learning, it is used in cross-validation to create representative folds that support reliable model evaluation (see [11]), and in neural network training to form mini-batches for stochastic gradient descent, improving model generalization and convergence (see [19]–[21]). These recent applications in machine learning involve very large instances of Euclidean anticlustering with millions of objects and thousands of anticlusters. Although anticlustering is often considered easier on large datasets because random partitions are more likely to produce reasonable solutions (see [11]), this holds only when the number of anticlusters is small. The deterioration of the quality of random partitions with increasing number of anticlusters is clearly apparent in the empirical study here. Therefore random partitions, which are used in practice for applications such as mini-batch generation for neural network training, often provide low-quality solutions, creating a need for alternative anticlustering algorithms.

Various exact and heuristic methods have been developed for anticlustering. Exact methods are primarily based on mixed-integer programming formulations and are limited to small instances, solving problems with up to about 100 objects [5], [7], [11], [22], [23]. For larger instances, numerous heuristics have been introduced. [24] propose approximation algorithms for instances in which anticlusters contain exactly three or four objects. These algorithms run in cubic time in the number of objects and are therefore not suitable for large-scale applications. For metric spaces, [25], [26] propose approximation algorithms for anticlustering with prescribed, not necessarily equal, anticluster sizes. These algorithms have improved running times compared to the algorithms of [24]. Since these algorithms require all pairwise distances between objects as an input, when applied to Euclidean anticlustering, this limits their scalability. Other heuristics which require the complete distance matrix as input when used for Euclidean anticlustering face the same scalability issue (see [3], [4], [27], [28]). Several greedy constructive methods for anticlustering have been proposed in the context of mini-batch generation for training deep neural networks (see [19]–[21]). These methods generate mini-batches that enable faster convergence and higher neural network accuracy, however, they remain computationally expensive, requiring hours of running time for processing standard image datasets such as ImageNet. Many state-of-the-art anticlustering heuristics are exchange-based (see [11]). Such methods start from a random partition and iteratively improve it by exchanging pairs of objects from different anticlusters. The default method is to select an object and evaluate all pairwise exchanges between the selected object and objects from other anticlusters. The exchange that achieves the largest improvement in the objective value is performed. The process terminates when the exchange process has been repeated for each object. This default method is computationally prohibitive and the most-scalable methods restrict the number or the type of permitted exchanges. The leading exchange-based methods are available in the R package called anticlust (see [11]).

We introduce here a novel heuristic for Euclidean anticlustering, the Assignment-Based Anticlustering (ABA) algorithm. The ABA algorithm is a constructive heuristic that builds a solution with a single pass over the objects. It solves a series of assignment problems that assign batches of objects to anticlusters. The batches are generated from a ranked sequence of objects in terms of their distance to the global centroid of the dataset, where the centroid of a set of vectors is the vector of the average entries. The sequence is broken down into subsequences (batches) of the first \(K\) objects, the next \(K\) objects, and so forth. The objects of the first batch are the initial singleton anticlusters. To assign the \(K\) objects from the next batch, we solve the maximum weight assignment of the \(K\) objects to the \(K\) incumbent anticlusters. The weights are the distances (squared Euclidean) between the objects in the batch and the centroids of the incumbent anticlusters. After each batch assignment, the centroids of anticlusters are updated. Note that the last batch could be of size less than \(K\).

Some features of ABAmake it very efficient. Firstly, each object is assigned only once to its anticluster. Secondly, ABAcomputes the distance of each object in a batch to the centroid of the candidate anticlusters, instead of computing the distances to all objects in the anticlusters. ABAalso delivers solutions with desirable statistical properties. One desirable property is anticluster similarity, i.e., that the anticlusters are similar to each other in terms of mean and variance of the distances within the anticlusters (see [5], [29]). The assignments of ABAguarantee that there is exactly one object of each batch in each resulting anticluster, except maybe for the last batch. For centrality defined as the distance to the global centroid of the dataset, we note that the objects in each batch have similar centralities. ABAtherefore delivers solutions in which every anticluster has a representation of the entire range of centralities. ABA is shown in our experimental study to significantly outperform the other methods in terms of this anticluster similarity.

In addition to the base variant of ABAdescribed above, we introduce here two other variants: ABAfor anticlustering with categories and ABAwith a hierarchical decomposition strategy. Anticlustering with categories is an extension of the anticlustering problem where objects are associated with categories and each category must be equally represented in every anticluster (see [11], [18]). ABAwith a hierarchical decomposition strategy is a variant designed for very large-scale instances, which achieves drastic speedups with minor effect on the quality of the solution.

For the special case of anticlusters of size two, the Euclidean anticlustering problem is equivalent to the Euclidean maximum-weight non-bipartite matching problem. For this case, the work in [30] introduces a variant of ABA, ABA-matching, that is based on different sequencing of the objects. This variant was shown in [30] to outperform state-of-the-art algorithms for non-bipartite matching in terms of the trade-off between running time and quality of solution. Compared to exact algorithms, ABA-matching delivers almost optimal solutions, at worst \(1.7\%\) off, while offering very fast running times, whereas exact algorithms fail to deliver a solution within one hour of running time for the larger datasets. Also compared to heuristics, ABA-matching delivers consistently better quality of solutions and much faster running times.

To summarize, our contributions here are:

1. The introduction of the highly-scalable assignment-based algorithm (ABA) for the anticlustering problem.

2. Devising a variant of ABAfor anticlustering with categories, which achieves superior results compared to leading methods of [18] and [11].

3. For very large-scale datasets and very large values of \(K\) (e.g., \(K=100{,}000\)), we propose a variant of ABAthat employs a hierarchical decomposition strategy resulting in drastically reduced running times while maintaining high solution quality.

4. We provide the most comprehensive computational study of anticlustering algorithms to date, using a broad spectrum of published datasets.

5. It is demonstrated empirically that the ABA algorithm outperforms the leading exchange-based anticlustering methods in both solution quality and running time. Unlike existing methods, ABAalso scales to very large instances with millions of objects and thousands of anticlusters within seconds to minutes.

6. We generate new insights about the performance of random partitioning, that its performance deteriorates with smaller size anticlusters. This poor performance trend applies also to all benchmark algorithms tested here.

7. For the extensively studied anticlustering problem under the name balanced \(K\)-cut, ABA is shown here to be very effective for the Euclidean case. In particular, it achieves superior results compared to the state-of-the-art METISmethod in terms of both solution quality and running time.

8. It is shown that the design of ABAis such that it not only delivers on the anticlustering objective, but also on the anticluster similarity objective. In all experiments, ABAconsistently delivers substantially higher anticluster similarity than the benchmark algorithms.

The remainder of the paper is organized as follows. Section 2 formalizes the anticlustering problem and introduces the notation used throughout. Section 3 reviews existing algorithms for Euclidean anticlustering and related problems. Section 4 presents the Assignment-Based Anticlustering (ABA) algorithm, including its base variant; anticlustering with categories; the hierarchical decomposition strategy; and complexity analysis. Section 5 reports our experimental results. Section 6 concludes and outlines future research directions.

2 Problem Description↩︎

Let \(G=(V, E)\) be an undirected, weighted graph with \(V=\{1, \ldots, N\}\) the set of nodes (objects), \(E \subseteq \{ \{i, i'\}: i < i', i, i' \in V\}\) the set of edges, and edge weights \(w_{ii'}\geq0\) representing dissimilarities between nodes \(i\) and \(i'\). The anticlustering problem consists of partitioning the set of nodes into \(K\) groups (anticlusters) of equal size such that the sum of edge weights within each group is maximized (see [17]). The problem is NP-hard because even the case of partitioning into two equal-sized groups is at least as hard as the balanced cut problem (see [31]). In this work, we focus on the most common variant, where objects are points in a \(D\)-dimensional Euclidean space and pairwise dissimilarities are defined by squared Euclidean distances.

Formally, the anticlustering problem we study can be described as follows. Given a dataset of \(N\) objects \({\mathcal{X}}=\{\boldsymbol{x}_1, \ldots, \boldsymbol{x}_N\}\) with \(D\) features, where \(\boldsymbol{x}_i=[x_{i1}, \ldots, x_{iD}] \in \mathbb{R}^D\) is the \(i\)-th object, and \(x_{id}\) is the value of the \(d\)-th feature of this \(i\)-th object. Let \({\mathcal{N}} = \{1,\ldots, N\}\) denote the set of object indices. The problem is to find a partition \(\mathcal{C}=\{\mathcal{C}_1, \ldots, \mathcal{C}_K\}\) of the objects into \(K\) anticlusters of “approximately” equal size such that the total sum of squared Euclidean distances between objects within the same anticluster is maximized. Here we interpret “approximately” equal size as sizes that are strictly less than one unit away from the average size (\(N/K\)). Let \(\mathcal{K} = \{1, \ldots, K\}\) denote the set of anticluster indices, \(\mathcal{C}_k\) the set of object indices in anticluster \(k\), and \(d(i, i') = \|\boldsymbol{x}_i - \boldsymbol{x}_{i'}\|_2^2\) the squared Euclidean distance between objects \(i\) and \(i'\). With this notation, the Euclidean anticlustering problem (EA) can be formulated as follows:

\[\text{(EA)}\; \left\{ \begin{align} \max_{\mathcal{C}} \quad & W(\mathcal{C}) = \sum_{k \in \mathcal{K}} \sum_{i,i' \in \mathcal{C}_k,\, i<i'} d(i,i') & (1) \\[4pt] \text{s.t.} \quad & \lfloor N / K \rfloor \le |\mathcal{C}_k| \le \lceil N / K \rceil \quad (k \in \mathcal{K}) & (2) \\[4pt] & \bigcup_{k \in \mathcal{K}} \mathcal{C}_k = \mathcal{N} & (3) \\[4pt] & \mathcal{C}_k \cap \mathcal{C}_{k'} = \emptyset \quad (k, k' \in \mathcal{K},\, k < k') & (4) \end{align} \right.\]

The objective function (1) is the sum of pairwise squared Euclidean distances between objects assigned to the same anticluster. We refer to the objective function value as the diversity \(W(\mathcal{C})\) of the anticlustering solution \(\mathcal{C}\). Constraints (2) ensure that the size of two anticlusters differ by at most one. Constraints (3) and (4) ensure that every object is assigned to exactly one anticluster.

The Euclidean anticlustering problem with categories (EAc) is an extension of the Euclidean anticlustering where each object is associated with a category \(g\) from a given set of categories \(\mathcal{G}=\{1, \ldots, G\}\). Let \(\mathcal{N}_g = \{i \in \mathcal{N}| \text{category}(i) = g\}\) be the indices of the objects that belong to category \(g \in \mathcal{G}\). With this additional notation, the Euclidean anticlustering problem with categories (EAc) is formulated as follows:

\[\text{(EAc)}\; \left\{ \begin{align} \max_{\mathcal{C}} \quad & W(\mathcal{C}) \\[4pt] \text{s.t.}\quad & (2), (3), (4) \\[4pt] & \displaystyle \left\lfloor \frac{|\mathcal{N}_g|}{K} \right\rfloor \le \big|\mathcal{C}_k \cap \mathcal{N}_g\big| \quad (k\in\mathcal{K}, g\in\mathcal{G}) & (5)\\ & \displaystyle \big|\mathcal{C}_k \cap \mathcal{N}_g\big| \le \left\lceil \frac{|\mathcal{N}_g|}{K} \right\rceil \quad (k\in\mathcal{K}, g\in\mathcal{G}) & (6) \\ \end{align} \right. \label{form:A95categories}\tag{1}\]

In this extended formulation, constraints (5) and (6) ensure that for each category \(g \in \mathcal{G}\), the number of objects belonging to category \(g\) differs by at most one object between each pair of anticlusters. Specifically, the number of objects from category \(g\) assigned to any anticluster \(\mathcal{C}_k\) is constrained to lie between \(\left\lfloor |\mathcal{N}_g| / K \right\rfloor\) and \(\left\lceil |\mathcal{N}_g| / K \right\rceil\), so that all anticlusters represent the overall category distribution.

3 Literature Review↩︎

In this section, we review existing algorithms for the Euclidean anticlustering or closely related problems. Section 3.1 discusses exact approaches and Section 3.2 reviews heuristic approaches.

3.1 Exact Approaches↩︎

Although there are no exact approaches developed specifically for Euclidean anticlustering, the general anticlustering methods obviously apply for that case. [22] used a quadratic integer programming formulation for the anticlustering problem and a variant allowing for the size of each anticluster to be constrained by an upper and lower bound. In their paper, the authors refer to the anticlustering problem under the name maximally diverse grouping problem (MDGP).

[32] introduced a linear integer programming formulation for a related clustering problem. This formulation was extended and applied to anticlustering by [11].

[5] studied the anticlustering problem with few features in which dissimilarities are computed using the Manhattan distance (\(L_1\)). For special cases, such as when \(N/K \leq 3\) and a single feature, the problem is shown to be polynomial-time solvable. For a single feature and non-negative integer feature values, the problem is proved to be weakly NP-hard. However, any slight generalization, including allowing the feature values to be rational, renders the problem to be strongly NP-hard. The author also presents an integer programming formulation that is tested for instances with one feature or two features. In a follow-up study, [23] compared a variant of this formulation to the formulations of [22] and [11] and found that it performs best for \(L_1\) distances. [7] extended this work and proposed a two-step exact mixed-integer programming approach for anticlustering with \(L_1\) distances, reporting optimal solutions for instances on one feature, two features, and five features, with up to \(200\) objects. [6] demonstrated that an enhanced integer programming formulation solves the problem with single feature, integer feature values, and \(L_1\) distances, for instances with up to \(6{,}000\) objects to optimality within reasonable computation times (less than 10 minutes).

Exact approaches were also proposed for other variants of anticlustering. For example, [33] proposed an exact approach for an anticlustering problem where the goal is to maximize the minimum distance between any two objects within the same anticluster (maximum dispersion). The approach is based on multiple calls for solving the \(K\)-coloring problem. Another variant, introduced by [10], is the bicriterion anticlustering problem. Bicriterion anticlustering is anticlustering that seeks to maximize the sum of distances within the anticlusters subject to the maximum dispersion exceeding a user-specified lower bound. [33] showed how an extension of the exact approach for maximum dispersion is effective also for the bicriterion anticlustering problem.

All the exact approaches discussed above work only for small instances, which is far below the scale of practical instances.

3.2 Heuristic Approaches↩︎

[17] introduced Euclidean anticlustering where dissimilarity is measured by squared Euclidean distances with specified number of anticlusters but without anticluster-size constraints. The author introduced a move-based heuristic that moves a single object from one anticluster to another. At any iteration, this results in a feasible solution because there are no size constraints. [17] also observed that random partitions do not work well.

[1] proposed a heuristic for anticlustering, with equal-sized anticlusters, that considers pairwise exchanges of objects between anticlusters instead of single-object moves. The heuristic first randomly assigns objects to anticlusters, and then for one object at a time considers exchanges with all objects from other anticlusters. The exchange that improves the objective function the most is executed. Note that an exchange is only conducted if it improves the objective function. The exchange procedure is terminated when there is no improving exchange for all objects.

[11] presented two types of exchange-based heuristics. The first type is the exchange-based heuristic of [1] which uses by default a different stopping criterion, i.e., it stops after a single pass of exchanges through all objects. The second type is an exchange-based heuristic called fast-anticlustering that is specifically designed for large instances of Euclidean anticlustering. It works in the same way as the standard exchange-based heuristic, but considers only a user-defined number of exchange partners for each object and uses a different formulation of the objective function, which only considers the distances between the anticluster centroids and the global centroid instead of all distances between objects and the centroid of their assigned anticluster. The default behavior of fast-anticlustering is to generate exchange partners by using a nearest neighbor search. Using more exchange partners tends to improve the quality of the solution, but increases running time. To avoid running the nearest neighbor search, the exchange partners can be chosen randomly. Selecting exchange partners randomly is significantly faster. An advantage of exchange-based heuristics is that additional constraints can easily be integrated into the exchange process. As an example, exchange-based heuristics can be applied with minor modifications to Euclidean anticlustering with categories (see Section 2), and anticlustering with must-link and cannot-link constraints between pairs of objects.

As noted by [29] the definition of anticlustering does not fully capture the needs in practical applications. The objective of anticlustering encourages anticlusters that have centroids very close to the global centroid. For instance, two anticlusters that have objects arranged along concentric circles of very different radii would be an optimal solution for an anticlustering problem. However, their statistical distribution properties are very different. In most practical applications, the anticlusters should have similar statistical properties. That is, the sum of pairwise distances within all anticlusters should be approximately equal - achieving anticluster similarity. This secondary objective of anticluster similarity was addressed by [29] for tabular input data. They proposed to use the exchange-based heuristic with adjusted input data that involves adding, for each feature, a list of statistical-moment features, e.g., variance, skewness, or kurtosis. Adding \(p\) additional statistical moments increases the dimension of the original feature space by a factor of \(p + 1\). This strategy’s significant increase of the dimensionality of the data leads to very high computational costs.

Numerous heuristics have been developed for anticlustering under the name maximally diverse grouping problem (MDGP): [3], [4], [22], [27], [34], and [28]. These heuristics are mainly based on metaheuristic frameworks such as tabu search, iterated local search, variable neighborhood search, and genetic algorithms. Among those metaheuristics, the method of [28] is reported to dominate the others in this group. This method of [28] is a population-based metaheuristic that is included in the R-package anticlust. For the anticlustering with Manhattan distance problem, [7] presented exact approaches, complexity study, and a number of heuristics. These heuristics are based on the case of a single feature that is then extended to account for multiple features.

Several approximation algorithms are applicable to Euclidean anticlustering. [24] proposed one-half approximation algorithms for special cases of the \(K\)-partition problem in which all partitions have size three (\(K=N/3\)) or four (\(K=N/4\)). [25] proposed an approximation algorithm for the problem with prescribed, not necessarily equal, anticluster sizes and distances that satisfy the the triangular inequality. Their algorithm offers improved running time compared to the algorithm of [24] and obtains an approximation ratio of 0.375. [26] introduced an improved approximation algorithm for the same problem, whose approximation ratio is \((\frac{1}{2} - \frac{3}{q})\), where \(q\) is the size of the smallest anticluster.

Other types of anticlustering heuristics have been developed in the context of mini-batch construction for machine learning. [20] proposed a method to generate representative, equal-size mini-batches for training neural networks. Their approach uses a greedy algorithm that starts with empty mini-batches and iteratively selects the least representative one. Representativeness of a set \(S\) is measured as the sum of distances of all objects not in the set to their nearest object in set \(S\). From the set of unassigned objects, the algorithm assigns the object that improves the representativeness of the selected mini-batch the most, repeating this process until all mini-batches reach the desired size. The authors further introduced a hierarchical variant of the algorithm to reduce memory and computational costs, and show for the datasets CIFAR-100 and ImageNet, that the resulting mini-batch sequences consistently outperform random partitioning. However, the overall running time of the approach is dominated by the cost of constructing the distance matrix. This is reported, in [20], to require approximately \(3\) minutes for CIFAR-100 and almost \(90\) minutes for ImageNet on a 16-core CPU.

[21] proposed another approach for generating mini-batches. Their approach is based on integer programming that is relaxed to linear programming, the solution of which is rounded. This approach is computationally expensive since the linear program must be solved for each mini-batch.

The leading algorithm for anticlustering as balanced \(K\)-cut is the multilevel graph partitioning algorithm of [35], which is implemented in the well-known METISsoftware. The algorithm reduces the size of the graph by collapsing vertices and edges, then partitions the smaller graph, and then “uncoarsens" it to construct a partition for the original graph.

4 The New Assignment-Based Anticlustering (ABA) Algorithm↩︎

The ABA algorithm constructs an anticlustering solution by iteratively solving an assignment problem of \(K\) objects in a batch to the \(K\) anticlusters. The key idea in creating the batches is first to produce a ranked list of the objects in decreasing distance to the global centroid and then to create \(\left\lceil N/K \right\rceil\) batches formed by the subsequences: the first \(K\) objects, the next \(K\) objects, etc.with the last batch possibly including fewer than \(K\) objects. Each object of the first batch forms an initial singleton anticluster. In each iteration, the algorithm assigns the next batch of \(K\) objects (or possibly less for the last batch) and assigns it to anticlusters such that the total squared Euclidean distance between the objects and the centroids of the anticlusters is maximized. The centroids of the anticlusters are then updated based on the new assignments. With increasing number of iterations, this strategy tends to move the centroids of the anticlusters towards the global centroid of the data set. Since the final positions of the anticluster centroids tend to be close to the global centroid, the proposed batch selection strategy will usually result in anticlusters having similar distributions of distances between their objects and the respective anticluster centroid.

By representing anticlusters through their centroids, the ABA algorithm takes advantage of the equivalence between maximizing the within-cluster sum of squares and the within-cluster variance (see Fact 1). This allows distances to be computed between objects and centroids rather than between pairs of objects, resulting in greater computational efficiency. The following well-known fact, Fact 1, establishes the equivalence between the sum of distances to the centroids of the respective anticlusters to the sum of squares of distances within the anticlusters. For completeness’ sake, the proof is provided in the appendix.

In Section 4.1, we first describe the base variant of the algorithm. In Section 4.2, we introduce a variant of the ABA algorithm that can be applied to the Euclidean anticlustering problem with categories (see Section 2). In Section 4.3, we present a hierarchical decomposition strategy that substantially speeds up the ABA algorithm, in particular when \(K\) is large. Finally, in Section 4.4, we discuss the running time complexity of the ABA algorithm.

4.1 Base Variant of the ABA Algorithm↩︎

Algorithm 1 provides the pseudocode of the ABA algorithm. The ABA algorithm takes as input a dataset \({\mathcal{X}}=\{\boldsymbol{x}_1, \ldots, \boldsymbol{x}_N\}\) consisting of \(N\) objects, each represented by a \(D\)-dimensional feature vector, and a parameter \(K\) which specifies the desired number of anticlusters. The algorithm starts by computing the squared Euclidean distances between each object \(\boldsymbol{x}_i\) with \(i=1,\ldots,N\) and the centroid of the dataset \(\boldsymbol{\mu}=\frac{1}{N} \sum_{i=1,\ldots,N} \boldsymbol{x}_i\). The algorithm then creates a list \(\mathcal{N}^{\downarrow}\) which contains the indices of the objects, sorted by their squared Euclidean distance to the global centroid \(\boldsymbol{\mu}\) in descending order. The list \(\mathcal{N}^{\downarrow}\) is split into \(B=\lceil N / K \rceil\) batches. The first batch \(\mathcal{B}_1\) contains the first \(K\) indices of \(\mathcal{N}^{\downarrow}\), the batch \(\mathcal{B}_2\) the next \(K\), and so on. Thus, all batches contain \(K\) indices, with the possible exception of the last batch \(\mathcal{B}_B\) if \(N\) is not divisible by \(K\). Next, the algorithm assigns each object whose index is contained in \(\mathcal{B}_1\) to one of the \(K\) anticlusters and initializes the centroid of each anticluster with the feature vector of its assigned object. The remaining \(B-1\) batches are processed as follows. Given a batch \(\mathcal{B}_b\), a cost matrix of size \(|\mathcal{B}_b| \times K\) is computed where each entry \(j, k\) \(j=1, \ldots, |\mathcal{B}_b|\) and \(k=1, \ldots, K\) corresponds to the squared Euclidean distance between the corresponding object \(\boldsymbol{x}_{\mathcal{B}_b[j]}\) and the corresponding centroid \(\boldsymbol{\mu}_k\) of anticluster \(k\). The cost matrix is passed to a linear assignment problem solver that determines the maximal cost assignment. Based on the new assignments, the centroids of the anticlusters are updated. After the processing of all batches, the ABA algorithm returns a vector of length \(N\) that contains for each object the label (index) of the anticluster to which it was assigned.

4.2 The ABA Algorithm With Categories↩︎

We also propose a variant of the ABA algorithm for the anticlustering problem with categories (see Section 2). The base variant of the ABA algorithm requires two modifications to account for the additional constraint that all objects of the same category need to be evenly distributed across anticlusters. First, the objects in the sorted list \(\mathcal{N}^{\downarrow}\) need to be rearranged as follows. The list is divided into \(G\) sublists \(\mathcal{N}^{\downarrow}_g\) (\(g \in G\)), where each \(\mathcal{N}^{\downarrow}_g\) contains all objects belonging to category \(g\), preserving their original order. Each \(\mathcal{N}^{\downarrow}_g\) is then partitioned into consecutive blocks of size \(K\). If the number of objects in \(\mathcal{N}^{\downarrow}_g\) is not a multiple of \(K\), the final block contains fewer than \(K\) objects. The rearranged list is obtained by sequentially concatenating all full (\(K\)-sized) blocks from the \(G\) lists in an alternating fashion, always selecting the next available block according to the sorting. The remaining (incomplete) blocks are appended at the end in the same alternating order. Figure 2 illustrates for an example with \(N=22\) objects and \(K=3\) anticlusters how to construct the rearranged list \(\mathcal{N}^{\downarrow}_\text{new}\). Second, when splitting the rearranged list \(\mathcal{N}^{\downarrow}_\text{new}\) into batches \(\mathcal{B}_1\) to \(\mathcal{B}_B\), the last batches may contain objects that belong to different categories. Because of this, we need to keep track of the number of objects of category \(g \in G\) assigned to each anticluster \(k \in K\) during the iterations. When assigning object \(i\) to anticluster \(k\) would violate the corresponding upper bound \(\left\lceil \frac{|\mathcal{N}_g|}{K} \right\rceil\), the cost matrix entry that corresponds to the distance between \(\boldsymbol{x}_i\) and \(\boldsymbol{\mu}_k\) must be set to a sufficiently large negative value, such as the negative of the maximum entry in the cost matrix, before solving the assignment problem to ensure that the upper bound is never exceeded.

4.3 Computational Speed-Up with Hierarchical Decomposition↩︎

The size of the assignment problems solved during the execution of the ABA algorithm depends on \(K\). For large-scale instances with large values of \(K\), solving the assignment problems can become computationally prohibitive. For such instances, we propose a hierarchical decomposition strategy that achieves substantial reductions in running time while maintaining high solution quality. The idea is to construct the anticlusters in a hierarchical manner, i.e., first create \(K_1\) anticlusters and then subdivide each of the \(K_1\) anticlusters again into \(K_2\) anticlusters. This will yield \(K_1 \times K_2\) anticlusters. The number of levels \(L\) and the values \(K_1, K_2, \ldots, K_L\) can be specified by the user. As stated in Lemma 1, a balanced decomposition in which the values of \(K_{\ell}\) are as similar as possible, will deliver the lowest complexity for \(L\) levels. We also observe experimentally, in Figure 6, that such a choice does not noticeably diminish solution quality. Note that the subproblems that result from the decomposition can be solved in parallel, leading to further improvements in the computational speed of the algorithm on multi-core machines. Figure 3 illustrates the hierarchical decomposition strategy based on an example with \(N=100\) objects and \(K=9\) anticlusters. The hierarchical decomposition strategy proposed above still guarantees that the sizes of the final anticlusters lie within the prescribed bounds \(\left\lfloor N/K \right\rfloor\) and \(\left\lceil N/K \right\rceil\). This follows because each split is balanced, meaning every resulting anticluster receives either the baseline number of objects or one additional object, and these additional objects are simply passed down the recursion tree. Since no split can introduce an imbalance larger than one object, the final anticluster sizes also differ by at most one object.

4.4 The Complexity of the ABA Algorithm and the Hierarchical Decomposition↩︎

The time complexity of the base variant of the ABA algorithm is determined by three main steps. First, computing the global centroid of the objects and their distances to this centroid requires \(O(ND)\) operations. Second, sorting the objects in decreasing order of their distance to the global centroid requires \(O(N \log N)\) time. Third, the algorithm solves \(\left\lceil N/K \right\rceil-1\) assignment problems using an implementation of the algorithm of [36] called LAPJV. Since each assignment problem requires \(O(K^3)\) operations, this step requires a total of \(O(\frac{N}{K}K^3) = O(NK^2)\) time. Hence, the overall time complexity of the ABA algorithm is \(O(ND) + O(N \log N) + O(NK^2) \text{ or } O\bigl(N(D + \log N + K^2)\bigr)\). Since the calls to LAPJV dominate the running time, the running time is \(O(NK^2)\). The time complexity is the same for the ABA algorithm with categories as the modifications with respect to the base variant do not change the overall time complexity.

We next discuss the complexity of the hierarchical decomposition. To illustrate the total complexity expression consider the example of a hierarchical decomposition with \(L=3\) levels and the choice of parameters \(K_1,K_2,K_3\). The complexity of ABAat each level is as follows:

• Level 1: ABAis applied once to the full instance with parameter \(K_1\), with complexity, \(T_1 = O(NK_1^2)\), producing \(K_1\) subproblems.

• Level 2: Each of the \(K_1\) subproblems here contains approximately \(N/K_1\) objects and is solved with parameter \(K_2\), partitioning each one of the \(K_1\) subproblems to \(K_2\) subproblems, for a total of \(K_1K_2\) subproblems. The total cost at this level is then \(T_2 = K_1 \cdot O\!\left(\frac{N}{K_1}K_2^2\right) = O(NK_2^2).\)

• Level 3: Each of the \(K_1K_2\) resulting subproblems contains approximately \(N/(K_1K_2)\) objects and is solved with parameter \(K_3\). The total cost at this level is, \(T_3 = K_1K_2 \cdot O\!\left(\frac{N}{K_1K_2}K_3^2\right) = O(NK_3^2).\)

Summing over all three levels yields \(T_{\mathrm{total}} = O\bigl(N(K_1^2 + K_2^2 + K_3^2)\bigr).\) Extrapolating from this \(3\)-level example, the complexity of the hierarchical decomposition with \(L\) levels and parameters \(K_1,\ldots ,K_L\) is \(T_\ell= O(NK_\ell^2)\) for level \(\ell =1,\ldots, L\). The total complexity is then \(\sum_{\ell=1}^{L} T_\ell = O\!\left(N\sum_{\ell=1}^{L} K_\ell^2\right).\) The lemma below states that the selection of equal parameter values for \(K_{\ell}\) minimizes the total complexity expression.

The proof of the following lemma is straightforward and therefore omitted.

5 Experimental Results and Analysis↩︎

In this section, we compare the performance of ABA with state-of-the-art algorithms in three experiments. First, we evaluate ABA against the state-of-the-art algorithm of [11] for large-scale anticlustering in Euclidean space. Second, we assess the effectiveness of the hierarchical decomposition strategy. Third, we compare ABA to METIS(see [35]), the leading software for the balanced \(K\)-cut problem. The section is organized as follows. Section 5.1 introduces the datasets, Section 5.2 presents the benchmark algorithms, and Sections 5.3, 5.4, and 5.5 report the experimental results. The results of an additional experiment on Euclidean anticlustering with categories, reported in the Electronic Companion on GitHub, show that ABA outperforms the algorithm of [18] in both solution quality and running time, and matches the solution quality of the algorithms from [11] while being substantially faster. We implemented the ABA algorithm in C++ and used the LAPJV algorithm for solving the assignment problems. Our C++ source code is available on GitHub. We also provide a Python implementation of the ABA algorithm on GitHub. All computations were executed on an HP workstation with two Intel Xeon CPUs with clock speed 3.30 GHz and 256 GB of RAM.

5.1 Datasets↩︎

We use a variety of datasets that differ in the number of objects (\(N\)), the number of features (\(D\)), and the data type (tabular or image). Table 1 lists each dataset along with its source. Besides datasets from prior anticlustering research, we include additional datasets commonly used in machine learning. We applied the following preprocessing steps. For datasets with categorical features, we encoded the categorical features as a set of binary features using a one-hot encoding scheme, creating one binary feature for each category. For datasets that included nonbinary features, we standardized all features by subtracting the mean and dividing by the standard deviation. Additional preprocessing was performed for specific datasets as described next. For the Travel dataset, we drop the User feature and remove objects with missing values. For the Npi dataset, we preprocessed the data in the same way as in [11], i.e., we removed objects with missing values and kept only the binary features representing the answers of the participants. For the Creditcard dataset, we leave out the ID feature. For the Census dataset, we drop the caseid feature. For the Plants dataset, we converted the original data into a binary matrix, with rows representing plants and columns representing states. An entry of one indicates that the plant occurs in the corresponding state. In the image datasets Cifar10, Mnist, Imagenet8, and Imagenet32, the features represent pixel intensities with one (grayscale) or three (RGB) values ranging from 0 to 255. As is commonly done with image data, we scaled the features by dividing them by 255 instead of standardizing them, bringing all values into the range [0,1]. Note that the Imagenet8 and Imagenet32 datasets are downsampled versions of the original ImageNet dataset, with image resolutions of 8\(\times\)​8 and 32\(\times\)​32 pixels, respectively. For the Finance dataset, we eliminated the features step, nameOrig, and nameDest.

For the additional experiment on Euclidean anticlustering with categories, reported in the Electronic Companion on GitHub, we use the datasets that were considered in [18]. These datasets are listed in Table 2. The same preprocessing steps as described above were applied to these datasets.

5.2 Benchmark Algorithms↩︎

The benchmark algorithms used in our experiments include the fast-anticlustering algorithm from the R package of [11], the default balanced \(K\)-cut algorithm from the METISsoftware package (see [35]), and a random partitioning procedure. In the additional experiment on Euclidean anticlustering with categories reported on GitHub, we also use the integer linear programming model of [18] as a benchmark algorithm. The R package anticlust of [11] includes exact integer programming algorithms or exchange heuristics. The exact algorithms are only able to solve small problem instances with up to 70 objects in acceptable running time and therefore are not tested here. From the two exchange-based heuristics available in the anticlust package, we use the heuristic called fast-anticlustering as this is the most scalable one. In [11], the fast-anticlustering algorithm is applied with 5 exchange partners determined by nearest neighbor search. We run it with the same settings and in addition with 5, 50, and 500 randomly generated exchange partners. To the best of our knowledge, the fast-anticlustering algorithm is the leading algorithm for large-scale anticlustering. We applied the balanced \(K\)-cut algorithm from the METISsoftware package with its default control parameter values. It requires an input file that specifies all neighbors for each node of the graph together with the corresponding edge weights as integers. The tests of METISversus ABA are described in Section 5.5. Table 3 lists each algorithm together with its abbreviation, full name, source publication, programming language, and a link to its source code.

8pt

5.3 Comparison to Leading Algorithms on Standard Anticlustering Problems↩︎

In this experiment, we compare the ABA algorithm with the fast-anticlustering algorithm of [11] using the 16 datasets from Table 1. For each of the 16 datasets, we generated multiple problem instances by varying the number of anticlusters \(K\). For the smallest dataset named Travel with less than \(N=10{,}000\) objects, we created six problem instances by setting \(K = \{2, 5, 50, 500, 1{,}000, 2{,}000\}\), for the other datasets with \(N=10{,}000\) or more objects, we created seven problem instances by setting \(K = \{2, 5, 50, 500, 1{,}000, 2{,}000, 5{,}000\}\). This yields a total of 111 problem instances. We applied fast-anticlustering with the same configuration as in [11], using 5 exchange partners determined via nearest-neighbor search (denoted P-N5). In addition, we applied fast-anticlustering with 5, 50, and 500 randomly chosen exchange partners (P-R5, P-R50, P-R500). As a baseline, we use random partitioning (Rand), which randomly permutes the objects and assigns them cyclically to \(K\) anticlusters. We use the objective function values and the running time as performance metrics. The ABA algorithm is deterministic, whereas the other algorithms are randomized and require a random seed. We therefore ran each benchmark algorithm three times per problem instance and report the average performance metrics. We stopped a run if a time limit of two hours has been reached. For large instances, we applied ABA with hierarchical decomposition. Table 4 specifies the settings we used for the hierarchical decomposition as a function of the number of objects (\(N\)) and the number of anticlusters (\(K\)). The detailed results for all 111 problem instances are available on GitHub. Due to limited space, we provide here a summary of the findings. First, we present the results for the Npi dataset with all values of \(K=\{2, 5, 50, 500, 1{,}000, 2{,}000, 5{,}000\}\). This dataset was also used in [11]. Then, we present results for all datasets with \(K=5\) and \(K=1{,}000\).

Table 5 presents the results for the Npi dataset. The first column lists the number of anticlusters \(K\). The second column reports the objective function values for the solutions obtained by the ABA algorithm (ofv ABA), computed here as the sum of squared Euclidean distances between the objects and their corresponding anticluster centroid. Columns 3–7 show the percentage deviation of the objective function values obtained by the benchmark algorithms from that of ABA. A negative deviation indicates that the ABA algorithm outperformed the respective algorithm. Column 8 gives the running time of the ABA algorithm in seconds, while columns 9–12 report the percentage deviations of the running time of the fast-anticlustering algorithms from that of ABA. A positive deviation indicates that the respective algorithm is slower than the ABA algorithm. The bottom row of the table reports the average values. For each instance (row), the best solution quality and the best running time are highlighted in bold. The main conclusions from Table 5 are that the ABA algorithm consistently provides the best solution quality and is substantially faster than the fast-anticlustering algorithms. For small values of \(K\), all tested algorithms deliver similar solution quality. For larger values of \(K\), however, the ABA algorithm provides substantial improvements in terms of solution quality. In particular, for \(K=5{,}000\), the ABA algorithm provides a solution that is, on average, more than 16% better than the solutions produced by P-N5 and more than 30% better than the solutions produced by random partitioning.

4.5pt

Table 6 presents the results for all datasets when \(K=5\). The structure of the table is similar to that of Table 5 only that the first three columns list the name of the dataset, the number of objects (\(N\)), and the number of features (\(D\)). A dash (—) means that the respective algorithm did not return a solution within the prescribed time limit of two hours in any of the three runs. To compute the average, the bottom row of the table, we exclude the dash-entries and take the average only across the entries where the respective algorithm computed a solution. From Table 6, we observe that the fast-anticlustering algorithms (P-N5, P-R5, P-R50, P-R500) do not find solutions for all instances within the two hours time limit. In contrast, the ABA algorithm produces solutions to all instances in less than a second or within a few seconds. Since \(K\) is small, all algorithms achieve comparable solution quality, although Rand performs slightly worse. However, ABA is substantially faster. While it produces the solution for each dataset in under a second or just a few seconds, P-N5, P-R5, P-R50, and P-R500 require considerably longer running times, with average running times up to three orders of magnitude longer than those of ABA.

4.5pt

For larger values of \(K\), the ABA algorithm outperforms the fast-anticlustering algorithms not only in terms of speed, but also in terms of solution quality. The outperformance in terms of solution quality becomes more pronounced with larger values of \(K\). Table 7 presents the results for all datasets when \(K=1{,}000\) and supports this conclusion.

4.7pt

A further analysis showed that the ABA algorithm produces solutions with high anticluster similarity, i.e., the anticlusters are very similar to each other in terms of diversity. We measured the diversity of an anticluster as the sum of squared distances between its assigned objects and its centroid. The benchmark approaches P-N5, P-R5, P-R50, P-R500, and Rand tend to produce anticlusters that are far less balanced in terms of diversity. To quantify the similarity of anticlusters within a solution, we compute, for each of the \(K\) anticlusters, the diversity, i.e., the sum of squared distances between the assigned objects and the corresponding centroid. Based on these \(K\) values, we then calculate two statistics, namely the standard deviation and the range (the difference between the maximum and minimum). Table 8 presents these statistics for all datasets and benchmark algorithms for \(K=5\). Columns 4 and 10 report for each dataset the standard deviation (sd) and the range (range) obtained with ABA , respectively. The columns 5–9 provide for each benchmark algorithm the percentage deviations from the standard deviations of ABA. Analogously, columns 11–15 provide for each benchmark algorithm the percentage deviations from the range values of ABA. Positive deviations indicate that the corresponding benchmark algorithm produced a solution with a higher standard deviation or larger range. From Table 8, we observe that the ABA algorithm consistently produces anticlusters with more balanced diversity. The same conclusion can be drawn for \(K = \{2, 50, 500, 1{,}000, 2{,}000, 5{,}000\}\) as can be seen in the corresponding tables on GitHub.

2.8pt

We observed the largest differences in terms of balanced diversity between the ABA algorithm and the benchmark algorithms for the image datasets Mnist, Cifar10, Imagenet8, and Imagenet32 when \(K\) is large. Figure 4 shows the distributions of the anticluster diversity values for the solutions obtained with ABA and P-R5 with \(K=2{,}000\). For the dataset Imagenet32, the P-R5 algorithm found no solution within the time limit of two hours. We therefore compare ABA and Rand for this dataset. The diversity distributions of ABA exhibit not only higher means, but also smaller spreads than the diversity distributions of P-R5 and Rand.

To further illustrate the balanced diversity of anticlusters produced by ABA, we looked at the distribution of distances within anticlusters. Figure 5 visualizes for the Travel dataset with \(K=50\) the distribution of distances within anticlusters for the solutions obtained by ABA and the benchmark algorithms. For each algorithm, 50 boxplots are shown, one for each anticluster. Each boxplot shows the distribution of distances between the objects and the centroid of the anticluster. The outliers have been removed for clarity. We can see that the ABA algorithm produces anticlusters with very similar distance distributions, whereas the benchmark algorithms yield anticlusters with highly varying distance distributions. The ABA algorithm produces anticlusters with similar distance distribution because it first sorts all objects by their distance to the global centroid and then splits them into batches of size \(K\). This ensures that the objects in each batch have similar distances to the global centroid and since anticluster centroids tend to be close to the global centroid in final solutions, each anticluster gets one object from each distance range.

5.4 Effectiveness of the Hierarchical Decomposition Strategy↩︎

The hierarchical decomposition strategy presented in Section 4.3 allows the ABA algorithm to compute high-quality solutions for large values of \(K\) in short running time. To illustrate the effectiveness of this strategy, we applied different hierarchical settings on the Imagenet32 dataset which has \(N=1{,}281{,}167\) objects and \(D=3{,}072\) features for \(K=5{,}000\). Figure 6 compares the running times and normalized objective function values for different two-level hierarchical strategies to the base variant of ABA that uses no hierarchical decomposition. With no hierarchical decomposition, the ABA algorithm requires more than 3,900 seconds to compute a solution. By applying hierarchical decomposition, the running time can be drastically reduced to 44.3 seconds with only a marginal deterioration in the objective function value (-0.013%). As observed experimentally in Figure 6, the quality of the solution is not noticeably affected by the selected decomposition of \(K\). However, the running times are drastically improved by choosing a decomposition where the values of \(K_\ell\) are as balanced as possible.

With hierarchical decomposition, the ABA algorithm can handle even much larger values of \(K\). To demonstrate this capability, we applied ABA with \(K = \{10{,}000, 20{,}000, 40{,}000, 80{,}000, 160{,}000, 320{,}000, 640{,}000\}\) to the Imagenet32 dataset which has \(N=1{,}281{,}167\) objects. Table 10 lists the running times and the objective function values for ABA. For these instances, we applied the ABA algorithm with the hierarchical decomposition settings provided in Table 9. The only benchmark approach that was able to produce solutions within a time limit of two hours was random partitioning (Rand). We can see from Table 10 that ABA clearly outperforms Rand in terms of solution quality for all considered values of \(K\). The absolute percentage deviation of the objective function values of Rand from those of ABA increases with larger values of \(K\). The ABA algorithm obtains solutions that are over 30% better than those of Rand for \(K=640{,}000\).

16pt

5.5 Application of ABA to Balanced \(K\)-cut↩︎

Recall that the balanced \(K\)-cut problem consists of partitioning the nodes of a graph into \(K\) equal-sized anticlusters such that the sum of edge weights between the anticlusters (the cut cost) is minimized. In the case of tabular data, where the underlying graph is complete and the edge weights represent squared Euclidean distances between the corresponding objects (or data points), minimizing the cut cost corresponds to maximizing the within-anticluster sum of squared distances. Because of that equivalence, we can use the ABA algorithm for the balanced \(K\)-cut problem of tabular data. In this section, we compare the ABA algorithm to METIS, the state-of-the-art algorithm for solving balanced \(K\)-cut problems. The METISalgorithm is applicable to a more general setup than Euclidean anticlustering – to any general graph. It takes as input the graph representation in the form of an adjacency list with edge weights. As a result applying METISto Euclidean anticlustering requires to create a representation of a complete graph. Another requirement of METISis that edge weights are integer. In order to address that, we multiply the squared Euclidean distances by a factor of \(1{,}000\) and rounded the resulting values to the nearest integer.

We apply METIShere with its default parameter settings, except that we set the parameter ufactor to its minimum value of one. The parameter ufactor controls the maximum allowed deviation of anticluster sizes from the target size (\(N/K\)). Specifically, a value of \(x\) for parameter ufactor allows deviations of up to \(x/1000\), where \(x\) must be larger or equal to one and integer. For small values of ufactor, we found that METISoccasionally fails to return a solution. In such cases, we increased ufactor by one and reran METIS. This process was repeated until a solution was found or a time limit of \(7{,}200\) seconds was reached. Because constructing the graph representation for METISand running METISon it is computationally expensive and memory-intensive, we limited this experiment to datasets with at most \(30{,}000\) objects from Table 1 and Table 2. For datasets with fewer than \(10{,}000\) objects, we tested \(K=\{2, 5, 50, 500, 1{,}000, 2{,}000\}\). For datasets with at least \(10{,}000\) objects, we additionally tested \(K=5{,}000\). Random partitioning (Rand) again served as a baseline. ABAis applied in this experiment without the hierarchical decomposition strategy.

Table 11 reports the results. Note that for several combinations of datasets and values of \(K\), METISreturned anticlusters whose sizes differed by more than one object, even when ufactor was set to its minimum value. Because comparing objective values is only meaningful when the anticluster size constraints are satisfied, these instances are excluded from Table 11 (the complete results are provided in the Electronic Companion to this paper on GitHub). The first four columns of Table 11 list the dataset name, the number of objects (\(N\)), the number of features (\(D\)), and the number of anticlusters (\(K\)). Column 5 reports the within-anticluster sum of squared distances (\(W(\mathcal{C})\)) obtained by ABA. Columns 6 and 7 report the percentage deviation of the \(W(\mathcal{C})\) values obtained by the benchmark algorithms from that of ABA. Negative values indicate that ABAperforms better. Columns 8 and 9 give the total running time of ABAand METISin seconds, respectively. Column 9 lists separately the running time required to construct the METISinput graph, i.e., the adjacency list. This running time is included in the total running time reported in column 9. Columns 10 and 11 report the ratio between the sizes of the smallest and largest anticlusters for ABAand METIS, respectively. This ratio equals 100% when all anticlusters have the same size. If \(N\) is not divisible by \(K\), we still report 100% whenever the largest and smallest anticlusters differ in size by at most one object. The best values for each instance, are highlighted in bold and the last row reports average values. The results in Table 11 demonstrate that ABA produces better solutions than METISfor all but one instance (Facebook with \(K=2{,}000\)). The outperformance of ABAgenerally increases with increasing values of \(K\), consistent with our observations on the poor quality of other algorithms for small anticlusters. ABAalso consistently outperforms random partitioning (Rand), and often by a substantial margin. In addition, ABAis considerably faster than METIS, for some instances by several orders of magnitude.

6.5pt

6 Conclusions↩︎

In this paper, we present a new heuristic algorithm called Assignment-Based Anticlustering (ABA), for solving large-scale Euclidean anticlustering problems. ABAis scalable to an unprecedented degree due to its efficient exploitation of the properties of the Euclidean sum of square metric. On large-scale benchmark instances, ABAconsistently outperforms existing methods in both solution quality and running time, often by large margins, especially when the number of anticlusters is large. ABAnot only achieves the best objective function values and the fastest running times known for these datasets, but it is also superior to existing methods in terms of anticluster similarity, producing anticlusters with highly similar statistical properties. High anticluster similarity is recognized in the literature as a desirable property in practical anticlustering applications.

This work suggests several promising directions for future research. The basic concept of ABAof pre-ranking objects and then assigning them in ranked order could be promising in other scenarios. For example, for single cluster diversity problems such as the maximum diversity problem (MDP, see [8]) or for anticlustering problems with predefined, but not equal, anticluster sizes, and anticlustering that respect must-link and cannot-link constraints on the objects.

*Funding The research of Dorit S.Hochbaum is supported in part by AI institute NSF award 2112533.

*Appendix

We prove Fact 1. Let \(\mathcal{C}_k\) be an anticluster of size \(N_k = |\mathcal{C}_k|\) with centroid \[\boldsymbol{\mu}_k = \frac{1}{N_k}\sum_{i \in \mathcal{C}_k} \boldsymbol{x}_i .\] Using \[\|\boldsymbol{x}_i-\boldsymbol{x}_{i'}\|_2^2 = \|\boldsymbol{x}_i\|_2^2+\|\boldsymbol{x}_{i'}\|_2^2 -2\boldsymbol{x}_i^\top\boldsymbol{x}_{i'},\] we obtain \[\begin{align} \sum_{\substack{i,i' \in \mathcal{C}_k\\ i<i'}} \|\boldsymbol{x}_i-\boldsymbol{x}_{i'}\|_2^2 &= (N_k-1)\sum_{i \in \mathcal{C}_k}\|\boldsymbol{x}_i\|_2^2 -2\sum_{\substack{i,i' \in \mathcal{C}_k\\ i<i'}} \boldsymbol{x}_i^\top\boldsymbol{x}_{i'} \\ &= N_k\sum_{i \in \mathcal{C}_k}\|\boldsymbol{x}_i\|_2^2 - \Big\|\sum_{i \in \mathcal{C}_k}\boldsymbol{x}_i\Big\|_2^2 \\ &= N_k\sum_{i \in \mathcal{C}_k}\|\boldsymbol{x}_i\|_2^2 - N_k^2\|\boldsymbol{\mu}_k\|_2^2 . \end{align}\] On the other hand, \[\begin{align} N_k\sum_{i \in \mathcal{C}_k}\|\boldsymbol{x}_i-\boldsymbol{\mu}_k\|_2^2 &= N_k\sum_{i \in \mathcal{C}_k} \left(\|\boldsymbol{x}_i\|_2^2 -2\boldsymbol{x}_i^\top\boldsymbol{\mu}_k +\|\boldsymbol{\mu}_k\|_2^2\right) \\ &= N_k\sum_{i \in \mathcal{C}_k}\|\boldsymbol{x}_i\|_2^2 - N_k^2\|\boldsymbol{\mu}_k\|_2^2 , \end{align}\] where we used \(\sum_{i \in \mathcal{C}_k}\boldsymbol{x}_i=N_k\boldsymbol{\mu}_k\). Thus, \[\sum_{\substack{i,i' \in \mathcal{C}_k\\ i<i'}} \|\boldsymbol{x}_i-\boldsymbol{x}_{i'}\|_2^2 = N_k\sum_{i \in \mathcal{C}_k} \|\boldsymbol{x}_i-\boldsymbol{\mu}_k\|_2^2 . \qquad \square\]

References↩︎

---

1. Corresponding author: philipp.baumann@unibe.ch↩︎