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

Class FlexibleLOF<O,D extends NumberDistance<D,?>>

java.lang.Object

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

de.lmu.ifi.dbs.elki.algorithm.outlier.lof.FlexibleLOF<O,D>

Type Parameters:

O - the type of DatabaseObjects handled by this Algorithm

D - Distance type

All Implemented Interfaces:

Algorithm, OutlierAlgorithm, Parameterizable

Direct Known Subclasses:

OnlineLOF

@Title(value="LOF: Local Outlier Factor")
@Description(value="Algorithm to compute density-based local outlier factors in a database based on the neighborhood size parameter \'k\'")
@Reference(authors="M. M. Breunig, H.-P. Kriegel, R. Ng, and J. Sander",
           title="LOF: Identifying Density-Based Local Outliers",
           booktitle="Proc. 2nd ACM SIGMOD Int. Conf. on Management of Data (SIGMOD \'00), Dallas, TX, 2000",
           url="http://dx.doi.org/10.1145/342009.335388")
public class FlexibleLOF<O,D extends NumberDistance<D,?>>
extends AbstractAlgorithm<OutlierResult>
implements OutlierAlgorithm

Flexible variant of the "Local Outlier Factor" algorithm.

This implementation diverts from the original LOF publication in that it allows the user to use a different distance function for the reachability distance and neighborhood determination (although the default is to use the same value.)

The k nearest neighbors are determined using the parameter DistanceBasedAlgorithm.DISTANCE_FUNCTION_ID , while the reference set used in reachability distance computation is configured using FlexibleLOF.Parameterizer.REACHABILITY_DISTANCE_FUNCTION_ID.

The original LOF parameter was called "minPts". For consistency with the name "kNN query", we chose to rename the parameter to k. Flexible LOF allows you to set the two values different, which yields the parameters FlexibleLOF.Parameterizer.KREF_ID (-lof.krefer) and FlexibleLOF.Parameterizer.KREACH_ID (-lof.kreach)

Reference:
M. M. Breunig, H.-P. Kriegel, R. Ng, J. Sander: LOF: Identifying Density-Based Local Outliers.
In: Proc. 2nd ACM SIGMOD Int. Conf. on Management of Data (SIGMOD'00), Dallas, TX, 2000.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	FlexibleLOF.LOFResult<O,D extends NumberDistance<D,?>> Encapsulates information like the neighborhood, the LRD and LOF values of the objects during a run of the FlexibleLOF algorithm.
static class	FlexibleLOF.Parameterizer<O,D extends NumberDistance<D,?>> Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
protected int	kreach Number of neighbors used for reachability distance.
protected int	krefer Number of neighbors in comparison set.
private static Logging	LOG The logger for this class.
private static boolean	objectIsInKNN Include object itself in kNN neighborhood.
protected DistanceFunction<? super O,D>	reachabilityDistanceFunction Reachability distance function.
protected DistanceFunction<? super O,D>	referenceDistanceFunction Neighborhood distance function.

Constructor Summary

Constructors

Constructor and Description
FlexibleLOF(int krefer, int kreach, DistanceFunction<? super O,D> neighborhoodDistanceFunction, DistanceFunction<? super O,D> reachabilityDistanceFunction) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
protected Pair<WritableDoubleDataStore,DoubleMinMax>	computeLOFs(DBIDs ids, DoubleDataStore lrds, KNNQuery<O,D> knnRefer) Computes the Local outlier factor (LOF) of the specified objects.
protected WritableDoubleDataStore	computeLRDs(DBIDs ids, KNNQuery<O,D> knnReach) Computes the local reachability density (LRD) of the specified objects.
protected FlexibleLOF.LOFResult<O,D>	doRunInTime(DBIDs ids, KNNQuery<O,D> kNNRefer, KNNQuery<O,D> kNNReach, StepProgress stepprog) Performs the Generalized LOF_SCORE algorithm on the given database and returns a FlexibleLOF.LOFResult encapsulating information that may be needed by an OnlineLOF algorithm.
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
private Pair<KNNQuery<O,D>,KNNQuery<O,D>>	getKNNQueries(Database database, Relation<O> relation, StepProgress stepprog) Get the kNN queries for the algorithm.
protected Logging	getLogger() Get the (STATIC) logger for this class.
OutlierResult	run(Database database, Relation<O> relation) Performs the Generalized LOF algorithm on the given database by calling doRunInTime(de.lmu.ifi.dbs.elki.database.ids.DBIDs, de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery<O, D>, de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery<O, D>, de.lmu.ifi.dbs.elki.logging.progress.StepProgress).

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.

krefer

protected int krefer

Number of neighbors in comparison set.

kreach

protected int kreach

Number of neighbors used for reachability distance.

referenceDistanceFunction

protected DistanceFunction<? super O,D extends NumberDistance<D,?>> referenceDistanceFunction

Neighborhood distance function.

reachabilityDistanceFunction

protected DistanceFunction<? super O,D extends NumberDistance<D,?>> reachabilityDistanceFunction

Reachability distance function.

objectIsInKNN

private static boolean objectIsInKNN

Include object itself in kNN neighborhood. In the official LOF publication, the point itself is not considered to be part of its k nearest neighbors.

Constructor Detail

FlexibleLOF

public FlexibleLOF(int krefer,
           int kreach,
           DistanceFunction<? super O,D> neighborhoodDistanceFunction,
           DistanceFunction<? super O,D> reachabilityDistanceFunction)

Constructor.

Parameters:

krefer - The number of neighbors for reference

kreach - The number of neighbors for reachability distance

neighborhoodDistanceFunction - the neighborhood distance function

reachabilityDistanceFunction - the reachability distance function

Method Detail

run

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

Performs the Generalized LOF algorithm on the given database by calling doRunInTime(de.lmu.ifi.dbs.elki.database.ids.DBIDs, de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery<O, D>, de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery<O, D>, de.lmu.ifi.dbs.elki.logging.progress.StepProgress).

Parameters:

database - Database to query

relation - Data to process

Returns:

LOF outlier result

getKNNQueries

private Pair<KNNQuery<O,D>,KNNQuery<O,D>> getKNNQueries(Database database,
                                              Relation<O> relation,
                                              StepProgress stepprog)

Get the kNN queries for the algorithm.

Parameters:

relation - the data

stepprog - the progress logger

Returns:

the kNN queries for the algorithm

doRunInTime

protected FlexibleLOF.LOFResult<O,D> doRunInTime(DBIDs ids,
                                     KNNQuery<O,D> kNNRefer,
                                     KNNQuery<O,D> kNNReach,
                                     StepProgress stepprog)

Performs the Generalized LOF_SCORE algorithm on the given database and returns a FlexibleLOF.LOFResult encapsulating information that may be needed by an OnlineLOF algorithm.

Parameters:

ids - Object ids

kNNRefer - the kNN query w.r.t. reference neighborhood distance function

kNNReach - the kNN query w.r.t. reachability distance function

stepprog - Progress logger

Returns:

LOF result

computeLRDs

protected WritableDoubleDataStore computeLRDs(DBIDs ids,
                                  KNNQuery<O,D> knnReach)

Computes the local reachability density (LRD) of the specified objects.

Parameters:

ids - the ids of the objects

knnReach - the precomputed neighborhood of the objects w.r.t. the reachability distance

Returns:

the LRDs of the objects

computeLOFs

protected Pair<WritableDoubleDataStore,DoubleMinMax> computeLOFs(DBIDs ids,
                                                     DoubleDataStore lrds,
                                                     KNNQuery<O,D> knnRefer)

Computes the Local outlier factor (LOF) of the specified objects.

Parameters:

ids - the ids of the objects

lrds - the LRDs of the objects

knnRefer - the precomputed neighborhood of the objects w.r.t. the reference distance

Returns:

the LOFs of the objects and the maximum LOF

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