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

java.lang.Object
  extended by de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<R>
      extended by de.lmu.ifi.dbs.elki.algorithm.AbstractDistanceBasedAlgorithm<O,D,Clustering<Model>>
          extended by de.lmu.ifi.dbs.elki.algorithm.clustering.DBSCAN<O,D>
Type Parameters:
O - the type of Object the algorithm is applied to
D - the type of Distance used
All Implemented Interfaces:
Algorithm, ClusteringAlgorithm<Clustering<Model>>, InspectionUtilFrequentlyScanned, 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://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.71.1980")
public class DBSCAN<O,D extends Distance<D>>
extends AbstractDistanceBasedAlgorithm<O,D,Clustering<Model>>
implements ClusteringAlgorithm<Clustering<Model>>

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.


Nested Class Summary
static class DBSCAN.Parameterizer<O,D extends Distance<D>>
          Parameterization class.
 
Field Summary
private  D epsilon
          Holds 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.
protected  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.
protected  ModifiableDBIDs noise
          Holds a set of noise.
protected  ModifiableDBIDs processedIDs
          Holds a set of processed ids.
protected  List<ModifiableDBIDs> resultList
          Holds a list of clusters found.
 
Fields inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractDistanceBasedAlgorithm
DISTANCE_FUNCTION_ID
 
Constructor Summary
DBSCAN(DistanceFunction<? super O,D> distanceFunction, D epsilon, int minpts)
          Constructor with parameters.
 
Method Summary
protected  void expandCluster(Database database, RangeQuery<O,D> rangeQuery, DBID startObjectID, FiniteProgress objprog, IndefiniteProgress clusprog)
          DBSCAN-function expandCluster.
 TypeInformation[] getInputTypeRestriction()
          Get the input type restriction used for negotiating the data query.
protected  Logging getLogger()
          Get the (STATIC) logger for this class.
 Clustering<Model> run(Database database, Relation<O> relation)
          Performs the DBSCAN algorithm on the given 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.ClusteringAlgorithm
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.


epsilon

private D extends Distance<D> epsilon
Holds the value of EPSILON_ID.


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.


minpts

protected int minpts
Holds the value of MINPTS_ID.


resultList

protected List<ModifiableDBIDs> resultList
Holds a list of clusters found.


noise

protected ModifiableDBIDs noise
Holds a set of noise.


processedIDs

protected ModifiableDBIDs processedIDs
Holds a set of processed ids.

Constructor Detail

DBSCAN

public DBSCAN(DistanceFunction<? super O,D> distanceFunction,
              D epsilon,
              int minpts)
Constructor with parameters.

Parameters:
distanceFunction - Distance function
epsilon - Epsilon value
minpts - Minpts parameter
Method Detail

run

public Clustering<Model> run(Database database,
                             Relation<O> relation)
Performs the DBSCAN algorithm on the given database.


expandCluster

protected void expandCluster(Database database,
                             RangeQuery<O,D> rangeQuery,
                             DBID 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
rangeQuery - Range query to use
startObjectID - potential seed of a new potential cluster
objprog - the progress object for logging the current status

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<Clustering<Model>>
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<Clustering<Model>>
Returns:
the static logger

Release 0.4.0 (2011-09-20_1324)