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, Parameterizable

@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

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, BitSet subspace, DBIDRef id, OUTRES.KernelDensityEstimator kernel) Main loop of OUTRES.
private DoubleDistanceDBIDList	refineRange(DistanceDBIDList<DoubleDistance> neighc, double adjustedEps) Refine a range query.
protected boolean	relevantSubspace(BitSet subspace, DoubleDistanceDBIDList neigh, OUTRES.KernelDensityEstimator kernel) Subspace relevance test.
OutlierResult	run(Relation<V> relation) Main loop for OUTRES
private DoubleDistanceDBIDList	subsetNeighborhoodQuery(DistanceDBIDList<DoubleDistance> neighc, DBIDRef dbid, PrimitiveDoubleDistanceFunction<? 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,
                 BitSet 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 DoubleDistanceDBIDList refineRange(DistanceDBIDList<DoubleDistance> neighc,
                                 double adjustedEps)

Refine a range query.

Parameters:

neighc - Original result

adjustedEps - New epsilon

Returns:

refined list

subsetNeighborhoodQuery

private DoubleDistanceDBIDList subsetNeighborhoodQuery(DistanceDBIDList<DoubleDistance> neighc,
                                             DBIDRef dbid,
                                             PrimitiveDoubleDistanceFunction<? 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(BitSet subspace,
                       DoubleDistanceDBIDList 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