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 :
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.
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 ?