Grafting (decision trees)

Grafting is the process of adding nodes to inferred decision trees to improve the predictive accuracy. A decision tree is a graphical model that is used as a support tool for decision process.

Introduction

Once the decision tree is constructed, then the new branches that can be added productively to the tree are identified. Then they are grafted to the existing tree to improve the decision making process. Pruning and Grafting are complementary methods to improve the decision tree in supporting the decision. Pruning allows cutting parts of decision trees to give more clarity and Grafting adds nodes to the decision trees to increase the predictive accuracy. To achieve grafting new branches can be added in the place of a single leaf or graft within leaves.

Illustration

The information required is given in the form of a chart as,

The nodes and leaves can be identified from the given information and the decision trees are constructed. One such decision tree is as follows,

Here the X-axis is represented as A and Y-axis as B. There are two cuts in the decision trees – nodes at 11 and 5 respective to A.

  A > 11
  A <= 11
  |  A >= 5
  |  A < 5

Using Grafting, new branches are added to the above classification.

Here B is also taken into consideration for the nodes and leaves. There are two more cuts at B – 7 and 2.

  A > 11
  A <= 11
  |  A >= 5
  |  A < 5
     |  B > 7
     |  B <= 7
        |  B > 2
        |  B <= 2

Thus the branching has increased due to the grafting technique.

This is the simplest form of illustration to represent grafting techniques.

Conclusion

Grafting can identify regions where there are no occupancy and correct the poor class assignments which increases the accuracy. The extension to graft multiple branches at each leaf reduces the number of errors.

However, the potential new branches have to be selected carefully to avoid increasing the error and failure cases.

Future Study

Improving multicast tree construction

Problem of missing value in decision tree grafting Optimal grafting and appropriate selection of branches to be added

See also

• Decision tree
• Artificial neural network

External links

• R-tree implementation using branch-grafting method (R-tree implementation)
• Deep copy and persistence of a BWidget's Tree (BWidget Trees)