<p>Even if you had the (pseudo-)distances between each pair of possible trees, this is actually not what you're after. You actually want to do <strong>unsupervised learning</strong> (clustering) in which you combine structure learning with parameter learning. The types of data structures you want to perform inference on are trees. To postulate "some metric space" for your clustering method, you introduce something that is not really necessary. To find the proper <strong>distance measure</strong> is a very difficult problem. I'll point in different directions in the following paragraphs and hope they can help you on your way.</p>

<p>The following is not the only way to represent this problem... You can see your problem as <strong>Bayesian inference</strong> over all possible trees with all possible values at the tree nodes. You probably would have some prior knowledge on what kind of trees are more likely than others and/or what kind of values are more likely than others. The Bayesian approach would allow you to define priors for both.</p>

<p>One article you might like to read is "Learning with Mixtures of Trees" by Meila and Jordan, 2000 (<a href="http://machinelearning.wustl.edu/mlpapers/paper_files/MeilaJ00.pdf" rel="nofollow">pdf</a>). It explains that it is possible to use a <strong>decomposable prior</strong>: the tree structure has a different prior from the values/parameters (this of course means that there is some assumption of independence at play here).</p>

<p>I know you were hinting at heuristics such as the average fan-out etc., but you might find it worthwhile to check out these new applications of Bayesian inference. Note, for example that within nonparametric Bayesian method it is also feasible to reason about infinite trees, as done e.g. by Hutter, 2004 (<a href="http://arxiv.org/pdf/math.ST/0411515" rel="nofollow">pdf</a>)!</p>
Similarities Between Trees
<p>I am working on a problem of Clustering of Results of Keyword Search on Graph. The results are in the form of Tree and I need to cluster those threes in group based on their similarities. Every node of the tree has two keys, one is the table name in the SQL database(semantic form) and second is the actual values of a record of that table(label).</p>

<p>I have used Zhang and Shasha, Klein, Demaine and RTED algorithms to find the Tree Edit Distance between the trees based on these two keys. All algorithms use no of deletion/insertion/relabel operation need to modify the trees to make them look same. </p>

<p>**I want some more matrices of to check the similarities between two trees e.g. Number of Nodes, average fan outs and more so that I can take a weighted average of these matrices to reach on a very good similarity matrix which takes into account both the semantic form of the tree (structure) and information contained in the tree(Labels at the node).</p>

<p>Can you please suggest me some way out or some literature which can be of some help?**</p>

<p>Can anyone suggest me some good paper</p>