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