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

Class KNNWeightOutlier<O>

java.lang.Object

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

de.lmu.ifi.dbs.elki.algorithm.AbstractDistanceBasedAlgorithm<O,OutlierResult>

de.lmu.ifi.dbs.elki.algorithm.outlier.distance.KNNWeightOutlier<O>

Type Parameters:

O - the type of DatabaseObjects handled by this Algorithm

All Implemented Interfaces:

Algorithm, DistanceBasedAlgorithm<O>, OutlierAlgorithm

@Title(value="KNNWeight outlier detection")
 @Description(value="Outlier detection based on the sum of distances of an object to its k nearest neighbors.")
 @Reference(authors="F. Angiulli, C. Pizzuti",
           title="Fast Outlier Detection in High Dimensional Spaces",
           booktitle="Proc. European Conference on Principles of Knowledge Discovery and Data Mining (PKDD\'02), Helsinki, Finland, 2002",
           url="http://dx.doi.org/10.1007/3-540-45681-3_2")
 @Alias(value={"de.lmu.ifi.dbs.elki.algorithm.outlier.KNNWeightOutlier","knnw"})
public class KNNWeightOutlier<O>
extends AbstractDistanceBasedAlgorithm<O,OutlierResult>
implements OutlierAlgorithm

Outlier Detection based on the accumulated distances of a point to its k nearest neighbors. As in the original publication (as far as we could tell from the pseudocode included), the current point is not included in the nearest neighbors (see figures in the publication). This matches the intuition common in nearest neighbor classification, where the evaluated instances are not part of the training set; but it contrasts to the pseudocode of the kNN outlier method and the database interpretation (which returns all objects stored in the database). Furthermore, we report the sum of the k distances (called "weight" in the original publication). Other implementations may return the average distance instead, and therefore yield different results. Reference:

F. Angiulli, C. Pizzuti:
Fast Outlier Detection in High Dimensional Spaces.
In: Proc. European Conference on Principles of Knowledge Discovery and Data Mining (PKDD'02), Helsinki, Finland, 2002.

Author:

Lisa Reichert

Nested Class Summary

Nested Classes

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

Field Summary

Fields

Modifier and Type	Field and Description
private int	k Holds the number of nearest neighbors to query (including query point!)
private static Logging	LOG The logger for this class.

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

DISTANCE_FUNCTION_ID

Constructor Summary

Constructors

Constructor and Description
KNNWeightOutlier(DistanceFunction<? super O> distanceFunction, int k) Constructor with parameters.

Method Summary

Modifier and Type	Method and Description
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected Logging	getLogger() Get the (STATIC) logger for this class.
OutlierResult	run(Database database, Relation<O> relation) Runs the algorithm in the timed evaluation part.

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

getDistanceFunction

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.

k

private int k

Holds the number of nearest neighbors to query (including query point!)

Constructor Detail

KNNWeightOutlier

public KNNWeightOutlier(DistanceFunction<? super O> distanceFunction,
                        int k)

Constructor with parameters.

Parameters:

distanceFunction - Distance function

k - k Parameter (not including query point!)

Method Detail

run

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

Runs the algorithm in the timed evaluation part.

Parameters:

database - Database context

relation - Data relation

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