QChi: A Faster Classification Algorithm Based on Wang-Mendel Algorithm

Abstract

To address learning problems in which many examples and variables are involved, the use of algorithms that are capable of processing the data using simple and efficient techniques is required. The Wang and Mendel algorithm applied to classification (also known as the Chi algorithm) satisfies these properties in many cases. However, in particularly complex problems, such as those provided by big data, it has become necessary to use architectures for parallel processing, such as MapReduce, whose base algorithm is just this algorithm. The use of these architectures is necessary because the bottleneck of the algorithm is the calculation of the weight of the rules. This calculation requires, for each selected rule, to consider the adaptation of all the examples with this rule. Although this calculation is polynomial-order, in problems with many examples and where many rules are generated, it is very time consuming. In this article, we propose Quick Chi (QChi), a new algorithm based on the Wang-Mendel algorithm that uses, among other changes to make it efficient, a new way of calculating the weights of the rules that is much less computationally expensive. The reduction in learning time is so significant that it allows the algorithm to tackle big data problems without parallel processing structures. In addition to the description of the algorithm, this article checks experimentally on a wide variety of problems, including those that other authors have used as big data problems that this algorithm drastically reduces the learning time while maintaining the classification performance.