DBSCAN

ArborX

ArborX::dbscan

Defined in header <ArborX_DBSCAN.hpp>

template <typename ExecutionSpace, typename Primitives>
Kokkos::View<int *, typename ArborX::AccessTraits<Primitives, ArborX::PrimitivesTag>::memory_space>
dbscan(ExecutionSpace const &space, Primitives const &primitives, float eps, int core_min_size);

The free function ArborX::dbscan performs DBSCAN (Density-Based Spatial Clustering of Applications with Noise) clustering from a set of points.

Parameters

space : the execution space.
primitives : geometrical objects one wishes to index. The return value of ArborX::AccessTraits<Primitives, ArborX::PrimitivesTag>::get() must decay to ArborX::Point.
eps : The eps parameter in the DBSCAN algorithm, corresponding to the maximum distance between two objects to be considered in the neighborhood of each other.
core_min_size : The minPts parameter in the DBSCAN algorithm, corresponding to the number of objects in the neighborhood for a point to be considered a core point.

Returns

Cluster labels for each point in the dataset. Noise points are given the label -1.

Example

#include <ArborX_DBSCAN.hpp>

#include <iostream>

int main(int argc, char *argv[])
{
  Kokkos::ScopeGuard guard(argc, argv);

  Kokkos::View<ArborX::Point *> cloud("point_cloud", 9);
  auto cloud_host = Kokkos::create_mirror_view(cloud);
  //     0 1 2 3 4
  //    ----------
  // 3 |     0 7
  // 2 |     5 6
  // 1 | 4 3
  // 0 | 1 2     8
  cloud_host[0] = {3.f, 2.f, 0.f};
  cloud_host[1] = {0.f, 0.f, 0.f};
  cloud_host[2] = {0.f, 1.f, 0.f};
  cloud_host[3] = {1.f, 1.f, 0.f};
  cloud_host[4] = {1.f, 0.f, 0.f};
  cloud_host[5] = {2.f, 2.f, 0.f};
  cloud_host[6] = {2.f, 3.f, 0.f};
  cloud_host[7] = {3.f, 3.f, 0.f};
  cloud_host[8] = {4.f, 0.f, 0.f};
  Kokkos::deep_copy(cloud, cloud_host);

  using execution_space = decltype(cloud)::execution_space; // where to execute code
  auto labels = ArborX::dbscan(execution_space{}, cloud, 1.2, 2);

  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 << std::endl;

  return 0;
}

Output

0 1 1 1 1 0 0 0 -1

Notes

References

Ester, M., H. P. Kriegel, J. Sander, and X. Xu, “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise”. In: Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining, Portland, OR, AAAI Press, pp. 226-231. 1996