Package elki.outlier.lof

Class LOCI<O>

java.lang.Object

elki.outlier.lof.LOCI<O>

Type Parameters:

O - Object type

All Implemented Interfaces:

Algorithm, OutlierAlgorithm

@Title("LOCI: Fast Outlier Detection Using the Local Correlation Integral")
@Description("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")
public class LOCI<O>
extends java.lang.Object
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	Description
private static class	LOCI.DoubleIntArrayList	Array of double-int values.

Nested classes/interfaces inherited from interface elki.Algorithm

Algorithm.Utils

Field Summary

Fields

Modifier and Type	Field	Description
private double	alpha	Scaling of averaging neighborhood.
private Distance<? super O>	distance	Distance function used.
private static Logging	LOG	The logger for this class.
private int	nmin	Minimum neighborhood size.
private double	rmax	Maximum radius.

Constructor Summary

Constructors

Constructor	Description
LOCI(Distance<? super O> distance, double rmax, int nmin, double alpha)	Constructor.

Method Summary

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

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface elki.outlier.OutlierAlgorithm

autorun

Field Detail

LOG

private static final Logging LOG

The logger for this class.

distance

private Distance<? super O> distance

Distance function used.

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(Distance<? super O> distance,
            double rmax,
            int nmin,
            double alpha)

Constructor.

Parameters:

distance - Distance function

rmax - Maximum radius

nmin - Minimum neighborhood size

alpha - Alpha value

Method Detail

getInputTypeRestriction

public TypeInformation[] getInputTypeRestriction()

Description copied from interface: Algorithm

Get the input type restriction used for negotiating the data query.

Specified by:

getInputTypeRestriction in interface Algorithm

Returns:

Type restriction

run

public OutlierResult run(Relation<O> relation)

Run the algorithm

Parameters:

relation - Relation to process

Returns:

Outlier result

precomputeInterestingRadii

protected void precomputeInterestingRadii(DBIDs ids,
                                          RangeSearcher<DBIDRef> 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