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.utilities.optionhandling.AbstractParameterizable
          de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<O>
              de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm<O,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>, Loggable, Parameterizable

public class OPTICS<O extends DatabaseObject,D extends Distance<D>>
extends DistanceBasedAlgorithm<O,D>

OPTICS provides the OPTICS algorithm.

Author:

Elke Achtert

Nested Class Summary

class

OPTICS.COEntry Encapsulates an entry in the cluster order.

Field Summary

private ClusterOrder<O,D>	clusterOrder Provides the result of the algorithm.
private String	epsilon Hold the value of the epsilon parameter.
private PatternParameter	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 the minpts parameter.
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.utilities.optionhandling.AbstractParameterizable

optionHandler

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

debug

Constructor Summary

OPTICS()
Sets epsilon and minimum points to the optionhandler additionally to the parameters provided by super-classes.

Method Summary

protected void	expandClusterOrder(Database<O> database, Integer objectID, Progress progress) OPTICS-function expandClusterOrder.
Description	getDescription() Returns a description of the algorithm.
Result<O>	getResult() Returns the result of the algorithm.
protected void	runInTime(Database<O> database) The run method encapsulated in measure of runtime.
String[]	setParameters(String[] args) Calls AbstractAlgorithm#setParameters(args) and instantiates DistanceBasedAlgorithm.distanceFunction according to the value of parameter DistanceBasedAlgorithm.DISTANCE_FUNCTION_PARAM.
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

getAttributeSettings, getDistanceFunction

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

description, isTime, isVerbose, run, setTime, setVerbose

Methods inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable

addOption, checkGlobalParameterConstraints, deleteOption, description, description, getParameters, getParameterValue, getPossibleOptions, inlineDescription, isSet, setParameters

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

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

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.utilities.optionhandling.Parameterizable

checkGlobalParameterConstraints, getParameters, getPossibleOptions, inlineDescription

Field Detail

EPSILON_PARAM

private final PatternParameter 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

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

epsilon

private String epsilon

Hold the value of the epsilon parameter.

minpts

private int minpts

Holds the value of the minpts parameter.

clusterOrder

private ClusterOrder<O extends DatabaseObject,D extends Distance<D>> clusterOrder

Provides the result of the algorithm.

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()

Sets epsilon and minimum points to the optionhandler additionally to the parameters provided by super-classes.

Method Detail

runInTime

protected void runInTime(Database<O> database)

Description copied from class: AbstractAlgorithm

The run method encapsulated in measure of runtime. An extending class needs not to take care of runtime itself.

Specified by:

runInTime in class AbstractAlgorithm<O extends DatabaseObject>

Parameters:

database - the database to run the algorithm on

See Also:

Algorithm.run(de.lmu.ifi.dbs.elki.database.Database)

expandClusterOrder

protected void expandClusterOrder(Database<O> database,
                                  Integer objectID,
                                  Progress 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 progess if the algorithm

getDescription

public Description getDescription()

Description copied from interface: Algorithm

Returns a description of the algorithm.

Returns:

a description of the algorithm

See Also:

Algorithm.getDescription()

setParameters

public String[] setParameters(String[] args)
                       throws ParameterException

Description copied from class: DistanceBasedAlgorithm

Calls AbstractAlgorithm#setParameters(args) and instantiates DistanceBasedAlgorithm.distanceFunction according to the value of parameter DistanceBasedAlgorithm.DISTANCE_FUNCTION_PARAM. The remaining parameters are passed to the DistanceBasedAlgorithm.distanceFunction.

Specified by:

setParameters in interface Parameterizable

Overrides:

setParameters in class DistanceBasedAlgorithm<O extends DatabaseObject,D extends Distance<D>>

Parameters:

args - parameters to set the attributes accordingly to

Returns:

String[] an array containing the unused parameters

Throws:

ParameterException - in case of wrong parameter-setting

See Also:

Parameterizable.setParameters(String[])

getResult

public Result<O> getResult()

Description copied from interface: Algorithm

Returns the result of the algorithm.

Returns:

the result of the algorithm

See Also:

Algorithm.getResult()

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