Decision rules are one of the most interpretable and flexible models for data mining prediction tasks. Till now, few works presented online, any-time and one-pass algorithms for learning decision rules in the stream mining scenario. A quite recent algorithm, the Very Fast Decision Rules (VFDR), learns set of rules, where each rule discriminates one class from all the other. In this work we extend the VFDR algorithm by decomposing a multi-class problem into a set of two-class problems and inducing a set of discriminative rules for each binary problem. The proposed algorithm maintains all properties required when learning from stationary data streams: online and any-time classifiers, processing each example once. Moreover, it is able to learn ordered and unordered rule sets. The new approach is evaluated on various real and artificial datasets. The new algorithm improves the performance of the previous version and is competitive with the state-of-the-art decision tree learning method for data streams.  Categories and Subject Descriptors In machine learning and particularly for classification tasks, decision trees are among the most popular tools: Decision trees exhibit high predictive capability, high degree of interpretability, and efficient algorithms are available. A decision tree can be converted to a set of IF-THEN decision rules. Each path from the root to a leaf generates a rule, and there are so many rules as leaves in the tree. The main advantage of decision rules is that each rule can be processed independently of the others. Although generating rules from decision trees is a common approach, several approaches learn such rule sets directly from data. In stream mining scenarios, decision trees are also popular, but few works address the problem of rule learning. One of the pioneer Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. works was presented in [13] . The authors introduced VFDR, an incremental classifier that is able to induce a set of rules (ordered or unordered) by scanning the data only once. In this work, we followed the concept and focused on the fact that many off-line learning approaches decompose a multi-class problem into twoclass problems in order to achieve better results. We present Very Fast Decision Rules for Multi-Class problems (VFDR-MC) which is an extension to the rule set classifier for data streams VFDR. The contribution of this work is three-fold. First, VFDR-MC focus on the multi-class learning tasks and decomposes them into two-class problems. Second, it employs different criterion to find a new condition for rule expansion. Third, when expanding a rule it can create multiple rules from the original rule, each one for different class. The paper is organized as follows. The next section discusses related work in rule learning and handling multi-class problems. The VFDR-MC system is presented in Section 3 and the experimental results are in Section 4. Finally, Section 5 concludes the paper and presents future work directions. As it was mentioned before, a widely used strategy consists of building decision lists from decision trees, being C4.5rules [19] the most representative system in the literature. In any decision tree, the set of conditions in the path from the root to a leaf define the conditional part of a rule, whereas the class-label assigned to the leaf defines the conclusion of that rule. Each rule corresponds to the path from the root to a leaf, and there are as many rules as leaves. However, it has been shown that the antecedents of individual rules may contain irrelevant conditions. Empirical studies [19] have shown that the optimized set of rules is both simpler and more accurate than the initial tree. In [10] authors present a method for generating rules from decision trees without using global optimization. The basic idea is to generate a decision tree in a breadth-first order, select the best rule, remove the examples covered by the rule and iteratively induce further rules for the remaining instances. Several algorithms appear in the literature for building decision lists [20, 4, 5, 6, 23] with different capabilities and approaches to handle multi-class problems. The first proposed version of CN2 [4] evaluates every possible complex, i.e., conjunction of attribute tests (if-condition) of a rule, based on information-theoretic entropy measure. Namely, this classifier is able to learn multiple classes assigning the rule the most common class of examples covered by rule's complex. In its improved version [3] , the entropy measure is replaced by Laplace accuracy estimate and the main loop of rule set algorithm searches the rules for each class in turn each time separating one (positive) from all the others (negative) as two-class problem. Only positive examples that satisfy learned rule are removed from the training set for next iteration of the rule search. 795
The system is further extended in REF to focus the attention on learning rules for various classes of labeled data and it can induce multiple rules (one for each such class) at one point when specialization is evaluated.
Very Fast Decision Rules for multi-class problems
SAC '12
Computer Science