State-of-the-art rule mining algorithms rely on summarizing the training set into efficient data structures which allow to quickly answer arbitrary conjunctive queries about the data. The key limitation of such techniques is their memory consumption. Pre-post code trees (PPC-trees) which are the basis of several efficient association and classification rule mining algorithms, are only constructed as an intermediate representation and subsequently converted into a much more efficient N-lists structure. In this paper, we introduce partial pre-post code trees (P3C-trees), which are based on the idea that partial trees are iteratively constructed, and immediately converted into N-lists. This tight integration of these phases allows to avoid the memory bottleneck of a full PPC-tree construction, and thus enables these algorithms to tackle the memory scalability problem posed by large-scale datasets. Our experiments with big datasets confirm that the memory used by P3C-tree is orders of magnitude smaller than the memory consumed by PPC-tree, and the generated N-lists are also more effective than alternative structures such as Tidset or Diffset. Moreover, the N-list construction can also be considerably sped up with the P3C-tree structure.

Abstract Conventional rule learning algorithms aim at finding a set of simple rules, where each rule covers as many examples as possible. In this paper, we argue that the rules found in this way may not be the optimal explanations for each of the examples they cover. Instead, we propose an efficient algorithm that aims at finding the best rule covering each training example in a greedy optimization consisting of one specialization and one generalization loop. These locally optimal rules are collected and then filtered for a final rule set, which is much larger than the sets learned by conventional rule learning algorithms. A new example is classified by selecting the best among the rules that cover this example. In our experiments on small to very large datasets, the approach’s average classification accuracy is higher than that of state-of-the-art rule learning algorithms. Moreover, the algorithm is highly efficient and can inherently be processed in parallel without affecting the learned rule set and so the classification accuracy. We thus believe that it closes an important gap for large-scale classification rule induction.