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 n {\textstyle n} objects in a set into a configuration of n {\textstyle n} 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 Strain D ( x 1 , x 2 , . . . , x n ) = ( ∑ ∑ --> i , j ( b i j − − --> x i T x j ) 2 ∑ ∑ --> i , j b i j 2 ) 1 / 2 , {\displaystyle {\text{Strain}}_{D}(x_{1},x_{2},...,x_{n})={\Biggl (}{\frac {\sum _{i,j}{\bigl (}b_{ij}-x_{i}^{T}x_{j}{\bigr )}^{2}}{\sum _{i,j}b_{ij}^{2}}}{\Biggr )}^{1/2},} where x i {\displaystyle x_{i}} denote vectors in N-dimensional space, x i T x j {\displaystyle x_{i}^{T}x_{j}} denotes the scalar product between x i {\displaystyle x_{i}} and x j {\displaystyle x_{j}} , and b i j {\displaystyle b_{ij}} are the elements of the matrix B {\displaystyle B} 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:
Stress D ( x 1 , x 2 , . . . , x n ) = ∑ ∑ --> i ≠ ≠ --> j = 1 , . . . , n ( d i j − − --> ‖ ‖ --> x i − − --> x j ‖ ‖ --> ) 2 . {\displaystyle {\text{Stress}}_{D}(x_{1},x_{2},...,x_{n})={\sqrt {\sum _{i\neq j=1,...,n}{\bigl (}d_{ij}-\|x_{i}-x_{j}\|{\bigr )}^{2}}}.}
Metric scaling uses a power transformation with a user-controlled exponent p {\textstyle p} : d i j p {\textstyle d_{ij}^{p}} and − − --> d i j 2 p {\textstyle -d_{ij}^{2p}} for distance. In classical scaling p = 1. {\textstyle p=1.} 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 d i j {\displaystyle d_{ij}} be the dissimilarity between points i , j {\displaystyle i,j} . Let d ^ ^ --> i j = ‖ ‖ --> x i − − --> x j ‖ ‖ --> {\displaystyle {\hat {d}}_{ij}=\|x_{i}-x_{j}\|} be the Euclidean distance between embedded points x i , x j {\displaystyle x_{i},x_{j}} .
Now, for each choice of the embedded points x i {\displaystyle x_{i}} and is a monotonically increasing function f {\displaystyle f} , define the "stress" function:
S ( x 1 , . . . , x n ; f ) = ∑ ∑ --> i < j ( f ( d i j ) − − --> d ^ ^ --> i j ) 2 ∑ ∑ --> i < j d ^ ^ --> i j 2 . {\displaystyle S(x_{1},...,x_{n};f)={\sqrt {\frac {\sum _{i<j}{\bigl (}f(d_{ij})-{\hat {d}}_{ij}{\bigr )}^{2}}{\sum _{i<j}{\hat {d}}_{ij}^{2}}}}.}
The factor of ∑ ∑ --> i < j d ^ ^ --> i j 2 {\displaystyle \sum _{i<j}{\hat {d}}_{ij}^{2}} in the denominator is necessary to prevent a "collapse". Suppose we define instead S = ∑ ∑ --> i < j ( f ( d i j ) − − --> d ^ ^ --> i j ) 2 {\displaystyle S={\sqrt {\sum _{i<j}{\bigl (}f(d_{ij})-{\hat {d}}_{ij})^{2}}}} , then it can be trivially minimized by setting f = 0 {\displaystyle f=0} , 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]
The data to be analyzed is a collection of M {\displaystyle M} 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 D {\displaystyle D} , to find M {\displaystyle M} vectors x 1 , … … --> , x M ∈ ∈ --> R N {\displaystyle x_{1},\ldots ,x_{M}\in \mathbb {R} ^{N}} such that
where ‖ ‖ --> ⋅ ⋅ --> ‖ ‖ --> {\displaystyle \|\cdot \|} 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.[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 M {\displaystyle M} objects into R N {\displaystyle \mathbb {R} ^{N}} such that distances are preserved. If the dimension N {\displaystyle N} is chosen to be 2 or 3, we may plot the vectors x i {\displaystyle x_{i}} to obtain a visualization of the similarities between the M {\displaystyle M} objects. Note that the vectors x i {\displaystyle x_{i}} are not unique: With the Euclidean distance, they may be arbitrarily translated, rotated, and reflected, since these transformations do not change the pairwise distances ‖ ‖ --> x i − − --> x j ‖ ‖ --> {\displaystyle \|x_{i}-x_{j}\|} .
(Note: The symbol R {\displaystyle \mathbb {R} } indicates the set of real numbers, and the notation R N {\displaystyle \mathbb {R} ^{N}} refers to the Cartesian product of N {\displaystyle N} copies of R {\displaystyle \mathbb {R} } , which is an N {\displaystyle N} -dimensional vector space over the field of the real numbers.)
There are various approaches to determining the vectors x i {\displaystyle x_{i}} . Usually, MDS is formulated as an optimization problem, where ( x 1 , … … --> , x M ) {\displaystyle (x_{1},\ldots ,x_{M})} 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.
Lokasi Pengunjung: 3.21.97.217