Hierarchical
PortfolioOptimisers.ClusterNode — Type
struct ClusterNode{T, H} <: AbstractResultBinds 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, ornothingfor a leaf.
right: The right child, ornothingfor a leaf.
height: The height of the node in the dendrogram.
level: The number of leaves in the subtree below the node,1for a leaf. It is the fourth column of a linkage matrix, andpre_ordersizes its traversal stack from it.
Constructors
ClusterNode( id, left::Option{<:ClusterNode} = nothing, right::Option{<:ClusterNode} = nothing, height::Number = 0.0, level::Int = 1) -> ClusterNodeArguments 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
leftandrightare eachnothingor aClusterNode{T, H}, withTthe type ofidandHthe type ofheightof the new node. A child of another type throws aDomainErrorthat names its type.
Examples
julia> ClusterNode(1)ClusterNode id ┼ Int64: 1 left ┼ nothing right ┼ nothing height ┼ Float64: 0.0 level ┴ Int64: 1Related
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
ClusterNodeandto_treeofscipy.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.
PortfolioOptimisers.AbstractPreorderBy — Type
abstract type AbstractPreorderBy <: AbstractAlgorithmAbstract 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 thataadds 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
PortfolioOptimisers.PreorderTreeByID — Type
struct PreorderTreeByID <: AbstractPreorderByCollects 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_orderofscipy.cluster.hierarchy, which that work names and does not describe.
PortfolioOptimisers.get_node_property — Function
get_node_property(preorder_by::PreorderTreeByID, a::ClusterNode)Return the property that a leaf adds to the output of a preorder traversal.
The PreorderTreeByID method returns the id of the node.
Arguments
preorder_by: The traversal strategy.a: The node.
Returns
id: The identifier of the node.
Related
PortfolioOptimisers.is_leaf — Function
is_leaf(a::ClusterNode)Test whether a node is a leaf, which is the node of one asset.
It tests left alone. A ClusterNode has both children or neither, so one test is enough.
Arguments
a: The node to check.
Returns
flag::Bool:truewhen the node has no children.
Examples
julia> PortfolioOptimisers.is_leaf(ClusterNode(1))trueRelated
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
- Make the stack
curNodewith2 * a.levelslots. The stack holds the path fromato the node that the walk reads. Thelevelof aClusterNodecounts the leaves below it, so that path has at mosta.levelnodes. - Put
ain the first slot. Make the two setslvisitedandrvisited, which record the internal nodes whose left child and whose right child the walk pushed. - Read the node
ndon top of the stack. - If
ndis a leaf, push the value ofget_node_propertyontopreorderand popnd. - If
ndis an internal node outsidelvisited, push itsleftchild and addndtolvisited. - If
ndis insidelvisitedand outsidervisited, push itsrightchild and addndtorvisited. - If
ndis inside both sets, pop it, because the walk below it is finished. - 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 isa.level. The element type is the type ofget_node_property(preorder_by, a), so the default strategy gives aVector{Int}.
Related
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
- Read
N, the number of assets, from the length ofa.order, andH, the element type ofa.heights. Maked, a vector of2N - 1nodes of the typeClusterNode{Int, H}. - Make one leaf per asset,
d[i] = ClusterNode(i, nothing, nothing, zero(H)), so the leaves have the ids1:Nin the asset order of the clustering, and the height type of the merges. - Walk the merges in the order of
a.heights, which is the order in which they happened. - Resolve each side of row
iofa.mergesto an index intod. A negative entryfinames the asset-fi, and a positive entry names the mergefi + N. - Make the merge node
ClusterNode(i + N, d[fi], d[fj], height)and store it atd[N + i], so the merge nodes have the idsN+1:2N-1in the order of the merges. - 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}}: All2N - 1nodes, 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, asvalid_k_clustersandoptimal_number_clustersdo.
Related
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.
- Read the stated count
onc.algintok, and the ceiling intomax_k. The ceiling ismin(floor(Int, sqrt(N)), onc.max_k), whereNis the number of assets. Amax_kofnothinggivesfloor(Int, sqrt(N)). - Lower
ktomax_kwhen it is larger. - Rebuild the tree with
to_treeand sort its nodes by descending height intonodes. - Ask
validate_k_valuewhether the tree has a valid cut atk, and returnkwhen it has. - Search upward from
k + 1tomax_kfor the first valid countku, at the distancedu = ku - k. If the search finds none,kustays atkandduat0. - Search downward from
k - 1to1for the first valid countkl, at the distancedl = k - kl. This search always finds one whenk > 1, becausek = 1is always a valid cut. - 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 anddu == dl, takekuwhenmax_k - ku > kl - 1andklotherwise. 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 statedk, lowered to the ceiling. If thatkis 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 tovalid_k_clusters. The dispersion of a cut is the sum over its clusters ofonc.alg.algapplied to the pairwise distances of the cluster.onc::OptimalNumberClusters{<:Any, <:SilhouetteScore}: Scores each count byonc.alg.algapplied to the vector of per-asset silhouettes, then passes the scores tovalid_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
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.
- Read the stated count
onc.algintok, and the ceiling intomax_k. The ceiling ismin(floor(Int, sqrt(N)), onc.max_k), whereNis the number of assets. Amax_kofnothinggivesfloor(Int, sqrt(N)). - Lower
ktomax_kwhen it is larger. - Cluster
Donce atkintoreswithget_k_clusters_from_alg. - Return
resandk.
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 statedk, lowered to the ceiling.onc::OptimalNumberClusters{<:Any, <:SecondOrderDifference}: Scores each count by the second-order difference ofonc.alg.algapplied to the per-point costs of the run at that count, and takes theargmax.onc::OptimalNumberClusters{<:Any, <:SilhouetteScore}: Scores each count byonc.alg.algapplied to the vector of per-asset silhouettes, and takes theargmax.
alg: The non-hierarchical clustering algorithm, for exampleKMeansAlgorithm.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
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
- Estimate the similarity matrix
Sand the distance matrixDfromXwithcor_and_dist, undercle.deandcle.ce. - Refuse each asset that the reader could not estimate with
assert_distance_reader_rows. Then refuse any otherNaNinD. - Cluster
Dinto the dendrogramresunder the linkagecle.alg.linkagewithbranch_ordered_hclustonVal(branchorder). - Select the number of clusters
kwithoptimal_number_clusters(cle.onc, res, D). - Return
Clusters(; res = res, S = S, D = D, k = k). The fieldPkeeps its default,nothing, because the clustering ran onDitself.
Arguments
cle: The clustering estimator.X: The data matrix, with one row per observation and one column per asset whendims = 1.branchorder: The order of the branches.:optimalorders the leaves withoptimal_leaf_order!.Clustering.hclusttakes any other value, and it accepts:barjosephand:r.dims: Dimension along which the computation runs.kwargs...: Keyword arguments forcor_and_dist.
Validation
- No diagonal entry of
DisNaN. Raises aDistanceReaderRefusalErrorthat names the columns of the assets that the reader could not estimate. A fit catches it and drops those assets. Dholds no otherNaN. Raises aDomainErrorthat names the firstNaNcell, a pair, throughassert_no_nan_distance. An undetermined pair gives it, and an asset with zero variance does not, because the first check refuses itsNaNrow. Without the check,Clustering.hclustrefusesDas not symmetric, becauseNaNis not equal to itself.
Returns
res::Clusters: The dendrogram, the similarity matrix, the distance matrix and the number of clusters.
Related
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
- If
clr.resis aClustering.Hclust, it is a dendrogram with no labels. Cut it atclr.kwithClustering.cutree, which gives one label per asset. - If
clr.resis aClustering.ClusteringResult, one run at one count made it, and it holds its own labels. Readclr.res.assignments.
Arguments
clr: The clustering result to label.
Returns
idx::AbstractVector{<:Integer}: One label per asset, over1:clr.k, in the order of the asset axis of the universe.
Related
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).