Constrained pattern mining extracts patterns based on their individual merit. Usually this results in far more patterns than a human expert or a machine learning technique could make use of. Often different patterns or combinations of patterns cover a similar subset of the examples, thus being redundant and not carrying any new information. To remove the redundant information contained in such pattern sets, we propose a general heuristic approach for selecting a small subset of patterns. We identify several selection techniques for use in this general algorithm and evaluate those on several data sets. The results show that the technique succeeds in severely reducing the number of patterns, while at the same time apparently retaining much of the original information. Additionally the experiments show that reducing the pattern set indeed improves the quality of classification results. Both results show that the approach is very well suited for the goals we aim at.

We present CTC, a new approach to structural classification. It uses the predictive power of tree patterns correlating with the class values, combining state-of-the-art tree mining with sophisticated pruning techniques to find the k most discriminative pattern in a dataset. In contrast to existing methods, CTC uses no heuristics and the only parameters to be chosen by the user are the maximum size of the rule set and a single, statistically well founded cut-off value. The experiments show that CTC classifiers achieve good accuracies while the induced models are smaller than those of existing approaches, facilitating comprehensibility.

Various definitions and frameworks for discovering frequent trees in forests have been developed. At the heart of these frameworks lies the notion of matching, which determines when a pattern tree matches a tree in a data set. We introduce a notion of tree matching for use in frequent tree mining and we show that it generalizes the framework of Zaki while still being more specific than that of Termier et al. Furthermore, we show how Zaki's TreeMinerV algorithm can be adapted towards our notion of tree matching. Experiments show the promise of the approach.