fast_anticlustering {anticlust}R Documentation

Fast anticlustering


Increasing the speed of (k-means / k-plus) anticlustering by (1) conducting fewer exchanges during the optimization and (2) using an alternative formulation of the k-means objective. Makes anticlustering applicable to quite large data sets.


  k_neighbours = Inf,
  categories = NULL,
  exchange_partners = NULL



A numeric vector, matrix or data.frame of data points. Rows correspond to elements and columns correspond to features. A vector represents a single numeric feature.


How many anticlusters should be created. Alternatively: (a) A vector describing the size of each group, or (b) a vector of length nrow(x) describing how elements are assigned to anticlusters before the optimization starts.


The number of nearest neighbours that serve as exchange partner for each element. See details.


A vector, data.frame or matrix representing one or several categorical constraints.


Optional argument. A list of length NROW(x) specifying for each element the indices of the elements that serve as exchange partners. If used, this argument overrides the k_neighbours argument. See examples.


This function was created to make anticlustering applicable to large data sets (e.g., several 100,000 elements). It optimizes the k-means objective because computing all pairwise distances as is done when optimizing the "diversity" (i.e., the default in anticlustering) is not feasible for very large data sets (for about N > 20000 on my personal computer). Using fast_anticlustering for k-plus anticlustering is also possible by applying kplus_moment_variables on the input (and possibly by using the argument exchange_partners, see Examples).

The function fast_anticlustering employs a speed-optimized exchange method, which is basically equivalent to method = "exchange" in anticlustering, but may reduce the number of exchanges that are investigated for each input element. The number of exchange partners per element has to be set using the argument k_neighbours. By default, it is set to Inf, meaning that all possible swaps are tested. If k_neighbours is set differently (which is usually recommended when running this function), the default behaviour is to generate exchange partners using a nearest neighbour search (using the function nn2 from the RANN package). Using more exchange partners can improve the quality of the results, but also increase run time. Note that for very large data sets, anticlustering generally becomes "easier" (even a random split may yield satisfactory results), so using few exchange partners is usually not a problem.

It is possible to specify custom exchange partners using the argument exchange_partners instead of relying on the default nearest neighbour search. When using exchange_partners, it is not necessary that each element has the same number of exchange partners; this is why the argument exchange_partners has to be a list instead of a matrix or data.frame. Exchange partners can for example be generated by generate_exchange_partners (see Examples), but a custom list may also be used. Note that categorical constraints induced via categories may not be respected during the optimization if the exchange_partners argument allows exchanges between members of different categories, so care must be taken when combining the arguments exchange_partners and categories.

In anticlustering(..., objective = "variance"), the run time of computing the k-means objective is in O(M N), where N is the total number of elements and M is the number of variables. This is because the variance is computed as the sum of squared distances between all data points and their cluster centers. The function fast_anticlustering uses a different - but equivalent - formulation of the k-means objective, where the re-computation of the objective only depends and M but no longer on N. In particular, this variant of k-means anticlustering minimizes the weighted sum of squared distances between cluster centroids and the overall data centroid; the distances between all individual data points and their cluster center are not computed (Späth, 1986). Using the different objective formulation reduces the run time by an order of magnitude and makes k-means anticlustering applicable to very large data sets (even in the millions). For a fixed number of exchange partners (specified using the argument k_neighbours), the approximate run time of fast_anticlustering is in O(M N). The algorithm method = "exchange" in anticlustering with objective = "variance" has a run time of O(M N^3). Thus, fast_anticlustering can improve the run time by two orders of magnitude as compared to the standard exchange algorithm. The nearest neighbour search, which is done in the beginning usually does not strongly contribute to the overall run time. It is nevertheless possible to suppress the nearest neighbour search by using the exchange_partners argument.

When setting the categories argument, exchange partners (i.e., nearest neighbours) will be generated from the same category. Note that when categories has multiple columns, each combination of these categories is treated as a distinct category by the exchange method. You can also use categories_to_binary to potentially improve results for several categorical variables, instead of using the argument categories.


Martin Papenberg


Papenberg, M., & Klau, G. W. (2021). Using anticlustering to partition data sets into equivalent parts. Psychological Methods, 26(2), 161–174.

Papenberg, M. (2024). K-plus Anticlustering: An Improved k-means Criterion for Maximizing Between-Group Similarity. British Journal of Mathematical and Statistical Psychology, 77(1), 80–102.

Späth, H. (1986). Anticlustering: Maximizing the variance criterion. Control and Cybernetics, 15, 213-218.

See Also







## Use fewer or more exchange partners to adjust speed (vs. quality tradeoff)
features <- iris[, - 5]
N <- nrow(features)
init <- sample(rep_len(1:3, N)) # same starting point for all calls:
groups1 <- fast_anticlustering(features, K = init) # default: all exchanges
groups2 <- fast_anticlustering(features, K = init, k_neighbours = 20) 
groups3 <- fast_anticlustering(features, K = init, k_neighbours = 2)

variance_objective(features, groups1)
variance_objective(features, groups2)
variance_objective(features, groups3)

# K-plus anticlustering is straight forward when sticking with the default
# for k_neighbours
kplus_anticlusters <- fast_anticlustering(
  kplus_moment_variables(features, T = 2), 
  K = 3
mean_sd_tab(features, kplus_anticlusters)

# Some care is needed when applying k-plus using with this function 
# while using a reduced number of exchange partners generated in the 
# nearest neighbour search. Then we:
# 1) Use kplus_moment_variables() on the numeric input
# 2) Generate custom exchange_partners because otherwise nearest 
#    neighbours are internally selected based on the extended k-plus 
#    variables returned by kplus_moment_variables() 
#    (which does not really make sense)
kplus_anticlusters <- fast_anticlustering(
  kplus_moment_variables(features, T = 2), 
  K = 3,
  exchange_partners = generate_exchange_partners(120, features = features, method = "RANN")
mean_sd_tab(features, kplus_anticlusters)
# Or we use random exchange partners: 
kplus_anticlusters <- fast_anticlustering(
  kplus_moment_variables(features, T = 2), 
  K = 3,
  exchange_partners = generate_exchange_partners(120, N = nrow(features), method = "random")
mean_sd_tab(features, kplus_anticlusters)

# Working on several 1000 elements is very fast (Here n = 10000, m = 2)
data <- matrix(rnorm(10000 * 2), ncol = 2)
start <- Sys.time()
groups <- fast_anticlustering(data, K = 5, k_neighbours = 5)
Sys.time() - start 

[Package anticlust version 0.8.5 Index]