4
$\begingroup$

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">
    - <button value="Click here">

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ depends on what you are trying to measure/achieve?! $\endgroup$
    – oW_
    Commented Jan 14, 2019 at 19:28
  • $\begingroup$ really? okay, what could could be different per goal? $\endgroup$
    – Chris Pillen
    Commented Jan 14, 2019 at 19:29
  • $\begingroup$ 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. $\endgroup$
    – Chris Pillen
    Commented Jan 14, 2019 at 19:33
  • $\begingroup$ 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. $\endgroup$
    – Sean Owen
    Commented Jan 14, 2019 at 23:39

3 Answers 3

Reset to default
1
$\begingroup$

The distance between objects of complex structure can be tricky. Consider a simpler example, when you got two sequences of words. How do you calculate the distance? In speech recognition, the distance between the groundtruth and recognized transcriptions is calculated as the word-error-rate based on the Levenstein distance between the aligned sentences.

GRAAL is an extension of the alignment algorithm to the networks. However, it only considers the network topology. You might want to extend the node similarity degree to encounter the type and attributes of the nodes.

Improve this answer
$\endgroup$
1
$\begingroup$

One approach to that would be to use graph kernels to calculate similarity (since kernels are equivalent to taking dot products in some euclidean embedding space), and use kernelized kNN algorithm.

Improve this answer
$\endgroup$
0
$\begingroup$

Since the objective of finding how far the trees are , or in what sense are the trees far you can try multiple things 1. One dimensional distance in terms of "Total Entropy" of tree. Or Prediction accuracy of tree. 2. One proxy of finding how far apart your trees are could be to pick a set of sample points and evaluate the output of your trees and feed that into a t-SNE to see how far apart these outputs are. If the samples are a good representation of your dataset, then you can get meaningful insights from the t-SNE output.

Link - https://lvdmaaten.github.io/tsne/

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.