Package elki.outlier.density

Class HySortOD

java.lang.Object

elki.outlier.density.HySortOD

All Implemented Interfaces:

Algorithm, OutlierAlgorithm

@Title("HySortOD: Hypercube-Based Outlier Detection")
@Description("Algorithm that uses an efficient hypercube-ordering-and-searching strategy for fast outlier detection.")
@Reference(authors="Eug\u00eanio F. Cabral, and Robson L.F. Cordeiro",
           title="Fast and Scalable Outlier Detection with Sorted Hypercubes",
           booktitle="Proc. 29th ACM Int. Conf. on Information & Knowledge Management (CIKM\'20)",
           url="https://doi.org/10.1145/3340531.3412033")
public class HySortOD
extends java.lang.Object
implements OutlierAlgorithm

Hypercube-Based Outlier Detection.

Algorithm that uses an efficient hypercube-ordering-and-searching strategy for fast outlier detection. Its main focus is the analysis of data with many instances and a low-to-moderate number of dimensions.

Reference:

Eugênio F. Cabral and Robson L.F. Cordeiro
Fast and Scalable Outlier Detection with Sorted Hypercubes
Proc. 29th ACM Int. Conf. on Information and Knowledge Management (CIKM'20)

Since:

0.8.0

Author:

Cabral, Eugênio F. (Original Code), Braulio V.S. Vinces (ELKIfication)

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private static class	HySortOD.DensityStrategy	Strategy for compute density.
private static class	HySortOD.Hypercube	Bounded regions of the space where at least one instance exists.
private static class	HySortOD.NaiveStrategy	Naive strategy for computing density.
private static class	HySortOD.TreeStrategy	Tree strategy for computing density.

Nested classes/interfaces inherited from interface elki.Algorithm

Algorithm.Utils

Field Summary

Fields

Modifier and Type	Field	Description
private int	b	Number of bins.
private double	l	Hypercube's length.
private static Logging	LOG	The logger for this class.
private HySortOD.DensityStrategy	strategy	Strategy for hypercubes density search.

Constructor Summary

Constructors

Constructor	Description
HySortOD(int b, int minSplit)	Constructor with parameters.

Method Summary

Modifier and Type	Method	Description
TypeInformation[]	getInputTypeRestriction()	Get the input type restriction used for negotiating the data query.
private java.util.List<HySortOD.Hypercube>	getSortedHypercubes(Relation<? extends NumberVector> relation)	Create and sort hypercubes considering their coordinates.
OutlierResult	run(Database db, Relation<? extends NumberVector> relation)
private double	score(int density)	Compute score according to hypercube neighborhood density.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface elki.outlier.OutlierAlgorithm

autorun

Field Detail

LOG

private static final Logging LOG

The logger for this class.

b

private int b

Number of bins.

l

private final double l

Hypercube's length.

strategy

private HySortOD.DensityStrategy strategy

Strategy for hypercubes density search.

Constructor Detail

HySortOD

public HySortOD(int b,
                int minSplit)

Constructor with parameters.

Parameters:

b - Number of bins

minSplit - Threshold to balance the tree strategy

Method Detail

run

public OutlierResult run(Database db,
                         Relation<? extends NumberVector> relation)

getSortedHypercubes

private java.util.List<HySortOD.Hypercube> getSortedHypercubes(Relation<? extends NumberVector> relation)

Create and sort hypercubes considering their coordinates.

Parameters:

relation - Data to process

Returns:

Hypercubes sorted

score

private double score(int density)

Compute score according to hypercube neighborhood density.

Parameters:

density - Hypercube density

Returns:

score

getInputTypeRestriction

public TypeInformation[] getInputTypeRestriction()

Description copied from interface: Algorithm

Get the input type restriction used for negotiating the data query.

Specified by:

getInputTypeRestriction in interface Algorithm

Returns:

Type restriction