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) 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	Description
OUTRES(double eps)	Constructor.

Method Summary

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 OUTRES
private 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

Constructor Detail

OUTRES

public OUTRES(double eps)

Constructor.

Parameters:

eps - Epsilon

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 interface Algorithm

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 dimension

subspace - Current subspace

id - Current object ID

kernel - Kernel

cands - 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 - Object

cands - Candidates

df - Distance function

eps - Epsilon radius

kernel - Kernel

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