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?

  • $\begingroup$ Hi Xupeng, welcome to Cross-validated. It is a good question. However, if it is a homework question, please add the tag "homework". $\endgroup$ – Simone Oct 1 '15 at 4:42
  • $\begingroup$ Also you can add latex notations if you use the \$ symbol. E.g. for any dataset \$D\$.. $\endgroup$ – Simone Oct 1 '15 at 4:43

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.

  • $\begingroup$ 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) ? $\endgroup$ – xxx222 Oct 1 '15 at 5:26
  • $\begingroup$ Yes, I think you have to think about the worst dataset where your decision tree is just a root node. $\endgroup$ – Simone Oct 1 '15 at 7:26
  • $\begingroup$ 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. $\endgroup$ – xxx222 Oct 1 '15 at 7:36
  • $\begingroup$ 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. $\endgroup$ – Simone Oct 1 '15 at 7:39
  • $\begingroup$ 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? $\endgroup$ – xxx222 Oct 1 '15 at 7:56

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.