Intron Nodes. Intron nodes are root nodes of subtrees of which each leaf node contains the same class assignment atom (e.g., class := A). Regardless of the path tra- versed through such trees, as a result of the tests in the root node or internal nodes, the resulting target class will always be the same (e.g., A). Since the internal nodes in such a subtree do not influence the classification outcome and can be replaced by any other possible internal node without affecting the classification outcome, they are called intron nodes. The negative effects of intron subtrees are mostly related to the size and thus understandability of our decision trees. However, intron nodes also have a negative influence on the computation time needed to evaluate a tree since intron nodes are evaluated but do not contribute to the classification outcome of a tree. false true Y < 2 class := B false true class:= A class:= A Figure 5.7: A top-down atomic tree containing an intron node (Y < 2) since both its children result in the same class. Consider the top-down atomic tree displayed in Figure 5.7. Regardless of the outcome the second internal node (Y < 2) the right subtree will always result in a class assignment node for class A. In this case the second internal node of the tree is an intron node. {A,B} {A} {B} Y < 2 class := B {A} {A} class:= A class:= A Figure 5.8: A top-down atomic tree with the set of possible target classes for each node. false true Y < 2 class := B false true class:= A class:= A Figure 5.9: A top-down atomic tree containing a marked (dotted) intron node. In order to detect all intron nodes in a top-down atomic decision tree we recursively propagate the set of possible class outcomes through the tree in a bottom-up manner. A class assignment node always returns a set containing a single class. In each internal node the sets of possible classes of its children are joined. If the set of possible class outcomes for an internal node contains only a single class the node is marked as an intron node. Once all the intron nodes have been detected the tree can be pruned. During the pruning phase the tree is traversed in a top-down manner and subtrees with an intron node as the root node are replaced by class assignment nodes corresponding to their possible class outcome detected earlier.
