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

Class LOCI<O>

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.LOCI<O>

Type Parameters:

O - Object type

All Implemented Interfaces:

Algorithm, DistanceBasedAlgorithm<O>, OutlierAlgorithm

@Title(value="LOCI: Fast Outlier Detection Using the Local Correlation Integral")
@Description(value="Algorithm to compute outliers based on the Local Correlation Integral")
@Reference(authors="S. Papadimitriou, H. Kitagawa, P. B. Gibbons, C. Faloutsos",
           title="LOCI: Fast Outlier Detection Using the Local Correlation Integral",
           booktitle="Proc. 19th IEEE Int. Conf. on Data Engineering (ICDE \'03), Bangalore, India, 2003",
           url="http://dx.doi.org/10.1109/ICDE.2003.1260802")
@Alias(value="de.lmu.ifi.dbs.elki.algorithm.outlier.LOCI")
public class LOCI<O>
extends AbstractDistanceBasedAlgorithm<O,OutlierResult>
implements OutlierAlgorithm

Fast Outlier Detection Using the "Local Correlation Integral". Exact implementation only, not aLOCI. See ALOCI. Outlier detection using multiple epsilon neighborhoods. This implementation has O(n³ log n) runtime complexity! Based on: S. Papadimitriou, H. Kitagawa, P. B. Gibbons and C. Faloutsos: LOCI: Fast Outlier Detection Using the Local Correlation Integral. In: Proc. 19th IEEE Int. Conf. on Data Engineering (ICDE '03), Bangalore, India, 2003.

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected static class	LOCI.DoubleIntArrayList Array of double-int values.
static class	LOCI.Parameterizer<O> Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
private double	alpha Holds the value of ALPHA_ID.
static OptionID	ALPHA_ID Parameter to specify the averaging neighborhood scaling.
private static Logging	LOG The logger for this class.
private int	nmin Holds the value of NMIN_ID.
static OptionID	NMIN_ID Parameter to specify the minimum neighborhood size
private double	rmax Holds the value of RMAX_ID.
static OptionID	RMAX_ID Parameter to specify the maximum radius of the neighborhood to be considered, must be suitable to the distance function specified.

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

DISTANCE_FUNCTION_ID

Constructor Summary

Constructors

Constructor and Description
LOCI(DistanceFunction<? super O> distanceFunction, double rmax, int nmin, double alpha) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected Logging	getLogger() Get the (STATIC) logger for this class.
protected void	precomputeInterestingRadii(DBIDs ids, RangeQuery<O> rangeQuery, WritableDataStore<LOCI.DoubleIntArrayList> interestingDistances) Preprocessing step: determine the radii of interest for each point.
OutlierResult	run(Database database, Relation<O> relation) Run the algorithm

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.

RMAX_ID

public static final OptionID RMAX_ID

Parameter to specify the maximum radius of the neighborhood to be considered, must be suitable to the distance function specified.

NMIN_ID

public static final OptionID NMIN_ID

Parameter to specify the minimum neighborhood size

ALPHA_ID

public static final OptionID ALPHA_ID

Parameter to specify the averaging neighborhood scaling.

rmax

private double rmax

Holds the value of RMAX_ID.

nmin

private int nmin

Holds the value of NMIN_ID.

alpha

private double alpha

Holds the value of ALPHA_ID.

Constructor Detail

LOCI

public LOCI(DistanceFunction<? super O> distanceFunction,
    double rmax,
    int nmin,
    double alpha)

Constructor.

Parameters:

distanceFunction - Distance function

rmax - Maximum radius

nmin - Minimum neighborhood size

alpha - Alpha value

Method Detail

run

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

Run the algorithm

Parameters:

database - Database to process

relation - Relation to process

Returns:

Outlier result

precomputeInterestingRadii

protected void precomputeInterestingRadii(DBIDs ids,
                              RangeQuery<O> rangeQuery,
                              WritableDataStore<LOCI.DoubleIntArrayList> interestingDistances)

Preprocessing step: determine the radii of interest for each point.

Parameters:

ids - IDs to process

rangeQuery - Range query

interestingDistances - Distances of interest

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