Detecting a consistent pattern in a dataset via Decision Trees and cross-validation

Question

Assume a classification problem where there are two classes and the aim is to detect a consistent pattern which successfully separates the input dataset regardless of how we divide it into training / testing. The broader question is does such a consistent pattern exist across different partitions of the dataset at hand ? Let's assume that the classification is done by decision trees (e.g. J48). Also, suppose that a k-fold cross-validation is done to evaluate how consistent the pattern is across different combinations of training / testing. In each fold the testing sets contains completely unrelated and never before seen samples by the training phase. Although some folds may yield the same tree, it's very likely that the majority of folds will yield a different decision tree, in other words a different pattern. I would like to ask the following questions :

1. If each fold reports a different decision tree but gives good classification accuracy, does this mean there is no consistent pattern ? Off course there may be a lot of ways to divide a dataset, not all of them covered by a k-fold validation.

2. Cross-validation aims to assess the performance of a classifier. But when each fold yields a completely different decision tree, does it make sense to assess the performance only by looking at the classification accuracy AUC, TP/FP rates ? Is the diversity/variability of models (usually pruning trees is responsible for that behavior) a sign of a poor classifier or an indication of a complex dataset ?

Answer 1

Decision trees are notoriously unstable: small perturbations in the training data can produce dramatically different trees, even though these trees can, and often do, perform about the same on held-out data. Decision trees are particularly prone to this because they make a series of sequential decisions and the decisions are discrete.

If you just want to classify your data, this isn't really an issue. Cross-validation is telling you that your approach (training a decision tree) works with your data. Assuming the performance is acceptably high, I'd fit a final tree with all of the data and deploy it.

It is worth noting that this instability can actually be turned to your advantage. Model-averaging or ensemble methods fit a collection of decision trees, using subsets of the data/features each time. The results of these trees are then combined and used to make predictions. This is the idea behind bagging and random forests.

On the other hand, if you need to examine the structure of your decision tree, there have been a couple of attempts at creating more stable decision trees, like this and this paper