divide_conquer_mds {bigmds}R Documentation

Divide-and-conquer MDS

Description

Roughly speaking, a large data set, x, of size nn is divided into parts, then classical MDS is performed over every part and, finally, the partial configurations are combined so that all the points lie on the same coordinate system with the aim to obtain a global MDS configuration.

Usage

divide_conquer_mds(x, l, c_points, r, n_cores)

Arguments

x

A matrix with nn points (rows) and kk variables (columns).

l

The size for which classical MDS can be computed efficiently (using cmdscale function). It means that if lˉ\bar{l} is the limit size for which classical MDS is applicable, then llˉ\leq \bar{l}.

c_points

Number of points used to align the MDS solutions obtained by the division of x into pp data subsets. Recommended value: 5·r.

r

Number of principal coordinates to be extracted.

n_cores

Number of cores wanted to use to run the algorithm.

Details

The divide-and-conquer MDS starts dividing the nn points into pp partitions: the first partition contains l points and the others contain l-c_points points. Therefore, p=1+(np = 1 + (n-l)/(l-c_points). The partitions are created at random.

Once the partitions are created, c_points different random points are taken from the first partition and concatenated to the other partitions After that, classical MDS is applied to each partition, with target low dimensional configuration r.

Since all the partitions share c_points points with the first one, Procrustes can be applied in order to align all the configurations. Finally, all the configurations are concatenated in order to obtain a global MDS configuration.

Value

Returns a list containing the following elements:

points

A matrix that consists of nn points (rows) and r variables (columns) corresponding to the principal coordinates. Since a dimensionality reduction is performed, r<<k<<k

eigen

The first r largest eigenvalues: λˉi,i{1,,r}\bar{\lambda}_i, i \in \{1, \dots, r\} , where λˉi=1/pj=1pλij/nj\bar{\lambda}_i = 1/p \sum_{j=1}^{p}\lambda_i^j/n_j, being λij\lambda_i^j the ithi-th eigenvalue from partition jj and njn_j the size of the partition jj.

References

Delicado P. and C. Pachón-García (2021). Multidimensional Scaling for Big Data. https://arxiv.org/abs/2007.11919.

Borg, I. and P. Groenen (2005). Modern Multidimensional Scaling: Theory and Applications. Springer.

Examples

set.seed(42)
x <- matrix(data = rnorm(4 * 10000), nrow = 10000) %*% diag(c(9, 4, 1, 1))
mds <- divide_conquer_mds(x = x, l = 200, c_points = 5 * 2, r = 2, n_cores = 1)
head(mds$points)
mds$eigen


[Package bigmds version 3.0.0 Index]