Multidimensional scaling
Multidimensional scaling (MDS) is a means of visualizing the level of similarity of individual cases of a data set.
points mapped into an abstract Cartesian space.
[1] More technically, MDS refers to a set of related ordination techniques used in information visualization, in particular to display the information contained in a distance matrix.
It is a form of non-linear dimensionality reduction.
Given a distance matrix with the distances between each pair of objects in a set, and a chosen number of dimensions, N, an MDS algorithm places each object into N-dimensional space (a lower-dimensional representation) such that the between-object distances are preserved as well as possible.
For N = 1, 2, and 3, the resulting points can be visualized on a scatter plot.
[2] Core theoretical contributions to MDS were made by James O. Ramsay of McGill University, who is also regarded as the founder of functional data analysis.
[3] MDS algorithms fall into a taxonomy, depending on the meaning of the input matrix: It is also known as Principal Coordinates Analysis (PCoA), Torgerson Scaling or Torgerson–Gower scaling.
It takes an input matrix giving dissimilarities between pairs of items and outputs a coordinate matrix whose configuration minimizes a loss function called strain,[2] which is given by
denote vectors in N-dimensional space,
defined on step 2 of the following algorithm, which are computed from the distances.
It is a superset of classical MDS that generalizes the optimization procedure to a variety of loss functions and input matrices of known distances with weights and so on.
A useful loss function in this context is called stress, which is often minimized using a procedure called stress majorization.
Metric MDS minimizes the cost function called “stress” which is a residual sum of squares:
Metric scaling uses a power transformation with a user-controlled exponent
Non-metric scaling is defined by the use of isotonic regression to nonparametrically estimate a transformation of the dissimilarities.
In contrast to metric MDS, non-metric MDS finds both a non-parametric monotonic relationship between the dissimilarities in the item-item matrix and the Euclidean distances between items, and the location of each item in the low-dimensional space.
The core of a non-metric MDS algorithm is a twofold optimization process.
First the optimal monotonic transformation of the proximities has to be found.
Secondly, the points of a configuration have to be optimally arranged, so that their distances match the scaled proximities as closely as possible.
NMDS needs to optimize two objectives simultaneously.
This is usually done iteratively: Louis Guttman's smallest space analysis (SSA) is an example of a non-metric MDS procedure.
An extension of metric multidimensional scaling, in which the target space is an arbitrary smooth non-Euclidean space.
In classical MDS, this norm is the Euclidean distance, but, in a broader sense, it may be a metric or arbitrary distance function.
[6] For example, when dealing with mixed-type data that contain numerical as well as categorical descriptors, Gower's distance is a common alternative.
[citation needed] In other words, MDS attempts to find a mapping from the
are not unique: With the Euclidean distance, they may be arbitrarily translated, rotated, and reflected, since these transformations do not change the pairwise distances
indicates the set of real numbers, and the notation
-dimensional vector space over the field of the real numbers.)
For some particularly chosen cost functions, minimizers can be stated analytically in terms of matrix eigendecompositions.
