Decision trees as we know assigns label to the node based on majority class voting. I am curious to find that what could be the problems with such labeling schemes? Does it lead to overfitting the data?


Decision Tree does assign the label based on majority given the attribute test condition and its value.

Regarding the class label assignment-

In case DT has a longer depth, there might not be enough instance left for a certain branch/test condition/node . then this might not be the reliable estimation of the class label statistically. This is also called Data fragmentation problem.

so a DT with 50 nodes, at dept 10, for day = Humid there is only 1 instance left which is -ve. So Its assigned as -ve but there is not enough data ideally to support this.

One way to solve this is to dis-allow to grow the tree beyond a certain threshold in terms of number of node i.e. stopping condition.

Which also brings us to Over-fitting, Regarding Over-fitting- There is this classic Error vs number of nodes graph on train and test to show how over-fitting happens in DT.

As you can see in below graph, tree with more number of nodes has lower training error but while its being tested error is higher. The gap between test and training error is telling us that the tree is over-fitting/has captured the noise when tree size is growing.

enter image description here

Now Random Forest is a Assembly/forest of multiple Decision Trees. While classifying the example we take majority voting out of Trees.

| improve this answer | |
  • 1
    $\begingroup$ Its related to dept. As i said data fragmentation problem may occur.Dept has 2 consequences here. Even if you leave the depth aside, if data/instances to learn from for a certain node is little and strategy is to label the majority class, i can't be sure that these instances are actually a majority label(true representation of data) or just noise. $\endgroup$ – BlackCurrant May 21 at 10:17
  • 1
    $\begingroup$ Okay so lets say, I need to predict if my friend likes to watch MotoGP or not.He/she decides on factors like weather condition of the day, track location etc if he/she would like to watch the race.Now, I have been keeping the record of the days and location on which days he/she watched the race. but my another friend came and messed up the record by marking few days when he/she did not go to watch race because it was rainy and race was in Silver stone. So, my friend actually doesn't like to watch race on these days but since data says he/she does its rather noisy data. $\endgroup$ – BlackCurrant May 21 at 16:25
  • 1
    $\begingroup$ Also, lets say this new friend added a new entry in record saying when day is sunny and race is in Antarctica region out mutual friends likes to go to see the race. $\endgroup$ – BlackCurrant May 21 at 16:27
  • 1
    $\begingroup$ Here while building the tree I have 2 instances which say he likes to watch the race out of 3 and only 1 says he doesn't , majority class is +ve that he does but its noise and since we are labeling it with majority class we are assigning the wrong label. $\endgroup$ – BlackCurrant May 21 at 16:30
  • 1
    $\begingroup$ Yes, Its more likely that majority votes classifies better . as we see the case in random forest. $\endgroup$ – BlackCurrant May 21 at 16:39

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.