Solved – Minimum number of instances to create a decision tree

cartweka

I'm kind of new doing data mining, so sorry if my question is not very clear.

I'm working in a project that is aiming to do data mining over the interactions of the students with a e-learning platform. So, I'm trying to generate decision trees with some data that I collected (number of times that student use a resource, number of activities done, number quizzes taken, etc). The trees that I'm getting are interesting for me and according with the cross-validation tests, it's kind of accurate.

So my doubt is the following, I generated the tree with the data collected over two months and there were 44 students in the course. Is this enough data to trust in the tree? I have only the 44 instances that gather the two months of interactions…

Thanks in advanced for your help.

Best Answer

{I'm guessing that for each person and each variable you have a single value covering the 2 months--i.e., you don't have repeated measures.} 44 sounds like an awfully small number. Is it a random sample of a larger population? The answer to that, for one thing, would affect your confidence in the findings.

I won't say it's impossible to achieve useful, replicable results in this situation, but it seems unlikely. Data mining via decision trees is an opportunistic process and requires crossvalidation, probably even more than other modelling procedures do.

I'd also like to know, if you're getting statistically significant differences that form the basis for the branchings, what criterion are you using for significance?

Related Solutions

Decision Tree – How to Train a Decision Tree Against Unbalanced Data?

This is an interesting and very frequent problem in classification - not just in decision trees but in virtually all classification algorithms.

As you found empirically, a training set consisting of different numbers of representatives from either class may result in a classifier that is biased towards the majority class. When applied to a test set that is similarly imbalanced, this classifier yields an optimistic accuracy estimate. In an extreme case, the classifier might assign every single test case to the majority class, thereby achieving an accuracy equal to the proportion of test cases belonging to the majority class. This is a well-known phenomenon in binary classification (and it extends naturally to multi-class settings).

This is an important issue, because an imbalanced dataset may lead to inflated performance estimates. This in turn may lead to false conclusions about the significance with which the algorithm has performed better than chance.

The machine-learning literature on this topic has essentially developed three solution strategies.

You can restore balance on the training set by undersampling the large class or by oversampling the small class, to prevent bias from arising in the first place.
Alternatively, you can modify the costs of misclassification, as noted in a previous response, again to prevent bias.
An additional safeguard is to replace the accuracy by the so-called balanced accuracy. It is defined as the arithmetic mean of the class-specific accuracies, $\phi := \frac{1}{2}\left(\pi^+ + \pi^-\right),$ where $\pi^+$ and $\pi^-$ represent the accuracy obtained on positive and negative examples, respectively. If the classifier performs equally well on either class, this term reduces to the conventional accuracy (i.e., the number of correct predictions divided by the total number of predictions). In contrast, if the conventional accuracy is above chance only because the classifier takes advantage of an imbalanced test set, then the balanced accuracy, as appropriate, will drop to chance (see sketch below).

Accuracy vs. balanced accuracy

I would recommend to consider at least two of the above approaches in conjunction. For example, you could oversample your minority class to prevent your classifier from acquiring a bias in favour the majority class. Following this, when evaluating the performance of your classifier, you could replace the accuracy by the balanced accuracy. The two approaches are complementary. When applied together, they should help you both prevent your original problem and avoid false conclusions following from it.

I would be happy to post some additional references to the literature if you would like to follow up on this.

Solved – Number of variables for decision trees

This depends on your classification problem and whether it is easily solvable by a few splits in a few variables or not.There are real classification problems with relatively simple patterns where a couple of splits already yield very good results - but, of course, there are also problems where you need many observations from more variables to get meaningful results. The classic textbook example for the former is the iris dataset. In R using the partykit package you can do:

library("partykit")
ct <- ctree(Species ~ Sepal.Length + Sepal.Width + Petal.Length + Petal.Width,
  data = iris)
ct

which yields

Model formula:
Species ~ Sepal.Length + Sepal.Width + Petal.Length + Petal.Width

Fitted party:
[1] root
|   [2] Petal.Length <= 1.9: setosa (n = 50, err = 0.0%)
|   [3] Petal.Length > 1.9
|   |   [4] Petal.Width <= 1.7
|   |   |   [5] Petal.Length <= 4.8: versicolor (n = 46, err = 2.2%)
|   |   |   [6] Petal.Length > 4.8: versicolor (n = 8, err = 50.0%)
|   |   [7] Petal.Width > 1.7: virginica (n = 46, err = 2.2%)

Number of inner nodes:    3
Number of terminal nodes: 4

So here we supply 150 observations of four predictor variables, only two of which are used by the algorithm. The classification performs very well with only the small node [6] having a hard time separating the versicolor and virginica species. Using rpart instead of partykit yields similar results. Use:

library("rpart")
rp <- rpart(Species ~ Sepal.Length + Sepal.Width + Petal.Length + Petal.Width,
  data = iris)
as.party(rp)

Whether or not tree-based methods perform well on your particular data is hard to predict. But you can easily try this out using standard software (e.g., partykit or rpart in R or using the caret interface) and compare the results with other techniques.

Best Answer

Related Solutions

Decision Tree – How to Train a Decision Tree Against Unbalanced Data?

Solved – Number of variables for decision trees

Related Question