# Maximum training error for a decision tree

For any dataset $D$, with the label space containing m labels. Using decision tree, can we calculate the maximum training error on that?

Yes I have to admit, it's a homework question and I have completely no clues on that. Could any one gives me some hint on that? And what is label, does it mean edges of the tree?

• Hi Xupeng, welcome to Cross-validated. It is a good question. However, if it is a homework question, please add the tag "homework". – Simone Oct 1 '15 at 4:42
• Also you can add latex notations if you use the \$symbol. E.g. for any dataset \$D\$.. – Simone Oct 1 '15 at 4:43 ## 1 Answer A decision tree is a classification model. You can train a decision tree on a training set$D$in order to predict the labels of records in a test set.$m$is the possible number of labels. E.g.$m = 2$you have a binary class problem, for example classifying patients who might either have or not have a disease;$m > 2\$ you have multi-class problem, for example if you had to classify news in "politics", "sport", and "culture".

Think about how decision trees work. I wrote an explanation here. The hint I can give to you is that in your homework attributes are not relevant to the class. Also, think about the way decision trees classify records on leaf nodes.

• So does it mean the dataset that may meet the maximum training error here has to be the worst one (one with the highest entropy) ? – xxx222 Oct 1 '15 at 5:26
• Yes, I think you have to think about the worst dataset where your decision tree is just a root node. – Simone Oct 1 '15 at 7:26
• Do you mean considering one root node situation is good enough? I am confused because of I know nothing about the information of node, which centers in the decision tree theory. – xxx222 Oct 1 '15 at 7:36
• I mean, what is the worst case for a decision tree? that attributes are totally unpredictive to the class. In this case you wouldn't even grow a decision tree. You would just have a single root node, which can also be seen as a single leaf node. Now you have just to think about how you classify records on a leaf node: majority voting. – Simone Oct 1 '15 at 7:39
• Does it mean in the worst case we can't even select a proper feature to grow the tree? So what should I do now? Randomly allocate m classifications? What does the majority means here? – xxx222 Oct 1 '15 at 7:56