Package elki.projection

Class 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

    • 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

      • 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