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

Since their invention of k-Nearest Neighbor (kNN) algorithms in 1967
(by Hart~\cite{Hart67}), many researchers have
explored intelligent {\em  instance selection methods (ISM)}
to address the drawbacks with kNN~\cite{Gates72,Hart68a,Dasarathy94,lot2010,
Aha91,Bezdek2001,Brighton2002,CHL03,Carrasco05,Chien06,García2008,Lumini06,Narayan06,OCM2007,
OCM2008,Raicharoen05,Riquelme03,Ritter75,Srisawat06,Tomek76,Veenman2005,Wilson72,wilson00,Olvera2010}.
These drawbacks include, (a)~the high computation
costs caused by the need for each test sample to find the distance
between it and each training sample (b)~the storage required
to hold the
entire dataset in memory; 
(c)~the effects of outliers which can negatively affect the accuracy of the classifier;
(d)~the negative effect of data sets with non-separable and/or
overlapping classes; and (e)~the effects on noise on kNN inference \cite{Li08, wilson00}.
Noise can lead to {\em brittleness} i.e. when random changes to an instance leads
to a major change in the inferences drawn from those instances.

Brittleness occurs from
trying to reason in noisy regions where there are many competing classes.
For example, \fig{intropic} shows a test instance 
at position {\em length=6.1}
and {\em width=2.95} within the 
the iris data set~\cite{Frank+Asuncion:2010}.
There are two competing classes (green and blue)
around the test instance.
Minor changes to
 the test instance's position (due to noise)
would change the predictions made
by a 1NN algorithm.


A standard solution to these drawbacks is some {\em instance selection}
algorithm that replaces all the data with X\% fewer instances.
Instance selection can mitigate the effects of noise and reduce brittleness.
The bottom of \fig{intropic} shows the iris instances selected
by CLIFF (the instance selection algorithm proposed in this paper).
CLIFF has 
reduced the confusion  about the class of the $versicolor$
test instance by increasing its distance from instances of different classes,
thereby reducing $brittleness$.
Observe how the test instance can now move up or left or down {\em without} changing its 
nearest neighbor classification

\begin{figure}[!t]
\begin{center}
\includegraphics[width=2.5in]{ir2fss}
\includegraphics[width=2.5in]{ir2fssaf}      
\end{center}
    \caption{Illustration of brittleness in the iris data-set. Before using the instance selector CLIFF (described later in this paper) the classes versicolor and virginica show intermingling (brittleness). After using CLIFF, brittleness is reduced.}
    \label{fig:intropic}
\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}
This paper recommends CLIFF for instance selection.
This a new algorithm (previously unreported) that runs in linear time. %; that  is independent
%of the order of the training set; and avoids overfitting\footnote{fayola- you have not introduced these as problems}.
 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 algorithm called BORE (Best Or
Rest) \cite{jalali08}, that 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 that adheres to
some or all the criteria is or are selected.  
Like any other ISM, if a kNN algorithm runs
in the reduced space, then CLIFF will reduce all of the following: (a) the computational cost of finding the distances
of test instances to training instances; (b) the storage cost of holding the instances in memory;
(c) the effects of outliers; (d) the negative effect of data sets with non-separable regions.



\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%\footnote{fayola- you have not introduced these as problems}
/model for the evaluation of trace forensic evidence. This is our main motivation for creating CLIFF. Here we address the issues put forward by \cite{09NAS}, that no forensic method has been rigorously shown to have the capacity to {\em consistently}, and with a high {\em degree of certainty}, demonstrate a connection between evidence and a specific individual or source. Since we view these issues as being caused by brittleness, CLIFF is a promising tool to reduce or eliminate them.

\begin{comment}
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.
\end{comment}

To determine if CLIFF is a viable instance selector, our research is guided by the following research questions:

\begin{itemize}
%\item RQ1: Is CLIFF viable as an instance selector for kNN? %\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 RQ1: Does CLIFF reduce the storage requirements?
\item RQ2: Is CLIFF better at reducing brittleness than other ISM?
\item RQ3: Is CLIFF more tolerant to noise than other ISM?
\item RQ4: Is the performance of CLIFF comparable or better than other ISM?
\end{itemize}

The paper is organized as follows: The next section we discuss fundamental concepts and definitions. Section \ref{section:related} provides a survey of ISM. 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}.
