fastmap: FastMap Projection

In kuwisdelu/matter: Out-of-core statistical computing and signal processing

FastMap Projection

Description

The FastMap algorithm performs approximate multidimensional scaling (MDS) based on any distance function. It is faster and more efficient than traditional MDS algorithms, scaling as O(n) rather than O(n^2). FastMap accomplishes this by finding two distant pivot objects on some hyperplane for each projected dimension, and then projecting all other objects onto the line between these pivots.

Usage

# FastMap projection
fastmap(x, k = 3L, group = NULL, distfun = NULL,
	transpose = FALSE, pivots = 10L, niter = 10L, verbose = NA, ...)

## S3 method for class 'fastmap'
predict(object, newdata, ...)

Arguments

x	A numeric matrix-like object.
k	The number of FastMap components to project.
group	Grouping variable if pivots should be guaranteed to come from different groups.
distfun	A distance function with the same usage (i.e., supports the same arguments and return values) as rowDists or colDists.
transpose	A logical value indicating whether x should be considered transposed or not. This only used internally to indicate whether the input matrix is (P x N) or (N x P), and therefore extract the number of objects and their names.
pivots	The number of pivot candidates to attempt each iteration. Using more pivot candidates can help improve the quality of the pivot selection. Using fewer can help speed up computation.
niter	The maximum number of iterations for selecting the pivots.
...	Additional options passed to distfun.
object	An object inheriting from fastmap.
newdata	An optional data matrix to use for the prediction.
verbose	Should progress be printed for each pivot iteration and FastMap component projection?

Details

The pivots are initialized randomly for each new dimension, so the selection of pivots (and therefore the resulting projection) can be sensitive to the random seed for some datasets.

A custom distance function can be passed via distfun. If not provided, then this defaults to rowDists if transpose=FALSE or colDists if transpose=TRUE.

If a custom function is passed, it must support the same arguments and return values as rowDists and colDists.

Value

An object of class fastmap, with the following components:

• x: The projected variable matrix.

• sdev: The standard deviations of each column of the projected matrix x.

• pivots: A matrix giving the indices of the pivots and the distances between them.

• pivot.array: A subset of the original data matrix containing only the pivots.

• distfun: The function used to generate the distance function.

Author(s)

Kylie A. Bemis

References

C. Faloutsos, and D. Lin. “FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets.” Proceedings of the 1995 ACM SIGMOD international conference on Management of data, pp. 163 - 174, June 1995.

See Also

rowDists, colDists, cmdscale, prcomp

Examples

register(SerialParam())
set.seed(1)

a <- matrix(sort(runif(500)), nrow=50, ncol=10)
b <- matrix(rev(sort(runif(500))), nrow=50, ncol=10)
x <- cbind(a, b)

fm <- fastmap(x, k=2)

kuwisdelu/matter documentation built on Oct. 19, 2024, 10:31 a.m.