Reduce dimensions

Status

Variants

Factorise a matrix into low-rank parts

Split a matrix into two or three low-rank factor matrices, as SVD and non-negative matrix factorisation do.

Project rows onto fewer dimensions

Replace many numeric columns with a few components or coordinates for each row, as PCA, MDS or ICA do.

What other tools call it

Meridian's classification; an independent blind rating agreed on 86.2% of 312 rows (exact class, version 2).

Background

When to use it

Working in high-dimensional spaces can be undesirable because raw data are often sparse, as a consequence of the curse of dimensionality.^[1] For high-dimensional datasets, dimension reduction is usually performed before applying a k-nearest neighbours (k-NN) algorithm, to mitigate the curse of dimensionality.^[1] Principal component analysis (PCA) is most commonly used when many of the variables are highly correlated with each other and it is desirable to reduce their number to an independent set.^[2]

PCA is sensitive to the scaling of the variables, so when variables have different units, such as temperature and mass, PCA is a somewhat arbitrary method of analysis.^[2] Scaling each variable to a variance of 1 before PCA affects the components PCA calculates, but makes them independent of the units used to measure the variables.^[2] Standardise columns measured in different units before running PCA, and keep that choice alongside the result. (Meridian's view) The new variables PCA produces cannot be interpreted in the same way as the original variables.^[2]

t-distributed stochastic neighbor embedding (t-SNE) is a nonlinear technique useful for visualising high-dimensional datasets, but it is not recommended for analysis such as clustering or outlier detection.^[1] A t-SNE parameter called perplexity says, loosely, how to balance attention between local and global aspects of the data.^[3] Visual clusters in a t-SNE plot can be strongly influenced by the chosen perplexity, and such clusters can appear even in data with no clear clustering.^[4] In a t-SNE plot, the size of clusters is not informative, and neither is the distance between clusters.^[4] Getting the most from t-SNE may mean analysing several plots made with different perplexities.^[3]

Uniform Manifold Approximation and Projection (UMAP) is a stochastic algorithm, so different runs of UMAP can produce different results.^[5] UMAP lets the user set a random seed state so that results can be reproduced exactly.^[5] UMAP, like t-SNE, does not completely preserve density, and UMAP can create false tears in clusters, giving a finer clustering than is necessarily present in the data.^[6] Using UMAP as a preprocessing step for density-based clustering is somewhat controversial and should be attempted with care.^[6] Treat a cluster seen in a t-SNE or UMAP picture as a lead to check against the original columns, not as a finding in itself. (Meridian's view)

The method

Feature projection, also called feature extraction, transforms the data from the high-dimensional space to a space of fewer dimensions.^[1] PCA performs a linear mapping of the data to a lower-dimensional space in such a way that the variance of the data in the low-dimensional representation is maximised.^[1] The first principal component is the linear combination of the original variables that explains the most variance, and the second explains the most variance in what is left once the first is removed.^[2] The principal components are often computed by eigendecomposition of the data covariance matrix or by singular value decomposition (SVD) of the data matrix.^[2] PCA was invented in 1901 by Karl Pearson, and was later independently developed and named by Harold Hotelling in the 1930s.^[2]

Non-negative matrix factorisation (NMF) decomposes a non-negative matrix into the product of two non-negative matrices.^[1] NMF has been a promising tool in fields where only non-negative signals exist, such as astronomy.^[1] Manifold learning techniques such as Isomap and locally linear embedding (LLE) assume that the high-dimensional input data lies near a low-dimensional manifold embedded in the ambient space.^[1]

t-SNE first builds a probability distribution over pairs of high-dimensional objects, then defines a similar distribution over the points in the low-dimensional map and minimises the Kullback–Leibler divergence between the two.^[4] t-SNE is based on Stochastic Neighbor Embedding, developed by Geoffrey Hinton and Sam Roweis, and Laurens van der Maaten and Hinton proposed the t-distributed variant.^[4] For a data set with n elements, t-SNE runs in O(n²) time and requires O(n²) space.^[4]

UMAP rests on three assumptions: the data is uniformly distributed on a Riemannian manifold, the Riemannian metric is locally constant or can be approximated as such, and the manifold is locally connected.^[7] UMAP finds its embedding by searching for a low-dimensional projection of the data that has the closest possible equivalent fuzzy topological structure.^[7] UMAP was described by Leland McInnes, John Healy and James Melville in a paper first submitted to arXiv on 9 February 2018.^[8]

Compared with the alternatives

Feature selection, a different route to fewer dimensions, aims to find a suitable subset of the input variables for the task at hand.^[1] Where a result must keep columns a reader can name, selecting features suits better than projecting them into new ones. (Meridian's view)

Classical multidimensional scaling (MDS) is identical to PCA, while Isomap uses geodesic distances in the data space.^[1] PCA is closely related to factor analysis, which typically incorporates more domain-specific assumptions about the underlying structure.^[2] Linear discriminant analysis (LDA) finds a linear combination of features that characterises or separates two or more classes of objects or events.^[1] Where rows carry a class label and the aim is to tell the classes apart, LDA is a closer fit than PCA. (Meridian's view)

UMAP is competitive with t-SNE for visualisation quality, and arguably preserves more of the global structure with superior run time performance.^[8] UMAP has no computational restrictions on embedding dimension, which makes it viable as a general-purpose dimension reduction technique for machine learning.^[8]

Sources

1. [1]Dimensionality reduction - Wikipediasecondary source
2. [2]Principal component analysis - Wikipediasecondary source
3. [3]How to Use t-SNE Effectivelysecondary source
4. [4]t-distributed stochastic neighbor embedding - Wikipediasecondary source
5. [5]UMAP Reproducibility — umap 0.6.0 documentationdocumentation
6. [6]Using UMAP for Clustering — umap 0.6.0 documentationdocumentation
7. [7]UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction — umap 0.6.0 documentationdocumentation
8. [8][1802.03426] UMAP: Uniform Manifold Approximation and Projection for Dimension Reductionsecondary source

Used in