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

Class LoOP<O>

java.lang.Object

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

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

Type Parameters:

O - type of objects handled by this algorithm

All Implemented Interfaces:

Algorithm, OutlierAlgorithm

@Title(value="LoOP: Local Outlier Probabilities")
@Description(value="Variant of the LOF algorithm normalized using statistical values.")
@Reference(authors="H.-P. Kriegel, P. Kr\u00f6ger, E. Schubert, A. Zimek",
           title="LoOP: Local Outlier Probabilities",
           booktitle="Proceedings of the 18th International Conference on Information and Knowledge Management (CIKM), Hong Kong, China, 2009",
           url="http://dx.doi.org/10.1145/1645953.1646195")
@Alias(value={"de.lmu.ifi.dbs.elki.algorithm.outlier.LoOP","LoOP"})
public class LoOP<O>
extends AbstractAlgorithm<OutlierResult>
implements OutlierAlgorithm

LoOP: Local Outlier Probabilities Distance/density based algorithm similar to LOF to detect outliers, but with statistical methods to achieve better result stability. Reference:

Hans-Peter Kriegel, Peer Kröger, Erich Schubert, Arthur Zimek:
LoOP: Local Outlier Probabilities< br /> In Proceedings of the 18th International Conference on Information and Knowledge Management (CIKM), Hong Kong, China, 2009

Implementation notes:

• The lambda parameter was removed from the pdist term, because it cancels out.
• In ELKI 0.7.0, the k parameters have changed by 1 to make them similar to other methods and more intuitive.

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	LoOP.Parameterizer<O> Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
protected DistanceFunction<? super O>	comparisonDistanceFunction Distance function for comparison set.
(package private) int	kcomp Comparison neighborhood size.
(package private) int	kreach Reachability neighborhood size.
(package private) double	lambda Lambda parameter.
private static Logging	LOG The logger for this class.
protected DistanceFunction<? super O>	reachabilityDistanceFunction Distance function for reachability.

Constructor Summary

Constructors

Constructor and Description
LoOP(int kreach, int kcomp, DistanceFunction<? super O> reachabilityDistanceFunction, DistanceFunction<? super O> comparisonDistanceFunction, double lambda) Constructor with parameters.

Method Summary

Methods

Modifier and Type	Method and Description
protected void	computePDists(Relation<O> relation, KNNQuery<O> knn, WritableDoubleDataStore pdists) Compute the probabilistic distances used by LoOP.
protected double	computePLOFs(Relation<O> relation, KNNQuery<O> knn, WritableDoubleDataStore pdists, WritableDoubleDataStore plofs) Compute the LOF values, using the pdist distances.
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected 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 LoOP algorithm on the given database.

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.

kreach

int kreach

Reachability neighborhood size.

kcomp

int kcomp

Comparison neighborhood size.

lambda

double lambda

Lambda parameter.

reachabilityDistanceFunction

protected DistanceFunction<? super O> reachabilityDistanceFunction

Distance function for reachability.

comparisonDistanceFunction

protected DistanceFunction<? super O> comparisonDistanceFunction

Distance function for comparison set.

Constructor Detail

LoOP

public LoOP(int kreach,
    int kcomp,
    DistanceFunction<? super O> reachabilityDistanceFunction,
    DistanceFunction<? super O> comparisonDistanceFunction,
    double lambda)

Constructor with parameters.

Parameters:

kreach - k for reachability

kcomp - k for comparison

reachabilityDistanceFunction - distance function for reachability

comparisonDistanceFunction - distance function for comparison

lambda - Lambda parameter

Method Detail

getKNNQueries

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

Get the kNN queries for the algorithm.

Parameters:

database - Database to analyze

relation - Relation to analyze

stepprog - Progress logger, may be null

Returns:

result

run

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

Performs the LoOP algorithm on the given database.

Parameters:

database - Database to process

relation - Relation to process

Returns:

Outlier result

computePDists

protected void computePDists(Relation<O> relation,
                 KNNQuery<O> knn,
                 WritableDoubleDataStore pdists)

Compute the probabilistic distances used by LoOP.

Parameters:

relation - Data relation

knn - kNN query

pdists - Storage for distances

computePLOFs

protected double computePLOFs(Relation<O> relation,
                  KNNQuery<O> knn,
                  WritableDoubleDataStore pdists,
                  WritableDoubleDataStore plofs)

Compute the LOF values, using the pdist distances.

Parameters:

relation - Data relation

knn - kNN query

pdists - Precomputed distances

plofs - Storage for PLOFs.

Returns:

Normalization factor.

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