clustering data set based on the similarity of tree structure

Question

I have a data set (>5000). each individual record of data is structured as a multilevel n-ary tree (>200 nodes). The tree node identifiers are unique within the tree. but the same identifiers are used to represent the same type of node across the data set. I would like to group the data set into multiple clusters based on the similarity between records. The records generally have a similar structure except some records have some branches pruned.

Here are some overly simplified examples.

basic type:
A - B - C
 \- D - E - F
 \- G - H - I
         \- J

sample 1:
A
 \- D - E - F
 \- G - H - I
         \- J
 
sample 2:
A - B - C
 \- G - H - I
         \- J

sample 3:
A - B - C
 \- D - E - F
 \- G - H - I

I have no idea how many different types of tree structures are there in the dataset. I guess it's about 10-30. This is why I want to have a better understanding of the dataset by clustering the dataset. I want 'clustering' because I want to allow small variations in a cluster so that I could have a controllable number of clusters for analysis purposes.

any thought? thanks

Answer 1

Since these trees are all subtrees (in the rooted sense) of some universal tree, you can go as simple as the size of the symmetric difference.

If your trees can have very different sizes, it might be beneficial to be more lax in measuring similarity of large trees compared to small trees; in that case, the Jaccard distance may work well.

Finally, you might want to care more about the actual tree structures. Consider:

basic type:
A - B - C
 \- D - E - F
 \- G - H - I
         \- J
 
sample 2:
A - B - C
 \- G - H - I
         \- J

sample 4:
A - B
 \- D - E
 \- G - H
        \- J

Samples 2 and 4 both have lost 3 nodes from the basic type, and so are the same distance from it according to either of my first two metrics. But for your use-case, maybe losing an entire branch is more or less different than losing three leaves. You can weight by distance from the root, or any number of other things, to accommodate these differences; just be careful if your clustering algorithm requires a strict metric that your weighting still satisfies the axioms.

Answer 2

You have to convert your data into graphs. There are tools like Networkx to create graphs that you can classify with functions from karateclub libraries, for example graph2vec.

To convert you data into graphs, you will want to parse your data structure to fit the networkx one.

import networkx as nx
G = nx.Graph()

Then make a loop taking the data following its hierarchical structure adding nodes or edges:

G.add_node(1)
G.add_edge(1, 2) 

Answer 3

Another idea would be to use matrix factorization suitable for three dimension data like Tucker_decomposition or PARAFAC Decomposition and tons of other deep learning based architecture.

Basically every network/tree can be seen as a NxN binary matrix where N is the number of nodes and where ever node i is connected to node j, x_ij would be 1. If you have directionality in your network you can also consider +1 versus -1. The third dimension would be your samples. Let's say you have M samples, you will end up with a 3d tensor NxNxM.

Depending on what are your samples one can decide which algorithm is more suitable. If it is time (so there is a relationship across M dimension or some other structural differences)