Tools for dimensionality reduction

Collaboration diagram for Tools for dimensionality reduction:

Classes
class	GenerateData
class	DimRedAlgorithm

Typedefs
typedef double(*	DimRedDistance2) (const Matrix2D< double > &X, size_t i1, size_t i2)

Enumerations
enum	DatasetType {   DatasetType::SWISS, DatasetType::HELIX, DatasetType::TWINPEAKS, DatasetType::CLUSTER3D,   DatasetType::INTERSECT }

Functions
void	computeDistance (const Matrix2D< double > &X, Matrix2D< double > &distance, DimRedDistance2 f=NULL, bool computeSqrt=true)
void	computeRandomPointsDistance (const Matrix2D< double > &X, Matrix1D< double > &distance, Matrix1D< int > ind1, Matrix1D< int > ind2, DimRedDistance2 f, bool computeSqrt)
void	computeDistanceToNeighbours (const Matrix2D< double > &X, int K, Matrix2D< double > &distance, DimRedDistance2 f=NULL, bool computeSqrt=true)
void	computeSimilarityMatrix (Matrix2D< double > &D2, double sigma, bool skipZeros=false, bool normalize=false)
void	computeGraphLaplacian (const Matrix2D< double > &G, Matrix2D< double > &L)
double	intrinsicDimensionality (Matrix2D< double > &X, const String &method="MLE", bool normalize=true, DimRedDistance2 f=NULL)
void	kNearestNeighbours (const Matrix2D< double > &X, int K, Matrix2D< int > &idx, Matrix2D< double > &distance, DimRedDistance2 f=NULL, bool computeSqrt=true)
void	extractNearestNeighbours (const Matrix2D< double > &X, Matrix2D< int > &idx, int i, Matrix2D< double > &Xi)

Detailed Description

Typedef Documentation

DimRedDistance2

typedef double(* DimRedDistance2) (const Matrix2D< double > &X, size_t i1, size_t i2)

Function type to compute the squared distance between individuals i1 and i2 of X

Definition at line 75 of file dimred_tools.h.

Enumeration Type Documentation

DatasetType

enum DatasetType

strong

Generate test data. Translated from drtools/generate_data.m http://homepage.tudelft.nl/19j49/Matlab_Toolbox_for_Dimensionality_Reduction.html

Original code by Laurens van der Maaten, Delft University of Technology

Enumerator
SWISS
HELIX
TWINPEAKS
CLUSTER3D
INTERSECT

Definition at line 42 of file dimred_tools.h.

{ SWISS, HELIX, TWINPEAKS, CLUSTER3D, INTERSECT};

Function Documentation

computeDistance()

void computeDistance	(	const Matrix2D< double > &	X,
		Matrix2D< double > &	distance,
		DimRedDistance2	f = NULL,
		bool	computeSqrt = true
	)

Compute the distance of all vs all elements in a matrix of observations. Each observation is a row of the matrix X.

Definition at line 274 of file dimred_tools.cpp.

{
    distance.initZeros(MAT_YSIZE(X),MAT_YSIZE(X));
    for (size_t i1=0; i1<MAT_YSIZE(X)-1; ++i1)
        for (size_t i2=i1+1; i2<MAT_YSIZE(X); ++i2)
        {
            // Compute the distance between i1 and i2
            double d=0;
            if (f==NULL)
                for (int j=0; j<MAT_XSIZE(X); ++j)
                {
                    double diff=MAT_ELEM(X,i1,j)-MAT_ELEM(X,i2,j);
                    d+=diff*diff;
                }
            else
                d=(*f)(X,i1,i2);

            if (computeSqrt)
                d=sqrt(d);
            MAT_ELEM(distance,i2,i1)=MAT_ELEM(distance,i1,i2)=d;
        }
}

computeDistanceToNeighbours()

void computeDistanceToNeighbours	(	const Matrix2D< double > &	X,
		int	K,
		Matrix2D< double > &	distance,
		DimRedDistance2	f = NULL,
		bool	computeSqrt = true
	)

Compute the distance of each observation to its K nearest neighbours. Each observation is a row of the matrix X. If there are N observations, the size of distance is NxN.

Definition at line 297 of file dimred_tools.cpp.

{
    Matrix2D<int> idx;
    Matrix2D<double> kDistance;
    kNearestNeighbours(X, K, idx, kDistance, f, computeSqrt);
    distance.initZeros(MAT_YSIZE(X),MAT_YSIZE(X));
    FOR_ALL_ELEMENTS_IN_MATRIX2D(kDistance)
    {
        int idx_ij=MAT_ELEM(idx,i,j);
        MAT_ELEM(distance,idx_ij,i)=MAT_ELEM(distance,i,idx_ij)=MAT_ELEM(kDistance,i,j);
    }
}

computeGraphLaplacian()

void computeGraphLaplacian	(	const Matrix2D< double > &	G,
		Matrix2D< double > &	L
	)

Compute graph laplacian. L=D-G where D is a diagonal matrix with the row sums of G.

Definition at line 329 of file dimred_tools.cpp.

{
    Matrix1D<double> d;
    G.rowSum(d);
    L.resizeNoCopy(G);
    FOR_ALL_ELEMENTS_IN_MATRIX2D(L)
        if (i==j)
            MAT_ELEM(L,i,i)=VEC_ELEM(d,i)-MAT_ELEM(G,i,i);
        else
            MAT_ELEM(L,i,j)=-MAT_ELEM(G,i,j);
}

computeRandomPointsDistance()

void computeRandomPointsDistance	(	const Matrix2D< double > &	X,
		Matrix1D< double > &	distance,
		Matrix1D< int >	ind1,
		Matrix1D< int >	ind2,
		DimRedDistance2	f,
		bool	computeSqrt
	)

Compute the distance of the elements said by the arrays ind1 and ind2

Definition at line 247 of file dimred_tools.cpp.

{
    distance.initZeros();
    int ii=0;
    for (size_t i1=0; i1<VEC_XSIZE(ind1); ++i1)
    {
        // Compute the distance between ind1[i] and ind2[i]
        double d=0;
        if (f==NULL){
            for (size_t j=0; j<MAT_XSIZE(X); ++j)
            {
            double diff=MAT_ELEM(X,ind1(i1),j)-MAT_ELEM(X,ind2(i1),j);
            d+=diff*diff;
            }
        }
        else
            d=(*f)(X,ind1(i1),ind2(i1));

        if (computeSqrt){
            d=sqrt(d);
        }

        distance(ii) = d;
        ii++;
    }
}

computeSimilarityMatrix()

void computeSimilarityMatrix	(	Matrix2D< double > &	D2,
		double	sigma,
		bool	skipZeros = false,
		bool	normalize = false
	)

Compute a similarity matrix from a squared distance matrix. dij=exp(-dij/(2*sigma^2)) The distance matrix can be previously normalized so that the maximum distance is 1

Definition at line 310 of file dimred_tools.cpp.

{
    double maxDistance=1.0;
    if (normalize)
        maxDistance=D2.computeMax();
    double K=-0.5/(sigma*sigma*maxDistance);
    if (skipZeros)
    {
        FOR_ALL_ELEMENTS_IN_MATRIX2D(D2)
            if (MAT_ELEM(D2,i,j)!=0)
                MAT_ELEM(D2,i,j)=exp(MAT_ELEM(D2,i,j)*K);
    }
    else
    {
        FOR_ALL_ELEMENTS_IN_MATRIX2D(D2)
            MAT_ELEM(D2,i,j)=exp(MAT_ELEM(D2,i,j)*K);
    }
}

extractNearestNeighbours()

void extractNearestNeighbours	(	const Matrix2D< double > &	X,
		Matrix2D< int > &	idx,
		int	i,
		Matrix2D< double > &	Xi
	)

Extract k-nearest neighbours. This function extracts from the matrix X, the neighbours given by idx for the i-th observation.

Definition at line 450 of file dimred_tools.cpp.

{
    Xi.resizeNoCopy(MAT_XSIZE(idx),MAT_XSIZE(X));
    for (int j=0; j<MAT_XSIZE(idx); ++j)
    {
        int jNeighbour=MAT_ELEM(idx,i,j);
        memcpy(&MAT_ELEM(Xi,j,0),&MAT_ELEM(X,jNeighbour,0),MAT_XSIZE(X)*sizeof(double));
    }
}

intrinsicDimensionality()

double intrinsicDimensionality	(	Matrix2D< double > &	X,
		const String &	method = "MLE",
		bool	normalize = true,
		DimRedDistance2	f = NULL
	)

Estimate the intrinsic dimensionality. Performs an estimation of the intrinsic dimensionality of dataset X based on the method specified by method. Possible values for method are 'CorrDim' (based on correlation dimension) and 'MLE' (maximum likelihood estimator). The default method is 'MLE'. All methods are parameterless.

Columns of the input matrix may be normalized to have zero mean and standard deviation 1.

Translated from drtools/intrinsic_dimensionality.m http://homepage.tudelft.nl/19j49/Matlab_Toolbox_for_Dimensionality_Reduction.html

Original code by Laurens van der Maaten, Delft University of Technology

Definition at line 432 of file dimred_tools.cpp.

{
    if (normalize)
        normalizeColumns(X);

    if (method=="MLE")
        return intrinsicDimensionalityMLE(X,f);
    else if (method=="CorrDim")
        return intrinsicDimensionalityCorrDim(X,f);
    else
        REPORT_ERROR(ERR_ARG_INCORRECT,"Unknown dimensionality estimate method");

    // I do not implement NearNbDim because it gives a wrong answer on the swiss roll
    // I do not implement PackingNumbers because it is too slow on the swiss roll and gives a wrong answer
    // I do not implement EigValue because it only provides integer dimensions
    // I do not implement GMST because it is slower than MLE and CorrDim
}

kNearestNeighbours()

void kNearestNeighbours	(	const Matrix2D< double > &	X,
		int	K,
		Matrix2D< int > &	idx,
		Matrix2D< double > &	distance,
		DimRedDistance2	f = NULL,
		bool	computeSqrt = true
	)

k-Nearest neighbours. Given a data matrix (each row is a sample, each column a variable), this function returns a matrix of the indexes of the K nearest neighbours to each one of the input samples sorted by distance. It also returns the corresponding distance.

The element i,j of the output matrices is the index(distance) of the j-th nearest neighbor to the i-th sample.

You can provide a distance function of your own. If not, Euclidean distance is used.

Definition at line 219 of file dimred_tools.cpp.

{
    K=std::min(K,(int)MAT_YSIZE(X)-1);
    idx.initConstant(MAT_YSIZE(X),K,-1);
    distance.initConstant(MAT_YSIZE(X),K,1e38);
    for (size_t i1=0; i1<MAT_YSIZE(X)-1; ++i1)
        for (size_t i2=i1+1; i2<MAT_YSIZE(X); ++i2)
        {
            // Compute the distance between i1 and i2
            double d=0;
            if (f==NULL)
                for (int j=0; j<MAT_XSIZE(X); ++j)
                {
                    double diff=MAT_ELEM(X,i1,j)-MAT_ELEM(X,i2,j);
                    d+=diff*diff;
                }
            else
                d=(*f)(X,i1,i2);

            // Check if they are nearest neighbours
            insertNeighbour(idx,distance,i1,i2,d);
            insertNeighbour(idx,distance,i2,i1,d);
        }
    if (computeSqrt)
        FOR_ALL_ELEMENTS_IN_MATRIX2D(distance)
            MAT_ELEM(distance,i,j)=sqrt(MAT_ELEM(distance,i,j));
}