DBSCAN¶

Density-based spatial clustering of applications with noise (DBSCAN) is a data clustering algorithm proposed in [Ester96]. It is a density-based clustering non-parametric algorithm: given a set of observations in some space, it groups together observations that are closely packed together (observations with many nearby neighbors), marking as outliers observations that lie alone in low-density regions (whose nearest neighbors are too far away).

Operation	Computational methods	Programming Interface
Compute	Default method	compute(…)	compute_input	compute_result

Mathematical formulation¶

Computation¶

Given the set $X = {x_{1} = (x_{11}, \dots, x_{1 p}), \dots, x_{n} = (x_{n 1}, \dots, x_{n p})}$ of $n$ $p$ -dimensional feature vectors (further referred as observations), a positive floating-point number epsilon and a positive integer minObservations, the problem is to get clustering assignments for each input observation, based on the definitions below [Ester96]: two observations $x$ and $y$ are considered to be in the same cluster if there is a core observation $z$ , and $x$ and $y$ are both reachable from $z$ .

Each cluster gets a unique identifier, an integer number from $0$ to $total number of clusters - 1$ . Each observation is assigned an identifier of the cluster it belongs to, or $- 1$ if the observation considered to be a noise observation.

Programming Interface¶

Refer to API Reference: DBSCAN.

Distributed mode¶

The algorithm supports distributed execution in SPMD mode (only on GPU).

Usage Example¶

Compute¶

void run_compute(const table& data,
                           const table& weights) {
   double epsilon = 1.0;
   std::int64_t max_observations = 5;
   const auto dbscan_desc = kmeans::descriptor<float>{epsilon, max_observations}
      .set_result_options(dal::dbscan::result_options::responses);

   const auto result = compute(dbscan_desc, data, weights);

   print_table("responses", result.get_responses());
}

Examples¶

Batch Processing:

dbscan_brute_force_batch.cpp

Clustering

K-Means

oneDAL documentation