DBHT Dendrogram: private API

The functions on this page turn the clusters of DBHTs into a hierarchy, after the functions on the bubble tree page assign the assets to clusters. HierarchyConstruct4s takes the clusters and the bubble membership, and returns a linkage matrix in the Matlab format. turn_into_Hclust_merges converts that matrix into the format of Clustering.Hclust, and it is the only function here that uses that format.

PortfolioOptimisers.DendroConstruct — Function
DendroConstruct(Zi::MatNum, LabelVec1::VecNum,
                LabelVec2::VecNum,
                LinkageDist::Num_VecNum)

Append one merge to a linkage matrix.

The function finds the merge from the change between two label vectors, and it appends one row for it to the linkage matrix. build_link_and_dendro and HierarchyConstruct4s call it once for each merge of the dendrogram.

Algorithm

  1. Take indx, the vertices whose label is different in LabelVec1 and LabelVec2. The merge moved those vertices.
  2. Read the labels that LabelVec1 gave them, drop the repeats and sort them. A merge joins two labels, so exactly two labels remain.
  3. Append one row to Zi, which holds those two labels and then LinkageDist.

Arguments

  • Zi: i × 3 linkage matrix at iteration i, in the format of the Matlab output. Each row holds the two merged labels and the height of the merge.
  • LabelVec1: N × 1 label vector of the vertices, for the last valid iteration.
  • LabelVec2: N × 1 label vector of the vertices, for the trial iteration.
  • LinkageDist: Height of the current merge, which the function writes into the third column.

Returns

Related

source
PortfolioOptimisers.LinkageFunction — Function
LinkageFunction(d::MatNum, labelvec::VecNum)

Find the pair of clusters of smallest union diameter in a bubble.

The function scores every pair of clusters that labelvec names by the diameter of their union under the distance matrix d, and it returns the pair of smallest score. The diameter is the largest non-zero distance inside the union, so the score is a complete linkage. build_link_and_dendro and HierarchyConstruct4s call it to select each merge.

Mathematical definition

\[\begin{align} \delta(I,\, J) &= \underset{u,\,v \in \mathcal{C}_{I} \cup \mathcal{C}_{J},\; d_{u,\,v} \neq 0}{\max}\; d_{u,\,v}\,, \\ (I^{\star},\, J^{\star}) &= \underset{I < J}{\arg\min}\; \delta(I,\, J)\,. \end{align}\]

Where:

  • $d_{u,\,v}$: Distance between vertices $u$ and $v$, the entry of the input matrix.
  • $\mathcal{C}_{I}$: Vertices that carry label $I$.
  • $\delta(I,\, J)$: Diameter of the union of the two clusters.

The function scores the union, not the cut between the two clusters, so a distance between two members of one cluster can set $\delta$. A pair whose union has no non-zero distance scores $0$, the smallest possible score.

Algorithm

  1. Take lvec, the sorted distinct labels of labelvec.
  2. For each pair (r, c) of labels with r < c, select the vertices that have either label.
  3. Take the largest non-zero entry of the distance submatrix on those vertices, and record (lvec[r], lvec[c], value) as a row of Links. Record 0 as the value when the submatrix has no non-zero entry.
  4. Take the row of smallest value, which gives the pair PairLink and the score dvu.

Arguments

  • d: Nv×Nv distance matrix of the vertices of a bubble, a cluster or the graph. Row and column i are the same vertex, and entry i of labelvec names its cluster.
  • labelvec: Nv×1 label vector of the same vertices.

Returns

  • PairLink::Vector{Int}: 2 × 1 vector of the two cluster labels of the selected pair.
  • dvu::Number: Diameter of the union of that pair, the smallest such value over every pair.

Related

source
PortfolioOptimisers.build_link_and_dendro — Function
build_link_and_dendro(
    rg::AbstractRange,
    dpm::MatNum,
    LabelVec::VecNum,
    LabelVec1::VecNum,
    LabelVec2::VecNum,
    V::VecNum,
    nc::Number,
    Z::MatNum
)

Merge the clusters of a bubble or a cluster one pair at a time, and append each merge to the linkage matrix.

At each step the function merges the pair of clusters that LinkageFunction selects, and it appends the row of the merge to the linkage matrix with DendroConstruct. HierarchyConstruct4s calls it for each bubble and for each cluster.

Algorithm

  1. Take the pair of smallest union diameter with LinkageFunction over dpm and LabelVec.
  2. Give both members of the pair the label maximum(LabelVec1) + 1, so the merged cluster takes a label no vertex carries yet.
  3. Write the merged labels back into LabelVec2 at the vertices V.
  4. Append one row to Z with DendroConstruct, at the height 1 / nc.
  5. Subtract one from nc, and copy LabelVec2 into LabelVec1.
  6. Repeat from step 1 once for each element of rg.

Arguments

  • rg: Range whose length sets the number of merges. The function does not read its values.
  • dpm: Nv×Nv distance matrix of the vertices of the bubble or cluster, in the order of V.
  • LabelVec: Nv×1 label vector of those vertices. Step 2 changes it in place.
  • LabelVec1: N × 1 label vector of every vertex, for the last valid iteration.
  • LabelVec2: N × 1 label vector of every vertex, for the trial iteration. Step 3 changes it in place.
  • V: Nv×1 vector of the vertices of the bubble or cluster, which index the rows of LabelVec1.
  • nc::Number: Merge counter. Step 4 writes the height 1 / nc and step 5 lowers it by one, so the heights of a run rise towards 1.
  • Z: Current linkage matrix, with three columns.

Returns

  • Z::MatNum: Linkage matrix after every merge of the range, one row longer per merge.
  • nc::Number: Merge counter, lowered by the number of merges.
  • LabelVec1::VecNum: N × 1 label vector for the next iteration, with the merged labels.

Related

source
PortfolioOptimisers.HierarchyConstruct4s — Function
HierarchyConstruct4s(
    Rpm::MatNum,
    Dpm::MatNum,
    Tc::VecNum,
    Mv::MatNum
)

Build the dendrogram of the Direct Bubble Hierarchical Tree (DBHT), first inside each cluster and then across the clusters.

The function first merges the vertices inside each discrete cluster, bubble by bubble, on the bubble tree of the Planar Maximally Filtered Graph (PMFG). It then merges the clusters into one hierarchy.

Algorithm

  1. Give every vertex its own label in LabelVec1, and build E, the N × maximum(Tc) indicator of the discrete clustering Tc.
  2. For each cluster k, restrict Mv to the vertices of that cluster, which gives Mc. Assign each of them to exactly one bubble with BubbleMember, which gives Mvv. Set the merge counter nc to the vertex count of the cluster minus one.
  3. For each bubble of the cluster that holds more than one vertex, merge its vertices with build_link_and_dendro over length(V) - 1 steps, on the distance submatrix of that bubble.
  4. Merge the bubbles of the cluster with build_link_and_dendro over length(Bub) - 1 steps, on the distance submatrix of the whole cluster. Steps 3 and 4 share one nc, so the heights of a cluster rise across both steps.
  5. Repeat steps 2 to 4 for each cluster, which leaves one label for each cluster.
  6. Merge the clusters over length(kvec) - 1 steps. At each step, take the pair of smallest union diameter with LinkageFunction over all of Dpm, and give both sides a new label.
  7. Write the height of that merge from dcl, not from the score of step 6. dcl starts at 1 for every vertex, and each merge sets both sides to the sum of the two, so the height counts the clusters that the merge joins. Thus every merge across clusters is above every merge inside a cluster, whose height is never more than 1.

Arguments

  • Rpm: N × N sparse weighted adjacency matrix of the PMFG. Only BubbleMember reads it.
  • Dpm: N × N matrix of the shortest path lengths of the PMFG. Each linkage score comes from it.
  • Tc: N × 1 cluster membership vector. Tc[n] = k means that vertex n belongs to the k-th discrete cluster.
  • Mv: N × Nb bubble membership matrix. Mv[n, bi] = 1 means that vertex n is a vertex of bubble bi.

Returns

  • Z::MatNum: (N-1)×3 linkage matrix in the format of the Matlab output. Each row holds the two merged labels and the height of the merge. turn_into_Hclust_merges converts it to the Clustering.Hclust convention.

Related

source
PortfolioOptimisers.turn_into_Hclust_merges — Function
turn_into_Hclust_merges(Z::MatNum)

Convert a linkage matrix in the Matlab convention to the convention of Clustering.Hclust.

The function writes the linkage matrix of HierarchyConstruct4s in the index convention of Clustering.Hclust, and it adds the size of the cluster of each merge.

At this function the result passes to Clustering.Hclust, so every consumer downstream reads the convention below. DBHTs loads the first two columns into mleft and mright and the third into heights. Clusters and each function that cuts a dendrogram read them on that convention.

Both conventions give one merge to each row, and they name the two sides of a row in different ways.

The side isMatlab writesClustering.Hclust writes
a leaf, vertex aa, which is at most N-a
the cluster built by row jj + Nj

Thus a row names only rows above it, and the size of the cluster that it builds is the sum of the sizes of its two sides.

Algorithm

  1. Set N to size(Z, 1) + 1, the leaf count, and append a fourth column of zeros to hold the cluster sizes.
  2. For each row i, read each of its first two entries a. When a is at most N, it names a leaf. Write -a in its place and add 1 to the size of row i.
  3. Otherwise a names the cluster that row j = a - N built. Write j in its place and add the size of row j to the size of row i. Row j is above row i, so its size is already final.

Arguments

  • Z: (N-1)×3 linkage matrix in the Matlab convention. Each row is one merge, with the two merged labels and the height of the merge.

Returns

  • Z::MatNum: (N-1)×4 linkage matrix in the format of Clustering.Hclust. Columns one and two hold the two sides in the convention of the table above. Column three holds the heights with no change, and column four holds the leaf count of the cluster that each row builds.

Related

source