de.lmu.ifi.dbs.elki.algorithm.projection

Class SNE<O>

java.lang.Object

de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<R>

de.lmu.ifi.dbs.elki.algorithm.projection.AbstractProjectionAlgorithm<Relation<DoubleVector>>

de.lmu.ifi.dbs.elki.algorithm.projection.SNE<O>

Type Parameters:

O - Object type

All Implemented Interfaces:

Algorithm

@Reference(authors="G. Hinton, S. Roweis",
           title="Stochastic Neighbor Embedding",
           booktitle="Advances in Neural Information Processing Systems 15",
           url="http://papers.nips.cc/paper/2276-stochastic-neighbor-embedding",
           bibkey="DBLP:conf/nips/HintonR02")
public class SNE<O>
extends AbstractProjectionAlgorithm<Relation<DoubleVector>>

Stochastic Neighbor Embedding is a projection technique designed for visualization that tries to preserve the nearest neighbor structure.

Reference:

G. Hinton, S. Roweis
Stochastic Neighbor Embedding
Advances in Neural Information Processing Systems 15

Since:

0.7.5

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	SNE.Parameterizer<O> Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
protected AffinityMatrixBuilder<? super O>	affinity Affinity matrix builder.
protected int	dim Desired projection dimensionality
protected double	finalMomentum Final momentum.
protected static double	INITIAL_SOLUTION_SCALE Scale of the initial solution.
protected double	initialMomentum Final momentum.
protected int	iterations Number of iterations.
protected double	learningRate Initial learning rate.
private static Logging	LOG Class logger.
protected static double	MIN_GAIN Minimum gain in learning rate.
protected static double	MIN_QIJ Minimum value for qij entries (even when duplicate)
protected int	momentumSwitch Iteration when to switch momentum.
protected long	projectedDistances Number of distance computations performed in projected space.
protected RandomFactory	random Random generator

Fields inherited from class de.lmu.ifi.dbs.elki.algorithm.projection.AbstractProjectionAlgorithm

KEEP_ID

Fields inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm

ALGORITHM_ID

Constructor Summary

Constructors

Constructor and Description
SNE(AffinityMatrixBuilder<? super O> affinity, int dim, double finalMomentum, double learningRate, int iterations, RandomFactory random, boolean keep) Constructor.
SNE(AffinityMatrixBuilder<? super O> affinity, int dim, RandomFactory random) Constructor with default values.

Method Summary

Modifier and Type	Method and Description
protected void	computeGradient(AffinityMatrix pij, double[][] qij, double qij_isum, double[][] sol, double[] meta) Compute the gradients.
protected double	computeQij(double[][] qij, double[][] solution) Compute the qij of the solution, and the sum.
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected Logging	getLogger() Get the (STATIC) logger for this class.
protected void	optimizeSNE(AffinityMatrix pij, double[][] sol) Perform the actual tSNE optimization.
protected static double[][]	randomInitialSolution(int size, int dim, java.util.Random random) Generate a random initial solution.
Relation<DoubleVector>	run(Relation<O> relation)
protected double	sqDist(double[] v1, double[] v2) Squared distance, in projection space.
protected void	updateSolution(double[][] sol, double[] meta, int it) Update the current solution on iteration.

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.projection.AbstractProjectionAlgorithm

removePreviousRelation

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm

run

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

LOG

private static final Logging LOG

Class logger.

MIN_QIJ

protected static final double MIN_QIJ

Minimum value for qij entries (even when duplicate)

See Also:

Constant Field Values

INITIAL_SOLUTION_SCALE

protected static final double INITIAL_SOLUTION_SCALE

Scale of the initial solution.

See Also:

Constant Field Values

MIN_GAIN

protected static final double MIN_GAIN

Minimum gain in learning rate.

See Also:

Constant Field Values

affinity

protected AffinityMatrixBuilder<? super O> affinity

Affinity matrix builder.

projectedDistances

protected long projectedDistances

Number of distance computations performed in projected space.

dim

protected int dim

Desired projection dimensionality

learningRate

protected double learningRate

Initial learning rate.

initialMomentum

protected double initialMomentum

Final momentum.

finalMomentum

protected double finalMomentum

Final momentum.

momentumSwitch

protected int momentumSwitch

Iteration when to switch momentum.

iterations

protected int iterations

Number of iterations.

random

protected RandomFactory random

Random generator

Constructor Detail

SNE

public SNE(AffinityMatrixBuilder<? super O> affinity,
           int dim,
           RandomFactory random)

Constructor with default values.

Parameters:

affinity - Affinity matrix builder

dim - Output dimensionality

random - Random generator

SNE

public SNE(AffinityMatrixBuilder<? super O> affinity,
           int dim,
           double finalMomentum,
           double learningRate,
           int iterations,
           RandomFactory random,
           boolean keep)

Constructor.

Parameters:

affinity - Affinity matrix builder

dim - Output dimensionality

finalMomentum - Final momentum

learningRate - Learning rate

iterations - Number of iterations

random - Random generator

keep - Keep the original data (or remove it)

Method Detail

run

public Relation<DoubleVector> run(Relation<O> relation)

randomInitialSolution

protected static double[][] randomInitialSolution(int size,
                                                  int dim,
                                                  java.util.Random random)

Generate a random initial solution.

Parameters:

size - Data set size

dim - Output dimensionality

random - Random generator

Returns:

Initial solution matrix

optimizeSNE

protected void optimizeSNE(AffinityMatrix pij,
                           double[][] sol)

Perform the actual tSNE optimization.

Parameters:

pij - Initial affinity matrix

sol - Solution output array (preinitialized)

computeQij

protected double computeQij(double[][] qij,
                            double[][] solution)

Compute the qij of the solution, and the sum.

Parameters:

qij - Qij matrix (output)

solution - Solution matrix (input)

Returns:

qij sum

sqDist

protected double sqDist(double[] v1,
                        double[] v2)

Squared distance, in projection space.

Parameters:

v1 - First vector

v2 - Second vector

Returns:

Squared distance

computeGradient

protected void computeGradient(AffinityMatrix pij,
                               double[][] qij,
                               double qij_isum,
                               double[][] sol,
                               double[] meta)

Compute the gradients.

Parameters:

pij - Desired affinity matrix

qij - Projected affinity matrix

qij_isum - Normalization factor

sol - Current solution coordinates

meta - Point metadata

updateSolution

protected void updateSolution(double[][] sol,
                              double[] meta,
                              int it)

Update the current solution on iteration.

Parameters:

sol - Solution matrix

meta - Metadata array (gradient, momentum, learning rate)

it - Iteration number, to choose momentum factor.

getInputTypeRestriction

public TypeInformation[] getInputTypeRestriction()

Description copied from class: AbstractAlgorithm

Get the input type restriction used for negotiating the data query.

Specified by:

getInputTypeRestriction in interface Algorithm

Specified by:

getInputTypeRestriction in class AbstractAlgorithm<Relation<DoubleVector>>

Returns:

Type restriction

getLogger

protected Logging getLogger()

Description copied from class: AbstractAlgorithm

Get the (STATIC) logger for this class.

Specified by:

getLogger in class AbstractAlgorithm<Relation<DoubleVector>>

Returns:

the static logger