Introduced LPP (Locality Preserving Projections) converter

shogun-toolbox · Nov 1, 2011 · 20d5063 · 20d5063
1 parent 456d8c8
commit 20d5063
Show file tree

Hide file tree

Showing 8 changed files with 209 additions and 7 deletions.
diff --git a/examples/undocumented/libshogun/Makefile b/examples/undocumented/libshogun/Makefile
@@ -49,6 +49,7 @@ TARGETS =	  basic_minimal classifier_libsvm classifier_minimal_svm \
 		  converter_laplacianeigenmaps \
 		  converter_neighborhoodpreservingembedding \
 		  converter_linearlocaltangentspacealignment \
+		  converter_localitypreservingprojections \
 
 all: $(TARGETS)
 

diff --git a/examples/undocumented/libshogun/converter_localitypreservingprojections.cpp b/examples/undocumented/libshogun/converter_localitypreservingprojections.cpp
@@ -0,0 +1,39 @@
+/*
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * Written (W) 2011 Sergey Lisitsyn
+ * Copyright (C) 2011 Berlin Institute of Technology and Max-Planck-Society
+ */
+
+#include <shogun/base/init.h>
+#include <shogun/features/SimpleFeatures.h>
+#include <shogun/converter/LocalityPreservingProjections.h>
+
+using namespace shogun;
+
+int main(int argc, char** argv)
+{
+	init_shogun();
+
+	int N = 100;
+	int dim = 3;
+	float64_t* matrix = new double[N*dim];
+	for (int i=0; i<N*dim; i++)
+		matrix[i] = i;
+
+	CSimpleFeatures<double>* features = new CSimpleFeatures<double>(SGMatrix<double>(matrix,dim,N));
+	SG_REF(features);
+	CLocalityPreservingProjections* lpp = new CLocalityPreservingProjections();
+	lpp->set_target_dim(2);
+	lpp->set_k(10);
+	lpp->parallel->set_num_threads(4);
+	CSimpleFeatures<double>* embedding = lpp->embed(features);
+	SG_UNREF(embedding);
+	SG_UNREF(lpp);
+	SG_UNREF(features);
+	exit_shogun();
+	return 0;
+}
diff --git a/src/interfaces/modular/Converter.i b/src/interfaces/modular/Converter.i
@@ -18,6 +18,7 @@
 %rename(KernelLocalTangentSpaceAlignment) CKernelLocalTangentSpaceAlignment;
 %rename(DiffusionMaps) CDiffusionMaps;
 %rename(LaplacianEigenmaps) CLaplacianEigenmaps;
+%rename(LocalityPreservingProjections) CLocalityPreservingProjections;
 %rename(MultidimensionalScaling) CMultidimensionalScaling;
 %rename(Isomap) CIsomap;
 
@@ -34,6 +35,7 @@
 %include <shogun/converter/KernelLocalTangentSpaceAlignment.h>
 %include <shogun/converter/DiffusionMaps.h>
 %include <shogun/converter/LaplacianEigenmaps.h>
+%include <shogun/converter/LocalityPreservingProjections.h>
 %include <shogun/converter/MultidimensionalScaling.h>
 %include <shogun/converter/Isomap.h>
 
diff --git a/src/interfaces/modular/Converter_includes.i b/src/interfaces/modular/Converter_includes.i
@@ -10,6 +10,7 @@
 #include <shogun/converter/KernelLocalTangentSpaceAlignment.h>
 #include <shogun/converter/DiffusionMaps.h>
 #include <shogun/converter/LaplacianEigenmaps.h>
+#include <shogun/converter/LocalityPreservingProjections.h>
 #include <shogun/converter/MultidimensionalScaling.h>
 #include <shogun/converter/Isomap.h>
 %}
diff --git a/src/shogun/converter/LaplacianEigenmaps.cpp b/src/shogun/converter/LaplacianEigenmaps.cpp
@@ -79,13 +79,13 @@ CFeatures* CLaplacianEigenmaps::apply(CFeatures* features)
 	// compute distance matrix
 	ASSERT(m_distance);
 	m_distance->init(features,features);
-	CSimpleFeatures<float64_t>* embedding = embed_distance(m_distance);
+	CSimpleFeatures<float64_t>* embedding = embed_distance(m_distance,features);
 	m_distance->remove_lhs_and_rhs();
 	SG_UNREF(features);
 	return (CFeatures*)embedding;
 }
 
-CSimpleFeatures<float64_t>* CLaplacianEigenmaps::embed_distance(CDistance* distance)
+CSimpleFeatures<float64_t>* CLaplacianEigenmaps::embed_distance(CDistance* distance, CFeatures* features)
 {
 	int32_t i,j;
 	SGMatrix<float64_t> W_sgmatrix = distance->get_distance_matrix();
@@ -151,13 +151,14 @@ CSimpleFeatures<float64_t>* CLaplacianEigenmaps::embed_distance(CDistance* dista
 	}
 
 	// compute D
-	CSimpleFeatures<float64_t>* embedding = construct_embedding(W_sgmatrix);
+	CSimpleFeatures<float64_t>* embedding = construct_embedding(features,W_sgmatrix);
 	W_sgmatrix.destroy_matrix();
 
 	return embedding;
 }
 
-CSimpleFeatures<float64_t>* CLaplacianEigenmaps::construct_embedding(SGMatrix<float64_t> W_matrix)
+CSimpleFeatures<float64_t>* CLaplacianEigenmaps::construct_embedding(CFeatures* features,
+                                                                     SGMatrix<float64_t> W_matrix)
 {
 	int32_t i,j;
 	int32_t N = W_matrix.num_cols;
@@ -222,6 +223,7 @@ CSimpleFeatures<float64_t>* CLaplacianEigenmaps::construct_embedding(SGMatrix<fl
 			#endif
 		}
 	}
+	return new CSimpleFeatures<float64_t>(new_features);
 }
 
 #endif /* HAVE_LAPACK */
diff --git a/src/shogun/converter/LaplacianEigenmaps.h b/src/shogun/converter/LaplacianEigenmaps.h
@@ -64,7 +64,7 @@ class CLaplacianEigenmaps: public CEmbeddingConverter
 	 * @param distance to use for embedding
 	 * @param embedding features
 	 */
-	virtual CSimpleFeatures<float64_t>* embed_distance(CDistance* distance);
+	virtual CSimpleFeatures<float64_t>* embed_distance(CDistance* distance, CFeatures* features=NULL);
 
 	/** setter for K parameter
 	 * @param k k value
@@ -94,10 +94,12 @@ class CLaplacianEigenmaps: public CEmbeddingConverter
 	/** init */
 	void init();
 
-	/** construct embedding 
+	/** construct embedding
+	 * @param features features
 	 * @param W_matrix W matrix to be used
 	 */
-	CSimpleFeatures<float64_t>* construct_embedding(SGMatrix<float64_t> W_matrix);
+	virtual CSimpleFeatures<float64_t>* construct_embedding(CFeatures* features, 
+	                                                        SGMatrix<float64_t> W_matrix);
 
 protected:
 

diff --git a/src/shogun/converter/LocalityPreservingProjections.cpp b/src/shogun/converter/LocalityPreservingProjections.cpp
@@ -0,0 +1,105 @@
+/*
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * Written (W) 2011 Sergey Lisitsyn
+ * Copyright (C) 2011 Berlin Institute of Technology and Max-Planck-Society
+ */
+
+#include <shogun/converter/LocalityPreservingProjections.h>
+#ifdef HAVE_LAPACK
+#include <shogun/mathematics/arpack.h>
+#include <shogun/mathematics/lapack.h>
+#include <shogun/lib/FibonacciHeap.h>
+#include <shogun/mathematics/Math.h>
+#include <shogun/io/SGIO.h>
+#include <shogun/distance/Distance.h>
+#include <shogun/lib/Signal.h>
+
+using namespace shogun;
+
+CLocalityPreservingProjections::CLocalityPreservingProjections() :
+		CLaplacianEigenmaps()
+{
+}
+
+CLocalityPreservingProjections::~CLocalityPreservingProjections()
+{
+}
+
+const char* CLocalityPreservingProjections::get_name() const 
+{ 
+	return "LocalityPreservingProjections";
+};
+
+CSimpleFeatures<float64_t>* CLocalityPreservingProjections::construct_embedding(CFeatures* features,
+                                                                                SGMatrix<float64_t> W_matrix)
+{
+	CSimpleFeatures<float64_t>* simple_features = (CSimpleFeatures<float64_t>*)features;
+	ASSERT(simple_features);
+	int i,j;
+	int N = simple_features->get_num_vectors();
+	int dim = simple_features->get_num_features();
+
+	float64_t* D_diag_vector = SG_CALLOC(float64_t, N);
+	for (i=0; i<N; i++)
+	{
+		for (j=0; j<N; j++)
+			D_diag_vector[i] += W_matrix[i*N+j];
+	}
+
+	// W = -W
+	for (i=0; i<N*N; i++)
+		if (W_matrix[i]>0.0)
+			W_matrix[i] *= -1.0;
+	// W = W + D
+	for (i=0; i<N; i++)
+		W_matrix[i*N+i] += D_diag_vector[i];
+
+	SGMatrix<float64_t> feature_matrix = simple_features->get_feature_matrix();
+	float64_t* XTM = SG_MALLOC(float64_t, dim*N);
+	float64_t* lhs_M = SG_MALLOC(float64_t, dim*dim);
+	float64_t* rhs_M = SG_MALLOC(float64_t, dim*dim);
+
+	cblas_dgemm(CblasColMajor,CblasNoTrans,CblasNoTrans,dim,N,N,1.0,feature_matrix.matrix,dim,W_matrix.matrix,N,0.0,XTM,dim);
+	cblas_dgemm(CblasColMajor,CblasNoTrans,CblasTrans,dim,dim,N,1.0,XTM,dim,feature_matrix.matrix,dim,0.0,lhs_M,dim);
+
+	for (i=0; i<N; i++)
+		cblas_dscal(dim,D_diag_vector[i],feature_matrix.matrix+i*dim,1);
+
+	cblas_dgemm(CblasColMajor,CblasNoTrans,CblasTrans,dim,dim,N,1.0,feature_matrix.matrix,dim,feature_matrix.matrix,dim,0.0,rhs_M,dim);
+
+	for (i=0; i<N; i++)
+		cblas_dscal(dim,1.0/D_diag_vector[i],feature_matrix.matrix+i*dim,1);
+
+	float64_t* evals = SG_MALLOC(float64_t, dim);
+	float64_t* evectors = SG_MALLOC(float64_t, m_target_dim*dim);
+	int32_t info = 0;
+#ifdef HAVE_ARPACK
+	arpack_dsxupd(lhs_M,rhs_M,false,dim,m_target_dim,"LA",false,3,true,-1e-9,0.0,
+	              evals,evectors,info);
+#else
+	wrap_dsygvx(1,'V','U',dim,lhs_M,dim,rhs_M,dim,dim-m_target_dim+1,dim,evals,evectors,&info);
+#endif
+	SG_FREE(lhs_M);
+	SG_FREE(rhs_M);
+	SG_FREE(evals);
+	if (info!=0) SG_ERROR("Failed to solve eigenproblem (%d)\n",info);
+
+	cblas_dgemm(CblasColMajor,CblasTrans,CblasNoTrans,N,m_target_dim,dim,1.0,feature_matrix.matrix,dim,evectors,dim,0.0,XTM,N);
+	SG_FREE(evectors);
+
+	SGMatrix<float64_t> new_features(m_target_dim,N);
+	for (i=0; i<m_target_dim; i++)
+	{
+		for (j=0; j<N; j++)
+			new_features[j*m_target_dim+i] = XTM[i*N+j];
+	}
+	SG_FREE(D_diag_vector);
+	SG_FREE(XTM);
+	return new CSimpleFeatures<float64_t>(new_features);
+}
+
+#endif /* HAVE_LAPACK */
diff --git a/src/shogun/converter/LocalityPreservingProjections.h b/src/shogun/converter/LocalityPreservingProjections.h
@@ -0,0 +1,50 @@
+/*
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * Written (W) 2011 Sergey Lisitsyn
+ * Copyright (C) 2011 Berlin Institute of Technology and Max-Planck-Society
+ */
+
+#ifndef LOCALITYPRESERVINGPROJECTIONS_H_
+#define LOCALITYPRESERVINGPROJECTIONS_H_
+#include <shogun/lib/config.h>
+#ifdef HAVE_LAPACK
+#include <shogun/converter/LaplacianEigenmaps.h>
+
+namespace shogun
+{
+
+class CFeatures;
+class CDistance;
+
+/** @brief  */
+class CLocalityPreservingProjections: public CLaplacianEigenmaps
+{
+public:
+
+	/** constructor */
+	CLocalityPreservingProjections();
+
+	/** destructor */
+	virtual ~CLocalityPreservingProjections();
+
+	 	/** get name */
+	virtual const char* get_name() const;
+
+protected:
+
+	/** construct embedding 
+	 * @param features features
+	 * @param W_matrix W matrix to be used
+	 */
+	virtual CSimpleFeatures<float64_t>* construct_embedding(CFeatures* features, 
+	                                                        SGMatrix<float64_t> W_matrix);
+
+};
+}
+
+#endif /* HAVE_LAPACK */
+#endif /* LOCALITYPRESERVINGPROJECTIONS_H_ */