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
- Take
indx, the vertices whose label is different inLabelVec1andLabelVec2. The merge moved those vertices. - Read the labels that
LabelVec1gave them, drop the repeats and sort them. A merge joins two labels, so exactly two labels remain. - Append one row to
Zi, which holds those two labels and thenLinkageDist.
Arguments
Zi:i × 3linkage matrix at iterationi, in the format of the Matlab output. Each row holds the two merged labels and the height of the merge.LabelVec1:N × 1label vector of the vertices, for the last valid iteration.LabelVec2:N × 1label vector of the vertices, for the trial iteration.LinkageDist: Height of the current merge, which the function writes into the third column.
Returns
Z::MatNum:(i + 1)×3linkage matrix at iterationi + 1, in the format of the Matlab output.turn_into_Hclust_mergesconverts it to theClustering.Hclustconvention.
Related
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
- Take
lvec, the sorted distinct labels oflabelvec. - For each pair
(r, c)of labels withr < c, select the vertices that have either label. - Take the largest non-zero entry of the distance submatrix on those vertices, and record
(lvec[r], lvec[c], value)as a row ofLinks. Record0as the value when the submatrix has no non-zero entry. - Take the row of smallest value, which gives the pair
PairLinkand the scoredvu.
Arguments
d:Nv×Nvdistance matrix of the vertices of a bubble, a cluster or the graph. Row and columniare the same vertex, and entryioflabelvecnames its cluster.labelvec:Nv×1label vector of the same vertices.
Returns
PairLink::Vector{Int}:2 × 1vector 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
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
- Take the pair of smallest union diameter with
LinkageFunctionoverdpmandLabelVec. - Give both members of the pair the label
maximum(LabelVec1) + 1, so the merged cluster takes a label no vertex carries yet. - Write the merged labels back into
LabelVec2at the verticesV. - Append one row to
ZwithDendroConstruct, at the height1 / nc. - Subtract one from
nc, and copyLabelVec2intoLabelVec1. - 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×Nvdistance matrix of the vertices of the bubble or cluster, in the order ofV.LabelVec:Nv×1label vector of those vertices. Step 2 changes it in place.LabelVec1:N × 1label vector of every vertex, for the last valid iteration.LabelVec2:N × 1label vector of every vertex, for the trial iteration. Step 3 changes it in place.V:Nv×1vector of the vertices of the bubble or cluster, which index the rows ofLabelVec1.nc::Number: Merge counter. Step 4 writes the height1 / ncand step 5 lowers it by one, so the heights of a run rise towards1.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 × 1label vector for the next iteration, with the merged labels.
Related
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
- Give every vertex its own label in
LabelVec1, and buildE, theN × maximum(Tc)indicator of the discrete clusteringTc. - For each cluster
k, restrictMvto the vertices of that cluster, which givesMc. Assign each of them to exactly one bubble withBubbleMember, which givesMvv. Set the merge counterncto the vertex count of the cluster minus one. - For each bubble of the cluster that holds more than one vertex, merge its vertices with
build_link_and_dendrooverlength(V) - 1steps, on the distance submatrix of that bubble. - Merge the bubbles of the cluster with
build_link_and_dendrooverlength(Bub) - 1steps, on the distance submatrix of the whole cluster. Steps 3 and 4 share onenc, so the heights of a cluster rise across both steps. - Repeat steps 2 to 4 for each cluster, which leaves one label for each cluster.
- Merge the clusters over
length(kvec) - 1steps. At each step, take the pair of smallest union diameter withLinkageFunctionover all ofDpm, and give both sides a new label. - Write the height of that merge from
dcl, not from the score of step 6.dclstarts at1for 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 than1.
Arguments
Rpm:N × Nsparse weighted adjacency matrix of the PMFG. OnlyBubbleMemberreads it.Dpm:N × Nmatrix of the shortest path lengths of the PMFG. Each linkage score comes from it.Tc:N × 1cluster membership vector.Tc[n] = kmeans that vertexnbelongs to thek-th discrete cluster.Mv:N × Nbbubble membership matrix.Mv[n, bi] = 1means that vertexnis a vertex of bubblebi.
Returns
Z::MatNum:(N-1)×3linkage matrix in the format of the Matlab output. Each row holds the two merged labels and the height of the merge.turn_into_Hclust_mergesconverts it to theClustering.Hclustconvention.
Related
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 is | Matlab writes | Clustering.Hclust writes |
|---|---|---|
a leaf, vertex a | a, which is at most N | -a |
the cluster built by row j | j + N | j |
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
- Set
Ntosize(Z, 1) + 1, the leaf count, and append a fourth column of zeros to hold the cluster sizes. - For each row
i, read each of its first two entriesa. Whenais at mostN, it names a leaf. Write-ain its place and add1to the size of rowi. - Otherwise
anames the cluster that rowj = a - Nbuilt. Writejin its place and add the size of rowjto the size of rowi. Rowjis above rowi, so its size is already final.
Arguments
Z:(N-1)×3linkage 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)×4linkage matrix in the format ofClustering.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