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

@Title(value="DBSCAN: Density-Based Clustering of Applications with Noise")
@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. Ester, H.-P. Kriegel, J. Sander, and X. Xu",
           title="A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise",
           booktitle="Proc. 2nd Int. Conf. on Knowledge Discovery and Data Mining (KDD \'96), Portland, OR, 1996",
           url="http://dx.doi.org/10.1145/93605.98741")
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  D epsilon
          Holds the value of EPSILON_PARAM.
static OptionID EPSILON_ID
          OptionID for EPSILON_PARAM
private  DistanceParameter<D> 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  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.logging.AbstractLoggable
debug, logger
 
Constructor Summary
DBSCAN(Parameterization config)
          Constructor, adhering to Parameterizable
 
Method Summary
protected  void expandCluster(Database<O> database, Integer startObjectID, FiniteProgress objprog, IndefiniteProgress clusprog)
          DBSCAN-function expandCluster.
protected  Clustering<Model> runInTime(Database<O> database)
          Performs the DBSCAN algorithm on the given database.
 
Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm
getDistanceFactory, 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.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
 

Field Detail

EPSILON_ID

public static final OptionID EPSILON_ID
OptionID for EPSILON_PARAM


EPSILON_PARAM

private final DistanceParameter<D extends Distance<D>> 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 D extends Distance<D> 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.


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(Parameterization config)
Constructor, adhering to Parameterizable

Parameters:
config - Parameterization
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

Release 0.3 (2010-03-31_1612)