HDBSCAN

HDBSCAN#

Hierarchical Density-Based Spatial Clustering of Applications with Noise (HDBSCAN) is a clustering algorithm proposed in [Campello2013]. It extends DBSCAN by converting it into a hierarchical clustering algorithm, then extracting a flat clustering based on the stability of clusters. Unlike DBSCAN, HDBSCAN does not require the user to choose an epsilon parameter and can find clusters of varying densities.

Operation

Computational methods

Programming Interface

Compute

Bf, kd tree, ball tree

compute(…)

compute_input

compute_result

Mathematical formulation#

Refer to Developer Guide: HDBSCAN.

Programming Interface#

All types and functions in this section are declared in the oneapi::dal::hdbscan namespace and are available via inclusion of the oneapi/dal/algo/hdbscan.hpp header file.

Enum classes#

enum class distance_metric#
distance_metric::euclidean

Euclidean (\(L_2\)) distance. Supported by all methods.

distance_metric::manhattan

Manhattan (\(L_1\)) distance. Supported by all methods.

distance_metric::minkowski

Minkowski (\(L_p\)) distance with configurable degree. Supported by all methods.

distance_metric::chebyshev

Chebyshev (\(L_\infty\)) distance. Supported by all methods.

distance_metric::cosine

Cosine distance (\(1 - \cos\theta\)). Supported by method::brute_force only.

enum class cluster_selection_method#
cluster_selection_method::eom

Excess of Mass — selects clusters that maximise total stability (default).

cluster_selection_method::leaf

Selects all leaf nodes of the condensed tree, producing a finer-grained clustering.

enum class store_centers_method#
store_centers_method::none

Do not compute cluster centers (default).

store_centers_method::centroid

Compute centroids (weighted mean of member points).

store_centers_method::medoid

Compute medoids (member point minimizing intra-cluster distance).

store_centers_method::both

Compute both centroids and medoids.

Result options#

class result_option_id#

Constructors

Descriptor#

template<typename Float = float, typename Method = method::by_default, typename Task = task::by_default>
class descriptor#
Template Parameters:

  • Float – The floating-point type that the algorithm uses for intermediate computations. Can be float or double.

  • Method – Tag-type that specifies an implementation of algorithm. Can be method::brute_force, method::kd_tree, or method::ball_tree.

  • Task – Tag-type that specifies the type of the problem to solve. Can be task::clustering.

Constructors

descriptor(std::int64_t min_cluster_size = 5, std::int64_t min_samples = 5)#

Creates a new instance of the class with the given min_cluster_size, min_samples.

Properties

std::int64_t min_cluster_size#

The minimum cluster size.

Getter & Setter
std::int64_t get_min_cluster_size() const
auto & set_min_cluster_size(std::int64_t value)
Invariants
min_cluster_size >= 2
std::int64_t min_samples#

The number of samples in a neighborhood for a point to be considered a core point.

Getter & Setter
std::int64_t get_min_samples() const
auto & set_min_samples(std::int64_t value)
Invariants
min_samples >= 1
result_option_id result_options#

Choose which results should be computed and returned.

Getter & Setter
result_option_id get_result_options() const
auto & set_result_options(const result_option_id &value)
distance_metric metric#

The distance metric used for pairwise distance computation.

Getter & Setter
distance_metric get_metric() const
auto & set_metric(distance_metric value)
Invariants
Cosine metric is only supported with brute_force method.
double degree#

The degree parameter for Minkowski distance.

Getter & Setter
double get_degree() const
auto & set_degree(double value)
Invariants
degree > 0
cluster_selection_method cluster_selection#

The cluster selection method: eom (Excess of Mass) or leaf.

Getter & Setter
cluster_selection_method get_cluster_selection() const
auto & set_cluster_selection(cluster_selection_method value)
bool allow_single_cluster#

When false (default), the root cluster of the condensed tree is never selected. When true, the root cluster may be selected if it meets min_cluster_size.

Getter & Setter
bool get_allow_single_cluster() const
auto & set_allow_single_cluster(bool value)
double cluster_selection_epsilon#

Distance threshold below which clusters are merged after selection.

Getter & Setter
double get_cluster_selection_epsilon() const
auto & set_cluster_selection_epsilon(double value)
Invariants
cluster_selection_epsilon >= 0
std::int64_t max_cluster_size#

Maximum cluster size for EOM selection. 0 means no limit.

Getter & Setter
std::int64_t get_max_cluster_size() const
auto & set_max_cluster_size(std::int64_t value)
Invariants
max_cluster_size >= 0
double alpha#

Distance scaling parameter for robust single linkage.

Getter & Setter
double get_alpha() const
auto & set_alpha(double value)
Invariants
alpha > 0
store_centers_method store_centers#

Which cluster centers to compute and store: none, centroid, medoid, or both.

Getter & Setter
store_centers_method get_store_centers() const
auto & set_store_centers(store_centers_method value)
std::int64_t leaf_size#

Leaf size for kd_tree nearest neighbor queries.

Getter & Setter
std::int64_t get_leaf_size() const
auto & set_leaf_size(std::int64_t value)
Invariants
leaf_size >= 1
std::int64_t distance_block_size#

Row block size B for the GPU blocked pairwise-distance sweep in method::kd_tree / method::ball_tree. When left at the default (0), an internal heuristic picks a value that targets a B x N device buffer of roughly 256 MB (clamped to [256, row_count]). Non-zero values override the heuristic and are clamped to row_count. Ignored by CPU backends and by method::brute_force.

Getter & Setter
std::int64_t get_distance_block_size() const
auto & set_distance_block_size(std::int64_t value)
Invariants
distance_block_size >= 0

Method tags#

struct ball_tree#

Tag-type that denotes ball tree computational method.

struct brute_force#

Tag-type that denotes brute-force computational method.

struct kd_tree#

Tag-type that denotes k-d tree computational method.

using by_default = brute_force#

Alias tag-type for brute-force computational method.

Task tags#

struct clustering#

Tag-type that parameterizes entities used for solving clustering problem.

using by_default = clustering#

Alias tag-type for the clustering task.

Computation compute(...)#

Input#

template<typename Task = task::by_default>
class compute_input#
Template Parameters:

Task – Tag-type that specifies type of the problem to solve. Can be task::clustering.

Constructors

compute_input(const table &data = {})#

Creates a new instance of the class with the given data.

Properties

const table &data#

An \(n \times p\) table with the data to be clustered, where each row stores one feature vector.

Getter & Setter
const table & get_data() const
auto & set_data(const table &data)

Result#

template<typename Task = task::by_default>
class compute_result#
Template Parameters:

Task – Tag-type that specifies type of the problem to solve. Can be task::clustering.

Constructors

compute_result()#

Creates a new instance of the class with the default property values.

Properties

std::int64_t cluster_count#

The number of clusters found by the algorithm.

Getter & Setter
std::int64_t get_cluster_count() const
auto & set_cluster_count(std::int64_t value)
Invariants
cluster_count >= 0
const table &responses#

An \(n \times 1\) table with the responses \(y_i\) assigned to the samples \(x_i\) in the input data. -1 indicates noise. Default value: table{}.

Getter & Setter
const table & get_responses() const
auto & set_responses(const table &value)
const table &core_flags#

An \(n \times 1\) table with the core flags \(y_i\) assigned to the samples \(x_i\) in the input data.

Getter & Setter
const table & get_core_flags() const
auto & set_core_flags(const table &value)
const table &core_observation_indices#

An \(m \times 1\) table with the indices of core observations in the input data. \(m\) is a number of core observations.

Getter & Setter
const table & get_core_observation_indices() const
auto & set_core_observation_indices(const table &value)
const table &core_observations#

An \(m \times p\) table with the core observations in the input data. \(m\) is a number of core observations.

Getter & Setter
const table & get_core_observations() const
auto & set_core_observations(const table &value)
const table &cluster_centers#

A \(k \times p\) table with cluster centroids (mean of member points). \(k\) is the number of clusters.

Getter & Setter
const table & get_cluster_centers() const
auto & set_cluster_centers(const table &value)
const table &medoid_centers#

A \(k \times p\) table with cluster medoids (member point minimizing intra-cluster distance). \(k\) is the number of clusters.

Getter & Setter
const table & get_medoid_centers() const
auto & set_medoid_centers(const table &value)
const result_option_id &result_options#

Result options that indicates availability of the properties. Default value: default_result_options<Task>.

Getter & Setter
const result_option_id & get_result_options() const
auto & set_result_options(const result_option_id &value)

Operation#

template<typename Descriptor>
hdbscan::compute_result compute(const Descriptor &desc, const hdbscan::compute_input &input)#
Parameters:

  • desc – HDBSCAN algorithm descriptor hdbscan::descriptor

  • input – Input data for the compute operation

Preconditions
input.data.has_data == true

Examples#