package jsat.datatransform;
import java.util.Random;
import jsat.DataSet;
import jsat.classifiers.DataPoint;
import jsat.distributions.Distribution;
import jsat.distributions.LogUniform;
import jsat.linear.DenseMatrix;
import jsat.linear.Matrix;
import jsat.linear.RandomMatrix;
import jsat.linear.Vec;
import jsat.linear.distancemetrics.EuclideanDistance;
import jsat.utils.random.RandomUtil;
import jsat.utils.random.XORWOW;
/**
* The Johnson-Lindenstrauss (JL) Transform is a type of random projection down
* to a lower dimensional space. The goal is, with a high probability, to keep
* the {@link EuclideanDistance Euclidean distances} between points
* approximately the same in the original and projected space.
* The JL lemma, with a high probability, bounds the error of a distance
* computation between two points u and v in the lower dimensional
* space by (1 ± ε) d(u, v)2, where d is
* the Euclidean distance. It works best for very high dimension problems, 1000
* or more.
*
* For more information see:
* Achlioptas, D. (2003). Database-friendly random projections:
* Johnson-Lindenstrauss with binary coins. Journal of Computer and System
* Sciences, 66(4), 671–687. doi:10.1016/S0022-0000(03)00025-4
*
* @author Edward Raff
*/
public class JLTransform extends DataTransformBase
{
private static final long serialVersionUID = -8621368067861343912L;
//TODO for SPARSE, avoid unecessary computations for 0 values
/**
* Determines which distribution to construct the transform matrix from
*/
public enum TransformMode
{
/**
* The transform matrix values come from the gaussian distribution and
* is dense
* This transform is expensive to use when not using an in memory matrix
*/
GAUSS,
/**
* The transform matrix values are binary and faster to generate.
*/
BINARY,
/**
* The transform matrix values are sparse. NOTE: this sparsity
* is not currently taken advantage of
*/
SPARSE
}
private TransformMode mode;
private Matrix R;
/**
* Copy constructor
* @param transform the transform to copy
*/
protected JLTransform(JLTransform transform)
{
this.mode = transform.mode;
this.R = transform.R.clone();
}
/**
* Creates a new JL Transform that uses a target dimension of 50 features.
* This may not be optimal for any particular dataset.
*
* @param k the target dimension size
*/
public JLTransform()
{
this(50);
}
/**
* Creates a new JL Transform
* @param k the target dimension size
*/
public JLTransform(final int k)
{
this(k, TransformMode.SPARSE);
}
/**
* Creates a new JL Transform
* @param k the target dimension size
* @param mode how to construct the transform
* @param rand the source of randomness
*/
public JLTransform(final int k, final TransformMode mode)
{
this(k, mode, true);
}
private int k;
private boolean inMemory;
/**
* Creates a new JL Transform
* @param k the target dimension size
* @param mode how to construct the transform
* @param inMemory if {@code false}, the matrix will be stored in O(1)
* memory at the cost of execution time.
*/
public JLTransform(final int k, final TransformMode mode, boolean inMemory)
{
this.mode = mode;
this.k = k;
this.inMemory = inMemory;
}
@Override
public void fit(DataSet data)
{
final int d = data.getNumNumericalVars();
Random rand = RandomUtil.getRandom();
Matrix oldR = R = new RandomMatrixJL(k, d, rand.nextLong(), mode);
if(inMemory)
{
R = new DenseMatrix(k, d);
R.mutableAdd(oldR);
}
}
/**
* The JL transform uses a random matrix to project the data, and the mode
* controls which method is used to construct this matrix.
*
* @param mode how to construct the transform
*/
public void setMode(TransformMode mode)
{
this.mode = mode;
}
/**
*
* @return how to construct the transform
*/
public TransformMode getMode()
{
return mode;
}
/**
* Sets whether or not the transform matrix is stored explicitly in memory
* or not. Explicit storage is often faster, but can be prohibitive for
* large datasets
* @param inMemory {@code true} to explicitly store the transform matrix,
* {@code false} to re-create it on the fly as needed
*/
public void setInMemory(boolean inMemory)
{
this.inMemory = inMemory;
}
/**
*
* @return {@code true} if this object will explicitly store the transform
* matrix, {@code false} to re-create it on the fly as needed
*/
public boolean isInMemory()
{
return inMemory;
}
/**
* Sets the target dimension size to use for the output
* @param k the dimension after apply the transform
*/
public void setProjectedDimension(int k)
{
this.k = k;
}
/**
*
* @return the dimension after apply the transform
*/
public int getProjectedDimension()
{
return k;
}
public static Distribution guessProjectedDimension(DataSet d)
{
//huristic, could be improved by some theory app
double max = 100;
double min = 10;
if(d.getNumNumericalVars() > 10000)
{
min = 100;
max = 1000;
}
return new LogUniform(min, max);
}
@Override
public DataPoint transform(DataPoint dp)
{
Vec newVec = dp.getNumericalValues();
newVec = R.multiply(newVec);
DataPoint newDP = new DataPoint(newVec, dp.getCategoricalValues(),
dp.getCategoricalData(), dp.getWeight());
return newDP;
}
@Override
public DataTransform clone()
{
return new JLTransform(this);
}
private static class RandomMatrixJL extends RandomMatrix
{
private static final long serialVersionUID = 2009377824896155918L;
private double cnst;
private TransformMode mode;
public RandomMatrixJL(int rows, int cols, long XORSeed, TransformMode mode)
{
super(rows, cols, XORSeed);
this.mode = mode;
int k = rows;
if (mode == TransformMode.GAUSS || mode == TransformMode.BINARY)
cnst = 1.0 / Math.sqrt(k);
else if (mode == TransformMode.SPARSE)
cnst = Math.sqrt(3) / Math.sqrt(k);
}
@Override
protected double getVal(Random rand)
{
if (mode == TransformMode.GAUSS)
{
return rand.nextGaussian()*cnst;
}
else if (mode == TransformMode.BINARY)
{
return (rand.nextBoolean() ? -cnst : cnst);
}
else if (mode == TransformMode.SPARSE)
{
int val = rand.nextInt(6);
//1 with prob 1/6, -1 with prob 1/6
if(val == 0)
return -cnst;
else if(val == 1)
return cnst;
else //0 with prob 2/3
return 0;
}
else
throw new RuntimeException("BUG: Please report");
}
}
}
Ads help maintain this website.