dimred_tools.cpp File Reference

#include <random>
#include <algorithm>
#include "dimred_tools.h"
#include "core/xmipp_funcs.h"

Include dependency graph for dimred_tools.cpp:

Go to the source code of this file.

Functions
void	insertNeighbour (Matrix2D< int > &idx, Matrix2D< double > &distance, int i1, int i2, double d)
void	kNearestNeighbours (const Matrix2D< double > &X, int K, Matrix2D< int > &idx, Matrix2D< double > &distance, DimRedDistance2 f, bool computeSqrt)
void	computeRandomPointsDistance (const Matrix2D< double > &X, Matrix1D< double > &distance, Matrix1D< int > ind1, Matrix1D< int > ind2, DimRedDistance2 f, bool computeSqrt)
void	computeDistance (const Matrix2D< double > &X, Matrix2D< double > &distance, DimRedDistance2 f, bool computeSqrt)
void	computeDistanceToNeighbours (const Matrix2D< double > &X, int K, Matrix2D< double > &distance, DimRedDistance2 f, bool computeSqrt)
void	computeSimilarityMatrix (Matrix2D< double > &D2, double sigma, bool skipZeros, bool normalize)
void	computeGraphLaplacian (const Matrix2D< double > &G, Matrix2D< double > &L)
double	intrinsicDimensionalityMLE (const Matrix2D< double > &X, DimRedDistance2 f)
double	intrinsicDimensionalityCorrDim (const Matrix2D< double > &X, DimRedDistance2 f)
double	intrinsicDimensionality (Matrix2D< double > &X, const String &method, bool normalize, DimRedDistance2 f)
void	extractNearestNeighbours (const Matrix2D< double > &X, Matrix2D< int > &idx, int i, Matrix2D< double > &Xi)

Function Documentation

insertNeighbour()

void insertNeighbour	(	Matrix2D< int > &	idx,
		Matrix2D< double > &	distance,
		int	i1,
		int	i2,
		double	d
	)

Definition at line 197 of file dimred_tools.cpp.

{
    int K=MAT_XSIZE(idx);
    int kInsert=K;
    for (int k=K-1; k>=0; --k)
        if (MAT_ELEM(distance,i1,k)>d)
            kInsert=k;
        else
            break;
    if (kInsert<K)
    {
        for (int kp=K-1; kp>kInsert; --kp)
        {
            int kp_1=kp-1;
            MAT_ELEM(distance,i1,kp)=MAT_ELEM(distance,i1,kp_1);
            MAT_ELEM(idx,i1,kp)=MAT_ELEM(idx,i1,kp_1);
        }
        MAT_ELEM(distance,i1,kInsert)=d;
        MAT_ELEM(idx,i1,kInsert)=i2;
    }
}

intrinsicDimensionalityCorrDim()

double intrinsicDimensionalityCorrDim	(	const Matrix2D< double > &	X,
		DimRedDistance2	f
	)

Definition at line 379 of file dimred_tools.cpp.

{
    int K=3;
    Matrix2D<int> idx;
    Matrix2D<double> distance;
    kNearestNeighbours(X,K,idx,distance,f);

    // Compute median and maximum
    size_t N=MAT_XSIZE(distance)*MAT_YSIZE(distance);
    std::sort(MATRIX2D_ARRAY(distance),MATRIX2D_ARRAY(distance)+N);
    double median=MATRIX2D_ARRAY(distance)[N/2];
    double maxVal=MATRIX2D_ARRAY(distance)[N-1];
    median*=median; // Because we compute dist^2 instead of dist
    maxVal*=maxVal;
    if (maxVal==0)
        return 0;

    // Compute the distance of all versus all
    double countLessMedianK=0, countLessMaxK=0;
    std::cerr << "Estimating dimensionality ... " << std::endl;
    init_progress_bar(MAT_YSIZE(X)-1);
    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 d
            if (d<=maxVal)
            {
                countLessMaxK+=1;
                if (d<=median)
                    countLessMedianK+=1;
            }
        }
        progress_bar(i1);
    }
    progress_bar(MAT_YSIZE(X)-1);
    double iCombinations=2.0/(MAT_YSIZE(X)*(MAT_YSIZE(X)-1));
    double probLessMedianK=countLessMedianK*iCombinations; // Probability of a distance being less than medianK
    double probLessMaxK=countLessMaxK*iCombinations; // Probability of a distance being less than maxK
    return 2*log(probLessMaxK/probLessMedianK)/log(maxVal/median);
}

intrinsicDimensionalityMLE()

double intrinsicDimensionalityMLE	(	const Matrix2D< double > &	X,
		DimRedDistance2	f
	)

Definition at line 341 of file dimred_tools.cpp.

{
    int k1=5;
    int k2=12;
    if (k2>MAT_YSIZE(X))
    {
        k2=MAT_YSIZE(X)-1;
        k1=k2/2;
    }
    Matrix2D<int> idx;
    Matrix2D<double> distance;
    kNearestNeighbours(X,k2,idx,distance,f);

    // Estimate d
    double dsum=0;
    std::cerr << "Estimating dimensionality ... " << std::endl;
    init_progress_bar(MAT_YSIZE(distance));
    for (int i=0; i<MAT_YSIZE(distance); ++i)
    {
        double dist=log(MAT_ELEM(distance,i,0));
        double S=dist;
        for (int k=1; k<MAT_XSIZE(distance); ++k)
        {
            dist=log(MAT_ELEM(distance,i,k));
            S+=dist;
            if (k>=k1)
            {
                double d=(k-1)/(S-dist*(k+1));
                dsum+=d;
            }
        }
        progress_bar(i);
    }
    progress_bar(MAT_YSIZE(distance));
    return -dsum/((k2-k1)*MAT_YSIZE(distance));
}