de.lmu.ifi.dbs.elki.algorithm

Class KNNDistancesSampler<O>

java.lang.Object

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

de.lmu.ifi.dbs.elki.algorithm.AbstractDistanceBasedAlgorithm<O,KNNDistancesSampler.KNNDistanceOrderResult>

de.lmu.ifi.dbs.elki.algorithm.KNNDistancesSampler<O>

Type Parameters:

O - the type of objects handled by this algorithm

All Implemented Interfaces:

Algorithm, DistanceBasedAlgorithm<O>

@Title(value="KNN-Distance-Order")
 @Description(value="Assesses the knn distances for a specified k and orders them.")
 @Alias(value="de.lmu.ifi.dbs.elki.algorithm.KNNDistanceOrder")
 @Reference(authors="Martin Ester, Hans-Peter Kriegel, J\u00f6rg Sander, Xiaowei Xu",title="A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise",booktitle="Proc. 2nd Int. Conf. on Knowledge Discovery and Data Mining (KDD \'96)",url="http://www.aaai.org/Library/KDD/1996/kdd96-037.php",bibkey="DBLP:conf/kdd/EsterKSX96") @Reference(authors="Erich Schubert, J\u00f6rg Sander, Martin Ester, Hans-Peter Kriegel, Xiaowei Xu",title="DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN",booktitle="ACM Trans. Database Systems (TODS)",url="https://doi.org/10.1145/3068335",bibkey="DBLP:journals/tods/SchubertSEKX17")
public class KNNDistancesSampler<O>
extends AbstractDistanceBasedAlgorithm<O,KNNDistancesSampler.KNNDistanceOrderResult>

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.

Reference:

Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu
A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise
Proc. 2nd Int. Conf. on Knowledge Discovery and Data Mining (KDD '96)

Further discussion:

Erich Schubert, Jörg Sander, Martin Ester, Hans-Peter Kriegel, Xiaowei Xu
DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN
ACM Trans. Database Systems (TODS)

Since:

0.1

Author:

Arthur Zimek

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	KNNDistancesSampler.KNNDistanceOrderResult Curve result for a list containing the knn distances.
static class	KNNDistancesSampler.Parameterizer<O> Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
protected int	k Parameter k.
private static Logging	LOG The logger for this class.
private RandomFactory	rnd Random number seeding.
protected double	sample Sampling percentage.

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

ALGORITHM_ID

Fields inherited from interface de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm

DISTANCE_FUNCTION_ID

Constructor Summary

Constructors

Constructor and Description
KNNDistancesSampler(DistanceFunction<? super O> distanceFunction, int k, double sample, RandomFactory rnd) Constructor.

Method Summary

Modifier and Type	Method and Description
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected Logging	getLogger() Get the (STATIC) logger for this class.
KNNDistancesSampler.KNNDistanceOrderResult	run(Database database, Relation<O> relation) Provides an order of the kNN-distances for all objects within the specified database.

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

getDistanceFunction

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

run

Methods inherited from class java.lang.Object

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

Methods inherited from interface de.lmu.ifi.dbs.elki.algorithm.Algorithm

run

Field Detail

LOG

private static final Logging LOG

The logger for this class.

k

protected int k

Parameter k.

sample

protected double sample

Sampling percentage.

rnd

private RandomFactory rnd

Random number seeding.

Constructor Detail

KNNDistancesSampler

public KNNDistancesSampler(DistanceFunction<? super O> distanceFunction,
                           int k,
                           double sample,
                           RandomFactory rnd)

Constructor.

Parameters:

distanceFunction - Distance function

k - k Parameter

sample - Sampling rate, or sample size (when > 1)

rnd - Random source.

Method Detail

run

public KNNDistancesSampler.KNNDistanceOrderResult run(Database database,
                                                      Relation<O> relation)

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

Parameters:

database - Database

relation - Relation

Returns:

Result

getInputTypeRestriction

public TypeInformation[] getInputTypeRestriction()

Description copied from class: AbstractAlgorithm

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

Specified by:

getInputTypeRestriction in interface Algorithm

Specified by:

getInputTypeRestriction in class AbstractAlgorithm<KNNDistancesSampler.KNNDistanceOrderResult>

Returns:

Type restriction

getLogger

protected Logging getLogger()

Description copied from class: AbstractAlgorithm

Get the (STATIC) logger for this class.

Specified by:

getLogger in class AbstractAlgorithm<KNNDistancesSampler.KNNDistanceOrderResult>

Returns:

the static logger