Hierarchical

PortfolioOptimisers.ClusterNode — Type
struct ClusterNode{T, H} <: AbstractResult

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

It is the tree form of a linkage matrix. to_tree makes one node per asset and one per merge from a Clustering.Hclust, and the last node it makes is the root. A leaf has nothing in left and in right, and is_leaf tests that.

level counts leaves and is not a depth

level is the number of assets in the subtree below the node. It is 1 for a leaf, and the sum of the counts of the two children for a merge. It is the fourth column of a linkage matrix and not a position in the tree. The root of a balanced tree of eight leaves has level = 8, and its depth is 3.

pre_order sizes its traversal stack as 2 * a.level. The stack holds the path from a to the node that the walk reads, and that path has at most depth + 1 <= a.level nodes.

The type does not hold the shape of the tree

The type is ClusterNode{T, H}, with T the type of id and H the type of height. Each child is a ClusterNode{T, H} too, so all the nodes of one tree have one type. A type that held the types of its children would be a new type for each new dendrogram, and each method that reads a tree would compile again on new data.

Fields

  • id: The identifier of the node.
  • left: The left child, or nothing for a leaf.
  • right: The right child, or nothing for a leaf.
  • height: The height of the node in the dendrogram.
  • level: The number of leaves in the subtree below 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 with children ignores the level argument and takes left.level + right.level, so only a leaf takes its level from the caller.

Validation

  • left and right are each nothing or a ClusterNode{T, H}, with T the type of id and H the type of height of the new node. A child of another type throws a DomainError that names its type.

Examples

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

Related

References

  • [123] 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). The type ports ClusterNode and to_tree of scipy.cluster.hierarchy, which that work names and does not describe.
  • [12] D. Cajas. Advanced Portfolio Optimization: A Cutting-edge Quantitative Approach (Springer Nature Switzerland, 2025). Section 12.1.1, Equation 12.5, for the four columns of a linkage matrix.
source
PortfolioOptimisers.AbstractPreorderBy — Type
abstract type AbstractPreorderBy <: AbstractAlgorithm

Abstract supertype for the strategies of a preorder traversal.

A strategy sets the property that each leaf adds to the output of pre_order. It does not change the order of the walk, which visits the left subtree before the right one.

Interfaces

To implement a new traversal strategy, subtype AbstractPreorderBy and implement the following method:

Required method

  • get_node_property(preorder_by::MyPreorderBy, a::ClusterNode): Return the property that a adds to the output when the walk reaches it as a leaf.

Arguments

  • preorder_by: The concrete traversal strategy.
  • a: The node that the walk reached.

Returns

  • The property to collect. Every leaf below one root must give a value of 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 the type of that value, so a property of any type works. PreorderTreeByID is the one strategy of the library. Its property is the id of the node, so the default output is a Vector{Int}.

Related

source
PortfolioOptimisers.PreorderTreeByID — Type
struct PreorderTreeByID <: AbstractPreorderBy

Collects the id of each leaf, which is the index of its asset.

It is the default strategy and the one strategy of the library. to_tree numbers the leaves 1:N in the order of the asset axis of the clustering, so pre_order under this strategy returns asset indices that can index the columns of a returns matrix.

Related

References

  • [123] 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). The traversal ports ClusterNode.pre_order of scipy.cluster.hierarchy, which that work names and does not describe.
source
PortfolioOptimisers.pre_order — Function
pre_order(a::ClusterNode, preorder_by::AbstractPreorderBy = PreorderTreeByID())

List the leaves below a node, left to right.

Walks the subtree below a in preorder and collects one property per leaf. An internal node adds no value. It only sets the order of its two children. get_node_property gives the property, so a caller changes preorder_by to collect a property other than the id of the node.

preorder_by is a positional argument, not a keyword.

Algorithm

  1. Make the stack curNode with 2 * a.level slots. The stack holds the path from a to the node that the walk reads. The level of a ClusterNode counts the leaves below it, so that path has at most a.level nodes.
  2. Put a in the first slot. Make the two sets lvisited and rvisited, which record the internal nodes whose left child and whose right child the walk pushed.
  3. Read the node nd on top of the stack.
  4. If nd is a leaf, push the value of get_node_property onto preorder and pop nd.
  5. If nd is an internal node outside lvisited, push its left child and add nd to lvisited.
  6. If nd is inside lvisited and outside rvisited, push its right child and add nd to rvisited.
  7. If nd is inside both sets, pop it, because the walk below it is finished.
  8. Repeat from step 3 until the stack is empty. The result is preorder, one property per leaf in left-to-right order.

Arguments

  • a: The root of the subtree to walk.
  • preorder_by: The traversal strategy. It sets the property that each leaf adds.

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

source
PortfolioOptimisers.to_tree — Function
to_tree(a::Hclust)

Rebuild a linkage matrix as a tree of ClusterNode objects.

Reads a Clustering.Hclust from Clustering.jl and makes 2N - 1 nodes. The N leaves come first, numbered 1:N in the asset order of the clustering. One node per merge comes next, numbered from N+1 in the order of the merges, so the node of the last merge is the root.

Algorithm

  1. Read N, the number of assets, from the length of a.order, and H, the element type of a.heights. Make d, a vector of 2N - 1 nodes of the type ClusterNode{Int, H}.
  2. Make one leaf per asset, d[i] = ClusterNode(i, nothing, nothing, zero(H)), so the leaves have the ids 1:N in the asset order of the clustering, and the height type of the merges.
  3. Walk the merges in the order of a.heights, which is the order in which they happened.
  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. Make the merge node ClusterNode(i + N, d[fi], d[fj], height) and store it at d[N + i], so the merge nodes have the ids N+1:2N-1 in the order of the merges.
  6. Return the node made last, which is the root, together with d.

Arguments

  • a: The dendrogram.

Returns

  • root::ClusterNode: The root of the tree, which is the node of the last merge.
  • nodes::Vector{ClusterNode{Int, H}}: All 2N - 1 nodes, the leaves first and then the merges in their order. The vector is not sorted by height. A caller that needs that order sorts it, as valid_k_clusters and optimal_number_clusters do.

Related

source
PortfolioOptimisers.optimal_number_clusters — Function
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)

Select the number of clusters at which to cut a dendrogram.

The SecondOrderDifference and SilhouetteScore methods score every candidate count up to the ceiling of onc. They take the count with the highest score at which the dendrogram has a valid cut. When validate_k_value rejects a count, the method tries the next highest score, so the answer is the best valid count and not always the best score.

Every method returns k alone. The non-hierarchical methods of the same name return the tuple (res, k), because a flat partition cannot be cut again, so they return the partition that they made at k.

Algorithm

The Integer method runs these steps. It replaces a stated count that is not valid with the nearest valid count, and it never refuses one.

  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 gives floor(Int, sqrt(N)).
  2. Lower k to max_k when it is larger.
  3. Rebuild the tree with to_tree and sort its nodes by descending height into nodes.
  4. Ask validate_k_value whether the tree has a valid cut at k, and return k when it has.
  5. Search upward from k + 1 to max_k for the first valid count ku, at the distance du = ku - k. If the search finds none, ku stays at k and du at 0.
  6. Search downward from k - 1 to 1 for the first valid count kl, at the distance dl = k - kl. This search always finds one when k > 1, because k = 1 is always a valid cut.
  7. Select the count. If one search alone found a count, take it. If both found one and du != dl, take the nearer. If both found one and du == dl, take ku when max_k - ku > kl - 1 and kl otherwise. So a tie goes to the side with more candidate counts beyond the count it found.

The SecondOrderDifference and SilhouetteScore methods run the steps that their own algorithm types state. Both pass the array of scores to valid_k_clusters, which takes the highest score at which the dendrogram has a valid cut. With two assets or fewer, the SecondOrderDifference method has no second-order difference to take and returns the number of assets.

Arguments

  • onc: The estimator of the number of clusters.

    • onc::OptimalNumberClusters{<:Any, <:Integer}: Takes the stated k, lowered to the ceiling. If that k is not valid, it takes the nearest valid count above or below, as steps 5 to 7 state.
    • onc::OptimalNumberClusters{<:Any, <:SecondOrderDifference}: Scores each count by the second-order difference of the within-cluster dispersions, then passes the scores to valid_k_clusters. The dispersion of a cut is the sum over its clusters of onc.alg.alg applied to the pairwise distances of the cluster.
    • onc::OptimalNumberClusters{<:Any, <:SilhouetteScore}: Scores each count by onc.alg.alg applied to the vector of per-asset silhouettes, then passes the scores to valid_k_clusters.
  • res: The dendrogram.

  • D: The distance matrix of the clustering.

Returns

  • k::Integer: The selected number of clusters. The dendrogram always has a valid cut at it.

Related

source
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)

Select the number of clusters for a non-hierarchical algorithm, and return the partition at that number.

The SecondOrderDifference and SilhouetteScore methods cluster the distance matrix once per candidate count and score each partition. Each method returns the partition at the selected count together with that count. A flat partition cannot be cut again at another count, so the method returns the partition that it already made.

No validity test

valid_k_clusters has no counterpart here. It rejects a count at which the dendrogram has no valid cut. A flat partition has no dendrogram, so each method takes the argmax of the scores as it is.

The dispersion under SecondOrderDifference is also a different quantity from the dispersion of the hierarchical branch. Here it is onc.alg.alg applied to the per-point costs of k-means, and not to the pairwise distances inside each cluster. The vector of costs has one entry per asset at every count, so a cluster of two assets never reduces it to one value. These are the dispersions at the counts 2 to 6 on a universe of 20 assets with two pairs of near-copies:

  • The hierarchical dispersions rise, 11.27, 26.04, 47.89, 112.96 and 114.11, and select 3.
  • The k-means dispersions fall, 6.58, 2.83, 2.57, 2.17 and 2.06, and select 2.

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 gives floor(Int, sqrt(N)).
  2. Lower k to max_k when it is larger.
  3. Cluster D once at k into res with get_k_clusters_from_alg.
  4. Return res and k.

The SecondOrderDifference and SilhouetteScore methods run the steps that their own algorithm types state, with one difference. No dendrogram rejects a count, so each method takes the argmax as it is. Each method then returns cluster_lvls[k], the run that it made at the selected count, together with k. It does not run the algorithm again.

Arguments

  • onc: The estimator of the number of clusters.

    • onc::OptimalNumberClusters{<:Any, <:Integer}: Takes the stated k, lowered to the ceiling.
    • onc::OptimalNumberClusters{<:Any, <:SecondOrderDifference}: Scores each count by the second-order difference of onc.alg.alg applied to the per-point costs of the run at that count, 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: The non-hierarchical clustering algorithm, for example KMeansAlgorithm.

  • D: The distance matrix.

Returns

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

The method returns the two as a tuple. The hierarchical methods of the same name in 03_Hierarchical.jl return k alone, because the caller can cut the dendrogram again at any count.

Related

source
PortfolioOptimisers.clusterise — Method
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, makes a dendrogram under the linkage of cle.alg, and selects the number of clusters with cle.onc.

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. Refuse each asset that the reader could not estimate with assert_distance_reader_rows. Then refuse any other NaN in D.
  3. Cluster D into the dendrogram res under the linkage cle.alg.linkage with branch_ordered_hclust on Val(branchorder).
  4. Select the number of clusters k with optimal_number_clusters(cle.onc, res, D).
  5. Return Clusters(; res = res, S = S, D = D, k = k). The field P keeps its default, nothing, because the clustering ran on D itself.

Arguments

  • cle: The clustering estimator.
  • X: The data matrix, with one row per observation and one column per asset when dims = 1.
  • branchorder: The order of the branches. :optimal orders the leaves with optimal_leaf_order!. Clustering.hclust takes any other value, and it accepts :barjoseph and :r.
  • dims: Dimension along which the computation runs.
  • kwargs...: Keyword arguments for cor_and_dist.

Validation

  • No diagonal entry of D is NaN. Raises a DistanceReaderRefusalError that names the columns of the assets that the reader could not estimate. A fit catches it and drops those assets.
  • D holds no other NaN. Raises a DomainError that names the first NaN cell, a pair, through assert_no_nan_distance. An undetermined pair gives it, and an asset with zero variance does not, because the first check refuses its NaN row. Without the check, Clustering.hclust refuses D as not symmetric, because NaN is not equal to itself.

Returns

  • res::Clusters: The dendrogram, the similarity matrix, the distance matrix and the number of clusters.

Related

source
Clustering.assignments — Function
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.

The function has one method for each clustering family. The two methods differ only in the source of the labels. A dendrogram has no labels until a cut makes them, and a flat partition already holds them. 03_Hierarchical.jl declares the method for a Clustering.Hclust, and this file declares the method for a Clustering.ClusteringResult.

Algorithm

  1. If clr.res is a Clustering.Hclust, it is a dendrogram with no labels. Cut it at clr.k with Clustering.cutree, which gives one label per asset.
  2. If clr.res is a Clustering.ClusteringResult, one run at one count made it, and it holds its own labels. Read clr.res.assignments.

Arguments

  • clr: The clustering result to label.

Returns

  • idx::AbstractVector{<:Integer}: One label per asset, over 1:clr.k, in the order of the asset axis of the universe.

Related

source

References

[12]
D. Cajas. Advanced Portfolio Optimization: A Cutting-edge Quantitative Approach (Springer Nature Switzerland, 2025).
[123]
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).