de.lmu.ifi.dbs.elki.algorithm.clustering.optics

Class OPTICS<O>

java.lang.Object

de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<R>

de.lmu.ifi.dbs.elki.algorithm.AbstractDistanceBasedAlgorithm<O,ClusterOrderResult<DoubleDistanceClusterOrderEntry>>

de.lmu.ifi.dbs.elki.algorithm.clustering.optics.OPTICS<O>

Type Parameters:

O - the type of DatabaseObjects handled by the algorithm

All Implemented Interfaces:

Algorithm, OPTICSTypeAlgorithm<DoubleDistanceClusterOrderEntry>, DistanceBasedAlgorithm<O>

@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")
 @Alias(value={"OPTICS","de.lmu.ifi.dbs.elki.algorithm.clustering.OPTICS"})
public class OPTICS<O>
extends AbstractDistanceBasedAlgorithm<O,ClusterOrderResult<DoubleDistanceClusterOrderEntry>>
implements OPTICSTypeAlgorithm<DoubleDistanceClusterOrderEntry>

The OPTICS algorithm for density-based hierarchical clustering. 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

Nested Classes

Modifier and Type	Class and Description
static class	OPTICS.Parameterizer<O> Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
private double	epsilon Holds the maximum distance to search for objects (performance parameter)
private static Logging	LOG The logger for this class.
private int	minpts The density threshold, in number of points.
private ModifiableDBIDs	processedIDs Holds a set of processed ids.

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

DISTANCE_FUNCTION_ID

Constructor Summary

Constructors

Constructor and Description
OPTICS(DistanceFunction<? super O> distanceFunction, double epsilon, int minpts) Constructor.

Method Summary

Modifier and Type	Method and Description
protected void	expandClusterOrder(ClusterOrderResult<DoubleDistanceClusterOrderEntry> clusterOrder, Relation<O> database, RangeQuery<O> rangeQuery, DBID objectID, double epsilon, FiniteProgress progress) OPTICS-function expandClusterOrder.
Class<? super DoubleDistanceClusterOrderEntry>	getEntryType() Get the entry type.
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<DoubleDistanceClusterOrderEntry>	run(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.optics.OPTICSTypeAlgorithm

run

Field Detail

LOG

private static final Logging LOG

The logger for this class.

epsilon

private double epsilon

Holds the maximum distance to search for objects (performance parameter)

minpts

private int minpts

The density threshold, in number of points.

processedIDs

private ModifiableDBIDs processedIDs

Holds a set of processed ids.

Constructor Detail

OPTICS

public OPTICS(DistanceFunction<? super O> distanceFunction,
              double epsilon,
              int minpts)

Constructor.

Parameters:

distanceFunction - Distance function

epsilon - Epsilon value

minpts - Minpts value

Method Detail

run

public ClusterOrderResult<DoubleDistanceClusterOrderEntry> run(Relation<O> relation)

Run OPTICS on the database.

Parameters:

relation - Relation

Returns:

Result

expandClusterOrder

protected void expandClusterOrder(ClusterOrderResult<DoubleDistanceClusterOrderEntry> clusterOrder,
                                  Relation<O> database,
                                  RangeQuery<O> rangeQuery,
                                  DBID objectID,
                                  double 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<DoubleDistanceClusterOrderEntry>

Returns:

minpts value

getEntryType

public Class<? super DoubleDistanceClusterOrderEntry> getEntryType()

Description copied from interface: OPTICSTypeAlgorithm

Get the entry type. Needed for type checking (i.e. is number distance)

Specified by:

getEntryType in interface OPTICSTypeAlgorithm<DoubleDistanceClusterOrderEntry>

Returns:

entry type

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<DoubleDistanceClusterOrderEntry>>

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<DoubleDistanceClusterOrderEntry>>

Returns:

the static logger