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

Class KDEOS<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.lof.KDEOS<O>

Type Parameters:

O - Object type

All Implemented Interfaces:

Algorithm, DistanceBasedAlgorithm<O>, OutlierAlgorithm

@Title(value="KDEOS: Kernel Density Estimator Outlier Score")
 @Reference(authors="Erich Schubert, Arthur Zimek, Hans-Peter Kriegel",
           title="Generalized Outlier Detection with Flexible Kernel Density Estimates",
           booktitle="Proc. 14th SIAM International Conference on Data Mining (SDM 2014)",
           url="https://doi.org/10.1137/1.9781611973440.63",
           bibkey="DBLP:conf/sdm/SchubertZK14")
public class KDEOS<O>
extends AbstractDistanceBasedAlgorithm<O,OutlierResult>
implements OutlierAlgorithm

Generalized Outlier Detection with Flexible Kernel Density Estimates.

This is an outlier detection inspired by LOF, but using kernel density estimation (KDE) from statistics. Unfortunately, for higher dimensional data, kernel density estimation itself becomes difficult. At this point, the kdeos.idim parameter can become useful, which allows to either disable dimensionality adjustment completely (0) or to set it to a lower dimensionality than the data representation. This may sound like a hack at first, but real data is often of lower intrinsic dimensionality, and embedded into a higher data representation. Adjusting the kernel to account for the representation seems to yield worse results than using a lower, intrinsic, dimensionality.

If your data set has many duplicates, the kdeos.kernel.minbw parameter sets a minimum kernel bandwidth, which may improve results in these cases, as it prevents kernels from degenerating to single points.

Reference:

Erich Schubert, Arthur Zimek, Hans-Peter Kriegel
Generalized Outlier Detection with Flexible Kernel Density Estimates
Proc. 14th SIAM International Conference on Data Mining (SDM 2014)

Since:

0.7.0

Author:

Erich Schubert

Nested Class Summary

Nested Classes

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

Field Summary

Fields

Modifier and Type	Field and Description
(package private) static double	CUTOFF Significance cutoff when computing kernel density.
(package private) int	idim Intrinsic dimensionality.
(package private) KernelDensityFunction	kernel Kernel function to use for density estimation.
(package private) int	kmax Minimum and maximum number of neighbors to use.
(package private) int	kmin Minimum and maximum number of neighbors to use.
private static Logging	LOG Class logger.
(package private) double	minBandwidth Kernel minimum bandwidth.
(package private) double	scale Kernel scaling parameter.

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

ALGORITHM_ID

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

DISTANCE_FUNCTION_ID

Constructor Summary

Constructors

Constructor and Description
KDEOS(DistanceFunction<? super O> distanceFunction, int kmin, int kmax, KernelDensityFunction kernel, double minBandwidth, double scale, int idim) Constructor.

Method Summary

Modifier and Type	Method and Description
protected void	computeOutlierScores(KNNQuery<O> knnq, DBIDs ids, WritableDataStore<double[]> densities, WritableDoubleDataStore kdeos, DoubleMinMax minmax) Compute the final KDEOS scores.
private int	dimensionality(Relation<O> rel) Ugly hack to allow using this implementation without having a well-defined dimensionality.
protected void	estimateDensities(Relation<O> rel, KNNQuery<O> knnq, DBIDs ids, WritableDataStore<double[]> densities) Perform the kernel density estimation step.
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> rel) Run the KDEOS outlier detection algorithm.

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

getDistanceFunction

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

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

Class logger.

kernel

KernelDensityFunction kernel

Kernel function to use for density estimation.

kmin

int kmin

Minimum and maximum number of neighbors to use.

kmax

int kmax

Minimum and maximum number of neighbors to use.

scale

double scale

Kernel scaling parameter.

minBandwidth

double minBandwidth

Kernel minimum bandwidth.

idim

int idim

Intrinsic dimensionality.

CUTOFF

static final double CUTOFF

Significance cutoff when computing kernel density.

See Also:

Constant Field Values

Constructor Detail

KDEOS

public KDEOS(DistanceFunction<? super O> distanceFunction,
             int kmin,
             int kmax,
             KernelDensityFunction kernel,
             double minBandwidth,
             double scale,
             int idim)

Constructor.

Parameters:

distanceFunction - Distance function

kmin - Minimum number of neighbors

kmax - Maximum number of neighbors

kernel - Kernel function

minBandwidth - Minimum bandwidth

scale - Kernel scaling parameter

idim - Intrinsic dimensionality (use 0 to use real dimensionality)

Method Detail

run

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

Run the KDEOS outlier detection algorithm.

Parameters:

database - Database to query

rel - Relation to process

Returns:

Outlier detection result

estimateDensities

protected void estimateDensities(Relation<O> rel,
                                 KNNQuery<O> knnq,
                                 DBIDs ids,
                                 WritableDataStore<double[]> densities)

Perform the kernel density estimation step.

Parameters:

rel - Relation to query

knnq - kNN query

ids - IDs to process

densities - Density storage

dimensionality

private int dimensionality(Relation<O> rel)

Ugly hack to allow using this implementation without having a well-defined dimensionality.

Parameters:

rel - Data relation

Returns:

Dimensionality

computeOutlierScores

protected void computeOutlierScores(KNNQuery<O> knnq,
                                    DBIDs ids,
                                    WritableDataStore<double[]> densities,
                                    WritableDoubleDataStore kdeos,
                                    DoubleMinMax minmax)

Compute the final KDEOS scores.

Parameters:

knnq - kNN query

ids - IDs to process

densities - Density estimates

kdeos - Score outputs

minmax - Minimum and maximum scores

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