lle {seriation}

Locally Linear Embedding (LLE)

Description

Performs the non linear dimensionality reduction method locally linear embedding proposed in Roweis and Saul (2000).

Usage

lle(x, m, k, reg = 2)

Arguments

x

a matrix.

m

dimensions of the desired embedding.

k

number of neighbors.

reg

regularization method. 1, 2 and 3, by default 2. See details.

Details

LLE tries to find a lower-dimensional projection which preserves distances within local neighborhoods. This is done by (1) find for each object the k nearest neighbors, (2) construct the LLE weight matrix which represents each point as a linear combination of its neighborhood, and (2) perform partial eigenvalue decomposition to find the embedding.

The reg parameter allows the decision between different regularization methods. As one step of the LLE algorithm, the inverse of the Gram-matrix G\in R^{kxk} has to be calculated. The rank of G equals m which is mostly smaller than k - this is why a regularization G^{(i)}+r\cdot I should be performed. The calculation of regularization parameter r can be done using different methods:

• reg = 1: standardized sum of eigenvalues of G (Roweis and Saul; 2000)

• reg = 2 (default): trace of Gram-matrix divided by k (Grilli, 2007)

• reg = 3: constant value 3*10e-3

Value

a matrix of vector with the embedding.

Author(s)

Michael Hahsler (based on code by Holger Diedrich and Markus Abel)

References

Roweis, Sam T. and Saul, Lawrence K. (2000), Nonlinear Dimensionality Reduction by Locally Linear Embedding, Science, 290(5500), 2323–2326. doi:10.1126/science.290.5500.2323

Grilli, Elisa (2007) Automated Local Linear Embedding with an application to microarray data, Dissertation thesis, University of Bologna. doi:10.6092/unibo/amsdottorato/380

Examples

data(iris)
x <- iris[, -5]

# project iris on 2 dimensions
conf <- lle(x, m = 2, k = 30)
conf

plot(conf, col = iris[, 5])

# project iris onto a single dimension
conf <- lle(x, m = 1, k = 30)
conf

plot_config(conf, col = iris[, 5], labels = FALSE)