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

Class RANSACCovarianceMatrixBuilder

java.lang.Object

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

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

All Implemented Interfaces:

CovarianceMatrixBuilder

@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
extends AbstractCovarianceMatrixBuilder

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

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	RANSACCovarianceMatrixBuilder.Parameterizer 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 NumberVector> 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 NumberVector> relation)

Description copied from interface: CovarianceMatrixBuilder

Compute Covariance Matrix for a collection of database IDs.

Specified by:

processIds in interface CovarianceMatrixBuilder

Specified by:

processIds in class AbstractCovarianceMatrixBuilder

Parameters:

ids - a collection of ids

relation - the database used

Returns:

Covariance Matrix