Intron Subtrees Sample Clauses

Intron Subtrees. Intron subtrees are parts (subtrees) of non-fuzzy top-down atomic decision trees which can and will never be traversed because of the outcome of nodes higher up in the tree. An example of an intron subtree is shown in Figure 5.2. false true class:= A X < 2 false true class := B class := C Figure 5.2: A top-down atomic decision tree containing an intron subtree (class := C). Once the root node containing X > 3 has been evaluated either the left or the right branch is traversed depending on the value of X. If X is less than or equal to 3 the left branch is traversed resulting in class A. If X has a value higher than 3 the right branch is traversed and the second internal node X < 2 is reached. Normally this node would be evaluated for every possible data record (with a value of X greater than 3). However, an analysis of the decision tree traversed so far shows that this node will always result in false since node X < 2 is reached only if X has a value higher than 3. Therefore, the right branch of node (X < 2) will never be traversed, making it an intron subtree since it does not influence the behaviour of the decision tree. ∅ In order to detect intron subtrees, we recursively propagate the possible domains of the attributes through the decision trees in a top-down manner. Given a certain data set we determine for each attribute Xi the domain D(Xi) of possible values. By propagating the domain of each attribute Xi recursively through the non-fuzzy top-down atomic trees we can identify situations in which the domain of an attribute becomes empty ( ), indicating the presence of an intron subtree. D(X) = [0, 10] X > 3 D(X) = [0, 3] D(X) = (3, 10] class:= A X < 2 D(X) = (3, 10] class := B D(X) = ∅ class := C Figure 5.3: A top-down atomic decision tree containing an intron subtree with the domain of attribute X displayed at each point in the tree. ∅ Observe the top-down atomic decision tree in Figure 5.3. Let X be a continuous valued attribute in the range [0, 10]. Before evaluation of the atom in the root node (X > 3) the domain of X is [0, 10]. Just as the atom splits a data set into two parts, the domain of possible values of X is split into two. In the left subtree the domain of X is limited to [0, 3] and in the right subtree the domain of possible values for X is (3, 10]. Thus if the second internal node of the tree is reached it means that X has a value greater than 3 and less than or equal to 10. After the evaluation of the second internal node (X < 2) of t...