GitHub

Hierarchical: private API

PortfolioOptimisers.validate_k_value — Function
validate_k_value(res::Clustering.Hclust, nodes::VecClN, k::Integer)

Can this tree be cut into exactly k clusters?

Cuts the tree at k, then walks the k - 1 tallest nodes. Each non-leaf node among them must have at least one of the k clusters contained wholly within one of its two subtrees; a node for which no cluster does 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, so each of them carries a whole cluster below one of its children and the answer is true. Two merges of equal height break that correspondence, because nodes is ordered by sortperm and the cut is not, so the walk can reach a node the cut left standing. A dendrogram with distinct heights rejects no k; a tree with tied merges rejects every k whose cut falls inside a tie.

k = 1 is always valid: the walk of step 3 is then empty.

Algorithm

  1. Cut the tree at k with Clustering.cutree, giving idx, one label per asset.
  2. Collect the assets carrying each label into clusters, one vector of asset indices per cluster.
  3. Walk the k - 1 tallest entries of nodes, skipping any leaf among them.
  4. List the leaves below the node's left child and below its right child with pre_order, giving ln and rn.
  5. Count the clusters of step 2 that lie wholly inside ln or wholly inside rn, giving count. A count of zero answers false at once.
  6. Answer true once every node of step 3 has carried at least one such cluster.

Arguments

  • res: Hierarchical clustering object.
  • nodes: Vector of nodes in the clustering tree, sorted by descending height.
  • k: Number of clusters to validate.

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 highest-scoring number of clusters the tree can be cut at.

Takes a candidate, tests it with validate_k_value, and on failure blanks that entry to typemin(eltype(arr)) and takes the next. The candidate is argmax(arr), or length(arr) when no entry of arr is finite. It returns 1 instead when a rejected candidate leaves no finite entry behind.

Warning

The scores are trusted as they arrive, and a NaN is not rejected. argmax returns the index of the first NaN in an array that carries one, ahead of every real score. An array that is NaN throughout takes the length(arr) branch instead, because a NaN is neither finite nor infinite, and answers 1 when the tree rejects that candidate. SecondOrderDifference's default measure no longer produces such an array: an undefined standard deviation divides by one, so a cluster of exactly two assets contributes its single pairwise distance rather than a NaN.

Algorithm

  1. Rebuild the tree with to_tree and order its nodes by descending height, giving nodes.
  2. Take the candidate k: argmax(arr), or length(arr) when no entry of arr is finite.
  3. Ask validate_k_value whether the tree can be cut at k, and return k when it can.
  4. Return 1 when step 3 rejected k and no entry of arr is finite, because blanking a non-finite entry offers 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 blanks a rejected entry, so argmax never offers it twice; once every entry is typemin step 2 takes the length(arr) branch, and step 4 then answers 1. The search usually ends far sooner, because k = 1 is always a valid cut.

Arguments

  • res: Hierarchical clustering object.
  • arr: Score for each candidate number of clusters. Modified in place: a candidate that fails validation is set to typemin(eltype(arr)) so that the next iteration skips it. Both callers pass a local score array and neither reads it after the call, so the mutation reaches no caller.

Returns

  • k::Integer: Valid number of clusters.

Related

source