Hdbscan(min_cluster_size, min_samples=nothing; kwargs...)

Hierarchical Density-Based Spatial Clustering of Applications with Noise (HDBSCAN).

Hdbscan performs hierarchical density-based clustering by constructing a hierarchy of density-connected components and selecting the most stable clusters. Unlike DBSCAN, HDBSCAN can identify clusters with varying densities and is generally less sensitive to parameter selection.

Arguments

• min_cluster_size::Int=5: Minimum number of samples required for a group to be considered a cluster.
• min_samples::Union{Nothing,Int}=nothing: Number of neighbors used to compute the core distance. If nothing, it defaults to min_cluster_size.
• cluster_selection_epsilon::Real=0.0: Distance threshold used when merging clusters during cluster selection.
• max_cluster_size::Union{Nothing,Int}=nothing: Maximum size of clusters selected by the "eom" cluster selection method.
• metric::String="euclidean": Distance metric used to compute pairwise distances. Use "precomputed" if the input is a distance matrix.
• metric_params: Additional arguments passed to the selected distance metric.
• alpha::Real=1.0: Distance scaling parameter used in Robust Single Linkage.
• algorithm::String="auto": Algorithm used to compute core distances. Supported values are "auto", "brute", "kd_tree" and "ball_tree".
• leaf_size::Int=40: Leaf size used by tree-based nearest-neighbor algorithms.
• n_jobs::Union{Nothing,Int}=nothing: Number of parallel jobs used during distance computations, if supported.
• cluster_selection_method::String="eom": Cluster selection method. Supported values are "eom" and "leaf".
• allow_single_cluster::Bool=false: Whether a single cluster may be returned.
• store_centers::Union{Nothing,String}=nothing: Cluster centers to compute and store. Supported values are "centroid", "medoid" and "both".
• copy::Bool=false: Whether to copy the input before performing in-place operations.

Fields

After calling fit!, the following fields are populated:

• labels_::Vector{Int}: Cluster label assigned to each sample.
• probabilities_::Vector{Float64}: Membership strength of each sample.
• n_features_in_: Number of input features.
• feature_names_in_: Names of the input features, when available.
• centroids_: Cluster centroids, if requested.
• medoids_: Cluster medoids, if requested.

fit!(model, X; y=nothing)

Fit an HDBSCAN model to the input data.

If model.metric == "precomputed", X is interpreted as a square distance matrix. Otherwise, each row of X is treated as a data sample and pairwise distances are computed according to the selected metric.

The fitted model stores the resulting cluster labels, membership probabilities, and any requested cluster centers.

Arguments

• model::Hdbscan: HDBSCAN model to fit.
• X: Feature matrix or precomputed distance matrix.
• y=nothing: Ignored. Present for compatibility with the MLJ and scikit-learn APIs.

Returns

• Hdbscan: The fitted model.

fit_predict(model, X; y=nothing)

Fit an HDBSCAN model to the input data and return the resulting cluster labels.

If model.metric == "precomputed", X is interpreted as a square distance matrix. Otherwise, each row of X is treated as a data sample and pairwise distances are computed according to the selected metric.

Arguments

• model::Hdbscan: HDBSCAN model to fit.
• X: Feature matrix or precomputed distance matrix.
• y=nothing: Ignored. Present for compatibility with the MLJ and scikit-learn APIs.

Returns

• Vector{Int}: Cluster label assigned to each sample. A label of -1 denotes noise, while -2 and -3 denote samples containing infinite and missing values, respectively.

labels(model)

Return the cluster labels assigned to each sample after fitting the model.

Samples labelled -1 are considered noise. Labels -2 and -3 correspond to samples containing infinite and missing values, respectively.

probabilities(model)

Return the membership probability of each sample in its assigned cluster.

Values range from 0 to 1, where larger values indicate stronger cluster membership.

centroids(model)

Return the cluster centroids computed during fitting, if available.

Centroids are only available when store_centers is set to "centroid" or "both".

medoids(model)

Return the cluster medoids computed during fitting, if available.

Medoids are only available when store_centers is set to "medoid" or "both".

single_linkage_tree(model)

Return the single linkage hierarchy constructed during model fitting.

nclusters(model)

Return the number of clusters identified by the fitted model.

Noise points are not included in the count.

_brute_mst(mutual_reachability, min_samples)

Construct the Minimum Spanning Tree (MST) of a mutual reachability graph.

This function computes the MST from the provided mutual reachability graph, using an implementation specialized for either dense or sparse input.

Arguments

• mutual_reachability: Dense or sparse weighted adjacency matrix representing the mutual reachability graph.
• min_samples::Union{Nothing, Int}=nothing: Number of neighbors used to define core points. This parameter is only required when processing sparse graphs.

Returns

• Vector{MST_edge}: Minimum spanning tree represented as a collection of weighted edges.

_condense_tree(hierarchy, min_cluster_size=10)

Condense a single linkage hierarchy by pruning clusters smaller than the specified minimum cluster size.

This procedure is analogous to the runt pruning method described by Stuetzle and produces a simplified hierarchy that is easier to analyze. The condensed tree also records the lambda value at which individual points leave a cluster, which is later used for stability analysis and cluster selection.

Arguments

• hierarchy::Vector{HierarchyTree}: Single linkage hierarchy.
• min_cluster_size::Int=10: Minimum number of samples required for a cluster to be retained in the condensed tree.

Returns

• Vector{CondensedTree}: Condensed cluster tree represented as a list of parent-child relationships, where each entry stores the parent cluster, child cluster or point, the corresponding lambda value, and the size of the child cluster.

_dense_mutual_reachability_graph!(distance_matrix, further_neighbor_idx)

Compute the mutual reachability graph for a dense distance matrix.

This is the dense implementation of the mutual reachability graph construction. The computation is performed in-place by modifying distance_matrix directly.

Arguments

• distance_matrix: Pairwise distance matrix between samples.
• further_neighbor_idx::Int: Index of the furthest nearest neighbor used to compute the core distance of each sample.

Returns

• The modified distance matrix containing the mutual reachability distances.

_do_labelling(condensed_tree, clusters, cluster_label_map,
              allow_single_cluster, cluster_selection_epsilon)

Assign a cluster label to each sample based on the selected clusters in the condensed tree.

Samples that do not belong to any selected cluster are labelled as noise. For datasets containing a single large cluster, the assignment of border points to noise is influenced by the allow_single_cluster and cluster_selection_epsilon parameters.

Arguments

• condensed_tree::Vector{CondensedTree}: Condensed cluster hierarchy.
• clusters: Set of cluster nodes selected during cluster selection.
• cluster_label_map::Dict: Mapping from cluster node identifiers to the output cluster labels.
• allow_single_cluster::Bool: Whether the root cluster may be selected as the only cluster.
• cluster_selection_epsilon::Real: Distance threshold used during cluster selection.

Returns

• Vector{Int}: Cluster label for each sample. A label of -1 indicates that the sample is classified as noise.

_get_clusters(condensed_tree, stability, cluster_selection_method,
              allow_single_cluster, cluster_selection_epsilon,
              max_cluster_size)

Select the final clusters from a condensed cluster tree and compute the corresponding cluster labels and membership probabilities.

Clusters are selected using either the Excess of Mass ("eom") or leaf-based ("leaf") cluster selection method.

Arguments

• condensed_tree::Vector{CondensedTree}: Condensed cluster hierarchy.
• stability::Dict{Int, Float64}: Mapping from cluster identifiers to their stability values.
• cluster_selection_method::String="eom": Cluster selection method. Supported values are "eom" and "leaf".
• allow_single_cluster::Bool=false: Whether the root cluster may be selected as the only cluster.
• cluster_selection_epsilon::Real=0.0: Distance threshold used during cluster selection.
• max_cluster_size::Union{Nothing, Int}=nothing: Maximum size of a cluster selected by the EOM algorithm.

Returns

A tuple (labels, probabilities) where:

• labels::Vector{Int} contains the cluster label assigned to each sample, with -1 denoting noise.
• probabilities::Vector{Float64} contains the membership strength of each sample in its assigned cluster.

_get_finite_row_indices(X::AbstractMatrix)

Return the indices of the rows in X whose entries are all finite.

Arguments

• X::AbstractMatrix: Dense matrix to inspect.

Returns

• Vector{Int}: Indices of the rows that do not contain NaN or Inf values.

_get_finite_row_indices(X::SparseMatrixCSC)

Return the indices of the rows in X whose nonzero entries are all finite.

Arguments

• X::SparseMatrixCSC: Sparse matrix to inspect.

Returns

• Vector{Int}: Indices of the rows that do not contain NaN or Inf values.

_hdbscan_brute(X; min_samples=5, alpha=1.0,
               metric="euclidean", copy=false, metric_params...)

Construct a single linkage hierarchy from the input data using the brute-force HDBSCAN algorithm.

If metric == "precomputed", X is interpreted as a symmetric distance matrix. Otherwise, pairwise distances are computed from the input data and used to construct the mutual reachability graph.

Arguments

• X: Input data matrix or precomputed distance matrix.
• min_samples::Int=5: Number of neighbors used to determine the core distance of each sample.
• alpha::Float64=1.0: Distance scaling parameter used in Robust Single Linkage.
• metric="euclidean": Distance metric used to compute pairwise distances. If "precomputed", X is assumed to be a square distance matrix.
• copy::Bool=false: Whether to copy the input before performing any in-place modifications.
• metric_params::Array{Number}: Additional arguments passed to the distance metric.

Returns

• Vector{HierarchyTree}: Single linkage hierarchy represented as a dendrogram.

_hdbscan_prims(X, algo; min_samples=5, alpha=1.0,
               metric="euclidean", leaf_size=40,
               n_jobs=nothing, metric_params...)

Construct a single linkage hierarchy from the input data using Prim's algorithm.

Unlike _hdbscan_brute, this implementation computes the Minimum Spanning Tree (MST) directly from the input data without explicitly constructing the full mutual reachability graph.

Arguments

• X::Matrix{<:Real}: Input data matrix whose rows correspond to samples.
• algo::String: Nearest-neighbor search structure used during MST construction.
• min_samples::Int=5: Number of neighbors used to compute the core distance of each sample.
• alpha:::Float64=1.0: Distance scaling parameter used in Robust Single Linkage.
• metric=::String"euclidean": Distance metric used to compute pairwise distances.
• leaf_size::Int=40: Leaf size used by the nearest-neighbor search structure, when applicable.
• n_jobs::Union{Nothing,Int}=nothing: Number of parallel jobs used for distance computations, if supported.
• metric_params::Array{Number}: Additional arguments passed to the distance metric.

Returns

• Vector{HierarchyTree}: Single linkage hierarchy represented as a dendrogram.

_process_mst(min_spanning_tree)

Construct a single linkage hierarchy from a Minimum Spanning Tree (MST).

The edges of the MST are sorted by weight before being processed to build the single linkage hierarchy.

Arguments

• min_spanning_tree::Vector{MST_edge}: Minimum spanning tree represented as a collection of weighted edges.

Returns

• Vector{HierarchyTree}: Single linkage hierarchy represented as a dendrogram.

_sparse_mutual_reachability_graph!(
    data, rowval, colptr,
    n_samples, further_neighbor_idx, max_distance)

Compute the mutual reachability graph for a sparse distance matrix stored in Compressed Sparse Column (CSC) format.

This is the sparse implementation of the mutual reachability graph construction. The computation is performed in-place by modifying the nonzero values stored in data.

Arguments

• data::Vector{<:Real}: Nonzero values of the sparse distance matrix.
• rowval::Vector{Int}: Row indices corresponding to the entries in data.
• colptr::Vector{Int}: Column pointer array defining the CSC structure.
• n_samples::Int: Number of samples represented by the distance matrix.
• further_neighbor_idx::Int: Index of the furthest nearest neighbor used to compute the core distance of each sample.
• max_distance::Real: Value used to replace infinite mutual reachability distances.

Returns

• The modified sparse distance matrix represented by data, rowval, and colptr.

_weighted_cluster_center!(model, X)

Compute and store the centroids and/or medoids of the clusters identified by the fitted HDBSCAN model.

This function requires X to contain the original feature vectors rather than a precomputed distance matrix. The computed centers are stored in the centroids_ and/or medoids_ fields of model, depending on the value of model.store_centers.

Arguments

• model::Hdbscan: Fitted HDBSCAN model.
• X::Matrix{Float64}: Feature matrix used to fit the model.

Returns

• The updated model, with the requested cluster centers stored in centroids_ and/or medoids_.

centroids(model)

Return the cluster centroids computed during fitting, if available.

Centroids are only available when store_centers is set to "centroid" or "both".

fit!(model, X; y=nothing)

Fit an HDBSCAN model to the input data.

If model.metric == "precomputed", X is interpreted as a square distance matrix. Otherwise, each row of X is treated as a data sample and pairwise distances are computed according to the selected metric.

The fitted model stores the resulting cluster labels, membership probabilities, and any requested cluster centers.

Arguments

• model::Hdbscan: HDBSCAN model to fit.
• X: Feature matrix or precomputed distance matrix.
• y=nothing: Ignored. Present for compatibility with the MLJ and scikit-learn APIs.

Returns

• Hdbscan: The fitted model.

fit_predict(model, X; y=nothing)

Fit an HDBSCAN model to the input data and return the resulting cluster labels.

If model.metric == "precomputed", X is interpreted as a square distance matrix. Otherwise, each row of X is treated as a data sample and pairwise distances are computed according to the selected metric.

Arguments

• model::Hdbscan: HDBSCAN model to fit.
• X: Feature matrix or precomputed distance matrix.
• y=nothing: Ignored. Present for compatibility with the MLJ and scikit-learn APIs.

Returns

• Vector{Int}: Cluster label assigned to each sample. A label of -1 denotes noise, while -2 and -3 denote samples containing infinite and missing values, respectively.

labelling_at_cut(linkage, cut, min_cluster_size)

Return the cluster labels obtained by cutting a single linkage tree at the specified distance threshold.

Arguments

• linkage::Vector{HierarchyTree}: Single linkage hierarchy.
• cut::Real: Distance threshold.
• min_cluster_size::Int: Minimum cluster size. Smaller clusters are labelled as noise.

Returns

• Vector{Int}: Cluster labels, where -1 denotes noise.

labels(model)

Return the cluster labels assigned to each sample after fitting the model.

Samples labelled -1 are considered noise. Labels -2 and -3 correspond to samples containing infinite and missing values, respectively.

make_single_linkage(mst)

Construct a single linkage hierarchy from a Minimum Spanning Tree (MST).

The hierarchy is represented as a dendrogram in which each merge records the two merged nodes or clusters, the distance at which the merge occurs, and the size of the newly formed cluster.

Arguments

• mst::Vector{MST_edge}: Minimum spanning tree represented as a collection of weighted edges.

Returns

• Vector{HierarchyTree}: Single linkage hierarchy. Each element stores:
  • the left child node or cluster,
  • the right child node or cluster,
  • the merge distance,
  • the size of the newly formed cluster.

medoids(model)

Return the cluster medoids computed during fitting, if available.

Medoids are only available when store_centers is set to "medoid" or "both".

mst_from_data_matrix(raw_data, core_distances, dist_metric; alpha=1.0)

Compute the Minimum Spanning Tree (MST) of the mutual reachability graph constructed from the input data using Prim's algorithm.

The mutual reachability graph is computed implicitly from the input data, the corresponding core distances, and the selected distance metric, without explicitly constructing the full graph.

Arguments

• raw_data::Matrix{Float64}: Matrix whose rows correspond to data samples.
• core_distances::Vector{Float64}: Core distance associated with each sample.
• dist_metric: Distance metric used to compute pairwise distances between samples.
• alpha::Real=1.0: Scaling factor applied to pairwise distances before computing the mutual reachability distance.

Returns

• Vector{MST_edge}: Minimum spanning tree represented as a collection of weighted edges.

mst_from_mutual_reachability(mutual_reachability)

Compute the Minimum Spanning Tree (MST) of the mutual reachability graph using Prim's algorithm.

Arguments

• mutual_reachability::Matrix{Float64}: Matrix containing the mutual reachability distances between all pairs of samples.

Returns

• Vector{MST_edge}: Minimum spanning tree represented as a collection of edges connecting all samples with minimum total weight.

mutual_reachability_graph(distance_matrix, min_samples=5;
                          max_distance=0.0)

Compute the weighted adjacency matrix of the mutual reachability graph.

The mutual reachability distance between two samples xp and xq is defined as

max(d_core(x_p), d_core(x_q), d(x_p, x_q))

where d_core is the distance from a sample to its min_samples-th nearest neighbor.

The computation is performed in-place whenever possible.

Arguments

• distance_matrix: Pairwise distance matrix. Sparse matrices must be in CSR format.
• min_samples::Int=5: Number of nearest neighbors used to compute the core distance.
• max_distance::Real=0.0: Value used to replace infinite mutual reachability distances when distance_matrix is sparse.

Returns

• A dense or sparse weighted adjacency matrix representing the mutual reachability graph.

References

• Campello, R. J., Moulavi, D., & Sander, J. (2013). Density-based clustering based on hierarchical density estimates. Pacific-Asia Conference on Knowledge Discovery and Data Mining, 160-172.

nclusters(model)

Return the number of clusters identified by the fitted model.

Noise points are not included in the count.

probabilities(model)

Return the membership probability of each sample in its assigned cluster.

Values range from 0 to 1, where larger values indicate stronger cluster membership.

remap_single_linkage_tree(tree, internal_to_raw, non_finite)

Reconstruct a single linkage hierarchy by reintroducing samples that were removed because they contained non-finite values.

The reintroduced samples are merged into the root of the hierarchy at an infinite distance and are therefore treated as noise during cluster extraction.

Arguments

• tree::Vector{HierarchyTree}: Single linkage hierarchy built from the finite samples.
• internal_to_raw::Dict{Int, Int}: Mapping from the indices used in the filtered dataset to the corresponding indices in the original dataset.
• non_finite::Vector{Int}: Boolean vector indicating which samples in the original dataset contain non-finite values.

Returns

• Vector{HierarchyTree}: Single linkage hierarchy with the non-finite samples reinserted.

single_linkage_tree(model)

Return the single linkage hierarchy constructed during model fitting.