DBHT Clustering: private API

DBHTs(D::MatNum, S::MatNum; branchorder::Symbol = :optimal,
      root::DBHTRootMethod = UniqueRoot(),
      sim::Option{<:AbstractSimilarityMatrixAlgorithm} = nothing)

Perform Direct Bubble Hierarchical Tree clustering, a deterministic clustering algorithm [53]. This version uses a graph-theoretic filtering technique called Triangulated Maximally Filtered Graph (TMFG).

This function implements the full DBHT clustering pipeline: it constructs a Planar Maximally Filtered Graph (PMFG) from the similarity matrix, extracts the clique and bubble hierarchies, assigns clusters, and builds a hierarchical clustering (dendrogram) compatible with Clustering.Hclust.

Algorithm

1. Check that D and S are non-empty and of equal size.
2. Build the PMFG from S with PMFG_T2s, giving the weighted adjacency Rpm, and check its edge count with assert_pmfg_weights.
3. Copy the sparsity pattern of Rpm into Apm and fill it with the dissimilarities of D, so the structure comes from the similarities and the lengths from the distances.
4. Take the shortest path lengths Dpm on Apm with distance_wei.
5. Build the clique and bubble hierarchies from Rpm with CliqHierarchyTree2s, giving Hb, Mb, CliqList and Sb.
6. Lift the clique membership Mb to the vertex membership Mv: column n marks every vertex of every 3-clique that bubble n holds.
7. Assign the clusters with BubbleCluster8s, giving Adjv and the discrete membership T8.
8. Build the linkage matrix Z with HierarchyConstruct4s, and convert it with turn_into_Hclust_merges.
9. Load the two merge columns and the heights into a Clustering.HclustMerges, and order its branches through the branch branchorder selects.
10. Wrap the merges in a Clustering.Hclust tagged :DBHT.

Arguments

• D: N × N dissimilarity matrix (e.g., a distance matrix). It must be symmetric, and the symmetry is a caller contract that this function does not check.
• S: N × N non-negative similarity matrix. It must be symmetric, on the same unchecked contract.
• branchorder: Ordering method for the dendrogram branches. :optimal and :barjoseph both call Clustering.orderbranches_barjoseph!, and :r calls Clustering.orderbranches_r!. Any other value is not refused: it leaves the branches in the order HierarchyConstruct4s built them.
• root: Root selection method for the clique hierarchy.
• sim: Similarity matrix algorithm that produced S. It is forwarded to assert_pmfg_weights and read for nothing else, so that a refusal names the configuration rather than the matrix. A caller that holds only the matrices leaves it nothing.

Validation

• !isempty(S), raising IsEmptyError.
• !isempty(D), raising IsEmptyError.
• size(S) == size(D), raising DimensionMismatch.
• The PMFG built from S keeps its 3N - 6 edges, by assert_pmfg_weights. An exactly zero similarity is an absent edge.

Symmetry is not among them. A caller that derives both matrices from a correlation matrix gets it by construction, and a caller that assembles either by hand carries the contract itself.

Returns

• T8::Vector{Int}: N × 1 cluster membership vector. T8[n] = k puts vertex n in the k-th discrete cluster.
• Rpm::SparseMatrixCSC{<:Number, Int}: N × N adjacency matrix of the Planar Maximally Filtered Graph (PMFG).
• Adjv::SparseMatrixCSC{Int, Int}: Bubble cluster membership matrix from BubbleCluster8s.
• Dpm::Matrix{<:Number}: N × N shortest path length matrix of the PMFG.
• Mv::SparseMatrixCSC{Int, Int}: N × Nb bubble membership matrix. Mv[n, bi] = 1 means vertex n is a vertex of bubble bi.
• Z::Matrix{<:Number}: (N-1)×3 linkage matrix in Matlab format.
• Z_hclust::Clustering.Hclust: Dendrogram in Clustering.Hclust format.

Related

• DBHT
• CliqHierarchyTree2s
• BubbleCluster8s
• HierarchyConstruct4s
• turn_into_Hclust_merges
• Clustering.Hclust