de.lmu.ifi.dbs.elki.math.linearalgebra.pca

Class RANSACCovarianceMatrixBuilder<V extends NumberVector<?>>

java.lang.Object

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.AbstractCovarianceMatrixBuilder<V>

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.RANSACCovarianceMatrixBuilder<V>

Type Parameters:

V - Vector type

All Implemented Interfaces:

CovarianceMatrixBuilder<V>, Parameterizable

@Reference(authors="Hans-Peter Kriegel, Peer Kr\u00f6ger, Erich Schubert, Arthur Zimek",
           title="Outlier Detection in Arbitrarily Oriented Subspaces",
           booktitle="Proc. IEEE International Conference on Data Mining (ICDM 2012)")
public class RANSACCovarianceMatrixBuilder<V extends NumberVector<?>>
extends AbstractCovarianceMatrixBuilder<V>

RANSAC based approach to a more robust covariance matrix computation. This is an experimental adoption of RANSAC to this problem, not a generic RANSAC implementation! While using RANSAC for PCA at first sounds like a good idea, it does not work very well in high-dimensional spaces. The problem is that PCA has O(n^2) degrees of freedom, so we need to sample very many objects, then perform an O(n^3) matrix operation to compute PCA, for each attempt. References: RANSAC for PCA was a side note in:

Hans-Peter Kriegel, Peer Kröger, Erich Schubert, Arthur Zimek
Outlier Detection in Arbitrarily Oriented Subspaces
in: Proc. IEEE International Conference on Data Mining (ICDM 2012)

The basic RANSAC idea was explained in:

Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography
M.A. Fischler, R.C. Bolles
Communications of the ACM, Vol. 24 Issue 6

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	RANSACCovarianceMatrixBuilder.Parameterizer<V extends NumberVector<?>> Parameterization class

Field Summary

Fields

Modifier and Type	Field and Description
(package private) int	iterations Number of iterations to perform
(package private) RandomFactory	rnd Random generator

Constructor Summary

Constructors

Constructor and Description
RANSACCovarianceMatrixBuilder(int iterations, RandomFactory rnd) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
Matrix	processIds(DBIDs ids, Relation<? extends V> relation) Compute Covariance Matrix for a collection of database IDs.

Methods inherited from class de.lmu.ifi.dbs.elki.math.linearalgebra.pca.AbstractCovarianceMatrixBuilder

processDatabase, processQueryResults, processQueryResults

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

iterations

int iterations

Number of iterations to perform

rnd

RandomFactory rnd

Random generator

Constructor Detail

RANSACCovarianceMatrixBuilder

public RANSACCovarianceMatrixBuilder(int iterations,
                             RandomFactory rnd)

Constructor.

Parameters:

iterations - Number of iterations (attempts) to try

rnd - random generator

Method Detail

processIds

@Reference(title="Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography",
           authors="M.A. Fischler, R.C. Bolles",
           booktitle="Communications of the ACM, Vol. 24 Issue 6",
           url="http://dx.doi.org/10.1145/358669.358692")
public Matrix processIds(DBIDs ids,
                                                  Relation<? extends V> relation)

Description copied from interface: CovarianceMatrixBuilder

Compute Covariance Matrix for a collection of database IDs.

Specified by:

processIds in interface CovarianceMatrixBuilder<V extends NumberVector<?>>

Specified by:

processIds in class AbstractCovarianceMatrixBuilder<V extends NumberVector<?>>

Parameters:

ids - a collection of ids

relation - the database used

Returns:

Covariance Matrix