With dataset sizes and feature dimensions increasing exponentially over the last thrity to forty years, prototype learning schemes designed for nearest neighbour classifiers are essential. Researchers have risen to the challenge and as a result, an impressive collection of PLS exists today. Each scheme unique in terms of the methods used to create prototypes. For instance, various clustering methods such as k-mean [ref] and fuzzy c-means [ref] have been used. Also search algorithms including tabu [ref] and genetic algorithms have shown up in the literature. Even evolutionary algorithms [ref] and auto immune systems methods [ref] show some success as prototype generators. Fortunately, a few researchers organized the PLS into distinct categories. The most popular of these is Bezdek's categories. He and his co-authors presented three (3) categories for PLS in a 2000 paper titled, \emph{Some Notes on Twenty One (21) Nearest Prototype Classifiers}. Not to be left out, other authors, in distinguishing their PLS from others in the literature, elaborate on the characteristics which form the basis for their scheme. The following section explores Bezdek's three (3) categories for PLS as well as other popular characteristics for PLS which show up constantly in the literature.

\subsection{Bezdek's Categories}

Bezdek et al claims that among the many characteristics of prototype extraction methods for 1-np classifier design that can be discussed, they consider, 1) selection vs replacement, 2) pre-supervised vs post-supervised and 3) user defined n vs algorithmically defined n, all labelled as C1, C2 and C3 respectively, as the most important. 

The categories are defined as follows:

\textbf{(C1) Selection versus replacement}. That is, prototypes may be a subset made up of instances of the training data. This is called \emph{selection}. Examples of these are tabu and genetic algorithms, and also the Minimal Consistent Set (MCS) by Dasarathy. Replacement occurs when new instances are formed using the training data. Examples of this includes Chang's 1974 method, Bezdek modified Changs algorithm (MCA), LVQ and its variations. According to the literature, the selection method is best used in situations where the data is supervised and/or noisy. On the other hand this researcher so far has found no specific criteria for using the replacement method.

\textbf{(C2) Pre-supervised versus post-supervised designs} [4]. 
\begin{quotation}
Pre-supervised methods use the data and the class labels to locate the prototypes. Post-supervised methods first find prototypes without regard to the training data labels, and then assign a class label to (relabel) each prototype. Selection methods are naturally pre-supervised, because each prototype is a data point and already has its (presumably true) label.[ref]
\end{quotation}

\textbf{(C3) User-defined n versus algorithmically defined n} . 
\begin{quotation}
Most prototype generators require advance specification of n (e.g., classical clustering and competitive learning methods). Some models have "adaptive" variants where an initially specified n can increase or decrease, i.e., prototypes are added or deleted during training under the guidance of a mathematical criterion of prototype "quality". A third group of methods do not specify n at all, instead obtaining it as an output at the termination of training.[ref]
\end{quotation}

Looking at the above categories, it is clear that the goal of the paper [ref] is to figure out the best method in each category. From the experimental results, the authors concluded that replacement prototypes seem to produce better 1-nearest prototype designs than points selected from the training data at a ratio of 2:1. Also that pre-supervision seems to find more useful prototypes for 1-nearest prototype classifiers than post-supervision does at a ratio of 5:1. The experiments further indicated that methods which ''automatically" determine the best number of prototypes and methods that are largely based on user specification and trials-and-error are equally likely to yield good 1-nearest prototype classifiers. 


\subsection{Beyond Bezdek's Categories}

Although Bezdek's claims that the categorgies outlined in his paper are the most important in prototype learning schemes this research has uncovered other characteristics essential for a user in deciding which PLS is best for their dataset. These characteristics as listed as follows:

\begin{itemize}
\item Order Independent vs Order Dependent Methods
\item Consistent vs Non Consistent Methods
\item Scalable vs Non Scalable Methods
\end{itemize}

\subsubsection{Order Independent vs Order Dependent Methods}

In Devi's et. al. research titled, ''An incremental prototype set building technique", the authors go out of their way to show readers that their prototype learning scheme was order independent. Their argument against order dependent methods is as follows:

\begin{quotation}
It is a well-known fact that Condensed Nearest Neighbour (CNN) is order dependent. When it is applied to a particular data set, it gives a certain condensed prototype set leading to a set of non-intersecting Vornoi regions. Now if the order of the data set is changed, it will result in another set of non-intersecting Vornoi regions. If there are n data points, by permuting this data set in n! ways, we can get n! different condensed prototype sets.
\end{quotation}

The authors also highlight a major drawback of having n! prototype sets to choose from, i.e. the computational cost of finding out which prototype set will give the optimal result.

In contrast, the order independent procedure outlined in the paper [ref], indicates that points collected in a misclassified set and a correctly classified set will be the same, but will only differ in the order they appear if the order of the data set is changed.

Although the Devi's work casts a dark shadow over order dependent methods, there are some domains where they can be advantagous. For instance in areas such as robotics and online learning where previous experience (which is classified by a teacher) is used to classify future experiences or decide what is the next best move to achieve a goal. A perfect example of this is MESO (Multi-Element Self-Organizing tree) [ref]. Kasten describes it as ''...a perceptual memory system designed to support online, incremental learning, and decision making in autonomic systems". Basically, prototypes generated here are cluster based and are called spheres. Each sphere contains a collection of similar instances. Sphere membership is dictated by a grow function which manages the size of the sphere. So, any new instance finds its closest sphere, if the distance is less than the distance of the growth function then it gets added to the sphere otherwise a new sphere is created with the instance. Organizing the data in this way is perfect when the size of the data set is indefinite as they are in these domains.

\subsubsection{Consistent vs Non Consistent Methods}

In the literature and this work, consistent is used to mean that all (100\% of) the original samples are correctly classified by the prototype subset. Therefore non-consistent is anything less than 100\% classification accuracy. From the literature PLS which guarantees a consistent result on the training data set produced NNC with higher classification accuracy [ref] than those which are non-consistent. However, before the reader firmly decides that consistent methods are the only way to go, this researcher must admonish about a major limitation of this decision. The problem is overfitting. Veenman, explains:

\begin{quotation}
The problem is that perfect training performance by no means predicts the same performance of the trained classifier on unseen objects. Given that the training data is sampled similarly from the true distribution as the unseen objects, the cause of this problem is twofold. First, the training data set contains an unknown amount of noise in the features and class labels, so that the exact position of the training objects in feature space is uncertain. Second, the training data may be an undersampling of the true data distribution. Unfortunately, this is often the case, so that the model assumptions about the data distribution are not justified [ref]. 
\end{quotation}

\subsubsection{Scalable vs Non Scalable Methods}
 
Many prototype learning schemes can be excruciatingly slow according to the size of the data set. Also some PLS can fail to converge is the data set is to large. In comes fast and scalable methods. 




