\section{Background}
%\footnote{fayola- should this section be BEFORE section2? and should it include
%backgrun notes on NN aplications and algorithms?}
\label{section:bkg}
Our objective is to highlight the problem of brittleness in kNN algorithms and show that it can be reduced through the use of ISM. In Section \ref{section:cliff} we present CLIFF an instance selector proven to reduce brittleness better than three other ISM studied in this work. However, before we discuss CLIFF we explain how kNN is used in this work and how brittleness is measured.% and explain our selection criteria.

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

In fields such as pattern recognition, data mining and machine learning, kNN is a method for classifying a given test instance based on the closet training instances in the feature space. A test instance is classified by a majority vote of its neighbors, with the test being assigned to the class most common amongst its k nearest neighbors. If for example, k=1 then the test instance is simply assigned to the class of its nearest neighbor.

Although kNN has several disadvantages (see Section \ref{section:introduction}), this simple algorithm has favorable properties as well. First, $k$ is the only parameter required and second, little or no prior knowledge about the distribution of data is needed. 
%kNN %(KNN)\footnote{should this acronym be used in the intro instead of NN?}
%classification is a simple classification method usually used when there is little or no prior knowledge about the distribution of data. It is described in \cite{knn} as follows: Stores the complete training data. New samples or instances are classified by choosing the majority class among the k closest instance in the training data. 
For our particular problem, we used the Euclidean distance, i.e. sum of squares, to measure the distance between instances. Also, in kNN we use k as 1.%\footnote{the last five words make no sense}. 


\subsection{The Brittleness Measure}
\label{subsection:bm}
 We use the following {\em brittleness measure} to determine if the
 results of ISM and kNN come from a region where all the possible
 results are (dis)similar. Recall from the introduction,
that the brittleness problem disappears if the test instance falls
into a region of the training data that contains uniform classifications.
To make this determination, using the 1NN classifier as a baseline
for the ISM, each instance from a test set is assigned to a target
class. Next, we record the distances from their nearest unlike neighbor (NUN)
i.e. the distance from an instance with a different class.
Recall that brittleness is a small change can result in
a different outcome. That is:
\bi
\item
  {\em smaller} NUNs lead to {\em increased}
brittleness;
\item
The best
instance selector that most {\em reduces} brittleness will
{\em increase} the NUN.
\ei
%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 NUN 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}
%BRITTLENESS \leftarrow CLIFF \le 1NN 
%\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}





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

%Find papers with noise experiment results.
%In Section 1, the optimal goal of instance selectors as a solution to the drawbacks of NNC is highlighted. To continue this discussion, in this section we present a brief survey of instance selectors 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 instance selectors 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 three(3) different ways.

\be
\item incremental; e.g. CNN: Condensed Nearest Neighbor \cite{Hart68a};
\item decremental; e.g. RNN: Reduced Nearest Neighbor \cite{Gates72};
%\item a combination of 1 and 2\footnote{we never combine back to this one: can we drop it?};
\item border points, non-border points or central points; e.g. PSC: Prototype Selection by Clustering \cite{lot2010}.
\ee

In the following sections, we review ISM which abide by 1, 2 and 3. However, before moving forward, in the interest of clarity, the following terminology are used throughout the remainder of this work:
\bi
\item
All data-sets refer to {\em supervised data-sets};
\item
Each data-set consists of {\em rows} and {\em columns} where each row is referred to as an {\em
instance} and each column is called an {\em attribute} except for the last column which is the {\em target class}; 
\item
The selected instances found after applying an instance selector is referred 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}
\item
Finally, {\em consistency} is defined as the ability of the final subset 
of instances to correctly classify the original training set.
\ei
%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 instance selectors 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{instance selectors surveyed in this work}\label{fig:psw}
\end{figure*}
\end{comment}
%\subsection{Instance Selection}

\subsection{Condensed Nearest Neighbor (CNN)}

%\footnote{fayola- you never describe the complexity of PCS,NLN,CNN,RNN. perhaps you should add them to the top of fig2}
Different instance selectors 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. %The complexity for CNN is shown in \fig{lot-tab}.

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. According to \cite{wilson00}, 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

In terms of time complexity, note that for each iteration of CNN the entire training set (n) has to be used to find misclassified instances. Additionally, to find these misclassified instances, $n$ is compared to the current training subset (p) whose size begins at $\|C\|$, i.e. the number of class values and increases. So, if $i$ denote the number of iterations required, the complexity of CNN is $O(ipn)$. Furthermore, in the worst cast p=n, therefore overall complexity is $O(in^2)$. %Clearly the number of iterations dictates the time requirement of CNN. %time requirement (reword) 

\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
  Minstance selectorsCLASSIFIED = classify TRAIN and 
                  RETURN Minstance selectorsCLASSIFIED 
                  INSTANCES
  PREV = CUR
  CUR = Minstance selectorsCLASSIFIED + 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 because initially $p=n$, however RNN 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 {\em like instances} (in other words, those with the same class) closer to them than {\em 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, MCS calculates
the
distance of its nearest unlike neighbor (a quantity we will refer to as ``NUN''; i.e. distance to
the nearest neighbor with a different class). 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.

The time complexity of MCS can be regarded as follows:

\be
\item Initially, to find the NUN of each instance in the training subset and their NLN whose distances from the instance are less than the NUN distance, requires $O(n^2)$
\item To designate candidate prototypes, a count of the votes for each instance is taken - $O(n)$
\item Finally, the iteration process takes $O(ip)$
\ee

Since step 1 above dictates the time requirement for MCS, its time complexity is $O(n^2)$.


\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
   Dinstance selectorsTANCE_NUN = Dinstance selectorsTANCE(c, NUN)
   VOTER_Linstance selectorsT = NLN
   VOTES = COUNT(VOTER_Linstance selectorsT)
  END
  P* = NLN with MAX(VOTES)
  CUR = CUR - P*(VOTER_Linstance selectorsT)
END
\end{verbatim}
 \\ \hline
    \end{tabular}
\end{center}
\caption{Pseudo-code for MCS}\label{fig:mcs1}
\end{figure}  
\end{comment}

\begin{figure*}
\begin{center}
\scalebox{0.7}{
\begin{tabular}{ | l | l | p{12cm} | l |}
\hline
\multicolumn{3}{c}{Wrapper Methods} \\ \hline
Methods & Based on & Time Complexity& Reference\\ \hline
CNN (Condensed Nearest Neighbor)& Misclassification& $O(in^2)$, where $i$ is the number of iterations, 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} , where $d$ is the number of dimensions and $n$ is the cardinality of the training set $\|T\|$ & \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 SNN & \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 (in their experiments it was between 9 and 12) and $|DB|$ is the size of the database.%FAYOLA: anyway to demomstrate that ``number of operations'' is exponential? 
&\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(iN)$, where $i$ 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. According to the experiment in \cite{Garain2008}, ``"Experimentally it is verified that the average number of iterations (maximum and minimum are being 21 and 02) required to produce properly mutated clone is 8 (i.e., k = 8)."
  &\cite{Garain2008}\\ %FAYOLA: anyway to demonstrate that $k$ is large??? "Experimentally it is verified that the average number of iterations (maximum and minimum are being 21 and 02) required to produce properly mutated clone is 8 (i.e., k = 8). "
& & & \\

%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 (classifier) 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| $ 
%FAYOLA: how are the projections generated? PCA? some polynomial time matrix procedure?   
%MENZIES: projections are abscissa - a more general sense as a number determining the position of a point along a line
%&\cite{Riquelme03}\\ 
%&&& \\
POC-NN (Pair Opposite Class-NN)& Opposite class means, border instances & $O(dn^2i)$, for a 2-class system. Denotation same as CNN, and where $i$ 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 
%FAYOLA: building a kd-tree is fast, but are there some query operations on top of that that makes this undesirable? no
%MENZIES: no query operations on top of kd-tree
%&\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 & $O(C^2)$, where $C$ is the set of prototypes belonging to each class.
%Runtimes are significantly better than DROP and GCNN for large data-sets
&\cite{OCM2008}\\ 
\hline
\end{tabular}}
\end{center}
\caption{Characteristics of some ISM (extracted from Table 1 of \cite{Olvera2010}). Also included are some of the published time complexities of the ISM.} %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*}     


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

As explained in \cite{lot2010}, PSC begins by dividing the training data into regions using a clustering algorithm. The $Cmeans$ algorithm is used in their work. In Cmeans clustering, each instance in a cluster is weighted by a degree of belonging to that cluster. So, if an instances lies along the border of a cluster then its degree of belonging to that cluster is less than an instance that lies close to the centroid of the cluster \cite{Dunn73}.  Although $Cmeans$ is used in \cite{lot2010}, it is made clear that any clustering method can be used in its place and so in our experiments for this work, $Kmeans$ \cite{Hartigan75} is our algorithm of choice. 

After clustering, the {\em 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.

The time complexity of PSC can be regarded as follows:

\be
\item Clustering with K-means can be done in linear time - $O(iknd)$, where k is the number of clusters and d is the dimension.
\item Determining if a cluster is homogeneous or heterogeneous is done in $O(kn)$ time.
\item Finding the prototypes from the homogeneous clusters - $O(k)$
\item Finding the prototypes from the heterogeneous clusters - $O(Ck)$, where C is the number of classes.
\ee

Hence the overall complexity for PSC is $O(iknd)$ + $O(Ck)$.

\subsection{Other Instance Selection Methods}

The above set of ISM is obviously a sparse sample in the field of instance selection. A recent review of ISM presented by \cite{Olvera2010}, placed ISM 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 ISM except to state that the filter methods have smaller runtimes than wrapper methods \cite{Olvera2010}. %This may be due to the fact that most instance selectors 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 ISM studied in \cite{Olvera2010}. As shown, most ISM 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{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 instance selectors CLOSEST TO INSTANCE_K
    	   PROTOTYPE = PROTOTYPE + INSTANCE_M
        IF INSTANCE_K IN CK instance selectors 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. 


