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

then the two classifiers are regarded as different. The errors are compared
by testing the hypothesis that the errors are generated by the same binomial
random variable [ Dietterich (1998) ] .
The cross-inspection heuristic compares only two distinct classifiers.
However, in the DFID framework, more than two classifiers must be
compared at a time (if the attribute, which was selected by the gain
ratio criterion, has more than two possible values). For example, if it is
believed that graduate students from different schools behave differently,
one may consider splitting according to the school's name. The attribute
school can receive multiple values, all of which will have to be compared
simultaneously. A successful split will group similar schools together, while
different schools will be in different groups. Since an exhaustive search, over
all the possible groupings, is unacceptable in terms of complexity, grouped
gain ratio (see Figure 15.4) uses a greedy grouping heuristic, which is based
on cross-inspection.
The procedure begins by using cross-inspection, to compare all the
distinct pairs of classifiers (if there are q classifiers, there are q ( q -1)/2
comparisons). For each instance sub-space, the procedure computes the
number of instances that belong to sub-spaces that are similar to it
(by definition the similarity by cross-inspection is defined with regard to
classifiers rather than sub-spaces; each sub-space, however, is described
by a classifier). The classifier that represents the sub-space with the
largest such number is regarded as the classifier that covers the maximal
number of instances. The sub-spaces of all the instances which are covered
by this classifier are grouped together, and the procedure iterates. The
heuristic does not explicitly guarantee that any two classifiers in a group
are equivalent, but equivalence is assumed to be a transitive relation.
The greedy grouping procedure is a simple clustering method and other
clustering methods, like graph coloring [ Zupan et al . (1998) ] may also be
suitable here. Alternatively one could use the Warshall algorithm [Warshall
(1962)] for finding the transitive closure of the comparison matrix, which
canbeusedforcalculatingsup j . However, this form of calculation will not
be convenient in this case because it will tend to group too much as the
following example illustrates.
Cohen et al . (2007) demonstrated that CPOM improved the obtained
accuracy compared to the examined embedded methods (naive Bayes,
backpropagation and C4.5). Not only was CPOM more accurate than other
decision tree ISD methods, the grouping heuristic significantly improved
the accuracy results, compared to a CPOM variation which does not