PAST includes two methods for nonlinear ordination (embedding): spectral embedding and UMAP. These methods can be compared with e.g. Principal Coordinates Analysis, and are based on a distance measure. However, they can pick up groups having complicated shapes in high-dimensional space, possibly interfingering with other groups. These methods can be very good at identifying groups (often “too good”, causing oversplitting), but can also behave quite erratically, depending on analysis parameters.
The input is a multivariate data set with variables in columns, optionally with a group column for showing given groups (this does not influence the ordination). A distance measure must be chosen (default Euclidean).
Spectral embedding
The spectral embedding algorithm basically follows Belkin & Niyogi (2003). First, a graph is constructed where two points i and j are connected if and only if i is among the n nearest neighbours of j, or j is among the n nearest neighbours of i. The number n can be chosen by the user (“Embed neighbors”), and it can substantially influence the ordination. Larger n will tend to produce larger, less concentrated groups.
A matrix W is constructed, with Wij=1 if i and j are connected (adjacency matrix). If the “Embed kernel” option is selected, the values in this matrix are additionally scaled by a kernel function. Then compute the “graph Laplacian” L = D – W, where D is a diagonal matrix containing the row (or column, as W is symmetric) sums of W. Past uses the "normalized" graph Laplacian,
The scores on the two ordination axes are given by the two eigenvectors corresponding to the second smallest and third smallest eigenvalue.
UMAP
UMAP (McInnes et al. 2018) is a modern method for nonlinear ordination. The implementation in Past also builds on a description by Oskolkov (2019). The procedure is complex, for details see the references.
The implementation in Past uses a spectral embedding as starting condition, with parameters as given above. The “UMAP neighbors” (k) and the “Minimum distance” (min_dist) parameters can change the ordination quite a lot.
References
Belkin, M., Niyogi, P. 2003. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation 15:1373-1396.
McInnes, L., Healy, J., Melville, J. 2018. UMAP: Uniform Manifold Approximation and Projection for dimension reduction. https://arxiv.org/abs/1802.03426.
Oskolkov, N. 2019. How to program UMAP from scratch. https://towardsdatascience.com/how-to-program-umap-from-scratch-e6eff67f55fe