\section{Related Work}
\label{section:related}

%Find papers with noise experiment results.
%In Section 1, the optimal goal of IS as a solution to the drawbacks of NNC is highlighted. To continue this discussion, in this section we present a brief survey of IS starting with one of the earliest - Hart's 1968 Condensed Nearest Neighbor (CNN) \cite{Hart68a} to a method published in 2010. The reader will see that since 1968, researchers in this field have created IS which fit into at least one of two(2) categories: 1) instance selection and 2) instance abstraction.

%\subsection{Terminology}


%\subsection{Instance Selection for Nearest Neighbor Classifiers}

Research in instance selection is an active field of study \cite{Devi2002, Bezdek2001, Dasarathy94, Li2009, Bezdek98, Cano2005, Garain2008, Veenman2005, García2008}. Instance selection involves selecting a subset of instances from the original training set. Using what Dasarathy \cite{Dasarathy94} terms as \emph{edit rules}, instance selection can take place in four(4) different ways.

\be
\item incremental (e.g. Condensed Nearest Neighbor (CNN) \cite{Hart68a});
\item decremental (e.g. Reduced Nearest Neighbor (RNN) \cite{Gates72});
\item a combination of 1 and 2;
\item border points, non-border points or central points.
\ee

In the following sections, we review IS which abide by 1, 2 and 4. However, before moving forward, in the interest of clarity, the following terminology are used throughout the remainder of this work: all data-sets refers to supervised data-sets and each data-set consists of rows and columns where each row is referred to as an instance and each column is called an attribute except for the last column which is the target class; the selected instances found after applying an instance selector is refered to as a {\em training subset};
\begin{comment}a prototype is an instance selected or created to be part of the final reduced training set and \end{comment}
finally, consistency is defined as the ability of the final subset of instances to correctly classify the original training set.
%Instance abstraction involves creating prototypes by merging the instances in a training set according to pre-determined rules. For example, Chang \cite{Chang74} merges two instances if the have the same class, are closer to each other than any other instances and the result of merging does not degrade the performance of NNC. \fig{psw} shows the IS surveyed in this work.

\begin{comment}
\begin{figure*}[ht!]
\begin{center}
\begin{tabular}{| l@{~}|l@{~}| c@{~}| c@{~}|} \hline
Name & Abbreviation & Cite &  Type\\\hline
Condensed Nearest Neighbor & CNN & \cite{Hart68a} & Instance Selection \\ \hline
Reduced Nearest Neighbor & RNN & \cite{Gates72} & Instance Selection \\ \hline
Minimal Consistent Set & MCS & \cite{Dasarathy94} & Instance Selection \\ \hline
Prototype Selection by Clustering & PSC & \cite{lot2010} & Instance Selection \\ \hline
%The Chang and Modified Chang Algorithms & MCAs & \cite{Chang74, Bezdek98} & Instance Abstraction \\ \hline
%Learning Vector Quantization & LVQ & \cite{Kohonen90} & Instance Abstraction \\ \hline
\end{tabular}
\end{center}
\caption{IS surveyed in this work}\label{fig:psw}
\end{figure*}
\end{comment}
%\subsection{Instance Selection}

\subsection{Condensed Nearest Neighbor (CNN)}
Different IS use various rules to determine which instance in a training set is worthy of being selected for the training subset. Each also tend to focus on specific goals such as increasing speed or performance or storage reduction. CNN \cite{Hart68a} uses a \emph{incremental} strategy where it initializes a random subset of prototypes and adds to the list. Hart's goal with CNN focused on storage reduction with the aim to create a minimal consistent set, i.e. a smallest subset of the complete set that also classifies all the original instances correctly. 

%\fig{cnn} shows the pseudo-code for 
CNN begins by randomly selecting one instance from each target class and stores them as prototypes in a list. These prototypes are then used to classify (using the 1NN rule) the instances in the training set. If any of theses instances are misclassified they are added to the prototype list. This process is repeated until the prototype list can no longer be increased.

Admittedly, although a reduction in the training set with consistency was accomplished, Hart did not achieve his goal of a minimal consistent set with CNN. CNN also suffers with the following disadvantages:

\bi
\item sensitive to the initial order of input data
\item sensitive to noise which can degrade performance
\ei

\begin{comment}
\begin{figure}[h!]
\small
\begin{center}
\begin{tabular}{ p{8cm} }
\hline
\begin{verbatim}
INITIAL_PROTOTYPES = [RANDOM(FROM EACH TARGET CLASS)]
PREV = []
CUR = [INITIAL_PROTOTYPES]

REPEAT UNTIL PREV = CUR
  MISCLASSIFIED = classify TRAIN and 
                  RETURN MISCLASSIFIED 
                  INSTANCES
  PREV = CUR
  CUR = MISCLASSIFIED + CUR
END	
\end{verbatim}
 \\ \hline
    \end{tabular}
\end{center}
\caption{Pseudo-code for CNN}\label{fig:cnn}
\end{figure} 
\end{comment}
\subsection{Reduced Nearest Neighbor (RNN)}
RNN \cite{Gates72} takes an opposite approach to CNN. Its strategy is \emph{decremental}. So rather than start with a subset of the training set as CNN does, RNN uses the entire training set as initial prototypes and reduces the list. In the end, it is computationally more expensive than CNN, but always produces a subset of a CNN result.

The algorithm begins by setting the initial prototypes as the entire training set. From here, a prototype is removed if and only if its removal does not cause the misclassification of any instance in the training set. This procedure stops when no more prototypes can be removed from the prototype list. %\fig{rnn} shows the pseudo-code for RNN.

\begin{comment}
\begin{figure}[h!]
\small
\begin{center}
\begin{tabular}{ p{8cm} }
\hline
\begin{verbatim}
PREV = []
CUR = [TRAIN]
REPEAT UNTIL PREV = CUR
  PREV = CUR
  IF (CUR - (FIRST CUR)) cause 
  Misclassification of TRAIN
    CUR = CUR
    CUR = (REST CUR)
  END	
END	
\end{verbatim}
 \\ \hline
    \end{tabular}
\end{center}
\caption{Pseudo-code for RNN}\label{fig:rnn}
\end{figure}  
\end{comment}

\subsection{Minimal Consistent Set (MCS)}
The goal of the MCS is to achieve what Hart \cite{Hart68a} failed to achieve with CNN: a minimal consistent set. MCS uses a voting strategy which favors instances with the greatest number of like instances (in other words, those with the same class) closer to them than unlike instances.

As explained in \cite{Dasarathy94}, MCS takes a \emph{decremental} approach as with RNN where at first the entire training set is seen as the initial prototypes. Then for each of these prototypes the distance of its nearest unlike neighbor (NUN), i.e. nearest neighbor with a different class, is found. Next, all nearest like neighbors (NLN) of this prototype whose distances from the prototype are less than that of the NUN are stored. Each of these NLN are counted as a vote toward the prototype for candidacy as a final prototype. The prototype with the most votes is then designated as a candidate and all NLN who contributed to the vote are removed from candidacy consideration as well as from the voting lists of other prototypes.

With the votes now updated, the process is repeated by designating the prototype who now has the most votes as a candidate. This process continues until the list can no longer be reduced. Further, since the goal of MCS is to find the minimal consistent set, the entire strategy is iterative in that the reduced list is now used as input for the next iteration starting with finding the distance of NUN for each prototype. %\fig{mcs1} shows the pseudo-code for MCS.

\begin{comment}
\begin{figure}[h!]
\small
\begin{center}
\begin{tabular}{ p{8cm} }
\hline
\begin{verbatim}
PREV = []
CUR = [TRAIN]
P* = []   \\ CANDIDATE PROTOTYPE
REPEAT UNTIL PREV = CUR
 PREV = CUR
 CUR = MCS(CUR)
END
MCS(CUR)
REPEAT UNTIL PREV = CUR
  FOR EACH c IN CUR
   DISTANCE_NUN = DISTANCE(c, NUN)
   VOTER_LIST = NLN
   VOTES = COUNT(VOTER_LIST)
  END
  P* = NLN with MAX(VOTES)
  CUR = CUR - P*(VOTER_LIST)
END
\end{verbatim}
 \\ \hline
    \end{tabular}
\end{center}
\caption{Pseudo-code for MCS}\label{fig:mcs1}
\end{figure}  
\end{comment}

\subsection{Prototype Selection by Clustering (PSC)}
Unlike the previous methods, PSC is uses clusters to aid in instance selection. Based on the argument that ``...in a training set interior prototypes can be removed with little effect on classification accuracy; and they also argue that border prototypes are critical for classification since they provide relevant information for preserving discrimination between classes" \cite{lot2010}, PSC selects instances which are border instances and also some internal instances. 

As explained in \cite{lot2010}, PSC begins by dividing the training data into regions using a clustering algorithm. Although $Cmeans$ is used in their work, it is made clear that any clustering method can be used in its place and so in our experiments for this work, $Kmeans$ is our algorithm of choice. 

After clustering, the internal instances are found. This is done by first finding the homogeneous clusters (all instances in the cluster have the same target class). Once identified, the instance which is nearest to the centroid of each cluster is selected for the training subset.

Now, to find the border instances, those clusters which are non-homogeneous are identified. Next, all instances with the majority target class are found and the border instances for this class are those closest to instances of a different target class(es). This is true for instances of each class. %\fig{psc} shows the pseudo-code for PSC.

\subsection{More IS}

The above set of IS is obviously a sparse sample in the field of instance selection. A recent review of instance selection methods presented by \cite{Olvera2010}, placed IS in two categories, 1) Wrapper and 2) Filter. According to \cite{Olvera2010}, {\em wrapper methods} are those where the selection criterion is based on the accuracy obtained by a classifier, while {\em filter methods} are those where the classifier is not necessary. However, the authors were not explicitly clear about the time complexity of these IS except to state that the filter methods have smaller runtimes than wrapper methods \cite{Olvera2010}. %This may be due to the fact that most IS were created to reduce storage requirements and improve the accuracy of NN without regard to their computational cost. 
Therefore, in \fig{lot-tab}, we have included the published time complexities of some of the IS studied in \cite{Olvera2010}. As shown, most IS operate in polynomial time. Additionally, even the Fast Condensed NN (FCNN) \cite{FCNN07} (not shown in \fig{lot-tab}), can only claim to have a quadratic time complexity.

With this issue of time complexity in mind, in our work (Section \ref{section:cliff}), we propose CLIFF, novel instance selection method which runs in linear time. We also claim to the best of our knowledge that CLIFF is the first instance selector to show $O(n)$ time complexity.

%This is clear in some wrapper methods in \fig{lot-tab}, where some of the time complexities are clearly polynomial. 

%This may be because most of the wrapper methods in \fig{lot-tab} are based on misclassification which can cause these algorithms to have polynomial runtimes. According to \cite{wilson00}, the SNN algorithm takes appoximately O($mn^2$ + $n^3$), while most other instance selectors surveyed in that work had a runtime of O($mn^2$). The surveyed algorithms included DROP, IB, All-kNN, CNN, SNN, ENN and RNN.



%In contrast, since filter methods are mainly based on clustering and search algorithms causing smaller runtimes.

\begin{figure*}
\begin{center}
\scalebox{0.7}{
\begin{tabular}{ | l | l | p{7cm} | l |}
\hline
\multicolumn{3}{c}{Wrapper Methods} \\ \hline
Methods & Based on & Time Complexity& Reference\\ \hline
CNN (Condensed Nearest Neighbor)& Misclassification& $O(dn^3)$, where $d$ is the number of dimensions, $|D|$ and $n$ is the cardinality of the training set $|T|$ & \cite{Hart68a} \\ 
& & & \\
SNN (Selective Nearest Neighbor)& Misclassification& $O(dn^2$ + $n^3)$, according to \cite{wilson00} , denotation same as CNN& \cite{Ritter75}\\ 
& & & \\
%GCNN (Generalized CNN)& Misclassification, absorption& Requires more training time than CNN & \cite{Chien06}\\ 
ENN (Edited Nearest Neighbor)& Misclassification &$O(d^3n^{[d/2]}$ $ln$ n$)$, denotation same as CNN & \cite{Wilson72}\\ 
& & & \\
All k-NN & Misclassification & "...higher than the original CNN algorithm" \cite{Raicharoen05} &\cite{Tomek76}\\
&&&\\
%Multiedit  & Misclassification & &\\
%IB (Instance Based)& Misclassification & &\cite{Aha91}\\ 
%DROP (Decremental Reduction Optimization Procedure)& Associates & &\cite{wilson00}\\
ICF (Iterative Case Filtering)& Reachable, Coverage & $O(2\times(\#Iteration)\times|DB|^2)$, according to \cite{Kriegel05}, where \#Iteration is the number of iterations and $|DB|$ is the size of the database. &\cite{Brighton2002}\\ 
&&& \\
%SV-kNNC (Support Vector kNN Clustering)& SVM, k-means & &\cite{Srisawat06}\\
%Evolutionary algorithms & Natural evolution & &\cite{Bezdek2001, CHL03}\\ 
%Memetic algorithms &Evolutionary algorithms, local search & &\cite{García2008}\\
CSA (Clonal Selection Algorithm) &Artificial immune systems & $O(n')$ + $O(kN)$, where k is the number of iterations required, $n'$ denotes the size of the condensed prototype set and N is the number of prototypes in the original set. &\cite{Garain2008}\\ %"time complexity of CSA-based approach is determined by two factors: (i) finding the memory element for proliferation and (ii) the number of iterations (say, k) required in the proliferation stage to find a properly stimulated clone. If n′ denotes the size of the immune memory (i.e., size of the condensed prototype set) then the time complexity can be represented by O(n') + O(kN) where N is the number of antigens (i.e., prototypes in the original set). Here also the second term, i.e., O(kN) dictates the overall time complexity."
& & & \\

%TS &Tabu search & $O(mn)$ &\\ %one iteration costs O(M). Thus, for k iterations, the cost becomes O(Mk).
BSE (Backward Sequential Edition) & Sequential search & $O(m^2J(m,F))$, where m denotes the prototypes, F - the attributes and $J(m,F)$ is the complexity of the evaluation function (classiﬁer) along the search. &\cite{OCM2007, Carrasco05}\\ %If we have m prototypes and F attributes, in each step, the complexity of removing the worst prototype in the training set is O(m) and at most m − 1 prototypes can be removed. Therefore the complexity of BSPS is O(m2 J(m, F )), where J(m, F ) is the complexity of the evaluation function (classiﬁer) along the search.
%RFOS (Restricted Floating Object Selection)& Sequential search & &\cite{OCM2007, Carrasco05}\\ 
\hline \hline
\multicolumn{3}{c}{Filter Methods} \\ \hline
POP (Pattern Ordered by Projections)& Weakness, border instances & $O(mn$log$n)$, where $m$ is the $|attributes|$ and $n$ = $|T|$ &\cite{Riquelme03}\\ 
&&& \\
POC-NN (Pair Opposite Class-NN)& Opposite class means, border instances & $O(dn^2m)$, for a 2-class system. Denotation same as CNN, and where $m$ is the number of iterations until the algorithm converges. &\cite{Raicharoen05}\\
&&& \\
kd-trees & kd-trees &$O(kN$log$m)$, where N $=$ number of data points in the original data-set and m $=$ number of leaf nodes &\cite{Narayan06}\\
%GCM (Generalized-Modified Chang Algorithm)& Clustering & &\\
%NSB (Nearest Sub-class Classifier)& Clustering & &\cite{Veenman2005}\\ 
%CLU (Clustering)& Clustering, interior instances & &\cite{Lumini06} \\
%OSC (Object Selection by Clustering)& Clustering, border and interior instances & &\\
%WP (Weighing Prototypes)& Instance weight & &\\
%PSR (Prototype Selection by Relevance)& Instance relevance & Runtimes are significantly better than DROP and GCNN for large data-sets&\cite{OCM2008}\\ 
\hline
\end{tabular}}
\end{center}
\caption{Characteristics of some IS (extracted from Table 1 of \cite{Olvera2010}). Also included are some of the published time complexities of the instance selectors.} %Where there are no specific BigO-notations, the authors would simple state runtime as quadratic or polynomial or the actual runtimes of their algorithm. The blank spaces indicate no reference made by authors to time complexity.}
\label{fig:lot-tab}
\end{figure*}     

\begin{comment}
\begin{figure}[h!]
\small
\begin{center}
\begin{tabular}{ p{8cm} }
\hline
\begin{verbatim}
CLUSTER = [KMEANS]
CLUSTERS = CLUSTER ON TRAIN
FOR EACH cluster IN CLUSTERS
  IF cluster = homogeneous
    CENTROID = MEAN(cluster)
    PROTOTYPE = INSTANCE NEAREST CENTROID
  ELSE
    LET CM BE MAJORITY CLASS IN cluster
    FOR EACH CLASS CK IN cluster (CK NOT= CM)
    	FOR EACH INSTANCE_K IN CK
    	  IF INSTANCE_M IN CM IS CLOSEST TO INSTANCE_K
    	   PROTOTYPE = PROTOTYPE + INSTANCE_M
        IF INSTANCE_K IN CK IS CLOSEST TO INSTANCE_M
         PROTOTYPE = PROTOTYPE + INSTANCE_K
      END
  RETURN PROTOTYPE
END

\end{verbatim}
 \\ \hline
    \end{tabular}
\end{center}
\caption{Pseudo-code for PSC}\label{fig:psc}
\end{figure}  


\subsection{Instance Abstraction}
\subsubsection{The Chang and Modified Chang Algorithms}
Chang's \cite{Chang74} work on finding prototypes for nearest neighbor classifiers is one of the earliest abstraction methods in the literature. The basic idea of his algorithm is to start with every sample in the training set as a prototype, then merge any two nearest prototype (p1 and p2 to form p*) with the same class as long as the recognition rate is not degraded. The new prototype p* can be formed by simply finding the average of p1 and p2 or the average vector of weighted p1 and p2 (Chang uses the weighted average). p* will have the same class as the individual prototypes p1 and p2. The merging process will continue until the number of incorrect classifications of patterns in the data set starts to increase. \fig{chang}, shows Chang's algorithm. 

The Modified Chang Algorithm (MCA) \cite{Bezdek98} was proposed by Bezdek in 1998. In this approach, Chang's algorithm is modified in two(2) ways: 1) the arithmetic mean is used rather than the weighted mean to merge prototypes. 2) the search for prototypes to merge is improved by partitioning the training set by their class labels and only searches within these respective partitions for the nearest prototype to merge. This eliminates the need to check for the criteria of candidate prototypes having the same class. 

\begin{figure}[h!]
\small
\begin{center}
\begin{tabular}{ p{8cm} }
\hline
\begin{verbatim}
Step 1: Start with an arbitrary point tj
        in B* and assign it to A*
Step 2: For all points tk in B* such that
        class (tk) is not equal to class (tj),
        update bk to be the distance between
        tk ans tj if this distance is smaller
        than the present bk. Otherwise, bk is
        unchanged.
Step 3: Among all the points in B*, find the
        point ts which has the smallest bs
        associated with it.
Step 4: If tj is not the nearest point ts such
        that the classes of tj and ts are
        different, go to Step 6. Otherwise
        continue.
Step 5: Check whether or not d(tj, ts) is less
        than bj. If no, go to Step 6. If yes,
        let bj=d(tj, ts) and continue.
Step 6: Let j=s, move ts from B* to A*, and go
        to Step 2 until B* is empty. When B* is
        empty, the final b1,...,bm are the
        desired ones.
\end{verbatim}
 \\ \hline
    \end{tabular}
\end{center}
\caption{Chang's algorithm for finding prototypes}\label{fig:chang}
\end{figure} 


\subsubsection{Learning Vector Quantization (LVQ)}

Kohonen \cite{Kohonen90} in 1990, introduced the learning vector quantization (LVQ) to create prototypes for the 1NN classifier using error correction rules. LVQ is a set of learning algorithms for nearest prototype classification and its basic algorithm, LVQ1, works by first selecting a certain number of prototypes from each class randomly as initial prototypes. This ensures that each class is represented be at least one prototype. These initial prototypes are then updated using the training set with the basic idea that the prototypes will be attracted to training points with the same class label and repelled by those with different class labels. So for an input instance $x$, find the prototype, $m_i$ (which is denoted by $m_c$), that is closest to it. \eq{lvq1} to \eq{lvq} defines the basic LVQ1 process of how the prototypes are updated \cite{Kohonen90}. Here $\alpha(t)$ is a learning rate between 0 and 1 and it decreases with time.

\begin{equation}
m_c(t + 1) = m_c(t) + \alpha(t)[x(t) - m_c(t)] 
\label{eq:lvq1}
\end{equation}
if x and $m_c$ have the same class,

\begin{equation}
m_c(t + 1) = m_c(t) - \alpha(t)[x(t) - m_c(t)] 
\label{eq:lvq2}
\end{equation}
if x and $m_c$ have the different classes,

\begin{equation}
m_i(t + 1) = m_i(t) 
\label{eq:lvq}
\end{equation}
for i \neq c.
\end{comment}
%\subsection{Summary}
%A troublesome feature with all the above research is the computational cost of the proposed instance selection methods. For instance, RNN requires that for each new instance removed from the list, consistency must be checked to ensure that the removal does not degrade the classification of the training set. While PSC has a three(3) step process which contributes to its computational cost, first the clustering of the training set followed by the testing whether clusters are homogeneous or heterogeneous, and finally there is the task of finding the border instances of heterogeneous clusters. 

%In fact, a survey of instance selectors by Olvera-López et.al \cite{lot2010} lists 24 instance selection methods, all of which run in polynomial time. 



\section{Background}
\label{section:bkg}

Our objective is to highlight the problem of brittleness in NN algorithms and show that it can be reduced through the use of IS. In Section \ref{section:cliff} we present CLIFF an instance selector proven to reduce brittleness better than three other IS studied in this work. However, before we discuss CLIFF we explain KNN is used in this work and how brittleness is measured.% and explain our selection criteria.

\subsection{Classification with KNN}
\label{subsection:knn}

K-nearest neighbor (KNN) classification is a simple classification method usually used when there is little or no prior knowledge about the distribution of data. KNN is described in \cite{knn} as follows: Stores the complete training data. New samples are classified by choosing the majority class among the k closest examples in the training data. For our particular problem, we used the Euclidean, i.e. sum of squares, distance to measure the distance between samples and k = 1. 


\subsection{The Brittleness Measure}
\label{subsection:bm}
Calculating the brittleness measure is a novel operation. We use the brittleness measure in this work to determine if the results of IS and KNN come from a region where all the possible results are (dis)similar. For the purpose of this work the optimal result will come from a region of similar results. To make this determination, using the 1NN classifier as a baseline for the IS, each instance from a test set is assigned to a target class. Next, the distances from their nearest unlike neighbor (NUN) i.e. the distance from an instance with a different class are recorded. Recall that brittleness is a small change can result in a different outcome, so here the closer the distances of the IS to the baseline 1NN, the more brittle the model. So an ideal result will have the greatest distance between the IS and 1NN. 

%The brittleness measure will give an output of either $high$ or $low$: high indicating that there is no significant difference between the CAM and 1NN distances, while $low$ indicates the opposite. The significance of these values was calculated using the Mann-Whitney U test. This is a non-parametric test which replaces the distance values with their rank or position inside the population of all sorted values.

\eq{bm} embodies our definition of brittleness: for instance, if the significance of CLIFF values are less than or equal to the 1NN values, then an unacceptable level of  brittleness is present in the model. 

\begin{equation}
[CLIFF <= 1NN] ==> BRITTLENESS
\label{eq:bm}
\end{equation}


%In this section, we evaluate CAM as a forensic model on a data set donated by \cite{Karslake09} in cross validation experiments. First, we describe the data set and experimental procedures. Next we present results which show the probability of detection (pd), probability of false alarm (pf) and brittleness level of CAM.

%\subsection{The Selection Criteria}
%\label{subsection:sc}

\subsection{Noise vs Brittleness}

One might be tempted to believe that noise and brittleness are the same thing. However, where noise in a data-set includes outliers, misclassified instances, false instances injected into the data-set, the brittleness of a data-set can only be uncovered after the classification of test instances. In other words brittleness is not about specific instances, rather about closeness of instances with different predicted target classes. %Take for example  
