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.utilities.optionhandling.AbstractParameterizable
          de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<O,R>
              de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm<O,D,MultiResult>
                  de.lmu.ifi.dbs.elki.algorithm.outlier.LOF<O,D>

Type Parameters:

O - the type of DatabaseObjects handled by this Algorithm

All Implemented Interfaces:

Algorithm<O,MultiResult>, Parameterizable

public class LOF<O extends DatabaseObject,D extends NumberDistance<D,?>>
extends DistanceBasedAlgorithm<O,D,MultiResult>

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, and 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_MAX The association id to associate the maximum LOF_SCORE of an algorithm run.
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 ClassParameter<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.
(package private) MultiResult	result Provides the result of the algorithm.

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.utilities.optionhandling.AbstractParameterizable

optionHandler

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

debug, logger

Constructor Summary

LOF()
Provides the Generalized LOF_SCORE algorithm, adding parameters K_PARAM and REACHABILITY_DISTANCE_FUNCTION_PARAM to the option handler additionally to parameters of super class.

Method Summary

Description	getDescription() Returns a description of the algorithm.
MultiResult	getResult() Returns the result of the algorithm.
protected MultiResult	runInTime(Database<O> database) Performs the Generalized LOF_SCORE algorithm on the given database.
List<String>	setParameters(List<String> args) Calls the super method and sets additionally the value of the parameter K_PARAM and instantiates reachabilityDistanceFunction according to the value of parameter REACHABILITY_DISTANCE_FUNCTION_PARAM.

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

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.utilities.optionhandling.AbstractParameterizable

addOption, addParameterizable, addParameterizable, checkGlobalParameterConstraints, collectOptions, getAttributeSettings, getParameters, rememberParametersExcept, removeOption, removeParameterizable, shortDescription

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

Methods inherited from interface de.lmu.ifi.dbs.elki.utilities.optionhandling.Parameterizable

checkGlobalParameterConstraints, collectOptions, getParameters, shortDescription

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

LOF_MAX

public static final AssociationID<Double> LOF_MAX

The association id to associate the maximum LOF_SCORE of an algorithm run.

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.

result

MultiResult result

Provides the result of the algorithm.

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()

Provides the Generalized LOF_SCORE algorithm, adding parameters K_PARAM and REACHABILITY_DISTANCE_FUNCTION_PARAM to the option handler additionally to parameters of super class.

Method Detail

runInTime

protected MultiResult 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,MultiResult>

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

getDescription

public Description getDescription()

Description copied from interface: Algorithm

Returns a description of the algorithm.

Returns:

a description of the algorithm

setParameters

public List<String> setParameters(List<String> args)
                           throws ParameterException

Calls the super method and sets additionally the value of the parameter K_PARAM and instantiates reachabilityDistanceFunction according to the value of parameter REACHABILITY_DISTANCE_FUNCTION_PARAM. The remaining parameters are passed to the reachabilityDistanceFunction.

Specified by:

setParameters in interface Parameterizable

Overrides:

setParameters in class DistanceBasedAlgorithm<O extends DatabaseObject,D extends NumberDistance<D,?>,MultiResult>

Parameters:

args - parameters to set the attributes accordingly to

Returns:

a list containing the unused parameters

Throws:

ParameterException - in case of wrong parameter-setting

getResult

public MultiResult getResult()

Description copied from interface: Algorithm

Returns the result of the algorithm.

Returns:

the result of the algorithm