Multidimensional scaling: Difference between revisions

Revision as of 01:59, 30 July 2023

Revision as of 02:14, 30 July 2023

Line 51:

===Non-metric multidimensional scaling (NMDS)===

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 relationship is typically found using [[isotonic regression]]: let <math display="inline">x</math> denote the vector of proximities, <math display="inline">f(x)</math> a monotonic transformation of <math display="inline">x</math>, and <math display="inline">d</math> the point distances; then coordinates have to be found, that minimize the so-called stress,

:<blockquote><math>\text{Stress}=\sqrt{\frac{\sum\bigl(f(x)-d\bigr)^2}{\sum d^2}}.</math></blockquote>

The factor ofLet <math>\sum d^2d_{ij}</math> inbe the denominatordissimilarity isbetween necessarypoints to<math>i, prevent a "collapse"j</math>. Suppose we define insteadLet <math>\texthat d_{Stressij} = \sqrt{\sum\bigl(f(x)| x_i -d x_j\bigr)^2}|</math>, thenbe itthe can beEuclidean triviallydistance minimizedbetween byembedded settingpoints <math>fx_i, = 0x_j</math>, then collapse every point to the same point.

Now, for each choice of the embedded points <math>x_i</math> and is a monotonically increasing function <math>f</math>, define the "stress" function:

:<blockquote><math>\text{Stress}S(x_1, ..., x_n; f)=\sqrt{\frac{\sumsum_{i<j}\bigl(f(xd_{ij})-d\hat d_{ij}\bigr)^2}{\sumsum_{i<j} d\hat d_{ij}^2}}.</math></blockquote>

The factor of <math>\sum_{i<j} \hat d_{ij}^2</math> in the denominator is necessary to prevent a "collapse". Suppose we define instead <math>S=\sqrt{\sum_{i<j}\bigl(f(d_{ij})-\hat d_{ij})^2}</math>, then it can be trivially minimized by setting <math>f = 0</math>, 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. The basic steps in a non-metric MDS algorithm are:

:# Find a random configuration of points, e. g. by sampling from a normal distribution.

NMDS needs to optimize two objectives simultaneously. This is usually done iteratively:

:# Calculate the distances d between the points.

:# FindInitialize a<math>x_i</math> random configuration of pointsrandomly, e. g. by sampling from a normal distribution.

:# Find the optimal monotonic transformation of the proximities, in order to obtain optimally scaled data <math display="inline">f(x)</math>.

:# Do until a stopping criterion (for example, <math>S < \epsilon</math>)

:# Minimize the stress between the optimally scaled data and the distances by finding a new configuration of points.

:## Solve for <math>f = \arg\min_f S(x_1, ..., x_n ; f)</math> by [[isotonic regression]].

:# Compare the stress to some criterion. If the stress is small enough then exit the algorithm else return to 2.

:## Solve for <math>x_1, ..., x_n = \arg\min_{x_1, ..., x_n} S(x_1, ..., x_n ; f)</math> by gradient descent or other methods.

:#Return <math>x_i</math> and <math>f</math>

[[Louis Guttman]]'s smallest space analysis (SSA) is an example of a non-metric MDS procedure.