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

java.lang.Object
  extended by de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<R>
      extended by de.lmu.ifi.dbs.elki.algorithm.AbstractDistanceBasedAlgorithm<O,D,ClusterOrderResult<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, OPTICSTypeAlgorithm<D>, InspectionUtilFrequentlyScanned, Parameterizable
Direct Known Subclasses:
HiCO, HiSC

@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,D extends Distance<D>>
extends AbstractDistanceBasedAlgorithm<O,D,ClusterOrderResult<D>>
implements OPTICSTypeAlgorithm<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).


Nested Class Summary
static class OPTICS.Parameterizer<O,D extends Distance<D>>
          Parameterization class.
 
Field Summary
private  D epsilon
          Hold the value of EPSILON_ID.
static OptionID EPSILON_ID
          Parameter to specify the maximum radius of the neighborhood to be considered, must be suitable to the distance function specified.
private static Logging logger
          The logger for this class.
private  int minpts
          Holds the value of MINPTS_ID.
static OptionID MINPTS_ID
          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  ModifiableDBIDs processedIDs
          Holds a set of processed ids.
 
Fields inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractDistanceBasedAlgorithm
DISTANCE_FUNCTION_ID
 
Constructor Summary
OPTICS(DistanceFunction<? super O,D> distanceFunction, D epsilon, int minpts)
          Constructor.
 
Method Summary
protected  void expandClusterOrder(ClusterOrderResult<D> clusterOrder, Database database, RangeQuery<O,D> rangeQuery, DBID objectID, D epsilon, FiniteProgress progress)
          OPTICS-function expandClusterOrder.
protected  void expandClusterOrderDouble(ClusterOrderResult<DoubleDistance> clusterOrder, Database database, RangeQuery<O,DoubleDistance> rangeQuery, DBID objectID, DoubleDistance epsilon, FiniteProgress progress)
          OPTICS-function expandClusterOrder.
 D getDistanceFactory()
          Get the distance factory.
 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.
 ClusterOrderResult<D> run(Database database, Relation<O> relation)
          Run OPTICS on the database.
 
Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractDistanceBasedAlgorithm
getDistanceFunction
 
Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm
makeParameterDistanceFunction, 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.OPTICSTypeAlgorithm
run
 

Field Detail

logger

private static final Logging logger
The logger for this class.


EPSILON_ID

public static final OptionID EPSILON_ID
Parameter to specify the maximum radius of the neighborhood to be considered, must be suitable to the distance function specified.


MINPTS_ID

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


epsilon

private D extends Distance<D> epsilon
Hold the value of EPSILON_ID.


minpts

private int minpts
Holds the value of MINPTS_ID.


processedIDs

private ModifiableDBIDs processedIDs
Holds a set of processed ids.

Constructor Detail

OPTICS

public OPTICS(DistanceFunction<? super O,D> distanceFunction,
              D epsilon,
              int minpts)
Constructor.

Parameters:
distanceFunction - Distance function
epsilon - Epsilon value
minpts - Minpts value
Method Detail

run

public ClusterOrderResult<D> run(Database database,
                                 Relation<O> relation)
Run OPTICS on the database.

Parameters:
database - Database
relation - Relation
Returns:
Result

expandClusterOrder

protected void expandClusterOrder(ClusterOrderResult<D> clusterOrder,
                                  Database database,
                                  RangeQuery<O,D> rangeQuery,
                                  DBID objectID,
                                  D epsilon,
                                  FiniteProgress progress)
OPTICS-function expandClusterOrder.

Parameters:
clusterOrder - Cluster order result to expand
database - the database on which the algorithm is run
rangeQuery - the range query to use
objectID - the currently processed object
epsilon - Epsilon range value
progress - the progress object to actualize the current progress if the algorithm

expandClusterOrderDouble

protected void expandClusterOrderDouble(ClusterOrderResult<DoubleDistance> clusterOrder,
                                        Database database,
                                        RangeQuery<O,DoubleDistance> rangeQuery,
                                        DBID objectID,
                                        DoubleDistance epsilon,
                                        FiniteProgress progress)
OPTICS-function expandClusterOrder.

Parameters:
clusterOrder - Cluster order result to expand
database - the database on which the algorithm is run
rangeQuery - the range query to use
objectID - the currently processed object
epsilon - Query epsilon
progress - the progress object to actualize the current progress if the algorithm

getMinPts

public int getMinPts()
Description copied from interface: OPTICSTypeAlgorithm
Get the minpts value used. Needed for OPTICS Xi etc.

Specified by:
getMinPts in interface OPTICSTypeAlgorithm<D extends Distance<D>>
Returns:
minpts value

getDistanceFactory

public D getDistanceFactory()
Description copied from interface: OPTICSTypeAlgorithm
Get the distance factory. Needed for type checking (i.e. is number distance)

Specified by:
getDistanceFactory in interface OPTICSTypeAlgorithm<D extends Distance<D>>
Returns:
distance factory

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<ClusterOrderResult<D extends Distance<D>>>
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<ClusterOrderResult<D extends Distance<D>>>
Returns:
the static logger

Release 0.4.0 (2011-09-20_1324)