de.lmu.ifi.dbs.elki.algorithm.outlier
Class LOF<O extends DatabaseObject,D extends NumberDistance<D,?>>

java.lang.Object
  de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<O,R>
          de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm<O,D,OutlierResult>
              de.lmu.ifi.dbs.elki.algorithm.outlier.LOF<O,D>

Type Parameters:

O - the type of DatabaseObjects handled by this Algorithm

D - Distance type

All Implemented Interfaces:

Algorithm<O,OutlierResult>, Parameterizable

@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 LOF<O extends DatabaseObject,D extends NumberDistance<D,?>>
extends DistanceBasedAlgorithm<O,D,OutlierResult>

Algorithm to compute density-based local outlier factors in a database based on a specified parameter K_ID (-lof.k).

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

The original LOF parameter was called "minPts". Since kNN queries in ELKI have slightly different semantics - exactly k neighbors are returned - we chose to rename the parameter to K_ID (-lof.k) to reflect this difference.

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

Field Summary

(package private) int	k Holds the value of K_PARAM.
static OptionID	K_ID OptionID for K_PARAM
private IntParameter	K_PARAM Parameter to specify the number of nearest neighbors of an object to be considered for computing its LOF_SCORE, must be an integer greater than 1.
static AssociationID<Double>	LOF_SCORE The association id to associate the LOF_SCORE of an object for the LOF_SCORE algorithm.
(package private) boolean	objectIsInKNN Include object itself in kNN neighborhood.
(package private) MaterializeKNNPreprocessor<O,D>	preprocessor1 Preprocessor Step 1
(package private) MaterializeKNNPreprocessor<O,D>	preprocessor2 Preprocessor Step 2
static OptionID	REACHABILITY_DISTANCE_FUNCTION_ID OptionID for REACHABILITY_DISTANCE_FUNCTION_PARAM
private ObjectParameter<DistanceFunction<O,D>>	REACHABILITY_DISTANCE_FUNCTION_PARAM The distance function to determine the reachability distance between database objects.
private DistanceFunction<O,D>	reachabilityDistanceFunction Holds the instance of the reachability distance function specified by REACHABILITY_DISTANCE_FUNCTION_PARAM.

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

DISTANCE_FUNCTION_ID, DISTANCE_FUNCTION_PARAM

Fields inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable

debug, logger

Constructor Summary

LOF(Parameterization config)
Constructor, adhering to Parameterizable

Method Summary

protected OutlierResult

runInTime(Database<O> database) Performs the Generalized LOF_SCORE algorithm on the given database.

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm

getDistanceFactory, getDistanceFunction

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm

isTime, isVerbose, run, setTime, setVerbose

Methods inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable

debugFine, debugFiner, debugFinest, exception, progress, verbose, warning

Methods inherited from class java.lang.Object

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

Field Detail

REACHABILITY_DISTANCE_FUNCTION_ID

public static final OptionID REACHABILITY_DISTANCE_FUNCTION_ID

OptionID for REACHABILITY_DISTANCE_FUNCTION_PARAM

REACHABILITY_DISTANCE_FUNCTION_PARAM

private final ObjectParameter<DistanceFunction<O extends DatabaseObject,D extends NumberDistance<D,?>>> REACHABILITY_DISTANCE_FUNCTION_PARAM

The distance function to determine the reachability distance between database objects.

Default value: EuclideanDistanceFunction

Key: -lof.reachdistfunction

LOF_SCORE

public static final AssociationID<Double> LOF_SCORE

The association id to associate the LOF_SCORE of an object for the LOF_SCORE algorithm.

reachabilityDistanceFunction

private DistanceFunction<O extends DatabaseObject,D extends NumberDistance<D,?>> reachabilityDistanceFunction

Holds the instance of the reachability distance function specified by REACHABILITY_DISTANCE_FUNCTION_PARAM.

K_ID

public static final OptionID K_ID

OptionID for K_PARAM

K_PARAM

private final IntParameter K_PARAM

Parameter to specify the number of nearest neighbors of an object to be considered for computing its LOF_SCORE, must be an integer greater than 1.

Key: -lof.k

k

int k

Holds the value of K_PARAM.

preprocessor1

MaterializeKNNPreprocessor<O extends DatabaseObject,D extends NumberDistance<D,?>> preprocessor1

Preprocessor Step 1

preprocessor2

MaterializeKNNPreprocessor<O extends DatabaseObject,D extends NumberDistance<D,?>> preprocessor2

Preprocessor Step 2

objectIsInKNN

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

LOF

public LOF(Parameterization config)

Constructor, adhering to Parameterizable

Parameters:

config - Parameterization

Method Detail

runInTime

protected OutlierResult runInTime(Database<O> database)
                           throws IllegalStateException

Performs the Generalized LOF_SCORE algorithm on the given database.

Specified by:

runInTime in class AbstractAlgorithm<O extends DatabaseObject,OutlierResult>

Parameters:

database - the database to run the algorithm on

Returns:

the Result computed by this algorithm

Throws:

IllegalStateException - if the algorithm has not been initialized properly (e.g. the setParameters(String[]) method has been failed to be called).