\section{Introduction}
\label{sec.motivation}

The classification task %is to 
builds an abstract model from labeled data (i.e., the training-set), and then apply such abstract model (aka., classifier) for predicting unknown (discrete) variables in the data (i.e., the test-set).
Historically, the typical goal of classification algorithms is to maximize accuracy as much as possible, often by building classifiers that are not readable, such as KNNs~\cite{knn}, SVMs~\cite{cortes,svm}, and Naive Bayes~\cite{bayes2,bayes1}.
In several application scenarios, however, the ability to interpret the classification result is increasingly becoming as important as the ability to classify correctly.
For instance, in diagnosis of lung cancer the doctor must know
features that were decisive in the prediction~\cite{vis1}. Other applications in which the readability of the classifier is of paramount importance include
fraud detection, credit analysis and impact analysis of marketing campaigns.

Interpretable classifiers are mainly represented by decision trees~\cite{trees,boat} and by associative classifiers~\cite{cba}.
However, modeling large and complex datasets using tree-like structures and rule-sets usually results in large and possibly hard-to-read models. Learning associative classifiers on a demand-driven basis~\cite{tags,book} comes as an alternative to this problem: instead of building a single and unnecessarily complex rule-set that explains the entire training-set, several simpler rule-sets are built, where each rule-set explains a subset of the training-set which is relevant to a specific test instance, resulting in one classifier (i.e., model) for each test instance. It can be shown that the number of rules that compose each classifier increases polynomially with the number of distinct features in the training-set~\cite{lac}, but this still corresponds to an exponential growth with the number of features within the test instance. This exponential dependence may challenge the readability of the classifiers, and thus the problem we address in this paper is how to ensure readability of associative classifiers 
without compromising their accuracy.

Our proposed strategy lies on assessing the utility (or efficiency) of each rule in the original rule-set by evaluating it under different statistical criteria. Such criteria include important rule statistics~\cite{measure1}, namely: support, confidence, added-value, and Yule's Q. Intuitively, we want to select those rules that provide the best trade-off or balance amongst these four criteria. 
The proposed strategy for filtering efficient rules is based on the concept
of Pareto Efficiency~\cite{palda@book}. This is a central concept in Economics, which informally states
that ``{\em when some action could be done to make at least one person better off without
hurting anyone else, then it should be done.}'' This action is called Pareto improvement,
and a system is said to be Pareto-Efficient (or Pareto-Optimal) if no such improvement is possible.
The same concept may be exploited for the sake of selecting efficient rules.
In this case, each candidate rule is associated with a point in a $n$-dimensional space (or scattergram), which we call {\em rule-utility space}. Each dimension in this space corresponds to one of the four statistical criteria used. Points that are not dominated by any other point in this space compose the {\em Pareto Frontier}~\cite{pesa}. Points lying in the frontier correspond to rules for which no Pareto improvement is possible, being therefore optimal rules in the sense there is no rule that is better off when all the criteria are taken into account. Optimal rules are selected and compose the final classifier.

We conducted a systematic evaluation involving benchmark data from the UCI repository~\cite{uci}, as well as real data obtained from more challenging application scenarios, such as sentiment stream analysis~\cite{pak,sigir}.
Our experiments revealed that the proposed filtering strategy based on optimal multi-criteria rules
is extremely effective, drastically decreasing the complexity of the classifiers by reducing the number of rules by up to two orders of magnitude. Also, our filtering strategy may be coupled with condensed representations, such as closed rules. Further, an extensive set of significance tests indicates that the accuracy achieved by these simpler classifiers is statistically equivalent to the accuracy obtained by typically more complex classifiers. As a result, classification is still effective but the underlying model is extremely readable.

The specific contributions of this paper are summarized as follows:
\begin{itemize}
\item Instead of using ad hoc utility measures in order to assess the importance of each rule, we propose a rule-utility space. Rules are selected from such space based on the concept of Pareto-Efficiency.
\item Our rule filtering strategy is in accordance with the Occam's Razor principle~\cite{occam3,occam2,occam1}, since it significantly decreases the complexity of the final classifier, without hurting its classification performance.
\item An extensive set of experiments, in which we evaluate the accuracy and interpretability of the classifiers. Our findings are supported by a proper set of significance tests.
\end{itemize}

In Section 2 we discuss relevant related work and introduce the main concepts used to formulate our proposed rule filtering strategy.
In Section 3 we describe our rule filtering strategy.
In Section 4 we demonstrate the effectiveness of the proposed filtering strategy
through a systematic set of experiments. Finally, in Section 5 we conclude our paper and point out directions for future work.
