What is the best technique/algorithm to compare trees changes?

Question

I have a problem I would like to solve using machine learning. I would like to use some sort of classification to know if a just added change in a tree data structure is "good" or is "bad".

Let's say I have this tree:

        (A) 
        / \
       /   \
     (B)   (C)

And I apply a change to it (a "good" change, so the algorithm should associate this change with the "good" changes). The updated tree would be like this:

       (A)
       / \
      /   \
    (D)   (C)
    /
   /
 (B)

Added a certain node (D) above another node (B) would be classified as a "good" change.

So when I have the learner with the correct data, the algorithm should be able to know that if I add a node of type D above a node of type B, it is a "good" change.

I would like to work with XML files that keeps the tree structure, a simple classifier like a naive bayes would not work, because it wouldn't be able to recognise if a node is added above another one, it only would be able to know that a node has been added.

I don't know how which algorithm/technique I should use and I don't know how I should pass the data to the learner, because the context in this scenario is important.

What is the best technique/algorithm to compare trees changes?

Answer 1

Most of the machine learning algorithms are designed to work with data in a tabular format. That mean, each data instance is contained in a single row, and the values from each column are the observed values for a specific instance for a given variable. There are few reasons why the most ML algorithms are designed to work on this kind of data. An important factor is that the structure is very simple and various operations can be done with ease. A second reason is that even if looks like a inflexible structure, some sort of additional structure in your data still can be represented on tabular format (using redundancy). Another reason would be that an algorithm designed to work for a specific structure of the data will be constraint to work on a much smaller set of problems.

So, the main point is that "If the mountain won't come to Muhammad then Muhammad must go to the mountain" (note there's nothing religion related here). So what you have to do would be to fabricate the features yourself in a tabular format.

I will give you an example on how I see a starting point. Consider an instance a row in a table. Each row will be a change. A change has a label, it is good or bad. So, you can add a feature used as target feature called class. We go further by noting that a change is an insertion of a node. If your changes are of multiple type you can add a feature called operation-type having values: insert, delete, change, etc. Now, a node has a type also. You can add a new feature called node-type, which could be A, B, etc. What you have to do would be to invent those features by noting what is important for you or your business and eventually select only those features which would be relevant enough. I really hope it was clear enough.