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

Class BarnesHutTSNE<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.TSNE<O>

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

Type Parameters:

O - Object type

All Implemented Interfaces:

Algorithm

@Reference(authors="L. J. P. van der Maaten",
           title="Accelerating t-SNE using Tree-Based Algorithms",
           booktitle="Journal of Machine Learning Research 15",
           url="http://dl.acm.org/citation.cfm?id=2697068",
           bibkey="DBLP:journals/jmlr/Maaten14")
 @Priority(value=199)
public class BarnesHutTSNE<O>
extends TSNE<O>

tSNE using Barnes-Hut-Approximation.

For larger data sets, use an index to make finding the nearest neighbors faster, e.g. cover tree or k-d-tree.

Reference:

L. J. P. van der Maaten
Accelerating t-SNE using Tree-Based Algorithms
Journal of Machine Learning Research 15

Since:

0.7.5

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	BarnesHutTSNE.Parameterizer<O> Parameterization class.
protected static class	BarnesHutTSNE.QuadTree Quad Tree for use in a Barnes-Hut approximation.

Field Summary

Fields

Modifier and Type	Field and Description
private static Logging	LOG Class logger.
protected static double	PERPLEXITY_ERROR Threshold for optimizing perplexity.
protected static int	PERPLEXITY_MAXITER Maximum number of iterations when optimizing perplexity.
private static double	QUADTREE_MIN_RESOLUION Minimum resolution of quadtree.
protected double	sqtheta (Squared) approximation quality threshold.

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

affinity, dim, EARLY_EXAGGERATION, EARLY_EXAGGERATION_ITERATIONS, finalMomentum, INITIAL_SOLUTION_SCALE, initialMomentum, iterations, learningRate, MIN_GAIN, MIN_QIJ, momentumSwitch, projectedDistances, random

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
BarnesHutTSNE(AffinityMatrixBuilder<? super O> affinity, int dim, double finalMomentum, double learningRate, int maxIterations, RandomFactory random, boolean keep, double theta) Constructor.

Method Summary

Modifier and Type	Method and Description
private void	computeAttractiveForces(double[] attr, AffinityMatrix pij, double[][] sol)
private void	computeGradient(AffinityMatrix pij, double[][] solution, double[] grad)
private double	computeRepulsiveForces(double[] rep_i, int off, double[] sol_i, BarnesHutTSNE.QuadTree node) Compute the repulsive forces for a single point
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	optimizetSNE(AffinityMatrix pij, double[][] sol) Perform the actual tSNE optimization.
Relation<DoubleVector>	run(Database database, Relation<O> relation)

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

computeGradient, computeQij, randomInitialSolution, run, sqDist, updateSolution

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.

PERPLEXITY_ERROR

protected static final double PERPLEXITY_ERROR

Threshold for optimizing perplexity.

We deliberately allow more error than with "slow" tSNE.

See Also:

Constant Field Values

PERPLEXITY_MAXITER

protected static final int PERPLEXITY_MAXITER

Maximum number of iterations when optimizing perplexity.

We deliberately allow more error than with "slow" tSNE.

See Also:

Constant Field Values

QUADTREE_MIN_RESOLUION

private static final double QUADTREE_MIN_RESOLUION

Minimum resolution of quadtree.

See Also:

Constant Field Values

sqtheta

protected double sqtheta

(Squared) approximation quality threshold.

Constructor Detail

BarnesHutTSNE

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

Constructor.

Parameters:

affinity - Affinity matrix builder

dim - Output dimensionality

finalMomentum - Final momentum

learningRate - Learning rate

maxIterations - Maximum number of iterations

random - Random generator

keep - Keep the original data (or remove it)

theta - Theta parameter

Method Detail

run

public Relation<DoubleVector> run(Database database,
                                  Relation<O> relation)

optimizetSNE

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

Perform the actual tSNE optimization.

Overrides:

optimizetSNE in class TSNE<O>

Parameters:

pij - Sparse initial affinity matrix

sol - Solution output array (preinitialized)

computeGradient

private void computeGradient(AffinityMatrix pij,
                             double[][] solution,
                             double[] grad)

computeAttractiveForces

private void computeAttractiveForces(double[] attr,
                                     AffinityMatrix pij,
                                     double[][] sol)

computeRepulsiveForces

private double computeRepulsiveForces(double[] rep_i,
                                      int off,
                                      double[] sol_i,
                                      BarnesHutTSNE.QuadTree node)

Compute the repulsive forces for a single point

Parameters:

rep_i - Repulsive forces array

off - Point offset

sol_i - Solution vector

node - Quad tree

Returns:

force strength

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

Overrides:

getInputTypeRestriction in class TSNE<O>

Returns:

Type restriction

getLogger

protected Logging getLogger()

Description copied from class: AbstractAlgorithm

Get the (STATIC) logger for this class.

Overrides:

getLogger in class TSNE<O>

Returns:

the static logger