Classi cation Based on Associations (CBA) has for two decades been the algorithm of choice for researchers as well as practitioners owing to simplicity of the produced rules, accuracy of models, and also fast model building. Two versions of CBA di ering in speed { M1 and M2 { were originally proposed by Liu et al in 1998. While the more complex M2 version was originally designated as on average 50% faster, in this article we present benchmarks performed with multiple CBA implementations on the UCI lymph dataset contesting the M2 supremacy: the results show that M1 had faster processing speeds in most evaluated setups. M2 was recorded to be faster only when the number of input rules was very small and the number of input instances was large. We hypothesize that the better performance of the M1 version can be attributed to recent advances in optimization of vectorized operations and memory structures in SciKit learn and R, which the M1 can better utilize due to better predispositions for vectorization. This paper is accompanied by a Python implementation of CBA available at https://pypi.org/project/pyARC/.
CBA (Classi cation Based on Associations) [
In this paper, we investigate the proposition that M2 is faster than M1.
Following the recommendation in [
CMAR, FARC-HD and IDS.
the default (and often the only) supported CBA-CB algorithm. The essential
di erence between M1 and M2 is that M1 takes a straightforward approach to
rule pruning resulting in more operations with data or rules than what is
performed in the M2 version. The M2 version reduces the number of operations,
but this comes at a cost of introducing multiple embedded cycles, counters and
conditions. The hypothesis that we evaluate is that an e cient M1
implementation can take advantage of highly optimized vectorized operations available in
modern scienti c computing environments such as sci-kit learn [
The comparison between M1 and M2 can either be performed analytically or empirically. The rst option would entail analysis of all operations, taking into account their costs. However, the costs can di er dramatically based on the chosen implementation. Therefore, we have decided to perform the comparison empirically through a benchmark involving our reimplementation of CBA M1 and M2, as well as existing maintained implementations of the CBA algorithm. This paper is organized as follows. In Section 2 we brie y outline the CBA algorithm. The CBA implementations used in our benchmarks are covered in Section 3. Section 5 gives an overview of the benchmark setup. Finally, Section 6 presents the results and discusses their implications for choice of the right CBA version for given task. The conclusions present the limitations of our research, state availability of our CBA implementation and benchmarking code, and outline future work. 2
While relatively dated, CBA is used as a reference state-of-the-art algorithm in
many recent papers in the ARC eld (e.g. [
The CBA algorithm consists of two distinct phases [
The base comparison between M1 and M2 implementations was performed using our pyARC package.2 While we strived to equally well optimize both M1 and
M2 algorithm implementations in pyARC, for better representativeness of the
benchmark we also decided to include other pre-existing CBA implementations:
arulesCBA [
The M1 algorithm, as presented by its authors [
In the rst step, all rules are sorted according to the precedence operator (line 1). In this way, it is ensured that rules with high con dence and support are chosen rst. The rules are then iterated in this order { for each rule, it is tested how many instances the rule satis es. If any instance satis es rule's antecedent and the instance's class matches the consequent, the rule is marked and inserted into temp (line 2-6). After iterating through all the instances, we test if the rule is marked. If it is, it is inserted at the end of the classi er and all the instances in temp are removed from the dataset. The default class is selected (the majority class of the remaining instances). Next, it is evaluated how many errors are made by a classi er C consisting of all rules above the current rule (sorted according to the precedence operator), the current rule and a default rule. The number of errors is associated with the current rule. 3 http://cran.r-project.org/ 4 https://pypi.org/project/fim/ 1 R = sort(R); 2 foreach rule r 2 R do 3 temp = ?; 4 foreach data case d 2 D do 5 if d satis es the conditions of r then 6 store d.id in temp and mark r if it correctly classi es d 7 end 8 end 9 if r is marked then 10 insert r at the end of C ; 11 delete all the cases with the ids in temp from D; 12 select a default class for the current C ; 13 compute the total number of errors of C ; 14 end 15 end 16 Find the rst rule p in C with the lowest total number of errors and drop all the rules after p in C; 17 Add the default class associated with p to the end of C and return C; After all the rules have been iterated, the rule r with the lowest associated number of errors is found, rules below rule r are discarded. A rule with empty antecedent predicting the default class associated with rule r is then appended below r as the last rule of the nal classi er C.
1 Q = ?; U = ?; A = ?; 2 foreach case d 2 D do 3 cRule = maxCoverRule(Cc; d); 4 wRule = maxCoverRule(Cw; d); 5 U = U [ fcRuleg; 6 cRule.classCasesCovered[d.class]++; 7 if cRule wRule then 8 Q = Q [ fcRuleg; 9 mark cRule; 10 11 12 end end else A = A[ < d.id, d.class, cRule, wRule >;
Fig. 2: M2 algorithm, stage 1 [
In response, Liu98integratingclassi cation proposed the M2 version of CBA-CB. Liu98integratingclassi cation state that M2 needs to go through the dataset less than two times.
M2 can be divided into three distinct stages. For each instance, two rules are found by traversing the set of sorted rules { cRule, which classi es the instance correctly, and wRule, which classi es it incorrectly. If cRule has precedence before wRule, cRule is marked it means cRule will be chosen before wRule when building a classi er. If wRule has higher precedence, the situation is more complex and the wRule and crule need to be stored in a separate data structure. wSet = allCoverRules(U , dID.case, cRule); foreach entry w 2 wSet do w:replace = w:replace [ f< cRule, dID, y >g; w.classCasesCovered[y]++ The goal of the second stage is to traverse all con icting data structures in A. For each one, we check if wRule is marked. If it is, wRule is a cRule of another instance. In that case, the support and con dence counts are adjusted so that they correctly re ect the support and con dence of said rule. The second stage is depicted in Figure 3. 5 In subsequent iterations, the dataset shrinks since some instances have been removed. 1 classDistr = compClassDistr(D); 2 ruleErrors = 0; 3 Q = sort(Q); 4 foreach rule r 2 Q do 5 if r.classCasesCovered[r.class] 6= 0 then 6 foreach entry < rul; dID; y >2 r.replace do 7 if the dID case has been covered by a previous r then 8 r.classCassesCovered[y]{; 9 end 10 else rul.classCasesCovered[y]{ 11 end 12 ruleErrors = ruleErrors + errorsOfRule(r); 13 classDistr = update(r, classDistr); 14 defaultClass = selectDefault(classDistr); 15 defaultErrors = defErr(defaultClass, classDistr); 16 totalErrors = ruleErrors + defaultErrors; 17 Insert < r; def ault class; totalErrors > at end of C; 18 end 19 end 20 nd the rst rule p in C with the lowest total number of errors and drop all the rules after p in C; 21 Add the default class associated with p to the end of C and return C; In the third stage, the nal assembly of the classi er takes place. First, we iterate for every rule r in Q. For each such rule (line 7-11), all rules which could be replaced by rule r are checked. If the checked instance has already been covered by previous rule, support and con dence counts are adjusted. Next steps include { as in M1 { calculating total error count and nding the default rule. Then, the rule with the lowest number of total errors is found and the remaining rules are removed from the classi er. 5
We used the Lymph dataset from the UCI repository6. We chose lymph, because
it is included in the original benchmark by [
We perform two types of benchmarks: sensitivity of processing speed to a) changes in rule count and b) to changes in the data size.
For the rule count sensitivity comparison, input rules were generated using the arules R package with the following parameters: confidence = 0, support = 0.01, minlen = 1, maxlen = 20. The arules-based generation was applied to all implementations except for pyARC, which used the topRules function from the arc package to generate the same number of input rules as in the arules-based generation.
The list of generated rules was subsampled at di erent sizes and passed to the benchmarked packages. Only execution time of the classi er-building step (CBACB) was measured. The run time for each rule count threshold was measured ten times and the results were averaged. The benchmarking scripts are available on GitHub.7 For the data size sensitivity comparison, only the rst 100 rules generated in the previously described setting were used. To generate various data size thresholds, the training data were doubled at each iteration by oversampling. The benchmark was run on a machine with two cores (Intel Core M-5Y10 CPU @ 0.8GHz) and 8GB of RAM. The package versions used for the benchmark are: arc: 1.2, rCBA: 0.4.2, arulesCBA: 1.1.3-1. 6
In the rst benchmark, we varied the number of rules on the output of CBARG, keeping the data size constant. As Figure 5a shows, pyARC-M1 followed by pyARC-M2 were the fastest implementations irrespective of the number of input rules. A detailed comparison between pyARC-M1 and pyARC-M2 provided by Figure 5b shows that pyARC-M1 was at least three times faster than pyARC-M2 across the whole range.
(a) All implementations 7 https://github.com/jirifilip/pyARC/tree/master/notebooks/benchmark (a) All implementations
(b) pyARC implementation In the second benchmark, we varied the size of the input datasets, keeping the number of rules constant. The results depicted in Figure 6a show that the arc (M1) implementation, followed by pyARC-M1 were fastest for data set size up to about 133.120 instances. A detailed comparison between pyARC-M1 and pyARC-M2 provided by Figure 6b shows that the performance gap increases in favour of M1 when the number instances grows.
Two somewhat outlying patterns can be observed from Figure 5a and Figure 6a.
First, arc (M1) is the slowest implementation when the number of rules is high,
and the fastest implementation (up to 133.120 instances) in the second
benchmark focused on increasing the number of input rules. Deterioration of
performance for high number of input rules is generally not an issue for CBA
implementations, since classi cation accuracy starts to plateau between 60.000-80.000
input rules [
Overall, the results show that M1 version of CBA is faster than M2 in most benchmarked combinations. 7
The experiments presented in this paper contest the previously held belief that
M2 version of CBA is always faster than the M1 version. To ensure robustness of
our results, we followed crossvalidation, averaged execution times from repeated
experiments, and chose a dataset originally used in [
A by-product of our research is the rst (to our knowledge) CBA implementation in Python. According to the performed benchmarks, pyARC is highly competitive with existing CBA implementations in other languages. The pyARC package provides a scikit-learn-like interface, which makes it easy to use and further extend. pyARC is available at GitHub, and can be downloaded via pip or easy install.
Acknowledgments This research was supported by grant IGA 33/2018 and institutional support for research activities of the Faculty of Informatics and Statistics, University of Economics, Prague.