# A metric between trees

I have certain tree structures. I am not an expert in machine learning.

As I would with take KNN, I would calculate distances via metric function and a new data point and the points from the training set. Okay, understood.

Now let's consider the data points aren't tuples but trees. How would one calculate the distances between two graphs.

For instance, I want the following

I have several stereotypical trees like:

|
- <form class="xyz">
|
- <input type="text">


between all these node, there could be arbitrary other nodes, the value of the button-node could be different, the type of the input node could be different, even the button-node could be a different node type, like input, the form-node will be surrounded by arbitrary nodes.

How would one calculate such a distance between trees?

• depends on what you are trying to measure/achieve?! – oW_ Jan 14 '19 at 19:28
• really? okay, what could could be different per goal? – Chris Pillen Jan 14 '19 at 19:29
• My goal is to classify trees. I want to decide, whether a given tree includes such a structure given above. The nearer a structure is to some kind of average (or centroid) through the training-trees, the more likely the give tree contains such a structure of interest. – Chris Pillen Jan 14 '19 at 19:33
• While I agree that the problem really boils down to your definition of similarity, which you'd have to provide, I think it's possible to say something about an answer. You don't sound super concerned about ordering of elements. What about considering the HTML doc a bag of tags? then clustering via any standard text similarity measure? those don't have any notion of tree structure, but could be close enough -- depending on your use case. – Sean Owen Jan 14 '19 at 23:39