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

Class FlexibleLOF<O>

java.lang.Object

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

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

Type Parameters:

O - the type of DatabaseObjects handled by this Algorithm

All Implemented Interfaces:

Algorithm, OutlierAlgorithm

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, 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>
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.

Author:

Peer Kröger, Erich Schubert, Elke Achtert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	FlexibleLOF.LOFResult<O> 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> 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.
protected DistanceFunction<? super O>	reachabilityDistanceFunction Reachability distance function.
protected DistanceFunction<? super O>	referenceDistanceFunction Neighborhood distance function.

Constructor Summary

Constructors

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

Method Summary

Methods

Modifier and Type	Method and Description
protected void	computeLOFs(KNNQuery<O> knnq, DBIDs ids, DoubleDataStore lrds, WritableDoubleDataStore lofs, DoubleMinMax lofminmax) Computes the Local outlier factor (LOF) of the specified objects.
protected void	computeLRDs(KNNQuery<O> knnq, DBIDs ids, WritableDoubleDataStore lrds) Computes the local reachability density (LRD) of the specified objects.
protected FlexibleLOF.LOFResult<O>	doRunInTime(DBIDs ids, KNNQuery<O> kNNRefer, KNNQuery<O> 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>,KNNQuery<O>>	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>, de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery<O>, 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> referenceDistanceFunction

Neighborhood distance function.

reachabilityDistanceFunction

protected DistanceFunction<? super O> reachabilityDistanceFunction

Reachability distance function.

Constructor Detail

FlexibleLOF

public FlexibleLOF(int krefer,
           int kreach,
           DistanceFunction<? super O> neighborhoodDistanceFunction,
           DistanceFunction<? super O> 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>, de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery<O>, 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>,KNNQuery<O>> 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> doRunInTime(DBIDs ids,
                                   KNNQuery<O> kNNRefer,
                                   KNNQuery<O> 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 void computeLRDs(KNNQuery<O> knnq,
               DBIDs ids,
               WritableDoubleDataStore lrds)

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

Parameters:

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

ids - the ids of the objects

lrds - Reachability storage

computeLOFs

protected void computeLOFs(KNNQuery<O> knnq,
               DBIDs ids,
               DoubleDataStore lrds,
               WritableDoubleDataStore lofs,
               DoubleMinMax lofminmax)

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

Parameters:

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

ids - IDs to process

lrds - Local reachability distances

lofs - Local outlier factor storage

lofminmax - Score minimum/maximum tracker

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