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

Class AbstractAggarwalYuOutlier<V extends NumberVector>

java.lang.Object

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

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

Type Parameters:

V - Vector type

All Implemented Interfaces:

Algorithm, OutlierAlgorithm

Direct Known Subclasses:

AggarwalYuEvolutionary, AggarwalYuNaive

@Reference(authors="C.C. Aggarwal, P. S. Yu",
           title="Outlier detection for high dimensional data",
           booktitle="Proc. ACM SIGMOD Int. Conf. on Management of Data (SIGMOD 2001), Santa Barbara, CA, 2001",
           url="http://dx.doi.org/10.1145/375663.375668")
public abstract class AbstractAggarwalYuOutlier<V extends NumberVector>
extends AbstractAlgorithm<OutlierResult>
implements OutlierAlgorithm

Abstract base class for the sparse-grid-cell based outlier detection of Aggarwal and Yu. Reference:

Outlier detection for high dimensional data
C.C. Aggarwal, P. S. Yu
International Conference on Management of Data Proceedings of the 2001 ACM SIGMOD international conference on Management of data 2001, Santa Barbara, California, United States

Since:

0.4.0

Author:

Ahmed Hettab, Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	AbstractAggarwalYuOutlier.Parameterizer Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
static short	DONT_CARE Symbolic value for subspaces not in use.
static short	GENE_OFFSET The first bucket.
protected int	k The target dimensionality.
protected int	phi The number of partitions for each dimension.

Constructor Summary

Constructors

Constructor and Description
AbstractAggarwalYuOutlier(int k, int phi) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
protected ArrayList<ArrayList<DBIDs>>	buildRanges(Relation<V> relation) Grid discretization of the data: Each attribute of data is divided into phi equi-depth ranges.
protected DBIDs	computeSubspace(ArrayList<IntIntPair> subspace, ArrayList<ArrayList<DBIDs>> ranges) Method to get the ids in the given subspace.
protected DBIDs	computeSubspaceForGene(short[] gene, ArrayList<ArrayList<DBIDs>> ranges) Get the DBIDs in the current subspace.
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected static double	sparsity(int setsize, int dbsize, int k, double phi) Method to calculate the sparsity coefficient of.

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

getLogger, 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

DONT_CARE

public static final short DONT_CARE

Symbolic value for subspaces not in use.

See Also:

Constant Field Values

GENE_OFFSET

public static final short GENE_OFFSET

The first bucket.

See Also:

Constant Field Values

phi

protected int phi

The number of partitions for each dimension.

k

protected int k

The target dimensionality.

Constructor Detail

AbstractAggarwalYuOutlier

public AbstractAggarwalYuOutlier(int k,
                         int phi)

Constructor.

Parameters:

k - K parameter

phi - Phi parameter

Method Detail

buildRanges

protected ArrayList<ArrayList<DBIDs>> buildRanges(Relation<V> relation)

Grid discretization of the data:
Each attribute of data is divided into phi equi-depth ranges.
Each range contains a fraction f=1/phi of the records.

Parameters:

relation - Relation to process

Returns:

range map

sparsity

protected static double sparsity(int setsize,
              int dbsize,
              int k,
              double phi)

Method to calculate the sparsity coefficient of.

Parameters:

setsize - Size of subset

dbsize - Size of database

k - Dimensionality

phi - Phi parameter

Returns:

sparsity coefficient

computeSubspace

protected DBIDs computeSubspace(ArrayList<IntIntPair> subspace,
                    ArrayList<ArrayList<DBIDs>> ranges)

Method to get the ids in the given subspace.

Parameters:

subspace - Subspace to process

ranges - List of DBID ranges

Returns:

ids

computeSubspaceForGene

protected DBIDs computeSubspaceForGene(short[] gene,
                           ArrayList<ArrayList<DBIDs>> ranges)

Get the DBIDs in the current subspace.

Parameters:

gene - gene data

ranges - Database ranges

Returns:

resulting DBIDs

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