# ELKI: A large open-source library for data analysis

Erich Schubert  Arthur Zimek

8

ELKI: A large open-source library for data analysis

ELKI Release 0.7.5 “Heidelberg”

https://elki-project.github.io/

Erich Schubert

Technische Universität Dortmund

Arthur Zimek

University of Southern Denmark

####  1 Introduction

This paper documents the release of the ELKI data mining framework, version
0.7.5.

ELKI is an open source (AGPLv3) data mining software written in Java. The
focus of ELKI is research in algorithms, with an emphasis on unsupervised
methods in cluster analysis and outlier detection. In order to achieve high
performance and scalability, ELKI offers data index structures such as the
R*-tree that can provide major performance gains. ELKI is designed to be easy
to extend for researchers and students in this domain, and welcomes
contributions of additional methods. ELKI aims at providing a large collection
of highly parameterizable algorithms, in order to allow easy and fair
evaluation and benchmarking of algorithms.

We will first outline the motivation for this release, the plans for the
future, and then give a brief overview over the new functionality in this
version. We also include an appendix presenting an overview on the overall
implemented functionality.

####  2 ELKI 0.7.5: “Heidelberg”

The majority of the work in this release was done at Heidelberg University,
both by students (that for example contributed many unit tests as part of Java
programming practicals) and by Dr. Erich Schubert.

The last official release 0.7.1 is now three years old. Some changes in Java
have broken this old release, and it does not run on Java 11 anymore (trivial
fixes are long available, but there has not been a released version) — three
years where we have continuted to add functionality, improve APIs, fix bugs,
…yet surprisingly many users still use the old version rather than building
the latest development version from git (albeit conveniently available at
Github, https://github.com/elki-project/elki).

There are a number of breaking changes queued up, waiting for a good moment to
be pushed. This includes an overhaul of the package names, migration to Java
11, support for automatic indexing, some automatic memory management for
automatically added indexes, etc.

Release 0.7.5 is intended as a snapshot to make all the new functionality of
the last three years easily available to everybody, and to open a new window
where breaking changes are allowed to get in, for the next version 0.8.0.

####  3 ELKI Plans for the Future

ELKI is an ongoing project. But because of new career responsibilities, the
former lead authors will likely be able to devote only much less time to this
project in the future.

If you want this project to continue being the largest open-source collection
of clustering and outlier detection algorithms – and (not the least because of
the support for data indexing) also one of the fastest [KSZ17] – then you
should consider contributing to this project yourself: for example, by adding
missing algorithms from the literature to our collection, fixing smaller bugs,
adding completely new functionality, and improving documentation. Thank you.

####  4 New Functionality in ELKI 0.7.5

#####  4.1 Clustering

  * •

Gaussian Mixture Modeling Improvements:
– Additional models  – Improved numerical stability [SG18b] – MAP for
robustness  – Better initialization

  * •

DBSCAN Improvements:

– GDBSCAN with similarity functions [EKSX96] – Parallel Generalized DBSCAN
related to [PPA+12]

  * •

Hierarchical clustering additions:

    * ◦

NN-Chain algorithm [Mur83, Mü11]

    * ◦

MiniMax clustering [AYN+05, BT11]

    * ◦

Flexible Beta Linkage [LW67]

    * ◦

Minimum Variance Linkage [DLPT85, Pod89]

  * •

Cluster extraction from dendrograms with handling of noise points and minimum
cluster size [SSW+17]

  * •

Basic BIRCH: clustering into leaves, with support for: [ZRL97, ZRL96]

Distances:  – Average Intercluster Distance  – Average Intracluster Distance
– Centroid Euclidean Distance  – Centroid Manhattan Distance  – Variance
Increase Distance

Merge Criterions:  – Diameter Criterion  – Euclidean Distance Criterion  –
Radius Criterion

  * •

PAM clustering additions:

    * ◦

Reynolds’ PAM [RRdlIRS06] and FastPAM [SR18]

    * ◦

Improvements to CLARA [KR86, KR90a] and FastCLARA [SR18]

    * ◦

CLARANS [NH02] and FastCLARANS [SR18]

  * •

$k$-Means clustering additions:

    * ◦

Annulus algorithm [HD14, Dra13]

    * ◦

Exponion algorithm [NF16]

    * ◦

Simplified Elkan’s algorithm [NF16]

    * ◦

$k$-Means– (more robust to noise) [CG13]

  * •

$k$-Means and PAM initialization additions:

    * ◦

Linear Approximative BUILD (LAB) [SR18]

    * ◦

Ostrovsky’s initial means [ORSS06, ORSS12]

    * ◦

Park’s initial medoids [PJ09]

    * ◦

Generated from a normal distribution [Jan66]

  * •

Leader Clustering [Har75]

  * •

FastDOC subspace clustering [PJAM02]

#####  4.2 Association Rule Mining

  * •

Association Rule Generation [ZJ14]

  * •

Interestingness Measures:  – Added Value [SM99] – Certainty Factor [GBSM02] –
Confidence [AIS93] – Conviction [BMUT97] – Cosine [TK00] – Gini Index [TK00,
BFOS84] – J Measure [SG91] – Jaccard [vR79, TKS04] – Klosgen [Klö96] –
Leverage [PS91] – Lift [BMS97]

#####  4.3 Outlier Detection

  * •

Cluster-Based Local Outlier Factor (CBLOF) [HXD03]

  * •

KNN Data Descriptor (KNNDD) [dRTD98]

  * •

Stochastic Outlier Selection (SOS) [SG17, JHPvdH12], with kNN approximation
(KNNSOS) [SG17, JHPvdH12], and intrinsic dimensionality (ISOS) [SG17]

#####  4.4 Projections and Embeddings

  * •

Stochastic Neighbor Embedding (SNE) [HR02]

  * •

t-Stochastic Neighbor Embedding (t-SNE) [vdMH08]

  * •

Barnes Hut approximation for tSNE [vdM14]

  * •

Intrinsic t-SNE [SG17]

#####  4.5 Change Point Detection in Time Series

  * •

Offline Change Point Detection [Pag57, BN93, Pic85]

  * •

Signi-Trend-based Change Detection [SWK14]

#####  4.6 Distance and Similarity Functions

• Cosine distances optimized for unit-length vectors  • Mahalanobis [Mah36] •
Chi Distance [ES03, PRTB99] • Fisher Rao Distance [DD09, Rao45] • Triangular
Discrimination [Top00] • Triangular Distance [CCVR16]

#####  4.7 Evaluation

  * •

Density-Based Cluster Validation (DBCV) [MJC+14]

  * •

Discounted Cumulative Gain (DCG) [JK02]

  * •

Normalized Discounted Cumulative Gain (NDCG) [JK02]

#####  4.8 Indexing Additions

  * •

Basic index support for similarities

  * •

NN Descent [DCL11]

  * •

M-Tree enhancements:

– Farthest Points Split  – MST Split [JTSF00] – Balanced Distribution [CPZ97]
– Farthest Balanced Distribution  – Generalized Hyperplane Distribution
[CPZ97]

  * •

X-Tree [BKK96] (non-reviewed code)

#####  4.9 Statistics Layer

  * •

Exp-Gamma distribution parameters using the method of moments

  * •

Log-Gamma distribution parameters using the method of moments

  * •

ALID estimator of intrinsic dimensionality [CHK16]

#####  4.10 Other Improvements

  * •

ELKI Builder API (see Section 5)

  * •

Integer range parameters (e.g., 1,2,..,10,20,..,100,200,..,1000)

  * •

Xoroshiro 128 fast random generator [Lem16, BV16]

  * •

Dendrogram visualization for hierarchical clusterings

  * •

Numerous unit tests

  * •

Many bug fixes found in testing and reported by users

####  5 ELKI Builder API

The ELKI Builder API is a simpler API to initialize classes from Java.

It is based on the standard “builder” pattern, and as it builds upon the
Parameterization API, it has support for _default values_ (a feature
unfortunately not in the Java API, nor are named parameters).

You can use standard Java constructors, but you will have to specify all
parameters:

new KMeansSort<>( /* distance= */ EuclideanDistanceFunction.STATIC, /* k= */
10, /* maxiter= */ 0, /* init= */ new
KMeansPlusPlusInitialMeans<NumberVector>( new RandomFactory(/* seed= */
0L)));For more complex classes such as the R∗-tree this can become quite
complicated.

If we want to add R-tree indexes (with sort-tile-recursive bulk loading), we
can initialize the factory much easier with the ELKIBuilder API, and only
specify the page size and bulk load:

new ELKIBuilder<>(RStarTreeFactory.class)
.with(AbstractPageFileFactory.Parameterizer.PAGE_SIZE_ID, 300)
.with(RStarTreeFactory.Parameterizer.BULK_SPLIT_ID,
SortTileRecursiveBulkSplit.class) .build();Furthermore, the parameters
directly correspond to the settings in the MiniGUI, hence make it easier to
first experiment in the MiniGUI, then transfer these settings into Java code.
While in the ELKI unit tests we always use the constants (to enable automatic
refactoring), you can also use string parameters here:

new ELKIBuilder<>(RStarTreeFactory.class) .with("pagefile.pagesize", 300)
.with("spatial.bulkstrategy", "str") .build();

####  6 Availability

ELKI Release 0.7.5 will be available

• on the project website: |  https://elki-project.github.io/releases/
---|---
• on Github: |  https://github.com/elki-project/elki/releases
• on Maven central: | in the group de.lmu.ifi.dbs.elki
| (0.7.5 will be the last version using this group id)
• via Jitpack: |  https://jitpack.io/p/elki-project/elki
| (which also allows accessing development builds)

An example project depending on ELKI is available at
https://github.com/elki-project/example-elki-project.

## Appendix

Functionality Available in ELKI 0.7.5

In this Appendix, we give a structured overview of the functionality
implemented in ELKI.

This is not a complete class list. We only include those classes that are
_modular_ , i.e., that can be substituted with other components to configure
the data analysis.

Where the classes are annotated with scientific references, we include them in
this list, as well as the version when this functionality was introduced in
ELKI (possibly with a different name). Note that a reference does not imply
this is based on the original code, nor a complete implementation of each
paper; but the references can be used to study the underlying ideas of the
implementations.

This Appendix is, to a large extend, automatically generated from the ELKI
JavaDoc documentation.

*off parttoc0em

###  Chapter Algorithm

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

Algorithms suitable as a task for the KDDTask main routine.

The KDDTask main routine expects an algorithm to implement the Algorithm-
Interface. Basic functions are already provided within AbstractAlgorithm, see
there for basic instructions of how to implement an algorithm suitable to the
framework.

###### Dependency Derivator: Deriving numerical inter-dependencies on data

[ABK+06b] (since 0.1)

de.lmu.ifi.dbs.elki.algorithm.DependencyDerivator

Dependency derivator computes quantitatively linear dependencies among
attributes of a given dataset based on a linear correlation PCA.

###### KNN-Distance-Order

[EKSX96, SSE+17] (since 0.1)

de.lmu.ifi.dbs.elki.algorithm.KNNDistancesSampler

Provides an order of the kNN-distances for all objects within the database.

This class can be used to estimate parameters for other algorithms, such as
estimating the epsilon parameter for DBSCAN: set k to minPts-1, and then
choose a percentile from the sample as epsilon, or plot the result as a graph
and look for a bend or knee in this plot.

###### K-Nearest Neighbor Join

(since 0.1)

de.lmu.ifi.dbs.elki.algorithm.KNNJoin

Joins in a given spatial database to each object its k-nearest neighbors. This
algorithm only supports spatial databases based on a spatial index structure.

Since this method compares the MBR of every single leaf with every other leaf,
it is essentially quadratic in the number of leaves, which may not be
appropriate for large trees. It does currently not yet use the tree structure
for pruning.

###  Appendix A Benchmark

de.lmu.ifi.dbs.elki.algorithm.benchmark package:

Benchmarking pseudo algorithms.

The algorithms in this package are meant to be used in run time benchmarks, to
evalute e.g. the performance of an index structure.

###### KNN Benchmark Algorithm

(since 0.5.5)

de.lmu.ifi.dbs.elki.algorithm.benchmark.KNNBenchmarkAlgorithm

Benchmarking algorithm that computes the k nearest neighbors for each query
point. The query points can either come from a separate data source, or from
the original database.

###### Range Query Benchmark Algorithm

(since 0.5.5)

de.lmu.ifi.dbs.elki.algorithm.benchmark.RangeQueryBenchmarkAlgorithm

Benchmarking algorithm that computes a range query for each point. The query
points can either come from a separate data source, or from the original
database. In the latter case, the database is expected to have an additional,
1-dimensional vector field. For the separate data source, the last dimension
will be cut off and used as query radius.

The simplest data setup clearly is to have an input file:

x y z label1 2 3 Example14 5 6 Example27 8 9 Example3and a query file:

x y z radius1 2 3 1.24 5 6 3.37 8 9 4.1where the additional column is the
radius.

Alternatively, if you work with a single file, you need to use the filter
command -dbc.filter SplitNumberVectorFilter -split.dims 1,2,3 to split the
relation into a 3-dimensional data vector, and 1 dimensional radius vector.

###### Validate Approximative KNN Index

(since 0.6.0)

de.lmu.ifi.dbs.elki.algorithm.benchmark.ValidateApproximativeKNNIndex

Algorithm to validate the quality of an approximative kNN index, by performing
a number of queries and comparing them to the results obtained by exact
indexing (e.g. linear scanning).

###  Appendix B Classification

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

Classification algorithms.

###### kNN-classifier

(since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.classification.KNNClassifier

KNNClassifier classifies instances based on the class distribution among the k
nearest neighbors in a database.

###### Prior Probability Classifier

(since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.classification.PriorProbabilityClassifier

Classifier to classify instances based on the prior probability of classes in
the database, without using the actual data values.

###  Appendix C Clustering

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

Clustering algorithms.

Clustering algorithms are supposed to implement the Algorithm-Interface. The
more specialized interface ClusteringAlgorithm requires an implementing
algorithm to provide a special result class suitable as a partitioning of the
database. More relaxed clustering algorithms are allowed to provide a result
that is a fuzzy clustering, does not partition the database complete or is in
any other sense a relaxed clustering result.

###### Canopy Pre Clustering

[MNU00] (since 0.6.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.CanopyPreClustering

Canopy pre-clustering is a simple preprocessing step for clustering.

###### DBSCAN: Density-Based Clustering of Applications with Noise

[EKSX96, SSE+17] (since 0.1)

de.lmu.ifi.dbs.elki.algorithm.clustering.DBSCAN

Density-Based Clustering of Applications with Noise (DBSCAN), an algorithm to
find density-connected sets in a database.

###### GriDBSCAN: Using Grid for Accelerating Density-Based Clustering

[MM08] (since 0.7.1)

de.lmu.ifi.dbs.elki.algorithm.clustering.GriDBSCAN

Using Grid for Accelerating Density-Based Clustering.

An accelerated DBSCAN version for numerical data and Lp-norms only, by
partitioning the data set into overlapping grid cells. For best efficiency,
the overlap of the grid cells must be chosen well. The authors suggest a grid
width of 10 times epsilon.

Because of partitioning the data, this version does not make use of indexes.

###### Leader

[Har75] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.Leader

Leader clustering algorithm.

###### Naive Mean Shift Clustering

[Che95] (since 0.5.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.NaiveMeanShiftClustering

Mean-shift based clustering algorithm. Naive implementation: there does not
seem to be "the" mean-shift clustering algorithm, but it is a general concept.
For the naive implementation, mean-shift is applied to all objects until they
converge to other. This implementation is quite naive, and various
optimizations can be made.

It also is not really parameter-free: the kernel needs to be specified,
including a radius/bandwidth.

By using range queries, the algorithm does benefit from index structures!

###### SNN: Shared Nearest Neighbor Clustering

[ESK03] (since 0.1)

de.lmu.ifi.dbs.elki.algorithm.clustering.SNNClustering

Shared nearest neighbor clustering.

#####  C.1 Affinitypropagation

de.lmu.ifi.dbs.elki.algorithm.clustering.affinitypropagation package:

Affinity Propagation (AP) clustering.

###### Affinity Propagation: Clustering by Passing Messages Between Data
Points

[FD07] (since 0.6.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.affinitypropagation.AffinityPropagationClusteringAlgorithm

Cluster analysis by affinity propagation.

###### Distance Based Initialization With Median

(since 0.6.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.affinitypropagation.DistanceBasedInitializationWithMedian

Distance based initialization.

###### Similarity Based Initialization With Median

(since 0.6.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.affinitypropagation.SimilarityBasedInitializationWithMedian

Similarity based initialization.

#####  C.2 Biclustering

de.lmu.ifi.dbs.elki.algorithm.clustering.biclustering package:

Biclustering algorithms.

###### Cheng And Church

[CC00] (since 0.6.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.biclustering.ChengAndChurch

Cheng and Church biclustering.

#####  C.3 Correlation

de.lmu.ifi.dbs.elki.algorithm.clustering.correlation package:

Correlation clustering algorithms

###### CASH: Robust clustering in arbitrarily oriented subspaces

[ABD+08] (since 0.1)

de.lmu.ifi.dbs.elki.algorithm.clustering.correlation.CASH

The CASH algorithm is a subspace clustering algorithm based on the Hough
transform.

###### COPAC: COrrelation PArtition Clustering

[ABK+07c] (since 0.1)

de.lmu.ifi.dbs.elki.algorithm.clustering.correlation.COPAC

COPAC is an algorithm to partition a database according to the correlation
dimension of its objects and to then perform an arbitrary clustering algorithm
over the partitions.

###### ERiC: Exploring Relationships among Correlation Clusters

[ABK+07b] (since 0.1)

de.lmu.ifi.dbs.elki.algorithm.clustering.correlation.ERiC

Performs correlation clustering on the data partitioned according to local
correlation dimensionality and builds a hierarchy of correlation clusters that
allows multiple inheritance from the clustering result.

###### 4C: Computing Correlation Connected Clusters

[BKKZ04] (since 0.1)

de.lmu.ifi.dbs.elki.algorithm.clustering.correlation.FourC

4C identifies local subgroups of data objects sharing a uniform correlation.
The algorithm is based on a combination of PCA and density-based clustering
(DBSCAN).

###### Mining Hierarchies of Correlation Clusters

[ABKZ06] (since 0.1)

de.lmu.ifi.dbs.elki.algorithm.clustering.correlation.HiCO

Implementation of the HiCO algorithm, an algorithm for detecting hierarchies
of correlation clusters.

###### LMCLUS

[HH07] (since 0.5.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.correlation.LMCLUS

Linear manifold clustering in high dimensional spaces by stochastic search.

###### ORCLUS: Arbitrarily ORiented projected CLUSter generation

[AY00] (since 0.1)

de.lmu.ifi.dbs.elki.algorithm.clustering.correlation.ORCLUS

ORCLUS: Arbitrarily ORiented projected CLUSter generation.

#####  C.4 EM

de.lmu.ifi.dbs.elki.algorithm.clustering.em package:

Expectation-Maximization clustering algorithm.

###### Diagonal Gaussian Model Factory

(since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.em.DiagonalGaussianModelFactory

Factory for EM with multivariate gaussian models using diagonal matrixes.

These models have individual variances, but no covariance, so this corresponds
to the ’VVI’ model in Mclust (R).

###### EM-Clustering: Clustering by Expectation Maximization

[FR07, DLR77] (since 0.1)

de.lmu.ifi.dbs.elki.algorithm.clustering.em.EM

Clustering by expectation maximization (EM-Algorithm), also known as Gaussian
Mixture Modeling (GMM), with optional MAP regularization.

###### Multivariate Gaussian Model Factory

(since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.em.MultivariateGaussianModelFactory

Factory for EM with multivariate Gaussian models (with covariance; also known
as Gaussian Mixture Modeling, GMM).

These models have individual covariance matrixes, so this corresponds to the
’VVV’ model in Mclust (R).

###### Spherical Gaussian Model Factory

(since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.em.SphericalGaussianModelFactory

Factory for EM with multivariate gaussian models using a single variance.

These models have a single variances, no covariance, so this corresponds to
the ’VII’ model in Mclust (R).

###### Textbook Multivariate Gaussian Model Factory

(since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.em.TextbookMultivariateGaussianModelFactory

Factory for EM with multivariate Gaussian model, using the textbook algorithm.
There is no reason to use this in practice, it is only useful to study the
reliability of the textbook approach.

"Textbook" refers to the E[XY]-E[X]E[Y] equation for covariance, that is
numerically not reliable with floating point math, but popular in textbooks.

Again, do not use this. Always prefer #MultivariateGaussianModelFactory.

###### Two Pass Multivariate Gaussian Model Factory

(since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.em.TwoPassMultivariateGaussianModelFactory

Factory for EM with multivariate Gaussian models (with covariance; also known
as Gaussian Mixture Modeling, GMM).

These models have individual covariance matrixes, so this corresponds to the
’VVV’ model in Mclust (R).

#####  C.5 GDBSCAN

de.lmu.ifi.dbs.elki.algorithm.clustering.gdbscan package:

Generalized DBSCAN. Generalized DBSCAN is an abstraction of the original
DBSCAN idea, that allows the use of arbitrary "neighborhood" and "core point"
predicates.

For each object, the neighborhood as defined by the "neighborhood" predicate
is retrieved - in original DBSCAN, this is the objects within an epsilon
sphere around the query object. Then the core point predicate is evaluated to
decide if the object is considered dense. If so, a cluster is started (or
extended) to include the neighbors as well.

###### COPAC Neighbor Predicate

[ABK+07c] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.gdbscan.COPACNeighborPredicate

COPAC neighborhood predicate.

###### ERiC Neighbor Predicate

[ABK+07b] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.gdbscan.ERiCNeighborPredicate

ERiC neighborhood predicate.

###### Epsilon Neighbor Predicate

[EKSX96] (since 0.5.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.gdbscan.EpsilonNeighborPredicate

The default DBSCAN and OPTICS neighbor predicate, using an epsilon-
neighborhood.

###### Four C Core Predicate

[BKKZ04] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.gdbscan.FourCCorePredicate

The 4C core point predicate.

###### Four C Neighbor Predicate

[BKKZ04] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.gdbscan.FourCNeighborPredicate

4C identifies local subgroups of data objects sharing a uniform correlation.
The algorithm is based on a combination of PCA and density-based clustering
(DBSCAN).

###### Generalized DBSCAN

[SEKX98] (since 0.5.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.gdbscan.GeneralizedDBSCAN

Generalized DBSCAN, density-based clustering with noise.

###### LSDBC: Locally Scaled Density Based Clustering

[BY07] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.gdbscan.LSDBC

Locally Scaled Density Based Clustering.

This is a variant of DBSCAN which starts with the most dense point first, then
expands clusters until density has dropped below a threshold.

###### MinPts Core Predicate

[EKSX96] (since 0.5.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.gdbscan.MinPtsCorePredicate

The DBSCAN default core point predicate – having at least minpts neighbors.

###### PreDeCon Core Predicate

[BKKK04] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.gdbscan.PreDeConCorePredicate

The PreDeCon core point predicate – having at least minpts. neighbors, and a
maximum preference dimensionality of lambda.

###### PreDeCon Neighbor Predicate

[BKKK04] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.gdbscan.PreDeConNeighborPredicate

Neighborhood predicate used by PreDeCon.

###### Similarity Neighbor Predicate

[EKSX96] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.gdbscan.SimilarityNeighborPredicate

The DBSCAN neighbor predicate for a SimilarityFunction, using all neighbors
with a minimum similarity.

######  C.5.1 Gdbscan Parallel

de.lmu.ifi.dbs.elki.algorithm.clustering.gdbscan.parallel package:

Parallel versions of Generalized DBSCAN.

###### Parallel Generalized DBSCAN

[PPA+12] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.gdbscan.parallel.ParallelGeneralizedDBSCAN

Parallel version of DBSCAN clustering.

This is the archetype of a non-linear shared-memory DBSCAN that does not
sequentially expand a cluster, but processes points in arbitrary order and
merges clusters when neighboring core points occur.

Because of synchronization when labeling points, the speedup will only be
sublinear in the number of cores. But in particular without an index and on
large data, the majority of the work is finding the neighbors; not in labeling
the points.

#####  C.6 Hierarchical

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical package:

Hierarchical agglomerative clustering (HAC).

###### AGNES

[Cor71, KR90b, Sne57] (since 0.6.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.AGNES

Hierarchical Agglomerative Clustering (HAC) or Agglomerative Nesting (AGNES)
is a classic hierarchical clustering algorithm. Initially, each element is its
own cluster; the closest clusters are merged at every step, until all the data
has become a single cluster.

This is the naive O(n³) algorithm. See SLINK for a much faster algorithm
(however, only for single-linkage).

This implementation uses the pointer-based representation used by SLINK, so
that the extraction algorithms we have can be used with either of them.

The algorithm is believed to be first published (for single-linkage) by:

P. H. Sneath
The application of computers to taxonomy
Journal of general microbiology, 17(1).

This algorithm is also known as AGNES (Agglomerative Nesting), where the use
of alternative linkage criterions is discussed:

L. Kaufman, P. J. Rousseeuw
Agglomerative Nesting (Program AGNES),
in Finding Groups in Data: An Introduction to Cluster Analysis

###### Abstract HDBSCAN

[CMS13] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.AbstractHDBSCAN

Abstract base class for HDBSCAN variations.

###### Anderberg Hierarchical Clustering

[And73a] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.AnderbergHierarchicalClustering

This is a modification of the classic AGNES algorithm for hierarchical
clustering using a nearest-neighbor heuristic for acceleration.

Instead of scanning the matrix (with cost O(n²)) to find the minimum, the
nearest neighbor of each object is remembered. On the downside, we need to
check these values at every merge, and it may now cost O(n²) to perform a
merge, so there is no worst-case advantage to this approach. The average case
however improves from O(n³) to O(n²), which yields a considerable improvement
in running time.

This optimization is attributed to M. R. Anderberg.

###### CLINK

[Def77] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.CLINK

CLINK algorithm for complete linkage.

This algorithm runs in O(n²) time, and needs only O(n) memory. The results can
differ from the standard algorithm in unfavorable ways, and are order-
dependent (Defays: "Modifications of the labeling permit us to obtain
different minimal superior ultrametric dissimilarities"). Unfortunately, the
results are usually perceived to be substantially worse than the more
expensive algorithms for complete linkage clustering. This arises from the
fact that this algorithm has to add the new object to the existing tree in
every step, instead of being able to always do the globally best merge.

###### HDBSCAN: Hierarchical Density-Based Spatial Clustering of Applications
with Noise

[CMS13] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.HDBSCANLinearMemory

Linear memory implementation of HDBSCAN clustering.

By not building a distance matrix, we can reduce memory usage to linear memory
only; but at the cost of roughly double the runtime (unless using indexes) as
we first need to compute all kNN distances (for core sizes), then recompute
distances when building the spanning tree.

This implementation follows the HDBSCAN publication more closely than
SLINKHDBSCANLinearMemory, by computing the minimum spanning tree using Prim’s
algorithm (instead of SLINK; although the two are remarkably similar). In
order to produce the preferred internal format of hierarchical clusterings
(the compact pointer representation introduced in SLINK) we have to perform a
postprocessing conversion.

This implementation does not include the cluster extraction discussed as Step
4, which is provided in a separate step. For this reason, we also do not
include self-edges.

###### Mini Max

[AYN+05, BT11] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.MiniMax

Minimax Linkage clustering.

###### Mini Max Anderberg

[And73a] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.MiniMaxAnderberg

This is a modification of the classic MiniMax algorithm for hierarchical
clustering using a nearest-neighbor heuristic for acceleration.

This optimization is attributed to M. R. Anderberg.

This particular implementation is based on AnderbergHierarchicalClustering

###### Mini Max NN Chain

[Mur83, Mü11] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.MiniMaxNNChain

MiniMax hierarchical clustering using the NNchain algorithm.

###### NN Chain

[Mur83, Mü11] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.NNChain

NNchain clustering algorithm.

###### SLINK: Single Link Clustering

[Sib73] (since 0.6.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.SLINK

Implementation of the efficient Single-Link Algorithm SLINK of R. Sibson.

This is probably the fastest exact single-link algorithm currently in use.

###### SLINKHDBSCAN Linear Memory

[CMS13] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.SLINKHDBSCANLinearMemory

Linear memory implementation of HDBSCAN clustering based on SLINK.

By not building a distance matrix, we can reduce memory usage to linear memory
only; but at the cost of roughly double the runtime (unless using indexes) as
we first need to compute all kNN distances (for core sizes), then recompute
distances when building the spanning tree.

This version uses the SLINK algorithm to directly produce the pointer
representation expected by the extraction methods. The SLINK algorithm is
closely related to Prim’s minimum spanning tree, but produces the more compact
pointer representation instead of an edges list.

This implementation does not include the cluster extraction discussed as Step
4. This functionality should however already be provided by
HDBSCANHierarchyExtraction . For this reason, we also do not include self-
edges.

######  C.6.1 Hierarchical Birch

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.birch package:

BIRCH clustering.

###### Average Intercluster Distance

[Zha96] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.birch.AverageInterclusterDistance

Average intercluster distance.

###### Average Intracluster Distance

[Zha96] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.birch.AverageIntraclusterDistance

Average intracluster distance.

###### BIRCH Leaf Clustering

[ZRL97, ZRL96] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.birch.BIRCHLeafClustering

BIRCH-based clustering algorithm that simply treats the leafs of the CFTree as
clusters.

###### CF Tree

[ZRL97, ZRL96] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.birch.CFTree

Partial implementation of the CFTree as used by BIRCH.

Important differences:

  1. 1.

Leaf nodes and directory nodes have the same capacity

  2. 2.

Condensing and memory limits are not implemented

  3. 3.

Merging refinement (merge-resplit) is not implemented

Because we want to be able to track the cluster assignments of all data points
easily, we need to store the point IDs, and it is not possible to implement
the originally proposed page size management at the same time.

Condensing and merging refinement are possible, and improvements to this code
are welcome - please send a pull request!

###### Centroid Euclidean Distance

[Zha96] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.birch.CentroidEuclideanDistance

Centroid Euclidean distance.

###### Centroid Manhattan Distance

[Zha96] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.birch.CentroidManhattanDistance

Centroid Manhattan Distance

###### Diameter Criterion

[ZRL96] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.birch.DiameterCriterion

Average Radius (R) criterion.

###### Euclidean Distance Criterion

(since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.birch.EuclideanDistanceCriterion

Distance criterion.

This is not found in the original work, but used in many implementation
attempts: assign points if the Euclidean distances is below a threshold.

###### Radius Criterion

[ZRL96] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.birch.RadiusCriterion

Average Radius (R) criterion.

###### Variance Increase Distance

[Zha96] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.birch.VarianceIncreaseDistance

Variance increase distance.

######  C.6.2 Hierarchical Extraction

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.extraction package:

Extraction of partitional clusterings from hierarchical results.

###### Clusters With Noise Extraction

[SSW+17] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.extraction.ClustersWithNoiseExtraction

Extraction of a given number of clusters with a minimum size, and noise.

This will execute the highest-most cut where we retain k clusters, each with a
minimum size, plus noise (single points that would only merge afterwards). If
no such cut can be found, it returns a result with a relaxed k.

You need to specify: A) the minimum size of a cluster (it does not make much
sense to use 1 - then it will simply execute all but the last k merges) and B)
the desired number of clusters with at least minSize elements each.

###### Cut Dendrogram By Height

(since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.extraction.CutDendrogramByHeight

Extract a flat clustering from a full hierarchy, represented in pointer form.

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

(since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.extraction.CutDendrogramByNumberOfClusters

Extract a flat clustering from a full hierarchy, represented in pointer form.

###### HDBSCAN Hierarchy Extraction

[CMS13] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.extraction.HDBSCANHierarchyExtraction

Extraction of simplified cluster hierarchies, as proposed in HDBSCAN.

In contrast to the authors top-down approach, we use a bottom-up approach
based on the more efficient pointer representation introduced in SLINK.

In particular, it can also be used to extract a hierarchy from a hierarchical
agglomerative clustering.

###### Simplified Hierarchy Extraction

[CMS13] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.extraction.SimplifiedHierarchyExtraction

Extraction of simplified cluster hierarchies, as proposed in HDBSCAN.

In contrast to the authors top-down approach, we use a bottom-up approach
based on the more efficient pointer representation introduced in SLINK.

######  C.6.3 Hierarchical Linkage

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.linkage package:

Linkages for hierarchical clustering.

###### Centroid Linkage

[Gow67] (since 0.6.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.linkage.CentroidLinkage

Centroid linkage — Unweighted Pair-Group Method using Centroids (UPGMC).

This is closely related to GroupAverageLinkage (UPGMA), but the resulting
distance corresponds to the distance of the cluster centroids when used with
squared Euclidean distance.

For Lance-Williams, we can then obtain the following recursive definition:

$d_{\text{UPGMC}}(A\cup
B,C)=\tfrac{|A|}{|A|+|B|}d(A,C)+\tfrac{|B|}{|A|+|B|}d(B,C)-\tfrac{|A|\cdot|B|}{(|A|+|B|)^{2}}d(A,B)$

With squared Euclidean distance, we then get the cluster distance:

$d_{\text{UPGMC}}(A,B)=||\tfrac{1}{|A|}\sum\nolimits_{a\in
A}a,\tfrac{1}{|B|}\sum\nolimits_{b\in B}b||^{2}$

but for other distances, this will not generally be true.

Because the ELKI implementations use Lance-Williams, this linkage should only
be used with (squared) Euclidean distance.

While titled "unweighted", this method does take cluster sizes into account
when merging clusters with Lance-Williams.

While the idea of this method — at least for squared Euclidean — is compelling
(distance of cluster centers), it is not as well behaved as one may think. It
can yield so called "inversions", where a later merge has a smaller distance
than an early merge, because a cluster center can be closer to a neighboring
cluster than any of the individual points. Because of this, the
GroupAverageLinkage (UPGMA) is usually preferable.

###### Complete Linkage

[LW67, Sø48, Joh67, MS65] (since 0.6.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.linkage.CompleteLinkage

Complete-linkage ("maximum linkage") clustering method.

The distance of two clusters is simply the maximum of all pairwise distances
between the two clusters.

The distance of two clusters is defined as:

$d_{\max}(A,B):=\max_{a\in A}\max_{b\in B}d(a,b)$

This can be computed recursively using:

$d_{\max}(A\cup B,C)=\max(d(A,C),d(B,C))$

Note that with similarity functions, one would need to use the minimum instead
to get the same effect.

The algorithm CLINK is a faster algorithm to find such clusterings, but it is
very much order dependent and tends to find worse solutions.

###### Flexible Beta Linkage

[LW67] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.linkage.FlexibleBetaLinkage

Flexible-beta linkage as proposed by Lance and Williams.

Beta values larger than 0 cause chaining, and are thus not recommended.
Instead, choose a value between -1 and 0.

The general form of the recursive definition is:

$d_{\text{Flexible},\beta}(A\cup
B,C):=\tfrac{1-\beta}{2}d(A,C)+\tfrac{1-\beta}{2}d(B,C)+\beta d(A,B)$

###### Group Average Linkage

[SM02] (since 0.6.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.linkage.GroupAverageLinkage

Group-average linkage clustering method (UPGMA).

This is a good default linkage to use with hierarchical clustering, as it
neither exhibits the single-link chaining effect, nor has the strong tendency
of complete linkage to split large clusters. It is also easy to understand,
and it can be used with arbitrary distances and similarity functions.

The distances of two clusters is defined as the between-group average distance
of two points $a$ and $b$, one from each cluster. It should be noted that this
is not the average distance within the resulting cluster, because it does not
take within-cluster distances into account.

The distance of two clusters in this method is:

$d_{\text{UPGMA}}(A,B)=\tfrac{1}{|A|\cdot|B|}\sum\nolimits_{a\in
A}\sum\nolimits_{b\in B}d(a,b)$

For Lance-Williams, we can then obtain the following recursive definition:

$d_{\text{UPGMA}}(A\cup
B,C)=\tfrac{|A|}{|A|+|B|}d(A,C)+\tfrac{|B|}{|A|+|B|}d(B,C)$

While the method is also called "Unweighted Pair Group Method with Arithmetic
mean", it uses weights in the Lance-Williams formulation that account for the
cluster size. It is unweighted in the sense that every point keeps the same
weight, whereas in WeightedAverageLinkage (WPGMA), the weight of points
effectively depends on the depth in the cluster tree.

###### Linkage

[LW67] (since 0.6.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.linkage.Linkage

Abstract interface for implementing a new linkage method into hierarchical
clustering.

###### Median Linkage

[Gow67] (since 0.6.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.linkage.MedianLinkage

Median-linkage — weighted pair group method using centroids (WPGMC).

Similar to WeightedAverageLinkage (WPGMA), the weight of points in this method
decreases with the depth of the tree. This yields to difficult to understand
semantics of the result, as it does not yield the distance of medians. The
method is best defined recursively:

$d_{\text{WPGMC}}(A\cup
B,C):=\tfrac{1}{2}d(A,C)+\tfrac{1}{2}d(B,C)-\tfrac{1}{4}d(A,B)$

###### Minimum Variance Linkage

[DLPT85, Pod89] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.linkage.MinimumVarianceLinkage

Minimum increase in variance (MIVAR) linkage.

This is subtly different from Ward’s method (WardLinkage, MISSQ), because
variance is normalized by the cluster size; and Ward minimizes the increase in
sum of squares (without normalization).

$d_{\text{MIVAR}}(A\cup
B,C)=\left(\tfrac{|A|+|C|}{|A|+|B|+|C|}\right)^{2}d(A,C)+\left(\tfrac{|B|+|C|}{|A|+|B|+|C|}\right)^{2}d(B,C)-\tfrac{|C|\cdot(|A|+|B|)}{(|A|+|B|+|C|)^{2}}d(A,B)$

or equivalently:

$d_{\text{MIVAR}}(A\cup
B,C)=\tfrac{(|A|+|C|)^{2}d(A,C)+(|B|+|C|)^{2}d(B,C)-|C|\cdot(|A|+|B|)d(A,B)}{(|A|+|B|+|C|)^{2}}$

###### Single Linkage

[FŁP+51] (since 0.6.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.linkage.SingleLinkage

Single-linkage ("minimum") clustering method.

The distance of two clusters is simply the minimum of all pairwise distances
between the two clusters.

The distance of two clusters is defined as:

$d_{\min}(A,B):=\min_{a\in A}\min_{b\in B}d(a,b)$

This can be computed recursively using:

$d_{\min}(A\cup B,C)=\min(d(A,C),d(B,C))$

Note that with similarity functions, one would need to use the maximum instead
to get the same effect.

###### Ward Linkage

[Wis69, War63] (since 0.6.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.linkage.WardLinkage

Ward’s method clustering method.

This criterion minimizes the increase of squared errors, and should be used
with squared Euclidean distance. Usually, ELKI will try to automatically
square distances when you combine this with Euclidean distance. For
performance reasons, the direct use of squared distances is preferable!

The distance of two clusters in this method is:

$d_{\text{Ward}}(A,B):=\text{SSE}(A\cup B)-\text{SSE}(A)-\text{SSE}(B)$

where the sum of squared errors is defined as:

$\text{SSE}(X):=\sum\nolimits_{x\in X}(x-\mu_{X})^{2}\qquad\text{with
}\mu_{X}=\tfrac{1}{|X|}\sum\nolimits_{x\in X}X$

This objective can be rewritten to

$d_{\text{Ward}}(A,B):=\tfrac{|A|\cdot|B|}{|A|+|B|}||\mu_{A}-\mu_{B}||^{2}=\tfrac{1}{1/|A|+1/|B|}||\mu_{A}-\mu_{B}||^{2}$

For Lance-Williams, we can then obtain the following recursive definition:

$d_{\text{Ward}}(A\cup
B,C)=\tfrac{|A|+|C|}{|A|+|B|+|C|}d(A,C)+\tfrac{|B|+|C|}{|A|+|B|+|C|}d(B,C)-\tfrac{|C|}{|A|+|B|+|C|}d(A,B)$

These transformations rely on properties of the L2-norm, so they cannot be
used with arbitrary metrics, unless they are equivalent to the L2-norm in some
transformed space.

Because the resulting distances are squared, when used with a non-squared
distance, ELKI implementations will apply the square root before returning the
final result. This is statistically somewhat questionable, but usually yields
more interpretable distances that — roughly — correspond to the increase in
standard deviation. With ELKI, you can get both behavior: Either choose
squared Euclidean distance, or regular Euclidean distance.

This method is also referred to as "minimize increase of sum of squares"
(MISSQ) by Podani.

###### Weighted Average Linkage

[SM02] (since 0.6.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.linkage.WeightedAverageLinkage

Weighted average linkage clustering method (WPGMA).

This is somewhat a misnomer, as it actually ignores that the clusters should
likely be weighted differently according to their size when computing the
average linkage. See GroupAverageLinkage for the UPGMA method that uses the
group size to weight the objects the same way. Because of this, it is
sometimes also called "simple average".

There does not appear to be a closed form distance for this clustering, but it
is only defined recursively on the previous clusters simply by

$d_{\text{WPGMA}}(A\cup B,C):=\tfrac{1}{2}d(A,C)+\tfrac{1}{2}d(B,C)$

MedianLinkage (WPGMC) is similar in the sense that it is ignoring the cluster
sizes, and therefore the weight of points decreases with the depth of the
tree. The method is "weighted" in the sense that the new members get the
weight adjusted to match the old cluster members.

#####  C.7 Kmeans

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans package:

K-means clustering and variations.

###### Best Of Multiple K Means

(since 0.6.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.BestOfMultipleKMeans

Run K-Means multiple times, and keep the best run.

###### CLARA

[KR90a, KR86] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.CLARA

Clustering Large Applications (CLARA) is a clustering method for large data
sets based on PAM, partitioning around medoids (KMedoidsPAM) based on
sampling.

###### CLARANS

[NH02] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.CLARANS

CLARANS: a method for clustering objects for spatial data mining is inspired
by PAM (partitioning around medoids, KMedoidsPAM) and CLARA and also based on
sampling.

This implementation tries to balance memory and computation time. By caching
the distances to the two nearest medoids, we usually only need O(n) instead of
O(nk) distance computations for one iteration, at the cost of needing O(2n)
memory to store them.

The implementation is fairly ugly, because we have three solutions (the best
found so far, the current solution, and a neighbor candidate); and for each
point in each solution we need the best and second best assignments. But with
Java 11, we may be able to switch to value types that would clean this code
significantly, without the overhead of O(n) objects.

###### Fast CLARA

[SR18] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.FastCLARA

Clustering Large Applications (CLARA) with the KMedoidsFastPAM improvements,
to increase scalability in the number of clusters. This variant will also
default to twice the sample size, to improve quality.

###### Fast CLARANS

[SR18] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.FastCLARANS

A faster variation of CLARANS, that can explore O(k) as many swaps at a
similar cost by considering all medoids for each candidate non-medoid. Since
this means sampling fewer non-medoids, we suggest to increase the subsampling
rate slightly to get higher quality than CLARANS, at better runtime.

###### K Means Annulus

[HD14, Dra13] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.KMeansAnnulus

Annulus k-means algorithm. A variant of Hamerly with an additional bound,
based on comparing the norm of the mean and the norm of the points.

This implementation could be further improved by precomputing and storing the
norms of all points (at the cost of O(n) memory additionally).

###### K Means Bisecting

[SKK00] (since 0.6.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.KMeansBisecting

The bisecting k-means algorithm works by starting with an initial partitioning
into two clusters, then repeated splitting of the largest cluster to get
additional clusters.

###### Compare-Means

[Phi02] (since 0.7.1)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.KMeansCompare

Compare-Means: Accelerated k-means by exploiting the triangle inequality and
pairwise distances of means to prune candidate means.

###### K Means Elkan

[Elk03] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.KMeansElkan

Elkan’s fast k-means by exploiting the triangle inequality.

This variant needs O(n*k) additional memory to store bounds.

See KMeansHamerly for a close variant that only uses O(n*2) additional memory
for bounds.

###### K Means Exponion

[NF16] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.KMeansExponion

Newlings’s exponion k-means algorithm, exploiting the triangle inequality.

This is not a complete implementation, the approximative sorting part is
missing. We also had to guess on the paper how to make best use of F.

###### K Means Hamerly

[Ham10] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.KMeansHamerly

Hamerly’s fast k-means by exploiting the triangle inequality.

###### k-Means (Lloyd/Forgy Algorithm)

[For65, Llo82] (since 0.5.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.KMeansLloyd

The standard k-means algorithm, using bulk iterations and commonly attributed
to Lloyd and Forgy (independently).

###### k-Means (MacQueen Algorithm)

[Mac67] (since 0.1)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.KMeansMacQueen

The original k-means algorithm, using MacQueen style incremental updates;
making this effectively an "online" (streaming) algorithm.

This implementation will by default iterate over the data set until
convergence, although MacQueen likely only meant to do a single pass over the
data, but the result quality improves with multiple passes.

###### K-Means–

[CG13] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.KMeansMinusMinus

k-means–: A Unified Approach to Clustering and Outlier Detection.

Similar to Lloyds K-means algorithm, but ignores the farthest points when
updating the means, considering them to be outliers.

###### K Means Simplified Elkan

[NF16] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.KMeansSimplifiedElkan

Simplified version of Elkan’s k-means by exploiting the triangle inequality.

Compared to KMeansElkan, this uses less pruning, but also does not need to
maintain a matrix of pairwise centroid separation.

###### Sort-Means

[Phi02] (since 0.7.1)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.KMeansSort

Sort-Means: Accelerated k-means by exploiting the triangle inequality and
pairwise distances of means to prune candidate means (with sorting).

###### K Medians Lloyd

[BMS96] (since 0.5.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.KMediansLloyd

k-medians clustering algorithm, but using Lloyd-style bulk iterations instead
of the more complicated approach suggested by Kaufman and Rousseeuw (see
KMedoidsPAM instead).

###### K Medoids Fast PAM

[SR18] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.KMedoidsFastPAM

FastPAM: An improved version of PAM, that is usually O(k) times faster. This
class incorporates the benefits of KMedoidsFastPAM1, but in addition it tries
to perform multiple swaps in each iteration (FastPAM2), which can reduce the
total number of iterations needed substantially for large k, if some areas of
the data are largely independent.

There is a tolerance parameter, which controls how many additional swaps are
performed. When set to 0, it will only execute an additional swap if it
appears to be independent (i.e., the improvements resulting from the swap have
not decreased when the first swap was executed). We suggest to rather leave it
at the default of 1, which means to perform any additional swap that gives an
improvement. We could not observe a tendency to find worse results when doing
these additional swaps, but a reduced runtime.

Because of the speed benefits, we also suggest to use a linear-time
initialization, such as the k-means++ initialization or the proposed LAB
(linear approximative BUILD, the third component of FastPAM) initialization,
and try multiple times if the runtime permits.

###### K Medoids Fast PAM1

[SR18] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.KMedoidsFastPAM1

FastPAM1: A version of PAM that is O(k) times faster, i.e., now in O((n-k)²).
The change here feels pretty small - we handle all k medoids in parallel using
an array. But this means the innermost loop only gets executed in O(1/k) of
all iterations, and thus we benefit on average.

This acceleration gives exactly (assuming perfect numerical accuracy) the same
results as the original PAM. For further improvements that can affect the
result, see also KMedoidsFastPAM, which is recommended for usage in practice.

###### Partioning Around Medoids

[KR87, KR90c] (since 0.5.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.KMedoidsPAM

The original Partitioning Around Medoids (PAM) algorithm or k-medoids
clustering, as proposed by Kaufman and Rousseeuw in "Clustering by means of
Medoids".

###### K Medoids PAM Reynolds

[RRdlIRS06] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.KMedoidsPAMReynolds

The Partitioning Around Medoids (PAM) algorithm with some additional
optimizations proposed by Reynolds et al.

In our implementation, we could not observe a substantial improvement over the
original PAM algorithm. This may be because of modern CPU architectures, where
saving an addition may be neglibile compared to caching and pipelining.

###### K Medoids Park

[RRdlIRS06, PJ09] (since 0.5.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.KMedoidsPark

A k-medoids clustering algorithm, implemented as EM-style bulk algorithm.

In contrast to PAM, which will in each iteration update one medoid with one
(arbitrary) non-medoid, this implementation follows the EM pattern. In the
expectation step, the best medoid from the cluster members is chosen; in the
M-step, the objects are reassigned to their nearest medoid.

This implementation evolved naturally from EM and k-means algorithms, but
apparently a similar approach was published by Park and Jun, and also Reynolds
et al. discussed this kind of approach before as a side note.

In our experiments, it tends to be much faster than PAM, but also find less
good solutions, as the medoids are only chosen from the cluster members. This
aligns with findings of Reynolds et al. and can be explained with the
requirement of the new medoid to cover the entire cluster.

###### Single Assignment K Means

(since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.SingleAssignmentKMeans

Pseudo-k-Means variations, that assigns each object to the nearest center.

###### X Means

[PM00] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.XMeans

X-means: Extending K-means with Efficient Estimation on the Number of
Clusters.

Note: this implementation does currently not use a k-d-tree for acceleration.
Also note that kmax is not a hard threshold - the algorithm can return up to
2*kmax clusters!

######  C.7.1 Kmeans Initialization

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.initialization package:

Initialization strategies for k-means.

###### Farthest Points Initial Means

(since 0.6.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.initialization.FarthestPointsInitialMeans

K-Means initialization by repeatedly choosing the farthest point (by the
minimum distance to earlier points).

Note: this is less random than other initializations, so running multiple
times will be more likely to return the same local minima.

###### Farthest Sum Points Initial Means

(since 0.6.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.initialization.FarthestSumPointsInitialMeans

K-Means initialization by repeatedly choosing the farthest point (by the sum
of distances to previous objects).

Note: this is less random than other initializations, so running multiple
times will be more likely to return the same local minima.

###### First K Initial Means

[Mac67] (since 0.5.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.initialization.FirstKInitialMeans

Initialize K-means by using the first k objects as initial means.

###### K Means Plus Plus Initial Means

[AV07] (since 0.5.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.initialization.KMeansPlusPlusInitialMeans

K-Means++ initialization for k-means.

###### LAB Initial Means

[SR18] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.initialization.LABInitialMeans

Linear approximative BUILD (LAB) initialization for FastPAM (and k-means).

This is a O(nk) aproximation of the original PAM BUILD. For performance, it
uses an O(sqrt(n)) sample to achieve linear run time. The results will be
worse than those of BUILD, but provide a good starting point for FastPAM
optimization.

###### Ostrovsky Initial Means

[ORSS06, ORSS12] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.initialization.OstrovskyInitialMeans

Ostrovsky initial means, a variant of k-means++ that is expected to give
slightly better results on average, but only works for k-means and not for,
e.g., PAM (k-medoids).

###### PAM Initial Means

[KR87, KR90c] (since 0.5.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.initialization.PAMInitialMeans

PAM initialization for k-means (and of course, for PAM).

###### Park Initial Means

[PJ09] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.initialization.ParkInitialMeans

Initialization method proposed by Park and Jun.

It is easy to imagine that this approach can become problematic, because it
does not take the distances between medoids into account. In the worst case,
it may choose k duplicates as initial centers, therefore we cannot recommend
this strategy, but it is provided for completeness.

###### Predefined Initial Means

(since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.initialization.PredefinedInitialMeans

Run k-means with prespecified initial means.

###### Random Normal Generated Initial Means

[Jan66] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.initialization.RandomNormalGeneratedInitialMeans

Initialize k-means by generating random vectors (normal distributed with
$N(\mu,\sigma)$ in each dimension).

This is a different interpretation of the work of Jancey, who wrote little
more details but "introduced into known but arbitrary positions"; but
seemingly worked with standardized scores. In contrast to
RandomUniformGeneratedInitialMeans (which uses a uniform on the entire value
range), this class uses a normal distribution based on the estimated
parameters. The resulting means should be more central, and thus a bit less
likely to become empty (at least if you assume there is no correlation amongst
attributes… it is still not competitive with better methods).

Warning: this still tends to produce empty clusters in many situations, and is
one of the least effective initialization strategies, not recommended for use.

###### Random Uniform Generated Initial Means

[Jan66] (since 0.5.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.initialization.RandomUniformGeneratedInitialMeans

Initialize k-means by generating random vectors (uniform, within the value
range of the data set).

This is attributed to Jancey, but who wrote little more details but
"introduced into known but arbitrary positions". This class assumes this
refers to uniform positions within the value domain. For a normal distributed
variant, see RandomNormalGeneratedInitialMeans.

Warning: this tends to produce empty clusters, and is one of the least
effective initialization strategies, not recommended for use.

###### Randomly Chosen Initial Means

[For65, McR71, And73b] (since 0.5.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.initialization.RandomlyChosenInitialMeans

Initialize K-means by randomly choosing k existing elements as initial cluster
centers.

###### Sample K Means Initialization

[BF98] (since 0.6.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.initialization.SampleKMeansInitialization

Initialize k-means by running k-means on a sample of the data set only.

######  C.7.2 Kmeans Parallel

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.parallel package:

Parallelized implementations of k-means.

###### Parallel Lloyd K Means

(since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.parallel.ParallelLloydKMeans

Parallel implementation of k-Means clustering.

######  C.7.3 Kmeans Quality

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.quality package:

Quality measures for k-Means results.

###### Abstract K Means Quality Measure

[PM00, ZXF08] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.quality.AbstractKMeansQualityMeasure

Base class for evaluating clusterings by information criteria (such as AIC or
BIC). Provides helper functions (e.g. max likelihood calculation) to its
subclasses.

###### Akaike Information Criterion

[PM00, Aka73] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.quality.AkaikeInformationCriterion

Akaike Information Criterion (AIC).

###### Bayesian Information Criterion

[Sch78] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.quality.BayesianInformationCriterion

Bayesian Information Criterion (BIC), also known as Schwarz criterion (SBC,
SBIC) for the use with evaluating k-means results.

###### Bayesian Information Criterion Zhao

[ZXF08] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.quality.BayesianInformationCriterionZhao

Different version of the BIC criterion.

###### Within Cluster Mean Distance Quality Measure

(since 0.6.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.quality.WithinClusterMeanDistanceQualityMeasure

Class for computing the average overall distance.

The average of all average pairwise distances in a cluster.

###### Within Cluster Variance Quality Measure

(since 0.6.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.quality.WithinClusterVarianceQualityMeasure

Class for computing the variance in a clustering result (sum-of-squares).

#####  C.8 Meta

de.lmu.ifi.dbs.elki.algorithm.clustering.meta package:

Meta clustering algorithms, that get their result from other clusterings or
external sources.

###### External Clustering

(since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.meta.ExternalClustering

Read an external clustering result from a file, such as produced by
ClusteringVectorDumper.

The input format of this parser is text-based:

# Optional comment1 1 1 2 2 2 -1 Example labelWhere non-negative numbers are
cluster assignments, negative numbers are considered noise clusters.

#####  C.9 Onedimensional

de.lmu.ifi.dbs.elki.algorithm.clustering.onedimensional package:

Clustering algorithms for one-dimensional data.

###### KNN Kernel Density Minima Clustering

(since 0.6.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.onedimensional.KNNKernelDensityMinimaClustering

Cluster one-dimensional data by splitting the data set on local minima after
performing kernel density estimation.

#####  C.10 Optics

de.lmu.ifi.dbs.elki.algorithm.clustering.optics package:

OPTICS family of clustering algorithms.

Note that some OPTICS based algorithms (HiCO, DiSH) are in the subspace and
correlation packages, which better describes their use case.

###### Abstract OPTICS

[ABKS99] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.optics.AbstractOPTICS

The OPTICS algorithm for density-based hierarchical clustering.

This is the abstract base class, providing the shared parameters only.

###### DeliClu: Density-Based Hierarchical Clustering

[ABK06c] (since 0.1)

de.lmu.ifi.dbs.elki.algorithm.clustering.optics.DeLiClu

DeliClu: Density-Based Hierarchical Clustering

A hierarchical algorithm to find density-connected sets in a database, closely
related to OPTICS but exploiting the structure of a R-tree for acceleration.

###### Fast OPTICS

[SV13] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.optics.FastOPTICS

FastOPTICS algorithm (Fast approximation of OPTICS)

Note that this is not FOPTICS as in "Fuzzy OPTICS"!

###### OPTICS: Density-Based Hierarchical Clustering (implementation using a
heap)

[ABKS99] (since 0.1)

de.lmu.ifi.dbs.elki.algorithm.clustering.optics.OPTICSHeap

The OPTICS algorithm for density-based hierarchical clustering.

Algorithm to find density-connected sets in a database based on the parameters
’minPts’ and ’epsilon’ (specifying a volume). These two parameters determine a
density threshold for clustering.

This implementation uses a heap.

###### OPTICS: Density-Based Hierarchical Clustering (implementation using a
list)

[ABKS99] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.optics.OPTICSList

The OPTICS algorithm for density-based hierarchical clustering.

Algorithm to find density-connected sets in a database based on the parameters
’minPts’ and ’epsilon’ (specifying a volume). These two parameters determine a
density threshold for clustering.

This version is implemented using a list, always scanning the list for the
maximum. While this could be cheaper than the complex heap updates, benchmarks
indicate the heap version is usually still preferable.

###### OPTICS Xi Cluster Extraction

[ABKS99, SG18a] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.optics.OPTICSXi

Extract clusters from OPTICS Plots using the original Xi extraction.

Note: this implementation includes an additional filter step that prunes
elements from a steep up area that don’t have the predecessor in the cluster.
This removes a popular type of artifacts.

#####  C.11 Subspace

de.lmu.ifi.dbs.elki.algorithm.clustering.subspace package:

Axis-parallel subspace clustering algorithms

The clustering algorithms in this package are instances of both, projected
clustering algorithms or subspace clustering algorithms according to the
classical but somewhat obsolete classification schema of clustering algorithms
for axis-parallel subspaces.

###### CLIQUE: Automatic Subspace Clustering of High Dimensional Data for Data
Mining Applications

[AGGR98] (since 0.1)

de.lmu.ifi.dbs.elki.algorithm.clustering.subspace.CLIQUE

Implementation of the CLIQUE algorithm, a grid-based algorithm to identify
dense clusters in subspaces of maximum dimensionality.

The implementation consists of two steps:
1\. Identification of subspaces that contain clusters
2\. Identification of clusters

The third step of the original algorithm (Generation of minimal description
for the clusters) is not (yet) implemented.

Note: this is fairly old code, and not well optimized. Do not use this for
runtime benchmarking!

###### DOC: Density-based Optimal projective Clustering

[PJAM02] (since 0.6.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.subspace.DOC

DOC is a sampling based subspace clustering algorithm.

###### DiSH: Detecting Subspace cluster Hierarchies

[ABK+07a] (since 0.1)

de.lmu.ifi.dbs.elki.algorithm.clustering.subspace.DiSH

Algorithm for detecting subspace hierarchies.

###### FastDOC: Density-based Optimal projective Clustering

[PJAM02] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.clustering.subspace.FastDOC

The heuristic variant of the DOC algorithm, FastDOC

###### Finding Hierarchies of Subspace Clusters

[ABK+06a] (since 0.1)

de.lmu.ifi.dbs.elki.algorithm.clustering.subspace.HiSC

Implementation of the HiSC algorithm, an algorithm for detecting hierarchies
of subspace clusters.

###### P3C: A Robust Projected Clustering Algorithm.

[MSE06] (since 0.6.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.subspace.P3C

P3C: A Robust Projected Clustering Algorithm.

###### PROCLUS: PROjected CLUStering

[AWY+99] (since 0.1)

de.lmu.ifi.dbs.elki.algorithm.clustering.subspace.PROCLUS

The PROCLUS algorithm, an algorithm to find subspace clusters in high
dimensional spaces.

###### PreDeCon: Subspace Preference weighted Density Connected Clustering

[BKKK04] (since 0.1)

de.lmu.ifi.dbs.elki.algorithm.clustering.subspace.PreDeCon

PreDeCon computes clusters of subspace preference weighted connected points.
The algorithm searches for local subgroups of a set of feature vectors having
a low variance along one or more (but not all) attributes.

###### SUBCLU: Density connected Subspace Clustering

[KKK04] (since 0.3)

de.lmu.ifi.dbs.elki.algorithm.clustering.subspace.SUBCLU

Implementation of the SUBCLU algorithm, an algorithm to detect arbitrarily
shaped and positioned clusters in subspaces. SUBCLU delivers for each subspace
the same clusters DBSCAN would have found, when applied to this subspace
separately.

#####  C.12 Uncertain

de.lmu.ifi.dbs.elki.algorithm.clustering.uncertain package:

Clustering algorithms for uncertain data.

###### CK Means

[LKC07] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.uncertain.CKMeans

Run k-means on the centers of each uncertain object.

This is a baseline reference method, that computes the center of mass
(centroid) of each object, then runs k-means on this.

###### Center Of Mass Meta Clustering

[SKE+15] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.uncertain.CenterOfMassMetaClustering

Center-of-mass meta clustering reduces uncertain objects to their center of
mass, then runs a vector-oriented clustering algorithm on this data set.

###### FDBSCAN: Density-based Clustering of Applications with Noise on fuzzy
objects

[KP05] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.uncertain.FDBSCAN

FDBSCAN is an adaption of DBSCAN for fuzzy (uncertain) objects.

This implementation is based on GeneralizedDBSCAN. All implementation of
FDBSCAN functionality is located in the neighbor predicate
FDBSCANNeighborPredicate.

###### FDBSCAN Neighbor Predicate

[KP05] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.uncertain.FDBSCANNeighborPredicate

Density-based Clustering of Applications with Noise and Fuzzy objects
(FDBSCAN) is an Algorithm to find sets in a fuzzy database that are density-
connected with minimum probability.

###### Representative Uncertain Clustering

[ZES+14] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.uncertain.RepresentativeUncertainClustering

Representative clustering of uncertain data.

This algorithm clusters uncertain data by repeatedly sampling a possible
world, then running a traditional clustering algorithm on this sample.

The resulting "possible" clusterings are then clustered themselves, using a
clustering similarity measure. This yields a number of representatives for the
set of all possible worlds.

###### UK Means

[CCKN06] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.clustering.uncertain.UKMeans

Uncertain K-Means clustering, using the average deviation from the center.

Note: this method is, essentially, superficial. It was shown to be equivalent
to doing regular K-means on the object centroids instead (see CKMeans for the
reference and an implementation). This is only for completeness.

###  Appendix D Itemsetmining

de.lmu.ifi.dbs.elki.algorithm.itemsetmining package:

Algorithms for frequent itemset mining such as APRIORI.

###### APRIORI: Algorithm for Mining Association Rules

[AS94] (since 0.1)

de.lmu.ifi.dbs.elki.algorithm.itemsetmining.APRIORI

The APRIORI algorithm for Mining Association Rules.

###### Eclat

[ZPOL97] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.itemsetmining.Eclat

Eclat is a depth-first discovery algorithm for mining frequent itemsets.

Eclat discovers frequent itemsets by first transforming the data into a
(sparse) column-oriented form, then performing a depth-first traversal of the
prefix lattice, stopping traversal when the minimum support is no longer
satisfied.

This implementation is the basic algorithm only, and does not use diffsets.
Columns are represented using a sparse representation, which theoretically is
beneficial when the density is less than 1/31. This corresponds roughly to a
minimum support of 3% for 1-itemsets. When searching for itemsets with a
larger minimum support, it may be desirable to use a dense bitset
representation instead and/or implement an automatic switching technique!

Performance of this implementation is probably surpassed with a low-level C
implementation based on SIMD bitset operations as long as support of an
itemset is high, which are not easily accessible in Java.

###### FP Growth

[HPY00] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.itemsetmining.FPGrowth

FP-Growth is an algorithm for mining the frequent itemsets by using a
compressed representation of the database called FPGrowth.FPTree.

FP-Growth first sorts items by the overall frequency, since having high
frequent items appear first in the tree leads to a much smaller tree since
frequent subsets will likely share the same path in the tree. FP-Growth is
beneficial when you have a lot of (near-) duplicate transactions, and are
using a not too high support threshold, as it only prunes single items, not
item combinations.

This implementation is in-memory only, and has not yet been carefully
optimized.

The worst case memory use probably is $O(\min(n\cdot l,i^{l}))$ where i is the
number of items, l the average itemset length, and n the number of items. The
worst case scenario is when every item is frequent, and every transaction is
unique. The resulting tree will then be larger than the original data.

#####  D.1 Associationrules

de.lmu.ifi.dbs.elki.algorithm.itemsetmining.associationrules package:

Association rule mining.

###### Association Rule Generation

[ZJ14] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.itemsetmining.associationrules.AssociationRuleGeneration

Association rule generation from frequent itemsets

This algorithm calls a specified frequent itemset algorithm and calculates all
association rules, having a interest value between then the specified
boundaries form the obtained frequent itemsets

######  D.1.1 Associationrules Interest

de.lmu.ifi.dbs.elki.algorithm.itemsetmining.associationrules.interest package:

Association rule interestingness measures.

Much of the confusion with these measures arises from the anti-monotonicity of
itemsets, which are omnipresent in the literature.

In the itemset notation, the itemset $X$ denotes the set of matching
transactions $\\{T|X\subseteq T\\}$ that contain the itemset $X$. If we
enlarge $Z=X\cup Y$, the resulting set shrinks: $\\{T|Z\subseteq
T\\}=\\{T|X\subseteq T\\}\cap\\{T|Y\subseteq T\\}$.

Because of this: $\text{support}(X\cup Y)=P(X\cap Y)$ and
$\text{support}(X\cap Y)=P(X\cup Y)$. With "support" and "confidence", it is
common to see the reversed semantics (the union on the constraints is the
intersection on the matches, and conversely); with probabilities it is common
to use "events" as in frequentist inference.

To make things worse, the "support" is sometimes in absolute (integer) counts,
and sometimes used in a relative share.

###### Added Value

[SM99] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.itemsetmining.associationrules.interest.AddedValue

Added value (AV) interestingness measure: $\text{confidence}(X\rightarrow
Y)-\text{support}(Y)=P(Y|X)-P(Y)$.

###### Certainty Factor

[GBSM02] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.itemsetmining.associationrules.interest.CertaintyFactor

Certainty factor (CF; Loevinger) interestingness measure.
$\tfrac{\text{confidence}(X\rightarrow
Y)-\text{support}(Y)}{\text{support}(\neg Y)}$.

###### Confidence

[AIS93] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.itemsetmining.associationrules.interest.Confidence

Confidence interestingness measure, $\tfrac{\text{support}(X\cup
Y)}{\text{support}(X)}=\tfrac{P(X\cap Y)}{P(X)}=P(Y|X)$.

###### Conviction

[BMUT97] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.itemsetmining.associationrules.interest.Conviction

Conviction interestingness measure: $\frac{P(X)P(\neg Y)}{P(X\cap\neg Y)}$.

###### Cosine

[TK00] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.itemsetmining.associationrules.interest.Cosine

Cosine interestingness measure, $\tfrac{\text{support}(A\cup
B)}{\sqrt{\text{support}(A)\text{support}(B)}}=\tfrac{P(A\cap
B)}{\sqrt{P(A)P(B)}}$.

The interestingness measure called IS by Tan and Kumar.

###### Gini Index

[TK00, BFOS84] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.itemsetmining.associationrules.interest.GiniIndex

Gini-index based interestingness measure, using the weighted squared
conditional probabilities compared to the non-conditional priors.

$P(X)\left(P(Y|X)^{2}+P(\neg Y|X)^{2}\right)+P(\neg X)\left(P(Y|\neg
X)^{2}+P(\neg Y|\neg X)^{2}\right)-P(Y)^{2}-P(\neg Y)^{2}$

###### J Measure

[SG91] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.itemsetmining.associationrules.interest.JMeasure

J-Measure interestingness measure. $P(X\cap
Y)\log\tfrac{P(Y|X)}{P(Y)}+P(X\cap\neg Y)\log\tfrac{P(\neg Y|X)}{P(\neg Y)}$.

###### Jaccard

[vR79, TKS04] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.itemsetmining.associationrules.interest.Jaccard

Jaccard interestingness measure:

$\tfrac{\text{support}(A\cup B)}{\text{support}(A\cap B)}=\tfrac{P(A\cap
B)}{P(A)+P(B)-P(A\cap B)}=\tfrac{P(A\cap B)}{P(A\cup B)}$

###### Klosgen

[Klö96] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.itemsetmining.associationrules.interest.Klosgen

Klösgen interestingness measure.

$\sqrt{\text{support}(X\cup Y)}\left(\text{confidence}(X\rightarrow
Y)-\text{support}(Y)\right)=\sqrt{P(X\cap Y)}\left(P(Y|X)-P(Y)\right)$

###### Leverage

[PS91] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.itemsetmining.associationrules.interest.Leverage

Leverage interestingness measure.

$\text{support}(X\Rightarrow Y)-\text{support}(X)\text{support}(Y)=P(X\cap
Y)-P(X)P(Y)$

###### Lift

[BMS97] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.itemsetmining.associationrules.interest.Lift

Lift interestingness measure.

$\tfrac{\text{confidence}(X\rightarrow
Y)}{\text{support}(Y)}=\tfrac{\text{confidence}(Y\rightarrow
X)}{\text{support}(X)}=\tfrac{P(X\cap Y)}{P(X)P(Y)}$

###  Appendix E Outlier

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

Outlier detection algorithms

###### COP: Correlation Outlier Probability

[KKSZ12] (since 0.5.5)

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

Correlation outlier probability: Outlier Detection in Arbitrarily Oriented
Subspaces

###### DWOF: Dynamic Window Outlier Factor

[MMG13] (since 0.6.0)

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

Algorithm to compute dynamic-window outlier factors in a database based on a
specified parameter k, which specifies the number of the neighbors to be
considered during the calculation of the DWOF score.

###### Gaussian Model Outlier Detection

(since 0.3)

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

Outlier detection based on the probability density of the single normal
distribution.

###### Gaussian-Uniform Mixture Model Outlier Detection

[Esk00] (since 0.3)

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

Outlier detection algorithm using a mixture model approach. The data is
modeled as a mixture of two distributions, a Gaussian distribution for
ordinary data and a uniform distribution for outliers. At first all Objects
are in the set of normal objects and the set of anomalous objects is empty. An
iterative procedure then transfers objects from the ordinary set to the
anomalous set if the transfer increases the overall likelihood of the data.

###### OPTICS-OF: Identifying Local Outliers

[BKNS99] (since 0.3)

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

OPTICS-OF outlier detection algorithm, an algorithm to find Local Outliers in
a database based on ideas from OPTICSTypeAlgorithm clustering.

###### Simple COP: Correlation Outlier Probability

[Zim08] (since 0.5.5)

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

Algorithm to compute local correlation outlier probability.

This is the simpler, original version of COP, as published in

#####  E.1 Anglebased

de.lmu.ifi.dbs.elki.algorithm.outlier.anglebased package:

Angle-based outlier detection algorithms.

###### ABOD: Angle-Based Outlier Detection

[KSZ08] (since 0.2)

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

Angle-Based Outlier Detection / Angle-Based Outlier Factor.

Outlier detection using variance analysis on angles, especially for high
dimensional data sets. Exact version, which has cubic runtime (see also
FastABOD and LBABOD for faster versions).

###### Approximate ABOD: Angle-Based Outlier Detection

[KSZ08] (since 0.6.0)

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

Fast-ABOD (approximateABOF) version of Angle-Based Outlier Detection / Angle-
Based Outlier Factor.

Note: the minimum k is 3. The 2 nearest neighbors yields one 1 angle, which
implies a constant 0 variance everywhere.

###### LB-ABOD: Lower Bounded Angle-Based Outlier Detection

[KSZ08] (since 0.6.0)

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

LB-ABOD (lower-bound) version of Angle-Based Outlier Detection / Angle-Based
Outlier Factor.

Exact on the top k outliers, approximate on the remaining.

Outlier detection using variance analysis on angles, especially for high
dimensional data sets.

#####  E.2 Clustering

de.lmu.ifi.dbs.elki.algorithm.outlier.clustering package:

Clustering based outlier detection.

###### Discovering cluster-based local outliers

[HXD03] (since 0.7.5)

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

Cluster-based local outlier factor (CBLOF).

###### EM Outlier: Outlier Detection based on the generic EM clustering

(since 0.3)

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

Outlier detection algorithm using EM Clustering.

If an object does not belong to any cluster it is supposed to be an outlier.
If the probability for an object to belong to the most probable cluster is
still relatively low this object is an outlier.

###### K Means Outlier Detection

(since 0.7.0)

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

Outlier detection by using k-means clustering.

The scores are assigned by the objects distance to the nearest center.

We don’t have a clear reference for this approach, but it seems to be a best
practise in some areas to remove objects that have the largest distance from
their center. If you need to cite this approach, please cite the ELKI version
you used (use the ELKI publication list for citation information and BibTeX
templates).

###### Silhouette Outlier Detection

[Rou87] (since 0.7.0)

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

Outlier detection by using the Silhouette Coefficients.

Silhouette values are computed as by Rousseeuw and then used as outlier
scores. To cite this outlier detection approach, please cite the ELKI version
you used (use the ELKI publication list for citation information and BibTeX
templates).

#####  E.3 Distance

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

Distance-based outlier detection algorithms, such as DBOutlier and kNN.

For methods based on local density, see package
de.lmu.ifi.dbs.elki.algorithm.outlier.lof instead.

###### Abstract DB Outlier

[KN98] (since 0.3)

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

Simple distance based outlier detection algorithms.

###### DBOD: Distance Based Outlier Detection

[KN98] (since 0.3)

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

Simple distanced based outlier detection algorithm. User has to specify two
parameters An object is flagged as an outlier if at least a fraction p of all
data objects has a distance above d from c.

###### Distance Based Outlier Score

[KN98] (since 0.3)

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

Compute percentage of neighbors in the given neighborhood with size d.

Generalization of the DB Outlier Detection by using the fraction as outlier
score thus eliminating this parameter and turning the method into a ranking
method instead of a labelling one.

###### Fast Outlier Detection in High Dimensional Spaces

[AP02] (since 0.5.0)

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

Fast Outlier Detection in High Dimensional Spaces

Outlier Detection using Hilbert space filling curves

###### KNNDD: k-Nearest Neighbor Data Description

[dRTD98] (since 0.7.5)

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

Nearest Neighbor Data Description.

A variation inbetween of KNN outlier and LOF, comparing the nearest neighbor
distance of a point to the nearest neighbor distance of the nearest neighbor.

The initial description used k=1, where this equation makes most sense. For k
> 1, one may want to use averaging similar to LOF.

###### KNN outlier: Efficient Algorithms for Mining Outliers from Large Data
Sets

[RRS00] (since 0.3)

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

Outlier Detection based on the distance of an object to its k nearest
neighbor.

This implementation differs from the original pseudocode: the k nearest
neighbors do not exclude the point that is currently evaluated. I.e. for k=1
the resulting score is the distance to the 1-nearest neighbor that is not the
query point and therefore should match k=2 in the exact pseudocode - a value
of k=1 in the original code does not make sense, as the 1NN distance will be 0
for every point in the database. If you for any reason want to use the
original algorithm, subtract 1 from the k parameter.

###### KNNSOS: k-Nearest-Neighbor Stochastic Outlier Selection

[SG17, JHPvdH12] (since 0.7.5)

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

kNN-based adaption of Stochastic Outlier Selection.

This is a trivial variation of Stochastic Outlier Selection to benefit from
KNN indexes, but not discussed in the original publication. Instead of setting
perplexity, we choose the number of neighbors k, and set perplexity simply to
k/3. Objects outside of the kNN are not considered anymore.

###### KNNWeight outlier detection

[AP02] (since 0.3)

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

Outlier Detection based on the accumulated distances of a point to its k
nearest neighbors.

As in the original publication (as far as we could tell from the pseudocode
included), the current point is not included in the nearest neighbors (see
figures in the publication). This matches the intuition common in nearest
neighbor classification, where the evaluated instances are not part of the
training set; but it contrasts to the pseudocode of the kNN outlier method and
the database interpretation (which returns all objects stored in the
database).

Furthermore, we report the sum of the k distances (called "weight" in the
original publication). Other implementations may return the average distance
instead, and therefore yield different results.

###### Local Isolation Coefficient

[YSW09] (since 0.7.0)

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

The Local Isolation Coefficient is the sum of the kNN distance and the average
distance to its k nearest neighbors.

The algorithm originally used a normalized Manhattan distance on numerical
attributes, and Hamming distance on categorial attributes.

###### ODIN: Outlier Detection Using k-Nearest Neighbour Graph

[HKF04] (since 0.6.0)

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

Outlier detection based on the in-degree of the kNN graph.

This is a curried version: instead of using a threshold T to obtain a binary
decision, we use the computed value as outlier score; normalized by k to make
the numbers more comparable across different parameterizations.

###### An Efficient Reference-based Approach to Outlier Detection in Large
Datasets

[PZG06] (since 0.3)

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

Reference-Based Outlier Detection algorithm, an algorithm that computes kNN
distances approximately, using reference points.

kNN distances are approximated by the difference in distance from a reference
point. For this approximation to be of high quality, triangle inequality is
required; but the algorithm can also process non-metric distances.

###### SOS: Stochastic Outlier Selection

[SG17, JHPvdH12] (since 0.7.5)

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

Stochastic Outlier Selection.

######  E.3.1 Distance Parallel

de.lmu.ifi.dbs.elki.algorithm.outlier.distance.parallel package:

Parallel implementations of distance-based outlier detectors.

###### Parallel KNN Outlier

[SZK14b] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.outlier.distance.parallel.ParallelKNNOutlier

Parallel implementation of KNN Outlier detection.

###### Parallel KNN Weight Outlier

[SZK14b] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.outlier.distance.parallel.ParallelKNNWeightOutlier

Parallel implementation of KNN Weight Outlier detection.

#####  E.4 Intrinsic

de.lmu.ifi.dbs.elki.algorithm.outlier.intrinsic package:

Outlier detection algorithms based on intrinsic dimensionality.

###### IDOS: Intrinsic Dimensional Outlier Score

[vBHZ15] (since 0.7.0)

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

Intrinsic Dimensional Outlier Detection in High-Dimensional Data.

###### ISOS: Intrinsic Stochastic Outlier Selection

[SG17] (since 0.7.5)

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

Intrinsic Stochastic Outlier Selection.

###### Intrinsic Dimensionality Outlier

[HSZ18] (since 0.7.0)

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

Use intrinsic dimensionality for outlier detection.

#####  E.5 Lof

de.lmu.ifi.dbs.elki.algorithm.outlier.lof package:

LOF family of outlier detection algorithms.

###### Approximate LOCI: Fast Outlier Detection Using the Local Correlation
Integral

[PKGF03] (since 0.5.0)

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

Fast Outlier Detection Using the "approximate Local Correlation Integral".

Outlier detection using multiple epsilon neighborhoods.

###### COF: Connectivity-based Outlier Factor

[TCFC02] (since 0.7.0)

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

Connectivity-based Outlier Factor (COF).

###### FlexibleLOF: Local Outlier Factor with additional options

[BKNS00] (since 0.2)

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

Flexible variant of the "Local Outlier Factor" algorithm.

This implementation diverts from the original LOF publication in that it
allows the user to use a different distance function for the reachability
distance and neighborhood determination (although the default is to use the
same value.)

The k nearest neighbors are determined using the standard distance function,
while the reference set used in reachability distance computation is
configured using a separate reachability distance function.

The original LOF parameter was called "minPts". For consistency with the name
"kNN query", we chose to rename the parameter to k. Flexible LOF allows you to
set the two values different, which yields the parameters -lof.krefer and
-lof.kreach.

###### INFLO: Influenced Outlierness Factor

[JTHW06] (since 0.3)

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

Influence Outliers using Symmetric Relationship (INFLO) using two-way search,
is an outlier detection method based on LOF; but also using the reverse kNN.

###### KDEOS: Kernel Density Estimator Outlier Score

[SZK14a] (since 0.7.0)

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

Generalized Outlier Detection with Flexible Kernel Density Estimates.

This is an outlier detection inspired by LOF, but using kernel density
estimation (KDE) from statistics. Unfortunately, for higher dimensional data,
kernel density estimation itself becomes difficult. At this point, the
kdeos.idim parameter can become useful, which allows to either disable
dimensionality adjustment completely (0) or to set it to a lower
dimensionality than the data representation. This may sound like a hack at
first, but real data is often of lower intrinsic dimensionality, and embedded
into a higher data representation. Adjusting the kernel to account for the
representation seems to yield worse results than using a lower, intrinsic,
dimensionality.

If your data set has many duplicates, the kdeos.kernel.minbw parameter sets a
minimum kernel bandwidth, which may improve results in these cases, as it
prevents kernels from degenerating to single points.

###### LDF: Outlier Detection with Kernel Density Functions

[LLP07] (since 0.5.5)

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

Outlier Detection with Kernel Density Functions.

A variation of LOF which uses kernel density estimation, but in contrast to
SimpleKernelDensityLOF also uses the reachability concept of LOF.

###### LDOF: Local Distance-Based Outlier Factor

[ZHJ09] (since 0.3)

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

Computes the LDOF (Local Distance-Based Outlier Factor) for all objects of a
Database.

###### LOCI: Fast Outlier Detection Using the Local Correlation Integral

[PKGF03] (since 0.2)

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

Fast Outlier Detection Using the "Local Correlation Integral".

Exact implementation only, not aLOCI. See ALOCI.

Outlier detection using multiple epsilon neighborhoods.

This implementation has O(n3 log n) runtime complexity!

###### LOF: Local Outlier Factor

[BKNS00] (since 0.2)

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

Algorithm to compute density-based local outlier factors in a database based
on a specified parameter -lof.k.

The original LOF parameter was called "minPts", but for consistency within
ELKI we have renamed this parameter to "k".

Compatibility note: as of ELKI 0.7.0, we no longer include the query point,
for consistency with other methods.

###### LoOP: Local Outlier Probabilities

[KKSZ09a] (since 0.3)

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

LoOP: Local Outlier Probabilities

Distance/density based algorithm similar to LOF to detect outliers, but with
statistical methods to achieve better result stability.

###### Online LOF

(since 0.4.0)

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

Incremental version of the LOF Algorithm, supports insertions and removals.

###### Simple Kernel Density LOF

(since 0.5.5)

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

A simple variant of the LOF algorithm, which uses a simple kernel density
estimation instead of the local reachability density.

###### Simplified LOF

[SZK14b] (since 0.5.5)

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

A simplified version of the original LOF algorithm, which does not use the
reachability distance, yielding less stable results on inliers.

###### Variance Of Volume

[HS03] (since 0.7.0)

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

Variance of Volume for outlier detection.

The volume is estimated by the distance to the k-nearest neighbor, then the
variance of volume is computed.

Unfortunately, this approach needs an enormous numerical precision, and may
not work for high-dimensional, non-normalized data. We therefore divide each
volume by the average across the data set. This means values are even less
comparable across data sets, but this avoids some of the numerical problems of
this method.

######  E.5.1 Lof Parallel

de.lmu.ifi.dbs.elki.algorithm.outlier.lof.parallel package:

Parallelized variants of LOF.

This parallelization is based on the generalization of outlier detection
published in:

###### Parallel LOF

[SZK14b] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.outlier.lof.parallel.ParallelLOF

Parallel implementation of Local Outlier Factor using processors.

This parallelized implementation is based on the easy-to-parallelize
generalized pattern discussed in

Erich Schubert, Arthur Zimek, Hans-Peter Kriegel
Local Outlier Detection Reconsidered: a Generalized View on Locality with
Applications to Spatial, Video, and Network Outlier Detection
Data Mining and Knowledge Discovery 28(1)

###### Parallel Simplified LOF

[SZK14b] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.outlier.lof.parallel.ParallelSimplifiedLOF

Parallel implementation of Simplified-LOF Outlier detection using processors.

This parallelized implementation is based on the easy-to-parallelize
generalized pattern discussed in

Erich Schubert, Arthur Zimek, Hans-Peter Kriegel
Local Outlier Detection Reconsidered: a Generalized View on Locality with
Applications to Spatial, Video, and Network Outlier Detection
Data Mining and Knowledge Discovery 28(1)

#####  E.6 Meta

de.lmu.ifi.dbs.elki.algorithm.outlier.meta package:

Meta outlier detection algorithms: external scores, score rescaling.

###### External Double Outlier Score

(since 0.4.0)

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

External outlier detection scores, loading outlier scores from an external
file. This class is meant to be able to read the default output of ELKI, i.e.
one object per line, with the DBID specified as ID= and the outlier score
specified with an algorithm-specific prefix.

###### Feature Bagging for Outlier Detection

[LK05] (since 0.4.0)

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

A simple ensemble method called "Feature bagging" for outlier detection.

Since the proposed method is only sensible to run on multiple instances of the
same algorithm (due to incompatible score ranges), we do not allow using
arbitrary algorithms.

###### HiCS: High Contrast Subspaces for Density-Based Outlier Ranking

[KMB12] (since 0.5.0)

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

Algorithm to compute High Contrast Subspaces for Density-Based Outlier
Ranking.

###### Rescale Meta Outlier Algorithm

(since 0.4.0)

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

Scale another outlier score using the given scaling function.

###### Simple Outlier Ensemble

(since 0.5.5)

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

Simple outlier ensemble method.

#####  E.7 Spatial

de.lmu.ifi.dbs.elki.algorithm.outlier.spatial package:

Spatial outlier detection algorithms

###### GLS-Backward Search

[CLB10] (since 0.4.0)

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

GLS-Backward Search is a statistical approach to detecting spatial outliers.

Implementation note: this is just the most basic version of this algorithm.
The spatial relation must be two dimensional, the set of spatial basis
functions is hard-coded (but trivial to enhance) to
$\\{1,x,y,x^{2},y^{2},xy\\}$, and we assume the neighborhood is large enough
for the simpler formulas to work that make the optimization problem convex.

###### CTLu Mean Multiple Attributes

[LCK03b] (since 0.4.0)

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

Mean Approach is used to discover spatial outliers with multiple attributes.

###### Median Algorithm for Spatial Outlier Detection

[LCK03a] (since 0.4.0)

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

Median Algorithm of C.-T. Lu

###### CTLu Median Multiple Attributes

[LCK03b] (since 0.4.0)

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

Median Approach is used to discover spatial outliers with multiple attributes.

###### Moran Scatterplot Outlier

[SLZ03] (since 0.4.0)

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

Moran scatterplot outliers, based on the standardized deviation from the local
and global means. In contrast to the definition given in the reference, we use
this as a ranking outlier detection by not applying the signedness test, but
by using the score (- localZ) * (Average localZ of Neighborhood) directly.
This allows us to differentiate a bit between stronger and weaker outliers.

###### Random Walk on Exhaustive Combination

[LLC10] (since 0.4.0)

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

Spatial outlier detection based on random walks.

Note: this method can only handle one-dimensional data, but could probably be
easily extended to higher dimensional data by using an distance function
instead of the absolute difference.

###### Scatterplot Spatial Outlier

[SLZ03] (since 0.4.0)

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

Scatterplot-outlier is a spatial outlier detection method that performs a
linear regression of object attributes and their neighbors average value.

###### Z-Test Outlier Detection

[SLZ03] (since 0.4.0)

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

Detect outliers by comparing their attribute value to the mean and standard
deviation of their neighborhood.

###### SLOM: a new measure for local spatial outliers

[CS06] (since 0.4.0)

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

SLOM: a new measure for local spatial outliers

###### Spatial Outlier Factor

[HQ04] (since 0.4.0)

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

The Spatial Outlier Factor (SOF) is a spatial LOF variation.

Since the "reachability distance" of LOF cannot be used canonically in the
bichromatic case, this part of LOF is dropped and the exact distance is used
instead.

###### A Trimmed Mean Approach to Finding Spatial Outliers

[HS04] (since 0.4.0)

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

A Trimmed Mean Approach to Finding Spatial Outliers.

Outliers are defined by their value deviation from a trimmed mean of the
neighbors.

######  E.7.1 Spatial Neighborhood

de.lmu.ifi.dbs.elki.algorithm.outlier.spatial.neighborhood package:

Spatial outlier neighborhood classes

###### Extended Neighborhood

(since 0.4.0)

de.lmu.ifi.dbs.elki.algorithm.outlier.spatial.neighborhood.ExtendedNeighborhood

Neighborhood obtained by computing the k-fold closure of an existing
neighborhood.

###### External Neighborhood

(since 0.4.0)

de.lmu.ifi.dbs.elki.algorithm.outlier.spatial.neighborhood.ExternalNeighborhood

A precomputed neighborhood, loaded from an external file.

###### Precomputed K Nearest Neighbor Neighborhood

(since 0.4.0)

de.lmu.ifi.dbs.elki.algorithm.outlier.spatial.neighborhood.PrecomputedKNearestNeighborNeighborhood

Neighborhoods based on k nearest neighbors.

#####  E.8 Subspace

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

Subspace outlier detection methods.

Methods that detect outliers in subspaces (projections) of the data set.

###### Abstract Aggarwal Yu Outlier

[AY01] (since 0.4.0)

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

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

###### EAFOD: the evolutionary outlier detection algorithm

[AY01] (since 0.4.0)

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

Evolutionary variant (EAFOD) of the high-dimensional outlier detection
algorithm by Aggarwal and Yu.

###### BruteForce: Outlier detection for high dimensional data

[AY01] (since 0.4.0)

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

BruteForce variant of the high-dimensional outlier detection algorithm by
Aggarwal and Yu.

The evolutionary approach is implemented as AggarwalYuEvolutionary

###### OUTRES

[MSS10] (since 0.5.0)

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

Adaptive outlierness for subspace outlier ranking (OUTRES).

Note: this algorithm seems to have a O(n³d!) complexity with no obvious way to
accelerate it with usual index structures for range queries: each object in
each tested subspace will need to know the mean and standard deviation of the
density of the neighbors, which in turn needs another range query; except if
we precomputed the densities for each of O(d!) possible subsets of dimensions.

###### OutRank: ranking outliers in high dimensional data

[MASS08] (since 0.5.0)

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

OutRank: ranking outliers in high dimensional data.

Algorithm to score outliers based on a subspace clustering result. This class
implements score 1 of the OutRank publication, which is a score based on
cluster sizes and cluster dimensionality.

###### SOD: Subspace outlier degree

[KKSZ09b] (since 0.2)

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

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

#####  E.9 Svm

de.lmu.ifi.dbs.elki.algorithm.outlier.svm package:

Support-Vector-Machines for outlier detection.

###### LibSVMOne Class Outlier Detection

[SPST+01] (since 0.7.0)

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

Outlier-detection using one-class support vector machines.

Important note: from literature, the one-class SVM is trained as if 0 was the
only counterexample. Outliers will only be detected when they are close to the
origin in kernel space! In our experience, results from this method are rather
mixed, in particular as you would likely need to tune hyperparameters. Results
may be better if you have a training data set with positive examples only,
then apply it only to new data (which is currently not supported in this
implementation, it assumes a single-dataset scenario).

###  Appendix F Projection

de.lmu.ifi.dbs.elki.algorithm.projection package:

Data projections (see also preprocessing filters for basic projections).

###### Barnes Hut TSNE

[vdM14] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.projection.BarnesHutTSNE

tSNE using Barnes-Hut-Approximation.

For larger data sets, use an index to make finding the nearest neighbors
faster, e.g. cover tree or k-d-tree.

###### Gaussian Affinity Matrix Builder

[HR02] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.projection.GaussianAffinityMatrixBuilder

Compute the affinity matrix for SNE and tSNE using a Gaussian distribution
with a constant sigma.

###### Intrinsic t-Stochastic Neighbor Embedding

[SG17] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.projection.IntrinsicNearestNeighborAffinityMatrixBuilder

Build sparse affinity matrix using the nearest neighbors only, adjusting for
intrinsic dimensionality. On data sets with high intrinsic dimensionality,
this can give better results.

Furthermore, this approach uses a different rule to combine affinities: rather
than taking the arithmetic average of $p_{ij}$ and $p_{ji}$, we use
$\sqrt{p_{ij}\cdot p_{ji}}$, which prevents outliers from attaching closely to
nearby clusters.

###### Nearest Neighbor Affinity Matrix Builder

[vdM14] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.projection.NearestNeighborAffinityMatrixBuilder

Build sparse affinity matrix using the nearest neighbors only.

###### Perplexity Affinity Matrix Builder

[HR02] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.projection.PerplexityAffinityMatrixBuilder

Compute the affinity matrix for SNE and tSNE.

###### SNE

[HR02] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.projection.SNE

Stochastic Neighbor Embedding is a projection technique designed for
visualization that tries to preserve the nearest neighbor structure.

###### t-SNE

[vdMH08] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.projection.TSNE

t-Stochastic Neighbor Embedding is a projection technique designed for
visualization that tries to preserve the nearest neighbor structure.

###  Appendix G Statistics

de.lmu.ifi.dbs.elki.algorithm.statistics package:

Statistical analysis algorithms.

The algorithms in this package perform statistical analysis of the data (e.g.
compute distributions, distance distributions etc.)

###### Add Single Scale

(since 0.5.0)

de.lmu.ifi.dbs.elki.algorithm.statistics.AddSingleScale

Pseudo "algorithm" that computes the global min/max for a relation across all
attributes.

###### Add Uniform Scale

(since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.statistics.AddUniformScale

Pseudo "algorithm" that computes the global min/max for a relation across all
attributes.

###### Average Precision At K

(since 0.5.0)

de.lmu.ifi.dbs.elki.algorithm.statistics.AveragePrecisionAtK

Evaluate a distance functions performance by computing the average precision
at k, when ranking the objects by distance.

###### Distance Quantile Sampler

(since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.statistics.DistanceQuantileSampler

Compute a quantile of a distance sample, useful for choosing parameters for
algorithms.

###### Distance Histogram

(since 0.2)

de.lmu.ifi.dbs.elki.algorithm.statistics.DistanceStatisticsWithClasses

Algorithm to gather statistics over the distance distribution in the data set.

###### Estimate Intrinsic Dimensionality

(since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.statistics.EstimateIntrinsicDimensionality

Estimate global average intrinsic dimensionality of a data set.

Note: this algorithm does not produce a result, but only logs statistics.

###### Evaluate Ranking Quality

(since 0.2)

de.lmu.ifi.dbs.elki.algorithm.statistics.EvaluateRankingQuality

Evaluate a distance function with respect to kNN queries. For each point, the
neighbors are sorted by distance, then the ROC AUC is computed. A score of 1
means that the distance function provides a perfect ordering of relevant
neighbors first, then irrelevant neighbors. A value of 0.5 can be obtained by
random sorting. A value of 0 means the distance function is inverted, i.e. a
similarity.

In contrast to RankingQualityHistogram, this method uses a binning based on
the centrality of objects. This allows analyzing whether or not a particular
distance degrades for the outer parts of a cluster.

###### Evaluate Retrieval Performance

(since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.statistics.EvaluateRetrievalPerformance

Evaluate a distance functions performance by computing the mean average
precision, ROC, and NN classification performance when ranking the objects by
distance.

###### Hopkins Statistic Clustering Tendency

[HS54] (since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.statistics.HopkinsStatisticClusteringTendency

The Hopkins Statistic of Clustering Tendency measures the probability that a
data set is generated by a uniform data distribution.

The statistic compares the ratio of the 1NN distance for objects from the data
set compared to the 1NN distances of uniform distributed objects.

###### Range Query Selectivity

(since 0.7.0)

de.lmu.ifi.dbs.elki.algorithm.statistics.RangeQuerySelectivity

Evaluate the range query selectivity.

###### Ranking Quality Histogram

(since 0.2)

de.lmu.ifi.dbs.elki.algorithm.statistics.RankingQualityHistogram

Evaluate a distance function with respect to kNN queries. For each point, the
neighbors are sorted by distance, then the ROC AUC is computed. A score of 1
means that the distance function provides a perfect ordering of relevant
neighbors first, then irrelevant neighbors. A value of 0.5 can be obtained by
random sorting. A value of 0 means the distance function is inverted, i.e. a
similarity.

###  Appendix H Timeseries

de.lmu.ifi.dbs.elki.algorithm.timeseries package:

###### Off-line Change Point Detection

[Pag57, BN93, Pic85] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.timeseries.OfflineChangePointDetectionAlgorithm

Off-line change point detection algorithm detecting a change in mean, based on
the cumulative sum (CUSUM), same-variance assumption, and using bootstrap
sampling for significance estimation.

###### Signi-Trend: scalable detection of emerging topics in textual streams
by hashed significance thresholds

[SWK14] (since 0.7.5)

de.lmu.ifi.dbs.elki.algorithm.timeseries.SigniTrendChangeDetection

Signi-Trend detection algorithm applies to a single time-series.

This is not a complete implementation of the method, but a modified (two-
sided) version of the significance score use in Signi-Trend for change
detection. The hashing and scalability parts of Signi-Trend are not applicable
here.

This implementation currently does not use timestamps, and thus only works for
fixed-interval measurements. It could be extended to allow dynamic data
windows by adjusting the alpha parameter based on time deltas.

###  Chapter Application

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

Base classes for stand alone applications.

###### Abstract Application

[SKE+15] (since 0.2)

de.lmu.ifi.dbs.elki.application.AbstractApplication

AbstractApplication sets the values for flags verbose and help.

Any Wrapper class that makes use of these flags may extend this class. Beware
to make correct use of parameter settings via optionHandler as commented with
constructor and methods.

###### Classifier Holdout Evaluation Task

(since 0.7.0)

de.lmu.ifi.dbs.elki.application.ClassifierHoldoutEvaluationTask

Evaluate a classifier.

###### Convert To Bundle Application

(since 0.5.5)

de.lmu.ifi.dbs.elki.application.ConvertToBundleApplication

Convert an input file to the more efficient ELKI bundle format.

###### Generator XML Spec

(since 0.2)

de.lmu.ifi.dbs.elki.application.GeneratorXMLSpec

Generate a data set based on a specified model (using an XML specification)

###### KDDCLI Application

(since 0.3)

de.lmu.ifi.dbs.elki.application.KDDCLIApplication

Basic command line application for Knowledge Discovery in Databases use cases.
It allows running unsupervised Algorithms to run on any DatabaseConnection.

###  Appendix I Cache

de.lmu.ifi.dbs.elki.application.cache package:

Utility applications for the persistence layer such as distance cache
builders.

CacheDoubleDistanceInOnDiskMatrix and CacheFloatDistanceInOnDiskMatrix are
conversion utilities that materialize an arbitrary distance into a binary
distance cache on the harddisk (using OnDiskUpperTriangleMatrix)

###### Cache Double Distance In On Disk Matrix

(since 0.2)

de.lmu.ifi.dbs.elki.application.cache.CacheDoubleDistanceInOnDiskMatrix

Precompute an on-disk distance matrix, using double precision.

###### Cache Double Distance KNN Lists

(since 0.6.0)

de.lmu.ifi.dbs.elki.application.cache.CacheDoubleDistanceKNNLists

Precompute the k nearest neighbors in a disk cache.

###### Cache Double Distance Range Queries

(since 0.6.0)

de.lmu.ifi.dbs.elki.application.cache.CacheDoubleDistanceRangeQueries

Precompute the k nearest neighbors in a disk cache.

###### Cache Float Distance In On Disk Matrix

(since 0.2)

de.lmu.ifi.dbs.elki.application.cache.CacheFloatDistanceInOnDiskMatrix

Precompute an on-disk distance matrix, using float precision.

###### Precompute Distances Ascii Application

(since 0.2)

de.lmu.ifi.dbs.elki.application.cache.PrecomputeDistancesAsciiApplication

Application to precompute pairwise distances into an ascii file.

IDs in the output file will always begin at 0.

The result can then be used with the DoubleDistanceParse.

Symmetry is assumed.

###  Appendix J Experiments

de.lmu.ifi.dbs.elki.application.experiments package:

Packaged experiments to make them easy to reproduce.

###### Evaluate Intrinsic Dimensionality Estimators

(since 0.7.0)

de.lmu.ifi.dbs.elki.application.experiments.EvaluateIntrinsicDimensionalityEstimators

Class for testing the estimation quality of intrinsic dimensionality
estimators.

###### Visualize Geodesic Distances

[SZK13] (since 0.5.5)

de.lmu.ifi.dbs.elki.application.experiments.VisualizeGeodesicDistances

Visualization function for Cross-track, Along-track, and minimum distance
function.

###  Appendix K Greedyensemble

de.lmu.ifi.dbs.elki.application.greedyensemble package:

Greedy ensembles for outlier detection.

This package contains code used for the greedy ensemble experiment in Erich
Schubert, Remigius Wojdanowski, Arthur Zimek, Hans-Peter Kriegel
On Evaluation of Outlier Rankings and Outlier Scores
Proc. 12th SIAM Int. Conf. on Data Mining (SDM 2012)

###### Compute KNN Outlier Scores

[SWZK12] (since 0.5.0)

de.lmu.ifi.dbs.elki.application.greedyensemble.ComputeKNNOutlierScores

Application that runs a series of kNN-based algorithms on a data set, for
building an ensemble in a second step. The output file consists of a label and
one score value for each object.

Since some algorithms can be too slow to run on large data sets and for large
values of k, they can be disabled. For example -disable
’(LDOF|DWOF|COF|FastABOD)’ disables these two methods completely.
Alternatively, you can use the parameter -ksquaremax to control the maximum k
for these four methods separately.

For methods where k=1 does not make sense, this value will be skipped, and the
procedure will commence at 1+stepsize.

###### Evaluate Precomputed Outlier Scores

(since 0.7.0)

de.lmu.ifi.dbs.elki.application.greedyensemble.EvaluatePrecomputedOutlierScores

Class to load an outlier detection summary file, as produced by
ComputeKNNOutlierScores, and compute popular evaluation metrics for it.

File format description:

  * •

Each column is one object in the data set

  * •

Each line is a different algorithm

  * •

There is a mandatory label column, containing the method name

  * •

The first line must contain the ground-truth, titled bylabel, where 0
indicates an inlier and 1 indicates an outlier

The evaluation assumes that high scores correspond to outliers, unless the
method name matches the pattern given using -reversed. The default value
matches several scores known to use reversed values.

###### Greedy Ensemble Experiment

[SWZK12] (since 0.5.0)

de.lmu.ifi.dbs.elki.application.greedyensemble.GreedyEnsembleExperiment

Class to load an outlier detection summary file, as produced by
ComputeKNNOutlierScores, and compute a naive ensemble for it. Based on this
initial estimation, and optimized ensemble is built using a greedy strategy.
Starting with the best candidate only as initial ensemble, the most diverse
candidate is investigated at each step. If it improves towards the (estimated)
target vector, it is added, otherwise it is discarded.

This approach is naive, and it may be surprising that it can improve results.
The reason is probably that diversity will result in a comparable ensemble,
while the reduced ensemble size is actually responsible for the improvements,
by being more decisive and less noisy due to dropping "unhelpful" members.

This still leaves quite a bit of room for improvement. If you build upon this
basic approach, please acknowledge our proof of concept work.

###### Visualize Pairwise Gain Matrix

[SWZK12] (since 0.5.0)

de.lmu.ifi.dbs.elki.application.greedyensemble.VisualizePairwiseGainMatrix

Class to load an outlier detection summary file, as produced by
ComputeKNNOutlierScores, and compute a matrix with the pairwise gains. It will
have one column / row obtained for each combination.

The gain is always computed in relation to the better of the two input
methods. Green colors indicate the result has improved, red indicate it became
worse.

###  Chapter Data

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

Basic classes for different data types, database object types and label types.

###### Hierarchical Class Label

(since 0.1)

de.lmu.ifi.dbs.elki.data.HierarchicalClassLabel

A HierarchicalClassLabel is a ClassLabel to reflect a hierarchical structure
of classes.

###### Simple Class Label

(since 0.1)

de.lmu.ifi.dbs.elki.data.SimpleClassLabel

A simple class label casting a String as it is as label.

###  Appendix L Projection

de.lmu.ifi.dbs.elki.data.projection package:

Data projections.

###### Feature Selection

(since 0.5.0)

de.lmu.ifi.dbs.elki.data.projection.FeatureSelection

Projection class for number vectors.

###### LatLngToECEF Projection

(since 0.6.0)

de.lmu.ifi.dbs.elki.data.projection.LatLngToECEFProjection

Project (Latitude, Longitude) vectors to (X, Y, Z), from spherical coordinates
to ECEF (earth-centered earth-fixed).

###### LngLatToECEF Projection

(since 0.6.0)

de.lmu.ifi.dbs.elki.data.projection.LngLatToECEFProjection

Project (Longitude, Latitude) vectors to (X, Y, Z), from spherical coordinates
to ECEF (earth-centered earth-fixed).

###### Numerical Feature Selection

(since 0.5.0)

de.lmu.ifi.dbs.elki.data.projection.NumericalFeatureSelection

Projection class for number vectors.

###### Random Projection

(since 0.6.0)

de.lmu.ifi.dbs.elki.data.projection.RandomProjection

Randomized projections of the data.

This class allows projecting the data with different types of random
projections, in particular database friendly projections (as suggested by
Achlioptas, see AchlioptasRandomProjectionFamily), but also as suggested for
locality sensitive hashing (LSH).

#####  L.1 Random

de.lmu.ifi.dbs.elki.data.projection.random package:

Random projection families.

###### Achlioptas Random Projection Family

[Ach01] (since 0.6.0)

de.lmu.ifi.dbs.elki.data.projection.random.AchlioptasRandomProjectionFamily

Random projections as suggested by Dimitris Achlioptas.

###### Cauchy Random Projection Family

[DIIM04] (since 0.6.0)

de.lmu.ifi.dbs.elki.data.projection.random.CauchyRandomProjectionFamily

Random projections using Cauchy distributions (1-stable).

###### Gaussian Random Projection Family

[DIIM04] (since 0.6.0)

de.lmu.ifi.dbs.elki.data.projection.random.GaussianRandomProjectionFamily

Random projections using Cauchy distributions (1-stable).

###### Random Subset Projection Family

[Bre96] (since 0.6.0)

de.lmu.ifi.dbs.elki.data.projection.random.RandomSubsetProjectionFamily

Random projection family based on selecting random features.

The basic idea of using this for data mining should probably be attributed to
L. Breiman, who used it to improve the performance of predictors in an
ensemble.

###### Simplified Random Hyperplane Projection Family

[Hen06] (since 0.7.0)

de.lmu.ifi.dbs.elki.data.projection.random.SimplifiedRandomHyperplaneProjectionFamily

Random hyperplane projection family.

###  Appendix M Uncertain

de.lmu.ifi.dbs.elki.data.uncertain package:

Uncertain data objects.

###### Unweighted Discrete Uncertain Object

[DRS09, BSHW06] (since 0.7.0)

de.lmu.ifi.dbs.elki.data.uncertain.UnweightedDiscreteUncertainObject

Unweighted implementation of discrete uncertain objects.

  * •

Every object is represented by a finite number of discrete samples.

  * •

Every sample has the same weight.

  * •

Every sample is equally likely to be returned by drawSample(java.util.Random).

###### Weighted Discrete Uncertain Object

[DRS09, BSHW06, BKR+09] (since 0.7.0)

de.lmu.ifi.dbs.elki.data.uncertain.WeightedDiscreteUncertainObject

Weighted version of discrete uncertain objects.

  * •

Every object is represented by a finite number of discrete samples.

  * •

Every sample has a weight associated with it.

  * •

Samples with higher weight are more likely to be returned by
drawSample(java.util.Random).

#####  M.1 Uncertainifier

de.lmu.ifi.dbs.elki.data.uncertain.uncertainifier package:

Classes to generate uncertain objects from existing certain data.

###### Simple Gaussian Uncertainifier

(since 0.7.0)

de.lmu.ifi.dbs.elki.data.uncertain.uncertainifier.SimpleGaussianUncertainifier

Vector factory

###### Uniform Uncertainifier

(since 0.7.0)

de.lmu.ifi.dbs.elki.data.uncertain.uncertainifier.UniformUncertainifier

Factory class.

###### Unweighted Discrete Uncertainifier

(since 0.7.0)

de.lmu.ifi.dbs.elki.data.uncertain.uncertainifier.UnweightedDiscreteUncertainifier

Class to generate unweighted discrete uncertain objects.

This is a second-order generator: it requires the use of another generator to
sample from (e.g. UniformUncertainifier or SimpleGaussianUncertainifier).

###### Weighted Discrete Uncertainifier

(since 0.7.0)

de.lmu.ifi.dbs.elki.data.uncertain.uncertainifier.WeightedDiscreteUncertainifier

Class to generate weighted discrete uncertain objects.

This is a second-order generator: it requires the use of another generator to
sample from (e.g. UniformUncertainifier or SimpleGaussianUncertainifier).

###  Chapter Database

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

ELKI database layer - loading, storing, indexing and accessing data

###  Appendix N Ids

de.lmu.ifi.dbs.elki.database.ids package:

Database object identification and ID group handling API.

Database IDs (short: DBID) in ELKI are based on the factory pattern, to allow
replacing the simple Integer-based DBIDs with more complex implementations,
e.g. for use with external databases or to add tracking for debugging
purposes. This also allows adding of more efficient implementations later on
in a single place.

###### DBID interface:

The DBID object identifies a single object.

The DBIDs hierarchy contains classes for handling groups (sets, arrays) of
IDs, that can be seen as a two-dimensional matrix consisting

ArrayDBIDs HashSetDBIDs

ModifiableDBIDs ArrayModifiableDBIDs HashSetModifiableDBIDs

StaticDBIDs ArrayStaticDBIDs n/a

StaticDBIDs are structures that cannot support modifications, but thus can be
implemented more efficiently, for example as Interval. They are mostly used by
the data sources.

These interfaces cannot be instantiated, obviously. Instead, use the static
DBIDFactory.FACTORY, which is also wrapped in the DBIDUtil class.

###### Examples:

DBIDs allids = database.getIDs();// preallocate an array of initial capacity
123ArrayModifiableDBIDs array = DBIDUtil.newArraySet(123);// new DBID hash set
with minimum initial capacityModifiableDBIDs hash = DBIDUtil.newHashSet();//
add all DBIDs from the hashtree.addDBIDs(hash)

###### Utility functions:

  * •

DBIDUtil.ensureArray to ensure ArrayDBIDs

  * •

DBIDUtil.ensureModifiable to ensure ModifiableDBIDS

  * •

DBIDUtil.makeUnmodifiable to wrap DBIDs unmodifiable

###### Generic utility classes:

MaskedDBIDs allows masking an ArrayDBIDs with a BitSet.

#####  N.1 Integer

de.lmu.ifi.dbs.elki.database.ids.integer package:

Integer-based DBID implementation – do not use directly - always use DBIDUtil.

###### Integer DBID Array Quick Sort

[Yar09] (since 0.5.5)

de.lmu.ifi.dbs.elki.database.ids.integer.IntegerDBIDArrayQuickSort

Class to sort an integer DBID array, using a modified quicksort.

Two array iterators will be used to seek to the elements to compare, while the
backing storage is a plain integer array.

###### Reusing DBID Factory

(since 0.4.0)

de.lmu.ifi.dbs.elki.database.ids.integer.ReusingDBIDFactory

Slightly more complex DBID management, that allows reuse of DBIDs.

NOT tested a lot yet. Not reusing is much simpler!

###### Simple DBID Factory

(since 0.4.0)

de.lmu.ifi.dbs.elki.database.ids.integer.SimpleDBIDFactory

Simple DBID management, that never reuses IDs. Statically allocated DBID
ranges are given positive values, Dynamically allocated DBIDs are given
negative values.

###### Trivial DBID Factory

(since 0.4.0)

de.lmu.ifi.dbs.elki.database.ids.integer.TrivialDBIDFactory

Trivial DBID management, that never reuses IDs and just gives them out in
sequence. All IDs will be positive.

###  Chapter Datasource

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

Data normalization (and reconstitution) of data sets.

###  Appendix O Filter

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

Data filtering, in particular for normalization and projection.

###### Fixed DBI Ds Filter

(since 0.4.0)

de.lmu.ifi.dbs.elki.datasource.filter.FixedDBIDsFilter

This filter assigns static DBIDs, based on the sequence the objects appear in
the bundle by adding a column of DBID type to the bundle.

#####  O.1 Cleaning

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

Filters for data cleaning.

###### Drop Na N Filter

(since 0.6.0)

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

A filter to drop all records that contain NaN values.

Note: currently, only dense vector columns are supported.

###### No Missing Values Filter

(since 0.4.0)

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

A filter to remove entries that have missing values.

###### Replace Na N With Random Filter

(since 0.6.0)

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

A filter to replace all NaN values with random values.