de.lmu.ifi.dbs.elki.algorithm.clustering
Class DBSCAN<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.DBSCAN<O,D>

Type Parameters:

O - the type of DatabaseObject the algorithm is applied on

D - the type of Distance used

All Implemented Interfaces:

Algorithm<O>, Clustering<O>, Loggable, Parameterizable

public class DBSCAN<O extends DatabaseObject,D extends Distance<D>>
extends DistanceBasedAlgorithm<O,D>
implements Clustering<O>

DBSCAN provides the DBSCAN algorithm, an algorithm to find density-connected sets in a database.

Reference:
M. Ester, H.-P. Kriegel, J. Sander, and X. Xu: A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise.
In Proc. 2nd Int. Conf. on Knowledge Discovery and Data Mining (KDD '96), Portland, OR, 1996.

Author:

Arthur Zimek

Field Summary

private String	epsilon Holds the value of EPSILON_PARAM.
static OptionID	EPSILON_ID OptionID for EPSILON_PARAM
private PatternParameter	EPSILON_PARAM Parameter to specify the maximum radius of the neighborhood to be considered, must be suitable to the distance function specified.
protected int	minpts Holds the value of MINPTS_PARAM.
static OptionID	MINPTS_ID OptionID for MINPTS_PARAM
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.
protected Set<Integer>	noise Holds a set of noise.
protected Set<Integer>	processedIDs Holds a set of processed ids.
protected ClustersPlusNoise<O>	result Provides the result of the algorithm.
protected List<List<Integer>>	resultList Holds a list of clusters found.

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

DBSCAN()
Provides the DBSCAN algorithm, adding parameters EPSILON_PARAM and MINPTS_PARAM to the option handler additionally to parameters of super class.

Method Summary

protected void	expandCluster(Database<O> database, Integer startObjectID, Progress progress) DBSCAN-function expandCluster.
Description	getDescription() Returns a description of the algorithm.
ClustersPlusNoise<O>	getResult() Returns the result of the algorithm.
protected void	runInTime(Database<O> database) Performs the DBSCAN algorithm on the given database.
String[]	setParameters(String[] args) Calls DistanceBasedAlgorithm#setParameters(args) and sets additionally the values of the parameters EPSILON_PARAM and MINPTS_PARAM.

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.algorithm.Algorithm

run, setTime, setVerbose

Methods inherited from interface de.lmu.ifi.dbs.elki.utilities.optionhandling.Parameterizable

checkGlobalParameterConstraints, description, getAttributeSettings, getParameters, getPossibleOptions, inlineDescription

Field Detail

EPSILON_ID

public static final OptionID EPSILON_ID

OptionID for EPSILON_PARAM

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: -dbscan.epsilon

epsilon

private String epsilon

Holds the value of EPSILON_PARAM.

MINPTS_ID

public static final OptionID MINPTS_ID

OptionID for MINPTS_PARAM

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: -dbscan.minpts

minpts

protected int minpts

Holds the value of MINPTS_PARAM.

resultList

protected List<List<Integer>> resultList

Holds a list of clusters found.

result

protected ClustersPlusNoise<O extends DatabaseObject> result

Provides the result of the algorithm.

noise

protected Set<Integer> noise

Holds a set of noise.

processedIDs

protected Set<Integer> processedIDs

Holds a set of processed ids.

Constructor Detail

DBSCAN

public DBSCAN()

Provides the DBSCAN algorithm, adding parameters EPSILON_PARAM and MINPTS_PARAM to the option handler additionally to parameters of super class.

Method Detail

runInTime

protected void runInTime(Database<O> database)
                  throws IllegalStateException

Performs the DBSCAN algorithm on the given database.

Specified by:

runInTime in class AbstractAlgorithm<O extends DatabaseObject>

Parameters:

database - the database to run the algorithm on

Throws:

IllegalStateException - if the algorithm has not been initialized properly (e.g. the setParameters(String[]) method has been failed to be called).

See Also:

AbstractAlgorithm.runInTime(de.lmu.ifi.dbs.elki.database.Database)

expandCluster

protected void expandCluster(Database<O> database,
                             Integer startObjectID,
                             Progress progress)

DBSCAN-function expandCluster.

Border-Objects become members of the first possible cluster.

Parameters:

database - the database on which the algorithm is run

startObjectID - potential seed of a new potential cluster

progress - the progress object for logging the current status

getDescription

public Description getDescription()

Description copied from interface: Algorithm

Returns a description of the algorithm.

Specified by:

getDescription in interface Algorithm<O extends DatabaseObject>

Returns:

a description of the algorithm

See Also:

Algorithm.getDescription()

setParameters

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

Calls DistanceBasedAlgorithm#setParameters(args) and sets additionally the values of the parameters EPSILON_PARAM and MINPTS_PARAM.

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 ClustersPlusNoise<O> getResult()

Description copied from interface: Algorithm

Returns the result of the algorithm.

Specified by:

getResult in interface Algorithm<O extends DatabaseObject>

Specified by:

getResult in interface Clustering<O extends DatabaseObject>

Returns:

the result of the algorithm

See Also:

Algorithm.getResult()