11institutetext: Department of Information and Knowledge Engineering, Faculty
of Informatics and Statistics, University of Economics Prague, W Churchill sq.
4, Prague, Czech Republic
11email<EMAIL_ADDRESS>
# QCBA: Postoptimization of Quantitative Attributes in Classifiers based on
Association Rules

Tomáš Kliegr

(Received: date / Accepted: date)

###### Abstract

The need to prediscretize numeric attributes before they can be used in
association rule learning is a source of inefficiencies in the resulting
classifier. This paper describes several new rule tuning steps aiming to
recover information lost in the discretization of numeric (quantitative)
attributes, and a new rule pruning strategy, which further reduces the size of
the classification models. We demonstrate the effectiveness of the proposed
methods on postoptimization of models generated by three state-of-the-art
association rule classification algorithms: Classification based on
Associations (Liu, 1998), Interpretable Decision Sets (Lakkaraju et al, 2016),
and Scalable Bayesian Rule Lists (Yang, 2017). Benchmarks on 22 datasets from
the UCI repository show that the postoptimized models are consistently smaller
– typically by about 50% – and have better classification performance on most
datasets.

###### Keywords:

association rule classification CBA quantitative association rule learning
rule list optimization interpretable machine learning

##  1 Introduction

Current rule learning algorithms can be divided into two categories depending
on how they learn rules and process quantitative attributes: variations on
separate-and-conquer approach natively supporting quantitative (numerical,
continuous) attributes, and association rule-based classification approaches,
which work only on nominal data but owing to this can be very fast on datasets
with many instances and high dimensions. This paper focuses on the inability
to process quantitative attributes in existing association rule classification
algorithms. These address this limitation by discretization, which is
performed as part of preprocessing. For example, the “temperature” attribute
would be automatically split to intervals such as [10;20), [20;30), $\ldots$,
which are then used as independent nominal categories during rule mining. We
propose several rule tuning steps aiming to recover information lost in the
discretization of quantitative attributes. We also propose a new rule pruning
strategy, which further reduces the size of the classification model.

The work presented here was initially inspired by Classification Based on
Associations (CBA) algorithm Liu98integratingclassification , and since the
aim is to incorporate quantitative information, we call the resulting
framework “Quantitative CBA”. The framework can also be used with other rule
learning approaches that rely on prediscretized data, which we demonstrate on
the case of the recently proposed Interpretable Decision Sets (IDS) algorithm
by Lakkaraju et al, 2016 lakkarajuinterpretable  and Scalable Bayesian Rule
Lists (SBRL) algorithm by Yang et al, 2017 yang2017scalable .

The main contributions of this article are:

  * •

A novel approach for recovering information lost in prediscretization based on
postprocessing association rule models.

  * •

All proposed rule tuning steps have clear motivation supported by two
dimensional visualizations of the effect on rule coverage, documented
complexity, and guarantees in terms of the effect on selected rule quality
measures. An ablation study provides an empirical evaluation of the effect on
classifier performance, model size, and runtime.

  * •

Benchmark on 22 UCI datasets shows consistent improvements as opposed to all
three baseline association rule classification algorithms.

  * •

Robust implementation available for R and Python, including code for
reproducing the benchmark.

This paper is organized as follows. Section 2 provides a brief introduction to
association rule classification. Section 3 introduces the proposed rule tuning
and pruning steps. Section 4 contains the experimental validation and
discusses the benefits and limitations of the presented approach. Section 5
provides a comparison of the presented approach with related work. The
conclusions summarize the contributions and point to the publicly available
implementation of the framework. To facilitate reproducibility, Appendix A
contains detailed pseudocode listings for all proposed algorithms. Appendix B
complements Section 2 by providing a more formal introduction to the problem
of association rule classification. The definitions introduced in this
appendix are referenced from Appendix C, which presents an analytical
evaluation of individual tuning steps in terms of their complexity, and also
in terms of their effect on predictive performance and model size.

There are several complimentary online resources. The code expanding on the
short continuous example included in the paper, featuring some additional
visualizations and animations, is at
http://nb.vse.cz/~klit01/qcba/tutorial.html. The implementation of the
proposed algorithms for the R environment (with performance-intensive parts
implemented in Java) is available under an open license at
http://github.com/kliegr/qcba (also available in the CRAN package repository).
An alternative third-party Python implementation is available at
https://github.com/jirifilip/pyARC/ (also available in the PyPi package
repository). Detailed evaluation results as well as instructions for
replication are available at http://github.com/kliegr/arcBench.

An earlier version of this paper has been posted on the arXiv preprint server
as kliegr2017quantitative . An initial version of this article was published
as a part of the author’s PhD thesis at Queen Mary University of London
kliegr2017effect .

##  2 Preliminaries: Association Rule Learning and Classification

In this section, we introduce the association rule learning and classification
tasks, and then we briefly review selected association rule classification
algorithms, comparing them in terms of their main properties: predictive
accuracy, comprehensibility of the produced models and run-time. This
comparison will serve as a basis for selection of representative algorithms
that will be postprocessed by the proposed framework.

###  2.1 Association Rule Learning

Association rule learning is an algorithmic approach that was originally
designed to discover interesting patterns in very large and sparse instance
spaces DBLP:conf/sigmod/AgrawalIS93 . Quantitative features (attributes) need
to be discretized prior to the execution of association rule learning and
converted along with all nominal attributes to binary-valued features. The
resulting rules correspond to high-density regions in data with boundaries
aligned to the discretization breakpoints. This impairs precision, but
improves computational efficiency on high-dimensional data, allowing
association rule learning to be applied to much larger data than amenable to
other types of analyses (friedman2009elements, , p. 492).

The output of association rule learning algorithms is determined typically by
two parameters: minimum confidence and support thresholds. The confidence of a
rule is defined as $conf(r)=a/(a+b)$, where $a$ is the number of correctly
classified objects, i.e. those matching rule antecedent as well rule
consequent, and $b$ is the number of misclassified objects, i.e. those
matching the antecedent, but not the consequent. The support of a rule is
defined as $supp(r)=a/n$, where $n$ is the number of all objects (relative
support), or simply as $a$ (absolute support). The main obstacles for a
straightforward use of the discovered association rules as a classifier is the
excessive number of rules discovered even on small datasets, and the fact that
the generated rules can be contradicting and incomplete (no matching rule for
a certain valid combination of attribute values).

###  2.2 Building an Association Rule Classifier

Association rule learning was adopted also for classification several years
after its conception in the early 90’s. The first Association Rule
Classification (ARC) algorithm dubbed CBA (Classification based on
Associations) was introduced in 1998 Liu98integratingclassification . While
there were multiple follow-up algorithms, the structure of most ARC algorithms
follows that of CBA arcReview :  1. learn classification association rules,
2. select subset of association rules,  3. classify new objects.  In the
following, we briefly describe the individual steps.

#### Rule Learning

In the first step of an ARC framework, standard association rule learning
algorithms are used to learn conjunctive classification rules from data. The
mining setup is constrained or the algorithms adapted so that only the target
class can occur in the consequent of the rules.

The Apriori algorithm DBLP:conf/sigmod/AgrawalIS93  association rule learning
algorithm was used in CBA, but also in the recently proposed Interpretable
Decision Sets (IDS) lakkarajuinterpretable  algorithms. Some other algorithms,
such as Bayesian Rule Sets (BRS) wang2017bayesian  use FP-Growth
Han:2004:MFP:954514.954525 , while other algorithms such as CORELS
angelino2017learning  and Scalable Bayesian Rule Lists (SBRL) yang2017scalable
are explicitly agnostic about the underlying rule learning algorithm.111The
reference SBRL implementation uses ECLAT zaki2000scalable .

The large number of rules discovered even on small datasets with association
rule learning provides both an opportunity and a challenge for ARC algorithms:
there is a large base of rules to select from, but this selection process
needs to be fast, effective and cope with the presence of contradicting rules.

#### Rule selection (also called pruning)

A qualitative review of rule selection (pruning) algorithms used in ARC is
presented in thabtah2006pruning ; arcReview . The most commonly used method
according to these survey papers is _data coverage pruning_. This type of
pruning processes the rules in the order of their strength, removing
transactions (instances, objects) that the rule matches from the database. If
a rule does not correctly cover at least one instance, it is deleted. In CBA,
data coverage pruning is combined with “default rule pruning”: the algorithm
replaces all rules below the current rule if a default rule inserted at that
place would reduce the number of errors. Default rule is a rule with empty
antecedent, which ensures that a query instance is always classified even if
it is not matched by any other rule in the classifier. The effect of pruning
on the size of the rule list is reported in Liu98integratingclassification .
Based on experiments on 26 datasets, the authors reported the following effect
of data coverage pruning: the average number of rules per dataset without
pruning was 35,140; with pruning the average number of rules was reduced to 69
without effectively impacting accuracy.

The latest ARC algorithms use optimization algorithms to select subset of the
candidate rules generated by association rule learning. For example, the IDS
algorithm optimizes objective function, which reflects accuracy of the
individual rules as well as multiple facets of model interpretability,
including number of rules.

#### Classification

There are two principal types of ARC algorithms differing in the way
classification is performed: rule sets and rule lists.

The CBA algorithm, as well as some recent approaches, such as SBRL and
IDS222While the algorithm uses the term “sets” in its title, the generated
models are actually lists. produce rule lists. These are conditional
structures used for “one rule” classification: instance is assigned to the
class in the consequent of the first rule in the ordered list of rules, whose
antecedent matched the instance. The advantage of rule lists is that it is
easy to explain a classification of a particular instance, since always only
one rule is accountable for it DBLP:conf/ruleml/KliegrKSV14 .

Rule sets provide an alternative approach, where multiple rules with matching
antecedents are used to classify the instance. An example of an ARC approach
combining multiple rules to perform classification is CPAR, or recently BRS.

###  2.3 Overview of Association Rule Classification Algorithms

The main benefit of using a rule-based classifier, as opposed to a state-of-
the-art sub-symbolic method such as a deep neural network, should be the
comprehensibility of the rule-based model, combined with fast execution on
large and sparse datasets and accuracy comparable to state-of-the-art “black-
box” classification models. Individual ARC algorithms meet these aspirations
to a different degree. Table 1 presents a comparison between the ten most
well-known ARC algorithms and closely related approaches in terms of several
comprehensibility metrics, accuracy, and performance.

As follows from Table 1, CBA produces more comprehensible models than any of
its successors while maintaining high accuracy and fast execution times. In
terms of accuracy, CBA is outperformed only by FARC-HD (by 4%) and CPAR (by
2%). However, CPAR has 4x times more rules on the output and performs multi-
rule classification, which is possibly less comprehensible than the one-rule
classification in CBA. While FARC-HD outperforms CBA in terms of accuracy,
this fuzzy rule learning algorithm is more than 100x slower than CBA.

Note that Table 1, which is based on data from alcala2011fuzzy , excludes
several relevant recently proposed algorithms. These typically subject the
input rule set generated by association rule learning to a sophisticated
selection process, involving optimization techniques such as Markov Chain
Monte Carlo (in SBRL), branch-and-bounds (in CORELS), submodular optimization
(in IDS) or simulated annealing (in BRS). A comprehensive previously published
benchmark on a larger number of datasets is not to our knowledge available,
nevertheless, these algorithms are widely considered as state-of-the-art in
the area of association rule classification (e.g. in wang2018multi ). We
selected SBRL and IDS as two additional algorithms, which will be
postprocessed with our approach, as reported in the Experiments section. We
have not included BRS, because it produces rule sets, while our approach is
primarily intended for rule lists. The evaluation of the postprocessing of
CORELS models is left for future work.

algorithm |  year |  single |  crisp |  det |  assoc |  acc |  rules |  time
---|---|---|---|---|---|---|---|---
CBA Liu98integratingclassification  |  1998 |  yes |  yes |  yes |  yes |  .80 |  185 |  35s
CBA 2 liu2001classification  |  2001 |  yes |  yes |  yes |  yes |  .79 |  184 |  2 m
2SLAVE gonzalez2001selection  |  2001 |  no? |  no |  no |  no |  .77 |  16 |  22m
CMAR li2001cmar  |  2001 |  no |  yes |  yes |  yes |  .79 |  1419 |  6m
CPAR Yin03cpar:classification  |  2003 |  no |  yes |  yes |  yes |  .82 |  788 |  11s
LAFAR hu2003finding  |  2003 |  no |  no |  no |  yes |  .75* |  47* |  5h*
FH-GBML ishibuchi2005hybridization  |  2005 |  no |  no |  no |  no |  .77 |  11 |  3h
CFAR chen2008building  |  2008 |  yes |  no |  yes |  yes |  .71* |  47* |  17m*
SGERD mansoori2008sgerd  |  2008 |  no? |  no |  no |  no |  .74 |  7 |  3s
FARC-HD alcala2011fuzzy  |  2011 |  no? |  no |  no |  yes |  .84 |  39 |  1h 20m
Table 1:  Comparison between CBA and other association rule (or closely
related) classifiers. _single_ refers to single rule (one rule)
classification, _crisp_ to whether the rules comprising the classifier are
crisp (as opposed to fuzzy), _det._ to whether the algorithm is deterministic
with no random element such as genetic optimization, _assoc_ corresponds to
whether the method is based on association rules, _acc_ , _rules_ and _time_
is average accuracy, average rule count and average time across 26 datasets as
reported by alcala2011fuzzy . * indicates that the algorithm did not process
all datasets

##  3 Proposed Approach

The proposed method333Referred to as QCBA (Quantitative Classification By
Associations) in the following. composes of a collection of rule tuning steps
that use the original continuous data to “edit” the rules, refining the scope
of literals (conditions, attribute-value pairs) in the antecedent of the
rules. As a consequence, the fit of the individual rules to data improves,
rendering some of the rules and literals redundant. These can be removed,
making the classifier smaller. The resulting models are ordered rule lists
with favourable comprehensibility properties, such as one-rule classification
and crisp rules. The individual rule tuning steps are associated with
guarantees, which are presented in Appendix C.

The method takes on the input:

  * •

set of rules learnt on prediscretized data,

  * •

original source data with numeric attributes before discretization.

The output is an ordered classification rule list, which has the same or
smaller number of rules than the (unordered) input rule set. The individual
rules in the rule list have the boundaries of numerical conditions (literals)
adjusted, some conditions may also be completely removed. The first phase
consists of the following rule tuning (optimization444We prefer to use the
term “tuning”, because the term “optimization”, which is used in the same
context in some other papers, such as huhn2009furia , evokes application of
mathematical programming. ) steps:

  1. 1.

Refitting rules to value grid. Literals originally aligned to borders of the
discretized regions are refit to a finer grid with steps corresponding to all
unique attribute values appearing in the training data.

  2. 2.

Literal pruning: Remove redundant literals from rules.

  3. 3.

Trimming. Boundary regions with none correctly covered instances are removed.

  4. 4.

Extension. Ranges of literals in the body of each rule are extended preserving
or improving rule confidence.

Once the rules have been extended, they match more objects, which can make
some of the rules redundant. These are removed through the following pruning
steps:

  1. 5.

Data coverage pruning and default rule pruning. These two pruning steps,
proposed in Liu98integratingclassification , correspond to the Classifier
Builder phase of CBA.

  2. 6.

Default rule overlap pruning. Rules that classify into the same class as the
default rule at the end of the classifier can be removed, if there is no other
rule between the removed rule and the default rule that would change the
classification of instances originally classified by the removed rule.

Algorithm 1 QCBA _qcba()_

1:$rules$ – input rule list generated by CBA

2:optimized $rules$

3:

4:$rules\leftarrow$ remove any rules with empty antecedent from $rules$.

5:for $rule\in rules$ do {process rules in the sort order given by Fig. 3}

6: $rule\leftarrow refit(rule)$ {cf. Alg. 2}

7: $rule\leftarrow pruneAttributes(rule)${cf. Alg. 3}

8: $rule\leftarrow trim(rule)${cf. Alg. 4}

9: $rule\leftarrow extendRule(rule)$ {cf. Alg. 5, 6}

10:end for

11:_rules_ $\leftarrow postprune(rules)$ {cf. Alg. 7, postpruning adds a new
default rule, if postpruning is disabled, QCBA ensures that default rule is
added at this point.}

12:_rules_ $\leftarrow drop(rules)$ {cf. Alg. 8 for transaction-based version
and Alg. 9 for range-based version of default rule overlap pruning}

13:return $rules$

Algorithm 1 depicts the succession of tuning steps in QCBA and provides
pointers to algorithms described in detail in the following subsections. The
remaining pseudocode listings are in Appendix A.

###  3.1 Example

In order to illustrate the rule tuning steps, we will use the humtemp
synthetic data set. The dataset is plotted in Figure 1a. There are two
explanatory attributes (Temperature and Humidity). The target attribute is a
subjective comfort level with values ranging from 0 (worst) to 3 (best).

The grid depicted with the dashed lines denotes the result of a discretization
algorithm, which was performed as part of preprocessing. In this case,
equidistant binning was applied. Figure 1b and Table 2 show an input list of
rules learnt on the humtemp data. In our example, these rules were learnt by
CBA, but other algorithm generating rule lists could also have been applied.

id | antecedent | consequent | conf | supp
---|---|---|---|---
1 | Humidity=(80;100] |  $\rightarrow$ Class=1 | 0.11 | 0.80
2 | Temperature=(30;35] |  $\rightarrow$ Class=4 | 0.14 | 0.63
3 | Temperature=(25;30] and Humidity=(40;60] |  $\rightarrow$ Class=4 | 0.08 | 0.60
4 | Temperature=(15;20] |  $\rightarrow$ Class=2 | 0.11 | 0.57
5 | Temperature=(25;30] |  $\rightarrow$ Class=4 | 0.14 | 0.50
6 |  |  $\rightarrow$ Class=2 | 0.28 | 0.28
Table 2: Textual form of the input rule list depicted in Figure 1b. Predicted
classes are colour coded.

A QCBA model generated after all tuning steps is shown in Fig. 1c. Fig. 1e-h
correspond to the individual tuning steps, which transformed the original rule
R#3 from the CBA model to its final form in the QCBA Model. These figures will
be referred to again from the detailed description included below.

Figure 1: Illustration of refit, trimming and extension tuning steps

###  3.2 Refit

The refit operation is inspired by the way the C4.5 decision tree learning
algorithm DBLP:books/mk/Quinlan93  selects splitting points for numerical
attributes. Fig. 1d shows rule “Rule #3: Temperature=(25;30] and
Humidity=(40;60] $=>$ Class=4” contained in the CBA model. It can be noticed
that there is some “padding” between the rule boundary and a nearest data
point.

The refit tuning step (Algorithm 2 on page 2) contracts interval boundaries to
a finer grid, which corresponds to the raw, undiscretized attribute values
ensuring that the same instances are covered by the refit rule as by the
original rule.

The red boxes in Figure 1e mark the instances that were used as “anchors” for
the refit of Rule #3. For the literal “Temperature=(25;30]”, the upper
boundary corresponds to an existing instance, therefore there is no change.
Since the lower boundary is exclusive, it is adjusted to the nearest value of
a real instance, which is 26. Since there are no instances with Humidity=40 or
Humidity=60, the boundaries in Rule #3 are adjusted to values of nearest
instances within the original boundaries, resulting in “Humidity=(42;58]”.

###  3.3 Literal pruning

The literal pruning algorithm attempts to remove literals from a rule in a
greedy way. If the confidence of the rule does not drop, the shorter rule is
kept and becomes a seed for further attempts at literal pruning. Literal
pruning is depicted in Algorithm 3 on page 3.

###  3.4 Trimming

This step adjusts the interval boundaries to actual values in covered
instances. If there is any covered but misclassified instance on the boundary,
it is removed, the boundary is adjusted, and this process repeats until no
instance is removed (Algorithm 4 on page 4).

In Figure 1f, trimming has been applied and the rule was shaved of boundary
regions that are not covering any correctly classified instances: one instance
with class 3 (denoted by a red box) on rule boundary was initially covered by
Rule #3, but misclassified by it. As part of trimming, the lower boundary of
the Temperature literal on Rule #3 was increased not to cover this instance.

###  3.5 Extension

The purpose of this step is to move literal boundaries outwards, increasing
the coverage of the rule. Each extension corresponds to a new rule, which is
derived from the current rule by extending boundaries of literals in its
antecedent in one direction with steps corresponding to breakpoints on the
finer grid. The extension process for the current rule generates multiple
extension candidates. These are generated by Algorithm 5. The algorithm refers
to the notion of direct extension of a literal presented in Definition 1:

######  Definition 1.

(direct extension of literal defined over quantitative attribute) Let
$l=(A,V)$ be a cardinal literal, and $V=\langle
x_{i},\ldots,x_{j},\ldots,x_{k}\rangle$ a value range. A direct extension of
$l$ is a set $E_{l}$ of up to two literals derived from $l$: higher direct
extension and lower direct extension. A higher direct extension of $l$ is a
literal $l_{H}=(A_{i},V^{\prime})$, where $V^{\prime}=\langle
x_{i},\ldots,x_{j},\ldots,x_{k},x_{k+1}\rangle$. A lower direct extension of
$l$ is a literal $l_{L}=(A_{i},V^{\prime})$, where $V^{\prime}=\langle
x_{i-1},x_{i},\ldots,x_{j},\ldots,x_{k}\rangle$.

The direct extension of a literal is used to create direct extension of a rule
(cf. Definition 2):

######  Definition 2.

(direct extension of rule) Let $r$ be a rule with literals
$l_{1},\ldots,l_{n}$ in its body. Let $L_{1},\ldots,L_{n}$ be sets of
literals, which are direct extensions of literals $l_{1},\ldots,l_{n}$. A
direct extension of rule $r$ is a set of $m$ rules $R=\\{r_{i,j}\\}$, where
$m=\sum^{n}_{i=1}{|L_{i}|}$: for each $l_{i}$ in the body of $r$, there are
$|L_{i}|$ rules in R, $r_{i,1}\ldots r_{i,|L_{i}|}$, each created by replacing
$l_{i}$ in $r$ with literal $l_{j}\in L_{i}$ for $j=1,\ldots,|L_{i}|$.

Note that a formal definition of rule, literal, value range and value
referenced from the two definitions above, is included in Appendix B.

An extension is accepted if there is an improvement in confidence over the
last confirmed extension by a user-set $minImprovement$ threshold (see
criteria for _crisp accept_ in Fig. 2 top). If multiple extension rules meet
the crisp accept criteria, the extension rules are sorted according to
criteria depicted in Fig. 3. The first ranked extension rule replaces the
current rule and becomes a new seed for further extensions.

Assuming $minImprovement=0$, the crisp extension process is finished, when the
confidence of the best possible extension drops for all candidates below the
confidence of the original rule.555$minImprovement>0$ can be used to reduce
the number of evaluated extensions. In other words, the extension is stopped
when extending the current rule by one step in any of the literals in rule
antecedent does not result in a crisp accept. The complete extension process
is depicted in Algorithm 6 on page 6.

Inputs:

  1. 1.

$\Delta_{conf}=confidence(\mbox{refined rule})-confidence(\mbox{original
rule})$

  2. 2.

$\Delta_{supp}=support(\mbox{refined rule})-support(\mbox{original rule})$

Crisp accept: rule is accepted if confidence improves at least by
$minImprovement$ and support of the rule does not drop below the original rule
on the input of extension:

  1. 1.

IF $\Delta_{conf}\geq minImprovement$ and  $\Delta_{supp}\geq 0$ then true

  2. 2.

ELSE false

Conditional accept: rule is conditionally accepted if confidence improves at
least by $minCondImprovement$:

  1. 1.

IF $\Delta_{conf}\geq minCondImprovement$ then true

  2. 2.

ELSE false

Figure 2: Criteria for crisp and conditional accept

  1. 1.

rule $A$ is ranked higher if confidence of rule $A$ is greater than that of
rule $B$,

  2. 2.

rule $A$ is ranked higher if confidence of rule $A$ is the same as confidence
of rule $B$, but support of rule $A$ is greater than that of rule $B$,

  3. 3.

rule $A$ is ranked higher if rule $A$ has a shorter antecedent (fewer
conditions) than rule $B$.

Figure 3: Rule sorting criteria

To overcome the early stopping of the growth process, e.g. caused by noise in
data, _conditional extension_ is attempted after crisp extension has finished.
The conditional extension process proceeds differently from the crisp
extension in that it first selects one literal and one direction for the
extension. When the criteria for conditional accept are not met, or there is
no other extension candidate since all values were exhausted, the conditional
extension process proceeds to the next literal and direction. In this literal
and direction, the rule is extended by one step at a time corresponding to the
finer grid. Referring to criteria for conditional accept in Fig. 2 bottom,
when $minCondImprovement=-1$, conditional extension is always performed
irrespective of its effect on confidence. If such extension meets criteria for
crisp accept, conditional extension successfully finishes with the extension
replacing the current rule.666$minCondImprovement>-1$ can be used to obtain
faster failure of the conditional extension process, improving performance on
datasets with many distinct values. This process corresponds to the
_getBeamExtension_ procedure referenced from Algorithm 6.

After an extension is crisp-accepted, the process recursively continues by
reevaluating all extensions of the current rule for crisp accept and then for
conditional accept. If no extension for the current rule is crisp accepted,
the extension process for the current rule is finished. Individual rules can
be extended independently, which allows for easy parallelization.

The red boxes in Fig. 1g demonstrate confirmed extension steps for seed rule
depicted in Fig. 1f. In the first confirmed extension, the upper Temperature
boundary is increased to 30 by one step of the finer grid. Since the
confidence of the extended rule does not decrease, this extension meets
conditions for crisp accept. Subsequent extensions result in the rule depicted
by the blue region in Fig. 1f. This rule cannot be further extended in any of
the directions without a drop in confidence. The algorithm tries therefore
conditional extension (red region in Fig. 1h) by lowering boundary of the
Humidity literal to 22. This will make the rule cover two more instances, one
correctly and one incorrectly, decreasing the confidence below the initial
75%. Further extends in Humidity in the same direction, make the rule cover
two more instances correctly, bringing the confidence back at 75% resulting in
a crisp accept. While the algorithm tried additional conditional extensions,
none were successful. Fig. 1c shows the final rule, which has both higher
confidence and support than the original rule in Fig.1d.

###  3.6 Data Coverage Pruning and Default Rule Pruning

The previous steps affected individual rules, changing their coverage. The
number of rules can now be reduced using an adaptation of CBA’s data coverage
pruning, which will also add a default rule to the end of the rule list that
ensures that the rule list covers all possible test instances. As a first step
of the postpruning, rules are sorted according to criteria in Figure 3: The
postpruning algorithm is depicted in Algorithm 7 (page 7) and corresponds to
the core of the CBA algorithm described in Section 2.

###  3.7 Default Rule Overlap Pruning

The default rule overlap pruning iterates through all rules classifying into
the same class as the default rule. These rules all overlap with the default
rule both in terms of coverage and class assigned and are thus candidates for
pruning. They are removed only if their removal will not change classification
of instances which they correctly classify by rules that are between them and
the default rule. We consider two versions of default rule overlap pruning:
transaction-based and range-based.

Figure 4: Illustration of default rule tuning. To demonstrate this tuning
step, this figure uses a different rule list than the previous examples. The
example rule list is intentionally shown from rule #6 (previous rules are not
relevant). The complete list of rules is available at
https://nb.vse.cz/~klit01/qcba/tutorial.html.

The _transaction-based_ version, depicted in Algorithm 8 on page 7, removes a
rule if there is no transaction (instance) in the training data, which would
be misclassified as a result of the removal. Referring to example in Fig. 4,
Rule #6 is the only pruning candidate since other rules assign to different
classes than the default rule (Rule #11). Because none of the rules between #6
and #11 would cause misclassification of instances covered by #6 if #6 is
removed, Rule #6 is removed by transaction-based pruning.

The _range-based_ version, depicted in Algorithm 9, analyzes overlaps in the
range of literals between the _pruning candidate_ – rule that is a candidate
for removal – and all _potentially clashing rules_. A potential clashing rule
is a rule ranked below the pruning candidate with respect to criteria in Fig.
3, which has a different class in the consequent than the pruning candidate.

The pruning candidate is removed only if none of the potential clashing rules
overlaps the region covered by the pruning candidate. Referring to example
data in Fig. 4 left, rules between #6 and #11 cover different geometric
regions, which would be an argument for removing #6. After closer inspection
(Fig. 4 right) we can notice that #6 shares an inclusive boundary on
Temperature (34) with rule #8, which classifies to a different class. Rule #8
is thus a confirmed clashing rule and #6 is not removed.

The range-based pruning imposes more stringent conditions for removal of a
rule than the transaction-based pruning as it checks empty overlap in regions
covered by the rule (as opposed to an overlap in specific instances). As also
can be be seen in our evaluation (Section 4), it thus prunes much fewer rules.

##  4 Experiments

In this section, we present an evaluation of the presented rule tuning steps
comprising the QCBA framework. The scope of the evaluation – in terms of the
number and character of included datasets and reference baselines – was
designed to match or exceed setup adopted in recently published highly
authoritative papers on similar topics.

In lakkarajuinterpretable , the results of IDS were compared against seven
other algorithms, out of these five were general machine learning algorithms
(random forests, decision trees, etc), and two were closely related BDL
(Bayesian Decision Lists) and CBA. In yang2017scalable , the results of SBRL
are compared against nine other algorithms, out of these seven were general
machine learning algorithms (CART, C4.5, RIPPER), and two were closely related
(CBA and CMAR).

In our benchmark, we include three closely related ARC algorithms (CBA, IDS,
and SBRL), and four standard symbolic – intrinsically explainable – learning
algorithms (FURIA, RIPPER, PART, C4.5). Note that the SBRL algorithm is a
newer algorithm from the same team as BDL used in the IDS evaluation, and
since we referred in Table 1 to an earlier authoritative benchmark
demonstrating that CBA outperforms CMAR, therefore there was no reason to
include CMAR into our evaluation. As for the datasets, IDS in
lakkarajuinterpretable  was evaluated on three proprietary datasets and SBRL
in yang2017scalable  on seven publicly available datasets. In our approach, we
used 22 open datasets.

###  4.1 Datasets and Setup

The University of California provides at https://archive.ics.uci.edu a
collection of publicly available datasets, which are commonly used for
benchmarking machine learning algorithms. We chose 22 datasets to perform the
evaluation. The selection criteria were a) at least one numerical predictor
attribute, b) the dataset being previously used in evaluation of symbolic
learning algorithms in one of the following seminal papers: alcala2011fuzzy ;
huhn2009furia ; Liu98integratingclassification ; quinlan1996improved  (ordered
by publication date).

Details of the selected datasets are given in Table 3. Several datasets come
from visual information processing or signal processing domains (ionosphere,
letter, segment, sonar). The second strongly represented domain are medical
datasets (colic, breast-w, diabetes, heart-statlog, lymph). Eleven datasets
are binary classification problems, nine datasets are multinominal (more than
two classes) and two datasets have ordinal class attribute (autos and labour).

dataset | att. | inst. | miss. | class | description
---|---|---|---|---|---
anneal | 39 | 898 | Y | nominal (6) | NA
australian | 15 | 690 | N | binary | credit card applications
autos | 26 | 205 | Y | ordinal (7) | riskiness of second hand cars
breast-w | 10 | 699 | Y | binary | breast cancer
colic | 23 | 368 | Y | binary | horse colic (surgical or not)
credit-a | 16 | 690 | Y | binary | credit approval
credit-g | 21 | 1000 | N | binary | credit risk
diabetes | 9 | 768 | N | binary | diabetes
glass | 10 | 214 | N | nominal (6) | types of glass
heart-statlog | 14 | 270 | N | binary | diagnosis of heart disease
hepatitis | 20 | 155 | Y | binary | hepatitis prognosis (die/live)
hypothyroid | 30 | 3772 | Y | nominal (3) | NA
ionosphere | 35 | 351 | N | binary | radar data
iris | 5 | 150 | N | nominal (3) | types of irises (flowers)
labor | 17 | 57 | Y | ordinal (3) | employer’s contribution to health plan
letter | 17 | 20000 | N | nominal (26) | letter recognition
lymph | 19 | 148 | N | nominal (4) | lymphography domain
segment | 20 | 2310 | N | nominal (7) | image segment classification
sonar | 61 | 208 | N | binary | determine object based on sonar signal
spambase | 58 | 4601 | N | binary | spam detection
vehicle | 19 | 846 | N | nominal (4) | object type based on silhouette
vowel | 13 | 990 | N | nominal (11) | NA
Table 3: Overview of datasets involved in the benchmark. att. denotes number
of attributes, inst. number of instances (objects), miss. whether or not the
dataset contains missing observations.

Numeric (quantitative) explanatory attributes with three or more distinct
values were subject to discretization using the MDLP algorithm
conf/ijcai/FayyadI93 . We used MDLP implementation wrapped in our _arc_
package. Prediscretized data were used only for association rule
classification algorithms (CBA, IDS, SBRL). Remaining algorithms involved in
the benchmark did not require prediscretization. The evaluation was performed
using a 10-fold stratified cross-validation. All evaluations used the same
folds.

Results were obtained using open source CBA and QCBA implementations in arc
and qcba packages, which we made available in the CRAN repository of R
language. The evaluation was performed on a Linux machine equipped with 32 GB
of RAM memory, SSD disks, and Intel core i5 processor.

###  4.2 Ablation Study

The CBA algorithm has three hyperparameters – minimum confidence, minimum
support thresholds and the total number of candidate rules. In
Liu98integratingclassification  it is recommended to use 50% as minimum
confidence and 1% as minimum support. For our experiments, we used these
thresholds. In Liu98integratingclassification  the total number of rules used
was 80.000, however it was noted that the performance starts to stabilize
already around 60.000 rules. According to our experiments (not included in
this article), there is virtually no difference between the 80.000 and 50.000
thresholds apart from the higher computation time for the former, therefore we
used 50.000.777In our best setup, we observed less than 0.1% improvement in
average accuracy and 5% increase in average rule count when the maximum number
of rules was increased from 50.000 to 80.000. We also limited the maximum
number of literals in the antecedent to 5. For the standalone CBA run, default
rule pruning was used as described Liu98integratingclassification , otherwise
it was not performed within CBA.888Preferably, QCBA should obtain on its input
model built with CBA, but with default rule pruning not performed to obtain
more rules for tuning. Such variation of CBA is not reported to be separately
described in Liu98integratingclassification  or in other prior research. Our
CBA implementation was thus adapted to allow deactivation of default rule
pruning.

The proposed tuning steps do not have any mandatory thresholds. The extension
process contains two numeric parameters, which were left set to their default
values: _minImprovement=0_ and _minCondImprovement=-1_. These default values
have natural explanations (cf. Section 3.5) and the tuning of these thresholds
can be generally recommended only for improving runtime on larger datasets.

#### Evaluation Methodology

We evaluated individual rule tuning steps. As a baseline, we use CBA run with
default parameters corresponding to those recommended in
Liu98integratingclassification  (with small deviations justified above).
Classification performance is measured by accuracy as in most recent studies
of ARC classifier performance, such as yang2017scalable ; angelino2017learning
; wang2018multi . All results are reported using ten-fold cross-validation
with macro averaging. All evaluations used exactly the same folds. The average
accuracy for all 22 datasets is reported as an indicative comparison measure
as well as a won-tie-loss matrix, which compares two classifiers by reporting
the number of datasets where the reference classifier wins, loses or the two
classifiers perform equally well. For a more reliable comparison, we include
p-values for the Wilcoxon signed-rank test computed on accuracies. This test
is preferred over Friedman’s test according to the authoritative work of
benavoli2016should .

We use three metrics to measure the size of the model: average antecedent
length (number of conditions in the rule), number of rules per model and
average number of conditions per model computed as _number of rules_ $\times$
_average antecedent length_. These are the most common measures in recent
related research: angelino2017learning ; lakkarajuinterpretable  used the
number of rules, and wang2018multi ; lakkarajuinterpretable  the total number
of conditions (or the average rule length).

We also include a benchmark indicating computational requirements of
individual proposed tuning steps. The build times reported in Table 4 were
computed as an average of classifier learning time for 220 models (10 folds
for each of the 22 datasets). In addition to the absolute run time, which can
be volatile across software and hardware platforms, we include the relative
execution time with the CBA baseline being assigned a score of 1.0. The CBA
baseline includes the discovery of candidate association rules, the data
coverage pruning and the default rule pruning. It should be noted that the
implementation of the tuning steps was not optimized for speed, therefore we
expect that substantial cuts in run time could be achieved if the
implementation is performance-optimized.

#### Overview of results

As a first step of the ablation study, we had to choose which ARC algorithm
will be used to generate base models that will be postprocessed. We chose CBA,
which is the most commonly used reference algorithm in related research, and
is still considered as a state-of-the-art lakkarajuinterpretable .

Table 4: Ablation study – aggregate results for 22 UCI datasets configuration | cba | #1 | #2 | #3 | #4 | #5 | #6 | #7
---|---|---|---|---|---|---|---|---
refit |  | Y | Y | Y | Y | Y | Y | Y
literal pruning |  | - | Y | Y | Y | Y | Y | Y
trimming |  | - | - | Y | Y | Y | Y | Y
extension |  | - | - | - | Y | Y | Y | Y
postpruning |  | - | - | - | - | Y | Y | Y
def. rule overlap - tran. |  | - | - | - | - | - | Y | -
def. rule overlap - range |  | - | - | - | - | - | - | Y
wins/ties/losses against CBA |  | 13-2-7 | 13-2-7 | 10-4-8 | 10-5-7 | 11-7-4 | 8-4-10 | 11-7-4
P-value (Wilcoxon) | na | 0.10 | 0.21 | 1 | 0.40 | 0.11 | 0.21 | 0.11
accuracy | 0.81 | 0.81 | 0.81 | 0.81 | 0.81 | 0.81 | 0.80 | 0.81
avg conditions/rule | 3.4 | 3.4 | 2.8 | 2.8 | 2.8 | 2.8 | 2.8 | 2.8
avg number of rules | 84.3 | 91.9 | 91.9 | 91.9 | 91.9 | 65.8 | 47.5 | 65.4
avg conditions / model | 284.5 | 310.6 | 259.5 | 259.5 | 259.5 | 183.9 | 131.7 | 182.7
build time [s] (median) | 12.3 | 0.3 | 0.5 | 0.6 | 22.9 | 23.2 | 24 | 24.1
avg build time normalized | 1 | 0.05 | 0.23 | 0.24 | 16.03 | 15.88 | 15.95 | 16.03

Table 4 demonstrates the effect of the individual tuning steps comprising our
postprocessing framework when applied on models learnt with CBA. Configuration
#1 corresponds to the refit tuning step being performed on top of CBA,
configuration #2 to refit tuning step and literal pruning, etc. Configuration
#6 and #7 correspond to all proposed tuning steps performed (#6 uses
transaction-based pruning and #7 default rule overlap pruning).

The QCBA setup that produces the highest accuracy while achieving maximum
reduction in the size of the classifier is configuration #7, which includes
all the tuning steps. This is very closely followed by #5, which excludes the
default overlap pruning. As follows from a comparison of #5 and #7, the range-
based pruning was ineffective (for CBA as a base learner) on this collection
of datasets.

#### Reduction in Model Size

The full QCBA model (#6) reduces the size of the model with the average of 133
conditions by 53% compared to the original CBA model (285 conditions) while
incurring 1% drop in the average accuracy resulting in a tie (11-0-11) in
terms of the won-tie-loss record on the 22 datasets (Table 4).

The QCBA configuration #5 has the same average accuracy as CBA and surpasses
CBA what concerns the won-tie-loss metric: it wins on 14 datasets while CBA
wins on 7 datasets and there is a draw on 1 dataset. The p-value of 0.12 is
close to the 10% level significance level, QCBA configurations #5 and #7 thus
marginally improve on CBA results.

#### Runtime

The results for runtime are reported in the last two rows of Table 4. It can
be seen that refit, literal pruning and trimming take together roughly as much
time on average as learning of a CBA model alone. The most computationally
intensive operation is the extension. If we look at the median build times, we
can observe that the postprocessing takes about twice as long as it takes to
build the input CBA model.

However, there are several datasets for which the extension step takes
excessive time to complete. This results in the run time of postprocessing
taking on average 16x the duration of CBA. The Extension algorithm is slowest
on data with many distinct values, which corresponds to segment, letter and
spambase datasets. The segment and letter datasets contain various image
metrics and spambase word frequency attributes. Such datasets are not typical
representatives of use cases, where interpretable machine learning models are
required. Nevertheless, the evaluation of the runtime indicates that the
computational optimization of the extension algorithm is one of the most
important areas for further work.

###  4.3 Postprocessing SBRL models

Scalable Bayesian Rule Lists yang2017scalable  is a recently proposed rule
learning algorithm. As most association rule learning approaches, the SBRL
algorithm can process only nominal attributes. In this experiment, we
postprocess models generated by SBRL with the proposed rule tuning steps.

Since SBRL is limited to datasets with binary class, we processed all eleven
datasets with binary class labels from Table 3. R Implementation sbrl (CRAN
version 1.2) from the SBRL authors was
used.999https://cran.r-project.org/web/packages/sbrl/ The postprocessed models
were generated using the QCBA package referenced earlier. For prediction,
rules were applied in the order output by QCBA.

#### Metaparameter Setup

SBRL was run with the following default parameter setting: iters=30000,
pos_sign=0, neg_sign=1, rule_minlen=1, rule_maxlen=1, eta=1.0,
minsupport_pos=0.10, minsupport_neg=0.10, lambda=10.0, , alpha={1,1},
nchain=10.

In this setting, which limits the antecedent length to 1, SBRL produces very
simple models with highly competitive accuracy. The second evaluated setting
for SBRL differed only by increased maximum rule length, which allowed the
algorithm to learn more expressive models. The rule_maxlen parameter was set
to 10 for all datasets, except those, where this setting resulted in an out of
memory error in the first rule generation phase within SBRL.101010For
hepatitis, the threshold was decreased to 5, for ionosphere and sonar datasets
to 3, and for spambase it had to be decreased to 2.

We evaluated the complete QCBA framework and the configuration with omitted
default rule overlap pruning (QCBA #5 and QCBA #6 from Table 4).

#### Results

Table 5 shows predictive performance and comprehensibility metrics for SBRL
only, SBRL model postprocessed with all the proposed tuning steps except
default rule overlap pruning (SBRL+QCBA#5), and SBRL model postprocessed with
all proposed tuning steps including transaction-based default rule overlap
pruning (SBRL+QCBA#6). The won/tie/loss record denotes the number of times the
postprocessed model had better/same/lower accuracy than the input SBRL model,
p-value was computed by Wilcoxon signed-rank test from paired accuracies. The
model size is computed as a product of average rule count and average rule
length. The build times for postprocessing does not include the time required
to build the input SBRL model. Normalized build time is reported relative to
the build time of SBRL only.

Table 5: Aggregate results for 11 benchmark datasets for two configurations of SBRL: rules of length 1, rules of length 10 (with several exceptions noted above).  | SBRL trained on short rules | SBRL trained on long rules
---|---|---
|  only SBRL |  SBRL+ QCBA#5 |  SBRL+ QCBA#6 |  only SBRL |  SBRL+ QCBA#5 |  SBRL+ QCBA#6
accuracy (macro average) |  0.8 |  0.81 |  0.79 |  0.81 |  0.81 |  0.80
won/tie/loss |  |  6-5-0 |  2-5-4 |  |  7-1-3 |  6-1-4
p-value |  na |  0.03 |  0.25 |  na |  0.75 |  0.72
avg number of rules |  4.8 |  3.7 |  3.4 |  3.3 |  3 |  2.7
avg conditions / rule |  0.8 |  0.7 |  0.6 |  1.5 |  1.2 |  1.2
avg conditions / model |  3.7 |  2.5 |  2.2 |  4.8 |  3.6 |  3.2
median build time [s] |  0.6 |  0.1 |  0.1 |  24.9 |  0.1 |  0.1
avg. build time norm. |  1 |  1.9 |  1.97 |  1 |  0.04 |  0.04

It follows from the ablation study done for CBA and reported in Table 4 that
the configuration QCBA#6 with all tuning steps enabled generated the smallest
models, while the configuration #5 with all tuning steps, but without default
rule overlap pruning, has the highest accuracy. Results reported in Table 5
for SBRL show the same pattern.

The configuration QCBA#6 resulted in a reduction in size by 35–40%, while the
configuration #5 resulted in a reduction of 25%-32%, but had higher gains in
predictive performance. According to the won/tie/loss record in Table 5, SBRL
models postprocessed by the proposed tuning steps have a higher accuracy on
most datasets compared to the SBRL-only models. The postprocessing is most
effective on models composed of short rules – there the improvement is
statistically significant ($p<0.05$).

Overall, the evaluation showed that postprocessing SBRL models with the
proposed tuning steps results in reduced model size and improved accuracy. The
computationally most intensive part is the generation of input rules performed
within SBRL. As Table 5 shows the additional computational cost of
postprocessing SBRL models is very low, even when the SBRL setup involves
learning of long input rules. The reason is that the models on SBRL output
consistently contain a small number of rules, which eases their subsequent
tuning.

###  4.4 Postprocessing IDS models

Similarly to SBRL and CBA, Interpretable Decision Sets (IDS)
lakkarajuinterpretable  is an association rule learning approach. In the first
step, candidate association rules are generated from frequent itemsets
returned by the Apriori algorithm. In the rule optimization step, a subset of
the generated rules is selected to form the final classifier. The rule
selection procedure is a subject of optimization using the Smooth Local Search
(SLS) algorithm feige2011maximizing , which guarantees a near-optimal solution
which will be at least 2/5 of the optimal solution. IDS uses a compound
objective function composed of several interpretability subobjectives (number
of rules, rule length, minimize rule overlap) and accuracy (maximize precision
and recall).

Table 6: Aggregate results for 22 benchmark datasets. The meaning of all columns is the same as for Table 5 |  only IDS |  IDS+ QCBA#5 |  IDS+ QCBA#6
---|---|---|---
accuracy (macro average) |  0.6 |  0.64 |  0.64
won/tie/loss |  |  17-3-2 |  17-3-2
p-value |  na |  0.00042 |  0.00036
avg number of rules |  14.2 |  7.1 |  5
avg conditions / rule |  2.2 |  1.6 |  1.4
avg conditions / model |  31.9 |  11.2 |  6.9
median build time [s] |  33.8 |  0.6 |  0.7
avg build time normalized |  1 |  0.03 |  0.03

#### Setup

For evaluation purposes, we used our reimplementation of the IDS algorithm
described in idsRULEML . While the IDS authors have made a reference
implementation available on GitHub, the evaluation reported in idsRULEML
shows that the reference implementation is too slow to be applied on the
benchmark datasets introduced in Table 3. While our implementation is faster,
there are still performance issues. For this reason, our work on adjusting the
IDS metaparameters centered primarily on making the IDS algorithm work on the
benchmark datasets by reducing the number of candidates. After some
experimentation, we determined the following procedure: generate frequent
itemsets as described in lakkarajuinterpretable  with minimum support
threshold of 1%, sort them according to criteria in Figure 3), and then use
the top 50 rules as the set of candidates. The $\lambda_{1}\ldots\lambda_{7}$
metaparameters that determine the weight of the individual partial objectives
were set to the same value (1.0).

For prediction on IDS models, rules were sorted by a harmonic mean of support
and confidence as specified in lakkarajuinterpretable , and applied in this
order – an instance was classified by the first firing rule. The rule order
for prediction on models postprocessed by QCBA was determined by the order
output by QCBA (criteria in Figure 3).

#### Results

Results reported in Table 6 indicate that the proposed tuning steps
consistently reduce the size of models generated by IDS, while also improving
predictive performance on the majority of datasets. On average, there was 4%
improvement in the accuracy and the model size was reduced by 78% (for QCBA#6
involving default rule overlap pruning). The Wilcoxon signed-rank test shows a
statistically significant improvement over IDS at $p<0.001$. The time required
for postprocessing is negligible in comparison with the time needed to learn
the IDS models.

###  4.5 Comparison with Related Symbolic Classifiers

In this section, we will compare of the proposed method against predictive
performance of several state-of-the-art reference algorithms. Since QCBA is a
postprocessing framework, we had to choose the base algorithm producing the
models, which will be postprocessed. We selected CBA since it is probably the
most commonly used ARC algorithm. We included all proposed tuning steps,
choosing the transaction-based version of the default rule overlap
pruning.111111This corresponds to configuration QCBA#5 from Table 4.

#### Selection of reference algorithms

C4.5 DBLP:books/mk/Quinlan93  and RIPPER Cohen:1995:FER:3091622.3091637  are
well-established interpretable classifiers that are widely used as standard
reference algorithms. FURIA algorithm huhn2009furia , also covered in our
related work section, is a state-of-the-art association rule classifier, which
outputs fuzzy rules. PART frank1998generating  is a rule learning algorithm
designed to address some of the shortcomings of C4.5 and RIPPER.

We also include a comparison against the three association rule classifiers
(CBA, IDS, and SBRL) used as baselines in the previous three subsections.

#### Implementations

For standard learners (C4.5, FURIA, PART, RIPPER), we used the implementations
available in the Weka framework.121212Instead of C4.5 we used the very similar
J48 decision tree learner available in Weka
(http://www.cs.waikato.ac.nz/ml/weka/). For CBA, SBRL, IDS, and QCBA we use
the implementations referenced from the previous sections.

#### Metaparameter Tuning

For C4.5, FURIA, PART, and RIPPER we performed hyperparameter optimization
using the MultiSearch package131313https://github.com/fracpete/multisearch-
weka-package, which implements a variation of grid search over multi-parameter
spaces. As evaluation metric we chose accuracy. Parameter tuning was performed
separately for each fold on the training data. The grid for individual
learners is defined in Table 7.

The metaparameters for CBA, IDS and SBRL were set as described above (cf.
Section 4.2 for CBA, Section 4.3 for SBRL, and Section 4.4 for IDS).

Table 7: Grid definition for hyperparameter optimization parameter | value range | step
---|---|---
J48
confidenceFactor | [0.05,0.4] | 0.05
minNumObj | [2,14] | 4
numFolds | [2,4] | 1
reducedErrorPruning | boolean |
subtreeRaising | boolean |
binarySplits | boolean |
FURIA
minNo | [0,1] | 0.25
folds | [2,4] | 1
PART
confidenceFactor | [0.05,0.4] | 0.05
minNumObj | [2,14] | 4
numFolds | [2,4] | 1
useMDLcorrection | boolean |
reducedErrorPruning | boolean |
unpruned | boolean |
binarySplits | boolean |
RIPPER
numFolds | [2,4] | 1
checkErrorRate | boolean |
usePruning | boolean |
Table 8: Counts of wins, losses and ties for QCBA (#5), and p-value for the Wilcoxon signed-rank test. For evaluation with PART, the letter dataset was skipped since the learner was not able to process the given dataset (omitted=1). For SBRL, all datasets with non-binary class labels were omitted.  dataset | QCBA won | tie | loss | omitted | p-value
---|---|---|---|---|---
Other association rule classifiers
CBA | 16 | 2 | 4 | 0 | 0.00450
SBRL | 9 | 0 | 2 | 11 | 0.0208
IDS | 21 | 0 | 1 | 0 | 0.00005
Related symbolic classifiers
J48 auto | 12 | 1 | 9 | 0 | 0.46510
PART auto | 8 | 5 | 8 | 1 | 0.71514
RIPPER auto | 12 | 4 | 6 | 0 | 0.15787
FURIA auto | 5 | 4 | 12 | 0 | 0.13963

#### Results

A won-tie-loss matrix for accuracy is in Table 8. QCBA performs significantly
better than any of the three association rule classification algorithms
generating crisp rules at $\alpha=0.05$ (before Bonfennori correction). In
line with recommendations in benavoli2016should , we perform Bonfennori
correction to control for type I error associated with multiple hypotheses
testing. In this case, the critical value (alpha) for an individual test is
obtained by dividing the family-wise error rate (which we set at
$\alpha=0.05$) by the number of tests (7), resulting in $\alpha=0.007$ after
Bonferroni correction. At this level, QCBA performs significantly better than
IDS and CBA. While QCBA loses only on two datasets against SBRL, due to the
smaller number of datasets used for SBRL evaluation (only binary class label
allowed) the better performance of QCBA is not statistically significant. What
can be noticed is that SBRL produces models of slightly smaller accuracy as
compared to the much older CBA algorithm. This observation is consistent with
another recent benchmark between SBRL and CBA wang2018multi . On the other
hand, SBRL models are also much smaller than CBA models, as follows from Table
4 and Table 5.

The comparison against other (non-ARC) classification algorithms showed that
CBA postprocessed by the proposed tuning steps (denoted as QCBA in the table)
does not perform statistically significantly better or worse, but is highly
competitive. QCBA won on more datasets than C4.5 (J48), and RIPPER, and had
the same number of wins and losses as PART. The PART algorithm (with
metaparameter tuning) was, however, unable to process one of the datasets. The
only algorithm that – in a pairwise comparison – performs better than QCBA is
FURIA, which is a rule classifier extending on RIPPER, but generating fuzzy
rule models. A detailed discussion of the similarities and differences between
the proposed approach and FURIA is presented in the following section.

##  5 Related Work

Separate-and-conquer strategy is possibly the most common approach to rule
learning. This strategy finds rules that explain part of training instances,
separates these instances, and iteratively uses the remaining examples to find
additional rules until no instances remain furnkranz1999separate . Separate-
and-conquer provides a basis, for example, for the seminal RIPPER algorithm
Cohen95fasteffective , or its fuzzy rule extension with FURIA huhn2009furia .
Numeric attributes are supported by both RIPPER and FURIA through selectors
($\neq,\leq,\geq$) and range operators (intervals). Association rule
classification is a principally different approach in which a large number of
rules is first generated with fast association rule learning algorithms, and a
subset of these rules is then selected to form the final classifier. To our
knowledge, all previously proposed association rule classification algorithms
support only categorical inputs. However, there has been work on learning
standard association rules (as a nugget discovery rather than classification
task) from numerical data. Also, quantitative information is processed in
fuzzy association rule classification approaches. In the following, we discuss
the differences between the new approach to supporting quantitative attributes
presented in this paper, which is based on postprocessing of already learnt
ARC models, and existing approaches for quantitative association rule learning
and fuzzy rule classification.

###  5.1 Quantitative Association Rule Mining

Several quantitative association rule learning141414Note that there is a
difference between (quantitative) association rule mining, which is
exploratory data mining task aimed at discovering interesting patterns in
data, and (quantitative) association rule classification, which aims at
building understandable classification (predictive) models. algorithms have
been proposed (cf. adhikary2015trends  for a recent review). Two
representative and widely referenced approaches include the QuantMiner
salleb2007quantminer  and NAR-Discovery song2013discovering . The earlier
proposed QuantMiner is an evolutionary algorithm, which optimizes a multi-
objective fitness function that combines support and confidence. The essence
of QuantMiner is that mutiple seed rules are evolved using standard
evolutionary operators, where e.g. mutation corresponds to an increase or
decrease of lower/upper bound of a rule. NAR-Discovery takes a different, two
stage approach. Similarly to QCBA, a set of “coarse” association rules is
generated on prediscretized data, with standard association rule generation
algorithms in the first stage. In the second stage, for each coarse-grained
rule, several refined-rules are generated using fine bins. The granularity of
the bins is a parameter of the algorithm. One feature of NAR-Discovery is that
it produces at least one order of magnitude more rules than QuantMiner.

Table 9: Comparison with Quantitative Association Rule Generation Approaches property |  QCBA |  NAR-D |  QuantMiner
---|---|---|---
classification models |  y |  n |  n
deterministic |  y |  y |  n
number of rules |  +++ |  + |  ++
precision of intervals |  +++ |  + |  ++
externally set parameters |  +++ |  ++ |  +

Table 9 compares our QCBA framework with NAR-Discovery and QuantMiner.
Justifications for individual values in the table:  1. classification models:
neither QuantMiner or NAR-Discovery were designed for classification,  2.
deterministic: QuantMiner is an evolutionary algorithm,  3. number of rules:
too many rules generated is one of the biggest issues facing association rule
generation algorithms, neither NAR-Discovery nor QuantMiner contain procedures
for limiting the number of rules, QCBA contains several rule pruning
algorithms,  4. precision of intervals: for QuantMiner the precision of the
intervals depends on the setting of the evolutionary process and for NAR-
Discovery on the discretization setting, QCBA generates interval boundaries
exactly corresponding to values in the input continuous data.  5. externally
set parameters151515In addition to confidence and support thresholds.: NAR-
Discovery requires two granularity settings, (fine/coarse), and QuantMiner
requires multiple parameters such as population size, mutation and crossover
rate for the evolutionary process, which have large effect on the result of
processing. QCBA does not require any externally set parameters, but several
optional parameters that can speed up the algorithm in exchange for a lower
accuracy of the generated models.

Finally, it should be noted that the comparison described above is not
completely fair to the quantitative association rule learning algorithms since
they address different task than QCBA. Unlike QCBA these are unsupervised
algorithms that do not have the class information available. This is exploited
by QCBA, among others, to perform rule pruning, which allows to reduce the
number of rules in an informed way.

###  5.2 Fuzzy Approaches

There are several ARC approaches that adopt fuzzy logic to deal with numerical
attributes. A notable representative of this class of algorithms is FARC-HD,
and its evolved version FARC-HD-OVO farchd2 . In the following, we will focus
on the FURIA algorithm huhn2009furia , which is not an ARC algorithm, but is
conceptually closer to our approach and is frequently referenced as the state-
of-the-art in terms of the accuracy a rule learning algorithm can achieve
palacios2016extension ; barsacchi2017multi . Also, in our benchmark, FURIA
obtained the best results.

FURIA postprocesses rules generated by the RIPPER algorithm for induction of
crisp rules. RIPPER produces ordered rule lists, the first matching rule in
the list is used for classification. A default rule is added to the end of the
list by RIPPER ensuring that a query object is always covered. As is typical
for fuzzy approaches, FURIA outputs an unordered rule set, where multiple
rules need to be combined to obtain the classification.

A by-product of the transition to the rule set performed by FURIA is the
removal of the default rule. In order to ensure coverage of each object, FURIA
implements _rule stretching_ , which is storing multiple generalizations (i.e.
with one or more literals in the antecedent omitted) of each rule, and using
these for classification.

The most important element in FURIA is the fuzzification of input rules: The
original intervals on quantitative attributes in rules produced by RIPPER are
used as upper and lower bound of the core $[\phi_{i}^{c,L}$,$\phi_{i}^{c,U}]$,
and FURIA determines the optimal upper and lower bounds of the fuzzy
supports161616Note that in fuzzy set theory, support bound denotes an “upper”
rule boundary, while in the scope of association rule learning it denotes
number or ratio of correctly classified objects.:
$[\phi_{i}^{s,L}$,$\phi_{i}^{s,U}]$. When searching for $\phi_{i}^{s,L}$ and
$\phi_{i}^{s,U}$, FURIA proceeds greedily: it evaluates fuzzifications for all
antecedents and fuzzifies the one which produces the best purity. As
fuzzification progresses training objects are gradually removed, therefore the
order in which the rules are fuzzified is important.

To compare FURIA with QCBA, both algorithms postprocess input rules, adjusting
boundaries of numerical attributes. Within the algorithms, there are numerous
differences. In QCBA we retain the default rule (although it may be updated),
therefore even if no other rule matches, a model postprocessed with QCBA is
able to provide a classification. Somewhat similar procedure to fuzzification
in FURIA is the QCBA extension. Unlike in FURIA, rules are extended
independently of one another, which eases parallelization. In summary, FURIA
produces fuzzy rules, and the resulting models are rule sets, and QCBA
produces rule lists composed of crisp rules.

While fuzzy rule models can achieve better accuracy than crisp rule models
huhn2009furia ; farchd2 , this comes at a cost of possibly higher run time and
impeded explainability. In a follow-up work hullermeier2017knowledge , the
authors critically reflect on fuzzy-rule learning systems, asserting that a)
standard fuzzy rule systems are not scalable, and b) that they lose
interpretability and cognitive plausibility when they are automatically learnt
from data.

As for scalability, postprocessing of RIPPER models with FURIA results in an
increase of runtime by a factor between 1.5 and 7.7 (as opposed to RIPPER
only) hullermeier2017knowledge . The benchmarks that we performed for QCBA
show a median increase against CBA by a factor of 2 (Table 4) and an average
increase by a factor of 16. The time added by postprocessing of models with
QCBA is therefore comparable to time taken to postprocess models by FURIA.
What can make a substantial difference is the processing time of the
underlying learner – RIPPER in case of FURIA and CBA, SBRL or IDS in case of
QCBA. To this end, association rule learning, which is a crucial
computationally intensive step in association rule classification algorithms,
is widely considered as a highly scalable approach for large and sparse data
(cf. e.g. hastie01statisticallearning ). This is confirmed in a benchmark
reported in DBLP:conf/clef/KliegrK15  comparing the performance of RIPPER and
CBA on a large dataset with a high number of distinct values, which showed
that unlike CBA, RIPPER was unable to process the complete dataset. The
results for another state-of-the-art algorithm, FARC-HD, have shown that this
fuzzy rule learning approach is much slower than crisp rule learning
approaches. Referring to Table 1, FARC-HD was on average more than 100x slower
than CBA farchd2 . The remaining two other fuzzy associative classifiers
(LAFAR hu2003finding  and CFAR chen2008building ) included into the benchmark
in farchd2  are reported to have even more severe scalability problems as they
could not be run on all datasets in the benchmark.

As for explainability (interpretability), we were unable to find a study that
would evaluate interpretability of automatically learnt fuzzy rule
classifiers. However, in principle, fuzzy rule algorithms generate rule sets
as multiple rules are combined using membership functions to classify one
instance, while models generated by QCBA are intended to be used as rule lists
with only the highest-ranked rule being used to classify an instance. Rule
lists and rule sets have a clearly different properties in terms of
interpretability, and future research will show for what purposes each
representation is most suitable for.

##  6 Conclusion

This research aimed at ameliorating one of the major drawbacks of association
rule classification: the adherence of the rules comprising the classifier to
the multidimensional grid created by discretization of numerical attributes.
Quantitative Classification based on Associations (QCBA) is, to the author’s
knowledge, the first non-fuzzy association rule classification approach that
recovers part of the information lost in prediscretization. Note that QCBA is
not a standalone learning algorithm, but rather a collection of postprocessing
steps applied after rule lists were learnt with an arbitrary rule learning
algorithm.

Our initial expectation was that the application of QCBA will result mainly in
improvements of classification accuracy. While we saw such improvements on
most datasets, the evaluation somewhat surprisingly showed that the proposed
tuning steps also lead to smaller model size. QCBA consistently reduced the
number of rules and their length for all three ARC algorithms, whose models
were postprocessed in our benchmark. These reductions are substantial: about
50% less total number of conditions for CBA, 35% for SBRL and even 78% for
IDS.

An interesting area of future work would be combining QCBA with a wider range
of base rule learning algorithms. Also, real-world datasets contain typically
both numerical and categorical attributes, while the presented work addresses
only quantitative attributes. There is a complementary line of research on
merging the categorical attributes by creating multi-value rule sets
wang2018multi , with very promising results in terms of gains in accuracy and
comprehensibility. Since QCBA has a modular architecture, some of its tuning
steps can become building blocks in a combined approach that would generate
small, yet accurate models on data containing mixed attribute types.

## Acknowledgments

I would like to thank Jiří Filip for feedback on the pseudo-code listings
included in Appendix A, and also for implementing an alternative QCBA
implementation, which is available in the pyARC Python package for association
rule classification.

## References

  * (1) Adhikary, D., Roy, S.: Trends in quantitative association rule mining techniques.  In: Recent Trends in Information Systems (ReTIS), 2015 IEEE 2nd International Conference on, pp. 126–131. IEEE (2015)
  * (2) Agrawal, R., Gehrke, J., Gunopulos, D., Raghavan, P.: Automatic subspace clustering of high dimensional data for data mining applications, vol. 27.  ACM (1998)
  * (3) Agrawal, R., Imielinski, T., Swami, A.N.: Mining association rules between sets of items in large databases.  In: SIGMOD, pp. 207–216. ACM Press (1993)
  * (4) Alcala-Fdez, J., Alcala, R., Herrera, F.: A fuzzy association rule-based classification model for high-dimensional problems with genetic rule selection and lateral tuning.  IEEE Transactions on Fuzzy Systems 19(5), 857–872 (2011)
  * (5) Angelino, E., Larus-Stone, N., Alabi, D., Seltzer, M., Rudin, C.: Learning certifiably optimal rule lists for categorical data.  The Journal of Machine Learning Research 18(1), 8753–8830 (2017)
  * (6) Barsacchi, M., Bechini, A., Marcelloni, F.: Multi-class boosting with fuzzy decision trees.  In: Fuzzy Systems (FUZZ-IEEE), 2017 IEEE International Conference on, pp. 1–6. IEEE (2017)
  * (7) Benavoli, A., Corani, G., Mangili, F.: Should we really use post-hoc tests based on mean-ranks?  The Journal of Machine Learning Research 17(1), 152–161 (2016)
  * (8) Chen, Z., Chen, G.: Building an associative classifier based on fuzzy association rules.  International Journal of Computational Intelligence Systems 1(3), 262–273 (2008)
  * (9) Cohen, W.W.: Fast effective rule induction.  In: Proceedings of the Twelfth International Conference on International Conference on Machine Learning, ICML’95, pp. 115–123. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (1995).  URL http://dl.acm.org/citation.cfm?id=3091622.3091637
  * (10) Cohen, W.W.: Fast effective rule induction.  In: Proceedings of the Twelfth International Conference on Machine Learning, pp. 115–123. Morgan Kaufmann (1995)
  * (11) Elkano, M., Galar, M., Sanz, J.A., Fernández, A., Barrenechea, E., Herrera, F., Bustince, H.: Enhancing multiclass classification in farc-hd fuzzy classifier: On the synergy between $n$-dimensional overlap functions and decomposition strategies.  IEEE Transactions on Fuzzy Systems 23(5), 1562–1580 (2015).  DOI 10.1109/TFUZZ.2014.2370677
  * (12) Fayyad, U.M., Irani, K.B.: Multi-Interval Discretization of Continuous-Valued Attributes for Classification Learning.  In: 13th International Joint Conference on Uncertainly in Artificial Intelligence (IJCAI93), pp. 1022–1029 (1993)
  * (13) Feige, U., Mirrokni, V.S., Vondrák, J.: Maximizing non-monotone submodular functions.  SIAM Journal on Computing 40(4), 1133–1153 (2011)
  * (14) Filip, J., Kliegr, T.: Pyids–python implementation of interpretable decision sets algorithm by lakkaraju et al, 2016.  In: RuleML Challenge, RuleML+RR 2019. CEUR-WS (2019)
  * (15) Frank, E., Witten, I.H.: Generating accurate rule sets without global optimization (1998).  University of Waikato, Department of Computer Science
  * (16) Friedman, J., Hastie, T., Tibshirani, R.: The elements of statistical learning: Data mining, inference, and prediction.  Springer Series in Statistics (2009)
  * (17) Fürnkranz, J.: Separate-and-conquer rule learning.  Artificial Intelligence Review 13(1), 3–54 (1999)
  * (18) González, A., Pérez, R.: Selection of relevant features in a fuzzy genetic learning algorithm.  IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 31(3), 417–425 (2001)
  * (19) Han, J., Cheng, H., Xin, D., Yan, X.: Frequent pattern mining: current status and future directions.  Data mining and knowledge discovery 15(1), 55–86 (2007)
  * (20) Han, J., Pei, J., Yin, Y., Mao, R.: Mining frequent patterns without candidate generation: A frequent-pattern tree approach.  Data Mining and Knowledge Discovery 8(1), 53–87 (2004)
  * (21) Hastie, T., Tibshirani, R., Friedman, J.: The Elements of Statistical Learning.  Springer Series in Statistics. Springer New York Inc., New York, NY, USA (2001)
  * (22) Hu, Y.C., Chen, R.S., Tzeng, G.H.: Finding fuzzy classification rules using data mining techniques.  Pattern Recognition Letters 24(1-3), 509–519 (2003)
  * (23) Hühn, J., Hüllermeier, E.: Furia: an algorithm for unordered fuzzy rule induction.  Data Mining and Knowledge Discovery 19(3), 293–319 (2009)
  * (24) Hüllermeier, E.: From knowledge-based to data-driven modeling of fuzzy rule-based systems: A critical reflection.  arXiv preprint arXiv:1712.00646 (2017)
  * (25) Ishibuchi, H., Yamamoto, T., Nakashima, T.: Hybridization of fuzzy GBML approaches for pattern classification problems.  IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 35(2), 359–365 (2005)
  * (26) Jirı, F., Kliegr, T.: Classification based on associations (cba)-a performance analysis
  * (27) Kliegr, T.: Effect of cognitive biases on human understanding of rule-based machine learning models.  Ph.D. thesis, Queen Mary University of London (2017)
  * (28) Kliegr, T.: Quantitative cba: Small and comprehensible association rule classification models.  arXiv preprint arXiv:1711.10166 (2017)
  * (29) Kliegr, T., Kuchař, J., Sottara, D., Vojíř, S.: Learning business rules with association rule classifiers.  In: A. Bikakis, P. Fodor, D. Roman (eds.) Rules on the Web. From Theory to Applications: 8th International Symposium, RuleML 2014, Co-located with the 21st European Conference on Artificial Intelligence, ECAI 2014, Prague, Czech Republic, August 18-20, 2014. Proceedings, pp. 236–250. Springer International Publishing, Cham (2014)
  * (30) Kliegr, T., Kuchař, J.: Benchmark of rule-based classifiers in the news recommendation task.  In: J. Mothe, J. Savoy, J. Kamps, K. Pinel-Sauvagnat, G.J.F. Jones, E. SanJuan, L. Cappellato, N. Ferro (eds.) Experimental IR Meets Multilinguality, Multimodality, and Interaction - 6th International Conference of the CLEF Association, CLEF 2015, Toulouse, France, September 8-11, 2015, Proceedings, _Lecture Notes in Computer Science_ , vol. 9283, pp. 130–141. Springer (2015)
  * (31) Lakkaraju, H., Bach, S.H., Leskovec, J.: Interpretable decision sets: A joint framework for description and prediction.  In: Proceedings of the 22Nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’16, pp. 1675–1684. ACM, New York, NY, USA (2016)
  * (32) Li, W., Han, J., Pei, J.: CMAR: Accurate and efficient classification based on multiple class-association rules.  In: Data Mining, 2001. ICDM 2001, Proceedings IEEE International Conference on, pp. 369–376. IEEE (2001)
  * (33) Liu, B., Hsu, W., Ma, Y.: Integrating classification and association rule mining.  In: Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining, KDD’98, pp. 80–86. AAAI Press (1998)
  * (34) Liu, B., Ma, Y., Wong, C.K.: Classification using association rules: weaknesses and enhancements.  Data mining for scientific applications 591 (2001)
  * (35) Mansoori, E.G., Zolghadri, M.J., Katebi, S.D.: Sgerd: A steady-state genetic algorithm for extracting fuzzy classification rules from data.  IEEE Transactions on Fuzzy Systems 16(4), 1061–1071 (2008)
  * (36) Palacios, A., Sánchez, L., Couso, I., Destercke, S.: An extension of the furia classification algorithm to low quality data through fuzzy rankings and its application to the early diagnosis of dyslexia.  Neurocomputing 176, 60–71 (2016)
  * (37) Quinlan, J.R.: C4.5: Programs for Machine Learning.  Morgan Kaufmann (1993)
  * (38) Quinlan, J.R.: Improved use of continuous attributes in C4. 5.  Journal of artificial intelligence research 4, 77–90 (1996)
  * (39) Salleb-Aouissi, A., Vrain, C., Nortet, C.: Quantminer: A genetic algorithm for mining quantitative association rules.  In: IJCAI, vol. 7 (2007)
  * (40) Song, C., Ge, T.: Discovering and managing quantitative association rules.  In: Proceedings of the 22nd ACM international conference on Conference on information & knowledge management, pp. 2429–2434. ACM (2013)
  * (41) Thabtah, F.: Pruning techniques in associative classification: Survey and comparison.  Journal of Digital Information Management 4(3) (2006)
  * (42) Vanhoof, K., Depaire, B.: Structure of association rule classifiers: a review.  In: 2010 International Conference on Intelligent Systems and Knowledge Engineering (ISKE), pp. 9–12 (2010)
  * (43) Wang, T.: Multi-value rule sets for interpretable classification with feature-efficient representations.  In: Advances in Neural Information Processing Systems, pp. 10,835–10,845 (2018)
  * (44) Wang, T., Rudin, C., Doshi-Velez, F., Liu, Y., Klampfl, E., MacNeille, P.: A bayesian framework for learning rule sets for interpretable classification.  The Journal of Machine Learning Research 18(1), 2357–2393 (2017)
  * (45) Yang, H., Rudin, C., Seltzer, M.: Scalable bayesian rule lists.  In: Proceedings of the 34th International Conference on Machine Learning-Volume 70, pp. 3921–3930. JMLR. org (2017)
  * (46) Yin, X., Han, J.: CPAR: Classification based on predictive association rules.  In: Proceedings of the SIAM International Conference on Data Mining, pp. 369–376. SIAM Press, San Franciso (2003)
  * (47) Zaki, M.J.: Scalable algorithms for association mining.  IEEE Transactions on Knowledge and Data Engineering 12(3), 372–390 (2000)

##  Appendix A Algorithm Listings

Algorithm 2 Refit rule _refit()_

1:$r$ – input rule learnt on discretized training data

2:rule $r$ with refit literals

3:

4:for $literal=(A,V)\in antecedent(r)$ do

5: $\mathcal{A}\leftarrow$ all unique values appearing in training data in
attribute A.

6:  _left_ $\leftarrow min(\mathcal{A}\cap V)$; _right_ $\leftarrow
max(\mathcal{A}\cap V)$

7: $r$ $\leftarrow$ replace $literal$ in $r$ with new _literal =
(A,[left,right])_

8:end for

9:return $r$

Algorithm 3 Literal pruning _pruneLiterals()_

1:$r$ – input rule

2:rule $r$ with redundant attributes (literals) removed

3:

4:_attrRemoved_ $\leftarrow$ _FALSE_

5:repeat

6: for $literal\in antecedent(r)$ do {Literals are iterated in arbitrary
order}

7: $r^{\prime}\leftarrow$ remove $literal$ from $r$

8: if  _confidence(_ $r^{\prime}$_)_ $\geq$ _confidence(r)_ then

9: $r\leftarrow r^{\prime}$; _attrRemoved_ $\leftarrow$ _TRUE_

10: break

11: else

12:  _attrRemoved_ $\leftarrow$ _FALSE_

13: end if

14: end for

15:until  _attrRemoved_ = _FALSE_ or _antecedent(r)_ is empty

16:return $r$

Algorithm 4 Rule trimming _trim()_

1:$r$ – input rule

2:rule $r$ with trimmed literals

3:

4:$corrCovByR$ $\leftarrow$ training instances covered and correctly
classified by $r$

5:for $literal=(A,V)\in antecedent(r)$ do {Literals are iterated in arbitrary
order}

6:  _corrCovByL_ $\leftarrow$ training instances covered by $literal$

7:  _distValsL_ $\leftarrow$ distinct values training instances have in
attribute $A$

8: if $size(distValsL)\leq 1$ then {Intervals restricted to single value are
not permitted}

9: continue

10: end if

11: $distValsLinR\leftarrow$ distinct values of attribute $A$ in $corrCovByR$

12: $V^{\prime}\leftarrow[min(distValsLinR),max(distValsLinR)]$

13: $r\leftarrow$ replace $literal$ in $r$ with new $literal=(A,V^{\prime})$

14:end for

15:return $r$

Algorithm 5 Get Extensions _getExtensions()_

1:_train_ = $\\{x_{l}|l=1,\ldots,n\\}$ – $n$ train objects, $m$ attributes:
$\\{A_{i}|i=1,\ldots,m\\}$, rule $r$

2:up to two extensions of rule $r$

3:

4:$extendedRules$ $\leftarrow\emptyset$

5:for $literal\in body(r)$ do

6: if type($literal$)=nominal then {Nominal attributes are skipped}

7: continue

8: end if

9: $neighbourhood$ $\leftarrow$ direct extension of $literal$ in _train_ {See
Def. 1}

10: for $extendedLiteral\in neighbourhood$ do

11: $extRule\leftarrow$ replace $literal$ in $r$ with $extendedLiteral$

12: $extendedRules\leftarrow extendedRules\cup extRule$

13: end for

14:end for

15:return  _$extendedRules$_

Algorithm 6 Rule Extension _extendRule()_

1:_train_ = $\\{x_{l}|l=1,\ldots,n\\}$ – $n$ train objects, defined over $m$
attributes: $\\{A_{i}|i=1,\ldots,m\\}$, $r$ – input rule, _minImprovement_
$\in(-1,1)$ with 0 as default, _minCondImprovement_ $\in(-1,0)$ with -1 as
default

2:extended rule $r$

3:

4:_curBest_ $\leftarrow r$

5:repeat

6: directExtensions $\leftarrow$ $getExtensions$($curBest$,$train$)

7: $extensionSuccessful\leftarrow$ false

8: for $cand\in directExtensions$ {Iteration in order according to criteria in
Figure 3} do

9: $\Delta_{conf}\leftarrow$ conf($cand$) - conf($curBest$),
$\Delta_{supp}\leftarrow$ sup($cand$) - sup($curBest$)

10: if  _crispAccept( $\Delta_{conf},\Delta_{supp},minImprovement$)_ then

11: $curBest\leftarrow cand$, $extensionSuccessful\leftarrow$ true

12: break

13: else if conditionalAccept($\Delta_{conf},minCondImprovement)$ then

14: $enlgmnt\leftarrow cand$

15: loop

16: $enlgmnt$ $\leftarrow$ $getBeamExtension$($enlgmnt$)

17: if $enlgmnt$=$\emptyset$ then

18: break

19: end if

20: $\Delta_{conf}\leftarrow$ conf($enlgmnt$) - conf($curBest$),
$\Delta_{supp}\leftarrow$ sup($enlgmnt$) - sup($curBest$)

21: if crispAccept($\Delta_{conf},\Delta_{supp},minImprovement$) then

22: $curBest\leftarrow enlgmnt$, _extensionSuccessful_ $\leftarrow$ true

23: break

24: else if conditionalAccept($\Delta_{conf},minCondImprovement)$ then

25: continue {Extension in conditional accept band}

26: else

27: break

28: end if

29: end loop

30: if  _extensionSuccessful_ = true then

31: break

32: end if

33: else

34: continue {Improvement below conditional threshold, going to next
candidate}

35: end if

36: end for

37:until  _extensionSuccessful_ = false

38:return $curBest$

Algorithm 7 Postpruning _postPruning()_

1:rules – output of _extendRuleList()_ , set of training instances $T$

2:pruned $rules$ (some elements of input rule list removed, default rule
added)

3:

4:_cutoffRule_ $\leftarrow\emptyset$; _cutoffClass_ ,_defClass_ $\leftarrow$
most frequent class in $T$; _lowestTotalError_ $\leftarrow|T|-|t\in
T:class(t)=\mbox{\emph{cutoffClass}}|$; _totalErrorsWithoutDefault_
$\leftarrow 0$

5:rules $\leftarrow$ sort rules according to criteria in Fig. 3

6:for all  _r_ $\in$ _rules_ do {Data coverage pruning}

7:  _covered_ $\leftarrow$ instances in _T_ matched by _antecedent(r)_

8:  _corrCovered_ $\leftarrow$ instances in _T_ matched by _antecedent(r)_ and
_consequent(r)_

9: $T:=T\setminus covered$ {Remove instances covered by $r$ from training
data}

10: if  _corrCovered_ =$\emptyset$ then

11: $rules$ $\leftarrow rules\setminus r$ {remove _r_ from _rules_}

12: else

13:  _misclassified_ $\leftarrow$ _covered_ \- _corrCovered_ ; _defClass_
$\leftarrow$ most frequent class in $T$

14:  _totalErrorsWithoutDefault_ $\leftarrow$ _totalErrorsWithoutDefault_
+_misclassified_

15:  _defaultRuleError_ $\leftarrow|T|-|t\in
T:class(t)=\mbox{\emph{defClass}}|$

16:  _totalErrorWithDefault_ $\leftarrow$ _defaultRuleError_ \+
_totalErrorsWithoutDefault_

17: if  _totalErrorWithDefault_ $<$_lowestTotalError_ then

18:  _cutoffRule, lowestTotalError, cutoffClass_ $\leftarrow
r,totalErrorWithDefault,defClass$

19: end if

20: end if

21:end for

22:{Default rule pruning}

23:$rules$ $\leftarrow$ remove all rules below _cutoffRule_ from $rules$

24:$rules$ $\leftarrow$ append new default rule “{} $\rightarrow$
_cutoffClass_ ’ at the end of $rules$

25:add default rule “{} $\rightarrow$ _defClass_ ” at the end of $rules$.

26:return _rules_

Algorithm 8 Default Rule Overlap Pruning (Transaction-based) _drop-tr()_

$rules$, set of training instances $T$

pruned $rules$ (some elements of $rules$ removed)

_defRule_ $\leftarrow$ default (last) rule in $rules$

for all  _prunCand_ $\in$ _rules_ do

if  _consequent(prunCand)_ $\neq$ _class(defRule)_ or _prunCand = defRule_
then

continue

end if

 _corrCovered_ $\leftarrow$ instances in _T_ correctly classified by
_prunCand_

 _nonEmptyIntersection_ $\leftarrow$ FALSE

for all  _candClash_ $\in$ rules below _prunCand_ in _rules_ do

if  _consequent(candClash)_ $=$ _class(defRule)_ then

continue

end if

$candClashCovered$ $\leftarrow$ instances in _T_ matching
_antecedent(candClash)_

if $candClashCovered\cap corrCovered\neq\emptyset$ then

$nonEmptyIntersection$ $\leftarrow$ TRUE

break

end if

end for

if $nonEmptyIntersection$ = FALSE then

$rules$ $\leftarrow$ $rules\setminus prunCand$

end if

end for

return _rules_

Algorithm 9 Default Rule Overlap Pruning (Range-based) _drop-ra()_

$rules$, set of training instances $T$

pruned $rules$ (some elements of $rules$ removed)

_defRule_ $\leftarrow$ default (last) rule in $rules$

for all  _prunCand_ $\in$ _rules_ do

if  _consequent(prunCand)_ $\neq$ _class(defRule)_ or _prunCand = defRule_
then

continue

end if

 _literals_ $\leftarrow$ literals in $antecedent(prunCand)$

 _attributes_ $\leftarrow$ attributes appearing in $antecedent(prunCand)$

$clashingRuleFound$ $\leftarrow$ FALSE

for all  _candClash_ $\in$ rules below _prunCand_ in _rules_ do

if  _consequent(candClash)_ $=$ _class(defRule)_ then

continue

end if

 _sharedAttributes_ $\leftarrow$ $attributes\cap$ attributes in
$antecedent(candClash)$

if $sharedAttributes=\emptyset$ then

$clashingRuleFound$ $\leftarrow$ TRUE

break

end if

 _literalsInClashOnSharedAtt_ $\leftarrow$ literals in $antecedent(candClash)$
defined over attributes in _sharedAttributes_

$attLeastOneAttDisjunct\leftarrow$ FALSE

for all $literalCC=(A,V)\in literalsInClashOnSharedAtt$ do

$literal\leftarrow$ get literal in $antecedent(prunCand)$, which is defined
over attribute $A$

if $V$ has empty intersection with value range of $literal$ then

$attLeastOneAttDisjunct\leftarrow$ TRUE

break

end if

end for

if $attLeastOneAttDisjunct$ = FALSE then

$clashingRuleFound\leftarrow$ TRUE

end if

end for

if $clashingRuleFound$ = FALSE then

$rules$ $\leftarrow$ $rules\setminus prunCand$

end if

end for

return _rules_

##  Appendix B Formal Introduction to Association Rule Classification

In the following, we define the main concepts relating to association rule
classification. We also introduce several extensions to the commonly used
notation in order to preserve the link between the discretized and the
original data.

######  Definition 3.

(training dataset) A training dataset $\mathbf{T}$ is a set of objects
$\\{o\\}$, each object described by vector $\langle
o_{1},\ldots,o_{n},c\rangle\in dom(\mathbf{A}_{1})\times\ldots\times
dom(\mathbf{A}_{n})\times dom(\mathbf{C})$, where $dom({A}_{i})$ is the domain
of predictor attribute $A_{i}$ and $dom(C)$ the domain of the target attribute
(class label) C.

The training dataset is comprised of objects (instances) which are described
by attributes. We distinguish between two types of attributes: nominal and
quantitative. An ordinal attribute is not considered as a separate type, since
it can be converted to a quantitative attribute.

######  Definition 4.

(attribute in training dataset) A domain of an attribute $A$, denoted as
$dom(\mathbf{A})$, is a set of all distinct values $dom(\mathbf{A})=\\{v\\}$
of attribute $A$ in the training dataset $T$. An attribute can be either of a
“nominal” or “cardinal” type.

  1. 1.

If A is a nominal attribute then $dom(\mathbf{A})$, then every two different
values $v_{1},v_{2}\in dom(\mathbf{A})$ are incomparable.

  2. 2.

If A is a quantitative attribute then $dom(\mathbf{A})$, then for every two
different values $v_{1},v_{2}\in dom(\mathbf{A})$ it either holds that
$v_{1}>v_{2}$ or $v_{2}>v_{1}$.

A typical association rule learning setup involves discretization of all
quantitative attributes in the training dataset into bins. Nominal attributes
with many distinct values can also be binned if a distance function is known,
but this is out of scope of our paper. The result of preprocessing is a
modified training dataset $\mathbf{\overline{T}}$, which contains a smaller
number of distinct values. Assuming that an attribute $A$ with domain
$dom(\mathbf{A})=\\{v\\}$ was discretized and the result is attribute
$\bar{A}$ with domain $\bar{dom(\mathbf{A})}=\\{\bar{v}\\}$, then each value
$\bar{v}\in\bar{dom(\mathbf{A})}$ can be mapped to one or more values $v\in
dom(\mathbf{A})$.

######  Definition 5.

(preprocessed training dataset) Let $f_{i}:dom(\mathbf{A_{i}})\rightarrow
dom(\mathbf{\bar{A}}_{i})$ be a preprocessing function for attribute $A_{i}$.
Training set $\mathbf{\overline{T}}$ consists of objects $\bar{o}=\langle
f_{1}(o_{1}),\ldots,f_{n}(o_{n}),c\rangle$, where $o=\langle o_{1}\ldots
o_{n},c\rangle\in\mathbf{T}$.

In the following we assume that rules are learned on the preprocessed dataset
$\mathbf{\overline{T}}$ in the attribute space
$dom(\mathbf{\bar{A}}_{1})\times\ldots\times dom(\mathbf{\bar{A}}_{n})\times
dom(\mathbf{C})$. Each preprocessed value $\bar{v}$ appearing in the
discovered rule can be represented using one or more values from the original
attribute space. In the following, we will thus refer to the original
attribute space and training set $\mathbf{T}$ unless explicitly noted
otherwise.

Example. (rule in original and preprocessed space) Consider the following rule
$r_{1}$: $A_{1}^{\prime}=a_{1,2}^{\prime}\land
A_{2}^{\prime}=a_{2,1}^{\prime}\rightarrow C=c_{1}$. The rule contains two
literals defined over two attributes:
$dom(\mathbf{A_{1}^{\prime}})=\\{a_{1,1}^{\prime},a_{1,2}^{\prime},a_{1,3}^{\prime}\\}$
and $dom(\mathbf{A_{2}^{\prime}})=\\{a_{2,1}^{\prime},a_{2,2}^{\prime}\\}$.
Attribute $A_{1}^{\prime}$ is created by performing discretization of
quantitative attribute $dom(\mathbf{A_{1}})=\langle
a_{1,1},a_{1,2},a_{1,3},a_{1,4},a_{1,5},a_{1,6},a_{1,7}\rangle$ in the
original dataset, which is depicted in Table 10. The attribute
$A_{2}^{\prime}$ is nominal, and the bins were created by user-defined value
merging. In a dataset dealing with preferences of second-hand car buyers,
$dom(\mathbf{A_{1}})=\\{1\ldots 7\\}$ could correspond to the age of the car
in years and $dom(\mathbf{A_{2}})=\\{yellow,brown,white,black\\}$ to colour of
the car, $dom(\mathbf{A_{1}})^{\prime}=\langle[1,3),[3,5),[5,7]\rangle$,
$dom(\mathbf{A_{2}^{\prime}})=\\{light,dark\\}$. The class $c_{1}$ expresses
the value “highly preferred”.

$A_{1}$ |  | $A_{1}^{\prime}$ | $A_{2}$ |  | $A_{2}^{\prime}$
---|---|---|---|---|---
$a_{1,1},a_{1,2}$ | $\rightarrow$ | $a_{1,1}^{\prime}$ | $a_{2,1},a_{2,3}$ | $\rightarrow$ | $a_{2,1}^{\prime}$
$a_{1,3},a_{1,4}$ | $\rightarrow$ | $a_{1,2}^{\prime}$ | $a_{2,2},a_{2,4}$ | $\rightarrow$ | $a_{2,2}^{\prime}$
$a_{1,5},a_{1,6},a_{1,7}$ | $\rightarrow$ | $a_{1,3}^{\prime}$ |  |  |
Table 10: Example of the discretization process

In our approach, we process conjunctive rules composed of literals:

######  Definition 6.

(literal) A literal $l=(A,V)$ defined on attribute $A$ is an association of
attribute $A$ with value range $V$.

Most association rule learning algorithms (such as Apriori, FP-Growth or Eclat
han2007frequent ), output rules in which one literal corresponds to one value
(or as originally called, with some simplification, an _item_). In our
framework, we assume that a literal may be associated with a value range,
which is a disjunction of multiple attribute values. The primary reason for
extending the definition of literal, as present in Yin03cpar:classification ,
is that multi-value literals are on the output of the Extension procedure,
which is a part of our approach introduced in Section 3.

######  Definition 7.

(value range of literal defined on nominal attribute) Let $l=(A,V)$ be a
literal defined over a nominal attribute $A$. The value range $V$ is a set of
$m\geq 1$ values: $V=\\{v_{i}\\},v_{i}\in dom(\mathbf{A})$.

For literals created over a quantitative attribute, the literal is a
subsequence of values in the domain of the attribute.

######  Definition 8.

(value range of literal defined on quantitative attribute) Let $l=(A,V)$ be a
literal defined over a quantitative attribute $A$. The value range $V$ is a
sequence of $m\geq 1$ values: $\langle
x_{1},\ldots,x_{i},\ldots,x_{m}\rangle,\forall_{i=1\ldots m}x_{i}\in
dom(\mathbf{A})$.The sequence $V$ has the property that among each two its
consecutive elements $x_{j}$, $x_{j+1}$ there is no element $y\in
dom(\mathbf{A})$ for which it would hold that $x_{j}<y<x_{j+1}$.

When a candidate rule is created during rule learning or when the rule is
applied on test objects, it is necessary to verify which objects match
individual literals in the rule.

######  Definition 9.

(satisfaction of literal by object) An object $o$ satisfies a literal
$l=(A_{i},V)$ if and only if the value of the object in an attribute $A_{i}$,
denoted as $o_{i}$, meets one of the following conditions:

  1. 1.

$A_{i}$ is a nominal or quantitative attribute and $\exists v_{i}\in
V:v_{i}=o_{i}$

  2. 2.

$A_{i}$ is a quantitative attribute and $\exists v_{u},v_{l}\in V:v_{u}\geq
o_{i}\land v_{l}\leq o_{i}$

Condition (2) is applicable only in the test phase, since as follows from
Definition 8, the value range $\langle v_{l},\ldots,v_{u}\rangle$ of a literal
created over a quantitative attribute contains all values in the domain of
attribute A in the training dataset within this range, hence the check with
condition (1) is satisfactory.

######  Definition 10.

(rule) A rule r takes the form $l_{1}\land l_{2},\land\ldots\land
l_{m}\rightarrow c$. The body of a rule, denoted as $body(r)$, consists of a
conjunction of literals $l_{1},l_{2},\ldots,l_{m}$, $m\geq 0$. There are no
two literals $l_{i},l_{j}$ in $body(r)$ which are associated with the same
attribute $A_{k}$. The consequent of the rule consists of a literal $c$, which
is the class label, denoted as $class(r)$, of the rule. Rule is assigned a
confidence, denoted _conf_ $(r)\in[0;1]$, and relative support, denoted as
$supp(r)\in[0;1]$.

######  Definition 11.

(satisfaction of rule body by object) An object $o$ satisfies $body(r)$ if and
only if $o$ satisfies every literal in $body(r)$. If $body(r)$ contains no
literals, any object satisfies it. If an object $o$ satisfies $body(r)$, $r$
predicts that object $o$ is of $class(r)$.

######  Definition 12.

(confidence and support of a rule) Let $r$ be a rule $l_{1}\ldots\land
l_{m}\rightarrow c$, $\mathbf{T}$ a training dataset. Let $\mathbf{S}$ denote
the set of all objects $x\in\mathbf{T}$ for which $x$ satisfies body(r).

Confidence is computed as:

$\mbox{\emph{conf}}(r)=\frac{|o\in\mathbf{S}:o\mbox{ has class label
}c|}{|\mathbf{S}|}.$ (1)

Absolute support is computed as:

$abs\\_supp(r)=|o\in\mathbf{S}:o\mbox{ has class label }c|.$ (2)

Support as:

$supp(r)=\frac{abs\\_supp(r)}{|\mathbf{T}|}.$ (3)

In addition to the standard confidence and support metrics typically used to
characterize association rules, we will introduce two other metrics: rule
volume and rule density. The notion of density and volume within the scope of
frequent itemset mining appeared already in agrawal1998automatic  as follows:
the data space is divided by discretization (equal-length intervals) into
indivisible units. Each unit is assumed to have the same volume and the
density corresponds to the number of points inside the unit.

Since the purpose of our work is to dismantle the intervals created by
discretization, we need to define the rule volume more precisely, taking into
account the real length of intervals and addressing nominal attributes.

######  Definition 13.

(rule volume) The volume of a rule $r$ is computed as

$volume(r)=\prod_{A\in\mathcal{A}}length(A,r),$ (4)

where $\mathcal{A}$ is the set of predictor attributes in training set
$\mathbf{T}$. The length computation for attribute $A$ depends on whether the
rule contains a literal $l=(A,V)$ defined on attribute $A$ and on whether $A$
is a nominal or a quantitative attribute:

Case 1: rule $r$ contains literal $l=(A,V)$ defined on attribute $A$.

$length(A,r)=\begin{cases}\frac{|min(V)-max(V)|}{|min(A)-max(A)|}\mbox{ if $A$
is a quantitative attribute }\\\ \frac{|V|}{|\mathcal{A}|}\mbox{if $A$ is a
nominal attribute.}\\\ \end{cases}$ (5)

Case 2: rule $r$ does not contain literal $l=(A,V)$ defined on attribute $A$.

$length(A,r)=1$ (6)

In Case 1, the value ranges of domains of predictor attributes are normalized
to the interval $[0;1]$ interval prior to the volume computation. For nominal
values, each value is considered to have an equal importance, length is thus
computed as the number of values in the condition divided by the number of
distinct values of the attribute. In Case 2, if a literal defined on attribute
$A$ is not present in the rule, the rule does not put any constraint on the
values of $A$ in the matching test instance. The rule thus covers the entire
domain of attribute $A$, denoted as $dom(\mathbf{A})$. Consistently with Case
1, the entire range is 1.

######  Definition 14.

(rule density) The density of rule $r$ is computed as

$\rho(r)=\frac{abs\\_supp(r)}{volume(r)},$ (7)

where $volume(r)$ is the _volume_ of rule $r$ and $abs\\_supp(r)$ is the
number of instances correctly classified by rule $r$.

The intuition behind the density equation is that $abs\\_supp$ corresponds to
the number of “particles of interest”: instances of the class in rule
antecedent that are covered by the rule. The concept of _volume_ delimits the
entire size of the spatial unit covered by the rule.

Class association rule learning is executed on the training dataset
$\mathbf{T}$ with $C$ as the target attribute. The output is a set of all
rules that meet the predefined minimum support and minimum confidence
thresholds (and possibly some other constraints and settings).

######  Definition 15.

(rule list) The output of class association rule learning is an ordered
sequence of rules $R=\langle r_{1},\ldots,r_{m}\rangle$.

The rule list represents a classifier, which can be evaluated using standard
machine learning metrics, such as accuracy.

######  Definition 16.

(classifier accuracy) Accuracy of classifier $cl$ is computed as

$acc(cl)=\frac{correct}{N},$ (8)

where correct is the total number of correctly classified objects, and N is
the total number of the classified objects.

##  Appendix C Properties of the Proposed Tuning Steps

###  C.1 Complexity

This subsection relates the complexity of the proposed steps to the number of
conditions in the input rule (for rule tuning steps) and to the number of
rules (for rule pruning steps). Similarly as in other works that analyze
complexity of association rule learning classifiers such as huhn2009furia , we
focus primarily on the number of conditions in the rule.171717For example,
Hühn and Hüllermeier huhn2009furia  state that for FURIA, the complexity or
re-evaluating a rule is $O(|\mathcal{A}(r)|)$, where $\mathcal{A}(r)$ is the
number of conditions in rule antecedent.

#### Refit

The refit tuning step processes all conditions in a given rule (Algorithm 2)
The complexity of the refit tuning step is $O(n)$, where $n$ is the number of
conditions.

#### Literal pruning

Each iteration of the inner loop in Algorithm 3 tries to removes one literal
(condition) from rule $r$ and evaluates the candidate rule $r^{\prime}$. In
the worst case, in each iteration of the outer loop, the last literal tried
will result in $r^{\prime}$ to be accepted, replacing $r$. In other words,
assuming that there are $n$ conditions, the first iteration of the outer loop
will remove a literal during the $n$-th iteration. In the next iteration of
the outer loop, there will be $n-1$ literals remaining. For a given rule, the
worst-case complexity of the literal pruning operation is thus $O(n!)$, where
$n$ is the number of attributes in the rule. While this worst-case complexity
may seem excessive, in our experience, it is rarely the case that the rule
learning setup needs to allow rules with more than four or five conditions.

#### Trimming

The number of iterations of Algorithm 4 corresponds to the number of
conditions in the rule. The complexity is thus $O(n)$.

#### Extension

In the worst case, the Algorithm 6 evaluates all possible extensions of the
input rule. Let $r$ be the seed rule on the input of extension and
$l_{i},\ldots,\l_{n}\in body(r)$ the literals in the rule antecedent.
According to Definition 8 value range of a literal $l=(A,V)$ on a quantitative
attribute $A$ is a sequence of $|V|$ distinct values. The extension procedure
will, in the worst case, evaluate rules corresponding to all combinations of
subsequences of value ranges of all attributes present in the seed rule, where
every subsequence created for given attribute has to contain the value range
from the literal in the seed rule. For attribute $A$, the number of distinct
values is $|dom(\mathbf{A})|$, however, every literal $l^{\prime}$ resulting
from extension of $l$ has to contain $V$ as a subsequence, therefore we need
to consider all values in $V$ as one value for the purpose of subsequence
counting. If the conditional accept is enabled, a particular combination can
be evaluated more than once. Assuming that all evaluations of a particular
candidate rule are cached and that the cost of retrieval of the cached
evaluation of the rule is zero, we can neglect these repeated evaluations. The
resulting complexity is thus
$O(\prod_{i=1}^{n}s(|dom(\mathbf{A}_{i})|-|V_{i}|+1))$, where the function
$s(n)=\frac{n(n+1)}{2}$ gives the number of subsequences of consecutive
elements that can be created from $n$ elements.

#### Postpruning

The complexity is the same as of the CBA pruning
Liu98integratingclassification . For an empirical evaluation, refer to
jiriclassification .

#### Default Rule Overlap Pruning

The complexity of the transaction-based default rule overlap pruning
(Algorithm 8) depends on the number of rules processed. To determine if a
given rule classifying into the same class as the default rule (_pruning
candidate_) is redundant, all rules below it that classify into a different
class need to be processed. The complexity also depends on the distribution of
rules by predicted class, and on the position of the rules in the rule list.
If the number of classes is $|C|$ and the number of rules is $|R|$, then we
can assume that $\frac{|R|}{|C|}$ rules classify into the default class and
$R-\frac{|R|}{|C|}$ rules classify to other than default class (_candidate
clash_ rules). Let us assume that the average position of the pruning
candidate is in the middle of the rule list, which means that we have on
average $\frac{1}{2}(R-\frac{|R|}{|C|})$ candidate clash rules to check for
the average pruning candidate. The average computational complexity is thus
$O(\frac{|R|}{|C|}\times\frac{1}{2}(R-\frac{|R|}{|C|})$.

###  C.2 Effects on classification performance and model size

Selected properties are present in Table 11. The first part of the table
contains measures applying to single rules as “local classifiers”.In the
second part, there are measures applying to the rule list as a whole (the
“global classifier”): number of rules in the rule list (rule count), and
classifier accuracy. The entries denote the effect of applying the algorithm
specified in the first column on the input rule list. $\geq$ denotes that the
value of the given metric will increase or will not change, = the value will
not change, $\leq$ decrease or will not change, $\lesseqqgtr$ can increase,
decrease or will not change. For example, applying the refit algorithm on a
rule can have the following effects according to the table: the density181818
_Density_ is a newly proposed measure, which is computed as the number of
correctly classified instances divided by the volume covered by the antecedent
of the rule (cf. Definition 14 in Appendix B). of the rule will improve or
remain the same: the (+) symbol in the table denotes that the increase in rule
density is considered as a favourable property. Rule confidence (_conf_), rule
support (_supp_), rule length (_length_) will remain unaffected. Considering
the entire rule list, the refit operation will not affect the rule count or
accuracy on training data ($acc_{train}$). There is no guarantee for accuracy
on unseen data ($acc_{test}$).

algorithm | rule (local classifier) | rule list
---|---|---
dataset | density | conf | supp | length | $acc_{train}$ | $acc_{test}$ | rule count
refit |  $\geq$ (+) | = | = | = | = | $\lesseqqgtr$ | =
literal pruning | $\lesseqqgtr$ | $\geq$ | $\geq(+)$ | $\geq(+)$ | $\lesseqqgtr$ | $\lesseqqgtr$ | =
trimming |  $\geq$(+) | $\geq(+)$ | = | = | $\geq(+)$ | $\lesseqqgtr$ | =
extension | $\lesseqqgtr$ | $\geq(+)$ | $\geq(+)$ | = | $\lesseqqgtr$ | $\lesseqqgtr$ | =
postpruning | = | = | = | = | $\lesseqqgtr$ | $\lesseqqgtr$ |  $\leq$ (+)
drop - trans. | = | = | = | = | = | $\lesseqqgtr$ |  $\leq$ (+)
drop - range | = | = | = | = | = | = |  $\leq$ (+)
Table 11: Properties of the proposed rule tuning algorithms.