\section{CLIFF Design and Operation}
\label{section:cliff}
As discussed in Section \ref{section:bkg}, some instance selectors can be a viable solution to $brittleness$. In this section, we present CLIFF, a novel instance selector base on a feature selection technique called Best Or Rest (BORE) \cite{jalali08}. As we will show later in Section \ref{section:assess}, CLIFF reduces brittleness significantly better than the other IS used in this study. The IS discussed in Section \ref{section:related} tend to be based on misclassification or clustering. Rarely does one come across a instance selector which considers the idea that {\em some attribute values can be significant in selecting instances for each class}. CLIFF was born from this idea, in that for an instance to be selected, its attribute values must adhere to the selection criteria for a particular class. The following section explains the design of CLIFF in detail starting with the core of CLIFF - BORE - and ending with CLIFF's time complexity.

Before we discuss the details of CLIFF, it is important to note that CLIFF is designed for discrete data-sets. So, if a data-set contains attributes whose values are numeric, the values are binned using the Fayyad and Irani supervised discretizing algorithm \cite{Fayyad1992}. This algorithm first sorts the instances on the attribute of interest, then it looks for potential break points where the class labels change. Each of these break points are then evaluated using info gain and the one with the maximum value is used. This process is then repeated recursively on both subsets until subsets are pure or a stopping criterion is met.

\subsection{BORE}
\label{section:bore}

The core of CLIFF is to find for a particular attribute values more likely to be present for a particular class. To find these values, CLIFF uses BORE. First we assume that the target class is divided into one class as $best$ and the other classes as $rest$ \cite{jalali08}. This makes it easy to find the attribute values which have a high probability of belonging to the current \emph{best} class using Bayes theorem. The theorem uses evidence $E$ and a prior probability $P(H)$ for hypothesis \emph{H $\in$ $\{$best, rest$\}$}, to calculate a posteriori probability \emph{P(H$|$E) = P(E$|$H) $\times$ P(H) / P(E)}. When applying the theorem, likelihoods are computed from observed frequencies, then normalized to create probabilities: this normalization cancels out $P(E)$ in Bayes theorem (see \eq{one1}). 


{\em Let likelihood = like}
\begin{equation}
P(best|E) = \frac{like(best|E)}{like(best|E) + like(rest|E)} 
\label{eq:one1}
\end{equation}

Unfortunately, one problem was found using the theorem. According to \cite{jalali08}, Bayes theorem is a poor ranking heuristic since it is distracted by low frequency evidence. To alleviate this problem the support measure was introduced. Its purpose was to increase as the frequency of a value increases i.e. like(best$|$E) is a valid support measure hence \eq{one}.
 

\begin{equation}
P(best|E) * support(best|E) = \frac{like(best|E)^2}{like(best|E) + like(rest|E)} 
\label{eq:one}
\end{equation}

So in this work, each attribute value is ranked according to \eq{one}. Once ranked, the critical value for each attribute are extracted (those with the highest ranks) and used as the criterion for selecting instances from the current $best$ class. The whole process is repeated using a different class as $best$ and all the others (including the previous $best$ class) as $rest$. When a criterion for each class has been found the process ends. \fig{sbbra} shows the pseudocode for ranking each value of an attribute for an entire training data-set. The parameters include: $a$, the list of attributes from the data-set; $best$, instances with the current best class; and $rest$, instances with classes not including the best class.

\begin{figure}[ht!]
\renewcommand{\baselinestretch}{1}
\begin{algorithmic} \footnotesize
\STATE freq = frequency
\STATE like = likelihood
\STATE \textit{$p_{best}$} = Probability of value in best
\STATE \textit{$p_{rest}$} = Probability of value in rest

\STATE begin initialize a, best, rest, $list=\emptyset$

\FORALL {~attributes in a} \DO
	\FORALL{~values in attribute} \DO
		\STATE   \textit{$p_{best}$} = \textit{$\left|{best}\right|$} / \textit{$\left|{data}\right|$} 
		\STATE   \textit{$p_{rest}$} = $\left|{rest}\right|$ / $\left|{data}\right|$
		\STATE   $freq(value|best)$ = $\left|{value in best}\right|$ / $\left|{best}\right|$
		\STATE   $freq(value|rest)$ = $\left|{value in rest}\right|$ / $\left|{rest}\right|$
		\STATE   $like(best|value)$ = $freq(value|best)$ x \textit{$p_{best}$}
		\STATE   $like(rest|value)$ = $freq(value|rest)$ x \textit{$p_{rest}$}
		\STATE   $like_{br}$ = $like(best|value)$ + $like(rest|value)$
		\STATE   $rank$ = $like(best|value)^2$ / $like_{br}$
		\STATE   {\em add [value, rank] to list}
	\ENDFOR
\ENDFOR
\STATE return list
\end{algorithmic}
\caption{Pseudo code for BORE}\label{fig:sbbra}
\end{figure}


\subsection{Using Criteria for Instance Selection}

%As discuss in Section \ref{subsection:sc}, 
A criterion is made up of a critical value for each attribute. Hence, once the criterion for each class has been found, the question remains: How do we use it to select instances? There is the possibility that using the entire criterion for each class could result in zero instances being selected. To avoid this we use one critical value at a time for instance selection until just before there are no more instances left. Furthermore, since there is also the possibility that only a few of the critical values will be used, another problem considered is the order in which the critical values are used. This problem is solved by sorting them in descending order according to their rank values. \fig{isc} shows the pseudocode for the process. We start with a list of critical values sorted according to their rank values (high to low). For each iteration, the current list of instances is reduced to only those instances which contain $c$ for a particular attribute. 


\begin{figure}[ht!]
\renewcommand{\baselinestretch}{1}
\center
\begin{algorithmic} \footnotesize

\STATE {\em criterion = list of critical values}
\STATE {\em begin initialize current $=$ instances in class , previous $=$ $\emptyset$}

\REPEAT 
	\STATE previous = current
	\WHILE {~c in criterion}
    		\STATE current = instances with c
		\IF {~current = $\emptyset$}
			\STATE current = previous
		\ENDIF
	\ENDWHILE
\UNTIL (current = previous)
  
\STATE {\em return current}
\end{algorithmic}
\caption{Instance Selection Method used in CLIFF}
\label{fig:isc}
\end{figure} 


\subsection{CLIFF: A Simple Example}

\begin{figure}[ht!]
\begin{center}
\scalebox{0.9}{
\begin{tabular}{l*{5}{l}r}
\#  & forecast & temp & humidty & windy & play \\
\hline
1. &	sunny &    hot &  high  &   FALSE & no \\
2. &	sunny  &   hot &  high  &   TRUE  & no \\
3. &	overcast & hot  & high   &  FALSE & yes \\
4. &	rainy  &   mild & high  &   FALSE & yes \\
5. &	rainy  &   cool & normal &  FALSE & yes \\
6. &	rainy   &  cool & normal &  TRUE &  no \\
7. &	overcast & cool & normal &  TRUE &  yes \\
8. &	sunny  &   mild & high  &   FALSE & no \\
9. &	sunny   &  cool & normal &  FALSE & yes \\
10. &	rainy  &   mild & normal &  FALSE & yes \\
11. &	sunny  &   mild & normal &  TRUE &  yes \\
12. &	overcast & mild & high    & TRUE &  yes \\
13. &	overcast & hot &  normal &  FALSE & yes \\
14. &	rainy  &   mild & high  &   TRUE &  no  \\
\end{tabular}}
\caption{A log of some golf-playing behavior}\label{fig:golf}
\end{center}
\end{figure}

For this example we use the $weather$ data-set shown in \fig{golf}. This data-set contains four(4) attributes that report on the forecast (sunny, overcast and rainy), temperature (hot, mild and cool), humidity (high and normal) and whether or not the day is windy (true or false). Of the 14 days observed, on nine(9) of them, golf was played and on the remaining five(5) days, no golf was played. 

To create a criterion for each class in this data-set, we first divide it into $best$ and $rest$. For this example, let us say that all the instances with the $yes$ class are $best$ while the others are $rest$. Next, we find the ranks of each value in each attribute. Let K = 14 (total number of instances), $\left|{best}\right|$ = 9 and $\left|{rest}\right|$ = 5. \fig{rank1} shows how to find the rank of $sunny$ in forecast.

\begin{figure}[ht!]
\renewcommand{\baselinestretch}{1}
\begin{algorithmic} \footnotesize
\STATE $E$ $=$ $sunny$
\STATE \textit{$p_{best}$} $=$ $\frac{9}{14}$
\STATE \textit{$p_{rest}$} $=$ $\frac{5}{14}$
\STATE $freq(E|best)$ $=$ $\frac{2}{9}$
\STATE $freq(E|rest)$ $=$ $\frac{3}{5}$
\STATE $like(best|E)$ $=$ $\frac{2}{9}$ $\times$ $\frac{9}{14}$ $=$ $0.14$
\STATE $like(rest|E)$ $=$ $\frac{3}{5}$ $\times$ $\frac{5}{14}$ $=$ $0.21$
\STATE $P(best|E)$ $=$ $\frac{0.14}{0.14 + 0.21}$ $=$ $0.40$

\STATE $P(best|E)$ * $support(best|E)$ $=$ $\frac{0.14^2}{0.14 + 0.21}$ $=$ $0.06$
\end{algorithmic}
\caption{Finding the rank of $sunny$}
\label{fig:rank1}
\end{figure} 

Once the ranks are found for each value for each attribute, the criterion is created using the highest ranked values in each attribute to create \{attribute, value\} pairs. For this example we will use the following as the criterion for the $yes$ class with te assumption that it is sorted by the highest to lowest ranks: 

\begin{figure}[ht!]
\scalebox{0.7}{
\begin{tabular}{l*{3}{c}r}
\{\{forecast, rainy\} & \{temp, mild\} & \{humidity, high\} & \{windy, FALSE\}\} \\
\end{tabular}}
\end{figure}

With this criterion, after applying \{forecast, rainy\}, we are left with three instances (4, 5 and 10):

\begin{figure}[ht!]
\begin{center}
\scalebox{0.9}{
\begin{tabular}{l*{5}{c}r}
4. & rainy  &   mild & high  &   FALSE & yes \\
5. & rainy   &  cool & normal  & FALSE & yes \\
10. & rainy   &  mild & normal  & FALSE & yes \\
\end{tabular}}
\end{center}
\end{figure}

This is about 33\% of the data in the $yes$ class. The second pair \{temp, mild\} in the criterion is used on the three instances. This yields two(2) instances (4 and 10) reducing the data in the $yes$ class to about 22\%:

\begin{figure}[ht!]
\begin{center}
\scalebox{0.9}{
\begin{tabular}{l*{5}{c}r}
4. & rainy  &   mild & high  &   FALSE & yes \\
10. & rainy   &  mild & normal  & FALSE & yes \\
\end{tabular}}
\end{center}
\end{figure}

Further applying the next attribute value pair, \{humidity, high\}, to the remaining two instances results in zero instances. Therefore the process stops here and the previous result of the two instances is returned.

\subsection{CLIFF: Time Complexity}
\label{section:time}
Intuitively, time complexity for CLIFF can be considered in terms of 1) ranking each value in each attribute, a $O(m)$ operation where m represents attributes, 2) finding the criteria for each class, a \emph{O(m) + O(k)} operation where k represents the class, and 3) selecting instances from each class using the criteria a $O(n)$ operation where n represents the number of instances.

Assuming that \emph{n $>$ m $>$ k} (which is the case for all data-sets used in this study), this process yields a complexity of $O(m)$ + \emph{O(m) + O(k)} + $O(n)$ which reduces to $O(n)$.
