dbscan¶
Defined in header <ArborX_DBSCAN.hpp>
-
template<typename ExecutionSpace, typename Primitives, typename Labels>
void dbscan(ExecutionSpace const &space, Primitives const &primitives, double eps, int core_min_size, Labels &labels, DBSCAN::Parameters const ¶meters = DBSCAN::Parameters())¶ Perform DBSCAN (Density-Based Spatial Clustering of Applications with Noise [1]) clustering of a set of points.
- Parameters:
space – The execution space in which to run the algorithm.
primitives – The points to cluster, accessed through
AccessTraits.eps – The
epsparameter of the DBSCAN algorithm, i.e., the maximum distance between two points for them to be in the neighborhood of each other. It must be positive.core_min_size – The
minPtsparameter of the DBSCAN algorithm, i.e., the number of points in the neighborhood of a point (itself included) for it to be a core point. It must be at least 2.labels – A one-dimensional Kokkos view of an integral type, in which the labels are stored. It is resized to the number of points.
parameters – The options of the algorithm.
The following requirements must be satisfied.
The memory space of
Primitivesmust be accessible fromExecutionSpace.A specialization of
AccessTraitsmust matchPrimitivesas the template argument, andAccessTraits::get()must return a point.Labelsmust be a Kokkos view of an integral type, accessible fromExecutionSpace.
After the call,
labels(i)is-1if thei-th point is noise. Otherwise, it identifies the cluster the point belongs to: points of the same cluster have the same label.The labels are not guaranteed to be identical between runs. If a border point is connected to core points belonging to different clusters, it may be assigned to either of them.
Note
A deprecated overload of
dbscan(), which returns the labels instead of taking them as an argument, is still available. Please use the one above.
Parameters¶
The options of the algorithm are passed through a DBSCAN::Parameters
object, whose setters can be chained.
By default, the algorithm is DBSCAN, run with the FDBSCAN-DenseBox
implementation, without printing anything.
-
struct Parameters¶
-
Parameters &setVerbosity(bool verbose)¶
Print statistics about the dense cells to the standard output if
verboseistrue.
-
Parameters &setImplementation(Implementation impl)¶
Select the implementation of the algorithm.
-
Parameters &setAlgorithm(Algorithm algorithm)¶
Select the variant of the algorithm.
-
Parameters &setVerbosity(bool verbose)¶
-
enum class Implementation¶
The implementation of the algorithm, see [2].
-
enumerator FDBSCAN¶
Search for the neighbors of each point with a tree.
-
enumerator FDBSCAN_DenseBox¶
In addition, group the points that fall in the same cell of a grid when the cell holds at least
core_min_sizepoints, and index each such dense cell as a single box. This is the default.
-
enumerator FDBSCAN¶
Example¶
The example below clusters ten points in 2D with different values of eps and
core_min_size.
#include <ArborX_DBSCAN.hpp>
#include <iostream>
using ExecutionSpace = Kokkos::DefaultExecutionSpace;
using MemorySpace = ExecutionSpace::memory_space;
template <typename... LabelProperties>
void printLabels(Kokkos::View<int *, LabelProperties...> labels)
{
auto labels_host =
Kokkos::create_mirror_view_and_copy(Kokkos::HostSpace{}, labels);
for (int i = 0; i < (int)labels_host.size(); ++i)
std::cout << labels_host(i) << " ";
std::cout << '\n';
}
int main(int argc, char *argv[])
{
Kokkos::ScopeGuard guard(argc, argv);
Kokkos::View<ArborX::Point<2> *, MemorySpace> cloud("Example::point_cloud",
10);
auto cloud_host = Kokkos::create_mirror_view(cloud);
// 4 | 0 7
// 3 | 5 6
// 2 | 9
// 1 | 4 3
// 0 | 1 2 8
// ----------
// 0 1 2 3 4
cloud_host[0] = {4.f, 3.f};
cloud_host[1] = {0.f, 0.f};
cloud_host[2] = {0.f, 1.f};
cloud_host[3] = {1.f, 1.f};
cloud_host[4] = {1.f, 0.f};
cloud_host[5] = {3.f, 3.f};
cloud_host[6] = {3.f, 4.f};
cloud_host[7] = {4.f, 4.f};
cloud_host[8] = {4.f, 0.f};
cloud_host[9] = {2.f, 2.f};
Kokkos::deep_copy(cloud, cloud_host);
Kokkos::View<int *> labels("Example::labels", 0);
// Running with minpts = 2 and eps = 1 would produce two clusters consisting
// of points with indices [1, 2, 3, 4] and [0, 5, 6, 7]. The corresponding
// entries in the labels array would be the same.
// Expected output:
// 0 1 1 1 1 0 0 0 -1 -1
ArborX::dbscan(ExecutionSpace{}, cloud, 1.f, 2, labels);
printLabels(labels);
// Running with minpts = 5 and eps = 1 would produce no clusters. All the
// entries in the labels array would be marked as noise, -1.
// Expected output:
// -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
ArborX::dbscan(ExecutionSpace{}, cloud, 1.f, 5, labels);
printLabels(labels);
// Running with minpts = 2 and eps = 1.5 would produce a single cluster
// consisting of points with indices [0, 1, 2, 3, 4, 5, 6, 7, 9].
// Expected output:
// 0 0 0 0 0 0 0 0 -1 0
ArborX::dbscan(ExecutionSpace{}, cloud, 1.5f, 2, labels);
printLabels(labels);
// Running with minpts = 4 and eps = 1.5 would produce two clusters
// consisting of points with indices [1, 2, 3, 4] and [0, 5, 6, 7]. The point
// with index 9 is a border point and may be assigned to the first, or the
// second cluster.
// Expected output:
// 0 1 1 1 1 0 0 0 -1 0
// or
// 0 1 1 1 1 0 0 0 -1 1
ArborX::dbscan(ExecutionSpace{}, cloud, 1.5f, 4, labels);
printLabels(labels);
return 0;
}