1
$\begingroup$

Background to make sure I understand decision trees:

In order to create a decision tree, we go through each dimension and we attempt create two partitions of the data by trying every possible "split" of the data along each dimension, constantly checking some metric of each split (e.g. the Gini coefficient of both of the partitioned datasets), and trying to minimize that metric (e.g. the sum of the Gini indexes of the partitioned data). Once we find that best split, we recursively apply this algorithm to each of the partitioned datasets, and we remember the hierarchy of splits. We stop either when every leaf node is pure, or when we reach some depth, or some other criteria.

My Question:

Does this mean that if I were to create a decision tree based on some m x n dataset, and then I find another n dimensional point that I would want to use to "train the tree," I would have to recreate the tree from scratch on the (m+1) x n dataset? Is this what is meant when it's said that decision trees are "unstable?" Does that mean that active learning on decision trees is impossible, since "retraining" the decision tree requires having the entire dataset - any existing tree structure / splits might have to be discarded if a new point is introduced that would "disrupt" the balance of, say, the topmost split?

$\endgroup$
2
  • $\begingroup$ you understand decision trees properly, but I'd remind you that node purity and depth are not the only possible stopping criteria. typically, a lot more controls are implemented. $\endgroup$ – carlo Aug 6 '20 at 22:21
  • $\begingroup$ @carlo you're right, I didn't flesh out the stopping criteria enough, I edited the post accordingly $\endgroup$ – bensenberner Aug 7 '20 at 0:07
1
$\begingroup$

CART and the original ID3 are non-incremental decision tree algorithms - so yes, you would have to build a new tree every time a datapoint is added. There are other incremental algorithms that were proposed to create such an online learner.

See: en.wikipedia.org/wiki/Incremental_decision_tree

$\endgroup$

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.