Hybridization of Decision Trees with other Techniques - Data Mining with Decision Trees: Theory and Applications - page 244

to be different. If the procedure returns just a single descendent node, the
split it has generated is regarded as invalid.

15.3.2 The Grouped Gain Ratio Splitting Rule

Grouped gain ratio is based on the gain ratio criterion followed by a
grouping heuristic. The gain ratio criterion selects a single attribute from
a set of candidate attributes. The instance sub-space, whose partition we
are now considering, may, in principle, be partitioned so that each new
sub-subspace will correspond to a unique value of the selected attribute.
Group gain ratio avoids this alternative, through heuristically grouping
sub-subspaces together. By grouping sub-subspaces together, grouped gain
ratio increases the generalization capabilities, since there are more instances
in a group of sub-subspaces than there are in the individual sub-subspaces.
Clearly, if we separately train I on each subset and obtain the same
exact classifier from each subset, then there is no point in the split, since
using this single classifier for the entire instance space is as accurate as using
the multiple classifiers; it is also much simpler and understandable, and it
can generalize better. The other direction of this argument is slightly less
straightforward. If the classifiers that were trained over the training subsets
are very different from one another, then none of them can classify X as one,
and we can believe that the split is beneficial. Based on this observation,
the grouped gain ratio splitting rule groups together sub-spaces that have
similar classifiers.
The intuition regarding the classifier comparisons raises questions of
what is similar, what is different and how to compare classifiers? Although
there may be multiple classifiers, all of which must be simultaneously
compared to each other, we begin answering these questions with the
simpler case of exactly two classifiers, using a comparison heuristic, which
we refer to as cross-inspection (see Figure 15.2).
Cross-inspection is based on two mutually-exclusive training subsets
and a classification method as inputs. The comparison begins by randomly
partitioning each subset into a training sub-subset and a test sub-subset.
Then, two classifiers are produced, by training the input method, once
over each training sub-subset. After producing the two classifiers, the cross-
inspection heuristic calculates the error rates of each classifier over each of
the test sub-subsets. If the error rate of the first classifier over the first test
sub-subset is significantly (with confidence level alpha) different from the
error of the first classifier over the second test sub-subset, or vice versa,