7
$\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$
5
$\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?

Like 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$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.