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)",
           url="https://doi.org/10.1109/ICDE.2003.1260802",
           bibkey="DBLP:conf/icde/PapadimitriouKGF03")
 @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!

Reference:

S. Papadimitriou, H. Kitagawa, P. B. Gibbons, C. Faloutsos:
LOCI: Fast Outlier Detection Using the Local Correlation Integral.
In: Proc. 19th IEEE Int. Conf. on Data Engineering (ICDE '03)

Since:

0.2

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private 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 Scaling of averaging neighborhood.
private static Logging	LOG The logger for this class.
private int	nmin Minimum neighborhood size.
private double	rmax Maximum radius.

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
LOCI(DistanceFunction<? super O> distanceFunction, double rmax, int nmin, double alpha) Constructor.

Method Summary

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

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

private double rmax

Maximum radius.

nmin

private int nmin

Minimum neighborhood size.

alpha

private double alpha

Scaling of averaging neighborhood.

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