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

Class DWOF<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.DWOF<O>

Type Parameters:

O - the type of DatabaseObjects handled by this Algorithm

All Implemented Interfaces:

Algorithm, DistanceBasedAlgorithm<O>, OutlierAlgorithm

@Title(value="DWOF: Dynamic Window Outlier Factor")
 @Description(value="Algorithm to compute dynamic-window outlier factors in a database based on the neighborhood size parameter \'k\'")
 @Reference(authors="R. Momtaz, N. Mohssen, M. A. Gowayyed",
           title="DWOF: A Robust Density-Based Outlier Detection Approach",
           booktitle="Pattern Recognition and Image Analysis, Proc. 6th Iberian Conference, IbPRIA 2013, Funchal, Madeira, Portugal, 2013.",
           url="http://dx.doi.org/10.1007%2F978-3-642-38628-2_61")
public class DWOF<O>
extends AbstractDistanceBasedAlgorithm<O,OutlierResult>
implements OutlierAlgorithm

Algorithm to compute dynamic-window outlier factors in a database based on a specified parameter DWOF.Parameterizer.K_ID (-dwof.k).

The parameter DWOF.Parameterizer.K_ID specifies the number of the neighbors to be considered during the calculation of the DWOF score.

All the distance queries -KNN and Range- are determined using the parameter DistanceBasedAlgorithm.DISTANCE_FUNCTION_ID

Reference:
Rana Momtaz, Nesma Mohssen and Mohammad A. Gowayyed: DWOF: A Robust Density-Based OutlierDetection Approach.
In: Pattern Recognition and Image Analysis , Proc. 6th Iberian Conference, IbPRIA 2013, Funchal, Madeira, Portugal, June 5-7, 2013.

Author:

Omar Yousry

Nested Class Summary

Nested Classes

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

Field Summary

Fields

Modifier and Type	Field and Description
private double	delta The radii changing ratio
protected int	k Holds the value of DWOF.Parameterizer.K_ID i.e.
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
DWOF(DistanceFunction<? super O> distanceFunction, int k, double delta) Constructor.

Method Summary

Modifier and Type	Method and Description
private void	clusterData(DBIDs ids, RangeQuery<O> rnnQuery, WritableDoubleDataStore radii, WritableDataStore<ModifiableDBIDs> labels) This method applies a density based clustering algorithm.
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected Logging	getLogger() Get the (STATIC) logger for this class.
private void	initializeRadii(DBIDs ids, KNNQuery<O> knnq, DistanceQuery<O> distFunc, WritableDoubleDataStore radii) This method prepares a container for the radii of the objects and initializes radii according to the equation: initialRadii of a certain object = (absoluteMinDist of all objects) * (avgDist of the object) / (minAvgDist of all objects)
OutlierResult	run(Database database, Relation<O> relation) Performs the Generalized DWOF_SCORE algorithm on the given database by calling all the other methods in the proper order.
private int	updateSizes(DBIDs ids, WritableDataStore<ModifiableDBIDs> labels, WritableIntegerDataStore newSizes) This method updates each object's cluster size after the clustering step.

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

protected int k

Holds the value of DWOF.Parameterizer.K_ID i.e. Number of neighbors to consider during the calculation of DWOF scores.

delta

private double delta

The radii changing ratio

Constructor Detail

DWOF

public DWOF(DistanceFunction<? super O> distanceFunction,
            int k,
            double delta)

Constructor.

Parameters:

distanceFunction - Distance function to use in queries

k - the value of k

delta - Radius increase factor

Method Detail

run

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

Performs the Generalized DWOF_SCORE algorithm on the given database by calling all the other methods in the proper order.

Parameters:

database - Database to query

relation - Data to process

Returns:

new OutlierResult instance

initializeRadii

private void initializeRadii(DBIDs ids,
                             KNNQuery<O> knnq,
                             DistanceQuery<O> distFunc,
                             WritableDoubleDataStore radii)

This method prepares a container for the radii of the objects and initializes radii according to the equation: initialRadii of a certain object = (absoluteMinDist of all objects) * (avgDist of the object) / (minAvgDist of all objects)

Parameters:

ids - Database IDs to process

distFunc - Distance function

knnq - kNN search function

radii - WritableDoubleDataStore to store radii

clusterData

private void clusterData(DBIDs ids,
                         RangeQuery<O> rnnQuery,
                         WritableDoubleDataStore radii,
                         WritableDataStore<ModifiableDBIDs> labels)

This method applies a density based clustering algorithm. It looks for an unclustered object and builds a new cluster for it, then adds all the points within its radius to that cluster. nChain represents the points to be added to the cluster and its radius-neighbors

Parameters:

ids - Database IDs to process

rnnQuery - Data to process

radii - Radii to cluster accordingly

labels - Label storage.

updateSizes

private int updateSizes(DBIDs ids,
                        WritableDataStore<ModifiableDBIDs> labels,
                        WritableIntegerDataStore newSizes)

This method updates each object's cluster size after the clustering step.

Parameters:

ids - Object IDs to process

labels - references for each object's cluster

newSizes - the sizes container to be updated

Returns:

the number of unclustered objects

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