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

Class ReferenceBasedOutlierDetection

java.lang.Object

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

de.lmu.ifi.dbs.elki.algorithm.AbstractNumberVectorDistanceBasedAlgorithm<NumberVector,OutlierResult>

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

All Implemented Interfaces:

Algorithm, DistanceBasedAlgorithm<NumberVector>, OutlierAlgorithm

@Title(value="An Efficient Reference-based Approach to Outlier Detection in Large Datasets")
@Description(value="Computes kNN distances approximately, using reference points with various reference point strategies.")
@Reference(authors="Y. Pei, O.R. Zaiane, Y. Gao",
           title="An Efficient Reference-based Approach to Outlier Detection in Large Datasets",
           booktitle="Proc. 6th IEEE Int. Conf. on Data Mining (ICDM \'06)",
           url="http://dx.doi.org/10.1109/ICDM.2006.17")
@Alias(value="de.lmu.ifi.dbs.elki.algorithm.outlier.ReferenceBasedOutlierDetection")
public class ReferenceBasedOutlierDetection
extends AbstractNumberVectorDistanceBasedAlgorithm<NumberVector,OutlierResult>
implements OutlierAlgorithm

Reference-Based Outlier Detection algorithm, an algorithm that computes kNN distances approximately, using reference points. kNN distances are approximated by the difference in distance from a reference point. For this approximation to be of high quality, triangle inequality is required; but the algorithm can also process non-metric distances. Reference:

Y. Pei, O. R. Zaiane, Y. Gao
An Efficient Reference-Based Approach to Outlier Detection in Large Datasets
In: Proc. IEEE Int. Conf. on Data Mining (ICDM'06), Hong Kong, China, 2006

Author:

Lisa Reichert, Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	ReferenceBasedOutlierDetection.Parameterizer Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
private int	k Holds the number of neighbors to use for density estimation.
private static Logging	LOG The logger for this class.
private ReferencePointsHeuristic	refp Stores the reference point strategy.

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

distanceFunction

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

DISTANCE_FUNCTION_ID

Constructor Summary

Constructors

Constructor and Description
ReferenceBasedOutlierDetection(int k, NumberVectorDistanceFunction<? super NumberVector> distanceFunction, ReferencePointsHeuristic refp) Constructor with parameters.

Method Summary

Methods

Modifier and Type	Method and Description
protected double	computeDensity(DoubleDBIDList referenceDists, DoubleDBIDListIter iter, int index) Computes the density of an object.
protected DoubleDBIDList	computeDistanceVector(NumberVector refPoint, Relation<? extends NumberVector> database, PrimitiveDistanceQuery<? super NumberVector> distFunc) Computes for each object the distance to one reference point.
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<? extends NumberVector> relation) Run the algorithm on the given relation.
protected void	updateDensities(WritableDoubleDataStore rbod_score, DoubleDBIDList referenceDists) Update the density estimates for each object.

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

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

private int k

Holds the number of neighbors to use for density estimation.

refp

private ReferencePointsHeuristic refp

Stores the reference point strategy.

Constructor Detail

ReferenceBasedOutlierDetection

public ReferenceBasedOutlierDetection(int k,
                              NumberVectorDistanceFunction<? super NumberVector> distanceFunction,
                              ReferencePointsHeuristic refp)

Constructor with parameters.

Parameters:

k - k Parameter

distanceFunction - distance function

refp - Reference points heuristic

Method Detail

run

public OutlierResult run(Database database,
                Relation<? extends NumberVector> relation)

Run the algorithm on the given relation.

Parameters:

database - Database

relation - Relation to process

Returns:

Outlier result

computeDistanceVector

protected DoubleDBIDList computeDistanceVector(NumberVector refPoint,
                                   Relation<? extends NumberVector> database,
                                   PrimitiveDistanceQuery<? super NumberVector> distFunc)

Computes for each object the distance to one reference point. (one dimensional representation of the data set)

Parameters:

refPoint - Reference Point Feature Vector

database - database to work on

distFunc - Distance function to use

Returns:

array containing the distance to one reference point for each database object and the object id

updateDensities

protected void updateDensities(WritableDoubleDataStore rbod_score,
                   DoubleDBIDList referenceDists)

Update the density estimates for each object.

Parameters:

rbod_score - Density storage

referenceDists - Distances from current reference point

computeDensity

protected double computeDensity(DoubleDBIDList referenceDists,
                    DoubleDBIDListIter iter,
                    int index)

Computes the density of an object. The density of an object is the distances to the k nearest neighbors. Neighbors and distances are computed approximately. (approximation for kNN distance: instead of a normal NN search the NN of an object are those objects that have a similar distance to a reference point. The k- nearest neighbors of an object are those objects that lay close to the object in the reference distance vector)

Parameters:

referenceDists - vector of the reference distances

iter - Iterator to this list (will be reused)

index - index of the current object

Returns:

density for one object and reference point

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