10
$\begingroup$

Are decision tree learning algorithms deterministic? Given a fixed dataset, do they always produce a tree with the same structure?

What about the random forest?

$\endgroup$

1 Answer 1

9
$\begingroup$

Are decision tree learning algorithms deterministic? Given a fixed dataset, do they always produce a tree with the same structure?

Generally, yes. Most decision tree learners, like the common ID3 and C4.5/C5.0 algorithms, are deterministic. At each step, the learners consider all possible features that have not yet been used to split the data and find the splits that maximize some function (e.g. information gain). There is no randomness (or pseudo-randomness) in this process.

The exceptions to this would be if you used randomness to break ties (rather than, say, using the index of each feature, as is common), but this would be an unusual modification. What about the random forest?

As the name suggests, random forests do make use of randomness, or at least, pseudo-randomness. If we're only concerned about whether or not the algorithm is deterministic in the usual sense of the word (at least, within computer science), the answer is no.

If you start the same random forest learning algorithm, with the same datasets, at two different times (or, using two different seeds for your pseudorandom number generator), you will get two different forests. This is because the algorithm selects random subsets of the features and/or datapoints to learn on, and, if different seeds are used, the subsets will be different each time.

$\endgroup$
2
  • 1
    $\begingroup$ It is also worth noting that early stopping might use a random subset of the data for validation. $\endgroup$
    – NikoNyrh
    Jan 15, 2022 at 14:08
  • $\begingroup$ 'At each step, the learners consider all possible features that have not yet been used to split the data and find the splits that maximize some function (e.g. information gain).' I think that decision trees also consider features that have already been used. $\endgroup$
    – kklaw
    Feb 9 at 12:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .