Public Member Functions | Protected Member Functions | Static Protected Member Functions | Protected Attributes

CLocallyLinearEmbedding Class Reference

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:

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

Definition at line 63 of file LocallyLinearEmbedding.h.

Inheritance diagram for CLocallyLinearEmbedding:
Inheritance graph

List of all members.

Public Member Functions

 CLocallyLinearEmbedding ()
virtual ~CLocallyLinearEmbedding ()
virtual CFeaturesapply (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 ()
virtual SGMatrix< float64_tconstruct_weight_matrix (CSimpleFeatures< float64_t > *simple_features, float64_t *W_matrix, SGMatrix< int32_t > neighborhood_matrix)
virtual SGMatrix< float64_tconstruct_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)
static void * run_linearreconstruction_thread (void *p)

Protected Attributes

int32_t m_k
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


Definition at line 83 of file LocallyLinearEmbedding.cpp.

~CLocallyLinearEmbedding (  )  [virtual]


Definition at line 115 of file LocallyLinearEmbedding.cpp.

Member Function Documentation

CFeatures * apply ( CFeatures features  )  [virtual]

apply preprocessor to 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

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

matrix computed weight matrix
dimension dimension of embedding
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]

constructs weight matrix

simple_features features to be used
W_matrix weight matrix
neighborhood_matrix matrix containing neighbor idxs

Reimplemented in CHessianLocallyLinearEmbedding, and CLocalTangentSpaceAlignment.

Definition at line 322 of file LocallyLinearEmbedding.cpp.

int32_t estimate_k ( CSimpleFeatures< float64_t > *  simple_features,
SGMatrix< int32_t >  neighborhood_matrix 
) [protected]

estimates k using ternary search

simple_features simple features to use
neighborhood_matrix matrix containing indexes of neighbors for every vector
optimal k (in means of reconstruction error)

Definition at line 241 of file LocallyLinearEmbedding.cpp.

bool get_auto_k (  )  const

getter for auto_k parameter

m_auto_k value

Definition at line 146 of file LocallyLinearEmbedding.cpp.

int32_t get_k (  )  const

getter for k parameter

m_k value

Definition at line 125 of file LocallyLinearEmbedding.cpp.

int32_t get_max_k (  )  const

getter for max_k parameter

m_max_k value

Definition at line 136 of file LocallyLinearEmbedding.cpp.

const char * get_name (  )  const [virtual]
SGMatrix< int32_t > get_neighborhood_matrix ( SGMatrix< float64_t distance_matrix,
int32_t  k 
) [protected, virtual]

constructs neighborhood matrix by distance

distance_matrix distance matrix to be used
k number of neighbors
matrix containing indexes of neighbors of i-th vector in i-th column

Reimplemented in CKernelLocallyLinearEmbedding.

Definition at line 532 of file LocallyLinearEmbedding.cpp.

float64_t get_nullspace_shift (  )  const

getter for nullspace shift parameter

m_nullspace_shift value

Definition at line 156 of file LocallyLinearEmbedding.cpp.

float64_t get_reconstruction_shift (  )  const

getter for reconstruction shift parameter

m_reconstruction_shift value

Definition at line 166 of file LocallyLinearEmbedding.cpp.

bool get_use_arpack (  )  const

getter for use arpack parameter

use_arpack value

Definition at line 176 of file LocallyLinearEmbedding.cpp.

void init (  )  [protected]


default init

Reimplemented from CEmbeddingConverter.

Definition at line 99 of file LocallyLinearEmbedding.cpp.

void * run_linearreconstruction_thread ( void *  p  )  [static, protected]

runs linear reconstruction thread

p thread params

Reimplemented in CKernelLocallyLinearEmbedding.

Definition at line 450 of file LocallyLinearEmbedding.cpp.

void * run_neighborhood_thread ( void *  p  )  [static, protected]


runs neighborhood determination thread

p thread params

Reimplemented in CKernelLocallyLinearEmbedding.

Definition at line 591 of file LocallyLinearEmbedding.cpp.

void set_auto_k ( bool  auto_k  ) 

setter for auto_k parameter

auto_k auto_k value

Definition at line 141 of file LocallyLinearEmbedding.cpp.

void set_k ( int32_t  k  ) 

setter for k parameter

k k value

Definition at line 119 of file LocallyLinearEmbedding.cpp.

void set_max_k ( int32_t  max_k  ) 

setter for max_k parameter

max_k max_k value

Definition at line 130 of file LocallyLinearEmbedding.cpp.

void set_nullspace_shift ( float64_t  nullspace_shift  ) 

setter for nullspace shift parameter

nullspace_shift nullsapce shift value

Definition at line 151 of file LocallyLinearEmbedding.cpp.

void set_reconstruction_shift ( float64_t  reconstruction_shift  ) 

setter for reconstruction shift parameter

reconstruction_shift reconstruction shift value

Definition at line 161 of file LocallyLinearEmbedding.cpp.

void set_use_arpack ( bool  use_arpack  ) 

setter for use arpack parameter

use_arpack use arpack value

Definition at line 171 of file LocallyLinearEmbedding.cpp.

Member Data Documentation

bool m_auto_k [protected]

whether use automatic k or not

Definition at line 212 of file LocallyLinearEmbedding.h.

int32_t m_k [protected]


number of neighbors

Definition at line 197 of file LocallyLinearEmbedding.h.

int32_t m_max_k [protected]

maximum number of neighbors

Definition at line 200 of file LocallyLinearEmbedding.h.

regularization shift of nullspace finding step

Definition at line 206 of file LocallyLinearEmbedding.h.

regularization shift of reconstruction step

Definition at line 203 of file LocallyLinearEmbedding.h.

bool m_use_arpack [protected]

whether use arpack or not

Definition at line 209 of file LocallyLinearEmbedding.h.

The documentation for this class was generated from the following files:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

SHOGUN Machine Learning Toolbox - Documentation