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

java.lang.Object
  de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<R>
      de.lmu.ifi.dbs.elki.algorithm.AbstractDistanceBasedAlgorithm<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, 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