Multidimensional Scaling

Classical Multidimensional Scaling (MDS), also known as Principal Coordinates Analysis (PCoA), is a specific technique in this family that accomplishes the embedding in two steps:

1. Convert the distance matrix to a Gram matrix. This conversion is based on

the following relations between a distance matrix $D$ and a Gram matrix $G$:

\[\mathrm{sqr}(\mathbf{D}) = \mathbf{g} \mathbf{1}^T + \mathbf{1} \mathbf{g}^T - 2 \mathbf{G}\]

Here, $\mathrm{sqr}(\mathbf{D})$ indicates the element-wise square of $\mathbf{D}$, and $\mathbf{g}$ is the diagonal elements of $\mathbf{G}$. This relation is itself based on the following decomposition of squared Euclidean distance:

\[\| \mathbf{x} - \mathbf{y} \|^2 = \| \mathbf{x} \|^2 + \| \mathbf{y} \|^2 - 2 \mathbf{x}^T \mathbf{y}\]

1. Perform eigenvalue decomposition of the Gram matrix to derive the coordinates.

Note: The Gramian derived from $D$ may have non-positive or degenerate eigenvalues. The subspace of non-positive eigenvalues is projected out of the MDS solution so that the strain function is minimized in a least-squares sense. If the smallest remaining eigenvalue that is used for the MDS is degenerate, then the solution is not unique, as any linear combination of degenerate eigenvectors will also yield a MDS solution with the same strain value.

fit(MDS, X; kwargs...)

Compute an embedding of X points by classical multidimensional scaling (MDS). There are two calling options, specified via the required keyword argument distances:

mds = fit(MDS, X; distances=false, maxoutdim=size(X,1)-1)

where X is the data matrix. Distances between pairs of columns of X are computed using the Euclidean norm. This is equivalent to performing PCA on X.

mds = fit(MDS, D; distances=true, maxoutdim=size(D,1)-1)

where D is a symmetric matrix D of distances between points.

predict(M)

Returns a coordinate matrix of size $(p, n)$ for the MDS model M, where each column is the coordinates for an observation in the embedding space.

predict(M, x::AbstractVector)

Calculate the out-of-sample transformation of the observation x for the MDS model M. Here, x is a vector of length d.

size(M::MDS)

Returns tuple where the first value is the MDS model M input dimension, i.e the dimension of the observation space, and the second value is the output dimension, i.e the dimension of the embedding.

projection(M::MDS)

Get the MDS model M eigenvectors matrix (of size $(n, p)$) of the embedding space. The eigenvectors are arranged in descending order of the corresponding eigenvalues.

loadings(M::MDS)

Get the loading of the MDS model M.

eigvals(M::MDS)

Get the eigenvalues of the MDS model M.

eigvecs(M::MDS)

Get the MDS model M eigenvectors matrix.

stress(M::MDS)

Get the stress of the MDS mode M.

stress(M::MetricMDS)

Get the stress of the MDS model M.

gram2dmat(G)

Convert a Gram matrix G to a distance matrix.

gram2dmat!(D, G)

Convert a Gram matrix G to a distance matrix, and write the results to D.

dmat2gram(D)

Convert a distance matrix D to a Gram matrix.

dmat2gram!(G, D)

Convert a distance matrix D to a Gram matrix, and write the results to G.

(Non)Metric Multidimensional Scaling

Use this class to perform (non)metric multidimensional scaling.

There are two calling options, specified via the required keyword argument distances:

mds = fit(MDS, X; distances=false, maxoutdim=size(X,1)-1)

where X is the data matrix. Distances between pairs of columns of X are computed using the Euclidean norm. This is equivalent to performing PCA on X.

mds = fit(MDS, D; distances=true, maxoutdim=size(D,1)-1)

where D is a symmetric matrix D of distances between points.

In addition, the metric parameter specifies type of MDS, By default, it is assigned with nothing value which results in performing metric MDS with dissimilarities calculated as Euclidean distances.

An arbitrary transformation function can be provided to metric parameter to perform metric MDS with transformed proximities. The function has to accept two parameters, a vector of proximities and a vector of distances, corresponding to the proximities, to calculate disparities required for stress calculation. Internally, the proximity and distance vectors are obtained from compact triangular matrix representation of proximity and distance matrices.

For ratio MDS, a following ratio transformation function can be used

mds = fit(MDS, D; distances=true, metric=((p,d)->2 .* p))

For order MDS, use isotonic regression function in the metric parameter:

mds = fit(MDS, D; distances=true, metric=isotonic)

fit(MetricMDS, X; kwargs...)

Compute an embedding of X points by (non)metric multidimensional scaling (MDS).

Keyword arguments:

Let (d, n) = size(X) be respectively the input dimension and the number of observations:

• distances: The choice of input (required):
  • false: use X to calculate dissimilarity matrix using Euclidean distance
  • true: use X input as precomputed dissimilarity symmetric matrix (distances)
• maxoutdim: Maximum output dimension (default d-1)
• metric : a function for calculation of disparity values
  • nothing: use dissimilarity values as the disparities to perform the metric MDS (default)
  • isotonic: converts dissimilarity values to ordinal disparities to perform non-metric MDS
  • any two parameter disparity transformation function, where the first parameter is a vector of proximities (i.e. dissimilarities) and the second parameter is a vector of distances, e.g. (p,d)->b*p for some b is a transformation function for ratio MDS.
• tol: Convergence tolerance (default 1.0e-3)
• maxiter: Maximum number of iterations (default 300)
• initial: an initial reduced space point configuration
  • nothing: then an initial configuration is randomly generated (default)
  • pre-defined matrix
• weights: a weight matrix
  • nothing: then weights are set to one, $w_{ij} = 1$ (default)
  • pre-defined matrix

Note: if the algorithm is unable to converge then ConvergenceException is thrown.

predict(M::MetricMDS)

Returns a coordinate matrix of size $(p, n)$ for the MDS model M, where each column is the coordinates for an observation in the embedding space.

size(M::MetricMDS)

Returns tuple where the first value is the MDS model M input dimension, i.e the dimension of the observation space, and the second value is the output dimension, i.e the dimension of the embedding.

stress(M::MetricMDS)

Get the stress of the MDS model M.