de.lmu.ifi.dbs.elki.algorithm.clustering
Class OPTICS<O extends DatabaseObject,D extends Distance<D>>

java.lang.Object
  de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<O,R>
          de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm<O,D,ClusterOrderResult<D>>
              de.lmu.ifi.dbs.elki.algorithm.clustering.OPTICS<O,D>

Type Parameters:

O - the type of DatabaseObjects handled by the algorithm

D - the type of Distance used to discern objects

All Implemented Interfaces:

Algorithm<O,ClusterOrderResult<D>>, Parameterizable

@Title(value="OPTICS: Density-Based Hierarchical Clustering")
@Description(value="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.")
@Reference(authors="M. Ankerst, M. Breunig, H.-P. Kriegel, and J. Sander",
           title="OPTICS: Ordering Points to Identify the Clustering Structure",
           booktitle="Proc. ACM SIGMOD Int. Conf. on Management of Data (SIGMOD \'99)",
           url="http://dx.doi.org/10.1145/304181.304187")
public class OPTICS<O extends DatabaseObject,D extends Distance<D>>
extends DistanceBasedAlgorithm<O,D,ClusterOrderResult<D>>

OPTICS provides the OPTICS algorithm.

Reference: M. Ankerst, M. Breunig, H.-P. Kriegel, and J. Sander: OPTICS: Ordering Points to Identify the Clustering Structure.
In: Proc. ACM SIGMOD Int. Conf. on Management of Data (SIGMOD '99).

Author:

Elke Achtert

Nested Class Summary

class

OPTICS.COEntry Encapsulates an entry in the cluster order.

Field Summary

private D	epsilon Hold the value of EPSILON_PARAM.
static OptionID	EPSILON_ID OptionID for EPSILON_PARAM
private DistanceParameter<D>	EPSILON_PARAM Parameter to specify the maximum radius of the neighborhood to be considered, must be suitable to the distance function specified.
private Heap<D,OPTICS.COEntry>	heap The priority queue for the algorithm.
private int	minpts Holds the value of MINPTS_PARAM.
static OptionID	MINPTS_ID OptionID for MINPTS_PARAM
private IntParameter	MINPTS_PARAM Parameter to specify the threshold for minimum number of points in the epsilon-neighborhood of a point, must be an integer greater than 0.
private Set<Integer>	processedIDs Holds a set of processed ids.

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

DISTANCE_FUNCTION_ID, DISTANCE_FUNCTION_PARAM

Fields inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable

debug, logger

Constructor Summary

OPTICS(Parameterization config)
Constructor, adhering to Parameterizable

Method Summary

protected void	expandClusterOrder(ClusterOrderResult<D> clusterOrder, Database<O> database, Integer objectID, FiniteProgress progress) OPTICS-function expandClusterOrder.
protected ClusterOrderResult<D>	runInTime(Database<O> database) Performs the OPTICS algorithm on the given database.
private void	updateHeap(D reachability, OPTICS.COEntry entry) Adds the specified entry with the specified key tp the heap.

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

getDistanceFactory, getDistanceFunction

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

isTime, isVerbose, run, setTime, setVerbose

Methods inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable

debugFine, debugFiner, debugFinest, exception, progress, verbose, warning

Methods inherited from class java.lang.Object

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

Field Detail

EPSILON_ID

public static final OptionID EPSILON_ID

OptionID for EPSILON_PARAM

EPSILON_PARAM

private final DistanceParameter<D extends Distance<D>> EPSILON_PARAM

Parameter to specify the maximum radius of the neighborhood to be considered, must be suitable to the distance function specified.

Key: -optics.epsilon

epsilon

private D extends Distance<D> epsilon

Hold the value of EPSILON_PARAM.

MINPTS_ID

public static final OptionID MINPTS_ID

OptionID for MINPTS_PARAM

MINPTS_PARAM

private final IntParameter MINPTS_PARAM

Parameter to specify the threshold for minimum number of points in the epsilon-neighborhood of a point, must be an integer greater than 0.

Key: -optics.minpts

minpts

private int minpts

Holds the value of MINPTS_PARAM.

processedIDs

private Set<Integer> processedIDs

Holds a set of processed ids.

heap

private Heap<D extends Distance<D>,OPTICS.COEntry> heap

The priority queue for the algorithm.

Constructor Detail

OPTICS

public OPTICS(Parameterization config)

Constructor, adhering to Parameterizable

Parameters:

config - Parameterization

Method Detail

runInTime

protected ClusterOrderResult<D> runInTime(Database<O> database)

Performs the OPTICS algorithm on the given database.

Specified by:

runInTime in class AbstractAlgorithm<O extends DatabaseObject,ClusterOrderResult<D extends Distance<D>>>

Parameters:

database - the database to run the algorithm on

Returns:

the Result computed by this algorithm

expandClusterOrder

protected void expandClusterOrder(ClusterOrderResult<D> clusterOrder,
                                  Database<O> database,
                                  Integer objectID,
                                  FiniteProgress progress)

OPTICS-function expandClusterOrder.

Parameters:

database - the database on which the algorithm is run

objectID - the currently processed object

progress - the progress object to actualize the current progress if the algorithm

updateHeap

private void updateHeap(D reachability,
                        OPTICS.COEntry entry)

Adds the specified entry with the specified key tp the heap. If the entry's object is already in the heap, it will only be updated.

Parameters:

reachability - the reachability of the entry's object

entry - the entry to be added