12.5. DECISION TREES
513
12.5.6
Parallel Design of Decision Trees
The design of decision trees using the methods just described involves a serious
amount of computation. The procedure must be applied to every node of the
tree. Moreover, while we have described what to do with one feature of the
input vector, the same must be done for every feature, after which we pick the
best split among all features. If the feature is numerical, we need to sort all the
training examples that reach the node. If the feature is categorical, we need
to ﬁrst group the training examples by the value of the feature, and then sort
the values according to the fraction of examples that belong to the ﬁrst class.
Moreover, if there are really more than two classes, we need to consider all ways
to divide the classes into two groups; these groups then play the role of the two
classes in the discussion of Section 12.5.5.
However, to speed the process, there is a lot of easy parallelism available.
• At a node, we can ﬁnd the best splits for all the features in parallel.
• All the nodes at one level can be designed in parallel. Moreover, each
training example reaches at most one node at any level. A training exam-
ple will reach exactly one node at a given level, unless it reaches a leaf at
a higher level. Thus, even without parallelism, we expect the total work
at each level to be about the same, rather than growing with the number
of nodes.
• Grouping of training examples by value of a feature can be done eﬃ-
ciently in parallel. For example, we discussed how to do this task using
MapReduce in Section 2.3.8.
• Parallelism can speed up sorting considerably. While we shall not discuss
it here, there are known algorithms that can sort n items in parallel in
O(log2 n) parallel steps in the worst case, or O(log n) parallel steps on
average.
Suppose now that we are working on the design of one node using one
feature A, perhaps in parallel with many other node-feature pairs in parallel.
After grouping (if A is nonnumeric) and sorting, we need to compute several
accumulated sums. For instance, if A is numeric, then we need to compute for
each training example and each class the number of training examples with that
class, among this training example and all previous examples on the sorted list.
The computation of accumulated sums appears to be inherently serial, but as
we shall see, it can be parallelized quite well. Once we have the accumulated
sums, we can compute the needed fractions and impurity values associated with
each member of the list, in parallel. Notice that the row-by-row calculations
suggested in Examples 12.17 and 12.18 are all independent and so open to a
parallel implementation.
To complete the story of parallelization for decision trees, let us see how
to compute accumulated sums in parallel. Formally, suppose we are given a
