nishant2yadav
commented
1 year ago Hi @preetbawa,
cluster_chain contains list of cluster matrixes encoding connections between nodes at level i and level i+1.
Let's assuming root node is level 0. In your example,
a) There are 24 nodes at level 1 -- which is encoded in a 24x1 matrix.
b) There are 184 nodes in level 2 and parent-child relations between 24 nodes from level 1 and 184 nodes from level 2 are encoded in this 184x24 sparse matrix. Each row contains exactly one non-zero entry corresponding to the parent node. if (i,j)-entry is 1 then it means that node i in level 2 has node j in level 1 as its parent.
c) Similarly, there are 701 nodes in level 3 and finally 2076 nodes in level 4.
a) Level 4 is actually just every node with in a singleton cluster so you can treat level 3 as the final level.
Why are so many clusters created at leaf level?
A lot these 701 clusters might be singleton clusters. The way cluster_chain is set up is that if a certain branch in the tree-based index ends up with just 1 node at level k while the tree depth is d, then this singleton branch is extended to depth d by creating (d - k) dummy internal nodes and chaining them together. This helps maintain the invariant that all leaf nodes at present at the same depth in the tree.
You can check how many of these 701 clusters are singleton by looking at columns of 2076 x 701. The sum jth column corresponds to number of child nodes from cluster j.
The depth parameter controls the depth of the trie in the hybrid-index (3 in your case). HybridIndexer uses hierarchical clustering beyond given depth parameter until each leaf node has at most max_leaf_size datapoints. These singleton clusters are probably created as the index only creates a trie with those 2076 datapoints which may result in a lot of singleton clusters (this would correspond to number of unique length 3 prefixes in your datapoints?). And after creating the trie, hierarchical clustering is not invoked in this example as all clusters probably already contain less than max_leaf_size=100 datapoints.
preetbawa
Description
i am using HybridIndexer to do label indexing, using PIFA Embedding for labels by combining label one hot encoded matrix with input feature matrix. i ran following code:
Build Hybrid Index using Trie and Clustering approach together with max trie depth of 3 and max_leaf size of 100
from pecos.utils.cluster_util import ClusterChain
Hierarchical Clustering Chain as a list of Sparse Matrices - sparse matrice to represent clusters at a specific depth
cluster_chain: ClusterChain = HybridIndexer.gen(feat_mat=label_features, label_strs=labels_sorted, depth=3, max_leaf_size=100, seed=0, max_iter=40, spherical_clustering=True )
and then run this to understand shape
Explore Shape of Cluster Chain
for i in range(len(cluster_chain)): print(type(cluster_chain[i])) print(f"shape of current matrix {cluster_chain[i].shape} " )
RESULTS: shape of current matrix (24, 1) <class 'scipy.sparse.csr.csr_matrix'> shape of current matrix (184, 24) <class 'scipy.sparse.csr.csr_matrix'> shape of current matrix (701, 184) <class 'scipy.sparse.csc.csc_matrix'> shape of current matrix (2076, 701)
it makes sense that there are 4 clusters, as trie depth is3 but does that mean for hierarchical clustering there is only one level - also last matrix is of shape 2076, 701 does that mean there are 701 clusters at leaf level - my sorted unique labels are only 2076 , why so many clusters are created at leaf level or am i understanding this piece correctly, also why its the hierarchical part of tree is flat with only one level depth , i would assume it would branch out after trie or is it in hybrid indexing you only get one level of clustering after trie is built with clusters built as the last depth level - that still maybe makes sense but not sure why so many clusters as 701 built for labels that are only 2k approx.