DBSCAN (density-based spatial clustering of applications with noise) algorithm.

The DBSCAN algorithm forms clusters based on the idea of density connectivity, i.e. a point p is density connected to another point q, if there exists a chain of points p_i, with i = 1 .. n and p₁ = p and p_n = q, such that each pair <p_i, p_i+1> is directly density-reachable. A point q is directly density-reachable from point p if it is in the ε-neighborhood of this point.

Any point that is not density-reachable from a formed cluster is treated as noise, and will thus not be present in the result.

The algorithm requires two parameters:

eps: the distance that defines the ε-neighborhood of a point
minPoints: the minimum number of density-connected points required to form a cluster

Note

as DBSCAN is not a centroid-based clustering algorithm, the resulting Cluster objects will have no defined center, i.e. Cluster#getCenter() will return null.

Nested and Inner Type Summary

Modifier and Type	Class and Description
private static enum	DBSCANClusterer.PointStatus Status of a point during the clustering process.

Field Summary

Modifier and Type	Field and Description
private final double	eps Maximum radius of the neighborhood to be considered.
private final int	minPts Minimum number of points needed for a cluster.

Constructor Summary

Access	Constructor and Description
public	DBSCANClusterer(final double maximum radius of the neighborhood to be considered eps, final int minimum number of points needed for a cluster minPts) Creates a new instance of a DBSCANClusterer.

Method Summary

Modifier and Type	Method and Description
public List<Cluster<T>>	Returns: the list of clusters cluster(final Collection<T> the points to cluster points) Performs DBSCAN cluster analysis.
private Cluster<T>	Returns: the expanded cluster expandCluster(final Cluster<T> Cluster to expand cluster, final T Point to add to cluster point, final List<T> List of neighbors neighbors, final Collection<T> the data set points, final Map<Clusterable<T>, DBSCANClusterer.PointStatus> the set of already visited points visited) Deprecated as a consequence of `Cluster` being deprecated. Expands the cluster to include density-reachable items.
public double	Returns: maximum radius of the neighborhood getEps() Returns the maximum radius of the neighborhood to be considered.
public int	Returns: minimum number of points needed for a cluster getMinPts() Returns the minimum number of points needed for a cluster.
private List<T>	Returns: the List of neighbors getNeighbors(final T the point to look for point, final Collection<T> possible neighbors points) Returns a list of density-reachable neighbors of a `point`.
private List<T>	Returns: merged lists merge(final List<T> first list one, final List<T> second list two) Merges two lists together.

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

eps	back to summary
private final double eps Maximum radius of the neighborhood to be considered.

minPts	back to summary
private final int minPts Minimum number of points needed for a cluster.

Constructor Detail

DBSCANClusterer back to summary

DBSCANClusterer	back to summary
public DBSCANClusterer(final double eps, final int minPts) throws NotPositiveException Creates a new instance of a DBSCANClusterer. Parameters eps:double maximum radius of the neighborhood to be considered minPts:int minimum number of points needed for a cluster Exceptions NotPositiveException: if `eps < 0.0` or `minPts < 0`

public DBSCANClusterer(final double eps, final int minPts) throws NotPositiveException

Creates a new instance of a DBSCANClusterer.

Parameters

eps:double: maximum radius of the neighborhood to be considered
minPts:int: minimum number of points needed for a cluster

Exceptions

NotPositiveException:: if eps < 0.0 or minPts < 0

Method Detail

cluster back to summary

cluster	back to summary
public List<Cluster<T>> cluster(final Collection<T> points) throws NullArgumentException Performs DBSCAN cluster analysis. Note as DBSCAN is not a centroid-based clustering algorithm, the resulting `Cluster` objects will have no defined center, i.e. `Cluster#getCenter()` will return `null`. Parameters points:Collection<T> the points to cluster Returns:List<Cluster<T>> the list of clusters Exceptions NullArgumentException: if the data points are null

public List<Cluster<T>> cluster(final Collection<T> points) throws NullArgumentException

Performs DBSCAN cluster analysis.

Note

as DBSCAN is not a centroid-based clustering algorithm, the resulting Cluster objects will have no defined center, i.e. Cluster#getCenter() will return null.

Parameters

points:Collection<T>: the points to cluster

Returns:List<Cluster<T>>

the list of clusters

Exceptions

NullArgumentException:: if the data points are null

expandCluster back to summary

expandCluster	back to summary
private Cluster<T> expandCluster(final Cluster<T> cluster, final T point, final List<T> neighbors, final Collection<T> points, final Map<Clusterable<T>, DBSCANClusterer.PointStatus> visited) Deprecated as a consequence of `Cluster` being deprecated. See corresponding docs for further information. Expands the cluster to include density-reachable items. Parameters cluster:Cluster<T> Cluster to expand point:T Point to add to cluster neighbors:List<T> List of neighbors points:Collection<T> the data set visited:Map<Clusterable<T>, DBSCANClusterer.PointStatus> the set of already visited points Returns:Cluster<T> the expanded cluster

private Cluster<T> expandCluster(final Cluster<T> cluster, final T point, final List<T> neighbors, final Collection<T> points, final Map<Clusterable<T>, DBSCANClusterer.PointStatus> visited)

Deprecated

as a consequence of Cluster being deprecated. See corresponding docs for further information.

Expands the cluster to include density-reachable items.

Parameters

cluster:Cluster<T>: Cluster to expand
point:T: Point to add to cluster
neighbors:List<T>: List of neighbors
points:Collection<T>: the data set
visited:Map<Clusterable<T>, DBSCANClusterer.PointStatus>: the set of already visited points

Returns:Cluster<T>

the expanded cluster

getEps	back to summary
public double getEps() Returns the maximum radius of the neighborhood to be considered. Returns:double maximum radius of the neighborhood

getEps

back to summary

public double getEps()

Returns the maximum radius of the neighborhood to be considered.

Returns:double: maximum radius of the neighborhood

getMinPts	back to summary
public int getMinPts() Returns the minimum number of points needed for a cluster. Returns:int minimum number of points needed for a cluster

getMinPts

back to summary

public int getMinPts()

Returns the minimum number of points needed for a cluster.

Returns:int: minimum number of points needed for a cluster

getNeighbors back to summary

getNeighbors	back to summary
private List<T> getNeighbors(final T point, final Collection<T> points) Returns a list of density-reachable neighbors of a `point`. Parameters point:T the point to look for points:Collection<T> possible neighbors Returns:List<T> the List of neighbors

private List<T> getNeighbors(final T point, final Collection<T> points)

Returns a list of density-reachable neighbors of a point.

Parameters

point:T: the point to look for
points:Collection<T>: possible neighbors

Returns:List<T>

the List of neighbors

merge	back to summary
private List<T> merge(final List<T> one, final List<T> two) Merges two lists together. Parameters one:List<T> first list two:List<T> second list Returns:List<T> merged lists

merge

back to summary

private List<T> merge(final List<T> one, final List<T> two)

Merges two lists together.

Parameters

one:List<T>: first list
two:List<T>: second list

Returns:List<T>

merged lists

org.apache.commons.math3.stat.clustering back to summary

private final Enum DBSCANClusterer.PointStatus

Class Inheritance

extends Enum<DBSCANClusterer.PointStatus>

java.lang.Object
java.lang.Enum
org.apache.commons.math3.stat.clustering.DBSCANClusterer.PointStatus

Status of a point during the clustering process.

Field Summary

Modifier and Type	Field and Description
public static final DBSCANClusterer.PointStatus	NOISE The point has is considered to be noise.
public static final DBSCANClusterer.PointStatus	PART_OF_CLUSTER The point is already part of a cluster.

Constructor Summary

Access	Constructor and Description
private	PointStatus()

Method Summary

Modifier and Type	Method and Description
public static DBSCANClusterer.PointStatus	valueOf(String name)
public static DBSCANClusterer.PointStatus[]	values()

Inherited from java.lang.Enum:: clone compareTo describeConstable equals finalize getDeclaringClass hashCode name ordinal toString valueOf

Field Detail

NOISE	back to summary
public static final DBSCANClusterer.PointStatus NOISE The point has is considered to be noise.

PART_OF_CLUSTER	back to summary
public static final DBSCANClusterer.PointStatus PART_OF_CLUSTER The point is already part of a cluster.

Constructor Detail

PointStatus	back to summary
private PointStatus()

Method Detail

valueOf	back to summary
public static DBSCANClusterer.PointStatus valueOf(String name)

values	back to summary
public static DBSCANClusterer.PointStatus[] values()

public Class DBSCANClusterer<T extends Clusterable<T>>

Nested and Inner Type Summary

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

private final Enum DBSCANClusterer.PointStatus

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail