Note: currently, only dense vector columns are supported.

###### Vector Dimensionality Filter

(since 0.7.0)

de.lmu.ifi.dbs.elki.datasource.filter.cleaning.VectorDimensionalityFilter

Filter to remove all vectors that do not have the desired dimensionality.

#####  O.2 Normalization

de.lmu.ifi.dbs.elki.datasource.filter.normalization package:

Data normalization.

######  O.2.1 Normalization Columnwise

de.lmu.ifi.dbs.elki.datasource.filter.normalization.columnwise package:

Normalizations operating on columns / variates; where each column is treated
independently.

###### Attribute Wise Beta Normalization

(since 0.7.0)

de.lmu.ifi.dbs.elki.datasource.filter.normalization.columnwise.AttributeWiseBetaNormalization

Project the data using a Beta distribution.

This is a crude heuristic, that may or may not work for your data set. There
currently is no theoretical foundation of why it may be sensible or not to do
this.

###### Attribute Wise CDF Normalization

(since 0.6.0)

de.lmu.ifi.dbs.elki.datasource.filter.normalization.columnwise.AttributeWiseCDFNormalization

Class to perform and undo a normalization on real vectors by estimating the
distribution of values along each dimension independently, then rescaling
objects to the cumulative density function (CDF) value at the original
coordinate.

This process is for example also mentioned in section 3.4 of

Effects of Feature Normalization on Image Retrieval
S. Aksoy, R. M. Haralick

but they do not detail how to obtain an appropriate function ‘F‘.

###### Attribute Wise MAD Normalization

(since 0.6.0)

de.lmu.ifi.dbs.elki.datasource.filter.normalization.columnwise.AttributeWiseMADNormalization

Median Absolute Deviation is used for scaling the data set as follows:

First, the median, and median absolute deviation are computed in each axis.
Then, each value is projected to (x - median(X)) / MAD(X).

This is similar to z-standardization of data sets, except that it is more
robust towards outliers, and only slightly more expensive to compute.

###### Attribute Wise Mean Normalization

(since 0.4.0)

de.lmu.ifi.dbs.elki.datasource.filter.normalization.columnwise.AttributeWiseMeanNormalization

Normalization designed for data with a meaningful zero:
The 0 is retained, and the data is linearly scaled to have a mean of 1, by
projection with f(x) = x / mean(X).

Each attribute is processed separately.

###### Attribute Wise Min Max Normalization

(since 0.4.0)

de.lmu.ifi.dbs.elki.datasource.filter.normalization.columnwise.AttributeWiseMinMaxNormalization

Class to perform and undo a normalization on real vectors with respect to a
given minimum and maximum in each dimension. This class performs a linear
scaling on the data.

###### Attribute Wise Variance Normalization

(since 0.4.0)

de.lmu.ifi.dbs.elki.datasource.filter.normalization.columnwise.AttributeWiseVarianceNormalization

Class to perform and undo a normalization on real vectors with respect to
given mean and standard deviation in each dimension.

We use the biased variance (MeanVariance.getNaiveStddev()), because this
produces that with exactly standard deviation 1. While often the unbiased
estimate (MeanVariance.getSampleStddev()) is more appropriate, it will not
ensure this interesting property. For large data, the difference will be small
anyway.

###### Integer Rank Tie Normalization

(since 0.5.0)

de.lmu.ifi.dbs.elki.datasource.filter.normalization.columnwise.IntegerRankTieNormalization

Normalize vectors according to their rank in the attributes.

Note: ranks are multiplied by 2, to be able to give ties an integer rank.
(e.g. when the first two records are tied, they both have rank "1" then,
followed by the next on "4")

###### Inverse Document Frequency Normalization

(since 0.4.0)

de.lmu.ifi.dbs.elki.datasource.filter.normalization.columnwise.InverseDocumentFrequencyNormalization

Normalization for text frequency (TF) vectors, using the inverse document
frequency (IDF). See also: TF-IDF for text analysis.

######  O.2.2 Normalization Instancewise

de.lmu.ifi.dbs.elki.datasource.filter.normalization.instancewise package:

Instancewise normalization, where each instance is normalized independently.

###### Hellinger Histogram Normalization

(since 0.7.0)

de.lmu.ifi.dbs.elki.datasource.filter.normalization.instancewise.HellingerHistogramNormalization

Normalize histograms by scaling them to unit absolute sum, then taking the
square root of the absolute value in each attribute, times the normalization
constant $1/\sqrt{2}$.

$H(x_{i})=\tfrac{\sqrt{|x_{i}|/\Sigma}}{\sqrt{2}}\quad\text{ with
}\Sigma=\sum\nolimits_{i}|x_{i}|$

Using Euclidean distance (linear kernel) and this transformation is the same
as using Hellinger distance: HellingerDistanceFunction

###### Instance Log Rank Normalization

(since 0.7.0)

de.lmu.ifi.dbs.elki.datasource.filter.normalization.instancewise.InstanceLogRankNormalization

Normalize vectors such that the smallest value of each instance is 0, the
largest is 1, but using $\log_{2}(1+x)$.

###### Instance Mean Variance Normalization

(since 0.7.0)

de.lmu.ifi.dbs.elki.datasource.filter.normalization.instancewise.InstanceMeanVarianceNormalization

Normalize vectors such that they have zero mean and unit variance.

###### Instance Min Max Normalization

(since 0.7.0)

de.lmu.ifi.dbs.elki.datasource.filter.normalization.instancewise.InstanceMinMaxNormalization

Normalize vectors with respect to a given minimum and maximum in each
dimension. By default, minimum 0 and maximum 1 is used. This class performs a
linear scaling on the data.

###### Instance Rank Normalization

(since 0.7.0)

de.lmu.ifi.dbs.elki.datasource.filter.normalization.instancewise.InstanceRankNormalization

Normalize vectors such that the smallest value of each instance is 0, the
largest is 1.

###### Length Normalization

(since 0.5.0)

de.lmu.ifi.dbs.elki.datasource.filter.normalization.instancewise.LengthNormalization

Class to perform a normalization on vectors to norm 1.

###### Log1 Plus Normalization

(since 0.7.0)

de.lmu.ifi.dbs.elki.datasource.filter.normalization.instancewise.Log1PlusNormalization

Normalize the data set by applying $\frac{\log(1+|x|b)}{\log 1+b}$ to any
value. If the input data was in [0;1], then the resulting values will be in
[0;1], too.

By default b=1, and thus the transformation is $\log_{2}(1+|x|)$.

#####  O.3 Selection

de.lmu.ifi.dbs.elki.datasource.filter.selection package:

Filters for selecting and sorting data to process.

###### By Label Filter

(since 0.4.0)

de.lmu.ifi.dbs.elki.datasource.filter.selection.ByLabelFilter

A filter to select data set by their label.

###### Random Sampling Stream Filter

(since 0.5.0)

de.lmu.ifi.dbs.elki.datasource.filter.selection.RandomSamplingStreamFilter

Subsampling stream filter.

###### Shuffle Objects Filter

(since 0.4.0)

de.lmu.ifi.dbs.elki.datasource.filter.selection.ShuffleObjectsFilter

A filter to shuffle the dataset.

###### Sort By Label Filter

(since 0.4.0)

de.lmu.ifi.dbs.elki.datasource.filter.selection.SortByLabelFilter

A filter to sort the data set by some label. The filter sorts the labels in
alphabetical order.

#####  O.4 Transform

de.lmu.ifi.dbs.elki.datasource.filter.transform package:

Data space transformations.

###### Classic Multidimensional Scaling Transform

(since 0.6.0)

de.lmu.ifi.dbs.elki.datasource.filter.transform.ClassicMultidimensionalScalingTransform

Rescale the data set using multidimensional scaling, MDS.

Note: the current implementation is rather expensive, both memory- and runtime
wise. Don’t use for large data sets! Instead, have a look at
FastMultidimensionalScalingTransform which uses power iterations instead.

###### Fast Multidimensional Scaling Transform

(since 0.7.0)

de.lmu.ifi.dbs.elki.datasource.filter.transform.FastMultidimensionalScalingTransform

Rescale the data set using multidimensional scaling, MDS.

This implementation uses power iterations, which is faster when the number of
data points is much larger than the desired number of dimensions.

This implementation is O(n²), and uses O(n²) memory.

###### Global Principal Component Analysis Transform

(since 0.5.0)

de.lmu.ifi.dbs.elki.datasource.filter.transform.GlobalPrincipalComponentAnalysisTransform

Apply Principal Component Analysis (PCA) to the data set.

This is also popular form of "Whitening transformation", and will project the
data to have a unit covariance matrix.

If you want to also reduce dimensionality, set the -pca.filter parameter! Note
that this implementation currently will always perform a full matrix
inversion. For very high dimensional data, this can take an excessive amount
of time O(d³) and memory O(d²). Please contribute a better implementation to
ELKI that only computes the requiried dimensions, yet allows for the same
filtering flexibility.

###### Histogram Jitter Filter

(since 0.5.5)

de.lmu.ifi.dbs.elki.datasource.filter.transform.HistogramJitterFilter

Add Jitter, preserving the histogram properties (same sum, nonnegative).

For each vector, the total sum of all dimensions is computed.
Then a random vector of the average length jitter * scale is added and the
result normalized to the original vectors sum. The individual dimensions are
drawn from an exponential distribution with scale jitter / dimensionality, so
it is expected that the error in most dimensions will be low, and higher in
few.

This is designed to degrade the quality of a histogram, while preserving the
total sum (e.g. to keep the normalization). The factor "jitter" can be used to
control the degradation amount.

###### LatLngToECEF Filter

(since 0.6.0)

de.lmu.ifi.dbs.elki.datasource.filter.transform.LatLngToECEFFilter

Project a 2D data set (latitude, longitude) to a 3D coordinate system (X, Y,
Z), such that Euclidean distance is line-of-sight.

###### Linear Discriminant Analysis Filter

[Fis36] (since 0.6.0)

de.lmu.ifi.dbs.elki.datasource.filter.transform.LinearDiscriminantAnalysisFilter

Linear Discriminant Analysis (LDA) / Fisher’s linear discriminant.

###### LngLatToECEF Filter

(since 0.6.0)

de.lmu.ifi.dbs.elki.datasource.filter.transform.LngLatToECEFFilter

Project a 2D data set (longitude, latitude) to a 3D coordinate system (X, Y,
Z), such that Euclidean distance is line-of-sight.

###### Number Vector Feature Selection Filter

(since 0.5.5)

de.lmu.ifi.dbs.elki.datasource.filter.transform.NumberVectorFeatureSelectionFilter

Parser to project the ParsingResult obtained by a suitable base parser onto a
selected subset of attributes.

###### Number Vector Random Feature Selection Filter

(since 0.4.0)

de.lmu.ifi.dbs.elki.datasource.filter.transform.NumberVectorRandomFeatureSelectionFilter

Parser to project the ParsingResult obtained by a suitable base parser onto a
randomly selected subset of attributes.

###### Data Perturbation for Outlier Detection Ensembles

[ZCS14] (since 0.7.0)

de.lmu.ifi.dbs.elki.datasource.filter.transform.PerturbationFilter

A filter to perturb the values by adding micro-noise.

The added noise is generated, attribute-wise, by a Gaussian with mean=0 and a
specified standard deviation or by a uniform distribution with a specified
range. The standard deviation or the range can be scaled, attribute-wise, to a
given percentage of the original standard deviation in the data distribution
(assuming a Gaussian distribution there), or to a percentage of the extension
in each attribute (maximumValue - minimumValue).

This filter has a potentially wide use but has been implemented for the
following publication:

###### Projection Filter

(since 0.6.0)

de.lmu.ifi.dbs.elki.datasource.filter.transform.ProjectionFilter

Apply a projection to the data.

#####  O.5 Typeconversions

de.lmu.ifi.dbs.elki.datasource.filter.typeconversions package:

Filters to perform data type conversions.

###### Class Label Filter

(since 0.4.0)

de.lmu.ifi.dbs.elki.datasource.filter.typeconversions.ClassLabelFilter

Class that turns a label column into a class label column.

###### Class Label From Pattern Filter

(since 0.6.0)

de.lmu.ifi.dbs.elki.datasource.filter.typeconversions.ClassLabelFromPatternFilter

Streaming filter to derive an outlier class label.

###### External ID Filter

(since 0.4.0)

de.lmu.ifi.dbs.elki.datasource.filter.typeconversions.ExternalIDFilter

Class that turns a label column into an external ID column.

###### Multivariate Time Series Filter

(since 0.7.0)

de.lmu.ifi.dbs.elki.datasource.filter.typeconversions.MultivariateTimeSeriesFilter

Class to "fold" a flat number vector into a multivariate time series.

###### Sparse Vector Field Filter

(since 0.5.0)

de.lmu.ifi.dbs.elki.datasource.filter.typeconversions.SparseVectorFieldFilter

Class that turns sparse float vectors into a proper vector field, by setting
the maximum dimensionality for each vector.

###### Split Number Vector Filter

(since 0.4.0)

de.lmu.ifi.dbs.elki.datasource.filter.typeconversions.SplitNumberVectorFilter

Split an existing column into two types.

###### Uncertain Split Filter

(since 0.7.0)

de.lmu.ifi.dbs.elki.datasource.filter.typeconversions.UncertainSplitFilter

Filter to transform a single vector into a set of samples to interpret as
uncertain observation.

###### Uncertainify Filter

(since 0.7.0)

de.lmu.ifi.dbs.elki.datasource.filter.typeconversions.UncertainifyFilter

Filter class to transform a database containing vector fields into a database
containing UncertainObject fields by invoking a Uncertainifier on each vector.

The purpose for that is to use those transformed databases in experiments
regarding uncertain data in some way.

###### Weighted Uncertain Split Filter

(since 0.7.0)

de.lmu.ifi.dbs.elki.datasource.filter.typeconversions.WeightedUncertainSplitFilter

Filter to transform a single vector into a set of samples and weights to
interpret as uncertain observation.

###  Appendix P Parser

de.lmu.ifi.dbs.elki.datasource.parser package:

Parsers for different file formats and data types.

The general use-case for any parser is to create objects out of an InputStream
(e.g. by reading a data file). The objects are packed in a
MultipleObjectsBundle which, in turn, is used by a DatabaseConnection-Object
to fill a Database containing the corresponding objects.

By default (i.e., if the user does not specify any specific requests), any
KDDTask will use the StaticArrayDatabase which, in turn, will use a
FileBasedDatabaseConnection and a NumberVectorLabelParser to parse a specified
data file creating a StaticArrayDatabase containing DoubleVector-Objects.

Thus, the standard procedure to use a data set of a real-valued vector space
is to prepare the data set in a file of the following format (as suitable to
NumberVectorLabelParser):

  * •

One point per line, attributes separated by whitespace.

  * •

Several labels may be given per point. A label must not be parseable as
double.

  * •

Lines starting with "#" will be ignored.

  * •

An index can be specified to identify an entry to be treated as class label.
This index counts all entries (numeric and labels as well) starting with 0.

  * •

Files can be gzip compressed.

This file format is e.g. also suitable to gnuplot.

As an example file following these requirements consider e.g.: exampledata.txt

###### ARFF File Format Parser

(since 0.4.0)

de.lmu.ifi.dbs.elki.datasource.parser.ArffParser

Parser to load WEKA .arff files into ELKI.

This parser is quite hackish, and contains lots of not yet configurable magic.

###### Bit Vector Label Parser

(since 0.1)

de.lmu.ifi.dbs.elki.datasource.parser.BitVectorLabelParser

Parser for parsing one BitVector per line, bits separated by whitespace.

Several labels may be given per BitVector. A label must not be parseable as
Bit. Lines starting with "#" will be ignored.

###### CSV Reader Format

(since 0.1)

de.lmu.ifi.dbs.elki.datasource.parser.CSVReaderFormat

Basic format factory for parsing CSV-like formats.

To read CSV files into ELKI, see NumberVectorLabelParser.

This class encapsulates csv format settings, that need to be parsed in
multiple places from ELKI, not only on input vector files.

###### Categorial Data As Number Vector Parser

(since 0.6.0)

de.lmu.ifi.dbs.elki.datasource.parser.CategorialDataAsNumberVectorParser

A very simple parser for categorial data, which will then be encoded as
numbers. This is closely modeled after the number vector parser.

###### Clustering Vector Parser

(since 0.7.0)

de.lmu.ifi.dbs.elki.datasource.parser.ClusteringVectorParser

Parser for simple clustering results in vector form, as written by
ClusteringVectorDumper.

This allows reading the output of multiple clustering runs, and analyze the
results using ELKI algorithm.

The input format is very simple, each line containing a sequence of cluster
assignments in integer form, and an optional label:

0 0 1 1 0 First0 0 0 1 2 Secondrepresents two clusterings for 5 objects. The
first clustering has two clusters, the second contains three clusters.

###### libSVM Format Parser

(since 0.7.0)

de.lmu.ifi.dbs.elki.datasource.parser.LibSVMFormatParser

Parser to read libSVM format files.

The format of libSVM is roughly specified in the README given:

<label> <index1>:<value1> <index2>:<value2> ...

i.e. a mandatory integer class label in the beginning followed by a classic
sparse vector representation of the data. indexes are integers, starting at 1
(Note that ELKI uses 0-based indexing, so we will map these to index-1) to not
always have a constant-0 dimension 0.

The libSVM FAQ states that you can also put comments into the file, separated
by a hash: #, but they must not contain colons and are not officially
supported.
ELKI will simply stop parsing a line when encountering a #.

###### Number Vector Label Parser

(since 0.1)

de.lmu.ifi.dbs.elki.datasource.parser.NumberVectorLabelParser

Parser for a simple CSV type of format, with columns separated by the given
pattern (default: whitespace).

Several labels may be given per point. A label must not be parseable as
double. Lines starting with "#" will be ignored.

An index can be specified to identify an entry to be treated as class label.
This index counts all entries (numeric and labels as well) starting with 0.

###### Simple Polygon Parser

(since 0.4.0)

de.lmu.ifi.dbs.elki.datasource.parser.SimplePolygonParser

Parser to load polygon data (2D and 3D only) from a simple format. One record
per line, points separated by whitespace, numbers separated by colons.
Multiple polygons components can be separated using \--.

Unparseable parts will be treated as labels.

###### Simple Transaction Parser

(since 0.7.0)

de.lmu.ifi.dbs.elki.datasource.parser.SimpleTransactionParser

Simple parser for transactional data, such as market baskets.

To keep the input format simple and readable, all tokens are assumed to be of
text and separated by whitespace, and each transaction is on a separate line.

An example file containing two transactions looks like this

bread butter milkpaste tomato basil

###### Sparse Vector Label Parser

(since 0.2)

de.lmu.ifi.dbs.elki.datasource.parser.SparseNumberVectorLabelParser

Parser for parsing one point per line, attributes separated by whitespace.

Several labels may be given per point. A label must not be parseable as
double. Lines starting with "#" will be ignored.

A line is expected in the following format: The first entry of each line is
the number of attributes with coordinate value not zero. Subsequent entries
are of the form index value  each, where index is the number of the
corresponding dimension, and value is the value of the corresponding
attribute. A complete line then could look like this:

3 7 12.34 8 56.78 11 1.234 objectlabelwhere 3 indicates there are three
attributes set, 7,8,11 are the attributes indexes and there is a non-numerical
object label.

An index can be specified to identify an entry to be treated as class label.
This index counts all entries (numeric and labels as well) starting with 0.

###### String Parser

(since 0.6.0)

de.lmu.ifi.dbs.elki.datasource.parser.StringParser

Parser that loads a text file for use with string similarity measures.

The parser produces two relations: the first of type String, the second of
type label list, which contains the same data for convenience.

###### Term Frequency Parser

(since 0.4.0)

de.lmu.ifi.dbs.elki.datasource.parser.TermFrequencyParser

A parser to load term frequency data, which essentially are sparse vectors
with text keys.

Parse a file containing term frequencies. The expected format is:

rowlabel1 term1 <freq> term2 <freq> ...rowlabel2 term1 <freq> term3 <freq> ...

Terms must not contain the separator character!

If your data does not contain frequencies, you can maybe use
SimpleTransactionParser instead.

###  Chapter Distance

de.lmu.ifi.dbs.elki.distance package:

###  Appendix Q Distancefunction

de.lmu.ifi.dbs.elki.distance.distancefunction package:

Distance functions for use within ELKI.

###### Distance functions

There are three basic types of distance functions:

  * •

Primitive Distance Functions that can be computed for any two objects.

  * •

DBID Distance Functions, that are only defined for object IDs, e.g. an
external distance matrix

  * •

Index-Based Distance Functions, that require an indexing/preprocessing step,
and are then valid for existing database objects.

These types differ significantly in both implementation and use.

###### Using distance functions

As a ’consumer’ of distances, you usually do not care about the type of
distance function you want to use. To facilitate this, a distance function can
be bound to a database by calling the ’instantiate’ method to obtain a
DistanceQuery object. A distance query is a best-effort adapter for the given
distance function. Usually, you pass it two DBIDs and get the distance value
back. When required, the adapter will get the appropriate records from the
database needed to compute the distance.

Note: instantiating a preprocessor based distance will invoke the
preprocessing step. It is recommended to do this as soon as possible, and only
instantiate the query once, then pass the query object through the various
methods.

###### Code example

DistanceQuery<V> distanceQuery =
database.getDistanceQuery(EuclideanDistanceFunction.STATIC);

###### Arc Cosine Distance Function

(since 0.2)

de.lmu.ifi.dbs.elki.distance.distancefunction.ArcCosineDistanceFunction

Arcus cosine distance function for feature vectors.

The arc cosine distance is computed as the arcus from the cosine similarity
value, i.e., arccos(<v1,v2>).

Cosine similarity is defined as

$\tfrac{\vec{x}\cdot\vec{y}}{||a||\cdot||b||}$

Arcus cosine distance then is

$\text{arccos}\tfrac{\vec{x}\cdot\vec{y}}{||a||\cdot||b||}\in[0;\pi]$

CosineDistanceFunction is a bit less expensive, and will yield the same
ranking of neighbors.

###### Arc Cosine Unitlength Distance Function

(since 0.7.5)

de.lmu.ifi.dbs.elki.distance.distancefunction.ArcCosineUnitlengthDistanceFunction

Arcus cosine distance function for feature vectors.

The arc cosine distance is computed as the arcus from the cosine similarity
value, i.e., arccos(<v1,v2>).

Cosine similarity is defined as

$\tfrac{\vec{x}\cdot\vec{y}}{||a||\cdot||b||}=_{||a||=||b||=1}\vec{x}\cdot\vec{y}$

Arcus cosine distance then is

$\operatorname{arccos}\tfrac{\vec{x}\cdot\vec{y}}{||a||\cdot||b||}=_{||a||=||b||=1}\operatorname{arccos}\vec{x}\cdot\vec{y}\in[0;\pi]$

This implementation assumes that $||a||=||b||=1$. If this does not hold for
your data, use ArcCosineDistanceFunction instead!

CosineUnitlengthDistanceFunction is a bit less expensive, and will yield the
same ranking of neighbors.

###### Bray Curtis Distance Function

[Sø48, BC57, Dic45] (since 0.6.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.BrayCurtisDistanceFunction

Bray-Curtis distance function / Sørensen–Dice coefficient for continuous
vector spaces (not only binary data).

###### Canberra Distance Function

[LW66] (since 0.5.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.CanberraDistanceFunction

Canberra distance function, a variation of Manhattan distance.

Canberra distance is defined as:

$\text{Canberra}(\vec{x},\vec{y}):=\sum\nolimits_{i}\tfrac{|x_{i}-y_{i}|}{|x_{i}|+|y_{i}|}$

###### Clark Distance Function

[DD09] (since 0.6.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.ClarkDistanceFunction

Clark distance function for vector spaces.

Clark distance is defined as:

$\text{Clark}(\vec{x},\vec{y}):=\sqrt{\tfrac{1}{d}\sum\nolimits_{i}\left(\tfrac{|x_{i}-y_{i}|}{|x_{i}|+|y_{i}|}\right)^{2}}$

###### Cosine Distance Function

(since 0.1)

de.lmu.ifi.dbs.elki.distance.distancefunction.CosineDistanceFunction

Cosine distance function for feature vectors.

The cosine distance is computed from the cosine similarity by 1-(cosine
similarity).

Cosine similarity is defined as

$\tfrac{\vec{x}\cdot\vec{y}}{||a||\cdot||b||}$

Cosine distance then is defined as

$1-\tfrac{\vec{x}\cdot\vec{y}}{||a||\cdot||b||}\in[0;2]$

ArcCosineDistanceFunction may sometimes be more appropriate, but also more
computationally expensive.

###### Cosine Unitlength Distance Function

(since 0.7.5)

de.lmu.ifi.dbs.elki.distance.distancefunction.CosineUnitlengthDistanceFunction

Cosine distance function for unit length feature vectors.

The cosine distance is computed from the cosine similarity by 1-(cosine
similarity).

Cosine similarity is defined as

$\tfrac{\vec{x}\cdot\vec{y}}{||a||\cdot||b||}=_{||a||=||b||=1}\vec{x}\cdot\vec{y}$

Cosine distance then is defined as

$1-\tfrac{\vec{x}\cdot\vec{y}}{||a||\cdot||b||}=_{||a||=||b||=1}1-\vec{x}\cdot\vec{y}\in[0;2]$

This implementation assumes that $||a||=||b||=1$. If this does not hold for
your data, use CosineDistanceFunction instead!

ArcCosineUnitlengthDistanceFunction may sometimes be more appropriate, but
also more computationally expensive.

###### Mahalanobis Distance Function

[Mah36] (since 0.7.5)

de.lmu.ifi.dbs.elki.distance.distancefunction.MahalanobisDistanceFunction

Mahalanobis quadratic form distance for feature vectors.

For a weight matrix M, this distance is defined as

$\text{Mahalanobis}_{M}(\vec{x},\vec{y}):=\sqrt{(\vec{x}-\vec{y})^{T}\cdot
M\cdot(\vec{x}-\vec{y})}$

###### Random Stable Distance Function

(since 0.4.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.RandomStableDistanceFunction

This is a dummy distance providing random values (obviously not metrical),
useful mostly for unit tests and baseline evaluations: obviously this distance
provides no benefit whatsoever.

This distance is based on the combined hash codes of the two objects queried,
if they are different. Extra caution is done to ensure symmetry and objects
with the same ID will have a distance of 0. Obviously this distance is not
metrical.

###### Shared Nearest Neighbor Jaccard Distance Function

(since 0.4.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.SharedNearestNeighborJaccardDistanceFunction

SharedNearestNeighborJaccardDistanceFunction computes the Jaccard coefficient,
which is a proper distance metric.

###### Weighted Canberra Distance Function

(since 0.5.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.WeightedCanberraDistanceFunction

Weighted Canberra distance function, a variation of Manhattan distance.

#####  Q.1 Adapter

de.lmu.ifi.dbs.elki.distance.distancefunction.adapter package:

Distance functions deriving distances from e.g. similarity measures

###### Arccos Similarity Adapter

(since 0.2)

de.lmu.ifi.dbs.elki.distance.distancefunction.adapter.ArccosSimilarityAdapter

Adapter from a normalized similarity function to a distance function using
arccos(sim).

###### Linear Adapter Linear

(since 0.2)

de.lmu.ifi.dbs.elki.distance.distancefunction.adapter.LinearAdapterLinear

Adapter from a normalized similarity function to a distance function using 1 -
sim.

###### Ln Similarity Adapter

(since 0.2)

de.lmu.ifi.dbs.elki.distance.distancefunction.adapter.LnSimilarityAdapter

Adapter from a normalized similarity function to a distance function using
-log(sim).

#####  Q.2 Colorhistogram

de.lmu.ifi.dbs.elki.distance.distancefunction.colorhistogram package:

Distance functions using correlations.

###### HSB Histogram Quadratic Distance Function

[SC96] (since 0.3)

de.lmu.ifi.dbs.elki.distance.distancefunction.colorhistogram.HSBHistogramQuadraticDistanceFunction

Distance function for HSB color histograms based on a quadratic form and color
similarity.

The matrix is filled according to:

VisualSEEk: a fully automated content-based image query system
J. R. Smith, S. F. Chang
Proc. 4th ACM Int. Conf. on Multimedia 1997

###### Histogram Intersection Distance Function

[SB91] (since 0.3)

de.lmu.ifi.dbs.elki.distance.distancefunction.colorhistogram.HistogramIntersectionDistanceFunction

Intersection distance for color histograms.

Distance function for color histograms that emphasizes ’strong’ bins.

###### RGB Histogram Quadratic Distance Function

[HSE+95] (since 0.3)

de.lmu.ifi.dbs.elki.distance.distancefunction.colorhistogram.RGBHistogramQuadraticDistanceFunction

Distance function for RGB color histograms based on a quadratic form and color
similarity.

#####  Q.3 Correlation

de.lmu.ifi.dbs.elki.distance.distancefunction.correlation package:

Distance functions using correlations.

###### Absolute Pearson Correlation Distance Function

(since 0.7.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.correlation.AbsolutePearsonCorrelationDistanceFunction

Absolute Pearson correlation distance function for feature vectors.

The absolute Pearson correlation distance is computed from the Pearson
correlation coefficient r as: 1-abs(r).

The distance between two vectors will be low (near 0), if their attribute
values are dimension-wise strictly positively or negatively correlated, it
will be high (near 1), if their attribute values are dimension-wise
uncorrelated.

###### Absolute Uncentered Correlation Distance Function

(since 0.7.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.correlation.AbsoluteUncenteredCorrelationDistanceFunction

Absolute uncentered correlation distance function for feature vectors.

This is highly similar to AbsolutePearsonCorrelationDistanceFunction, but uses
a fixed mean of 0 instead of the sample mean.

###### Pearson Correlation Distance Function

(since 0.3)

de.lmu.ifi.dbs.elki.distance.distancefunction.correlation.PearsonCorrelationDistanceFunction

Pearson correlation distance function for feature vectors.

The Pearson correlation distance is computed from the Pearson correlation
coefficient r as: 1-r. Hence, possible values of this distance are between 0
and 2.

The distance between two vectors will be low (near 0), if their attribute
values are dimension-wise strictly positively correlated, it will be high
(near 2), if their attribute values are dimension-wise strictly negatively
correlated. For Features with uncorrelated attributes, the distance value will
be intermediate (around 1).

###### Squared Pearson Correlation Distance Function

(since 0.3)

de.lmu.ifi.dbs.elki.distance.distancefunction.correlation.SquaredPearsonCorrelationDistanceFunction

Squared Pearson correlation distance function for feature vectors.

The squared Pearson correlation distance is computed from the Pearson
correlation coefficient $r$ as: $1-r^{2}$. Hence, possible values of this
distance are between 0 and 1.

The distance between two vectors will be low (near 0), if their attribute
values are dimension-wise strictly positively or negatively correlated. For
features with uncorrelated attributes, the distance value will be high (near
1).

###### Squared Uncentered Correlation Distance Function

(since 0.7.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.correlation.SquaredUncenteredCorrelationDistanceFunction

Squared uncentered correlation distance function for feature vectors.

This is highly similar to SquaredPearsonCorrelationDistanceFunction, but uses
a fixed mean of 0 instead of the sample mean.

###### Uncentered Correlation Distance Function

(since 0.7.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.correlation.UncenteredCorrelationDistanceFunction

Uncentered correlation distance.

This is highly similar to PearsonCorrelationDistanceFunction, but uses a fixed
mean of 0 instead of the sample mean.

###### Weighted Pearson Correlation Distance Function

(since 0.4.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.correlation.WeightedPearsonCorrelationDistanceFunction

Pearson correlation distance function for feature vectors.

The Pearson correlation distance is computed from the Pearson correlation
coefficient r as: 1-r. Hence, possible values of this distance are between 0
and 2.

The distance between two vectors will be low (near 0), if their attribute
values are dimension-wise strictly positively correlated, it will be high
(near 2), if their attribute values are dimension-wise strictly negatively
correlated. For Features with uncorrelated attributes, the distance value will
be intermediate (around 1).

This variation is for weighted dimensions.

###### Weighted Squared Pearson Correlation Distance Function

(since 0.4.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.correlation.WeightedSquaredPearsonCorrelationDistanceFunction

Weighted squared Pearson correlation distance function for feature vectors.

The squared Pearson correlation distance is computed from the Pearson
correlation coefficient $r$ as: $1-r^{2}$. Hence, possible values of this
distance are between 0 and 1.

The distance between two vectors will be low (near 0), if their attribute
values are dimension-wise strictly positively or negatively correlated. For
features with uncorrelated attributes, the distance value will be high (near
1).

This variation is for weighted dimensions.

#####  Q.4 External

de.lmu.ifi.dbs.elki.distance.distancefunction.external package:

Distance functions using external data sources.

###### Ascii Distance Parser

(since 0.1)

de.lmu.ifi.dbs.elki.distance.distancefunction.external.AsciiDistanceParser

Parser for parsing one distance value per line.

A line must have the following format: id1 id2 distanceValue, where id1 and
id2 are integers starting at 0 representing the two ids belonging to the
distance value. Lines starting with "#" will be ignored.

###### Disk Cache Based Double Distance Function

(since 0.2)

de.lmu.ifi.dbs.elki.distance.distancefunction.external.DiskCacheBasedDoubleDistanceFunction

Distance function that is based on double distances given by a distance matrix
of an external binary matrix file.

###### Disk Cache Based Float Distance Function

(since 0.2)

de.lmu.ifi.dbs.elki.distance.distancefunction.external.DiskCacheBasedFloatDistanceFunction

Distance function that is based on float distances given by a distance matrix
of an external binary matrix file.

###### File Based Sparse Double Distance Function

(since 0.1)

de.lmu.ifi.dbs.elki.distance.distancefunction.external.FileBasedSparseDoubleDistanceFunction

Distance function that is based on double distances given by a distance matrix
of an external ASCII file.

Note: parsing an ASCII file is rather expensive.

See AsciiDistanceParser for the default input format.

###### File Based Sparse Float Distance Function

(since 0.1)

de.lmu.ifi.dbs.elki.distance.distancefunction.external.FileBasedSparseFloatDistanceFunction

Distance function that is based on float distances given by a distance matrix
of an external ASCII file.

Note: parsing an ASCII file is rather expensive.

See AsciiDistanceParser for the default input format.

#####  Q.5 Geo

de.lmu.ifi.dbs.elki.distance.distancefunction.geo package:

Geographic (earth) distance functions.

###### Dimension Selecting Lat Lng Distance Function

[SZK13] (since 0.4.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.geo.DimensionSelectingLatLngDistanceFunction

Distance function for 2D vectors in Latitude, Longitude form.

The input data must be in degrees (not radians), and the output distance will
be in meters (see EarthModel.distanceDeg(double, double, double, double)).

This implementation allows index accelerated queries using R*-trees (by
providing a point-to-rectangle minimum distance).

###### LatLng Distance Function

[SZK13] (since 0.4.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.geo.LatLngDistanceFunction

Distance function for 2D vectors in Latitude, Longitude form.

The input data must be in degrees (not radians), and the output distance will
be in meters (see EarthModel.distanceDeg(double, double, double, double)).

This implementation allows index accelerated queries using R*-trees (by
providing a point-to-rectangle minimum distance).

###### LngLat Distance Function

[SZK13] (since 0.4.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.geo.LngLatDistanceFunction

Distance function for 2D vectors in Longitude, Latitude form.

The input data must be in degrees (not radians), and the output distance will
be in meters (see EarthModel.distanceDeg(double, double, double, double)).

This implementation allows index accelerated queries using R*-trees (by
providing a point-to-rectangle minimum distance).

#####  Q.6 Histogram

de.lmu.ifi.dbs.elki.distance.distancefunction.histogram package:

Distance functions for one-dimensional histograms.

###### Histogram Match Distance Function

[Vas69] (since 0.6.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.histogram.HistogramMatchDistanceFunction

Distance function based on histogram matching, i.e. Manhattan distance on the
cumulative density function.

This distance function assumes there exist a natural order in the vectors,
i.e. they should be some 1-dimensional histogram.

This is also known as Earth Movers Distance (EMD), 1st Mallows distance or 1st
Wasserstein metric (also Vasershtein metric), for the special case of a one-
dimensional histogram, where the cost is linear in the number of bins to
transport.

###### Kolmogorov Smirnov Distance Function

(since 0.6.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.histogram.KolmogorovSmirnovDistanceFunction

Distance function based on the Kolmogorov-Smirnov goodness of fit test.

This distance function assumes there exist a natural order in the vectors,
i.e. they should be some 1-dimensional histogram.

#####  Q.7 Minkowski

de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski package:

Minkowski space Lp norms such as the popular Euclidean and Manhattan
distances.

###### Euclidean Distance Function

(since 0.1)

de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.EuclideanDistanceFunction

Euclidean distance for NumberVectors.

Euclidean distance is defined as:

$\text{Euclidean}(\vec{x},\vec{y}):=\sqrt{\sum\nolimits_{i}(x_{i}-y_{i})^{2}}$

###### LP Norm Distance Function

(since 0.1)

de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.LPNormDistanceFunction

Lp-Norm (Minkowski norms) are a family of distances for NumberVectors.

The Lp distance is defined as:

$L_{p}(\vec{x},\vec{y}):=\left(\sum\nolimits_{i}(x_{i}-y_{i})\right)^{1/p}$

For p >= 1 this is a metric. For p=1, this yields the well known
ManhattanDistanceFunction, for p = 2 the standard EuclideanDistanceFunction.

###### Manhattan Distance Function

(since 0.1)

de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.ManhattanDistanceFunction

Manhattan distance for NumberVectors.

Manhattan distance is defined as:

$\text{Manhattan}(\vec{x},\vec{y}):=\sum_{i}|x_{i}-y_{i}|$

###### Maximum Distance Function

(since 0.3)

de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.MaximumDistanceFunction

Maximum distance for NumberVectors.

The maximum distance is defined as:

$\text{Maximum}(\vec{x},\vec{y}):=\max_{i}|x_{i}-y_{i}|$

and can be seen as limiting case of the LPNormDistanceFunction for
$p\rightarrow\infty$.

###### Minimum Distance Function

(since 0.3)

de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.MinimumDistanceFunction

Minimum distance for NumberVectors.

Minimum distance is defined as:

$\text{Minimum}_{p}(\vec{x},\vec{y}):=\min_{i}|x_{i}-y_{i}|$

This is not a metric, but can sometimes be useful as a lower bound.

###### Sparse Euclidean Distance Function

(since 0.5.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.SparseEuclideanDistanceFunction

Euclidean distance function, optimized for SparseNumberVectors.

Euclidean distance is defined as:

$\text{Euclidean}(\vec{x},\vec{y}):=\sqrt{\sum\nolimits_{i}(x_{i}-y_{i})^{2}}$

For sparse vectors, we can skip those i where both vectors are 0.

###### Sparse LP Norm Distance Function

(since 0.5.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.SparseLPNormDistanceFunction

Lp-Norm, optimized for SparseNumberVectors.

The Lp distance is defined as:

$L_{p}(\vec{x},\vec{y}):=\left(\sum\nolimits_{i}(x_{i}-y_{i})\right)^{1/p}$

###### Sparse Manhattan Distance Function

(since 0.5.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.SparseManhattanDistanceFunction

Manhattan distance, optimized for SparseNumberVectors.

Manhattan distance is defined as:

$\text{Manhattan}(\vec{x},\vec{y}):=\sum_{i}|x_{i}-y_{i}|$

###### Sparse Maximum Distance Function

(since 0.5.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.SparseMaximumDistanceFunction

Maximum distance, optimized for SparseNumberVectors.

The maximum distance is defined as:

$\text{Maximum}(\vec{x},\vec{y}):=\max_{i}|x_{i}-y_{i}|$

and can be seen as limiting case of the LPNormDistanceFunction for
$p\rightarrow\infty$.

###### Squared Euclidean Distance Function

(since 0.1)

de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.SquaredEuclideanDistanceFunction

Squared Euclidean distance, optimized for SparseNumberVectors. This results in
the same rankings as regular Euclidean distance, but saves computing the
square root.

Squared Euclidean is defined as:

$\text{Euclidean}^{2}(\vec{x},\vec{y}):=\sum_{i}(x_{i}-y_{i})^{2}$

###### Weighted Euclidean Distance Function

(since 0.4.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.WeightedEuclideanDistanceFunction

Weighted Euclidean distance for NumberVectors.

Weighted Euclidean distance is defined as:

$\text{Euclidean}_{\vec{w}}(\vec{x},\vec{y}):=\sqrt{\sum\nolimits_{i}w_{i}(x_{i}-y_{i})^{2}}$

###### Weighted LP Norm Distance Function

(since 0.4.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.WeightedLPNormDistanceFunction

Weighted version of the Minkowski Lp norm distance for NumberVector.

Weighted Lp Norms are defined as:

$L_{p,\vec{w}}(\vec{x},\vec{y}):=\left(\sum\nolimits_{i}w_{i}|x_{i}-y_{i}|^{p}\right)^{1/p}$

###### Weighted Manhattan Distance Function

(since 0.4.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.WeightedManhattanDistanceFunction

Weighted version of the Manhattan (L1) metric.

Weighted Manhattan distance is defined as:

$\text{Manhattan}_{\vec{w}}(\vec{x},\vec{y}):=\sum_{i}w_{i}|x_{i}-y_{i}|$

###### Weighted Maximum Distance Function

(since 0.6.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.WeightedMaximumDistanceFunction

Weighted version of the maximum distance function for NumberVectors.

Weighted maximum distance is defined as:

$\text{Maximum}_{\vec{w}}(\vec{x},\vec{y}):=\max_{i}w_{i}|x_{i}-y_{i}|$

###### Weighted Squared Euclidean Distance Function

(since 0.4.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.WeightedSquaredEuclideanDistanceFunction

Weighted squared Euclidean distance for NumberVectors. This results in the
same rankings as weighted Euclidean distance, but saves computing the square
root.

Weighted squared Euclidean is defined as:

$\text{Euclidean}^{2}_{\vec{w}}(\vec{x},\vec{y}):=\sum_{i}w_{i}(x_{i}-y_{i})^{2}$

#####  Q.8 Probabilistic

de.lmu.ifi.dbs.elki.distance.distancefunction.probabilistic package:

Distance from probability theory, mostly divergences such as K-L-divergence,
J-divergence, F-divergence, $\chi$²-divergence, etc.

###### Chi Distance Function

[ES03, PRTB99] (since 0.7.5)

de.lmu.ifi.dbs.elki.distance.distancefunction.probabilistic.ChiDistanceFunction

$\chi$ distance function, symmetric version. This is the square root of the
ChiSquaredDistanceFunction, and can serve as a fast approximation to
SqrtJensenShannonDivergenceDistanceFunction.

This implementation assumes $\sum_{i}x_{i}=\sum_{i}y_{i}$, and is defined as:

$\chi(\vec{x},\vec{y}):=\sqrt{2\sum\nolimits_{i}\tfrac{(x_{i}-x_{i})^{2}}{x_{i}+y_{i}}}$

###### Chi Squared Distance Function

[PRTB99] (since 0.6.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.probabilistic.ChiSquaredDistanceFunction

$\chi$² distance function, symmetric version.

This implementation assumes $\sum_{i}x_{i}=\sum_{i}y_{i}$, and is defined as:

$\chi^{2}(\vec{x},\vec{y}):=2\sum\nolimits_{i}\tfrac{(x_{i}-x_{i})^{2}}{x_{i}+y_{i}}$

###### Fisher Rao Distance Function

[DD09, Rao45] (since 0.7.5)

de.lmu.ifi.dbs.elki.distance.distancefunction.probabilistic.FisherRaoDistanceFunction

Fisher-Rao riemannian metric for (discrete) probability distributions.

$\text{Fisher-
Rao}(\vec{x},\vec{y}):=2\arccos\sum\nolimits_{i}\sqrt{p_{i}q_{i}}$

###### Hellinger Distance Function

[DD09, Hel09] (since 0.7.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.probabilistic.HellingerDistanceFunction

Hellinger metric / affinity / kernel, Bhattacharyya coefficient, fidelity
similarity, Matusita distance, Hellinger-Kakutani metric on a probability
distribution.

We assume vectors represent normalized probability distributions. Then

$\text{Hellinger}(\vec{x},\vec{y}):=\sqrt{\tfrac{1}{2}\sum\nolimits_{i}\left(\sqrt{x_{i}}-\sqrt{y_{i}}\right)^{2}}$

The corresponding kernel / similarity is

$K_{\text{Hellinger}}(\vec{x},\vec{y}):=\sum\nolimits_{i}\sqrt{x_{i}y_{i}}$

If we have normalized probability distributions, we have the nice property
that $K_{\text{Hellinger}}(\vec{x},\vec{x})=\sum\nolimits_{i}x_{i}=1$. and
therefore $K_{\text{Hellinger}}(\vec{x},\vec{y})\in[0:1]$.

Furthermore, we have the following relationship between this variant of the
distance and this kernel:

$\text{Hellinger}^{2}(\vec{x},\vec{y})=\tfrac{1}{2}\sum\nolimits_{i}\left(\sqrt{x_{i}}-\sqrt{y_{i}}\right)^{2}=\tfrac{1}{2}\sum\nolimits_{i}x_{i}+y_{i}-2\sqrt{x_{i}y_{i}}$
$\text{Hellinger}^{2}(\vec{x},\vec{y})=\tfrac{1}{2}K_{\text{Hellinger}}(\vec{x},\vec{x})+\tfrac{1}{2}K_{\text{Hellinger}}(\vec{y},\vec{y})-K_{\text{Hellinger}}(\vec{x},\vec{y})=1-K_{\text{Hellinger}}(\vec{x},\vec{y})$

which implies $\text{Hellinger}(\vec{x},\vec{y})\in[0;1]$, and is very similar
to the Euclidean distance and the linear kernel.

From this, it follows trivially that Hellinger distance corresponds to the
kernel transformation
$\phi:\vec{x}\mapsto(\tfrac{1}{2}\sqrt{x_{1}},\ldots,\tfrac{1}{2}\sqrt{x_{d}})$.

Deza and Deza unfortunately also give a second definition, as:

$\text{Hellinger-
Deza}(\vec{x},\vec{y}):=\sqrt{2\sum\nolimits_{i}\left(\sqrt{\tfrac{x_{i}}{\bar{x}}}-\sqrt{\tfrac{y_{i}}{\bar{y}}}\right)^{2}}$

which has a built-in normalization, and a different scaling that is no longer
bound to $[0;1]$. The 2 in this definition likely should be a $\frac{1}{2}$.

This distance is well suited for histograms, but it is then more efficient to
once normalize the histograms, apply the square roots, and then use Euclidean
distance (i.e., use the "kernel trick" in reverse, materializing the
transformation $\phi$ given above).

###### Jeffrey Divergence Distance Function

[PRTB99, ES03, Jef46, Top00] (since 0.5.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.probabilistic.JeffreyDivergenceDistanceFunction

Jeffrey Divergence for NumberVectors is a symmetric, smoothened version of the
KullbackLeiblerDivergenceAsymmetricDistanceFunction. Topsøe called this
"capacitory discrimination".

$JD(\vec{x},\vec{y}):=\sum\nolimits_{i}x_{i}\log\tfrac{2x_{i}}{x_{i}+y_{i}}+y_{i}\log\tfrac{2y_{i}}{x_{i}+y_{i}}=KL(\vec{x},\tfrac{1}{2}(\vec{x}+\vec{y}))+KL(\vec{y},\tfrac{1}{2}(\vec{x}+\vec{y}))$

###### Jensen Shannon Divergence Distance Function

[DD09, ES03, Lin91] (since 0.6.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.probabilistic.JensenShannonDivergenceDistanceFunction

Jensen-Shannon Divergence for NumberVectors is a symmetric, smoothened version
of the KullbackLeiblerDivergenceAsymmetricDistanceFunction.

It essentially is the same as JeffreyDivergenceDistanceFunction, only scaled
by half. For completeness, we include both.

$JS(\vec{x},\vec{y}):=\tfrac{1}{2}\sum\nolimits_{i}x_{i}\log\tfrac{2x_{i}}{x_{i}+y_{i}}+y_{i}\log\tfrac{2y_{i}}{x_{i}+y_{i}}=\tfrac{1}{2}KL(\vec{x},\tfrac{1}{2}(\vec{x}+\vec{y}))+\tfrac{1}{2}KL(\vec{y},\tfrac{1}{2}(\vec{x}+\vec{y}))$

There exists a variable definition where the two vectors are weighted with
$\beta$ and $1-\beta$, which for the common choice of $\beta=\tfrac{1}{2}$
yields this version.

###### Kullback Leibler Divergence Asymmetric Distance Function

[Kul59] (since 0.6.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.probabilistic.KullbackLeiblerDivergenceAsymmetricDistanceFunction

Kullback-Leibler divergence, also known as relative entropy, information
deviation, or just KL-distance (albeit asymmetric).

$KL(\vec{x},\vec{y}):=\sum\nolimits_{i}x_{i}\log\tfrac{x_{i}}{y_{i}}$

For a version with the arguments reversed, see
KullbackLeiblerDivergenceReverseAsymmetricDistanceFunction.

For a symmetric version, see JeffreyDivergenceDistanceFunction.

###### Kullback Leibler Divergence Reverse Asymmetric Distance Function

[Kul59] (since 0.6.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.probabilistic.KullbackLeiblerDivergenceReverseAsymmetricDistanceFunction

Kullback-Leibler divergence, also known as relative entropy, information
deviation or just KL-distance (albeit asymmetric).

$KL_{R}(\vec{x},\vec{y}):=\sum\nolimits_{i}y_{i}\log\tfrac{y_{i}}{x_{i}}=KL(\vec{y},\vec{x})$

This version has the arguments reversed, see
KullbackLeiblerDivergenceAsymmetricDistanceFunction for the "forward" version.

For a symmetric version, see JeffreyDivergenceDistanceFunction.

###### Sqrt Jensen Shannon Divergence Distance Function

[ES03] (since 0.6.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.probabilistic.SqrtJensenShannonDivergenceDistanceFunction

The square root of Jensen-Shannon divergence is a metric.

$\sqrt{JS}(\vec{x},\vec{y}):=\sqrt{\tfrac{1}{2}\sum\nolimits_{i}x_{i}\log\tfrac{2x_{i}}{x_{i}+y_{i}}+y_{i}\log\tfrac{2y_{i}}{x_{i}+y_{i}}}=\sqrt{JS(\vec{x},\vec{y})}$

A proof of triangle inequality (for "$D_{PQ}$") can be found in Endres and
Schindelin.

###### Triangular Discrimination Distance Function

[Top00] (since 0.7.5)

de.lmu.ifi.dbs.elki.distance.distancefunction.probabilistic.TriangularDiscriminationDistanceFunction

Triangular Discrimination has relatively tight upper and lower bounds to the
Jensen-Shannon divergence, but is much less expensive.

$\text{Triangular-
Discrimination}(\vec{x},\vec{y}):=\sum\nolimits_{i}\tfrac{|x_{i}-y_{i}|^{2}}{x_{i}+y_{i}}$

This distance function is meant for distribution vectors that sum to 1, and
does not work on negative values.

See also TriangularDistanceFunction for a metric version.

###### Triangular Distance Function

[CCVR16] (since 0.7.5)

de.lmu.ifi.dbs.elki.distance.distancefunction.probabilistic.TriangularDistanceFunction

Triangular Distance has relatively tight upper and lower bounds to the (square
root of the) Jensen-Shannon divergence, but is much less expensive.

$\text{Triangular-
Distance}(\vec{x},\vec{y}):=\sqrt{\sum\nolimits_{i}\tfrac{|x_{i}-y_{i}|^{2}}{x_{i}+y_{i}}}$

This distance function is meant for distribution vectors that sum to 1, and
does not work on negative values.

This differs from TriangularDistanceFunction simply by the square root, which
makes it a proper metric and a good approximation for the much more expensive
SqrtJensenShannonDivergenceDistanceFunction.

#####  Q.9 Set

de.lmu.ifi.dbs.elki.distance.distancefunction.set package:

Distance functions for binary and set type data.

###### Hamming Distance Function

[Ham50] (since 0.7.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.set.HammingDistanceFunction

Computes the Hamming distance of arbitrary vectors - i.e. counting, on how
many places they differ.

###### Jaccard Similarity Distance Function

[Jac02] (since 0.6.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.set.JaccardSimilarityDistanceFunction

A flexible extension of Jaccard similarity to non-binary vectors.

Jaccard coefficient is commonly defined as $\frac{A\cap B}{A\cup B}$.

We can extend this definition to non-binary vectors as follows:
$\tfrac{|\\{i\mid a_{i}=b_{i}\\}|}{|\\{i\mid a_{i}=0\wedge b_{i}=0\\}|}$

For binary vectors, this will obviously be the same quantity. However, this
version is more useful for categorical data.

#####  Q.10 Strings

de.lmu.ifi.dbs.elki.distance.distancefunction.strings package:

Distance functions for strings.

###### Levenshtein Distance Function

[Lev66] (since 0.6.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.strings.LevenshteinDistanceFunction

Classic Levenshtein distance on strings.

###### Normalized Levenshtein Distance Function

[Lev66] (since 0.6.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.strings.NormalizedLevenshteinDistanceFunction

Levenshtein distance on strings, normalized by string length.

Note: this is no longer a metric, the triangle inequality is violated.
Example: d("ab","bc")=1, d("ab", "abc")+d("abc","bc")=0.4+0.4=0.8

#####  Q.11 Subspace

de.lmu.ifi.dbs.elki.distance.distancefunction.subspace package:

Distance functions based on subspaces.

###### Onedimensional Distance Function

(since 0.1)

de.lmu.ifi.dbs.elki.distance.distancefunction.subspace.OnedimensionalDistanceFunction

Distance function that computes the distance between feature vectors as the
absolute difference of their values in a specified dimension only.

###### Subspace Euclidean Distance Function

(since 0.1)

de.lmu.ifi.dbs.elki.distance.distancefunction.subspace.SubspaceEuclideanDistanceFunction

Euclidean distance function between NumberVectors only in specified
dimensions.

###### Subspace LP Norm Distance Function

(since 0.1)

de.lmu.ifi.dbs.elki.distance.distancefunction.subspace.SubspaceLPNormDistanceFunction

Lp-Norm distance function between NumberVectors only in specified dimensions.

###### Subspace Manhattan Distance Function

(since 0.1)

de.lmu.ifi.dbs.elki.distance.distancefunction.subspace.SubspaceManhattanDistanceFunction

Manhattan distance function between NumberVectors only in specified
dimensions.

###### Subspace Maximum Distance Function

(since 0.1)

de.lmu.ifi.dbs.elki.distance.distancefunction.subspace.SubspaceMaximumDistanceFunction

Maximum distance function between NumberVectors only in specified dimensions.

#####  Q.12 Timeseries

de.lmu.ifi.dbs.elki.distance.distancefunction.timeseries package:

Distance functions designed for time series.

Note that some regular distance functions (e.g. Euclidean) are also used on
time series.

###### Dynamic Time Warping Distance Function

[BC94] (since 0.2)

de.lmu.ifi.dbs.elki.distance.distancefunction.timeseries.DTWDistanceFunction

Dynamic Time Warping distance (DTW) for numerical vectors.

###### Derivative dynamic time warping

[KP01] (since 0.7.0)

de.lmu.ifi.dbs.elki.distance.distancefunction.timeseries.DerivativeDTWDistanceFunction

Derivative Dynamic Time Warping distance for numerical vectors.

###### Edit Distance on Real Sequence

[CÖO05] (since 0.2)

de.lmu.ifi.dbs.elki.distance.distancefunction.timeseries.EDRDistanceFunction

Edit Distance on Real Sequence distance for numerical vectors.

###### Edit Distance with Real Penalty

[CN04] (since 0.2)

de.lmu.ifi.dbs.elki.distance.distancefunction.timeseries.ERPDistanceFunction

Edit Distance With Real Penalty distance for numerical vectors.

###### Longest Common Subsequence distance function

[VHGK03] (since 0.2)

de.lmu.ifi.dbs.elki.distance.distancefunction.timeseries.LCSSDistanceFunction

Longest Common Subsequence distance for numerical vectors.

Originally this was based on the Matlab Code by Michalis Vlachos, but we have
since switched to a version that uses less memory.

###  Appendix R Similarityfunction

de.lmu.ifi.dbs.elki.distance.similarityfunction package:

Similarity functions.

###### Fractional Shared Nearest Neighbor Similarity Function

(since 0.2)

de.lmu.ifi.dbs.elki.distance.similarityfunction.FractionalSharedNearestNeighborSimilarityFunction

SharedNearestNeighborSimilarityFunction with a pattern defined to accept
Strings that define a non-negative Integer.

###### Inverted Distance Similarity Function

(since 0.5.0)

de.lmu.ifi.dbs.elki.distance.similarityfunction.InvertedDistanceSimilarityFunction

Adapter to use a primitive number-distance as similarity measure, by computing
1/distance.

###### Kulczynski 1 Similarity Function

[DD09] (since 0.6.0)

de.lmu.ifi.dbs.elki.distance.similarityfunction.Kulczynski1SimilarityFunction

Kulczynski similarity 1.

$s_{\text{Kulczynski-1}}(\vec{x},\vec{y}):=\tfrac{\sum\nolimits_{i}\min\\{x_{i},y_{i}\\}}{\sum\nolimits_{i}|x_{i}-y_{i}|}$

or in distance form:

$d_{\text{Kulczynski-1}}(\vec{x},\vec{y}):=\tfrac{\sum\nolimits_{i}|x_{i}-y_{i}|}{\sum\nolimits_{i}\min\\{x_{i},y_{i}\\}}$

###### Kulczynski 2 Similarity Function

[DD09] (since 0.6.0)

de.lmu.ifi.dbs.elki.distance.similarityfunction.Kulczynski2SimilarityFunction

Kulczynski similarity 2.

$s_{\text{Kulczynski-2}}(\vec{x},\vec{y}:=\tfrac{n}{2}\left(\tfrac{1}{\bar{x}}+\tfrac{1}{\bar{y}}\right)\sum\nolimits_{i}\min\\{x_{i},y_{i}\\}$

###### Shared Nearest Neighbor Similarity Function

(since 0.1)

de.lmu.ifi.dbs.elki.distance.similarityfunction.SharedNearestNeighborSimilarityFunction

SharedNearestNeighborSimilarityFunction with a pattern defined to accept
Strings that define a non-negative Integer.

#####  R.1 Cluster

de.lmu.ifi.dbs.elki.distance.similarityfunction.cluster package:

Similarity measures for comparing clusters.

###### Cluster Intersection Similarity Function

(since 0.7.0)

de.lmu.ifi.dbs.elki.distance.similarityfunction.cluster.ClusterIntersectionSimilarityFunction

Measure the similarity of clusters via the intersection size.

###### Cluster Jaccard Similarity Function

[Jac02] (since 0.7.0)

de.lmu.ifi.dbs.elki.distance.similarityfunction.cluster.ClusterJaccardSimilarityFunction

Measure the similarity of clusters via the Jaccard coefficient.

###### Clustering Adjusted Rand Index Similarity Function

[HA85] (since 0.7.0)

de.lmu.ifi.dbs.elki.distance.similarityfunction.cluster.ClusteringAdjustedRandIndexSimilarityFunction

Measure the similarity of clusters via the Adjusted Rand Index.

###### Clustering B Cubed F1 Similarity Function

[BB98] (since 0.7.0)

de.lmu.ifi.dbs.elki.distance.similarityfunction.cluster.ClusteringBCubedF1SimilarityFunction

Measure the similarity of clusters via the BCubed F1 Index.

###### Clustering Fowlkes Mallows Similarity Function

[FM83] (since 0.7.0)

de.lmu.ifi.dbs.elki.distance.similarityfunction.cluster.ClusteringFowlkesMallowsSimilarityFunction

Measure the similarity of clusters via the Fowlkes-Mallows Index.

###### Clustering Rand Index Similarity Function

[Ran71] (since 0.7.0)

de.lmu.ifi.dbs.elki.distance.similarityfunction.cluster.ClusteringRandIndexSimilarityFunction

Measure the similarity of clusters via the Rand Index.

#####  R.2 Kernel

de.lmu.ifi.dbs.elki.distance.similarityfunction.kernel package:

Kernel functions.

###### Laplace Kernel Function

(since 0.6.0)

de.lmu.ifi.dbs.elki.distance.similarityfunction.kernel.LaplaceKernelFunction

Laplace / exponential radial basis function kernel.

###### Linear Kernel Function

(since 0.1)

de.lmu.ifi.dbs.elki.distance.similarityfunction.kernel.LinearKernelFunction

Linear Kernel function that computes a similarity between the two feature
vectors x and y defined by $x^{T}\cdot y$.

Note: this is effectively equivalent to using EuclideanDistanceFunction

###### Polynomial Kernel Function

(since 0.1)

de.lmu.ifi.dbs.elki.distance.similarityfunction.kernel.PolynomialKernelFunction

Polynomial Kernel function that computes a similarity between the two feature
vectors x and y defined by $(x^{T}\cdot y+b)^{\text{degree}}$.

###### Radial Basis Function Kernel Function

(since 0.6.0)

de.lmu.ifi.dbs.elki.distance.similarityfunction.kernel.RadialBasisFunctionKernelFunction

Gaussian radial basis function kernel (RBF Kernel).

###### Rational Quadratic Kernel Function

(since 0.6.0)

de.lmu.ifi.dbs.elki.distance.similarityfunction.kernel.RationalQuadraticKernelFunction

Rational quadratic kernel, a less computational approximation of the Gaussian
RBF kernel (RadialBasisFunctionKernelFunction).

###### Sigmoid Kernel Function

(since 0.6.0)

de.lmu.ifi.dbs.elki.distance.similarityfunction.kernel.SigmoidKernelFunction

Sigmoid kernel function (aka: hyperbolic tangent kernel, multilayer perceptron
MLP kernel).

###  Chapter Evaluation

de.lmu.ifi.dbs.elki.evaluation package:

Functionality for the evaluation of algorithms.

###  Appendix S Classification

de.lmu.ifi.dbs.elki.evaluation.classification package:

Evaluation of classification algorithms.

#####  S.1 Holdout

de.lmu.ifi.dbs.elki.evaluation.classification.holdout package:

Holdout and cross-validation strategies for evaluating classifiers.

###### Disjoint Cross Validation

(since 0.7.0)

de.lmu.ifi.dbs.elki.evaluation.classification.holdout.DisjointCrossValidation

DisjointCrossValidationHoldout provides a set of partitions of a database to
perform cross-validation. The test sets are guaranteed to be disjoint.

###### Leave One Out

(since 0.7.0)

de.lmu.ifi.dbs.elki.evaluation.classification.holdout.LeaveOneOut

A leave-one-out-holdout is to provide a set of partitions of a database where
each instances once hold out as a test instance while the respectively
remaining instances are training instances.

###### Randomized Cross Validation

(since 0.7.0)

de.lmu.ifi.dbs.elki.evaluation.classification.holdout.RandomizedCrossValidation

RandomizedCrossValidationHoldout provides a set of partitions of a database to
perform cross-validation. The test sets are not guaranteed to be disjoint.

###### Stratified Cross Validation

(since 0.7.0)

de.lmu.ifi.dbs.elki.evaluation.classification.holdout.StratifiedCrossValidation

A stratified n-fold crossvalidation to distribute the data to n buckets where
each bucket exhibits approximately the same distribution of classes as does
the complete data set. The buckets are disjoint. The distribution is
deterministic.

###  Appendix T Clustering

de.lmu.ifi.dbs.elki.evaluation.clustering package:

Evaluation of clustering results.

###### B Cubed

[BB98] (since 0.5.0)

de.lmu.ifi.dbs.elki.evaluation.clustering.BCubed

BCubed measures.

###### Edit Distance

[PL02] (since 0.5.0)

de.lmu.ifi.dbs.elki.evaluation.clustering.EditDistance

Edit distance measures.

P. Pantel, D. Lin
Document clustering with committees
Proc. 25th ACM SIGIR Conf. on Research and Development in Information
Retrieval

###### Entropy

[Mei03, NEB09] (since 0.5.0)

de.lmu.ifi.dbs.elki.evaluation.clustering.Entropy

Entropy based measures.

###### Evaluate Clustering

(since 0.4.0)

de.lmu.ifi.dbs.elki.evaluation.clustering.EvaluateClustering

Evaluate a clustering result by comparing it to an existing cluster label.

###### Log Cluster Sizes

(since 0.7.0)

de.lmu.ifi.dbs.elki.evaluation.clustering.LogClusterSizes

This class will log simple statistics on the clusters detected, such as the
cluster sizes and the number of clusters.

###### Pair Counting

[Jac02, HA85, FM83, Ran71, Mir96] (since 0.5.0)

de.lmu.ifi.dbs.elki.evaluation.clustering.PairCounting

Pair-counting measures.

###### Set Matching Purity

[SKK00, AGAV09, Mei02, ZK01] (since 0.5.0)

de.lmu.ifi.dbs.elki.evaluation.clustering.SetMatchingPurity

Set matching purity measures.

#####  T.1 Extractor

de.lmu.ifi.dbs.elki.evaluation.clustering.extractor package:

Classes to extract clusterings from hierarchical clustering.

###### Cut Dendrogram By Height Extractor

(since 0.7.0)

de.lmu.ifi.dbs.elki.evaluation.clustering.extractor.CutDendrogramByHeightExtractor

Extract clusters from a hierarchical clustering, during the evaluation phase.

Usually, it is more elegant to use ExtractFlatClusteringFromHierarchy as
primary algorithm. But in order to extract multiple partitionings from the
same clustering, this can be useful.

###### Cut Dendrogram By Number Of Clusters Extractor

(since 0.7.0)

de.lmu.ifi.dbs.elki.evaluation.clustering.extractor.CutDendrogramByNumberOfClustersExtractor

Extract clusters from a hierarchical clustering, during the evaluation phase.

Usually, it is more elegant to use ExtractFlatClusteringFromHierarchy as
primary algorithm. But in order to extract multiple partitionings from the
same clustering, this can be useful.

###### HDBSCAN Hierarchy Extraction Evaluator

(since 0.7.0)

de.lmu.ifi.dbs.elki.evaluation.clustering.extractor.HDBSCANHierarchyExtractionEvaluator

Extract clusters from a hierarchical clustering, during the evaluation phase.

Usually, it is more elegant to use HDBSCANHierarchyExtraction as primary
algorithm. But in order to extract multiple partitionings from the same
clustering, this can be useful.

###### Simplified Hierarchy Extraction Evaluator

(since 0.7.0)

de.lmu.ifi.dbs.elki.evaluation.clustering.extractor.SimplifiedHierarchyExtractionEvaluator

Extract clusters from a hierarchical clustering, during the evaluation phase.

Usually, it is more elegant to use SimplifiedHierarchyExtraction as primary
algorithm. But in order to extract multiple partitionings from the same
clustering, this can be useful.

#####  T.2 Internal

de.lmu.ifi.dbs.elki.evaluation.clustering.internal package:

Internal evaluation measures for clusterings.

###### Evaluate C Index

[HL76] (since 0.7.0)

de.lmu.ifi.dbs.elki.evaluation.clustering.internal.EvaluateCIndex

Compute the C-index of a data set.

Note: This requires pairwise distance computations, so it is not recommended
to use this on larger data sets.

###### Evaluate Concordant Pairs

[BH75, Roh74] (since 0.7.0)

de.lmu.ifi.dbs.elki.evaluation.clustering.internal.EvaluateConcordantPairs

Compute the Gamma Criterion of a data set.

###### Evaluate DBCV

[MJC+14] (since 0.7.5)

de.lmu.ifi.dbs.elki.evaluation.clustering.internal.EvaluateDBCV

Compute the Density-Based Clustering Validation Index.

###### Evaluate Davies Bouldin

[DB79] (since 0.7.0)

de.lmu.ifi.dbs.elki.evaluation.clustering.internal.EvaluateDaviesBouldin

Compute the Davies-Bouldin index of a data set.

###### Evaluate PBM Index

[PBM04] (since 0.7.0)

de.lmu.ifi.dbs.elki.evaluation.clustering.internal.EvaluatePBMIndex

Compute the PBM index of a clustering

###### Evaluate Silhouette

[Rou87] (since 0.7.0)

de.lmu.ifi.dbs.elki.evaluation.clustering.internal.EvaluateSilhouette

Compute the silhouette of a data set.

###### Evaluate Simplified Silhouette

(since 0.7.0)

de.lmu.ifi.dbs.elki.evaluation.clustering.internal.EvaluateSimplifiedSilhouette

Compute the simplified silhouette of a data set.

The simplified silhouette does not use pairwise distances, but distances to
centroids only.

###### Evaluate Squared Errors

(since 0.7.0)

de.lmu.ifi.dbs.elki.evaluation.clustering.internal.EvaluateSquaredErrors

Evaluate a clustering by reporting the squared errors (SSE, SSQ), as used by
k-means. This should be used with SquaredEuclideanDistanceFunction only (when
used with other distances, it will manually square the values; but beware that
the result is less meaningful with other distance functions).

For clusterings that provide a cluster prototype object (e.g. k-means), the
prototype will be used. For other algorithms, the centroid will be recomputed.

###### Evaluate Variance Ratio Criteria

[CH74] (since 0.7.0)

de.lmu.ifi.dbs.elki.evaluation.clustering.internal.EvaluateVarianceRatioCriteria

Compute the Variance Ratio Criteria of a data set, also known as Calinski-
Harabasz index.

#####  T.3 Pairsegments

de.lmu.ifi.dbs.elki.evaluation.clustering.pairsegments package:

Pair-segment analysis of multiple clusterings.

###### Cluster Pair Segment Analysis

[AGK+12] (since 0.5.0)

de.lmu.ifi.dbs.elki.evaluation.clustering.pairsegments.ClusterPairSegmentAnalysis

Evaluate clustering results by building segments for their pairs: shared pairs
and differences.

###### Segments

[AGK+12] (since 0.5.0)

de.lmu.ifi.dbs.elki.evaluation.clustering.pairsegments.Segments

Creates segments of two or more clusterings.

Segments are the equally paired database objects of all given (2+)
clusterings. Given a contingency table, an object Segment represents the
table’s cells where an intersection of classes and labels are given. Pair
Segments are created by converting an object Segment into its pair
representation. Converting all object Segments into pair Segments results in a
larger number of pair Segments, if any fragmentation (no perfect match of
clusters) within the contingency table has occurred (multiple cells on one row
or column). Thus for ever object Segment exists a corresponding pair Segment.
Additionally pair Segments represent pairs that are only in one Clustering
which occurs for each split of a clusterings cluster by another clustering.
Here, these pair Segments are referenced as fragmented Segments. Within the
visualization they describe (at least two) pair Segments that have a
corresponding object Segment.

###  Appendix U Outlier

de.lmu.ifi.dbs.elki.evaluation.outlier package:

Evaluate an outlier score using a misclassification based cost model.

###### Compute Outlier Histogram

(since 0.3)

de.lmu.ifi.dbs.elki.evaluation.outlier.ComputeOutlierHistogram

Compute a Histogram to evaluate a ranking algorithm.

The parameter -hist.positive specifies the class label of "positive" hits.

###### Judge Outlier Scores

(since 0.4.0)

de.lmu.ifi.dbs.elki.evaluation.outlier.JudgeOutlierScores

Compute a Histogram to evaluate a ranking algorithm.

The parameter -hist.positive specifies the class label of "positive" hits.

###### Outlier Precision At K Curve

(since 0.5.0)

de.lmu.ifi.dbs.elki.evaluation.outlier.OutlierPrecisionAtKCurve

Compute a curve containing the precision values for an outlier detection
method.

###### Outlier Precision Recall Curve

(since 0.5.0)

de.lmu.ifi.dbs.elki.evaluation.outlier.OutlierPrecisionRecallCurve

Compute a curve containing the precision values for an outlier detection
method.

###### Outlier ROC Curve

(since 0.2)

de.lmu.ifi.dbs.elki.evaluation.outlier.OutlierROCCurve

Compute a ROC curve to evaluate a ranking algorithm and compute the
corresponding ROCAUC value.

The parameter -rocauc.positive specifies the class label of "positive" hits.

The nested algorithm -algorithm will be run, the result will be searched for
an iterable or ordering result, which then is compared with the clustering
obtained via the given class label.

###### Outlier Ranking Evaluation

(since 0.7.0)

de.lmu.ifi.dbs.elki.evaluation.outlier.OutlierRankingEvaluation

Evaluate outlier scores by their ranking

###### Outlier Sm ROC Curve

[KFJM11] (since 0.5.0)

de.lmu.ifi.dbs.elki.evaluation.outlier.OutlierSmROCCurve

Smooth ROC curves are a variation of classic ROC curves that takes the scores
into account.

###### Outlier Threshold Clustering

(since 0.5.0)

de.lmu.ifi.dbs.elki.evaluation.outlier.OutlierThresholdClustering

Pseudo clustering algorithm that builds clusters based on their outlier score.
Useful for transforming a numeric outlier score into a 2-class dataset.

###  Appendix V Scores

de.lmu.ifi.dbs.elki.evaluation.scores package:

Evaluation of rankings and scorings.

###### Average Precision Evaluation

(since 0.7.0)

de.lmu.ifi.dbs.elki.evaluation.scores.AveragePrecisionEvaluation

Evaluate using average precision.

###### DCG Evaluation

[JK02] (since 0.7.5)

de.lmu.ifi.dbs.elki.evaluation.scores.DCGEvaluation

Discounted Cumulative Gain.

This evaluation metric would be able to use relevance information, but the
current implementation is for binary labels only (it is easy to add, but
requires API additions or changes).

###### Maximum F1 Evaluation

(since 0.7.0)

de.lmu.ifi.dbs.elki.evaluation.scores.MaximumF1Evaluation

Evaluate using the maximum F1 score.

###### NDCG Evaluation

[JK02] (since 0.7.5)

de.lmu.ifi.dbs.elki.evaluation.scores.NDCGEvaluation

Normalized Discounted Cumulative Gain.

This evaluation metric would be able to use relevance information, but the
current implementation is for binary labels only (it is easy to add, but
requires API additions or changes).

###### Precision At K Evaluation

(since 0.7.0)

de.lmu.ifi.dbs.elki.evaluation.scores.PrecisionAtKEvaluation

Evaluate using Precision@k, or R-precision (when k=0).

When k=0, then it is set to the number of positive objects, and the returned
value is the R-precision, or the precision-recall break-even-point (BEP).

###### ROC Evaluation

(since 0.7.0)

de.lmu.ifi.dbs.elki.evaluation.scores.ROCEvaluation

Compute ROC (Receiver Operating Characteristics) curves.

A ROC curve compares the true positive rate (y-axis) and false positive rate
(x-axis).

It was first used in radio signal detection, but has since found widespread
use in information retrieval, in particular for evaluating binary
classification problems.

ROC curves are particularly useful to evaluate a ranking of objects with
respect to a binary classification problem: a random sampling will
approximately achieve a ROC value of 0.5, while a perfect separation will
achieve 1.0 (all positives first) or 0.0 (all negatives first). In most use
cases, a score significantly below 0.5 indicates that the algorithm result has
been used the wrong way, and should be used backwards.

###  Appendix W Similaritymatrix

de.lmu.ifi.dbs.elki.evaluation.similaritymatrix package:

Render a distance matrix to visualize a clustering-distance-combination.

###### Compute Similarity Matrix Image

(since 0.4.0)

de.lmu.ifi.dbs.elki.evaluation.similaritymatrix.ComputeSimilarityMatrixImage

Compute a similarity matrix for a distance function.

###  Chapter Index

de.lmu.ifi.dbs.elki.index package:

Index structure implementations

###  Appendix X Distancematrix

de.lmu.ifi.dbs.elki.index.distancematrix package:

Precomputed distance matrix.

###### Precomputed Distance Matrix

(since 0.7.0)

de.lmu.ifi.dbs.elki.index.distancematrix.PrecomputedDistanceMatrix

Distance matrix, for precomputing similarity for a small data set.

This class uses a linear memory layout (not a ragged array), and assumes
symmetry as well as strictness. This way, it only stores the upper triangle
matrix with double precision. It has to store (n-1) * (n-2) distance values in
memory, requiring 8 * (n-1) * (n-2) bytes. Since Java has a size limit of
arrays of 31 bits (signed integer), we can store at most $2^{1}6$ objects
(precisely, 65536 objects) in a single array, which needs about 16 GB of RAM.

###### Precomputed Similarity Matrix

(since 0.7.0)

de.lmu.ifi.dbs.elki.index.distancematrix.PrecomputedSimilarityMatrix

Precomputed similarity matrix, for a small data set.

This class uses a linear memory layout (not a ragged array), and assumes
symmetry as well as strictness. This way, it only stores the upper triangle
matrix with double precision. It has to store (n-1) * (n-2) similarity values
in memory, requiring 8 * (n-1) * (n-2) bytes. Since Java has a size limit of
arrays of 31 bits (signed integer), we can store at most $2^{1}6$ objects
(precisely, 65536 objects) in a single array, which needs about 16 GB of RAM.

###  Appendix Y Idistance

de.lmu.ifi.dbs.elki.index.idistance package:

iDistance is a distance based indexing technique, using a reference points
embedding.

###### In Memory I Distance Index

[YOTJ01, JOT+05] (since 0.7.0)

de.lmu.ifi.dbs.elki.index.idistance.InMemoryIDistanceIndex

In-memory iDistance index, a metric indexing method using a reference point
embedding.

Important note: we are currently using a different query strategy. The
original publication discusses queries based on repeated radius queries. We
use a strategy based on shrinking spheres, iteratively refined starting with
the closes reference point. We also do not use a B+-tree as data structure,
but simple in-memory lists. Therefore, we cannot report page accesses needed.

Feel free to contribute improved query strategies. All the code is essentially
here, you only need to query every reference point list, not just the best.

###  Appendix Z Invertedlist

de.lmu.ifi.dbs.elki.index.invertedlist package:

Indexes using inverted lists.

###### In Memory Inverted Index

(since 0.7.0)

de.lmu.ifi.dbs.elki.index.invertedlist.InMemoryInvertedIndex

Simple index using inverted lists.

###  Appendix AA Lsh

de.lmu.ifi.dbs.elki.index.lsh package:

Locality Sensitive Hashing

###### In Memory LSH Index

(since 0.6.0)

de.lmu.ifi.dbs.elki.index.lsh.InMemoryLSHIndex

Locality Sensitive Hashing.

#####  AA.1 Hashfamilies

de.lmu.ifi.dbs.elki.index.lsh.hashfamilies package:

Hash function families for LSH.

###### Cosine Hash Function Family

[Hen06, Cha02] (since 0.7.0)

de.lmu.ifi.dbs.elki.index.lsh.hashfamilies.CosineHashFunctionFamily

Hash function family to use with Cosine distance, using simplified hash
functions where the projection is only drawn from +-1, instead of Gaussian
distributions.

###### Euclidean Hash Function Family

[DIIM04] (since 0.6.0)

de.lmu.ifi.dbs.elki.index.lsh.hashfamilies.EuclideanHashFunctionFamily

2-stable hash function family for Euclidean distances.

###### Manhattan Hash Function Family

[DIIM04] (since 0.6.0)

de.lmu.ifi.dbs.elki.index.lsh.hashfamilies.ManhattanHashFunctionFamily

2-stable hash function family for Euclidean distances.

#####  AA.2 Hashfunctions

de.lmu.ifi.dbs.elki.index.lsh.hashfunctions package:

Hash functions for LSH

###### Cosine Locality Sensitive Hash Function

[Cha02] (since 0.7.0)

de.lmu.ifi.dbs.elki.index.lsh.hashfunctions.CosineLocalitySensitiveHashFunction

Random projection family to use with sparse vectors.

###### Multiple Projections Locality Sensitive Hash Function

[DIIM04] (since 0.6.0)

de.lmu.ifi.dbs.elki.index.lsh.hashfunctions.MultipleProjectionsLocalitySensitiveHashFunction

LSH hash function for vector space data. Depending on the choice of random
vectors, it can be appropriate for Manhattan and Euclidean distances.

###  Appendix AB Preprocessed

de.lmu.ifi.dbs.elki.index.preprocessed package:

Index structure based on preprocessors

#####  AB.1 Fastoptics

de.lmu.ifi.dbs.elki.index.preprocessed.fastoptics package:

Preprocessed index used by the FastOPTICS algorithm.

###### Random Projected Neighbors And Densities

[SV13] (since 0.7.0)

de.lmu.ifi.dbs.elki.index.preprocessed.fastoptics.RandomProjectedNeighborsAndDensities

Random Projections used for computing neighbors and density estimates.

This index is specialized for the algorithm FastOPTICS

#####  AB.2 Knn

de.lmu.ifi.dbs.elki.index.preprocessed.knn package:

Indexes providing KNN and rKNN data.

###### NN Descent

[DCL11] (since 0.7.5)

de.lmu.ifi.dbs.elki.index.preprocessed.knn.NNDescent

NN-desent (also known as KNNGraph) is an approximate nearest neighbor search
algorithm beginning with a random sample, then iteratively refining this
sample until.

###### Spacefilling KNN Preprocessor

[SZK15] (since 0.7.0)

de.lmu.ifi.dbs.elki.index.preprocessed.knn.SpacefillingKNNPreprocessor

Compute the nearest neighbors approximatively using space filling curves.

This version computes the data projections and stores, then queries this data
on-demand. This usually needs less memory (except for very small neighborhood
sizes k) than SpacefillingMaterializeKNNPreprocessor, but will also be slower.

###### Spacefilling Materialize KNN Preprocessor

[SZK15] (since 0.7.0)

de.lmu.ifi.dbs.elki.index.preprocessed.knn.SpacefillingMaterializeKNNPreprocessor

Compute the nearest neighbors approximatively using space filling curves.

This version does the bulk kNN-join operation, i.e. precomputes the k nearest
neighbors for every object, then discards the curves. This is usually more
memory intensive but faster than SpacefillingKNNPreprocessor.

#####  AB.3 Localpca

de.lmu.ifi.dbs.elki.index.preprocessed.localpca package:

Index using a preprocessed local PCA.

###### Knn Query Based Local PCA Preprocessor

(since 0.4.0)

de.lmu.ifi.dbs.elki.index.preprocessed.localpca.KNNQueryFilteredPCAIndex

Provides the local neighborhood to be considered in the PCA as the k nearest
neighbors of an object.

#####  AB.4 Preference

de.lmu.ifi.dbs.elki.index.preprocessed.preference package:

Indexes storing preference vectors.

###### DiSH Preference Vector Index

(since 0.1)

de.lmu.ifi.dbs.elki.index.preprocessed.preference.DiSHPreferenceVectorIndex

Preprocessor for DiSH preference vector assignment to objects of a certain
database.

###### HiSC Preprocessor

[ABK+06a] (since 0.1)

de.lmu.ifi.dbs.elki.index.preprocessed.preference.HiSCPreferenceVectorIndex

Preprocessor for HiSC preference vector assignment to objects of a certain
database.

#####  AB.5 Snn

de.lmu.ifi.dbs.elki.index.preprocessed.snn package:

Indexes providing nearest neighbor sets

###### Shared Nearest Neighbor Preprocessor

(since 0.1)

de.lmu.ifi.dbs.elki.index.preprocessed.snn.SharedNearestNeighborPreprocessor

A preprocessor for annotation of the ids of nearest neighbors to each database
object.

The k nearest neighbors are assigned based on an arbitrary distance function.

This functionality is similar but not identical to MaterializeKNNPreprocessor:
While it also computes the k nearest neighbors, it does not keep the actual
distances, but organizes the NN set in a TreeSet for fast set operations.

###  Appendix AC Projected

de.lmu.ifi.dbs.elki.index.projected package:

Projected indexes for data.

###### LatLngAsECEF Index

(since 0.6.0)

de.lmu.ifi.dbs.elki.index.projected.LatLngAsECEFIndex

Index a 2d data set (consisting of Lat/Lng pairs) by using a projection to 3D
coordinates (WGS-86 to ECEF).

Earth-Centered, Earth-Fixed (ECEF) is a 3D coordinate system, sometimes also
referred to as XYZ, that uses 3 cartesian axes. The center is at the earths
center of mass, the z axis points to the north pole. X axis is to the prime
meridan at the equator (so latitude 0, longitude 0), and the Y axis is
orthogonal going to the east (latitude 0, longitude 90°E).

The Euclidean distance in this coordinate system is a lower bound for the
great-circle distance, and Euclidean coordinates are supposedly easier to
index.

Note: this index will only support the distance function
LatLngDistanceFunction, as it uses a projection that will map data according
to this great circle distance. If the query hint "exact" is set, it will not
be used.

###### LngLatAsECEF Index

(since 0.6.0)

de.lmu.ifi.dbs.elki.index.projected.LngLatAsECEFIndex

Index a 2d data set (consisting of Lng/Lat pairs) by using a projection to 3D
coordinates (WGS-86 to ECEF).

Earth-Centered, Earth-Fixed (ECEF) is a 3D coordinate system, sometimes also
referred to as XYZ, that uses 3 cartesian axes. The center is at the earths
center of mass, the z axis points to the north pole. X axis is to the prime
meridan at the equator (so latitude 0, longitude 0), and the Y axis is
orthogonal going to the east (latitude 0, longitude 90°E).

The Euclidean distance in this coordinate system is a lower bound for the
great-circle distance, and Euclidean coordinates are supposedly easier to
index.

Note: this index will only support the distance function
LngLatDistanceFunction, as it uses a projection that will map data according
to this great circle distance. If the query hint "exact" is set, it will not
be used.

###### PINN: Projection Indexed Nearest Neighbors

[dVCH10] (since 0.6.0)

de.lmu.ifi.dbs.elki.index.projected.PINN

Projection-Indexed nearest-neighbors (PINN) is an index to retrieve the
nearest neighbors in high dimensional spaces by using a random projection
based index.

###  Appendix AD Tree

de.lmu.ifi.dbs.elki.index.tree package:

Tree-based index structures

#####  AD.1 Metrical

de.lmu.ifi.dbs.elki.index.tree.metrical package:

Tree-based index structures for metrical vector spaces.

######  AD.1.1 Metrical Covertree

de.lmu.ifi.dbs.elki.index.tree.metrical.covertree package:

Cover-tree variations.

###### Cover Tree

[BKL06] (since 0.7.0)

de.lmu.ifi.dbs.elki.index.tree.metrical.covertree.CoverTree

Cover tree data structure (in-memory). This is a metrical data structure that
is similar to the M-tree, but not as balanced and disk-oriented. However, by
not having these requirements it does not require the expensive splitting
procedures of M-tree.

###### Simplified Cover Tree

(since 0.7.0)

de.lmu.ifi.dbs.elki.index.tree.metrical.covertree.SimplifiedCoverTree

Simplified cover tree data structure (in-memory). This is a metrical data
structure that is similar to the M-tree, but not as balanced and disk-
oriented. However, by not having these requirements it does not require the
expensive splitting procedures of M-tree.

This version does not store the distance to the parent, so it needs only about
40% of the memory of CoverTree but does more distance computations for search.

######  AD.1.2 Metrical Mtreevariants

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants package:

M-Tree and variants.

######  AD.1.3 Metrical Mtreevariants Mktrees

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees package:

Metrical index structures based on the concepts of the M-Tree supporting
processing of reverse k nearest neighbor queries by using the k-nn distances
of the entries.

######  AD.1.4 Metrical Mtreevariants Mktrees Mkapp

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkapp package:

MkAppTree

###### MkApp Tree Factory

(since 0.4.0)

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkapp.MkAppTreeFactory

Factory for a MkApp-Tree

######  AD.1.5 Metrical Mtreevariants Mktrees Mkmax

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkmax package:

MkMaxTree

###### MkMax Tree Factory

(since 0.4.0)

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mkmax.MkMaxTreeFactory

Factory for MkMaxTrees

######  AD.1.6 Metrical Mtreevariants Mktrees Mktab

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mktab package:

MkTabTree

###### MkTab Tree Factory

(since 0.4.0)

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mktrees.mktab.MkTabTreeFactory

Factory for MkTabTrees

######  AD.1.7 Metrical Mtreevariants Mtree

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mtree package:

MTree

###### M-Tree

[CPZ97] (since 0.1)

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mtree.MTree

MTree is a metrical index structure based on the concepts of the M-Tree. Apart
from organizing the objects it also provides several methods to search for
certain object in the structure. Persistence is not yet ensured.

###### M Tree Factory

(since 0.4.0)

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.mtree.MTreeFactory

Factory for a M-Tree

######  AD.1.8 Metrical Mtreevariants Strategies

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies package:

######  AD.1.9 Metrical Mtreevariants Strategies Insert

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.insert
package:

Insertion (choose path) strategies of nodes in an M-Tree (and variants).

###### Minimum Enlargement Insert

[CPZ97] (since 0.6.0)

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.insert.MinimumEnlargementInsert

Minimum enlargement insert - default insertion strategy for the M-tree.

######  AD.1.10 Metrical Mtreevariants Strategies Split

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.split
package:

Splitting strategies of nodes in an M-Tree (and variants).

###### Farthest Points Split

(since 0.7.5)

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.split.FarthestPointsSplit

Farthest points split.

###### MLB Dist Split

[CPZ97] (since 0.6.0)

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.split.MLBDistSplit

Encapsulates the required methods for a split of a node in an M-Tree. The
routing objects are chosen according to the MLBDIST strategy.

The benefit of this strategy is that it works with precomputed distances from
the parent, while most other strategies would require O(n²) distance
computations. So if construction time is critical, this is a good choice.

###### MMRad Split

[CPZ97] (since 0.2)

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.split.MMRadSplit

Encapsulates the required methods for a split of a node in an M-Tree. The
routing objects are chosen according to the mMrad strategy.

###### MRad Split

[CPZ97] (since 0.2)

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.split.MRadSplit

Encapsulates the required methods for a split of a node in an M-Tree. The
routing objects are chosen according to the Mrad strategy.

###### MST Split

[JTSF00] (since 0.7.5)

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.split.MSTSplit

Splitting algorithm using the minimum spanning tree (MST), as proposed by the
Slim-Tree variant.

Unfortunately, the slim-tree paper does not detail how to choose the "most
appropriate edge from the longest ones" (to find a more balanced split), so we
try to longest 50%, and keep the choice which yields the most balanced split.
This seems to work quite well.

###### Random Split

[CPZ97] (since 0.2)

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.split.RandomSplit

Encapsulates the required methods for a split of a node in an M-Tree. The
routing objects are chosen according to the RANDOM strategy.

Note: only the routing objects are chosen at random, this is not a random
assignment!

######  AD.1.11 Metrical Mtreevariants Strategies Split Distribution

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.split.distribution
package:

Entry distsribution strategies of nodes in an M-Tree (and variants).

###### Balanced Distribution

[CPZ97] (since 0.7.5)

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.split.distribution.BalancedDistribution

Balanced entry distribution strategy of the M-tree.

###### Farthest Balanced Distribution

(since 0.7.5)

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.split.distribution.FarthestBalancedDistribution

Balanced entry distribution strategy of the M-tree, beginning with the most
difficult points first. This should produce smaller covers.

###### Generalized Hyperplane Distribution

[CPZ97] (since 0.7.5)

de.lmu.ifi.dbs.elki.index.tree.metrical.mtreevariants.strategies.split.distribution.GeneralizedHyperplaneDistribution

Generalized hyperplane entry distribution strategy of the M-tree.

This strategy does not produce balanced trees, but often produces faster
access times, according to the original publication.

#####  AD.2 Spatial

de.lmu.ifi.dbs.elki.index.tree.spatial package:

Tree-based index structures for spatial indexing.

######  AD.2.1 Spatial Kd

de.lmu.ifi.dbs.elki.index.tree.spatial.kd package:

K-d-tree and variants.

###### Minimalistic Memory KD Tree

[Ben75] (since 0.6.0)

de.lmu.ifi.dbs.elki.index.tree.spatial.kd.MinimalisticMemoryKDTree

Simple implementation of a static in-memory K-D-tree. Does not support dynamic
updates or anything, but also is very simple and memory efficient: all it uses
is one ArrayModifiableDBIDs to sort the data in a serialized tree.

###### Small Memory KD Tree

[Ben75] (since 0.7.0)

de.lmu.ifi.dbs.elki.index.tree.spatial.kd.SmallMemoryKDTree

Simple implementation of a static in-memory K-D-tree. Does not support dynamic
updates or anything, but also is very simple and memory efficient: all it uses
is one ModifiableDoubleDBIDList to sort the data in a serialized tree and
store the current attribute value.

It needs about 3 times as much memory as MinimalisticMemoryKDTree but it is
also considerably faster because it does not need to lookup this value from
the vectors.

######  AD.2.2 Spatial Rstarvariants

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants package:

R*-Tree and variants.

######  AD.2.3 Spatial Rstarvariants Query

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query package:

Queries on the R-Tree family of indexes: kNN and range queries.

###### Euclidean R Star Tree KNN Query

[HS95] (since 0.7.0)

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query.EuclideanRStarTreeKNNQuery

Instance of a KNN query for a particular spatial index.

###### Euclidean R Star Tree Range Query

[KL97] (since 0.4.0)

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query.EuclideanRStarTreeRangeQuery

Instance of a range query for a particular spatial index.

###### R Star Tree KNN Query

[HS95] (since 0.4.0)

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query.RStarTreeKNNQuery

Instance of a KNN query for a particular spatial index.

###### R Star Tree Range Query

[KL97] (since 0.4.0)

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query.RStarTreeRangeQuery

Instance of a range query for a particular spatial index.

######  AD.2.4 Spatial Rstarvariants Rstar

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rstar package:

RStarTree

###### R*-Tree

[BKSS90] (since 0.1)

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rstar.RStarTree

RStarTree is a spatial index structure based on the concepts of the R*-Tree.
Apart from organizing the objects it also provides several methods to search
for certain object in the structure and ensures persistence.

###### R Star Tree Factory

(since 0.4.0)

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rstar.RStarTreeFactory

Factory for regular R*-Trees.

######  AD.2.5 Spatial Rstarvariants Strategies

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies package:

######  AD.2.6 Spatial Rstarvariants Strategies Bulk

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk package:

Packages for bulk-loading R*-Trees.

###### Adaptive Sort Tile Recursive Bulk Split

(since 0.6.0)

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk.AdaptiveSortTileRecursiveBulkSplit

This is variation of the original STR bulk load for non-rectangular data
spaces. Instead of iterating through the dimensions and splitting each by
(approximately) the same factor, this variation tries to adjust the factor to
the extends of the data space. I.e. if the data set is twice as wide as high,
this should produce twice as many partitions on the X than on the Y axis.

Whether or not this offers benefits greatly depends on the distance queries
used. But for symmetric distances, the resulting pages should be more
rectangular, which often is beneficial.

See SortTileRecursiveBulkSplit for the original STR bulk load.

###### File Order Bulk Split

(since 0.5.0)

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk.FileOrderBulkSplit

Trivial bulk loading - assumes that the file has been appropriately sorted
before.

###### Max Extension Bulk Split

(since 0.4.0)

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk.MaxExtensionBulkSplit

Split strategy for bulk-loading a spatial tree where the split axes are the
dimensions with maximum extension.

###### Max Extension Sort Tile Recursive Bulk Split

(since 0.6.0)

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk.MaxExtensionSortTileRecursiveBulkSplit

This is variation of the SortTileRecursiveBulkSplit, incorporating some ideas
from MaxExtensionBulkSplit. Instead of iterating through the axes in order, it
always chooses the axis with the largest extend. This may rarely lead to the
data being split on the same axis twice, but most importantly it varies the
splitting order compared to STR.

AdaptiveSortTileRecursiveBulkSplit takes these ideas one step further, by also
varying the fan-out degree.

###### OneDim Sort Bulk Split

[RL85] (since 0.5.0)

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk.OneDimSortBulkSplit

Simple bulk loading strategy by sorting the data along the first dimension.

This is also known as Nearest-X, and attributed to:

N. Roussopoulos, D. Leifker
Direct spatial search on pictorial databases using packed R-trees
ACM SIGMOD Record 14-4

###### Sort Tile Recursive Bulk Split

[LEL97] (since 0.5.0)

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk.SortTileRecursiveBulkSplit

Sort-Tile-Recursive aims at tiling the data space with a grid-like structure
for partitioning the dataset into the required number of buckets.

###### Spatial Sort Bulk Split

[KF93] (since 0.5.0)

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.bulk.SpatialSortBulkSplit

Bulk loading by spatially sorting the objects, then partitioning the sorted
list appropriately.

Based conceptually on:

On packing R-trees
I. Kamel, C. Faloutsos
Proc. 2nd Int. Conf. on Information and Knowledge Management (CIKM)

######  AD.2.7 Spatial Rstarvariants Strategies Insert

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.insert
package:

Insertion strategies for R-Trees

###### Approximative Least Overlap Insertion Strategy

[BKSS90] (since 0.5.0)

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.insert.ApproximativeLeastOverlapInsertionStrategy

The choose subtree method proposed by the R*-Tree with slightly better
performance for large leaf sizes (linear approximation).

Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger
The R*-tree: an efficient and robust access method for points and rectangles
Proc. 1990 ACM SIGMOD Int. Conf. Management of Data

###### Combined Insertion Strategy

[BKSS90] (since 0.5.0)

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.insert.CombinedInsertionStrategy

Use two different insertion strategies for directory and leaf nodes.

Using two different strategies was likely first suggested in:

Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger
The R*-tree: an efficient and robust access method for points and rectangles
Proc. 1990 ACM SIGMOD Int. Conf. Management of Data

###### Least Enlargement Insertion Strategy

[Gut84] (since 0.5.0)

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.insert.LeastEnlargementInsertionStrategy

The default R-Tree insertion strategy: find rectangle with least volume
enlargement.

###### Least Enlargement With Area Insertion Strategy

[BKSS90] (since 0.5.0)

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.insert.LeastEnlargementWithAreaInsertionStrategy

A slight modification of the default R-Tree insertion strategy: find rectangle
with least volume enlargement, but choose least area on ties.

Proposed for non-leaf entries in:

Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger
The R*-tree: an efficient and robust access method for points and rectangles
Proc. 1990 ACM SIGMOD Int. Conf. Management of Data

###### Least Overlap Insertion Strategy

[BKSS90] (since 0.5.0)

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.insert.LeastOverlapInsertionStrategy

The choose subtree method proposed by the R*-Tree for leaf nodes.

######  AD.2.8 Spatial Rstarvariants Strategies Overflow

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.overflow
package:

Overflow treatment strategies for R-Trees

###### Limited Reinsert Overflow Treatment

[BKSS90] (since 0.5.0)

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.overflow.LimitedReinsertOverflowTreatment

Limited reinsertions, as proposed by the R*-Tree: For each real insert, allow
reinsertions to happen only once per level.

###### Split Only Overflow Treatment

(since 0.5.0)

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.overflow.SplitOnlyOverflowTreatment

Always split, as in the original R-Tree

######  AD.2.9 Spatial Rstarvariants Strategies Reinsert

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.reinsert
package:

Reinsertion strategies for R-Trees

###### Close Reinsert

[BKSS90] (since 0.5.0)

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.reinsert.CloseReinsert

Reinsert objects on page overflow, starting with close objects first (even
when they will likely be inserted into the same page again!)

The strategy preferred by the R*-Tree

###### Far Reinsert

[BKSS90] (since 0.5.0)

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.reinsert.FarReinsert

Reinsert objects on page overflow, starting with farther objects first (even
when they will likely be inserted into the same page again!)

Alternative strategy mentioned in the R*-tree

######  AD.2.10 Spatial Rstarvariants Strategies Split

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.split package:

Splitting strategies for R-Trees

###### AngTan Linear Split

[AT97] (since 0.5.0)

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.split.AngTanLinearSplit

Line-time complexity split proposed by Ang and Tan.

This split strategy tries to minimize overlap only, which can however
degenerate to "slices".

###### Greene Split

[Gre89] (since 0.5.0)

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.split.GreeneSplit

Quadratic-time complexity split as used by Diane Greene for the R-Tree.

Seed selection is quadratic, distribution is O(n log n).

This contains a slight modification to improve performance with point data:
with points as seeds, the normalized separation is always 1, so we choose the
raw separation then.

D. Greene
An implementation and performance analysis of spatial data access methods
Proceedings of the Fifth International Conference on Data Engineering

###### R Tree Linear Split

[Gut84] (since 0.5.0)

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.split.RTreeLinearSplit

Linear-time complexity greedy split as used by the original R-Tree.

###### R Tree Quadratic Split

[Gut84] (since 0.5.0)

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.split.RTreeQuadraticSplit

Quadratic-time complexity greedy split as used by the original R-Tree.

###### Topological Splitter

[BKSS90] (since 0.4.0)

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.strategies.split.TopologicalSplitter

Encapsulates the required parameters for a topological split of a R*-Tree.

###  Appendix AE Vafile

de.lmu.ifi.dbs.elki.index.vafile package:

Vector Approximation File

###### DA File

[KKSZ06] (since 0.5.0)

de.lmu.ifi.dbs.elki.index.vafile.DAFile

Dimension approximation file, a one-dimensional part of the PartialVAFile.

###### Partial VA File

[KKSZ06] (since 0.5.0)

de.lmu.ifi.dbs.elki.index.vafile.PartialVAFile

PartialVAFile. In-memory only implementation.

###### An approximation based data structure for similarity search

[WB97] (since 0.5.0)

de.lmu.ifi.dbs.elki.index.vafile.VAFile

Vector-approximation file (VAFile)

###  Chapter Math

de.lmu.ifi.dbs.elki.math package:

Mathematical operations and utilities used throughout the framework.

###### Mean

[Nee66] (since 0.2)

de.lmu.ifi.dbs.elki.math.Mean

Compute the mean using a numerically stable online algorithm.

This class can repeatedly be fed with data using the put() methods, the
resulting values for mean can be queried at any time using getMean().

The high-precision function is based on:

P. M. Neely
Comparison of Several Algorithms for Computation of Means, Standard Deviations
and Correlation Coefficients
Communications of the ACM 9(7), 1966

###### Mean Variance

[Wel62, SG18b, YC71, Wes79] (since 0.2)

de.lmu.ifi.dbs.elki.math.MeanVariance

Do some simple statistics (mean, variance) using a numerically stable online
algorithm.

This class can repeatedly be fed with data using the add() methods, the
resulting values for mean and average can be queried at any time using
Mean.getMean() and getSampleVariance().

Make sure you have understood variance correctly when using getNaiveVariance()
\- since this class is fed with samples and estimates the mean from the
samples, getSampleVariance() is often the more appropriate version.

As experimentally studied in

Erich Schubert, Michael Gertz
Numerically Stable Parallel Computation of (Co-)Variance
Proc. 30th Int. Conf. Scientific and Statistical Database Management (SSDBM
2018)

the current approach is based on:

E. A. Youngs and E. M. Cramer
Some Results Relevant to Choice of Sum and Sum-of-Product Algorithms
Technometrics 13(3), 1971

We have originally experimented with:

B. P. Welford
Note on a method for calculating corrected sums of squares and products
Technometrics 4(3), 1962

D. H. D. West
Updating Mean and Variance Estimates: An Improved Method
Communications of the ACM 22(9)

###### Statistical Moments

[SG18b, YC71, Ter07, Pé08] (since 0.6.0)

de.lmu.ifi.dbs.elki.math.StatisticalMoments

Track various statistical moments, including mean, variance, skewness and
kurtosis.

###  Appendix AF Geodesy

de.lmu.ifi.dbs.elki.math.geodesy package:

Functions for computing on the sphere / earth.

###### Clarke 1858 Spheroid Earth Model

(since 0.6.0)

de.lmu.ifi.dbs.elki.math.geodesy.Clarke1858SpheroidEarthModel

The Clarke 1858 spheroid earth model.

Radius: 6378293.645 m

Flattening: 1 / 294.26068

###### Clarke 1880 Spheroid Earth Model

(since 0.6.0)

de.lmu.ifi.dbs.elki.math.geodesy.Clarke1880SpheroidEarthModel

The Clarke 1880 spheroid earth model.

Radius: 6378249.145 m

Flattening: 1 / 293.465

###### GRS67 Spheroid Earth Model

(since 0.6.0)

de.lmu.ifi.dbs.elki.math.geodesy.GRS67SpheroidEarthModel

The GRS 67 spheroid earth model.

Radius: 6378160.0 m

Flattening: 1 / 298.25

###### GRS80 Spheroid Earth Model

(since 0.6.0)

de.lmu.ifi.dbs.elki.math.geodesy.GRS80SpheroidEarthModel

The GRS 80 spheroid earth model, without height model (so not a geoid, just a
spheroid!)

Radius: 6378137.0 m

Flattening: 1 / 298.257222101

###### Sphere Util

[SZK13, Wil11, Vin75, Sin84] (since 0.5.5)

de.lmu.ifi.dbs.elki.math.geodesy.SphereUtil

Class with utility functions for distance computations on the sphere.

Note: the formulas are usually implemented for the unit sphere.

The majority of formulas are adapted from:

E. Williams
Aviation Formulary
Online: http://www.edwilliams.org/avform.htm

###### Spherical Cosine Earth Model

(since 0.6.0)

de.lmu.ifi.dbs.elki.math.geodesy.SphericalCosineEarthModel

A simple spherical earth model using radius 6371009 m.

For distance computations, this variant uses the Cosine formula, which is
faster but less accurate than the Haversince or Vincenty’s formula.

###### Spherical Haversine Earth Model

(since 0.6.0)

de.lmu.ifi.dbs.elki.math.geodesy.SphericalHaversineEarthModel

A simple spherical earth model using radius 6371009 m.

For distance computations, this variant uses the Haversine formula, which is
faster but less accurate than Vincenty’s formula.

###### Spherical Vincenty Earth Model

(since 0.6.0)

de.lmu.ifi.dbs.elki.math.geodesy.SphericalVincentyEarthModel

A simple spherical earth model using radius 6371009 m.

###### WGS72 Spheroid Earth Model

(since 0.6.0)

de.lmu.ifi.dbs.elki.math.geodesy.WGS72SpheroidEarthModel

The WGS72 spheroid earth model, without height model.

Radius: 6378135.0 m

Flattening: 1 / 298.26

###### WGS84 Spheroid Earth Model

(since 0.6.0)

de.lmu.ifi.dbs.elki.math.geodesy.WGS84SpheroidEarthModel

The WGS84 spheroid earth model, without height model (so not a geoid, just a
spheroid!)

Note that EGM96 uses the same spheroid, but what really makes the difference
is its geoid expansion.

Radius: 6378137.0 m

Flattening: 1 / 298.257223563

###  Appendix AG Geometry

de.lmu.ifi.dbs.elki.math.geometry package:

Algorithms from computational geometry.

###### Graham Scan Convex Hull 2D

[Gra72] (since 0.4.0)

de.lmu.ifi.dbs.elki.math.geometry.GrahamScanConvexHull2D

Classes to compute the convex hull of a set of points in 2D, using the classic
Grahams scan. Also computes a bounding box.

###### Prims Minimum Spanning Tree

[Pri57] (since 0.5.5)

de.lmu.ifi.dbs.elki.math.geometry.PrimsMinimumSpanningTree

Prim’s algorithm for finding the minimum spanning tree.

Implementation for dense graphs, represented as distance matrix.

###### Sweep Hull Delaunay 2D

[Sin16] (since 0.5.0)

de.lmu.ifi.dbs.elki.math.geometry.SweepHullDelaunay2D

Compute the Convex Hull and/or Delaunay Triangulation, using the sweep-hull
approach of David Sinclair.

Note: This implementation does not check or handle duplicate points!

###  Appendix AH Linearalgebra

de.lmu.ifi.dbs.elki.math.linearalgebra package:

The linear algebra package provides classes and computational methods for
operations on matrices and vectors.

Some content of this package is adapted from the Jama package.

Five fundamental matrix decompositions, which consist of pairs or triples of
matrices, permutation vectors, and the like, produce results in five
decomposition classes. These decompositions are accessed by the Matrix class
to compute solutions of simultaneous linear equations, determinants, inverses
and other matrix functions. The five decompositions are:

  * •

Cholesky Decomposition of symmetric, positive definite matrices.

  * •

LU Decomposition of rectangular matrices.

  * •

QR Decomposition of rectangular matrices.

  * •

Singular Value Decomposition of rectangular matrices.

  * •

Eigenvalue Decomposition of both symmetric and nonsymmetric square matrices.

Example of use: Solve a linear system $Ax=b$ and compute the residual norm,
$||b-Ax||$.

double[][] matrix = 1.,2.,3, 4.,5.,6., 7.,8.,10. ;
double[] b = MathUtil.randomDoubleArray(3, new Random());
double[] x = VMath.solve(matrix, b);
double[] r = VMath.minusEquals(VMath.times(matrix, x), b);
double norm = VMath.euclideanLength(r);

The original Jama-package has been developed by the MathWorks and NIST and can
be found at math.nist.gov.

Here, for the adaption some classes and methods convenient for data mining
applications within ELKI were added. Furthermore some erroneous comments were
corrected and the coding-style was subtly changed to a more Java-typical
style.

###### Vector and Matrix Math Library

[Mah36] (since 0.5.0)

de.lmu.ifi.dbs.elki.math.linearalgebra.VMath

Class providing basic vector mathematics, for low-level vectors stored as
double[]. While this is less nice syntactically, it reduces memory usage and
VM overhead.

#####  AH.1 Pca

de.lmu.ifi.dbs.elki.math.linearalgebra.pca package:

Principal Component Analysis (PCA) and Eigenvector processing.

###### Autotuning PCA

[KKSZ08] (since 0.5.0)

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.AutotuningPCA

Performs a self-tuning local PCA based on the covariance matrices of given
objects. At most the closest ’k’ points are used in the calculation and a
weight function is applied.

The number of points used depends on when the strong eigenvectors exhibit the
clearest correlation.

###### PCA Runner

(since 0.2)

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.PCARunner

Class to run PCA on given data.

The various methods will start PCA at different places (e.g. with database
IDs, database query results, a precomputed covariance matrix or eigenvalue
decomposition).

The runner can be parameterized by setting a covariance matrix builder (e.g.
to a weighted covariance matrix builder)

###### RANSAC Covariance Matrix Builder

[KKSZ12, FB81] (since 0.5.5)

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.RANSACCovarianceMatrixBuilder

RANSAC based approach to a more robust covariance matrix computation.

This is an experimental adoption of RANSAC to this problem, not a generic
RANSAC implementation!

While using RANSAC for PCA at first sounds like a good idea, it does not work
very well in high-dimensional spaces. The problem is that PCA has O(n²)
degrees of freedom, so we need to sample very many objects, then perform an
O(n³) matrix operation to compute PCA, for each attempt.

###### Standard Covariance Matrix Builder

(since 0.2)

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.StandardCovarianceMatrixBuilder

Class for building a "traditional" covariance matrix vai CovarianceMatrix.
Reasonable default choice for a CovarianceMatrixBuilder

###### Weighted Covariance Matrix / PCA

[KKSZ08] (since 0.2)

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.WeightedCovarianceMatrixBuilder

CovarianceMatrixBuilder with weights.

This builder uses a weight function to weight points differently during build
a covariance matrix. Covariance can be canonically extended with weights, as
shown in the article

######  AH.1.1 Pca Filter

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.filter package:

Filter eigenvectors based on their eigenvalues.

###### Drop EigenPair Filter

(since 0.5.0)

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.filter.DropEigenPairFilter

The "drop" filter looks for the largest drop in normalized relative
eigenvalues.

Let $s_{1}\ldots s_{n}$ be the eigenvalues.

Let $a_{k}:=1/(n-k)\sum_{i=k..n}s_{i}$

Then $r_{k}:=s_{k}/a_{k}$ is the relative eigenvalue.

The drop filter searches for $\operatorname{arg\,max}_{k}r_{k}/r_{k+1}$

###### First n Eigenpair filter

(since 0.1)

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.filter.FirstNEigenPairFilter

The FirstNEigenPairFilter marks the n highest eigenpairs as strong eigenpairs,
where n is a user specified number.

###### Limit-based Eigenpair Filter

(since 0.1)

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.filter.LimitEigenPairFilter

The LimitEigenPairFilter marks all eigenpairs having an (absolute) eigenvalue
below the specified threshold (relative or absolute) as weak eigenpairs, the
others are marked as strong eigenpairs.

###### Percentage based Eigenpair filter

(since 0.1)

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.filter.PercentageEigenPairFilter

The PercentageEigenPairFilter sorts the eigenpairs in descending order of
their eigenvalues and marks the first eigenpairs, whose sum of eigenvalues is
higher than the given percentage of the sum of all eigenvalues as strong
eigenpairs.

###### Progressive Eigenpair Filter

(since 0.2)

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.filter.ProgressiveEigenPairFilter

The ProgressiveEigenPairFilter sorts the eigenpairs in descending order of
their eigenvalues and marks the first eigenpairs, whose sum of eigenvalues is
higher than the given percentage of the sum of all eigenvalues as strong
eigenpairs. In contrast to the PercentageEigenPairFilter, it will use a
percentage which changes linearly with the subspace dimensionality. This makes
the parameter more consistent for different dimensionalities and often gives
better results when clusters of different dimensionality exist, since
different percentage alpha levels might be appropriate for different
dimensionalities.

Example calculations of alpha levels:

In a 3D space, a progressive alpha value of 0.5 equals:

\- 1D subspace: 50 % + 1/3 of remainder = 0.667

\- 2D subspace: 50 % + 2/3 of remainder = 0.833

In a 4D space, a progressive alpha value of 0.5 equals:

\- 1D subspace: 50% + 1/4 of remainder = 0.625

\- 2D subspace: 50% + 2/4 of remainder = 0.750

\- 3D subspace: 50% + 3/4 of remainder = 0.875

Reasoning why this improves over PercentageEigenPairFilter:

In a 100 dimensional space, a single Eigenvector representing over 85% of the
total variance is highly significant, whereas the strongest 85 Eigenvectors
together will by definition always represent at least 85% of the variance.
PercentageEigenPairFilter can thus not be used with these parameters and
detect both dimensionalities correctly.

The second parameter introduced here, walpha, serves a different function: It
prevents the eigenpair filter to use a statistically weak Eigenvalue just to
reach the intended level, e.g. 84% + 1% >= 85% when 1% is statistically very
weak.

###### Relative EigenPair Filter

(since 0.2)

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.filter.RelativeEigenPairFilter

The RelativeEigenPairFilter sorts the eigenpairs in descending order of their
eigenvalues and marks the first eigenpairs who are a certain factor above the
average of the remaining eigenvalues.

It is closely related to the WeakEigenPairFilter, and differs mostly by
comparing to the remaining Eigenvalues, not to the total sum.

There are some situations where one or the other is superior, especially when
it comes to handling nested clusters and strong global correlations that are
not too interesting. These benefits usually only make a difference at higher
dimensionalities.

###### Significant EigenPair Filter

(since 0.2)

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.filter.SignificantEigenPairFilter

The SignificantEigenPairFilter sorts the eigenpairs in descending order of
their eigenvalues and chooses the contrast of an Eigenvalue to the remaining
Eigenvalues is maximal.

It is closely related to the WeakEigenPairFilter and RelativeEigenPairFilter.
But while the RelativeEigenPairFilter chooses the highest dimensionality that
satisfies the relative alpha levels, the SignificantEigenPairFilter will chose
the local dimensionality such that the ’contrast’ is maximal.

There are some situations where one or the other is superior, especially when
it comes to handling nested clusters and strong global correlations that are
not too interesting. These benefits usually only make a difference at higher
dimensionalities.

###### Weak Eigenpair Filter

(since 0.2)

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.filter.WeakEigenPairFilter

The WeakEigenPairFilter sorts the eigenpairs in descending order of their
eigenvalues and returns the first eigenpairs who are above the average mark as
"strong", the others as "weak".

######  AH.1.2 Pca Weightfunctions

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.weightfunctions package:

Weight functions used in weighted PCA via WeightedCovarianceMatrixBuilder

###### Constant Weight

(since 0.2)

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.weightfunctions.ConstantWeight

Constant Weight function

The result is always 1.0

###### Erfc Stddev Weight

(since 0.2)

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.weightfunctions.ErfcStddevWeight

Gaussian Error Function Weight function, scaled using stddev. This probably is
the most statistically sound weight.

erfc(1 / sqrt(2) * distance / stddev)

###### Erfc Weight

(since 0.2)

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.weightfunctions.ErfcWeight

Gaussian Error Function Weight function, scaled such that the result it 0.1 at
distance == max

erfc(1.1630871536766736 * distance / max)

The value of 1.1630871536766736 is erfcinv(0.1), to achieve the intended
scaling.

###### Exponential Stddev Weight

(since 0.2)

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.weightfunctions.ExponentialStddevWeight

Exponential Weight function, scaled such that the result it 0.1 at distance ==
max

stddev * exp(-.5 * distance/stddev)

This is similar to the Gaussian weight function, except distance/stddev is not
squared.

###### Exponential Weight

(since 0.2)

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.weightfunctions.ExponentialWeight

Exponential Weight function, scaled such that the result it 0.1 at distance ==
max

exp(-2.3025850929940455 * distance/max)

This is similar to the Gaussian weight function, except distance/max is not
squared.

-2.3025850929940455 is log(-.1) to achieve the intended range of 1.0 - 0.1

###### Gauss Stddev Weight

(since 0.2)

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.weightfunctions.GaussStddevWeight

Gaussian weight function, scaled using standard deviation
$1/\sqrt{(}2\pi)\exp(-\frac{\text{dist}^{2}}{2\sigma^{2}})$

###### Gauss Weight

(since 0.2)

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.weightfunctions.GaussWeight

Gaussian weight function, scaled such that the result it 0.1 at distance ==
max, using $\exp(-2.3025850929940455\frac{\text{dist}^{2}}{\max^{2}})$.

###### Inverse Linear Weight

(since 0.2)

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.weightfunctions.InverseLinearWeight

Inverse Linear Weight Function.

This weight is not particularly reasonable. Instead it serves the purpose of
testing the effects of a badly chosen weight function.

This function has increasing weight, from 0.1 to 1.0 at distance == max.

###### Inverse Proportional Stddev Weight

(since 0.2)

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.weightfunctions.InverseProportionalStddevWeight

Inverse proportional weight function, scaled using the standard deviation.

1 / (1 + distance/stddev)

###### Inverse Proportional Weight

(since 0.2)

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.weightfunctions.InverseProportionalWeight

Inverse proportional weight function, scaled using the maximum.

1 / (1 + distance/max)

###### Linear Weight

(since 0.2)

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.weightfunctions.LinearWeight

Linear weight function, scaled using the maximum such that it goes from 1.0 to
0.1

1 - 0.9 * (distance/max)

###### Quadratic Stddev Weight

(since 0.2)

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.weightfunctions.QuadraticStddevWeight

Quadratic weight function, scaled using the standard deviation.

We needed another scaling here, we chose the cutoff point to be 3*stddev. If
you need another value, you have to reimplement this class.

$\max\\{0.0,1.0-\frac{\text{dist}^{2}}{3\sigma^{2}}\\}$

###### Quadratic Weight

(since 0.2)

de.lmu.ifi.dbs.elki.math.linearalgebra.pca.weightfunctions.QuadraticWeight

Quadratic weight function, scaled using the maximum to reach 0.1 at that
point.

1.0 - 0.9 * (distance/max)²

###  Appendix AI Spacefillingcurves

de.lmu.ifi.dbs.elki.math.spacefillingcurves package:

Space filling curves.

###### Binary Split Spatial Sorter

[Ben75] (since 0.5.0)

de.lmu.ifi.dbs.elki.math.spacefillingcurves.BinarySplitSpatialSorter

Spatially sort the data set by repetitive binary splitting, circulating
through the dimensions. This is essentially the bulk-loading proposed for the
k-d-tree, as it will produce a perfectly balanced k-d-tree. The resulting
order is the sequence in which objects would then be stored in the k-d-tree.

Note that when using this for bulk-loading an R-tree, the result will not be a
k-d-tree, not even remotely similar, as the splits are not preserved.

###### Hilbert Spatial Sorter

[Hil91] (since 0.5.0)

de.lmu.ifi.dbs.elki.math.spacefillingcurves.HilbertSpatialSorter

Sort object along the Hilbert Space Filling curve by mapping them to their
Hilbert numbers and sorting them.

Objects are mapped using 31 bits per dimension.

###### Peano Spatial Sorter

[Pea90] (since 0.5.0)

de.lmu.ifi.dbs.elki.math.spacefillingcurves.PeanoSpatialSorter

Bulk-load an R-tree index by presorting the objects with their position on the
Peano curve.

The basic shape of this space-filling curve looks like this:

3---4 9 | | | 2 5 8 | | | 1 6---7Which then expands to the next level as:

+-+ +-+ +-+ +-+ E | | | | | | | | | | +-+ +-+ | | +-+ | | | | +-+ +-+ | | +-+ | | | | | | | | | +-+ | | +-+ +-+ | | | | +-+ | | +-+ +-+ | | | | | | | | | | S +-+ +-+ +-+ +-+

and so on.

###### Z Curve Spatial Sorter

(since 0.5.0)

de.lmu.ifi.dbs.elki.math.spacefillingcurves.ZCurveSpatialSorter

Class to sort the data set by their Z-index, without doing a full
materialization of the Z indexes.

###  Appendix AJ Statistics

de.lmu.ifi.dbs.elki.math.statistics package:

Statistical tests and methods.

###### Probability Weighted Moments

[HWW85, Hos00] (since 0.6.0)

de.lmu.ifi.dbs.elki.math.statistics.ProbabilityWeightedMoments

Estimate the L-Moments of a sample.

#####  AJ.1 Dependence

de.lmu.ifi.dbs.elki.math.statistics.dependence package:

Statistical measures of dependence, such as correlation.

###### Correlation Dependence Measure

(since 0.7.0)

de.lmu.ifi.dbs.elki.math.statistics.dependence.CorrelationDependenceMeasure

Pearson product-moment correlation coefficient.

###### Distance Correlation Dependence Measure

[SRB07] (since 0.7.0)

de.lmu.ifi.dbs.elki.math.statistics.dependence.DistanceCorrelationDependenceMeasure

Distance correlation.

The value returned is the square root of the dCor² value. This matches the R
implementation by the original authors.

###### HSM Dependence Measure

[TAE+11] (since 0.5.5)

de.lmu.ifi.dbs.elki.math.statistics.dependence.HSMDependenceMeasure

Compute the "interestingness" of dimension connections using the hough
transformation. This is a very visual approach, designed to find certain
patterns in parallel coordinates visualizations. The patterns detected here
occur mostly if you have mutliple clusters of linear patterns as far as we
understood the approach (which is not easy to use, unfortunately).

###### HiCS Dependence Measure

[KMB12, AKSZ13] (since 0.5.5)

de.lmu.ifi.dbs.elki.math.statistics.dependence.HiCSDependenceMeasure

Use the statistical tests as used by HiCS to measure dependence of variables.

###### Hoeffdings D Dependence Measure

[Hoe48] (since 0.7.0)

de.lmu.ifi.dbs.elki.math.statistics.dependence.HoeffdingsDDependenceMeasure

Calculate Hoeffding’s D as a measure of dependence.

###### Jensen Shannon Equiwidth Dependence Measure

(since 0.7.0)

de.lmu.ifi.dbs.elki.math.statistics.dependence.JensenShannonEquiwidthDependenceMeasure

Jensen-Shannon Divergence is closely related to mutual information.

The output value is normalized, such that an evenly distributed and identical
distribution will yield a value of 1. Independent distributions may still
yield values close to .25, though.

###### MCE Dependence Measure

[Guo03] (since 0.7.0)

de.lmu.ifi.dbs.elki.math.statistics.dependence.MCEDependenceMeasure

Compute a mutual information based dependence measure using a nested means
discretization, originally proposed for ordering axes in parallel coordinate
plots.

###### Mutual Information Equiwidth Dependence Measure

(since 0.7.0)

de.lmu.ifi.dbs.elki.math.statistics.dependence.MutualInformationEquiwidthDependenceMeasure

Mutual Information (MI) dependence measure by dividing each attribute into
equal-width bins. MI can be seen as Kullback–Leibler divergence of the joint
distribution and the product of the marginal distributions.

For normalization, the resulting values are scaled by mi/log(nbins). This both
cancels out the logarithm base, and normalizes for the number of bins (a
uniform distribution will yield a MI with itself of 1).

###### SURFING Dependence Measure

[AKSZ13, BPK+04] (since 0.5.5)

de.lmu.ifi.dbs.elki.math.statistics.dependence.SURFINGDependenceMeasure

Compute the similarity of dimensions using the SURFING score. The parameter k
for the k nearest neighbors is currently hard-coded to 10% of the set size.

Note that the complexity is roughly O(n n k), so this is a rather slow method,
and with k at 10% of n, is actually cubic: O(0.1 * n²).

This version cannot use index support, as the API operates without database
attachment. However, it should be possible to implement some trivial sorted-
list indexes to get a reasonable speedup!

###### Slope Dependence Measure

[AKSZ13] (since 0.5.5)

de.lmu.ifi.dbs.elki.math.statistics.dependence.SlopeDependenceMeasure

Arrange dimensions based on the entropy of the slope spectrum.

This version only accepts positive correlations, see also
SlopeInversionDependenceMeasure.

###### Slope Inversion Dependence Measure

[AKSZ13] (since 0.5.5)

de.lmu.ifi.dbs.elki.math.statistics.dependence.SlopeInversionDependenceMeasure

Arrange dimensions based on the entropy of the slope spectrum.

###### Spearman Correlation Dependence Measure

(since 0.7.0)

de.lmu.ifi.dbs.elki.math.statistics.dependence.SpearmanCorrelationDependenceMeasure

Spearman rank-correlation coefficient, also known as Spearmans Rho.

#####  AJ.2 Distribution

de.lmu.ifi.dbs.elki.math.statistics.distribution package:

Standard distributions, with random generation functionalities.

###### Beta Distribution

(since 0.5.0)

de.lmu.ifi.dbs.elki.math.statistics.distribution.BetaDistribution