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

Class SOD<V extends NumberVector>

java.lang.Object

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

de.lmu.ifi.dbs.elki.algorithm.outlier.subspace.SOD<V>

Type Parameters:

V - the type of NumberVector handled by this Algorithm

All Implemented Interfaces:

Algorithm, OutlierAlgorithm

@Title(value="SOD: Subspace outlier degree")
 @Description(value="Outlier Detection in Axis-Parallel Subspaces of High Dimensional Data")
 @Reference(authors="Hans-Peter Kriegel, Peer Kr\u00f6ger, Erich Schubert, Arthur Zimek",
           title="Outlier Detection in Axis-Parallel Subspaces of High Dimensional Data",
           booktitle="Proc. Pacific-Asia Conf. on Knowledge Discovery and Data Mining (PAKDD 2009)",
           url="https://doi.org/10.1007/978-3-642-01307-2_86",
           bibkey="DBLP:conf/pakdd/KriegelKSZ09")
 @Alias(value="de.lmu.ifi.dbs.elki.algorithm.outlier.SOD")
public class SOD<V extends NumberVector>
extends AbstractAlgorithm<OutlierResult>
implements OutlierAlgorithm

Subspace Outlier Degree. Outlier detection method for axis-parallel subspaces.

Reference:

Hans-Peter Kriegel, Peer Kröger, Erich Schubert, Arthur Zimek:
Outlier Detection in Axis-Parallel Subspaces of High Dimensional Data
Proc. Pacific-Asia Conf. on Knowledge Discovery and Data Mining (PAKDD 2009)

Since:

0.2

Author:

Arthur Zimek

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	SOD.Parameterizer<V extends NumberVector> Parameterization class.
static class	SOD.SODModel SOD Model class

Field Summary

Fields

Modifier and Type	Field and Description
private double	alpha Alpha (discriminance value).
private int	knn Neighborhood size.
private static Logging	LOG The logger for this class.
private boolean	models Report models.
private SimilarityFunction<V>	similarityFunction Similarity function to use.

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

ALGORITHM_ID

Constructor Summary

Constructors

Constructor and Description
SOD(int knn, double alpha, SimilarityFunction<V> similarityFunction, boolean models) Constructor with parameters.

Method Summary

Modifier and Type	Method and Description
private static double[]	computePerDimensionVariances(Relation<? extends NumberVector> relation, double[] center, DBIDs neighborhood) Compute the per-dimension variances for the given neighborhood and center.
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected Logging	getLogger() Get the (STATIC) logger for this class.
private DBIDs	getNearestNeighbors(Relation<V> relation, SimilarityQuery<V> simQ, DBIDRef queryObject) Get the k nearest neighbors in terms of the shared nearest neighbor distance.
OutlierResult	run(Relation<V> relation) Performs the SOD algorithm on the given database.
private double	subspaceOutlierDegree(V queryObject, double[] center, long[] weightVector) Compute SOD score.

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

The logger for this class.

knn

private int knn

Neighborhood size.

alpha

private double alpha

Alpha (discriminance value).

similarityFunction

private SimilarityFunction<V extends NumberVector> similarityFunction

Similarity function to use.

models

private boolean models

Report models.

Constructor Detail

SOD

public SOD(int knn,
           double alpha,
           SimilarityFunction<V> similarityFunction,
           boolean models)

Constructor with parameters.

Parameters:

knn - knn value

alpha - Alpha parameter

similarityFunction - Shared nearest neighbor similarity function

models - Report generated models

Method Detail

run

public OutlierResult run(Relation<V> relation)

Performs the SOD algorithm on the given database.

Parameters:

relation - Data relation to process

Returns:

Outlier result

getNearestNeighbors

private DBIDs getNearestNeighbors(Relation<V> relation,
                                  SimilarityQuery<V> simQ,
                                  DBIDRef queryObject)

Get the k nearest neighbors in terms of the shared nearest neighbor distance. The query object is excluded from the knn list. FIXME: move this to the database layer.

Parameters:

relation - the database holding the objects

simQ - similarity function

queryObject - the query object for which the kNNs should be determined

Returns:

the k nearest neighbors in terms of the shared nearest neighbor distance without the query object

computePerDimensionVariances

private static double[] computePerDimensionVariances(Relation<? extends NumberVector> relation,
                                                     double[] center,
                                                     DBIDs neighborhood)

Compute the per-dimension variances for the given neighborhood and center.

Parameters:

relation - Data relation

center - Center vector

neighborhood - Neighbors

Returns:

Per-dimension variances.

subspaceOutlierDegree

private double subspaceOutlierDegree(V queryObject,
                                     double[] center,
                                     long[] weightVector)

Compute SOD score.

Parameters:

queryObject - Query object

center - Center vector

weightVector - Weight vector

Returns:

sod score

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