6
$\begingroup$

I thought I understood how a single decision tree is constructed as part of a Random Forest :

The data is split recursively until some kind of stopping conditions are met. Each split is determined by computing by optimizing an objective function. The parameters to that objective function are the dimension (variable/feature) along which to split, and where along that dimension to split.

My question: Are nodes ever compared to each other when determining where to make the next split? For example, let's say there are two nodes at the same level in the tree, should we find the best dimension and the best split location for each of those, compute the error metric of each of those, and then compare those errors to determine which node, dimension, and split location to use?

The reason I ask is this article makes an argument for what it calls "confidence splitting" based on the premise that the error for a node with a few data points in its region, can be the same as the error for a node with many data points in its region. This is because gini-impurity and entoropy are scale-invariant (explained in the section "Traditional Node Splitting Criterions").

But, if the error of one node is never compared with the error of another node, it makes the articles point obsolete, correct?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

Random forests are based on greedy induction of decision trees, which means that the best attribute to split on and best cut-off is computed independently for each internal node in the tree. Thus, nodes are not directly compared.

The article you cited does not specify that a split might be induced on a smaller number of points $N$ if an attribute has missing values. Indeed, in their experimental evaluation the adult dataset has missing values. It make sense to penalize split induced on attributes with missing values and they do that defining a new splitting criterion based on confidence intervals.

For example, let's say that you have the following data set:

A B Class
1 ? +
3 4 -
4 6 +

These 3 points can be splitted according to feature $A$ on the cut-offs 1 or 3, or according to feature $B$ on the cut-off 3. If we split according to feature $B$ we just take 2 points into account to compute the splitting criterion. If we split according to $B$ with the missing value ?, deciding whether to put the first point is a totally different story: C4.5 uses weights and CART uses surrogates splits.

Actually the topic of bias of splitting criteria has received attention in the past as well. The blog post you cited does not cite any previous work. We worked on a similar approach which penalizes missing values based on statistical significance rather than using confidence intervals: here. However, we focused in particular on categorical data sets which is another possible application domain. The positive side of using statistical significance is that this approach can be applied to the original Gini gain. Therefore it works also for multi-class classification and not just for binary classes.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the detailed answer. still it's unclear to me how this works. A Random Forest classifier only works on data when all the features of all the points are present. Unless we're talking about some variant of a RF that splits as much as it can until asked to split on a variable that is absent from a certain sample? And, the article explicitly targets random forest classiifiers. $\endgroup$
    – makansij
    Commented Jan 12, 2016 at 7:08
  • 1
    $\begingroup$ @Candic3 I edited the question, even the standard random forest is flexible enough to deal with missing values. $\endgroup$
    – Simone
    Commented Jan 12, 2016 at 9:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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