Complexity-based parallel rule induction for multiclass classification

To classify multiclass classification problems in RIPPER, classes are first sorted according to the increasing order of their prior probabilities. The rules for each class are then learned in that order. This learning process has two major shortcomings: (1) the order of class learning has a significant impact on the outcome of the classification, such that different permutations of classes perform differently; (2) the order in which the rules are learned is very important because the first rule to be fired determines the class of the instance. However, the correct class could be identified by another rule further down the list that is ignored and thus never examined. This paper offers two contributions that extend RIPPER to multiclass classification problems and address the mentioned shortcomings. The first issue is resolved by giving all of the classes an equal opportunity for rule extraction, and the class complexity is calculated using the description length. In the second execution of the algorithm, to learn each new rule, the complexity of the rules in each class is computed such that the class with the lowest remaining complexity is selected to determine the next rule. This algorithm is known as Complexity-based Parallel Rule Learning (CPRL), which can overcome the problem from the order of classes in rule learning. Furthermore, a Genetic Algorithm (GA) is developed to find the near optimal order of the rules with Evolutionary Reordering of the rules in the Decision list (ERD), which mitigates the second problem. Experimental results on 20 data sets demonstrate that the proposed algorithm outperforms RIPPER and can be considered to be a promising alternative for multiclass classification problems.