Skip to contents

Ordinates samples from their distances, for plotting beta diversity, by placing them so that their distances on the plot match the distances in dm as closely as possible, in least squares. Uses the SMACOF algorithm of scikit-learn's metric MDS(), ported to parallel C that works from dm directly, with far less time and memory.

Usage

mds(
  dm,
  n_axes = 2L,
  n_starts = 4L,
  max_iters = 1000L,
  tol = 1e-07,
  seed = 0L,
  cpus = n_cpus()
)

Arguments

dm

A dist object, such as from beta_div() or bray(), or a symmetric numeric matrix of distances. Must not contain NAs or negative values.

n_axes

The number of dimensions. Default: 2

n_starts

The number of random starts to run after the start from the PCoA solution, from 0 to 1000. Default: 4

max_iters

The maximum number of SMACOF iterations for each start. Default: 1000

tol

Each start stops once an iteration lowers the raw stress by no more than tol times the sum of squared distances on the plot. Default: 1e-7

seed

An integer seed for the random starts. Default: 0

cpus

How many parallel processing threads should be used. The default, n_cpus(), is the CPU cores this R process may use, within any limits set on it. Results are the same for any cpus.

Value

A numeric matrix with one row per sample and one column per dimension, named "MDS1", "MDS2", etc., as described in "Ordination result" below. method is "mds"; eig and prop are NA, as metric MDS has no eigenvalues. Then come:

  • stress: The stress of the solution, from 0 (a perfect fit) to 1 (no better than putting every point in one place). See "Stress" below.

  • converged: TRUE if the best start stopped because a plain step met tol, FALSE if it stopped at max_iters.

  • n_iters: The number of SMACOF iterations the best start ran.

  • n_starts: The number of random starts run.

  • best_start: Which start gave the solution: 0 for the PCoA start, else the random start's number.

  • n_best: How many starts (of n_starts + 1) ended within 0.1% of the lowest stress.

With fewer than two samples there is nothing to fit: the result has no columns, stress is 0, and no starts are run.

Details

Which ordination? pcoa(), mds(), and nmds() all fit a configuration to dm in n_axes dimensions. pcoa() (classical scaling) is exact and fast, has eigenvalues and "variance explained", but fits the squared distances after double centering, so large distances dominate, and non-Euclidean distances such as Bray-Curtis lose part of their structure to negative eigenvalues. mds() fits the distances themselves, in their own units, so the plot's distances can be read as the data's, with stress saying how well. nmds() fits only their rank order, which suits distances whose values matter less than their order, such as the saturated Bray-Curtis values of very different samples; it is the usual choice for community data. mds() and nmds() iterate from several starts and take longer than pcoa().

Method

Metric MDS minimizes the raw stress \(\sigma = \sum_{i<j}(d_{ij} - \delta_{ij})^2\), where \(d_{ij}\) are the distances between points on the plot and \(\delta_{ij}\) the distances in dm. It does so by SMACOF (de Leeuw, 1977; Borg & Groenen, 2005), as scikit-learn's metric smacof() does: each iteration moves the points by the Guttman transform, \(X \leftarrow \Gamma(X) = \frac{1}{n} B(X) X\), which never increases \(\sigma\). A start stops when an iteration lowers \(\sigma\) by no more than tol times \(\sum d_{ij}^2\), or after max_iters iterations.

As in nmds() (see there), iterations take relaxed steps, \(X \leftarrow 2\Gamma(X) - X\) (de Leeuw & Heiser, 1980), when k > 1, until one makes no more than tol progress, and then plain steps until a plain step does; n_axes = 1 uses plain steps only, and so does the last iteration allowed by max_iters. So the returned configuration is a fixed point of \(\Gamma\) to within tol, at the right scale (\(\sum d_{ij}\delta_{ij} = \sum d_{ij}^2\)), typically in about half the iterations that plain steps take. With plain steps only (an internal setting used by the tests), a start follows scikit-learn's iterations from the same starting configuration to within rounding error (about \(10^{-13}\), relatively, in every iteration's raw stress).

SMACOF only finds a local minimum of stress, so, as in nmds():

  1. The first start is the PCoA solution, from pcoa(). For distances that are Euclidean in n_axes dimensions, PCoA recovers the configuration, and SMACOF stops at once. (An axis without a positive eigenvalue gets small random coordinates instead.)

  2. Then come n_starts random starts, with coordinates uniform on [0, 1). On beta diversity distances, a random start sometimes ends with a stress up to a few percent lower than the PCoA start's.

  3. The start with the lowest stress is kept; if several tie exactly, the earliest. Its configuration is centered, rotated to its principal axes, and each axis is flipped so that its coordinate with the largest absolute value is positive (the first such sample, if several are within a relative \(10^{-8}\) of it). It is not rescaled: distances on the plot are in the units of dm.

Stress

The stress reported is \(\sqrt{\sigma / \sum \delta_{ij}^2}\): the raw stress, normalized by the distances in dm. It only depends on \(\sigma\), so the lowest stress is the best fit, and it doesn't depend on the units of dm. It is 1 when all points coincide, and at most 1 after any SMACOF iteration (max_iters = 0 returns the starting configuration, whose stress can be higher). Pairs with a distance of 0 in dm, such as duplicate samples, are pulled towards the same point.

scikit-learn reports \(\sigma\) itself by default for metric MDS, or, with normalized_stress = True, \(\sqrt{\sigma / \sum d_{ij}^2}\) (normalized by the distances on the plot instead). For a result x, that is sqrt(sum((dist(x) - dm)^2) / sum(dist(x)^2)).

Differences from scikit-learn

  • scikit-learn takes plain Guttman steps; mds() takes relaxed ones (see above).

  • scikit-learn runs n_init random starts (init = "random", its current default) or one start from classical MDS (init = "classical_mds"); mds() runs both kinds, and ranks them by the stress described above.

  • scikit-learn's defaults are max_iter = 300 and eps = 1e-6; mds()'s are max_iters = 1000 and tol = 1e-7.

  • scikit-learn returns the configuration as SMACOF leaves it; mds() centers, rotates, and flips it, which doesn't change the stress.

  • scikit-learn stops when stress falls by less than eps; mds() stops when it falls by no more than tol, so that tol = 0 stops once stress no longer falls.

  • scikit-learn computes distances on the plot with the expansion \(|x|^2 - 2 x \cdot y + |y|^2\), and replaces distances of 0 by \(10^{-5}\) in the Guttman transform; mds() computes them directly, and leaves out pairs at distance 0, whose contribution \(r_{ij}(x_i - x_j)\) is 0 either way.

  • The random starts come from seed, not from R's or NumPy's random number generators, so set.seed() has no effect, and R's random number stream is left untouched.

Speed and memory

mds() shares its C engine with nmds(), without the sorting and the isotonic regression: dm is read in its own order, once converted to a plain vector of doubles. Each start running at the same time needs \(256 n k\) bytes; nothing of size \(n \times n\) is formed, and there is no limit on the number of samples. Each SMACOF iteration makes one pass over the pairs, which takes time proportional to \(n^2 k\). Several starts run at once, one per thread, while one iteration takes under about \(2^{26}\) pairs of work (\(n\) up to about 11,500); otherwise starts run one at a time, with each iteration split across cpus threads (for at least \(2^{18}\) pairs), in parts between checks for user interrupts.

Reproducibility

The result, with all its attributes, is bit-identical from run to run, in new R sessions, and for any value of cpus, given the same dm, n_axes, n_starts, max_iters, tol, and seed, for the reasons given in nmds(). dm * 2^p gives exactly the result for dm, times \(2^p\). (As for every ordination, distances above \(10^{150}\) are rejected.) Results can still differ in the last bits between computers or compilers, as for any floating point code.

n_axes larger than \(n - 1\) is reduced to \(n - 1\).

Ordination result

Every ordination function (pcoa(), pca(), rpca(), dbrda(), capda(), capscale(), mds(), nmds(), isomap(), tsne(), umap(), and so dist_ord()) returns the same kind of object: a numeric matrix with one row per sample and one column per axis, so that it can go straight into a data frame. Rows are named after the samples, when the input has names. Columns are named after the method: "PCoA1", "PC1", "RPCA1", "dbRDA1" or "CAP1" (then "MDS1" for unconstrained axes), "MDS1", "NMDS1", "Isomap1", "TSNE1", "UMAP1", and so on.

Its attributes always begin with these three, in this order, each with one value per column:

  • method: The method's ID, e.g. "pcoa" or "nmds".

  • eig: Each axis's eigenvalue, on the method's own scale: pcoa() and isomap() give the eigenvalues of Gower's centered matrix (sums of squares); pca() and rpca() give variances, which are pcoa()'s divided by \(n - 1\) for \(n\) samples; and dbrda() and capscale() follow vegan, which also divides by \(n - 1\) when any distance is 4 or more. NA for mds(), nmds(), tsne(), and umap(), which have no eigenvalues.

  • prop: The proportion of the total variance (or inertia) that each axis explains. Unlike eig, it is comparable between methods, so use it to label axes. NA where it isn't defined.

Attributes particular to the method follow them, and last display, with the ordination's title for plot() and print(): the method's name, and for the methods that take distances, the distance matrix's title, such as "Principal Coordinates Analysis of Bray-Curtis Dissimilarity" (see ecodive_display). The matrix has class "ecodive_ord" (as well as "matrix"), so that print() lists the other attributes by name rather than in full, and plot() draws the samples on the first two axes, labelled from the attributes, with any loadings, constraints and centroids on top (see plot.ecodive_ord()). plot(ord, "Species", iris) colours the samples by a column of metadata. Subsetting with [, or as.data.frame(), gives a plain matrix or data frame without the attributes.

References

de Leeuw, J. (1977). Applications of convex analysis to multidimensional scaling. In J. R. Barra, F. Brodeau, G. Romier, & B. van Cutsem (Eds.), Recent Developments in Statistics (pp. 133-145). North Holland.

de Leeuw, J., & Heiser, W. J. (1980). Multidimensional scaling with restrictions on the configurations. In P. R. Krishnaiah (Ed.), Multivariate Analysis V (pp. 501-522). North Holland.

Borg, I., & Groenen, P. J. F. (2005). Modern Multidimensional Scaling: Theory and Applications (2nd ed.). Springer. doi:10.1007/0-387-28981-X

Pedregosa, F., et al. (2011). Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12, 2825-2830. The C code of mds() is ported from scikit-learn 1.9.1's sklearn.manifold.smacof(), under scikit-learn's BSD-3-Clause license (Copyright (c) 2007-2026 The scikit-learn developers).

See also

Examples

    dm  <- bray(iris[, 1:4])
    ord <- mds(dm)
    plot(ord, 'Species', iris)

    ord
#> # A matrix: 150 samples × 2 axes
#> # Metric Multidimensional Scaling of Bray-Curtis Dissimilarity
#>     MDS1     MDS2
#>  1 0.169 -0.0251
#>  2 0.171  0.0193
#>  3 0.19   0.00797
#>  4 0.183  0.0198
#>  5 0.176 -0.0273
#>  6 0.133 -0.0585
#>  7 0.19  -0.00634
#>  8 0.167 -0.0139
#>  9 0.197  0.0416
#> 10 0.172  0.0133
#> # … 140 more samples
#> # Use print(x, n = ...) to see more samples
#> # Attributes: method, eig, prop, stress, converged, n_iters, n_starts,
#> #   best_start, n_best
    str(ord)
#>  'ecodive_ord' num [1:150, 1:2] 0.169 0.171 0.19 0.183 0.176 ...
#>  - attr(*, "dimnames")=List of 2
#>   ..$ : NULL
#>   ..$ : chr [1:2] "MDS1" "MDS2"
#>  - attr(*, "method")= chr "mds"
#>  - attr(*, "eig")= num [1:2] NA NA
#>  - attr(*, "prop")= num [1:2] NA NA
#>  - attr(*, "stress")= num 0.0422
#>  - attr(*, "converged")= logi TRUE
#>  - attr(*, "n_iters")= int 17
#>  - attr(*, "n_starts")= int 4
#>  - attr(*, "best_start")= int 0
#>  - attr(*, "n_best")= int 1
#>  - attr(*, "display")=List of 1
#>   ..$ title: chr "Metric Multidimensional Scaling of Bray-Curtis Dissimilarity"