Package elki.outlier.meta

Class HiCS

java.lang.Object

elki.outlier.meta.HiCS

All Implemented Interfaces:

Algorithm, OutlierAlgorithm

@Title("HiCS: High Contrast Subspaces for Density-Based Outlier Ranking")
@Description("Algorithm to compute High Contrast Subspaces in a database as a pre-processing step for for density-based outlier ranking methods.")
@Reference(authors="F. Keller, E. M\u00fcller, K. B\u00f6hm",
           title="HiCS: High Contrast Subspaces for Density-Based Outlier Ranking",
           booktitle="Proc. IEEE 28th Int. Conf. on Data Engineering (ICDE 2012)",
           url="https://doi.org/10.1109/ICDE.2012.88",
           bibkey="DBLP:conf/icde/KellerMB12")
public class HiCS
extends java.lang.Object
implements OutlierAlgorithm

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

Reference:

F. Keller, E. Müller, K. Böhm
HiCS: High Contrast Subspaces for Density-Based Outlier Ranking
Proc. IEEE 28th Int. Conf. on Data Engineering (ICDE 2012)

Since:

0.5.0

Author:

Jan Brusis, Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	HiCS.HiCSSubspace	BitSet that holds a contrast value as field.

Nested classes/interfaces inherited from interface elki.Algorithm

Algorithm.Utils

Field Summary

Fields

Modifier and Type	Field	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	Description
HiCS(int m, double alpha, OutlierAlgorithm outlierAlgorithm, GoodnessOfFitTest statTest, int cutoff, RandomFactory rnd)	Constructor.

Method Summary

Modifier and Type	Method	Description
private java.util.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, java.util.ArrayList<ArrayDBIDs> subspaceIndex, java.util.Random random)	Calculates the actual contrast of a given subspace.
private java.util.Set<HiCS.HiCSSubspace>	calculateSubspaces(Relation<? extends NumberVector> relation, java.util.ArrayList<ArrayDBIDs> subspaceIndex, java.util.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.
OutlierResult	run(Relation<? extends NumberVector> relation)	Perform HiCS on a given database.

Methods inherited from class java.lang.Object

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

Methods inherited from interface elki.outlier.OutlierAlgorithm

autorun

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

getInputTypeRestriction

public TypeInformation[] getInputTypeRestriction()

Description copied from interface: Algorithm

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

Specified by:

getInputTypeRestriction in interface Algorithm

Returns:

Type restriction

run

public OutlierResult run(Relation<? extends NumberVector> 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 java.util.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 java.util.Set<HiCS.HiCSSubspace> calculateSubspaces(Relation<? extends NumberVector> relation,
                                                            java.util.ArrayList<ArrayDBIDs> subspaceIndex,
                                                            java.util.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,
                               java.util.ArrayList<ArrayDBIDs> subspaceIndex,
                               java.util.Random random)

Calculates the actual contrast of a given subspace.

Parameters:

relation - Relation to process

subspace - Subspace

subspaceIndex - Subspace indexes