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
hmer::Clustering.HclustMerges: The same merges, flipped byoptimal_leaf_order!.
Related
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
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
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
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
- Check that
DandSare non-empty and of equal size. - Build the TMFG from
SwithPMFG_T2s, which gives the weighted adjacencyRpm. Check its edge count withassert_pmfg_weights. - Copy the sparsity pattern of
RpmintoApmand fill it with the dissimilarities ofD, so the structure comes from the similarities and the lengths from the distances. - Take the shortest path lengths
DpmonApmwithdistance_wei. - Build the clique and bubble hierarchies from
RpmwithCliqHierarchyTree2s, which givesHb,Mb,CliqListandSb. - Lift the clique membership
Mbto the vertex membershipMv. ColumnnofMvmarks every vertex of every 3-clique that bubblenholds. - Assign the clusters with
BubbleCluster8s, which givesAdjvand the discrete membershipT8. - Build the linkage matrix
ZwithHierarchyConstruct4s, and convert it withturn_into_Hclust_merges. - Load the two merge columns and the heights into a
Clustering.HclustMerges, and order its branches withorder_branches!onVal(branchorder). - Wrap the merges in a
Clustering.Hclusttagged:DBHT.
Arguments
D:N × Ndissimilarity matrix, such as a distance matrix. It must be symmetric. The caller holds that contract, and this function does not check it.S:N × Nnon-negative similarity matrix. It must be symmetric, on the same contract that the function does not check.branchorder: Order method for the dendrogram branches.:optimalfinds the leaf order with the least sum of the distances between adjacent leaves.:barjosephcalls the heuristicClustering.orderbranches_barjoseph!, and:rcallsClustering.orderbranches_r!. The function refuses no other value. Another value leaves the branches in the order thatHierarchyConstruct4sbuilt them.root: Root selection method for the clique hierarchy.sim: Similarity matrix algorithm that madeS. The function passes it toassert_pmfg_weightsand reads it for nothing else, so that a refusal names the configuration and not the matrix. A caller that holds only the matrices leaves itnothing.
Validation
!isempty(S), raisingIsEmptyError.!isempty(D), raisingIsEmptyError.size(S) == size(D), raisingDimensionMismatch.- The TMFG that the function builds from
Skeeps its3N - 6edges, byassert_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 × 1cluster membership vector.T8[n] = kputs vertexnin thek-th discrete cluster.Rpm::SparseMatrixCSC{<:Number, Int}:N × Nadjacency matrix of the Triangulated Maximally Filtered Graph (TMFG).Adjv::SparseMatrixCSC{Int, Int}: Non-discrete cluster membership matrix fromBubbleCluster8s. It is0 × 0when the graph has one converging bubble or none.Dpm::Matrix{<:Number}:N × Nshortest path length matrix of the TMFG.Mv::SparseMatrixCSC{Int, Int}:N × Nbbubble membership matrix.Mv[n, bi] = 1means that vertexnis a vertex of bubblebi.Z::Matrix{<:Number}:(N-1)×4linkage matrix in the convention ofClustering.Hclust, asturn_into_Hclust_mergeswrites it. The branch order of step 9 does not change it.Z_hclust::Clustering.Hclust: Dendrogram inClustering.Hclustformat.
Related
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).