Environment for
DeveLoping
KDD-Applications
Supported by Index-Structures

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

java.lang.Object
  extended by de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      extended by de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
          extended by de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<O>
              extended by de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm<O,D>
                  extended by 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

Release 0.1 (2008-07-10_1838)