Package elki.datasource.filter.transform

Class FastMultidimensionalScalingTransform<I,O extends NumberVector>

java.lang.Object

elki.datasource.filter.transform.FastMultidimensionalScalingTransform<I,O>

Type Parameters:

I - Data type

All Implemented Interfaces:

ObjectFilter

@Alias("fastmds")
@Priority(99)
public class FastMultidimensionalScalingTransform<I,O extends NumberVector>
extends java.lang.Object
implements ObjectFilter

Rescale the data set using multidimensional scaling, MDS.

This implementation uses power iterations, which is faster when the number of data points is much larger than the desired number of dimensions.

This implementation is O(n²), and uses O(n²) memory.

Since:

0.7.0

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	FastMultidimensionalScalingTransform.Par<I,O extends NumberVector>	Parameterization class.

Field Summary

Fields

Modifier and Type	Field	Description
(package private) PrimitiveDistance<? super I>	dist	Distance function to use.
(package private) NumberVector.Factory<O>	factory	Vector factory.
private static Logging	LOG	Class logger.
(package private) RandomFactory	random	Random generator.
(package private) int	tdim	Target dimensionality

Constructor Summary

Constructors

Constructor	Description
FastMultidimensionalScalingTransform(int tdim, PrimitiveDistance<? super I> dist, NumberVector.Factory<O> factory, RandomFactory random)	Constructor.

Method Summary

Modifier and Type	Method	Description
protected double	estimateEigenvalue(double[][] mat, double[] in)	Estimate the (singed!)
MultipleObjectsBundle	filter(MultipleObjectsBundle objects)	Filter a set of object packages.
protected void	findEigenVectors(double[][] imat, double[][] evs, double[] lambda)	Find the first eigenvectors and eigenvalues using power iterations.
protected double	multiply(double[][] mat, double[] in, double[] out)	Compute out = A * in, and return the (signed!)
protected void	randomInitialization(double[] out, java.util.Random rnd)	Choose a random vector of unit norm for power iterations.
protected double	updateEigenvector(double[] in, double[] out, double l)	Compute the change in the eigenvector, and normalize the output vector while doing so.
protected void	updateMatrix(double[][] mat, double[] evec, double eval)	Update matrix, by removing the effects of a known Eigenvector.

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.

dist

PrimitiveDistance<? super I> dist

Distance function to use.

tdim

int tdim

Target dimensionality

random

RandomFactory random

Random generator.

factory

NumberVector.Factory<O extends NumberVector> factory

Vector factory.

Constructor Detail

FastMultidimensionalScalingTransform

public FastMultidimensionalScalingTransform(int tdim,
                                            PrimitiveDistance<? super I> dist,
                                            NumberVector.Factory<O> factory,
                                            RandomFactory random)

Constructor.

Parameters:

tdim - Target dimensionality.

dist - Distance function to use.

factory - Vector factory.

random - Random generator.

Method Detail

filter

public MultipleObjectsBundle filter(MultipleObjectsBundle objects)

Description copied from interface: ObjectFilter

Filter a set of object packages.

Specified by:

filter in interface ObjectFilter

Parameters:

objects - Object to filter

Returns:

Filtered objects

findEigenVectors

protected void findEigenVectors(double[][] imat,
                                double[][] evs,
                                double[] lambda)

Find the first eigenvectors and eigenvalues using power iterations.

Parameters:

imat - Matrix (will be modified!)

evs - Eigenvectors output

lambda - Eigenvalues output

randomInitialization

protected void randomInitialization(double[] out,
                                    java.util.Random rnd)

Choose a random vector of unit norm for power iterations.

Parameters:

out - Output storage

rnd - Random source.

multiply

protected double multiply(double[][] mat,
                          double[] in,
                          double[] out)

Compute out = A * in, and return the (signed!) length of the output vector.

Parameters:

mat - Matrix.

in - Input vector.

out - Output vector storage.

Returns:

Length of this vector.

updateEigenvector

protected double updateEigenvector(double[] in,
                                   double[] out,
                                   double l)

Compute the change in the eigenvector, and normalize the output vector while doing so.

Parameters:

in - Input vector

out - Output vector

l - Eigenvalue

Returns:

Change

estimateEigenvalue

protected double estimateEigenvalue(double[][] mat,
                                    double[] in)

Estimate the (singed!) Eigenvalue for a particular vector.

Parameters:

mat - Matrix.

in - Input vector.

Returns:

Estimated eigenvalue

updateMatrix

protected void updateMatrix(double[][] mat,
                            double[] evec,
                            double eval)

Update matrix, by removing the effects of a known Eigenvector.

Parameters:

mat - Matrix

evec - Known normalized Eigenvector

eval - Eigenvalue