Maximize dispersion for K groups
optimal_dispersion(x, K, solver = NULL, max_dispersion_considered = NULL)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.
The number of groups or a vector describing the size of each group.
Optional argument; if passed, has to be either "glpk" or "symphony". See details.
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.
A list with four elements:
The optimal dispersion
An assignment of elements to groups (vector)
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).
All distances that were tested until the dispersion was found.
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
the 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. This function either requires the R package
Rglpk and the GNU linear programming kit
(<http://www.gnu.org/software/glpk/>) or the R package
Rsymphony and the COIN-OR SYMPHONY solver libraries
(<https://github.com/coin-or/SYMPHONY>). If the argument
solver is not specified, the function will try to find the
GLPK or SYMPHONY solver by itself (it prioritizes using SYMPHONY if
both are available). The GNU linear programming kit (solver =
"glpk") seems to be considerably slower for K >= 3 than the
SYMPHPONY solver (solver = "symphony").
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 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.
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
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.558493
#>
#> $groups
#> [1] 2 2 3 3 3 1 2 1 1 2 3 3 2 3 1 1 3 3 2 2 1 1 3 3 1 2 2 2 1 1
#>
#> $edges
#> [,1] [,2]
#> [1,] 2 8
#> [2,] 8 14
#> [3,] 7 21
#> [4,] 16 20
#> [5,] 13 29
#> [6,] 12 21
#> [7,] 2 14
#> [8,] 10 22
#> [9,] 7 12
#> [10,] 8 24
#> [11,] 2 11
#> [12,] 2 6
#> [13,] 1 30
#> [14,] 15 26
#> [15,] 11 27
#> [16,] 7 9
#> [17,] 8 11
#> [18,] 6 11
#> [19,] 6 10
#> [20,] 2 24
#> [21,] 6 8
#>
#> $dispersions_considered
#> [1] 0.7800843 0.9378773 1.0469722 1.0848882 1.2456892 1.2616679 1.2636728
#> [8] 1.2674152 1.2782485 1.3077583 1.3128102 1.3478616 1.3947288 1.3978609
#> [15] 1.5123242 1.5282671 1.5304251 1.5413485 1.5458909 1.5568297 1.5584930
#>
# 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.558493 1.558493
# 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
#>
#> $edges
#> [,1] [,2]
#> [1,] 1 2
#> [2,] 1 3
#> [3,] 1 4
#> [4,] 1 5
#> [5,] 1 6
#> [6,] 2 3
#> [7,] 2 4
#> [8,] 2 5
#> [9,] 2 6
#> [10,] 3 4
#> [11,] 3 5
#> [12,] 3 6
#> [13,] 4 5
#> [14,] 4 6
#> [15,] 5 6
#>
#> $dispersions_considered
#> [1] -1 1
#>