Detailed Description

the class LocallyLinearEmbedding used to preprocess data using Locally Linear Embedding algorithm described in

Saul, L. K., Ave, P., Park, F., & Roweis, S. T. (2001). An Introduction to Locally Linear Embedding. Available from, 290(5500), 2323-2326. Retrieved from: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.123.7319&rep=rep1&type=pdf

The process of finding nearest neighbors is parallel and involves Fibonacci Heap and Euclidian distance.

Linear reconstruction step runs in parallel for objects and involves LAPACK routine DPOSV for solving a system of linear equations.

The eigenproblem stated in the algorithm is solved with LAPACK routine DSYEVR or with ARPACK DSAUPD/DSEUPD routines if available.

Due to computation speed, ARPACK is being used with small regularization of weight matrix and Cholesky factorization is used internally for Lanzcos iterations (in case of only LAPACK is available) and SUPERLU library for fast solving sparse equations stated by ARPACK is being used if available.

This class also have capability of selecting k automatically in range between "k" and "max_k" in case if "auto_k" is true. This is being done using ternary search of minima of the mean reconstruction error. The reconstruction error is considered to have only one global minimum in this mode.

It is optimized with alignment formulation as described in

Zhao, D. (2006). Formulating LLE using alignment technique. Pattern Recognition, 39(11), 2233-2235. Retrieved from http://linkinghub.elsevier.com/retrieve/pii/S0031320306002160

Definition at line 63 of file LocallyLinearEmbedding.h.

Inheritance diagram for CLocallyLinearEmbedding:

[legend]

List of all members.

Public Member Functions
	CLocallyLinearEmbedding ()
virtual	~CLocallyLinearEmbedding ()
virtual CFeatures *	apply (CFeatures *features)
void	set_k (int32_t k)
int32_t	get_k () const
void	set_max_k (int32_t max_k)
int32_t	get_max_k () const
void	set_auto_k (bool auto_k)
bool	get_auto_k () const
void	set_reconstruction_shift (float64_t reconstruction_shift)
float64_t	get_reconstruction_shift () const
void	set_nullspace_shift (float64_t nullspace_shift)
float64_t	get_nullspace_shift () const
void	set_use_arpack (bool use_arpack)
bool	get_use_arpack () const
virtual const char *	get_name () const
Protected Member Functions
void	init ()
	HELPERS.
virtual SGMatrix< float64_t >	construct_weight_matrix (CSimpleFeatures< float64_t > simple_features, float64_t W_matrix, SGMatrix< int32_t > neighborhood_matrix)
virtual SGMatrix< float64_t >	construct_embedding (SGMatrix< float64_t > matrix, int dimension)
virtual SGMatrix< int32_t >	get_neighborhood_matrix (SGMatrix< float64_t > distance_matrix, int32_t k)
int32_t	estimate_k (CSimpleFeatures< float64_t > *simple_features, SGMatrix< int32_t > neighborhood_matrix)
float64_t	compute_reconstruction_error (int32_t k, int dim, int N, float64_t feature_matrix, float64_t z_matrix, float64_t covariance_matrix, float64_t resid_vector, float64_t *id_vector, SGMatrix< int32_t > neighborhood_matrix)
Static Protected Member Functions
static void *	run_neighborhood_thread (void *p)
	THREADS.
static void *	run_linearreconstruction_thread (void *p)
Protected Attributes
int32_t	m_k
	FIELDS.
int32_t	m_max_k
float64_t	m_reconstruction_shift
float64_t	m_nullspace_shift
bool	m_use_arpack
bool	m_auto_k

Constructor & Destructor Documentation

CLocallyLinearEmbedding ( )

constructor

Definition at line 83 of file LocallyLinearEmbedding.cpp.

~CLocallyLinearEmbedding ( ) [virtual]

destructor

Definition at line 115 of file LocallyLinearEmbedding.cpp.

Member Function Documentation

CFeatures * apply ( CFeatures * features ) [virtual]

apply preprocessor to features

Parameters:

features

Implements CEmbeddingConverter.

Reimplemented in CKernelLocallyLinearEmbedding.

Definition at line 186 of file LocallyLinearEmbedding.cpp.

float64_t compute_reconstruction_error	(	int32_t	k,
		int	dim,
		int	N,
		float64_t *	feature_matrix,
		float64_t *	z_matrix,
		float64_t *	covariance_matrix,
		float64_t *	resid_vector,
		float64_t *	id_vector,
		SGMatrix< int32_t >	neighborhood_matrix
	)			`[protected]`

computes reconstruction error using subset of given features

Parameters:

	k
	dim
	N
	feature_matrix
	z_matrix
	covariance_matrix
	resid_vector
	id_vector
	neighborhood_matrix

Returns:: residual sum

Definition at line 278 of file LocallyLinearEmbedding.cpp.

SGMatrix< float64_t > construct_embedding	(	SGMatrix< float64_t >	matrix,
		int	dimension
	)			`[protected, virtual]`

constructs embedding

Parameters:

	matrix	computed weight matrix
	dimension	dimension of embedding

Returns:: embedding features

Definition at line 397 of file LocallyLinearEmbedding.cpp.

SGMatrix< float64_t > construct_weight_matrix	(	CSimpleFeatures< float64_t > *	simple_features,
		float64_t *	W_matrix,
		SGMatrix< int32_t >	neighborhood_matrix
	)			`[protected, virtual]`