Maximize dispersion for K groups

optimal_dispersion(
  x,
  K,
  solver = NULL,
  max_dispersion_considered = NULL,
  min_dispersion_considered = NULL,
  npartitions = 1,
  time_limit = NULL
)

Arguments

x: The data input. Can be one of two structures: (1) A feature matrix where rows correspond to elements and columns correspond to variables (a single numeric variable can be passed as a vector). (2) An N x N matrix dissimilarity matrix; can be an object of class dist (e.g., returned by dist or as.dist) or a matrix where the entries of the upper and lower triangular matrix represent pairwise dissimilarities.
K: The number of groups or a vector describing the size of each group.
solver: Optional argument; currently supports "lpSolve", "glpk", and "symphony". See optimal_anticlustering.
max_dispersion_considered: Optional argument used for early stopping. If the dispersion found is equal to or exceeds this value, a solution having the previous best dispersion is returned.
min_dispersion_considered: Optional argument used for speeding up the algorithm computation. If passed, the dispersion is optimized starting from this value instead the global minimum distance.
npartitions: The number of groupings that are returned, each having an optimal dispersion value (defaults to 1).
time_limit: Time limit in seconds, given to the solver. Default is there is no time limit.

Value

A list with four elements:

dispersion: The optimal dispersion
groups: An assignment of elements to groups (vector)
edges: A matrix of 2 columns. Each row contains the indices of elements that had to be investigated to find the dispersion (i.e., each pair of elements cannot be part of the same group in order to achieve maximum dispersion).
dispersions_considered: All distances that were tested until the dispersion was found.

Details

The dispersion is the minimum distance between two elements within the same group. This function implements an optimal method to maximize the dispersion. If the data input x is a feature matrix and not a dissimilarity matrix, the pairwise Euclidean distance is used. It uses the algorithm presented in Max Diekhoff's Bachelor thesis at the Computer Science Department at Heinrich Heine University Düsseldorf.

To find out which items are not allowed to be grouped in the same cluster for maximum dispersion, the algorithm sequentially builds instances of a graph coloring problem, using an integer linear programming (ILP) representation (also see Fernandez et al., 2013). It is possible to specify the ILP solver via the argument solver (See optimal_anticlustering for more information on this argument). Optimally solving the maximum dispersion problem is NP-hard for K > 2 and therefore computationally infeasible for larger data sets. For K = 3 and K = 4, it seems that this approach scales up to several 100 elements, or even > 1000 for K = 3 (at least when using the Symphony solver). For larger data sets, use the heuristic approaches in anticlustering or bicriterion_anticlustering. However, note that for K = 2, the optimal approach is usually much faster than the heuristics.

In the output, the element edges defines which elements must be in separate clusters in order to achieve maximum dispersion. All elements not listed here can be changed arbitrarily between clusters without reducing the dispersion. If the maximum possible dispersion corresponds to the minimum dispersion in the data set, the output elements edges and groups are set to NULL because all possible groupings have the same value of dispersion. In this case the output element dispersions_considered has length 1.

If a time_limit is set and the function cannot find in the optimal dispersion in the given time, it will throw an error.

Note

If the SYMPHONY solver is used, an unfortunate "message" is printed to the console when this function terminates:

sym_get_col_solution(): No solution has been stored!

This message is no reason to worry and instead is a direct result of the algorithm finding the optimal value for the dispersion. Unfortunately, this message is generated in the C code underlying the SYMPHONY library (via the printing function printf), which cannot be prevented in R.

References

Diekhoff (2023). Maximizing dispersion for anticlustering. Retrieved from https://www.cs.hhu.de/fileadmin/redaktion/Fakultaeten/Mathematisch-Naturwissenschaftliche_Fakultaet/Informatik/Algorithmische_Bioinformatik/Bachelor-_Masterarbeiten/2831963_ba_ifo_AbschlArbeit_klau_mapap102_madie120_20230203_1815.pdf

Fernández, E., Kalcsics, J., & Nickel, S. (2013). The maximum dispersion problem. Omega, 41(4), 721–730. https://doi.org/10.1016/j.omega.2012.09.005

Author

Max Diekhoff

Martin Papenberg martin.papenberg@hhu.de

Examples


N <- 30
M <- 5
K <- 3
data <- matrix(rnorm(N*M), ncol = M)
distances <- dist(data)

opt <- optimal_dispersion(distances, K = K)
opt
#> $dispersion
#> [1] 1.448638
#> 
#> $groups
#>  [1] 2 2 3 3 1 1 1 1 2 3 3 1 1 3 2 1 3 1 3 2 3 2 3 2 3 2 1 1 2 2
#> 
#> $groups_fixated
#>  [1]  2  2 NA NA  1  1  1  1  2 NA NA  1  1  3  2  1 NA  1  3 NA NA  2 NA  2  3
#> [26]  2  1  1  2 NA
#> 
#> $edges
#>       [,1] [,2]
#>  [1,]   13   19
#>  [2,]    5   25
#>  [3,]   19   22
#>  [4,]    1    5
#>  [5,]   13   24
#>  [6,]   15   18
#>  [7,]   13   26
#>  [8,]    1   25
#>  [9,]    8   14
#> [10,]   19   26
#> [11,]    9   27
#> [12,]    2   14
#> [13,]   16   22
#> [14,]    6   14
#> [15,]   12   26
#> [16,]   18   26
#> [17,]   13   22
#> [18,]   26   28
#> [19,]    7   29
#> 
#> $dispersions_considered
#>  [1] 0.7562317 0.8188051 0.8932547 0.9000676 0.9625287 0.9848395 0.9972598
#>  [8] 1.0666849 1.0879575 1.1949480 1.1966636 1.2927882 1.2994952 1.3275895
#> [15] 1.3311682 1.3464776 1.3575125 1.3695842 1.4470740 1.4486377
#> 

# Compare to bicriterion heuristic:
groups_heuristic <- anticlustering(
  distances, 
  K = K,
  method = "brusco", 
  objective = "dispersion", 
  repetitions = 100
)
c(
  OPT = dispersion_objective(distances, opt$groups),
  HEURISTIC = dispersion_objective(distances, groups_heuristic)
)
#>       OPT HEURISTIC 
#>  1.448638  1.448638 

# Different group sizes are possible:
table(optimal_dispersion(distances, K = c(15, 10, 5))$groups)
#> 
#>  1  2  3 
#> 15 10  5 

# Induce cannot-link constraints by maximizing the dispersion:
solvable <- matrix(1, ncol = 6, nrow = 6)
solvable[2, 1] <- -1
solvable[3, 1] <- -1
solvable[4, 1] <- -1
solvable <- as.dist(solvable)
solvable
#>    1  2  3  4  5
#> 2 -1            
#> 3 -1  1         
#> 4 -1  1  1      
#> 5  1  1  1  1   
#> 6  1  1  1  1  1

# An optimal solution has to put item 1 in a different group than 
# items 2, 3 and 4 -> this is possible for K = 2
optimal_dispersion(solvable, K = 2)$groups
#> [1] 2 1 1 1 2 2

# It no longer works when item 1 can also not be linked with item 5:
# (check out output!)
unsolvable <- as.matrix(solvable)
unsolvable[5, 1] <- -1
unsolvable <- as.dist(unsolvable)
unsolvable
#>    1  2  3  4  5
#> 2 -1            
#> 3 -1  1         
#> 4 -1  1  1      
#> 5 -1  1  1  1   
#> 6  1  1  1  1  1
optimal_dispersion(unsolvable, K = 2)
#> $dispersion
#> [1] -1
#> 
#> $groups
#> NULL
#> 
#> $edges
#> NULL
#> 
#> $dispersions_considered
#> [1] -1
#> 
# But:
optimal_dispersion(unsolvable, K = c(2, 4)) # group sizes, not number of groups
#> $dispersion
#> [1] 1
#> 
#> $groups
#> [1] 2 1 1 1 1 2
#> 
#> $groups_fixated
#> [1]  2  1  1  1  1 NA
#> 
#> $edges
#>      [,1] [,2]
#> [1,]    1    2
#> [2,]    1    3
#> [3,]    1    4
#> [4,]    1    5
#> 
#> $dispersions_considered
#> [1] -1  1
#>