Popular Decision Trees Induction Algorithms - Data Mining with Decision Trees: Theory and Applications - page 83

training set, the algorithm may choose an attribute which is not truly
the best one.
(4) The fragmentation problem causes partitioning of the data into smaller
fragments. This usually happens if many features are tested along the
path. If the data splits approximately equally on every split, then
a univariate decision tree cannot test more than )features.

This puts decision trees at a disadvantage for tasks with many
relevant features. Note that replication always implies fragmentation,
but fragmentation may happen without any replication.
(5) Another problem refers to the effort needed to deal with missing values
[Friedman et al . (1996)]. While the ability to handle missing values
is considered to be advantage, the extreme effort which is required
to achieve it is considered a drawback. The correct branch to take is
unknown if a feature tested is missing, and the algorithm must employ
special mechanisms to handle missing values. In order to reduce the
occurrences of tests on missing values, C4.5 penalizes the information
gain by the proportion of unknown instances and then splits these
instances into subtrees. CART uses a much more complex scheme of
surrogate features.
(6) The myopic nature of most of the decision tree induction algorithms
is reflected by the fact that the inducers look only one level ahead.
Specifically, the splitting criterion ranks possible attributes based on
their immediate descendants. Such strategy prefers tests that score high
in isolation and may overlook combinations of attributes. Using deeper
lookahead strategies is considered to be computationally expensive and
has not proven useful.

O ( logn