Environment for
DeveLoping
KDD-Applications
Supported by Index-Structures

de.lmu.ifi.dbs.elki.algorithm.clustering
Class DBSCAN<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,R>
              extended by de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm<O,D,Clustering<Model>>
                  extended by 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<Model>>, ClusteringAlgorithm<Clustering<Model>,O>, Parameterizable

public class DBSCAN<O extends DatabaseObject,D extends Distance<D>>
extends DistanceBasedAlgorithm<O,D,Clustering<Model>>
implements ClusteringAlgorithm<Clustering<Model>,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  Clustering<Model> 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, logger
 
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, FiniteProgress objprog, IndefiniteProgress clusprog)
          DBSCAN-function expandCluster.
 Description getDescription()
          Returns a description of the algorithm.
 Clustering<Model> getResult()
          Retrieve the result.
protected  Clustering<Model> runInTime(Database<O> database)
          Performs the DBSCAN algorithm on the given database.
 List<String> setParameters(List<String> args)
          Calls the super method and sets additionally the values of the parameters EPSILON_PARAM and MINPTS_PARAM.
 
Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm
getDistanceFunction
 
Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm
isTime, isVerbose, run, setTime, setVerbose
 
Methods inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
addOption, addParameterizable, addParameterizable, checkGlobalParameterConstraints, collectOptions, getAttributeSettings, getParameters, rememberParametersExcept, removeOption, removeParameterizable, shortDescription
 
Methods inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable
debugFine, debugFiner, debugFinest, exception, progress, 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.clustering.ClusteringAlgorithm
run
 
Methods inherited from interface de.lmu.ifi.dbs.elki.algorithm.Algorithm
setTime, setVerbose
 
Methods inherited from interface de.lmu.ifi.dbs.elki.utilities.optionhandling.Parameterizable
checkGlobalParameterConstraints, collectOptions, getParameters, shortDescription
 

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 Clustering<Model> 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 Clustering<Model> runInTime(Database<O> database)
                               throws IllegalStateException
Performs the DBSCAN algorithm on the given database.

Specified by:
runInTime in class AbstractAlgorithm<O extends DatabaseObject,Clustering<Model>>
Parameters:
database - the database to run the algorithm on
Returns:
the Result computed by this algorithm
Throws:
IllegalStateException - if the algorithm has not been initialized properly (e.g. the setParameters(String[]) method has been failed to be called).

expandCluster

protected void expandCluster(Database<O> database,
                             Integer startObjectID,
                             FiniteProgress objprog,
                             IndefiniteProgress clusprog)
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
objprog - 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,Clustering<Model>>
Returns:
a description of the algorithm

setParameters

public List<String> setParameters(List<String> args)
                           throws ParameterException
Calls the super method 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>,Clustering<Model>>
Parameters:
args - parameters to set the attributes accordingly to
Returns:
a list containing the unused parameters
Throws:
ParameterException - in case of wrong parameter-setting

getResult

public Clustering<Model> getResult()
Description copied from interface: ClusteringAlgorithm
Retrieve the result.

Specified by:
getResult in interface Algorithm<O extends DatabaseObject,Clustering<Model>>
Specified by:
getResult in interface ClusteringAlgorithm<Clustering<Model>,O extends DatabaseObject>
Returns:
the result of the algorithm

Release 0.2.1 (2009-07-13_1605)