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 &parameters = 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 eps parameter 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 minPts parameter 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 Primitives must be accessible from ExecutionSpace.

  • A specialization of AccessTraits must match Primitives as the template argument, and AccessTraits::get() must return a point.

  • Labels must be a Kokkos view of an integral type, accessible from ExecutionSpace.

After the call, labels(i) is -1 if the i-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 verbose is true.

Parameters &setImplementation(Implementation impl)

Select the implementation of the algorithm.

Parameters &setAlgorithm(Algorithm algorithm)

Select the variant of the algorithm.

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_size points, and index each such dense cell as a single box. This is the default.

enum class Algorithm

The variant of the algorithm.

enumerator DBSCAN

Border points, i.e., points that are not core points but are in the neighborhood of one, are assigned to a cluster. This is the default.

enumerator DBSCAN_STAR

Border points are considered noise.

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;
}

References