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

Class RANSACCovarianceMatrixBuilder

java.lang.Object

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 Int. Conf. on Data Mining (ICDM 2012)",url="https://doi.org/10.1109/ICDM.2012.21",bibkey="DBLP:conf/icdm/KriegelKSZ12") @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 24(6)",url="https://doi.org/10.1145/358669.358692",bibkey="DBLP:journals/cacm/FischlerB81")
public class RANSACCovarianceMatrixBuilder
extends java.lang.Object
implements CovarianceMatrixBuilder

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²) degrees of freedom, so we need to sample very many objects, then perform an O(n³) 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 24(6)

Since:

0.5.5

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

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

Methods inherited from class java.lang.Object

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

Methods inherited from interface de.lmu.ifi.dbs.elki.math.linearalgebra.pca.CovarianceMatrixBuilder

processQueryResults, processQueryResults, processRelation

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

public double[][] 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

Parameters:

ids - a collection of ids

relation - the database used

Returns:

Covariance Matrix