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

Class OUTRES

java.lang.Object

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

de.lmu.ifi.dbs.elki.algorithm.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 AbstractAlgorithm<OutlierResult>
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 and Description
protected static class	OUTRES.KernelDensityEstimator Kernel density estimation and utility class.
static class	OUTRES.Parameterizer Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
private double	eps The epsilon (in 2d) parameter
private static double	K_S_CRITICAL001 Constant for Kolmogorov-Smirnov at alpha=0.01 (table value)
private static Logging	LOG The logger for this class.

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

ALGORITHM_ID

Constructor Summary

Constructors

Constructor and Description
OUTRES(double eps) Constructor.

Method Summary

Modifier and Type	Method and Description
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected Logging	getLogger() Get the (STATIC) logger for this class.
private DoubleDBIDList	initialRange(DBIDRef obj, DBIDs cands, PrimitiveDistanceFunction<? 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 OUTRES
private DoubleDBIDList	subsetNeighborhoodQuery(DoubleDBIDList neighc, DBIDRef dbid, PrimitiveDistanceFunction<? super NumberVector> df, double adjustedEps, OUTRES.KernelDensityEstimator kernel, ModifiableDoubleDBIDList n) Refine neighbors within a subset.

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

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.

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

Constructor Detail

OUTRES

public OUTRES(double eps)

Constructor.

Parameters:

eps - Epsilon

Method Detail

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 dimension

subspace - Current subspace

id - Current object ID

kernel - Kernel

cands - neighbor candidates

Returns:

Score

initialRange

private DoubleDBIDList initialRange(DBIDRef obj,
                                    DBIDs cands,
                                    PrimitiveDistanceFunction<? super NumberVector> df,
                                    double eps,
                                    OUTRES.KernelDensityEstimator kernel,
                                    ModifiableDoubleDBIDList n)

Initial range query.

Parameters:

obj - Object

cands - Candidates

df - Distance function

eps - Epsilon radius

kernel - Kernel

n - Output buffer

Returns:

Neighbors

subsetNeighborhoodQuery

private DoubleDBIDList subsetNeighborhoodQuery(DoubleDBIDList neighc,
                                               DBIDRef dbid,
                                               PrimitiveDistanceFunction<? super NumberVector> df,
                                               double adjustedEps,
                                               OUTRES.KernelDensityEstimator kernel,
                                               ModifiableDoubleDBIDList n)

Refine neighbors within a subset.

Parameters:

neighc - Neighbor candidates

dbid - Query object

df - distance function

adjustedEps - Epsilon range

kernel - Kernel

n - 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 test

neigh - Neighbor list

kernel - Kernel density estimator

Returns:

relevance test result

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

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