Association rule extraction is a very well-known and important problem in machine learning, and especially in the sub- eld of explainable machine learning. Association rules are naturally extracted from data sets with Boolean (or at least categorical) attributes. In order for rule extraction algorithms to be applicable to data sets with numerical attributes as well, data must be suitably discretized, and a great amount of work has been devoted to nding good discretization algorithms, taking into account that optimal discretization is a NP-hard problem. Motivated by a speci c application, in this paper we provide a novel discretization algorithm de ned as an (heuristic) optimization problem and solved by an evolutionary algorithm, and we test its performances against well-known available solutions, proving (experimentally) that we are able to extract more rules in a easier way.
Among the most relevant problems in machine learning there are classi cation
problem and association rule extraction problem. An association rule is an if-then
statement that helps to show the probability of certain relationship among the
attributes of a data set. While classi cation is a global problem (e.g., a
logistic regression model that classi es all instances), association rule extraction is
a local problem, that makes it possible for unusual, uncommon relationships to
emerge. The rst, and most successful, rule extraction algorithm is Agrawal and
Srikant's APRIORI [
The approaches to the discretization (or binning) problem, or the problem
of mining quantitative association rules can be categorized into deterministic
(greedy), or non-deterministic (usually based on metaheuristics). Deterministic
static approaches simply cut the domain of a continuous attribute into a
predened number of bins before the mining process. Agrawal's solution to
discretization can be considered static. Indeed, it is built on a deterministic procedure
that partitions each quantitative attribute one-by-one (i.e., without considering
the distribution of the other attributes) into equal-width intervals, and on a
modi cation to the original APRIORI algorithm to handle sets of items that
are generalizations of others (e.g., saying that the age of someone varies in the
interval [20; 29] is more general than saying that it varies in the interval [20; 24])
and to take into account a newly introduced interestingness measure. Moreover,
adjacent intervals can be merged to compensate the low con dence of rules in
some cases. Discretization algorithms are available in some open-source learning
frameworks that belong to this category and allow both equal-width and
equalfrequency discretizations, but are separated from the rule learning phase, which
is applied to the resulting, discretized, data set: WEKA's discretization lter [
In this paper we consider a data set that represents the measurement of
several air quality parameters on a speci c monitoring station in the center of
Wroclaw (Poland) during the interval of three years. Such a data set has been
studied in the context of global explanation models (e.g., in [
The paper is organized as follows. Section 2 presents the needed preliminaries, Section 3 formalizes the dynamic discretization process as an optimization problem together with implementation details, Section 4 discusses the data and the experimental setup, and, nally, Section 5 discusses the results of the proposed method before concluding in Section 6. 2
Discretization. The discretization of the numerical attributes of a data set is a
preprocessing phase, much like feature selection or outlier detection.
Preprocessing approaches, which are designed to enable or improve a data mining process
on a data set, are classically separated into lters, wrappers, or embedded
algorithms. A lter, which is by large the most common type, is an algorithm that
uses statistical indicators to perform the preprocessing; it is independent from
the data mining or model extraction phase, which is applied to the resulting
data set. A wrapper is a combined approach, in which the result of the
preprocessing phase is continuously evaluated using the performances of a selected
data mining algorithm, in search of an optimal solution. Embedded algorithms
for preprocessing are integrated data mining algorithms, in which the
preprocessing is part of the mining process; by nature, embedded algorithms are more
di cult to implement, and therefore less common. The most relevant examples
of discretization lters are included in some open-source learning frameworks,
namely WEKA's discretization lter [
Multiobjective optimization. A multiobjective optimization problem (see,
e.g. [
: : :
>
>: min = max ft(x);
(1)
where x is a vector of decision variables. A multiobjective optimization problem
can be continuous, in which we look for real values, or combinatorial, where we
look for objects from a countably (in) nite set, typically integers, permutations,
or graphs. Maximization and minimization problems can be reduced to each
other, so that it is su cient to consider one type only. A set F of solutions for a
multiobjective problem is non-dominated (or Pareto optimal ) if and only if for
each x 2 F , there exists no y 2 F such that (i) there exists i (1 i t) that
fi (y) improves over fi (x), and (ii) for every j, (1 j t, j 6= i), fj (x) does
not improve fi (y). In other words, a solution x dominates a solution y if and
only if x is better than y in at least one objective, and it is not worse than y in
the remaining objectives. We say that x is non-dominated if and only if there
is no other solution that dominates it. The set of non-dominated solutions from
F is called Pareto front. Optimization problems can be approached in several
ways; among them, multiobjective evolutionary algorithms are a popular choice
(see, e.g. [
Rule extraction. For a given categorical data set A, with categorical attributes
A = fA1; : : : ; Ang, an association rule is an object of the type:
: 1 ^ : : : ^ s ) s+1
where s < n and i belongs to the domain of Ai, for each i. As de ned by
Agrawal and Srikant [
Binning. Given a numerical attribute, the rst step to dynamic discretization is de ning a parametric function that returns the bins. Thus, let now A be a numerical data set with attributes A = fA1; : : : ; Ang:
2 a11 a12 : : : a1n 3 A = 664 a:2:1: a:2:2: :: :: :: a: 2: n: 757
am1 am2 : : : amn For a variable Ai, we denote by i its mean in A, and by i its standard deviation; moreover, let ki 2 (0; 1] be a displacement parameter. For a given number li of expected bins in which we want to discretize the domain of Ai, let i1; : : : ; ili be the corresponding labels. Now, let v(Ai) be a certain value of the variable Ai; by writing v(Ai) 2 ip we indicate that the interval/bin denoted by the label ip includes the value v(Ai). Then, we set that v(Ai) 2 ip if: >8 v(Ai) < i bli=2cki i >><> i (dli=2e p + 1)ki i v(Ai) < i
i ki i v(Ai) i + ki i >>> i + (p dli=2e)ki i < v(Ai) > : i + bli=2cki i < v(Ai)
i + (p for an odd li, and if: (dli=2e
if p = 1 p)ki i if 1 < p < dli=2e
if p = dli=2e dli=2e + 1)ki i if dli=2e < p < li if p = li (2) 8> v(Ai) i >>>> i (li=2 >< i (li=2 > i < v(Ai) >>>> i + (p li=2 >: i + (p li=2 (li=2 p)ki i p + 1)ki i < v(Ai) p + 1)ki i < v(Ai) i + (p li=2)ki i 1)ki i < v(Ai) 1)ki i < v(Ai)
(li=2 i i i + (p
if p = 1 p)ki i if 1 < p < li=2 if p = li=2 if p = li=2 + 1 li=2)ki i if li=2 + 1 < p < li if p = li (3) for an even li. In Figure 1 (top) we graphically represented the transformation for a given i; i; and ki, and for the odd case with li = 5. Intuitively, ki represents how far an endpoint of a bin is from the mean ( i) in terms of standard i ki i i i + ki i Optimization parameters: ki 2 (0; 1] R displacement li 2 [2; : : : ; maxLabels] N number of labels deviations ( i). Applying it to the original numerical data set clearly leads to a categorical one from which rules can be extracted: For variables following the normal (Gaussian) distribution, this algorithm is a simple generalization of the common equal-width binning (with a particular con guration for li and ki); yet, as we shall see, for non-normally distributed variables our technique often returns more signi cant bins.
Binning as an optimization problem. Our purpose is to devise a good
discretization of a numerical data set using our distribution-based technique, that is,
to learn a good pair of values (ki; li), for each numerical attribute Ai. Following
the taxonomy that we have identi ed in Section 2, we design our
discretization algorithm as a wrapper, where APRIORI is used as a black-box. Because
of the nature of the classical implementation of APRIORI, support and con
dence must be set beforehand; therefore, optimizing these parameters may be
less meaningful. On the other hand, we are not just interested in precise rules,
but also in meaningful ones w.r.t. to speci c domain-application (e.g.,
particular situations). As pointed out in [
mmianxMCaeradn(bxin)s(x) (5)aa mmianxMMaexabnicnosn(fx)(x) (6)aa aa mmianxMMeeaannbcionnsf(x(x)) (7)aa Observe that minimizing the number of labels goes in favour of interpretable rules, while having at least two (non-empty) labels per attribute goes in favour of having meaningful rules.
Implementation. Multiobjective evolutionary algorithms are known to be
particularly suitable to perform multiobjective optimization, as they search for
multiple optimal solutions in parallel. In this experiment we have chosen the
well-known NSGA-II (Non-dominated Sorted Genetic Algorithm) [
(k1; l1); (k2; l2); : : : ; (kn; ln) in which, as in Figure 1 (bottom), 2 li maxLabels, where maxLabels is a predetermined parameter, and ki 2 (0; 1]. The initial population is generated randomly. Mutation and Crossover were slightly modi ed to take into account the particular nature of our solutions. In particular, a mutation is performed, randomly with the same probability, over the rst or the second component of the chosen attribute; the displacement is either substituted by random element in (0; 1] or incremented or subtracted by the value 0:1, while the number of labels is either substituted by a random (integer) element in [2; maxLabels] or incremented or subtracted by 1. Similarly, a crossover is performed at the level of the pair (ki; li), that is, given two individuals to be crossed, two random pairs are chosen for each one of them and cross-exchanged. This particular con guration for performing both Mutation and Crossover is one among many others; the systematic study of other con gurations is beyond the scope of this paper.
Variable Unit Air temp. (a) C Solar dur. (d) h Wind speed (w) ms 1 % Rel. hum. (r) Air pressure (p) hP a Tra c (t) N O2 N Ox 4
Data origin. There is only one communication station for measuring the air
quality in the city of Wroclaw, and it is located within a wide street with two
tra c lanes in each direction (GPS coordinates: 51.086390 North, 17.012076
East). The center of one of the largest intersections in the city with 14 tra c
lanes is located approximately 30 meters from the measuring station, and is
covered by tra c monitoring. The measurement station is located on the outskirts
of the city, at 9:6km from the airport. Pollution data are collected by the
Provincial Environment Protection Inspectorate and encompasses the hourly N O2 and
N Ox concentration values during full three years, from 2015 to 2017. Tra c data
are provided by the Tra c Public Transport Management Department of the
Roads and City Maintenance Board in Wroclaw, and include hourly count of all
types vehicles passing the intersection. Public meteorological data are provided
by the Institute of Meteorology and Water Management, and they include: air
temperature, solar duration, wind speed, relative humidity, and air pressure. In
order to have uniform data, solar duration values have been re-normalized in the
real interval [0; 1] (as standard). The full data set contains 26304 observations.
In the pre-processing phase, the instances with at least one missing value (617
samples, 2.3%) have been deleted. Some basic statistic indicators on the
remaining 25687 instances are presented in Table 1, along with the symbol used in the
tests for each variable. Unlike previous work in these data (e.g., in [
Results. In Table 2 and Table 3 we show the results of the execution of
optimization model (4) and (6). The results of model (5) (resp., (7)) are very similar
to those of model (4) (resp., (6)), and therefore are not shown. Model (4)
obviously extracts more rules than (6) in every con guration, given that we optimize
precisely the number of rules. In each line of both tables, we show: the
minimal support and con dence of rules with which APRIORI has been called; the
number of rules of the selected nal solution (more rules is better); the average
length of the rules (smaller rules is better for, e.g., interpretability); the average
con dence (more con dent rules is better); and a quality index that depends
on our particular application, that is, the number of rules whose consequent
is N O2 with highest values. In particular, we are interested in extracting rules
that may possibly explain sudden, and not necessarily common, high values of
the pollutant; yet, this parameter is merely informative, as not only depends on
the application, but, also, its importance is subject to interpretation. As we can
see, in both models we are able to extract progressively less rules as the
minimal support and minimal con dence that are requested grow. To each solution
is associated a mask, that is, the set of values (k1; l1); (k2; l2); : : : ; (kn; ln) that
correspond to the particular discretization; this mask, in turn, gives rise to the
values that have been used to decide the bin to which each attribute of each
particular instance belongs. As it often happens in rule extraction, interpreting
the results is not immediate due to the number of extracted rules. While a
correct and detailed N O2 contamination model is outside the scope of this paper,
from [
Comparison with existing methods. A natural question at this point is whether we could have obtained similar results with the existing methods. To answer this question we considered a static discretizer (the class Discretize in WEKA, which behaves identically to the other available static lters in R and in Python). As we have discussed in Section 2, a static discretizer usually o ers equal-width and equal-frequency binning. While for normally distributed variables (i.e., Gaussian-like) both settings may return meaningful results, for non-normally distributed ones a further analysis of this aspect is necessary. Consider the case, for example, of the variable N O2 in our data, which is strongly right-skewed. In Figure 2 we compare the result obtained by the three di erent solutions (equal-width, equal-frequency, and our dynamic discretizer) in the case of two bins; because of the distribution, equal-width binning in this case returns a bin (N O2 117:64) which is meaningless: as a matter of fact, all rules that can be extracted with the di erent settings (support varying from 0.1 to 0.4, con dence varying from 0.7 to 0.85) return rules with that particular bin as consequent, which is uninformative because it is true almost in every instance. Therefore, equal-width binning makes little sense in our data set. Equal-frequency binning returned better results. For an adequate comparison, for each experimental setup, we have chosen the best mask (e.g., [(0:2; 2); (0:4; 2); (1:0; 3); (1:0; 2); (0:7; 5); (0:6; 5); (1:0; 2)]) returned by our algorithm, and asked the static lter to use that particular choice as number of bins for each variable (observe that deciding the number of bins is a problem in static binning - obviously, choosing the best option goes towards the fairest comparison). The results of such an experiments are shown in Table 5: only a few rules emerged, and none of them falls in one of the interesting categories that we have mentioned above. The most frequent result in all experiment shows a 3bins splitting for N O2, and Figure 3 gives us a hint of the problems that emerge during equal-frequency binning: as one can see, the resulting middle group is too narrow for a meaningful rule to be extracted. 6
In this paper we have considered a data set that represents the hourly measurement of several air quality parameters on a speci c monitoring station in the center of Wroclaw (Poland) during the interval of three years. Instead of searching for a general explanation model for these data, we have focused on extracting meaningful local rules w.r.t. the pollutant, which may be useful to model the particular situations that occurred during the measurement period. We proposed and tested a multivariate, non-deterministic, distribution-based discretization algorithm coupled with the well-known rule extraction algorithm APRIORI, and implemented it via the evolutionary algorithm NSGA-II. We experimentally proved that our solution produces more rules and, in some cases, more interesting rules w.r.t. the speci c domain-application than those produced by the discretization algorithms available in some open-source learning libraries.
It is well known that optimal preprocessing is a computationally hard problem,
and commonly accepted that learning algorithms use sub-optimal (deterministic
or heuristic-based) solutions. Yet, precisely pinpointing the formal problem is
mathematically interesting per se. Discretization as a classi cation task has been
studied from the theoretical point of view in [
Consider a numerical data set A with n features plus one (categorical) class D (in this context, referred to as decision):
2 a11 a12 : : : a1n d1 3 A = 664 a:2:1: a:2:2: :: :: :: a: 2: n: :d:s:757
am1 am2 : : : amn dm
A pair (Ai; c), where Ai is an attribute and c 2 R is called cut. Any set of cuts f(Ai; c1); : : : ; (Ai; cl)g implicitly de nes the partition f( 1; c1); [c1; c2); : : : ; [cl; +1)g (denoted f i1; : : : ; ili g in Section 3). Having a partition for each attribute in A allows us to discretize the original data set to obtain a categorical one:
m1 m2 : : : mn dm Such a discretization is said to be D-consistent if there are no two instances with the same categorical values and di erent class; in other words a D-consistent transformation is the perfect classi cation. If A can be D-consistently discretized using at most l cuts (in total), we write l ! A. Now, let n = 2 and let D be a binary class. One can de ne the language:
L = fhA; li j l ! Ag
In [
L = fhA; l; t; s; ci j l; t !s;c Ag Theorem 1. L is N P -hard.
Proof. The proof is by polynomial reduction, that is, we prove that L p L. To this end, let A be a numerical data set with n = 2 and a binary decision D. We produce a numerical data set A0 with n = 3, where A01 = A1, A02 = A2, and A03 has domain f0; 1g (that is, we copy the entire data set column-by-column, interpreting the decision as a numerical attribute). Now, we claim that l ! A if and only if l + 2; 2 !1;1 A0, that is, hA; li 2 L if and only if hA; l + 2; 2; 1; 1i 2 L. Suppose, rst, that l + 2; 2 !1;1 A0. By de nition, there exists at least one rule 1 ^ : : : ^ s ! 0 and at least one rule 10 ^ : : : ^ s00 ! 1 that hold in (the discretized counterpart of) A0 with minimal con dence 1. Because of the requirement on the minimal total support, every instance is the support of some rule; because of the requirement on the minimal local con dence, no instance can be in the support of more than one rule. It is now immediate to interpret the set of extracted rules as a rule-based classi er with perfect score, that is, to see that l ! A. Suppose, on the other hand, that l ! A holds. Every instance can be seen as a rule; all such rules have con dence at least one, because A is D-consistently discretized, and no instance is left without its corresponding rule, which means that the total support is 1, that is, that l + 2; 2 !1;1 A0,as we wanted.