Package elki.projection
Class BarnesHutTSNE<O>
- java.lang.Object
-
- elki.projection.AbstractProjectionAlgorithm<Relation<DoubleVector>>
-
- elki.projection.TSNE<O>
-
- elki.projection.BarnesHutTSNE<O>
-
- Type Parameters:
O
- Object type
- All Implemented Interfaces:
Algorithm
@Title("t-SNE using Barnes-Hut-Approximation") @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(199) public class BarnesHutTSNE<O> extends TSNE<O>
t-SNE 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 Description protected static class
BarnesHutTSNE.QuadTree
Quad Tree for use in a Barnes-Hut approximation.-
Nested classes/interfaces inherited from interface elki.Algorithm
Algorithm.Utils
-
-
Field Summary
Fields Modifier and Type Field 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 elki.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 elki.projection.AbstractProjectionAlgorithm
KEEP_ID
-
-
Constructor Summary
Constructors Constructor Description BarnesHutTSNE(AffinityMatrixBuilder<? super O> affinity, int dim, double finalMomentum, double learningRate, int maxIterations, RandomFactory random, boolean keep, double theta)
Constructor.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method 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 pointTypeInformation[]
getInputTypeRestriction()
Get the input type restriction used for negotiating the data query.protected void
optimizetSNE(AffinityMatrix pij, double[][] sol)
Perform the actual tSNE optimization.Relation<DoubleVector>
run(Database database, Relation<O> relation)
-
Methods inherited from class elki.projection.TSNE
autorun, computeGradient, computeQij, randomInitialSolution, run, sqDist, updateSolution
-
Methods inherited from class elki.projection.AbstractProjectionAlgorithm
removePreviousRelation
-
-
-
-
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 builderdim
- Output dimensionalityfinalMomentum
- Final momentumlearningRate
- Learning ratemaxIterations
- Maximum number of iterationsrandom
- Random generatorkeep
- 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 classTSNE<O>
- Parameters:
pij
- Sparse initial affinity matrixsol
- 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 arrayoff
- Point offsetsol_i
- Solution vectornode
- Quad tree- Returns:
- force strength
-
getInputTypeRestriction
public TypeInformation[] getInputTypeRestriction()
Description copied from interface:Algorithm
Get the input type restriction used for negotiating the data query.- Specified by:
getInputTypeRestriction
in interfaceAlgorithm
- Overrides:
getInputTypeRestriction
in classTSNE<O>
- Returns:
- Type restriction
-
-