Articles
Posts Tags Categories Random
Partners
About
About Author Portfolio Terms of Use Privacy Policy Time Travel Donate
More
Settings Funny Tools Useful Websites Student Works Message Board Recent Comments

Contents

Multi-dimensional Scaling

 Included in Machine Learning
 Published   Updated    1034 words   5 minutes   views
https://raw.githubusercontent.com/Josh-test-lab/website-assets-repository/main/posts/Multi-Dimensional%20Scaling/cover%20image.png

The cover image was generated by ChatGPT as a visualization of multidimensional scaling, with the following prompt “A digital visualization illustrates multidimensional scaling (MDS): On the left side, a glowing cluster of colorful points is arranged in 3D space with a dark starry background, symbolizing high-dimensional data. On the right side, a clean white 2D grid contains the same points projected into 2D space. Thin lines connect each 3D point to its corresponding 2D location, showing dimensionality reduction. Futuristic, scientific style, 16:9 aspect ratio.”.

Introduction

Multi-dimensional Scaling (MDS) is a dimensionality reduction technique that calculates pairwise distances between objects in a dataset and represents them in a lower-dimensional space while preserving the original relative distance structure. MDS can be seen as a method for visualizing data to intuitively observe the relative relationships between data points.

Principles of MDS

MDS transforms samples in a dataset $\mathbf{X}$ into a distance matrix $\mathbf{D}$ using various distance functions, such as Euclidean distance. Then, by converting the distance matrix into an inner product matrix $\mathbf{B}$ and performing eigen decomposition, we retain the top $r$ positive eigenvalues and eigenvectors to obtain the $r$-dimensional coordinates $x_i$ of each sample in the reduced space.

Below is a detailed explanation of classical MDS implementation.

Example

Suppose we have the dataset

$$ \mathbf{X} = (x_1, x_2, \cdots, x_n), $$

where $x_i = (x_{i1}, x_{i2}, \cdots, x_{ip})^\top$, for $i = 1, 2, \cdots, n$. The matrix $\mathbf{X}$ is of size $n \times p$, and $x_{ik}$ denotes the observation of the $i$-th sample on the $k$-th variable, where $k = 1, 2, \cdots, p$.

Distance Matrix

First, we compute the pairwise distances between samples in the dataset. Common distance metrics include:

  • Euclidean Distance

    $$ \begin{align*} d_{ij} = \|x_i - x_j\| & = \sqrt{(x_{i1} - x_{j1})^2 + (x_{i2} - x_{j2})^2 + \cdots + (x_{ip} - x_{jp})^2} \\ & = \sqrt{ \sum_{k=1}^{p} (x_{ik} - x_{jk})^2 }, \end{align*} $$

    where $i, j = 1, 2, \cdots, n$ indicate the distance between samples $x_i$ and $x_j$.

    Euclidean distance is the most commonly used metric.

  • Manhattan Distance

    $$ d_{ij} = \sum_{k=1}^{p} |x_{ik} - x_{jk}|. $$

    Manhattan Distance also known as City Block Distance.

  • Cosine Distance

    $$ d_{ij} = 1 - \frac{ \sum_{k=1}^p x_{ik} x_{jk} }{ \|x_i\| \cdot \|x_j\| }, $$

    where $\|x_i\| = \sqrt{\sum_{k=1}^p x_{ik}^2}$ is the L2 norm (Euclidean norm) of vector $x_i$.

    Cosine distance measures the angle between vectors and is commonly used in text analysis and high-dimensional sparse data.

Using one of these formulas, we obtain the distance matrix $\mathbf{D}$:

$$ \mathbf{D} = \begin{pmatrix} d_{11} & d_{12} & \cdots & d_{1n} \\ d_{21} & d_{22} & \cdots & d_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ d_{n1} & d_{n2} & \cdots & d_{nn} \end{pmatrix}, $$

where $\mathbf{D} \in \mathbb{R}^{n \times n}$ and $d_{ij}$ is the distance between samples $x_i$ and $x_j$. $\mathbf{D}$ is a symmetric matrix with diagonal elements $d_{ii} = 0$.

Double Centering

Next, to recover the inner product structure between samples, we square the distance matrix to obtain the squared proximity matrix $\mathbf{D}^{(2)}$.

$$ \mathbf{D}^{(2)} = \begin{pmatrix} d_{11}^2 & d_{12}^2 & \cdots & d_{1n}^2 \\ d_{21}^2 & d_{22}^2 & \cdots & d_{2n}^2 \\ \vdots & \vdots & \ddots & \vdots \\ d_{n1}^2 & d_{n2}^2 & \cdots & d_{nn}^2 \end{pmatrix}. $$

Assuming all samples come from a centered space, we can derive the inner product matrix $\mathbf{B}$ using

$$ \mathbf{B} = - \frac{1}{2} \mathbf{C} \mathbf{D}^{(2)} \mathbf{C}, $$

where $\mathbf{C} = \mathbf{I} - \frac{1}{n} \mathbf{J}_n$ is the centering matrix, $\mathbf{I}$ is the $n \times n$ identity matrix, and $\mathbf{J}$ is an all-ones matrix:

$$ \mathbf{I} = \begin{pmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{pmatrix}, \qquad \mathbf{J} = \begin{pmatrix} 1 & 1 & \cdots & 1 \\ 1 & 1 & \cdots & 1 \\ \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & \cdots & 1 \end{pmatrix}. $$

This process is known as double centering, which removes the row and column means of the dataset and shifts the origin to the center. Each element $b_{ij}$ in $\mathbf{B}$ represents the inner product between samples $x_i$ and $x_j$:

$$ b_{ij} = x_i^\top x_j. $$

Eigen Decomposition

We then perform eigen decomposition on the inner product matrix $\mathbf{B}$:

$$ \mathbf{B} = \mathbf{V} \mathbf{\Lambda} \mathbf{V}^\top, $$

where $\mathbf{\Lambda} = \mathrm{diag}(\lambda_1, \lambda_2, \cdots, \lambda_n)$ is the diagonal matrix of eigenvalues ordered as $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$, and $\mathbf{V} = (v_1, v_2, \cdots, v_n)$ is the matrix of orthogonal eigenvectors.

Dimensionality Reduction and New Coordinates

Now we decide on the reduced dimension $r$. We retain the top $r$ largest positive eigenvalues and their corresponding eigenvectors to perform the dimensionality reduction. The new low-dimensional coordinates $\mathbf{X}_r$ are given by

$$ \mathbf{X}_r = \mathbf{V}_r \mathbf{\Lambda}_r^{1/2}, $$

where $\mathbf{X}_r$ contains the coordinates of each sample in the $r$-dimensional space, with each row representing one sample. $\mathbf{V}_r$ is the $n \times r$ matrix of the top $r$ eigenvectors, and $\mathbf{\Lambda}_r$ is the $r \times r$ diagonal matrix of the top $r$ eigenvalues.

This completes the dimensionality reduction process using MDS. If we reduce to 2D or 3D, the results can be plotted as scatterplots to help visualize data clusters or structures. If the dataset includes class labels, different colors can be used to represent different groups or sample types for easier identification.

Since MDS preserves only relative distances, the result can be arbitrarily rotated, translated, or reflected without affecting its interpretation. The MDS scatterplot can also be aligned with real-world coordinates to interpret spatial or structural relationships among samples.

Conclusion

MDS offers an intuitive way to transform relationships among samples from high-dimensional space into a lower-dimensional space while preserving relative distance structures. It is well-suited for visualizing high-dimensional data, making it easier to observe, interpret, and analyze patterns among samples. MDS is a valuable tool for data analysis and visualization.

References

Updated on 2025-05-15 22:34 UTC+0800   eb9a1634
Creative Commons License
 Machine Learning, Multivariate Analysis, Multi-Dimensional Scaling
Back | Home