Part of a series on Statistics |
Data and information visualization |
---|
Major dimensions |
Important figures |
Information graphic types |
Related topics |
Multidimensional scaling (MDS) is a means of visualizing the level of similarity of individual cases of a data set. MDS is used to translate distances between each pair of objects in a set into a configuration of 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 where denote vectors in N-dimensional space, denotes the scalar product between and , and are the elements of the matrix 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 : and for distance. In classical scaling 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.
Let be the dissimilarity between points . Let be the Euclidean distance between embedded points .
Now, for each choice of the embedded points and is a monotonically increasing function , define the "stress" function:
The factor of in the denominator is necessary to prevent a "collapse". Suppose we define instead , then it can be trivially minimized by setting , then collapse every point to the same point.
A few variants of this cost function exist. MDS programs automatically minimize stress in order to obtain the MDS solution.
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 cases where the dissimilarities are distances on a surface and the target space is another surface, GMDS allows finding the minimum-distortion embedding of one surface into another. [5]
An extension of MDS, known as Super MDS, incorporates both distance and angle information for improved source localization. Unlike traditional MDS, which uses only distance measurements, Super MDS processes both distance and angle-of-arrival (AOA) data algebraically (without iteration) to achieve better accuracy. [6]
The method proceeds in the following steps:
This concise approach reduces the need for multiple anchors and enhances localization precision by leveraging angle constraints.
The data to be analyzed is a collection of objects (colors, faces, stocks, . . .) on which a distance function is defined,
These distances are the entries of the dissimilarity matrix
The goal of MDS is, given , to find vectors such that
where is a vector norm. In classical MDS, this norm is the Euclidean distance, but, in a broader sense, it may be a metric or arbitrary distance function. [7] 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 objects into such that distances are preserved. If the dimension is chosen to be 2 or 3, we may plot the vectors to obtain a visualization of the similarities between the objects. Note that the vectors are not unique: With the Euclidean distance, they may be arbitrarily translated, rotated, and reflected, since these transformations do not change the pairwise distances .
(Note: The symbol indicates the set of real numbers, and the notation refers to the Cartesian product of copies of , which is an -dimensional vector space over the field of the real numbers.)
There are various approaches to determining the vectors . Usually, MDS is formulated as an optimization problem, where is found as a minimizer of some cost function, for example,
A solution may then be found by numerical optimization techniques. For some particularly chosen cost functions, minimizers can be stated analytically in terms of matrix eigendecompositions. [2]
There are several steps in conducting MDS research:
Abstract. Multidimensional scaling methods are now a common statistical tool in psychophysics and sensory analysis. The development of these methods is charted, from the original research of Torgerson (metric scaling), Shepard and Kruskal (non-metric scaling) through individual differences scaling and the maximum likelihood methods proposed by Ramsay.