Hierarchical: private API

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

  1. For each leaf i of A and l of B, find the least tab.M[i, k] + D[k, l] over the leaves k of A that can stop an order that starts at i. Store the cost in T[i, l] and the leaf k in K[i, l]. Two leaves i ≠ k qualify when tab.side puts them on different sides of their child. The one leaf of a child with one leaf qualifies with itself.
  2. For each leaf i of A and j of B, find the least T[i, l] + tab.M[l, j] over the leaves l of B that qualify with j by the same rule. Store it in tab.M[i, j].
  3. Write the same cost to tab.M[j, i]. Write the leaf k to tab.S[i, j] and the leaf l to tab.S[j, i], so that the order from i to j is the order from i to tab.S[i, j], followed by the order from tab.S[j, i] to j.

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, 1 for the left side and 2 for 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 of A and B filled.

Related

source
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

  1. Start a stack that holds the pair (i, j).
  2. Take the last pair (a, b) from the stack. When a == b, put the leaf a at the end of order.
  3. Otherwise, put (S[b, a], b) and then (a, S[a, b]) on the stack, so that the order from a to S[a, b] comes first.
  4. 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 from i to j.

Related

source
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

  1. Make the tables tab. They hold the costs M, which are zero for a leaf alone, the split leaves S and the sides side.
  2. Walk the merges in their order. For merge v, take the leaves A below ml[v] and B below mr[v], and fill the costs of the pairs of A and B with join_leaf_orders!. Then mark the leaves of A as side 1 and the leaves of B as side 2.
  3. Take the pair (i, j) of the last merge with the least cost, with i below ml[end].
  4. Rebuild the order order from i to j with trace_leaf_order.
  5. Swap ml[v] and mr[v] for each merge whose left child does not come first in order.

Arguments

  • ml, mr: The left and the right child of each merge, in the form of Clustering.hclust. An entry -i is the leaf i, a positive entry v is the merge v, 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 of Clustering.Hclust for 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.
source
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

  1. Cluster D into res with Clustering.hclust under linkage and 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.
  2. Order the leaves of res into order with optimal_leaf_order! on the two columns of res.merges and on D.
  3. 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 of D itself, also when the linkage is :ward, which clusters the squares of D.
  • linkage: The linkage of Clustering.hclust.

Returns

  • res::Clustering.Hclust: The dendrogram, with the leaf order of least cost.

Related

source
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 of Clustering.hclust.

Returns

  • res::Clustering.Hclust: The dendrogram.

Related

source
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

  1. Cut the tree at k with Clustering.cutree. The result is idx, one label per asset.
  2. Collect the assets of each label into clusters, one vector of asset indices per cluster.
  3. Walk the k - 1 tallest entries of nodes, and skip a leaf among them.
  4. List the leaves below the left child and below the right child of the node with pre_order. Call the two lists ln and rn.
  5. Count the clusters of step 2 that lie wholly inside ln or wholly inside rn. Answer false at once when the count is zero.
  6. Answer true when every node of step 3 holds at least one such cluster.

Arguments

  • res: The dendrogram.
  • nodes: The nodes of the tree of res, sorted by descending height.
  • k: The number of clusters to test.

Returns

  • flag::Bool: true if k is a valid number of clusters, false otherwise.

Related

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

Warning

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

  1. Rebuild the tree with to_tree and sort its nodes by descending height into nodes.
  2. Take the candidate k. It is argmax(arr), or length(arr) when no entry of arr is finite.
  3. Ask validate_k_value whether the tree has a valid cut at k, and return k when it has.
  4. Return 1 when step 3 rejected k and no entry of arr is finite. A non-finite entry set to typemin stays non-finite, so step 2 would offer the same candidate again.
  5. Write typemin(eltype(arr)) into arr[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 to typemin(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

source

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