de.lmu.ifi.dbs.elki.algorithm.outlier.meta

Class HiCS<V extends NumberVector>

java.lang.Object

de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<OutlierResult>

de.lmu.ifi.dbs.elki.algorithm.outlier.meta.HiCS<V>

Type Parameters:

V - vector type

All Implemented Interfaces:

Algorithm, OutlierAlgorithm

@Title(value="HiCS: High Contrast Subspaces for Density-Based Outlier Ranking")
@Description(value="Algorithm to compute High Contrast Subspaces in a database as a pre-processing step for for density-based outlier ranking methods.")
@Reference(authors="Fabian Keller, Emmanuel M\u00fcller, Klemens B\u00f6hm",
           title="HiCS: High Contrast Subspaces for Density-Based Outlier Ranking",
           booktitle="Proc. IEEE 28th International Conference on Data Engineering (ICDE 2012)",
           url="http://dx.doi.org/10.1109/ICDE.2012.88")
public class HiCS<V extends NumberVector>
extends AbstractAlgorithm<OutlierResult>
implements OutlierAlgorithm

Algorithm to compute High Contrast Subspaces for Density-Based Outlier Ranking. Reference:

Fabian Keller, Emmanuel Müller, Klemens Böhm:
HiCS: High Contrast Subspaces for Density-Based Outlier Ranking
in: Proc. IEEE 28th Int. Conf. on Data Engineering (ICDE 2012), Washington, DC, USA

Author:

Jan Brusis, Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	HiCS.HiCSSubspace BitSet that holds a contrast value as field.
static class	HiCS.Parameterizer<V extends NumberVector> Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
private double	alpha Alpha threshold.
private int	cutoff Candidates limit.
private static Logging	LOG The Logger for this class.
private int	m Monte-Carlo iterations.
private static int	MAX_RETRIES Maximum number of retries.
private OutlierAlgorithm	outlierAlgorithm Outlier detection algorithm.
private RandomFactory	rnd Random generator.
private GoodnessOfFitTest	statTest Statistical test to use.

Constructor Summary

Constructors

Constructor and Description
HiCS(int m, double alpha, OutlierAlgorithm outlierAlgorithm, GoodnessOfFitTest statTest, int cutoff, RandomFactory rnd) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
private ArrayList<ArrayDBIDs>	buildOneDimIndexes(Relation<? extends NumberVector> relation) Calculates "index structures" for every attribute, i.e. sorts a ModifiableArray of every DBID in the database for every dimension and stores them in a list
private void	calculateContrast(Relation<? extends NumberVector> relation, HiCS.HiCSSubspace subspace, ArrayList<ArrayDBIDs> subspaceIndex, Random random) Calculates the actual contrast of a given subspace.
private Set<HiCS.HiCSSubspace>	calculateSubspaces(Relation<? extends NumberVector> relation, ArrayList<ArrayDBIDs> subspaceIndex, Random random) Identifies high contrast subspaces in a given full-dimensional database.
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected Logging	getLogger() Get the (STATIC) logger for this class.
OutlierResult	run(Relation<V> relation) Perform HiCS on a given database.

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm

makeParameterDistanceFunction, run

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.algorithm.outlier.OutlierAlgorithm

run

Field Detail

LOG

private static final Logging LOG

The Logger for this class.

MAX_RETRIES

private static final int MAX_RETRIES

Maximum number of retries.

See Also:

Constant Field Values

m

private int m

Monte-Carlo iterations.

alpha

private double alpha

Alpha threshold.

outlierAlgorithm

private OutlierAlgorithm outlierAlgorithm

Outlier detection algorithm.

statTest

private GoodnessOfFitTest statTest

Statistical test to use.

cutoff

private int cutoff

Candidates limit.

rnd

private RandomFactory rnd

Random generator.

Constructor Detail

HiCS

public HiCS(int m,
    double alpha,
    OutlierAlgorithm outlierAlgorithm,
    GoodnessOfFitTest statTest,
    int cutoff,
    RandomFactory rnd)

Constructor.

Parameters:

m - value of m

alpha - value of alpha

outlierAlgorithm - Inner outlier detection algorithm

statTest - Test to use

cutoff - Candidate limit

rnd - Random generator

Method Detail

run

public OutlierResult run(Relation<V> relation)

Perform HiCS on a given database.

Parameters:

relation - the database

Returns:

The aggregated resulting scores that were assigned by the given outlier detection algorithm

buildOneDimIndexes

private ArrayList<ArrayDBIDs> buildOneDimIndexes(Relation<? extends NumberVector> relation)

Calculates "index structures" for every attribute, i.e. sorts a ModifiableArray of every DBID in the database for every dimension and stores them in a list

Parameters:

relation - Relation to index

Returns:

List of sorted objects

calculateSubspaces

private Set<HiCS.HiCSSubspace> calculateSubspaces(Relation<? extends NumberVector> relation,
                                        ArrayList<ArrayDBIDs> subspaceIndex,
                                        Random random)

Identifies high contrast subspaces in a given full-dimensional database.

Parameters:

relation - the relation the HiCS should be evaluated for

subspaceIndex - Subspace indexes

Returns:

a set of high contrast subspaces

calculateContrast

private void calculateContrast(Relation<? extends NumberVector> relation,
                     HiCS.HiCSSubspace subspace,
                     ArrayList<ArrayDBIDs> subspaceIndex,
                     Random random)

Calculates the actual contrast of a given subspace.

Parameters:

relation - Relation to process

subspace - Subspace

subspaceIndex - Subspace indexes

getInputTypeRestriction

public TypeInformation[] getInputTypeRestriction()

Description copied from class: AbstractAlgorithm

Get the input type restriction used for negotiating the data query.

Specified by:

getInputTypeRestriction in interface Algorithm

Specified by:

getInputTypeRestriction in class AbstractAlgorithm<OutlierResult>

Returns:

Type restriction

getLogger

protected Logging getLogger()

Description copied from class: AbstractAlgorithm

Get the (STATIC) logger for this class.

Specified by:

getLogger in class AbstractAlgorithm<OutlierResult>

Returns:

the static logger