Hierarchical

struct ClusterNode{tid, tl, tr, td, tcnt} <: AbstractResult

Binds one merge of a dendrogram to the two clusters it joined.

The tree form of a linkage matrix: to_tree turns a Clustering.Hclust into one of these per merge, plus one per asset, and the last one built is the root. A leaf carries left and right as nothing, which is what is_leaf tests.

level counts leaves, it does not measure depth

level is the number of assets in the subtree below the node — 1 for a leaf, and the sum of the two children's counts for a merge. It is the fourth column of a linkage matrix, not a position in the tree, and on an eight-asset universe the two disagree: the root carries level = 8 where its depth is 5.

pre_order sizes its traversal stack as 2 * a.level, so a depth would undersize it.

Fields

• id: Node identifier.

• left: Left child node.

• right: Right child node.

• height: Height of the node in the dendrogram.

• level: Number of leaves in the subtree rooted at the node, 1 for a leaf. It is the fourth column of a linkage matrix, and pre_order sizes its traversal stack from it.

Constructors

ClusterNode(    id,    left::Option{<:ClusterNode} = nothing,    right::Option{<:ClusterNode} = nothing,    height::Number = 0.0,    level::Int = 1) -> ClusterNode

Arguments correspond to the struct's fields. A node given children ignores the level argument and takes left.level + right.level instead, so only a leaf's level comes from the caller.

Examples

julia> ClusterNode(1)ClusterNode      id ┼ Int64: 1    left ┼ nothing   right ┼ nothing  height ┼ Float64: 0.0   level ┴ Int64: 1

Related

• is_leaf
• pre_order
• to_tree
• Clusters

References

• [50] P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Peterson, W. Weckesser, J. Bright, S. J. van der Walt, M. Brett, J. Wilson, K. J. Millman, N. Mayorov, A. R. Nelson, E. Jones, R. Kern, E. Larson, C. J. Carey, İ. Polat, Y. Feng, E. W. Moore, J. VanderPlas, D. Laxalde, J. Perktold, R. Cimrman, I. Henriksen, E. A. Quintero, C. R. Harris, A. M. Archibald, A. H. Ribeiro, F. Pedregosa and P. van Mulbregt. SciPy 1.0: fundamental algorithms for scientific computing in Python. Nature Methods 17, 261–272 (2020).
• [5] D. Cajas. Advanced Portfolio Optimization: A Cutting-edge Quantitative Approach (Springer Nature Switzerland, 2025). Section 12.1.1, Equation 12.5.

abstract type AbstractPreorderBy <: AbstractAlgorithm

Abstract supertype for all preorder traversal strategies.

All concrete and/or abstract types implementing specific preorder traversal logic should be subtypes of AbstractPreorderBy.

A strategy decides which property a leaf contributes to pre_order's output. It does not change the order of the walk, which is always left subtree before right.

Interfaces

In order to implement a new traversal strategy that works seamlessly with the library, subtype AbstractPreorderBy and implement the following method:

Required method

• get_node_property(preorder_by::MyPreorderBy, a::ClusterNode): Return the property that a contributes when it is reached as a leaf.

Arguments

• preorder_by: The concrete traversal strategy.
• a: Node reached by the walk.

Returns

• The property to collect. Every leaf below one root must contribute the same type.

The property sets the element type of the walk

pre_order takes the element type of its output from the strategy. It reads get_node_property(preorder_by, a) at the root of the walk, and collects into a vector of that value's type. A property of any type therefore works. PreorderTreeByID is the only strategy that ships, and its property is the node's id, so the default output is a Vector{Int}.

Related

• PreorderTreeByID
• get_node_property
• pre_order

struct PreorderTreeByID <: AbstractPreorderBy

Collects each leaf's id, which for a leaf is its asset index.

The default strategy, and the only one that ships. to_tree numbers the leaves 1:N in the order of the clustering's own asset axis, so a pre_order under this strategy returns asset indices ready to index a returns matrix with.

Related

• AbstractPreorderBy
• get_node_property
• pre_order
• to_tree

References

• [50] P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Peterson, W. Weckesser, J. Bright, S. J. van der Walt, M. Brett, J. Wilson, K. J. Millman, N. Mayorov, A. R. Nelson, E. Jones, R. Kern, E. Larson, C. J. Carey, İ. Polat, Y. Feng, E. W. Moore, J. VanderPlas, D. Laxalde, J. Perktold, R. Cimrman, I. Henriksen, E. A. Quintero, C. R. Harris, A. M. Archibald, A. H. Ribeiro, F. Pedregosa and P. van Mulbregt. SciPy 1.0: fundamental algorithms for scientific computing in Python. Nature Methods 17, 261–272 (2020).

get_node_property(preorder_by::PreorderTreeByID, a::ClusterNode)

Get the property of a node used for preorder traversal.

For PreorderTreeByID, this returns the node's id.

Arguments

• preorder_by: Preorder traversal strategy.
• a: The node.

Returns

• The node's identifier.

Related

• PreorderTreeByID
• pre_order

is_leaf(a::ClusterNode)

Is this node an asset, or a merge of two clusters?

Tests left alone. A ClusterNode is built with both children or with neither, so one test settles it.

Arguments

• a: The node to check.

Returns

• flag::Bool: true when the node has no children.

Examples

julia> PortfolioOptimisers.is_leaf(ClusterNode(1))true

Related

• ClusterNode

pre_order(a::ClusterNode, preorder_by::AbstractPreorderBy = PreorderTreeByID())

List the leaves below a node, left to right.

Walks the subtree rooted at a in preorder and collects one property per leaf; an internal node contributes nothing but the order it imposes on its two children. The property collected is get_node_property's, so preorder_by is what a caller changes to collect something other than the node's id.

preorder_by is positional, not a keyword.

Algorithm

1. Open the stack curNode, sized at 2 * a.level. ClusterNode's level counts the leaves below the node, so the stack holds twice as many slots as the walk can ever need.
2. Put a in the first slot, and open the two sets lvisited and rvisited, which record the internal nodes whose left and whose right child the walk has already pushed.
3. Read the node nd on top of the stack.
4. A leaf pushes get_node_property's value onto preorder and is popped.
5. An internal node outside lvisited pushes its left child and joins lvisited.
6. An internal node inside lvisited and outside rvisited pushes its right child and joins rvisited.
7. An internal node inside both sets is popped, because the walk below it is finished.
8. Repeat from step 3 until the stack is empty, giving preorder, one property per leaf in left-to-right order.

Arguments

• a: Root node of the subtree to walk.
• preorder_by: Traversal strategy, deciding which property each leaf contributes.

Returns

• res::Vector: One property per leaf, in left-to-right order. Its length is a.level. The element type is the type of get_node_property(preorder_by, a), so the default strategy gives a Vector{Int}.

Related

• ClusterNode
• AbstractPreorderBy
• PreorderTreeByID
• get_node_property

to_tree(a::Hclust)

Rebuild a linkage matrix as a tree of ClusterNode objects.

Reads a Clustering.Hclust from Clustering.jl and builds 2N - 1 nodes: one leaf per asset, numbered 1:N in the clustering's own asset order, then one node per merge, numbered N+1 upward in the order the merges happened. The last merge is therefore the root.

Algorithm

1. Read N, the number of assets, from the length of a.order, and open d, a vector of 2N - 1 nodes.
2. Build one leaf per asset, d[i] = ClusterNode(i), so the leaves carry the ids 1:N in the clustering's own asset order.
3. Walk the merges in the order a.heights gives them, which is the order they happened in.
4. Resolve each side of row i of a.merges to an index into d: a negative entry fi names the asset -fi, and a positive entry names the merge fi + N.
5. Build the merge node ClusterNode(i + N, d[fi], d[fj], height) and store it at d[N + i], so the merge nodes carry the ids N+1:2N-1 in merge order.
6. Return the node built last, which is the root, together with d.

Arguments

• a: Hierarchical clustering object.

Returns

• root::ClusterNode: Root of the tree, which is the node of the last merge.
• nodes::Vector{ClusterNode}: All 2N - 1 nodes, leaves first, then merges in merge order. The vector is not sorted by height; a caller that needs that ordering sorts it, as optimal_number_clusters does.

Related

• ClusterNode
• pre_order

optimal_number_clusters(onc::OptimalNumberClusters{<:Any, <:Integer}, res::Hclust,
                        args...)
optimal_number_clusters(onc::OptimalNumberClusters{<:Any, <:SecondOrderDifference},
                        res::Hclust, D::MatNum)
optimal_number_clusters(onc::OptimalNumberClusters{<:Any, <:SilhouetteScore},
                        res::Hclust, D::MatNum)

Cut a dendrogram at the number of clusters onc selects.

Scores every candidate count up to the ceiling onc sets, then takes the highest-scoring count the tree can actually be cut at. A count no node of the dendrogram supports is rejected by validate_k_value and the next-highest score is tried, so the answer is the best valid count rather than the best score.

Every method returns a bare k. The non-hierarchical methods of the same name return the tuple (res, k) instead, because a flat partition cannot be re-cut and the clustering is the choice of k.

Algorithm

The Integer method runs these steps. It is a search, not a test: an invalid stated count is replaced, never refused.

1. Read the stated count onc.alg into k, and the ceiling into max_k. The ceiling is min(floor(Int, sqrt(N)), onc.max_k), where N is the number of assets; a max_k of nothing leaves it at floor(Int, sqrt(N)).
2. Lower k to max_k when it exceeds it.
3. Rebuild the tree with to_tree and order its nodes by descending height, giving nodes.
4. Ask validate_k_value whether the tree can be cut at k, and return k when it can.
5. Search upward from k + 1 to max_k for the first valid count, giving ku and its distance du = ku - k. Both stay at k and 0 when the search finds none.
6. Search downward from k - 1 to 1 for the first valid count, giving kl and its distance dl = k - kl. This search always succeeds when k > 1, because k = 1 is always a valid cut.
7. Take the count. When one side alone found one, take that side. When both found one and du != dl, take the nearer. When both found one and du == dl, take ku if max_k - ku > kl - 1 and kl otherwise, so a tie goes to the side with more room left.

The SecondOrderDifference and SilhouetteScore methods run the steps their own algorithm types state. Both end by handing the score array to valid_k_clusters, which walks down from the largest entry until the dendrogram admits the count.

Arguments

• onc: Optimal number of clusters estimator.

  • onc::OptimalNumberClusters{<:Any, <:Integer}: Takes the stated k, lowered to the ceiling. If that k is not valid, searches upward and downward for the nearest valid count and takes the nearer of the two; a tie goes to whichever side has more room left.
  • onc::OptimalNumberClusters{<:Any, <:SecondOrderDifference}: Scores each count by the two-difference gap statistic of the within-cluster dispersions, then hands the scores to valid_k_clusters. The dispersion is onc.alg.alg applied to one cluster's pairwise distances, summed over clusters.
  • onc::OptimalNumberClusters{<:Any, <:SilhouetteScore}: Scores each count by onc.alg.alg applied to the vector of per-asset silhouettes, then hands the scores to valid_k_clusters.

• res: Hierarchical clustering object.

• D: Distance matrix the clustering was run on.

Returns

• k::Integer: Selected number of clusters, and always a count the dendrogram can be cut at.

Related

• OptimalNumberClusters
• valid_k_clusters
• validate_k_value

optimal_number_clusters(onc::OptimalNumberClusters{<:Any, <:Integer},
                         alg::AbstractNonHierarchicalClusteringAlgorithm, D::MatNum)
optimal_number_clusters(onc::OptimalNumberClusters{<:Any, <:SecondOrderDifference},
                         alg::AbstractNonHierarchicalClusteringAlgorithm, D::MatNum)
optimal_number_clusters(onc::OptimalNumberClusters{<:Any, <:SilhouetteScore},
                         alg::AbstractNonHierarchicalClusteringAlgorithm, D::MatNum)

Run a non-hierarchical algorithm at every candidate k and keep the best one.

Clusters the distance matrix once per candidate count, scores the results, and returns the winning clustering together with its k. Both come back because a flat partition cannot be re-cut: unlike the hierarchical branch, the clustering is the choice of k.

No validity test, and no tree to run one against

valid_k_clusters has no counterpart here. It rejects a count the dendrogram cannot be cut at, and a flat partition has no dendrogram, so the argmax is taken as it stands.

The dispersion under SecondOrderDifference is also a different quantity from the hierarchical branch's: it is onc.alg.alg applied to the k-means per-point costs, not to within-cluster pairwise distances. That vector has one entry per asset whatever the cut, so a cut never reduces a one-value vector here. The two rise and fall in opposite directions, and they select different counts.

Algorithm

The Integer method runs these steps.

1. Read the stated count onc.alg into k, and the ceiling into max_k. The ceiling is min(floor(Int, sqrt(N)), onc.max_k), where N is the number of assets; a max_k of nothing leaves it at floor(Int, sqrt(N)).
2. Lower k to max_k when it exceeds it.
3. Cluster D once at k with get_k_clusters_from_alg, giving res.
4. Return res and k.

The SecondOrderDifference and SilhouetteScore methods run the steps their own algorithm types state, with one difference: there is no dendrogram to reject a count, so each takes the argmax as it stands. Each then returns cluster_lvls[k], the run it already made at the winning count, together with k. No run is repeated.

Arguments

• onc: Optimal number of clusters estimator.

  • onc::OptimalNumberClusters{<:Any, <:Integer}: Uses a fixed k directly, clamped to max_k.
  • onc::OptimalNumberClusters{<:Any, <:SecondOrderDifference}: Scores each count by the two-difference gap statistic of onc.alg.alg applied to that run's per-point costs, and takes the argmax.
  • onc::OptimalNumberClusters{<:Any, <:SilhouetteScore}: Scores each count by onc.alg.alg applied to the vector of per-asset silhouettes, and takes the argmax.

• alg: Non-hierarchical clustering algorithm (e.g., KMeansAlgorithm).

• D: Pairwise distance matrix.

Returns

• res::Clustering.ClusteringResult: The partition made at the selected count.
• k::Integer: Selected number of clusters.

Both come back as a tuple. The hierarchical methods of the same name in 03_Hierarchical.jl return a bare k instead, because the dendrogram they were handed can be cut again at any count.

Related

• OptimalNumberClusters
• KMeansAlgorithm
• get_k_clusters_from_alg

clusterise(cle::ClustersEstimator{<:Any, <:Any, <:HClustAlgorithm, <:Any},
           X::MatNum; branchorder::Symbol = :optimal, dims::Int = 1,
           kwargs...)

Run hierarchical clustering and return the result as a Clusters object.

Estimates the similarity and distance matrices from X, runs the linkage cle.alg names, and cuts the dendrogram at the count cle.onc selects.

Algorithm

1. Estimate the similarity matrix S and the distance matrix D from X with cor_and_dist, under cle.de and cle.ce.
2. Cluster D with Clustering.hclust under the linkage cle.alg.linkage and the branch order branchorder, giving res, the dendrogram.
3. Choose the number of clusters with optimal_number_clusters(cle.onc, res, D), giving k.
4. Return Clusters(; res = res, S = S, D = D, k = k). P is left as nothing, because the clustering ran on D itself.

Arguments

• cle: Clustering estimator.
• X: Data matrix (observations × assets).
• branchorder: Branch ordering strategy for hierarchical clustering.
• dims: Dimension along which to perform the computation.
• kwargs...: Additional keyword arguments.

Returns

• res::Clusters: Result object containing clustering, similarity, distance matrices, and number of clusters.

Related

• Clusters
• ClustersEstimator

Clustering.assignments(clr::Clusters{<:Clustering.Hclust, <:Any, <:Any, <:Any})
Clustering.assignments(clr::Clusters{<:Clustering.ClusteringResult, <:Any, <:Any,
                                     <:Any})

Label every asset of a Clusters result with the cluster it belongs to.

One name over both clustering families. The two methods differ only in where the labels come from: a dendrogram has none until it is cut, and a flat partition already carries them. The method for a Clustering.Hclust is declared in 03_Hierarchical.jl, and the method for a Clustering.ClusteringResult here.

Algorithm

1. A Clustering.Hclust in clr.res is a dendrogram, which labels nothing on its own. Cut it at clr.k with Clustering.cutree, giving one label per asset.
2. A Clustering.ClusteringResult in clr.res was made at one count and carries its own labels. Read clr.res.assignments.

Arguments

• clr: Clustering result to label.

Returns

• idx::AbstractVector{<:Integer}: One label per asset, over 1:clr.k, in the order of the universe's asset axis. Both methods answer with one entry per asset.

Related

• Clusters
• clusterise
• optimal_number_clusters