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

Class ABOD<V extends NumberVector<?>>

java.lang.Object

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

de.lmu.ifi.dbs.elki.algorithm.AbstractDistanceBasedAlgorithm<V,DoubleDistance,OutlierResult>

de.lmu.ifi.dbs.elki.algorithm.outlier.ABOD<V>

Type Parameters:

V - Vector type

All Implemented Interfaces:

Algorithm, OutlierAlgorithm, Parameterizable

@Title(value="ABOD: Angle-Based Outlier Detection")
@Description(value="Outlier detection using variance analysis on angles, especially for high dimensional data sets.")
@Reference(authors="H.-P. Kriegel, M. Schubert, and A. Zimek",
           title="Angle-Based Outlier Detection in High-dimensional Data",
           booktitle="Proc. 14th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (KDD \'08), Las Vegas, NV, 2008",
           url="http://dx.doi.org/10.1145/1401890.1401946")
public class ABOD<V extends NumberVector<?>>
extends AbstractDistanceBasedAlgorithm<V,DoubleDistance,OutlierResult>
implements OutlierAlgorithm

Angle-Based Outlier Detection Outlier detection using variance analysis on angles, especially for high dimensional data sets. H.-P. Kriegel, M. Schubert, and A. Zimek: Angle-Based Outlier Detection in High-dimensional Data. In: Proc. 14th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (KDD '08), Las Vegas, NV, 2008.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	ABOD.Parameterizer<V extends NumberVector<?>> Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
static OptionID	FAST_SAMPLE_ID Parameter for sample size to be used in fast mode.
private int	k k parameter.
static OptionID	K_ID Parameter for k, the number of neighbors used in kNN queries.
static OptionID	KERNEL_FUNCTION_ID Parameter for the kernel function.
private static Logging	LOG The logger for this class.
static OptionID	PREPROCESSOR_ID The preprocessor used to materialize the kNN neighborhoods.
private PrimitiveSimilarityFunction<? super V,DoubleDistance>	primitiveKernelFunction Store the configured Kernel version.
(package private) int	sampleSize Variable to store fast mode sampling value.
private ArrayDBIDs	staticids Static DBID map.
private static boolean	USE_RND_SAMPLE use alternate code below.

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

DISTANCE_FUNCTION_ID

Constructor Summary

Constructors

Constructor and Description
ABOD(int k, int sampleSize, PrimitiveSimilarityFunction<? super V,DoubleDistance> primitiveKernelFunction, DistanceFunction<V,DoubleDistance> distanceFunction) Actual constructor, with parameters.
ABOD(int k, PrimitiveSimilarityFunction<? super V,DoubleDistance> primitiveKernelFunction, DistanceFunction<V,DoubleDistance> distanceFunction) Actual constructor, with parameters.

Method Summary

Methods

Modifier and Type	Method and Description
private double	calcCos(KernelMatrix kernelMatrix, DBIDRef aKey, DBIDRef bKey) Compute the cosinus value between vectors aKey and bKey.
private double	calcDenominator(KernelMatrix kernelMatrix, DBIDRef aKey, DBIDRef bKey, DBIDRef cKey)
private ComparableMinHeap<DoubleDBIDPair>	calcDistsandNN(Relation<V> data, KernelMatrix kernelMatrix, int sampleSize, DBIDRef aKey, WritableDoubleDataStore dists)
private ComparableMinHeap<DoubleDBIDPair>	calcDistsandRNDSample(Relation<V> data, KernelMatrix kernelMatrix, int sampleSize, DBIDRef aKey, WritableDoubleDataStore dists)
private double[]	calcFastNormalization(DBIDRef x, WritableDoubleDataStore dists, DBIDs ids)
private double	calcNumerator(KernelMatrix kernelMatrix, DBIDRef aKey, DBIDRef bKey, DBIDRef cKey)
private void	generateExplanation(StringBuilder buf, Relation<V> data, DBIDRef key, DBIDs expList)
private double	getAbofFilter(KernelMatrix kernelMatrix, DBIDRef aKey, WritableDoubleDataStore dists, double fulCounter, double counter, DBIDs neighbors)
String	getExplanations(Relation<V> data) Get explanations for points in the database.
OutlierResult	getFastRanking(Relation<V> relation) Main part of the algorithm.
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected Logging	getLogger() Get the (STATIC) logger for this class.
OutlierResult	getRanking(Relation<V> relation) Main part of the algorithm.
private int	mapDBID(DBIDRef aKey)
OutlierResult	run(Relation<V> relation) Run ABOD on the data set.

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

getDistanceFunction

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.

K_ID

public static final OptionID K_ID

Parameter for k, the number of neighbors used in kNN queries.

FAST_SAMPLE_ID

public static final OptionID FAST_SAMPLE_ID

Parameter for sample size to be used in fast mode.

KERNEL_FUNCTION_ID

public static final OptionID KERNEL_FUNCTION_ID

Parameter for the kernel function.

PREPROCESSOR_ID

public static final OptionID PREPROCESSOR_ID

The preprocessor used to materialize the kNN neighborhoods.

USE_RND_SAMPLE

private static final boolean USE_RND_SAMPLE

use alternate code below.

See Also:

Constant Field Values

k

private int k

k parameter.

sampleSize

int sampleSize

Variable to store fast mode sampling value.

primitiveKernelFunction

private PrimitiveSimilarityFunction<? super V extends NumberVector<?>,DoubleDistance> primitiveKernelFunction

Store the configured Kernel version.

staticids

private ArrayDBIDs staticids

Static DBID map.

Constructor Detail

ABOD

public ABOD(int k,
    int sampleSize,
    PrimitiveSimilarityFunction<? super V,DoubleDistance> primitiveKernelFunction,
    DistanceFunction<V,DoubleDistance> distanceFunction)

Actual constructor, with parameters. Fast mode (sampling).

Parameters:

k - k parameter

sampleSize - sample size

primitiveKernelFunction - Kernel function to use

distanceFunction - Distance function

ABOD

public ABOD(int k,
    PrimitiveSimilarityFunction<? super V,DoubleDistance> primitiveKernelFunction,
    DistanceFunction<V,DoubleDistance> distanceFunction)

Actual constructor, with parameters. Slow mode (exact).

Parameters:

k - k parameter

primitiveKernelFunction - kernel function to use

distanceFunction - Distance function

Method Detail

getRanking

public OutlierResult getRanking(Relation<V> relation)

Main part of the algorithm. Exact version.

Parameters:

relation - Relation to query

Returns:

result

getFastRanking

public OutlierResult getFastRanking(Relation<V> relation)

Main part of the algorithm. Fast version.

Parameters:

relation - Relation to use

Returns:

result

calcFastNormalization

private double[] calcFastNormalization(DBIDRef x,
                             WritableDoubleDataStore dists,
                             DBIDs ids)

getAbofFilter

private double getAbofFilter(KernelMatrix kernelMatrix,
                   DBIDRef aKey,
                   WritableDoubleDataStore dists,
                   double fulCounter,
                   double counter,
                   DBIDs neighbors)

calcCos

private double calcCos(KernelMatrix kernelMatrix,
             DBIDRef aKey,
             DBIDRef bKey)

Compute the cosinus value between vectors aKey and bKey.

Parameters:

kernelMatrix -

aKey -

bKey -

Returns:

cosinus value

mapDBID

private int mapDBID(DBIDRef aKey)

calcDenominator

private double calcDenominator(KernelMatrix kernelMatrix,
                     DBIDRef aKey,
                     DBIDRef bKey,
                     DBIDRef cKey)

calcNumerator

private double calcNumerator(KernelMatrix kernelMatrix,
                   DBIDRef aKey,
                   DBIDRef bKey,
                   DBIDRef cKey)

calcDistsandNN

private ComparableMinHeap<DoubleDBIDPair> calcDistsandNN(Relation<V> data,
                                               KernelMatrix kernelMatrix,
                                               int sampleSize,
                                               DBIDRef aKey,
                                               WritableDoubleDataStore dists)

calcDistsandRNDSample

private ComparableMinHeap<DoubleDBIDPair> calcDistsandRNDSample(Relation<V> data,
                                                      KernelMatrix kernelMatrix,
                                                      int sampleSize,
                                                      DBIDRef aKey,
                                                      WritableDoubleDataStore dists)

getExplanations

public String getExplanations(Relation<V> data)

Get explanations for points in the database.

Parameters:

data - to get explanations for

Returns:

String explanation

generateExplanation

private void generateExplanation(StringBuilder buf,
                       Relation<V> data,
                       DBIDRef key,
                       DBIDs expList)

run

public OutlierResult run(Relation<V> relation)

Run ABOD on the data set.

Parameters:

relation - Relation to process

Returns:

Outlier detection result

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

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