Package elki.projection

Class PerplexityAffinityMatrixBuilder<O>

java.lang.Object

elki.projection.GaussianAffinityMatrixBuilder<O>

elki.projection.PerplexityAffinityMatrixBuilder<O>

Type Parameters:

O - Vector type

All Implemented Interfaces:

AffinityMatrixBuilder<O>

Direct Known Subclasses:

NearestNeighborAffinityMatrixBuilder

@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 PerplexityAffinityMatrixBuilder<O>
extends GaussianAffinityMatrixBuilder<O>

Compute the affinity matrix for SNE and tSNE.

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	Description
static class	PerplexityAffinityMatrixBuilder.Par<O>	Parameterization class.

Field Summary

Fields

Modifier and Type	Field	Description
protected Distance<? super O>	distance	Input distance function.
private static Logging	LOG	Class logger.
protected static double	MIN_PIJ	Minimum value for pij entries (even when duplicate)
protected double	perplexity	Perplexity.
protected static double	PERPLEXITY_ERROR	Threshold for optimizing perplexity.
protected static int	PERPLEXITY_MAXITER	Maximum number of iterations when optimizing perplexity.

Fields inherited from class elki.projection.GaussianAffinityMatrixBuilder

sigma

Constructor Summary

Constructors

Constructor	Description
PerplexityAffinityMatrixBuilder(Distance<? super O> distance, double perplexity)	Constructor.

Method Summary

Modifier and Type	Method	Description
<T extends O> AffinityMatrix	computeAffinityMatrix(Relation<T> relation, double initialScale)	Compute the affinity matrix.
protected static double	computePi(int i, double[] dist_i, double[] pij_i, double perplexity, double logPerp)	Compute row pij[i], using binary search on the kernel bandwidth sigma to obtain the desired perplexity.
protected static double[][]	computePij(double[][] dist, double perplexity, double initialScale)	Compute the pij from the distance matrix.
protected static double	estimateInitialBeta(double[] dist_i, double perplexity)	Estimate beta from the distances in a row.
TypeInformation	getInputTypeRestriction()	Supported input data.

Methods inherited from class elki.projection.GaussianAffinityMatrixBuilder

buildDistanceMatrix, computeH

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.

See Also:

Constant Field Values

PERPLEXITY_MAXITER

protected static final int PERPLEXITY_MAXITER

Maximum number of iterations when optimizing perplexity.

See Also:

Constant Field Values

MIN_PIJ

protected static final double MIN_PIJ

Minimum value for pij entries (even when duplicate)

See Also:

Constant Field Values

distance

protected Distance<? super O> distance

Input distance function.

perplexity

protected double perplexity

Perplexity.

Constructor Detail

PerplexityAffinityMatrixBuilder

public PerplexityAffinityMatrixBuilder(Distance<? super O> distance,
                                       double perplexity)

Constructor.

Parameters:

distance - Distance function

perplexity - Perplexity

Method Detail

computeAffinityMatrix

public <T extends O> AffinityMatrix computeAffinityMatrix(Relation<T> relation,
                                                          double initialScale)

Description copied from interface: AffinityMatrixBuilder

Compute the affinity matrix.

Specified by:

computeAffinityMatrix in interface AffinityMatrixBuilder<O>

Overrides:

computeAffinityMatrix in class GaussianAffinityMatrixBuilder<O>

Type Parameters:

T - Relation type

Parameters:

relation - Data relation

initialScale - initial scale

Returns:

Affinity matrix

computePij

protected static double[][] computePij(double[][] dist,
                                       double perplexity,
                                       double initialScale)

Compute the pij from the distance matrix.

Parameters:

dist - Distance matrix.

perplexity - Desired perplexity

initialScale - Initial scale

Returns:

Affinity matrix pij

computePi

protected static double computePi(int i,
                                  double[] dist_i,
                                  double[] pij_i,
                                  double perplexity,
                                  double logPerp)

Compute row pij[i], using binary search on the kernel bandwidth sigma to obtain the desired perplexity.

Parameters:

i - Current point

dist_i - Distance matrix row pij[i]

pij_i - Output row

perplexity - Desired perplexity

logPerp - Log of desired perplexity

Returns:

Beta

estimateInitialBeta

protected static double estimateInitialBeta(double[] dist_i,
                                            double perplexity)

Estimate beta from the distances in a row.

This lacks a mathematical argument, but is a handcrafted heuristic to avoid numerical problems. The average distance is usually too large, so we scale the average distance by 2*N/perplexity. Then estimate beta as 1/x.

Parameters:

dist_i - Distances

perplexity - Desired perplexity

Returns:

Estimated beta.

getInputTypeRestriction

public TypeInformation getInputTypeRestriction()

Supported input data.

Specified by:

getInputTypeRestriction in interface AffinityMatrixBuilder<O>

Overrides:

getInputTypeRestriction in class GaussianAffinityMatrixBuilder<O>

Returns:

Input data type information.