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

Class VarianceOfVolume<O extends SpatialComparable>

java.lang.Object

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

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

de.lmu.ifi.dbs.elki.algorithm.outlier.lof.VarianceOfVolume<O>

Type Parameters:

O - the type of data objects handled by this algorithm

All Implemented Interfaces:

Algorithm, DistanceBasedAlgorithm<O>, OutlierAlgorithm

@Reference(authors="T. Hu, and S. Y. Sung",
           title="Detecting pattern-based outliers",
           booktitle="Pattern Recognition Letters 24(16)",
           url="http://dx.doi.org/10.1016/S0167-8655(03)00165-X")
public class VarianceOfVolume<O extends SpatialComparable>
extends AbstractDistanceBasedAlgorithm<O,OutlierResult>
implements OutlierAlgorithm

Variance of Volume for outlier detection. The volume is estimated by the distance to the k-nearest neighbor, then the variance of volume is computed. Unfortuately, this approach needs an enormous numerical precision, and may not work for high-dimensional, non-normalized data. Reference:

T. Hu, and S. Y. Sung
Detecting pattern-based outliers
Pattern Recognition Letters 24(16)

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	VarianceOfVolume.Parameterizer<O extends SpatialComparable> Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
protected int	k The number of neighbors to query (including the query point!)
private static Logging	LOG The logger for this class.

Fields inherited from interface de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm

DISTANCE_FUNCTION_ID

Constructor Summary

Constructors

Constructor and Description
VarianceOfVolume(int k, DistanceFunction<? super O> distanceFunction) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
private void	computeVolumes(KNNQuery<O> knnq, int dim, DBIDs ids, WritableDoubleDataStore vols) Compute volumes
private void	computeVOVs(KNNQuery<O> knnq, DBIDs ids, DoubleDataStore vols, WritableDoubleDataStore vovs, DoubleMinMax vovminmax) Compute variance of volumes.
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected Logging	getLogger() Get the (STATIC) logger for this class.
OutlierResult	run(Database database, Relation<O> relation) Runs the VOV algorithm on the given database.

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

protected int k

The number of neighbors to query (including the query point!)

Constructor Detail

VarianceOfVolume

public VarianceOfVolume(int k,
                DistanceFunction<? super O> distanceFunction)

Constructor.

Parameters:

k - the number of neighbors to use for comparison (excluding the query point)

distanceFunction - the neighborhood distance function

Method Detail

run

public OutlierResult run(Database database,
                Relation<O> relation)

Runs the VOV algorithm on the given database.

Parameters:

database - Database to query

relation - Data to process

Returns:

VOV outlier result

computeVolumes

private void computeVolumes(KNNQuery<O> knnq,
                  int dim,
                  DBIDs ids,
                  WritableDoubleDataStore vols)

Compute volumes

Parameters:

knnq - KNN query

dim - Data dimensionality

ids - IDs to process

vols - Volume storage

computeVOVs

private void computeVOVs(KNNQuery<O> knnq,
               DBIDs ids,
               DoubleDataStore vols,
               WritableDoubleDataStore vovs,
               DoubleMinMax vovminmax)

Compute variance of volumes.

Parameters:

knnq - KNN query

ids - IDs to process

vols - Volumes

vovs - Variance of Volume storage

vovminmax - Score minimum/maximum tracker

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