DBHT Clustering: private API

PortfolioOptimisers.order_branches! — Function
order_branches!(hmer::Clustering.HclustMerges, D::MatNum, ::Val{:optimal})

Flip the merges of hmer so that its leaf order has the least sum of the distances between adjacent leaves that the tree permits.

Arguments

  • hmer: The merges. The method changes them in place.
  • D: The distance matrix of the leaves.

Returns

Related

source
order_branches!(hmer::Clustering.HclustMerges, D::MatNum, ::Val{:barjoseph})

Flip the merges of hmer with the heuristic Clustering.orderbranches_barjoseph!, which decides each merge once from its four outermost leaves.

Arguments

  • hmer: The merges. The method changes them in place.
  • D: The distance matrix of the leaves.

Returns

  • hmer::Clustering.HclustMerges: The same merges, flipped.

Related

source
order_branches!(hmer::Clustering.HclustMerges, D::MatNum, ::Val{:r})

Order the merges of hmer by height with Clustering.orderbranches_r!, the order of the R function hclust.

Arguments

  • hmer: The merges. The method changes them in place.
  • D: The distance matrix of the leaves. This order does not read it.

Returns

  • hmer::Clustering.HclustMerges: The same merges, ordered.

Related

source
order_branches!(hmer::Clustering.HclustMerges, D::MatNum, ::Val)

Keep the merges of hmer in the order that they arrive, for a branch order that has no method of its own.

Arguments

  • hmer: The merges.
  • D: The distance matrix of the leaves. This method does not read it.

Returns

  • hmer::Clustering.HclustMerges: The same merges, not changed.

Related

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

Run the Direct Bubble Hierarchical Tree clustering of [127], a deterministic clustering algorithm.

This function filters the similarity matrix with a Triangulated Maximally Filtered Graph (TMFG). [127] builds a planar maximally filtered graph instead, and DBHT states the difference. The root and branchorder keywords come from this library alone.

The function runs the full DBHT pipeline. It builds the TMFG from the similarity matrix, builds the clique and bubble hierarchies, assigns the clusters, and builds a dendrogram as a Clustering.Hclust.

Algorithm

  1. Check that D and S are non-empty and of equal size.
  2. Build the TMFG from S with PMFG_T2s, which gives the weighted adjacency Rpm. 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, which gives Hb, Mb, CliqList and Sb.
  6. Lift the clique membership Mb to the vertex membership Mv. Column n of Mv marks every vertex of every 3-clique that bubble n holds.
  7. Assign the clusters with BubbleCluster8s, which gives 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 with order_branches! on Val(branchorder).
  10. Wrap the merges in a Clustering.Hclust tagged :DBHT.

Arguments

  • D: N × N dissimilarity matrix, such as a distance matrix. It must be symmetric. The caller holds that contract, and this function does not check it.
  • S: N × N non-negative similarity matrix. It must be symmetric, on the same contract that the function does not check.
  • branchorder: Order method for the dendrogram branches. :optimal finds the leaf order with the least sum of the distances between adjacent leaves. :barjoseph calls the heuristic Clustering.orderbranches_barjoseph!, and :r calls Clustering.orderbranches_r!. The function refuses no other value. Another value leaves the branches in the order that HierarchyConstruct4s built them.
  • root: Root selection method for the clique hierarchy.
  • sim: Similarity matrix algorithm that made S. The function passes it to assert_pmfg_weights and reads it for nothing else, so that a refusal names the configuration and not 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 TMFG that the function builds from S keeps its 3N - 6 edges, by assert_pmfg_weights. An exactly zero similarity is an absent edge.

The function does not check the symmetry of D or S. A caller that derives both matrices from a correlation matrix gets symmetric matrices. A caller that makes either matrix by hand holds 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 Triangulated Maximally Filtered Graph (TMFG).
  • Adjv::SparseMatrixCSC{Int, Int}: Non-discrete cluster membership matrix from BubbleCluster8s. It is 0 × 0 when the graph has one converging bubble or none.
  • Dpm::Matrix{<:Number}: N × N shortest path length matrix of the TMFG.
  • Mv::SparseMatrixCSC{Int, Int}: N × Nb bubble membership matrix. Mv[n, bi] = 1 means that vertex n is a vertex of bubble bi.
  • Z::Matrix{<:Number}: (N-1)×4 linkage matrix in the convention of Clustering.Hclust, as turn_into_Hclust_merges writes it. The branch order of step 9 does not change it.
  • Z_hclust::Clustering.Hclust: Dendrogram in Clustering.Hclust format.

Related

source

References

[127]
W.-M. Song, T. Di Matteo and T. Aste. Hierarchical information clustering by means of topologically embedded graphs. PloS one 7, e31929 (2012).