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
All Methods Instance Methods Concrete Methods 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 listprivate 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 malpha
- value of alphaoutlierAlgorithm
- Inner outlier detection algorithmstatTest
- Test to usecutoff
- Candidate limitrnd
- 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 interfaceAlgorithm
- 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 forsubspaceIndex
- 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 processsubspace
- SubspacesubspaceIndex
- Subspace indexes
-
-