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

Class NearestNeighborAffinityMatrixBuilder<O>

java.lang.Object

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

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

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

Type Parameters:

O - Object type

All Implemented Interfaces:

AffinityMatrixBuilder<O>

Direct Known Subclasses:

IntrinsicNearestNeighborAffinityMatrixBuilder

@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")
public class NearestNeighborAffinityMatrixBuilder<O>
extends PerplexityAffinityMatrixBuilder<O>

Build sparse affinity matrix using the nearest neighbors only.

Reference:

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

TODO: this implementation currently differs in one major point: we do not symmetrize the sparse \(p_{ij}\) matrix.

Since:

0.7.5

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	NearestNeighborAffinityMatrixBuilder.Parameterizer<O> Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
private static Logging	LOG Class logger.
protected int	numberOfNeighbours Number of neighbors to use.

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

distanceFunction, MIN_PIJ, perplexity, PERPLEXITY_ERROR, PERPLEXITY_MAXITER

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

sigma

Constructor Summary

Constructors

Constructor and Description
NearestNeighborAffinityMatrixBuilder(DistanceFunction<? super O> distanceFunction, double perplexity) Constructor.
NearestNeighborAffinityMatrixBuilder(DistanceFunction<? super O> distanceFunction, double perplexity, int neighbors) Constructor.

Method Summary

Modifier and Type	Method and Description
<T extends O> AffinityMatrix	computeAffinityMatrix(Relation<T> relation, double initialScale) Compute the affinity matrix.
protected static double	computeH(DoubleArray dist_i, double[] pij_row, double mbeta) Compute H (observed perplexity) for row i, and the row pij_i.
protected void	computePij(DBIDRange ids, KNNQuery<?> knnq, boolean square, int numberOfNeighbours, double[][] pij, int[][] indices, double initialScale) Compute the sparse pij using the nearest neighbors only.
protected static double	computeSigma(int i, DoubleArray pij_row, double perplexity, double log_perp, double[] pij_i) Compute row pij[i], using binary search on the kernel bandwidth sigma to obtain the desired perplexity.
protected static int	containsIndex(int[] is, int i) Check if the index array contains i.
protected void	convertNeighbors(DBIDRange ids, DBIDRef ix, boolean square, KNNList neighbours, DoubleArray dist, IntegerArray ind) Load a neighbor query result into a double and and integer array, also removing the query point.

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

computePi, computePij, estimateInitialBeta, getInputTypeRestriction

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.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.

numberOfNeighbours

protected int numberOfNeighbours

Number of neighbors to use.

Constructor Detail

NearestNeighborAffinityMatrixBuilder

public NearestNeighborAffinityMatrixBuilder(DistanceFunction<? super O> distanceFunction,
                                            double perplexity)

Constructor.

Parameters:

distanceFunction - Distance function

perplexity - Desired perplexity (will use 3*perplexity neighbors)

NearestNeighborAffinityMatrixBuilder

public NearestNeighborAffinityMatrixBuilder(DistanceFunction<? super O> distanceFunction,
                                            double perplexity,
                                            int neighbors)

Constructor.

Parameters:

distanceFunction - Distance function

perplexity - Desired perplexity

neighbors - Number of neighbors to use

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 PerplexityAffinityMatrixBuilder<O>

Type Parameters:

T - Relation type

Parameters:

relation - Data relation

initialScale - initial scale

Returns:

Affinity matrix

computePij

protected void computePij(DBIDRange ids,
                          KNNQuery<?> knnq,
                          boolean square,
                          int numberOfNeighbours,
                          double[][] pij,
                          int[][] indices,
                          double initialScale)

Compute the sparse pij using the nearest neighbors only.

Parameters:

ids - ID range

knnq - kNN query

square - Use squared distances

numberOfNeighbours - Number of neighbors to get

pij - Output of distances

indices - Output of indexes

initialScale - Initial scaling factor

convertNeighbors

protected void convertNeighbors(DBIDRange ids,
                                DBIDRef ix,
                                boolean square,
                                KNNList neighbours,
                                DoubleArray dist,
                                IntegerArray ind)

Load a neighbor query result into a double and and integer array, also removing the query point. This is necessary, because we have to modify the distances. TODO: sort by index, not distance

Parameters:

ids - Indexes

ix - Current Object

square - Use squared distances

neighbours - Neighbor list

dist - Output distance array

ind - Output index array

computeSigma

protected static double computeSigma(int i,
                                     DoubleArray pij_row,
                                     double perplexity,
                                     double log_perp,
                                     double[] pij_i)

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

Parameters:

i - Current point

pij_row - Distance matrix row pij[i]

perplexity - Desired perplexity

log_perp - Log of desired perplexity

pij_i - Output row

Returns:

beta

computeH

protected static double computeH(DoubleArray dist_i,
                                 double[] pij_row,
                                 double mbeta)

Compute H (observed perplexity) for row i, and the row pij_i.

Parameters:

dist_i - Distances to neighbors

pij_row - Row pij[i] (output)

mbeta - -1. / (2 * sigma * sigma)

Returns:

Observed perplexity

containsIndex

protected static int containsIndex(int[] is,
                                   int i)

Check if the index array contains i. TODO: sort arrays, use binary search!

Parameters:

is - Array to search

i - Index to search

Returns:

Position of index i, or -1 if not found.