Package elki.outlier.subspace
Class OUTRES
- java.lang.Object
-
- elki.outlier.subspace.OUTRES
-
- All Implemented Interfaces:
Algorithm
,OutlierAlgorithm
@Reference(authors="E. M\u00fcller, M. Schiffer, T. Seidl", title="Adaptive outlierness for subspace outlier ranking", booktitle="Proc. 19th ACM Int. Conf. on Information and Knowledge Management", url="https://doi.org/10.1145/1871437.1871690", bibkey="DBLP:conf/cikm/MullerSS10") public class OUTRES extends java.lang.Object implements OutlierAlgorithm
Adaptive outlierness for subspace outlier ranking (OUTRES).Note: this algorithm seems to have a O(n³d!) complexity with no obvious way to accelerate it with usual index structures for range queries: each object in each tested subspace will need to know the mean and standard deviation of the density of the neighbors, which in turn needs another range query; except if we precomputed the densities for each of O(d!) possible subsets of dimensions.
Reference:
E. Müller, M. Schiffer, T. Seidl
Adaptive outlierness for subspace outlier ranking
Proc. 19th ACM Int. Conf. on Information and Knowledge Management- Since:
- 0.5.0
- Author:
- Viktoria Pleintinger, Erich Schubert
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description protected static class
OUTRES.KernelDensityEstimator
Kernel density estimation and utility class.static class
OUTRES.Par
Parameterization class.-
Nested classes/interfaces inherited from interface elki.Algorithm
Algorithm.Utils
-
-
Field Summary
Fields Modifier and Type Field Description private double
eps
The epsilon (in 2d) parameterprivate static double
K_S_CRITICAL001
Constant for Kolmogorov-Smirnov at alpha=0.01 (table value)private static Logging
LOG
The logger for this class.
-
Constructor Summary
Constructors Constructor Description OUTRES(double eps)
Constructor.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description TypeInformation[]
getInputTypeRestriction()
Get the input type restriction used for negotiating the data query.private DoubleDBIDList
initialRange(DBIDRef obj, DBIDs cands, PrimitiveDistance<? super NumberVector> df, double eps, OUTRES.KernelDensityEstimator kernel, ModifiableDoubleDBIDList n)
Initial range query.double
outresScore(int s, long[] subspace, DBIDRef id, OUTRES.KernelDensityEstimator kernel, DBIDs cands)
Main loop of OUTRES.protected boolean
relevantSubspace(long[] subspace, DoubleDBIDList neigh, OUTRES.KernelDensityEstimator kernel)
Subspace relevance test.OutlierResult
run(Relation<? extends NumberVector> relation)
Main loop for OUTRESprivate DoubleDBIDList
subsetNeighborhoodQuery(DoubleDBIDList neighc, DBIDRef dbid, PrimitiveDistance<? super NumberVector> df, double adjustedEps, OUTRES.KernelDensityEstimator kernel, ModifiableDoubleDBIDList n)
Refine neighbors within a subset.-
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.
-
eps
private final double eps
The epsilon (in 2d) parameter
-
K_S_CRITICAL001
private static final double K_S_CRITICAL001
Constant for Kolmogorov-Smirnov at alpha=0.01 (table value)- See Also:
- Constant Field Values
-
-
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)
Main loop for OUTRES- Parameters:
relation
- Relation to process- Returns:
- Outlier detection result
-
outresScore
public double outresScore(int s, long[] subspace, DBIDRef id, OUTRES.KernelDensityEstimator kernel, DBIDs cands)
Main loop of OUTRES. Run for each object- Parameters:
s
- start dimensionsubspace
- Current subspaceid
- Current object IDkernel
- Kernelcands
- neighbor candidates- Returns:
- Score
-
initialRange
private DoubleDBIDList initialRange(DBIDRef obj, DBIDs cands, PrimitiveDistance<? super NumberVector> df, double eps, OUTRES.KernelDensityEstimator kernel, ModifiableDoubleDBIDList n)
Initial range query.- Parameters:
obj
- Objectcands
- Candidatesdf
- Distance functioneps
- Epsilon radiuskernel
- Kerneln
- Output buffer- Returns:
- Neighbors
-
subsetNeighborhoodQuery
private DoubleDBIDList subsetNeighborhoodQuery(DoubleDBIDList neighc, DBIDRef dbid, PrimitiveDistance<? super NumberVector> df, double adjustedEps, OUTRES.KernelDensityEstimator kernel, ModifiableDoubleDBIDList n)
Refine neighbors within a subset.- Parameters:
neighc
- Neighbor candidatesdbid
- Query objectdf
- distance functionadjustedEps
- Epsilon rangekernel
- Kerneln
- Output list- Returns:
- Neighbors of neighbor object
-
relevantSubspace
protected boolean relevantSubspace(long[] subspace, DoubleDBIDList neigh, OUTRES.KernelDensityEstimator kernel)
Subspace relevance test.- Parameters:
subspace
- Subspace to testneigh
- Neighbor listkernel
- Kernel density estimator- Returns:
- relevance test result
-
-