\section{Introduction}
\label{section:introduction}

\begin{comment}
Classification ...
Nearest neighbor ...
drawbacks... add brittleness
solution - instance selectors
 maintains comparable results
 removes drawbacks
in this work we propose CLIFF - instance selector
evaluations
case study
paper is organized as follows
\end{comment}

Since the creation of the Nearest Neighbor (NN) algorithm in 1967 (Hart \cite{Hart67}), a copious amount of Instance Selectors (IS) have appeared in order to suppress the drawbacks of Nearest Neighbor (NN) algorithms. These drawbacks include, 1) the high computation costs caused by the need for each test sample to find the distance between it and each training sample. 2) the storage requirement is large since the entire dataset needs to be stored in memory. 3) outliers which can negatively affect the accuracy of the classifer. 4) the negative effect of data sets with non-separable and/or overlapping classes and last, the low tolerance to noise. 

Unfortunately, to our knowledge, none have directly addressed the drawback of {\em brittleness}. Brittleness is a measure of whether a solution (predicted target class) comes from a region of similar solutions or from a region of dissimilar solutions. In other words, how far would a test instance have to move before a different target class is predicted. Our concern is that it would take only tiny changes in the data to cause this change. Take for example, the iris data-set \cite{Frank+Asuncion:2010} illustrated in \fig{intropic}. Here one can clearly see the importance of evaluating the brittleness of IS. As shown, before using the instance selector CLIFF (decribed later in this paper) the classes $versicolor$ and $virginica$ obviously show severe intermingling. Also, the versicolor test instance represented by the purple square does not have to move very far before it can change its predicted target class to $virginica$. On the other hand, after using CLIFF, a subset of instances is selected. This removes any confusion for the $versicolor$ test instance by increasing its distance from instances with the $virginica$ class thereby reducing $brittleness$.



\begin{figure*}[ht!]
  \begin{center}
  \scalebox{0.7}{
    \begin{tabular}{l}
      \resizebox{100mm}{!}{\includegraphics{ir2fss}}
      \resizebox{100mm}{!}{\includegraphics{ir2fssaf}}      
    \end{tabular}}
    \caption{Illustration of brittleness in the iris data-set. Before using the instance selector CLIFF (decribed later in this paper) the classes versicolor and virginica show intermingling (brittleness). After using CLIFF, brittleness is reduced.}
    \label{fig:intropic}
  \end{center}
\end{figure*} 


\begin{comment}
To solve these issues, PLS are used. Their main purpose is to reduce a training set via various selection and/or creation methods to produce \emph{good prototypes} (\fig{selection}). \emph{Good} here meaning that the prototypes are a good representation of the original training data set such that they maintain comparable or improved performance of a nearest neighbour classifier while simultaneously eliminating the effects of the drawbacks mentioned previously.

A review of the literature on prototype learning for this thesis has yielded at least 40 PLS each indicating with experimental proof that their particular design is comparable or better than the standard schemes; published surveys of PLS can be found in \cite{Bezdek2000, Bezdek2001, Kim2003, lot2010}. However many of these schemes suffer from at least one of the following disadvantages:

\bi
\item computationally expensive
\item order effects (where the resulting prototypes are unreasonably affected by the order of the original training set)
\item overfitting
\ei

The goal of this work is not to be unduly critical of the PLS which may succumb to any of the above disadvantages (particularly since many of them have proven to be successful), but rather to present a novel approach to this field of study which overcomes these disadvantages to report little or no loss in recognition of NNC.
\end{comment}
Therefore, this paper introduces CLIFF, an instance selector designed specifically to reduce brittleness when necessary while also addressing the other drawbacks of NN algorithms. CLIFF runs in linear time, is independent of the order of the training set and avoids overfitting. A novel feature of CLIFF is that instead of either removing or adding (un)qualified instances from/to a list based on misclassification or clustering, a criterion is generated for each target class. These criteria are created using a ranking algoritm called BORE (Best Or Rest) \cite{jalali08}, which  finds the value for each attribute which best represents the specific target class i.e. have the highest ranks. Any of the instances in the training set which adheres to some or all the criteria is or are selected. 
\begin{comment}
Using this structure the percentage reduction of the training set is directly related to the number of constraints from the criteria used on the instance selection process, in that the more constraints used the lower the percentage reduction. 

In this work, to be sure that each class is represented in the final list of prototypes, instances are selected using one contraint at a time until the prototype list is reduced as much a possible without being empty.
\end{comment}

After describing the design and operation of CLIFF, its performance is demonstrated by evaluating it using cross-validation experiments with the wide variety of standard data sets from the UCI repository \cite{Frank+Asuncion:2010}. 

Next we describe how CLIFF can be used as part of a tool/model for the evaluation of trace forensic evidence. The principal goal of forensic evaluation models is to check that evidence found at a crime scene is (dis)similar to evidence found on a suspect. In our studies of forensic models for evaluation particularly in the sub-field of glass forensics, we conjecture that many of these models succumb to the following flaws:

\be
\item A tiny error(s) in the collection of data;
\item Inappropriate statistical assumptions, such as assuming that the distributions of refractive indices of glass collected at a crime scene or a suspect obeys the properties of a normal distribution; 
\item and the use of measured parameters from surveys to calculate the \emph{frequency of occurrence} of trace evidence in a population.
\ee

In this work we show that CLIFF plays an effective role in the evaluation of forensic trace evidence.

Our research is guided by the following research questions:

\begin{itemize}
\item Is CLIFF viable as an IS for NN? %\newline
%The goal here is to see if the performance of CLIFF is comparable or better than the plain k nearest neighbor (KNN) algorithm and three(3) other IS. So in our first experiment we compare the performance of predicting the target class using the entire training set to using only the instance selected by CLIFF and the other IS.
\item Is CLIFF better at reducing brittleness than other IS?
\item Is CLIFF more tolerant to noise than other IS?
\end{itemize}

The paper is organized as follows: The next section provides a survey of IS over the years. In Section \ref{section:related}, we discuss fundamental concepts and definition. Section \ref{section:cliff} describes the design and operation of CLIFF. This is followed by a detailed description of the experimental procedure followed to analyze standard data-sets using CLIFF in Section \ref{section:assess}. Section \ref{section:forensics} examines a case study in which CLIFF is used as part of a forensic interpretation model to reduce the \emph{brittleness} of published forensic models. Finally, we conclude the paper and discuss future work in Section \ref{section:conclusion}.
