Hierarchical: private API
PortfolioOptimisers.VecClN — Type
const VecClN = AbstractVector{<:ClusterNode}Alias for a vector of ClusterNode objects.
to_tree returns one, with the leaves first and the merges after them. validate_k_value walks one sorted by descending height.
Related
PortfolioOptimisers.join_leaf_orders! — Function
join_leaf_orders!(tab::NamedTuple, A::AbstractVector{Int}, B::AbstractVector{Int},
D::MatNum)Fill the least cost of each order of a merge from the least costs of the orders of its two children.
A merge joins the child with the leaves A to the child with the leaves B. An order of the merge starts at a leaf i of A and stops at a leaf j of B. The cost of an order is the sum of the distances between its adjacent leaves.
Mathematical definition
\[\begin{align} M(i, j) &= \underset{k \in A_i,\, l \in B_j}{\min} M(i, k) + D_{kl} + M(l, j)\,, \\ M(j, i) &= M(i, j)\,. \end{align}\]
Where:
- $M(i, j)$: the least cost of an order of the leaves below a merge that starts at leaf $i$ and stops at leaf $j$, with $M(i, i) = 0$ for a leaf.
- $A_i$: the leaves of $A$ that can stop an order of $A$ that starts at $i$. For a child with one leaf it is $\{i\}$. For a child that is a merge it holds the leaves on the other side of that merge from $i$.
- $B_j$: the leaves of $B$ that can start an order of $B$ that stops at $j$, by the same rule.
- $D_{kl}$: the distance between leaves $k$ and $l$.
Algorithm
- For each leaf
iofAandlofB, find the leasttab.M[i, k] + D[k, l]over the leaveskofAthat can stop an order that starts ati. Store the cost inT[i, l]and the leafkinK[i, l]. Two leavesi ≠ kqualify whentab.sideputs them on different sides of their child. The one leaf of a child with one leaf qualifies with itself. - For each leaf
iofAandjofB, find the leastT[i, l] + tab.M[l, j]over the leaveslofBthat qualify withjby the same rule. Store it intab.M[i, j]. - Write the same cost to
tab.M[j, i]. Write the leafktotab.S[i, j]and the leafltotab.S[j, i], so that the order fromitojis the order fromitotab.S[i, j], followed by the order fromtab.S[j, i]toj.
A tie goes to the first least value, so the result is deterministic.
Arguments
tab: The tables of the dynamic programme. The function changes them in place.M: The least cost of each pair of end leaves, $M(i, j)$ above.S: The leaf next to the split of each order, as step 3 states.side: The side of its child that holds each leaf,1for the left side and2for the right side.
A,B: The leaves below the left child and below the right child of the merge.D: The distance matrix.
Returns
tab::NamedTuple: The same tables, with the pairs ofAandBfilled.
Related
PortfolioOptimisers.trace_leaf_order — Function
trace_leaf_order(S::AbstractMatrix{Int}, i::Int, j::Int)Rebuild the order from leaf i to leaf j from the split leaves that join_leaf_orders! wrote.
Algorithm
- Start a stack that holds the pair
(i, j). - Take the last pair
(a, b)from the stack. Whena == b, put the leafaat the end oforder. - Otherwise, put
(S[b, a], b)and then(a, S[a, b])on the stack, so that the order fromatoS[a, b]comes first. - Repeat from step 2 until the stack is empty.
The stack replaces a recursion, so a tree as deep as its count of leaves does not overflow the call stack.
Arguments
S: The split leaves of each pair of end leaves.i,j: The first and the last leaf of the order.
Returns
order::Vector{Int}: The leaves, in the order fromitoj.
Related
PortfolioOptimisers.optimal_leaf_order! — Function
optimal_leaf_order!(ml::AbstractVector{Int}, mr::AbstractVector{Int}, D::MatNum)Order the leaves of a dendrogram so that the sum of the distances between adjacent leaves is the least that the tree permits.
A flip of the two children of a merge keeps the tree and reverses the leaves below that merge. This method solves the problem of [300] exactly by dynamic programming. It finds the least sum over every combination of flips in $O(N^3)$ time and $O(N^2)$ memory. The algorithm of [300] runs in $O(N^4)$ time, and Section 3.2 of [301] gives the $O(N^3)$ form. Its temporary table, Equation 3, is the table T of join_leaf_orders!. Both works maximise a sum of similarities, and this method minimises the same sum of distances. Clustering.orderbranches_barjoseph! is a heuristic from the same source. It decides each merge once, from its four outermost leaves, so it can miss the least sum.
Mathematical definition
\[\begin{align} \boldsymbol{\pi}^{\star} &= \underset{\boldsymbol{\pi} \in \Pi(\mathcal{T})}{\arg\min} \sum_{t=1}^{N-1} D_{\pi_t \pi_{t+1}}\,. \end{align}\]
Where:
- $\Pi(\mathcal{T})$: the orders of the leaves that the dendrogram $\mathcal{T}$ permits, one for each combination of flips.
- $\pi_t$: the leaf at position $t$ of the order $\boldsymbol{\pi}$.
- $D_{kl}$: the distance between leaves $k$ and $l$.
- $N$: the number of leaves.
Algorithm
- Make the tables
tab. They hold the costsM, which are zero for a leaf alone, the split leavesSand the sidesside. - Walk the merges in their order. For merge
v, take the leavesAbelowml[v]andBbelowmr[v], and fill the costs of the pairs ofAandBwithjoin_leaf_orders!. Then mark the leaves ofAas side1and the leaves ofBas side2. - Take the pair
(i, j)of the last merge with the least cost, withibelowml[end]. - Rebuild the order
orderfromitojwithtrace_leaf_order. - Swap
ml[v]andmr[v]for each merge whose left child does not come first inorder.
Arguments
ml,mr: The left and the right child of each merge, in the form ofClustering.hclust. An entry-iis the leafi, a positive entryvis the mergev, and a merge comes after its children. Step 5 changes them in place.D: The distance matrix of the leaves.
Returns
order::Vector{Int}: The leaves in the order that step 4 rebuilds. It is the leaf order ofClustering.Hclustfor the merges that step 5 writes.
Related
References
- [300] Z. Bar-Joseph, D. K. Gifford and T. S. Jaakkola. Fast optimal leaf ordering for hierarchical clustering. Bioinformatics 17, S22–S29 (2001). Sections "Problem definition" and "Algorithm", for the problem and the recurrence.
- [301] Z. Bar-Joseph, E. D. Demaine, D. K. Gifford, N. Srebro, A. M. Hamel and T. S. Jaakkola. K-ary clustering with optimal leaf ordering for gene expression data. Bioinformatics 19, 1070–1078 (2003). Section 3.2, Equations 2-4, for the $O(N^3)$ time.
PortfolioOptimisers.branch_ordered_hclust — Function
branch_ordered_hclust(D::MatNum, linkage::Symbol, ::Val{:optimal})Cluster D with Clustering.hclust, and order its leaves with the least sum of the distances between adjacent leaves that the tree permits.
Algorithm
- Cluster
DintoreswithClustering.hclustunderlinkageand its branch order:barjoseph. The branch order flips merges and moves no merge, so the merges keep the order in which the linkage made them. - Order the leaves of
resintoorderwithoptimal_leaf_order!on the two columns ofres.mergesand onD. - Return
Clustering.Hclust(res.merges, res.heights, order, res.linkage).
Arguments
D: The distance matrix. The cost of an order is the sum of the entries ofDitself, also when the linkage is:ward, which clusters the squares ofD.linkage: The linkage ofClustering.hclust.
Returns
res::Clustering.Hclust: The dendrogram, with the leaf order of least cost.
Related
branch_ordered_hclust(D::MatNum, linkage::Symbol, ::Val{B}) where {B}Cluster D with Clustering.hclust under linkage and its own branch order B.
B = :barjoseph gives the heuristic of Clustering.orderbranches_barjoseph!, and B = :r gives the order of the R function hclust. Clustering.hclust refuses any other value with an ArgumentError.
Arguments
D: The distance matrix.linkage: The linkage ofClustering.hclust.
Returns
res::Clustering.Hclust: The dendrogram.
Related
PortfolioOptimisers.validate_k_value — Function
validate_k_value(res::Clustering.Hclust, nodes::VecClN, k::Integer)Test whether the dendrogram has a valid cut into k clusters.
Cuts the tree at k, then walks the k - 1 tallest nodes. Each internal node among them must hold at least one of the k clusters wholly inside one of its two subtrees. A node that holds no such cluster makes k invalid.
Only a tie in the heights makes the answer false
When every height is distinct, the k - 1 tallest nodes are the merges that the cut removes. Each of them then holds a whole cluster below one of its children, and the answer is true. Two merges of equal height break that match. sortperm orders nodes and Clustering.cutree makes the cut, and the two can disagree inside a tie, so the walk can reach a merge that the cut keeps. A dendrogram with distinct heights rejects no k. A balanced tree of eight leaves, with four merges at height 1, two at height 2 and one at height 3, admits only k in 1, 2, 4 and 8.
k = 1 is always valid, because the walk of step 3 is then empty.
Algorithm
- Cut the tree at
kwithClustering.cutree. The result isidx, one label per asset. - Collect the assets of each label into
clusters, one vector of asset indices per cluster. - Walk the
k - 1tallest entries ofnodes, and skip a leaf among them. - List the leaves below the
leftchild and below therightchild of the node withpre_order. Call the two listslnandrn. - Count the clusters of step 2 that lie wholly inside
lnor wholly insidern. Answerfalseat once when the count is zero. - Answer
truewhen every node of step 3 holds at least one such cluster.
Arguments
res: The dendrogram.nodes: The nodes of the tree ofres, sorted by descending height.k: The number of clusters to test.
Returns
flag::Bool:trueifkis a valid number of clusters,falseotherwise.
Related
PortfolioOptimisers.valid_k_clusters — Function
valid_k_clusters(res::Hclust, arr::VecNum)Take the number of clusters with the highest score at which the dendrogram has a valid cut.
The candidate is argmax(arr), or length(arr) when no entry of arr is finite. When validate_k_value rejects a candidate, the function sets its score to typemin(eltype(arr)) and takes the next candidate. When a rejection leaves no finite entry, the answer is 1.
The function does not check the scores, and it does not reject a NaN. In an array that holds a NaN, argmax returns the index of the first NaN, whatever the real scores are. An array of NaN alone has no finite entry, so it takes the length(arr) branch, and the answer is 1 when the tree rejects that candidate. The default measure of SecondOrderDifference gives no NaN for a cluster of two assets. The standard deviation of one value is undefined, so the measure divides by one, and the cluster contributes its one pairwise distance.
Algorithm
- Rebuild the tree with
to_treeand sort its nodes by descending height intonodes. - Take the candidate
k. It isargmax(arr), orlength(arr)when no entry ofarris finite. - Ask
validate_k_valuewhether the tree has a valid cut atk, and returnkwhen it has. - Return
1when step 3 rejectedkand no entry ofarris finite. A non-finite entry set totypeminstays non-finite, so step 2 would offer the same candidate again. - Write
typemin(eltype(arr))intoarr[k]and repeat from step 2.
The loop ends after at most length(arr) rejections. Step 5 sets a rejected entry to typemin, so argmax does not offer it again while a finite entry is left. When no finite entry is left, step 2 takes the length(arr) branch, and step 4 answers 1 if the tree rejects it. A dendrogram with distinct heights rejects no candidate, so there the first candidate is the answer.
Arguments
res: The dendrogram.arr: The score of each candidate number of clusters. The function changes it in place. It sets the score of a rejected candidate totypemin(eltype(arr)), so that the next pass skips it. Both callers pass a local array of scores and do not read it after the call, so the change reaches no caller.
Returns
k::Integer: A number of clusters at which the dendrogram has a valid cut.
Related
References
- [300]
- Z. Bar-Joseph, D. K. Gifford and T. S. Jaakkola. Fast optimal leaf ordering for hierarchical clustering. Bioinformatics 17, S22–S29 (2001).
- [301]
- Z. Bar-Joseph, E. D. Demaine, D. K. Gifford, N. Srebro, A. M. Hamel and T. S. Jaakkola. K-ary clustering with optimal leaf ordering for gene expression data. Bioinformatics 19, 1070–1078 (2003).