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, S. Y. Sung",
           title="Detecting pattern-based outliers",
           booktitle="Pattern Recognition Letters 24(16)",
           url="https://doi.org/10.1016/S0167-8655(03)00165-X",
           bibkey="DBLP:journals/prl/HuS03")
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.

Unfortunately, this approach needs an enormous numerical precision, and may not work for high-dimensional, non-normalized data. We therefore divide each volume by the average across the data set. This means values are even less comparable across data sets, but this avoids some of the numerical problems of this method.

Reference:

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

Since:

0.7.0

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 class de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm

ALGORITHM_ID

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

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

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