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

Class FastOPTICS<V extends NumberVector>

java.lang.Object

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

de.lmu.ifi.dbs.elki.algorithm.clustering.optics.FastOPTICS<V>

All Implemented Interfaces:

Algorithm, OPTICSTypeAlgorithm

@Reference(authors="J. Schneider, M. Vlachos",
           title="Fast parameterless density-based clustering via random projections",
           booktitle="Proc. 22nd ACM Int. Conf. on Information & Knowledge Management (CIKM 2013)",
           url="https://doi.org/10.1145/2505515.2505590",
           bibkey="DBLP:conf/cikm/SchneiderV13")
public class FastOPTICS<V extends NumberVector>
extends AbstractAlgorithm<ClusterOrder>
implements OPTICSTypeAlgorithm

FastOPTICS algorithm (Fast approximation of OPTICS)

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

Reference:

J. Schneider, M. Vlachos
Fast parameterless density-based clustering via random projections
Proc. 22nd ACM Int. Conf. on Information and Knowledge Management (CIKM 2013)

This is based on the original code provided by Johannes Schneider, with ELKIfications and optimizations by Erich Schubert.

Since:

0.7.0

Author:

Johannes Schneider, Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	FastOPTICS.Parameterizer<V extends NumberVector> Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
(package private) RandomProjectedNeighborsAndDensities<V>	index Index.
(package private) DoubleDataStore	inverseDensities Inverse Densities correspond to average distances in point set of projections
private static Logging	LOG Class logger.
(package private) int	minPts MinPts parameter.
(package private) DataStore<? extends DBIDs>	neighs neighbors of a point
(package private) ClusterOrder	order Result: output order of points
(package private) ModifiableDBIDs	processed processed points
(package private) WritableDoubleDataStore	reachDist Result: reachability distances
static double	UNDEFINED_DISTANCE undefined value for (reachability/average) distance

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

ALGORITHM_ID

Constructor Summary

Constructors

Constructor and Description
FastOPTICS(int minpts, RandomProjectedNeighborsAndDensities<V> index) Constructor.

Method Summary

Modifier and Type	Method and Description
protected void	expandClusterOrder(DBID ipt, ClusterOrder order, DistanceQuery<V> dq, FiniteProgress prog) OPTICS algorithm for processing a point, but with different density estimates
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected Logging	getLogger() Get the (STATIC) logger for this class.
int	getMinPts() Get the minpts value used.
ClusterOrder	run(Database db, Relation<V> rel) Run the algorithm.

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.clustering.optics.OPTICSTypeAlgorithm

run

Field Detail

LOG

private static final Logging LOG

Class logger.

UNDEFINED_DISTANCE

public static final double UNDEFINED_DISTANCE

undefined value for (reachability/average) distance

See Also:

Constant Field Values

order

ClusterOrder order

Result: output order of points

reachDist

WritableDoubleDataStore reachDist

Result: reachability distances

processed

ModifiableDBIDs processed

processed points

neighs

DataStore<? extends DBIDs> neighs

neighbors of a point

inverseDensities

DoubleDataStore inverseDensities

Inverse Densities correspond to average distances in point set of projections

minPts

int minPts

MinPts parameter.

index

RandomProjectedNeighborsAndDensities<V extends NumberVector> index

Index.

Constructor Detail

FastOPTICS

public FastOPTICS(int minpts,
                  RandomProjectedNeighborsAndDensities<V> index)

Constructor.

Parameters:

minpts - Minimum number of neighbors.

index - Index

Method Detail

run

public ClusterOrder run(Database db,
                        Relation<V> rel)

Run the algorithm.

Parameters:

db - Database

rel - Relation

expandClusterOrder

protected void expandClusterOrder(DBID ipt,
                                  ClusterOrder order,
                                  DistanceQuery<V> dq,
                                  FiniteProgress prog)

OPTICS algorithm for processing a point, but with different density estimates

Parameters:

ipt - Point

order - Cluster order (output)

dq - Distance query

prog - Progress for logging.

getMinPts

public int getMinPts()

Description copied from interface: OPTICSTypeAlgorithm

Get the minpts value used. Needed for OPTICS Xi.

Specified by:

getMinPts in interface OPTICSTypeAlgorithm

Returns:

minpts value

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<ClusterOrder>

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<ClusterOrder>

Returns:

the static logger