O - the type of Object the algorithm is applied toD - the type of Distance used@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>>
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.
| Modifier and Type | Class and Description |
|---|---|
static class |
DBSCAN.Parameterizer<O,D extends Distance<D>>
Parameterization class.
|
| Modifier and Type | Field and Description |
|---|---|
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.
|
DISTANCE_FUNCTION_ID| Constructor and Description |
|---|
DBSCAN(DistanceFunction<? super O,D> distanceFunction,
D epsilon,
int minpts)
Constructor with parameters.
|
| Modifier and Type | Method and Description |
|---|---|
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.
|
getDistanceFunctionmakeParameterDistanceFunction, runclone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, waitrunprivate static final Logging logger
public static final OptionID EPSILON_ID
private D extends Distance<D> epsilon
EPSILON_ID.public static final OptionID MINPTS_ID
protected int minpts
MINPTS_ID.protected List<ModifiableDBIDs> resultList
protected ModifiableDBIDs noise
protected ModifiableDBIDs processedIDs
public DBSCAN(DistanceFunction<? super O,D> distanceFunction, D epsilon, int minpts)
distanceFunction - Distance functionepsilon - Epsilon valueminpts - Minpts parameterpublic Clustering<Model> run(Database database, Relation<O> relation)
protected void expandCluster(Database database, RangeQuery<O,D> rangeQuery, DBID startObjectID, FiniteProgress objprog, IndefiniteProgress clusprog)
database - the database on which the algorithm is runrangeQuery - Range query to usestartObjectID - potential seed of a new potential clusterobjprog - the progress object for logging the current statuspublic TypeInformation[] getInputTypeRestriction()
AbstractAlgorithmgetInputTypeRestriction in interface AlgorithmgetInputTypeRestriction in class AbstractAlgorithm<Clustering<Model>>protected Logging getLogger()
AbstractAlgorithmgetLogger in class AbstractAlgorithm<Clustering<Model>>