\section{Background and Related Work}
\label{sec.background}

In this section we introduce the main concepts that we used to formulate our rule filtering strategy.

\subsection{The Occam's Razor Principle and the Cost of Complexity}

Informally, the Occam's Razor principle states that ``{\em all else being equal, simpler explanations are better}.'' In the context of machine learning and the theory of prediction, this idea can be made precise by choosing appropriate definitions for ``equal", ``simpler" and ``better".
One difficulty, however,
is that many different definitions are possible. Simplicity, for instance,
is typically given as a function of the syntactic size of the classifier:
the number of nodes in a decision tree, the number of conditions in a rule-set,
or, in general, the number of parameters
in the classifier~\cite{occam2}.
Unfortunately, no fully satisfactory
computable definition of simplicity exists, and perhaps none is possible. Thus,
in this paper we will be concerned with the heuristic view of simplicity
above.

Definitions for ``equal'' and ``better'' are also problematic \cite{occam4}. We may consider, for instance, that a classifier is better than other if the first provides lower training-set error. This definition, however, may lead to problems such as overfitting, since the best classifier would be the one with the lowest training-set error. Thus, in this paper we will compare classifiers considering approximations of their generalization error (i.e., by means of cross-validation). Finally, we also consider that a classifier is better than other only if its generalization error is significantly smaller, and thus in this paper we will employ a proper set of significance tests in order to assure statistical difference between the classifiers.

\subsection{Associative Classifiers and Demand-Driven Rule Extraction}

Despite all the discussion concerning Occam's Razor and machine learning, there is another good reason for preferring simpler models and classifiers: they are easier for people
to understand, remember and use (as well as cheaper for computers to store and
manipulate).
Readability and comprehensibility, however, are not solely dependent on model complexity $-$ some classifiers, although simple, are still unreadable. Classification models produced by SVM, KNN or Bayesian algorithms, are not readable, no matter how simple are the models. Although nomograms \cite{visu2,visu1} can be useful tools for enabling the visualization of these models, they are still problematic for high-dimensional problems. Decision trees, on the other hand, are a representative of classifiers that are naturally readable $-$ each path from the root node to a leaf corresponds to a decision or a prediction. 
However, modeling large and complex datasets using tree-like structures results in large and possibly hard-to-read models with many possible paths.

Associative classifiers appear as an alternative to decision trees, since they are highly effective and naturally readable. The classifier (which we denote as $\mathcal{R}$) is composed of rules~\cite{rules} of the form $\{X\xrightarrow{}y\}$, where $X$ is a feature-set and $y$ is the class variable. Such rules are extracted from the training-set (which we denote as $\mathcal{D}$) and then used to perform predictions, that is,
rules in $\mathcal{R}$ are collectively used to approximate the likelihood of an arbitrary example belonging to class $y$. Basically, $\mathcal{R}$ is interpreted as a poll, in which each rule $\{X\xrightarrow{}y\}\in\mathcal{R}$ is a vote given by $X$ for a specific class $y$. Given an example $x$ in the test-set, a rule $\{X\xrightarrow{}y\}$ is only considered a valid vote if it is applicable to $x$.

\vspace{0.2cm}
\noindent{\bf Definition 1:}
{\em A rule $\{X\xrightarrow{}y\}\in\mathcal{R}$ is said to be applicable to example $x$ if $X\subseteq x$. That is, if all features in $X$ are present in example $x$.}
\vspace{0.2cm}

We denote as $\mathcal{R}_x$ the set of rules in $\mathcal{R}$ that are applicable to example $x$. Thus, only and all the rules in $\mathcal{R}_x$ are considered as valid votes when classifying $x$. Further, we denote as $\mathcal{R}^{y}_{x}$ the subset of $\mathcal{R}_{x}$ containing only rules predicting class $y$. Votes in $\mathcal{R}^{y}_{x}$ have different weights, depending on statistics associated with the corresponding rules. The weighted votes for $y$ are averaged, giving the score for $y$ with regard to $x$, as shown in:
\begin{equation}
\label{eq1}
s(x, y)=\displaystyle\sum\theta(X\xrightarrow{}y)
\mbox{, where $\theta(r)$ represents a statistics associated with rule $r$.} 
\end{equation}

Finally, the likelihood of $x$ being a member of class $y$ is given by the normalized score:
\begin{equation}
\label{eq2}
\hat{p}(y|x)=\frac{s(x, y)}{s(x, y)+s(x, \overline{y})}
\end{equation}

\paragraph*{\bf{Training Projection and Demand-Driven Rule Extraction}}
Demand-driven rule extraction~\cite{lac,book} is a recent strategy used to avoid the huge search space for rules, by projecting the training-set $\mathcal{D}$ according to the example being processed. More specifically, rule extraction is delayed until an example $x$ is given for classification. Then,
features in $x$ are used as a filter which
configures the training-set $\mathcal{D}$ in a way that only rules that are applicable
to $x$ can be extracted. This filtering process produces a
projected training-set, denoted as $\mathcal{D}_x$, which contains only features
that are present in $x$. As shown in~\cite{tags}, the number of rules extracted using this strategy grows polynomially with the number of distinct features in $\mathcal{D}$.

\paragraph*{\bf{Extending the Classifier Dynamically}}
With demand-driven rule extraction, the classifier $\mathcal{R}$ is extended dynamically as examples are given for classification. Initially $\mathcal{R}$ is empty; a subset $\mathcal{R}_{x_i}$ is appended to $\mathcal{R}$ every time an example $x_i$ is processed. Thus, after processing a sequence of $m$ examples $\{x_1, x_2, \ldots, x_m\}$, the classifier $\mathcal{R}$ is $\{\mathcal{R}_{x_1}\cup\mathcal{R}_{x_2}\cup\ldots\cup\mathcal{R}_{x_m}\}$.

\subsection{Rule Statistics and Rule-Utility Space}

According to Equation~\ref{eq1}, a statistics is used in order to assess the utility of a rule. Intuitively, the more utility a rule $\{X\xrightarrow{}y\}$ has, the more heavily it contributes to the score associated with $y$. There is a number of possible rule statistics, as pointed out in~\cite{measure1}. Next we define four statistics that are particularly important for the sake of learning associative classifiers.

\vspace{0.2cm}
\noindent{\bf Definition 2:}
{\em The confidence of a rule $\{X\xrightarrow{}y\}$
measures its accuracy in the training-set $\mathcal{D}$, or, in other words, the probability of class $y$ given
 the features in $X$.}
\vspace{0.2cm}

\noindent{\bf Definition 3:}
{\em The support of a rule $\{X\xrightarrow{}y\}$
measures the fraction of examples in the training-set $\mathcal{D}$ in which $\{X\cup y\}$ appears.}
\vspace{0.2cm}

\noindent{\bf Definition 4:}
{\em The added-value of a rule $\{X\xrightarrow{}y\}$
measures the gain in accuracy obtained 
by using the rule instead of always predicting class $y$.}
\vspace{0.2cm}

\noindent{\bf Definition 5:}
{\em Yules'Q
is a measure commonly used to evaluate games. 
More specifically, given two players it evaluates the association between their bets.
The Yules'Q of a rule $\{X\xrightarrow{}y\}$
takes into account players $X$ and $\overline{X}$, and consider possible bets as $y$ and $\overline{y}$. The values assumed by Yules'Q range from perfect negative correlation between $X$ and $y$, to perfect positive correlation.} 
\vspace{0.2cm}

\begin{table}
\caption{Rule statistics and their properties.}
\label{table.intro.metrics.properties}
\centering
\begin{center}
\begin{tabular}{|l|l|c|c|c|c|c|c|c|c|c|}\hline
 \multicolumn{1}{|c|}{ \multirow{2}{*}{\textbf{Statistics}} }&  \multicolumn{1}{c|}{ \multirow{2}{*}{\textbf{Formula}}} & \multirow{2}{*}{\textbf{Range}} & \multicolumn{8}{c|}{\textbf{Properties}} \\ \cline{4-11}
 &  & & \textbf{P1} &  \textbf{P2} &  \textbf{P3} &  \textbf{P4} &  \textbf{P5} &  \textbf{P6} &  \textbf{P7} &  \textbf{P8} \\ \hline \hline

 Confidence &  $\mathbb{P}(y|X)$  & $ [0.0,1.0]$ & 0 & 1 & 0 &  0 & 0  & 0 & 0 & 1  \\ \hline

 Support & $\mathbb{P}(X\cup y)$ & $[0.0,1.0]$ & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0  \\ \hline

 Added Value & $\mathbb{P}(y|X) - \mathbb{P}(y)$   & $[-0.5,1.0]$ & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0  \\  \hline

 Yules'Q &  $\frac{\mathbb{P}(X\cup y) \mathbb{P}(\overline{X\cup y}) - \mathbb{P}(X\cup\overline{y}) \mathbb{P}(\overline{X}\cup y)}{\mathbb{P}(X\cup y) \mathbb{P}(\overline{X\cup y}) + \mathbb{P}(X\cup\overline{y}) \mathbb{P}(\overline{X}\cup y)}$&
	    $[-1.0,1.0]$ & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0  \\ \hline
\end{tabular}
\end{center}
\end{table}

Table~\ref{table.intro.metrics.properties} shows how the four rule statistics are mathematically expressed.
Researchers have extensively studied what are the key properties associated with an arbitrary statistics $S$ (including the aforementioned statistics).
Next, eight of these properties will be discussed. The first three were introduced
by \cite{Piatetsky-Shapiro1991}.

\begin{description}
 \item[\textbf{P1}]: $S=0$ if $X$ and $y$ are statistically independent.
 \item[\textbf{P2}]: $S$ monotonically increases with $\mathbb{P}(X, y)$, given that both $\mathbb{P}(X)$ and
 $\mathbb{P}(y)$ remain the same.
 \item[\textbf{P3}]: $S$ monotonically decreases with $\mathbb{P}(X)$ or $\mathbb{P}(y)$, given that
$\mathbb{P}(X, y)$, $\mathbb{P}(X)$ or $\mathbb{P}(y)$ remain the same.
\end{description}

\begin{wraptable}[5]{r}{5.5cm}
\caption{Contingency matrix, $\bm{M}$.}
\label{table.intro.matrixcontigence}
\centering
\begin{tabular}{|c|c|}\hline
$\mathbb{P}(X, y)$ & $\mathbb{P}(X, \overline{y})$\\ \hline
$\mathbb{P}(\overline{X}, y)$ & $\mathbb{P}(\overline{X}, \overline{y})$\\ \hline
\end{tabular}
\end{wraptable}
The next five properties were introduced by~\cite{measure1}, and are
described using the contingency
matrix $\bm{M}$ showed in Table \ref{table.intro.matrixcontigence}.
Each statistics is represented by a function $O$ that maps the matrix $\bm{M}$ to a scalar value. For example, the confidence statistics is given by the function $\frac{M_{1,1}}{M_{1,1} + M_{1,2}}$, while the support statistics is given by the function $M_{1,1}$.

\begin{description}
\item[\textbf{P4}] [Symmetry Under Variable Permutation]: $S$ is symmetric under variable permutation if 
$\theta(X\xrightarrow{}y) = \theta(y\xrightarrow{}X)$, that is, $O(\bm{M}^{T}) = O(\bm{M})$ for every matrices $\bm{M}$.

\item[\textbf{P5}] [Row/Column Scaling Invariance]: let $\bm{R} = \bm{C} = \left[ \begin{array}{cc} k_1 & 0 \\ 0 & k_2 \end{array} \right]$ be two matrices, where $k_1$ and $k_2$ are positive constants.
The product $\bm{R} \times \bm{M}$ corresponds to scaling the first row of $\bm{M}$ by $k_1$ and the second by $k_2$, while  $\bm{M} \times \bm{C}$
corresponds to scaling the first column of  $\bm{M}$ by $k_1$ and the second by $k_2$. $S$ is row/column scaling invariant if
$O(\bm{R} \times \bm{M}) = O(\bm{M} \times \bm{C}) = O(\bm{M})$ for every matrices $\bm{M}$.

\item[\textbf{P6}] [Antisymmetry Under Row/Column Permutation]: let $\bm{V} = \left[\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array}\right]$ be a matrix. $S$ is
antisymmetric under row permutation if  $O(\bm{V} \times \bm{M}) = -O(\bm{M})$ and antisymmetric under column permutation if $O(\bm{M} \times \bm{V}) = -O(\bm{M})$
for every matrices $\bm{M}$.
 
\item[\textbf{P7}] [Inversion Invariance]: in this case, inversion is to swap the rows and columns. Let $\bm{V} = \left[\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array}\right]$. $S$ is
is invariant under inversion if $O(  \bm{V} \times \bm{M} \times \bm{V}) = O(\bm{M})$ for every matrices $\bm{M}$.

\item[\textbf{P8}] [Null Invariance]: $S$ is null invariant if $O(\bm{M} + \bm{C}) = O(\bm{M})$, where
$\bm{C} = \left[\begin{array}{cc} 0 & 0 \\ 0 & k \end{array}\right]$ and $k$ a positive constant. This
operation corresponds to add examples that do not contain $X$ neither $y$ in the training-set.
\end{description}

Table~\ref{table.intro.metrics.properties} also shows the properties expressed by each rule statistics. It is worth noting that no statistics shows all properties, and some properties are expressed by only one statistics. Next we define the rule-utility space.

\vspace{0.2cm}
\noindent{\bf Definition 6:}
{\em Given an example $x$ in the test-set, each rule in $\mathcal{R}_x$ is associated with a point in a $n-$dimensional
scattergram, which we define as the rule-utility space. In this case, a
point is represented as $[m_1, \ldots, m_n]$, where each coordinate $m_i$ corresponds to
a rule statistics.}

\subsection{Condensed Representations}

The condensed representation principle is to compute a rule-set $\mathcal{C}_x\subseteq\mathcal{R}_x$, such that rules in $\mathcal{C}_x$ enable to regenerate all rules in $\mathcal{R}_x$. Maximal rules~\cite{genmax}, for instance, form a condensed representation, since all rules in $\mathcal{R}_x$ must be subset of a maximal rule. However, an additional pass in the training-set is necessary in order to gather rule statistics. Next we define an alternate condensed representation for which no additional pass in the training-set is necessary.

\vspace{0.2cm}
\noindent{\bf Definition 7:}
{\em A rule $\{X\to y\}\in\mathcal{R}_x$ is closed if there exists no other rule $\{C\to y\}\in\mathcal{R}_x$ such that $X\subseteq C$ and both rules $\{X\to y\}$ and $\{C\to y\}$ have the same support value.}

Closed rules~\cite{dci} are appropriate for building associative classifiers, since they do not carry redundant information $-$ there are no two rules in the classifier that are subset-related and explain exactly the same subset of the training-set.

\subsection{Pareto Efficiency}
\label{referencial.pareto}

The Pareto Efficiency is said to occur when it is impossible to make one party better off without making someone worse off. It is a state in which ``resources'' are distributed in the most efficient way.
Pareto Efficiency has broad implications in Economics, particularly in game theory. Unlike the predicted logical outcome of a prisoner's dilemma (participants choose selfishly and do not achieve the best possible outcome), if a state is Pareto Efficient, individuals are maximizing their utility.

In our particular context, participants are rules in $\mathcal{R}_x$, while resources are the statistics within each rule. We are interested in finding a subset of $\mathcal{R}_x$, denoted as $\mathcal{R}_{x}^{*}$, which is composed of rules satisfying the Pareto Efficiency condition. More specifically, $\mathcal{R}^{*}_x$ is composed of rules lying in the Pareto frontier~\cite{Borzsonyi2001}
(also known as \textit{skyline} or \textit{maximal vector}~\cite{Godfrey2007}).

\vspace{0.2cm}
\noindent{\bf Definition 8:}
{\em Given the rule-utility space, its Pareto frontier is composed of rules that are not dominated by any other rule.}
\vspace{0.2cm}

Figure~\ref{fig:ex1} shows a 2-dimensional rule-utility space, where the dimensions are the support and confidence statistics and each point corresponds to a rule. The
dominance operator relates two rules in such a space, so that the result of the dominance
operation has two possibilities: (i) one rule dominates another or (ii) the two
rules do not dominate each other.
Rules that are not dominated by any other rule compose the Pareto frontier.
Stripping off all rules lying in the Pareto frontier, and building another frontier from the
remaining rules reveals a partial ordering between the rules and successive Pareto frontiers, as shown in Figure~\ref{fig:ex1}.

\begin{figure}[tb]
  \centering
   \includegraphics[width=0.75\textwidth]{front.jpg}
  \caption{Rule-Utility space and successive Pareto frontiers.}
  \label{fig:ex1}
\end{figure}

If the data fits in memory, the best known algorithm for building Pareto frontiers is known as Block-Nested-Loops (BNL)~\cite{Borzsonyi2001}. Algorithm~\ref{alg.bnl} shows detailed steps of the BNL algorithm, which employs a window composed of non-dominated points that works as a self-organizing list in order to narrow down the number of dominance operations.
The best-case and average-case complexities for this algorithm are $O(|\mathcal{R}_x|\times n)$, and the worst-case complexity is $O(|\mathcal{R}_x|\times n^2)$, with $n$ as the number of dimensions (which in our case is a small constant).

\begin{algorithm}
  \caption{\textbf{BNL} Block-nested-loops}
  \label{alg.bnl}
  \begin{algorithmic}[1]
    \Require{Points (or rules) in $\mathcal{R}_x$}
    \Statex
     \State $window \gets \emptyset$
      \ForAll{points $r \in \mathcal{R}_x$}
	\State $notDominated \gets true$
        \ForAll{points $w \in window$}
	  \If{$r$ dominates $w$}
	    \State $window.remove(w)$
	  \ElsIf{$r$ is dominated by $w$}
	   \State $window.remove(w)$
	   \State $window.push\_front(w)$ \Comment self-organizing list
	   \State $notDominated \gets false$
	   \State \textbf{break}
	  \EndIf
        \EndFor
	  
	\If{$notDominated$}
	  \State $window.push\_back(r)$
	\EndIf

      \EndFor
      
      \Return{$window$} \Comment Pareto Frontier
     
  \end{algorithmic}
\end{algorithm}
