Solved – Accuracy of each path in a decision tree in Matlab

cartclassificationMATLAB

I would like to know the accuracy of each path in a decision tree in Matlab.

I can build a decision tree in Matlab by:

ctree = ClassificationTree.fit(X,Y)

Where X is a matrix of instances (rows are observations, columns are variables), and Y is the response variable.

Here's an example of a simple output tree:

Simple example

For example, the above tree has three different paths:

(x1 < .5) => class 0
(x1 >= .5) And (x2 < .5) => class 0
(x1 >= .5) And (x2 >= .5) => class 1

Now I would like to get the accuracy/confidence of each path. Is there a way to do that?

For example, I want to know how many instances were classified as 0 through the first path and they were actually class 0 (I can provide the same training set X,Y for that)

If I use the function resubLoss:

resuberror = resubLoss(ctree)

I will get the overall accuracy by resubmitting the same training set.

I'm confused why I could not find what I'm looking for, it seems that it's super useful/important.

Best Answer

If you use [yfit,nodes] = eval(ctree,X); nodes will contain the node number assigned to each row of X. Since each leaf has a unique path to root, you'll get what you're looking for using nodes.

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 – Why Decision tree is outperforming Random Forest in this simple case

In addition to @mariodeng's answer which explains why the random forest trained with default parameters is worse here, here's an explanation why it may not be better than single trees in your experiment anyways:

Aggregated/ensemble models are not universally better than their "single" counterparts, they are better if and only if the single models suffer of instability.

With 1000 training rows and only 3 columns, you are in a comfortable training sample size situation in which even a decision tree may get reasonably stable. (For 3d data you can easily check the variation you have in the assignment of input space to the classes when rerunning the experiment.)

If the predictions of the trees are stable, all submodels in the ensemble return the same prediction and then the prediction of the random forest is just the same as the prediction of each single tree.
So then not only will the overall performance be the same, it will be the same cases that are predicted correctly and wrongly, respectively.

This is the case in your example:

table (predict(dtFit, test) [, 2], predict (rfFit, test))

#     0  1
#  0 46  0
#  1  0 54

why not 100% accurate?

You train on data that is not representative for the test cases: the test cases cover regions of the input space that never appear in the training data. There is no way for a model to know which class (if any - or maybe a 3rd? ...) cases far outside training space should belong to.

Particularly for highly nonlinear partitioning models (such as the decision trees), leaving training space will typically rather sooner than later lead to disaster.

If you plan to train on one class only, you need to look into so-called one-class classifiers which try to establish independent boundaries for each class. One-class classification of your toy data should give you the result that the out-of-training-space cases do not belong to any of the known classes.

Decision trees are a partitioning method, they cannot do one-class classification.

Best Answer

Related Solutions

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

Solved – Why Decision tree is outperforming Random Forest in this simple case

Related Question