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

Class OUTRES<V extends NumberVector>

java.lang.Object

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

de.lmu.ifi.dbs.elki.algorithm.outlier.subspace.OUTRES<V>

Type Parameters:

V - vector type

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 International Conference on Information and knowledge management")
public class OUTRES<V extends NumberVector>
extends AbstractAlgorithm<OutlierResult>
implements OutlierAlgorithm

Adaptive outlierness for subspace outlier ranking (OUTRES). Note: this algorithm seems to have a O(n^3) complexity without appropriate index structures to accelerate 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. Reference:

E. Müller, M. Schiffer, T. Seidl
Adaptive outlierness for subspace outlier ranking
in: Proc. 19th ACM International Conference on Information and knowledge management

Author:

Viktoria Pleintinger, Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected class	OUTRES.KernelDensityEstimator Kernel density estimation and utility class.
static class	OUTRES.Parameterizer<O extends NumberVector> 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.

Constructor Summary

Constructors

Constructor and Description
OUTRES(double eps) Constructor.

Method Summary

Methods

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.
double	outresScore(int s, long[] subspace, DBIDRef id, OUTRES.KernelDensityEstimator kernel) Main loop of OUTRES.
private DoubleDBIDList	refineRange(DoubleDBIDList neighc, double adjustedEps) Refine a range query.
protected boolean	relevantSubspace(long[] subspace, DoubleDBIDList neigh, OUTRES.KernelDensityEstimator kernel) Subspace relevance test.
OutlierResult	run(Relation<V> relation) Main loop for OUTRES
private DoubleDBIDList	subsetNeighborhoodQuery(DoubleDBIDList neighc, DBIDRef dbid, PrimitiveDistanceFunction<? super V> df, double adjustedEps, OUTRES.KernelDensityEstimator kernel) Refine neighbors within a subset.

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.

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<V> 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)

Main loop of OUTRES. Run for each object

Parameters:

s - start dimension

subspace - Current subspace

id - Current object ID

kernel - Kernel

Returns:

Score

refineRange

private DoubleDBIDList refineRange(DoubleDBIDList neighc,
                         double adjustedEps)

Refine a range query.

Parameters:

neighc - Original result

adjustedEps - New epsilon

Returns:

refined list

subsetNeighborhoodQuery

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

Refine neighbors within a subset.

Parameters:

neighc - Neighbor candidates

dbid - Query object

df - distance function

adjustedEps - Epsilon range

kernel - Kernel

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