Are decision tree learning algorithms deterministic?

Question

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?

Answer 1

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.