de.lmu.ifi.dbs.elki.datasource.filter.transform

Class FastMultidimensionalScalingTransform<O>

java.lang.Object

de.lmu.ifi.dbs.elki.datasource.filter.transform.FastMultidimensionalScalingTransform<O>

Type Parameters:

O - Data type

All Implemented Interfaces:

ObjectFilter

@Alias(value="fastmds")
public class FastMultidimensionalScalingTransform<O>
extends 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^2), and uses O(n^2) memory.

Since:

0.6.0

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	FastMultidimensionalScalingTransform.Parameterizer<O extends NumberVector> Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
(package private) PrimitiveDistanceFunction<? super O>	dist Distance function to use.
private static Logging	LOG Class logger.
(package private) int	tdim Target dimensionality

Constructor Summary

Constructors

Constructor and Description
FastMultidimensionalScalingTransform(int tdim, PrimitiveDistanceFunction<? super O> dist) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
protected double[][]	computeDistanceMatrix(List<O> col) Compute the distance matrix of a vector column.
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, 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

PrimitiveDistanceFunction<? super O> dist

Distance function to use.

tdim

int tdim

Target dimensionality

Constructor Detail

FastMultidimensionalScalingTransform

public FastMultidimensionalScalingTransform(int tdim,
                                    PrimitiveDistanceFunction<? super O> dist)

Constructor.

Parameters:

tdim - Target dimensionality.

dist - Distance function to use.

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

computeDistanceMatrix

protected double[][] computeDistanceMatrix(List<O> col)

Compute the distance matrix of a vector column.

Parameters:

col - Column

Returns:

Distance matrix

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,
                        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