MARS which stands for \emph{MESO and Reduction Solution}, is a two (2) step procedure for first generating initial-prototypes, then removing those conflicting prototypes present in a local neighbourhood. MESO uses a "...data clustering approach which creates small clusters of patterns called sensitivity spheres" \cite{Kasten2007}, while our reduction strategy adopts the nearest unlike neighbour (NUN) concept used by Dasarathy \cite{Dasarathy94} to remove conflicting prototypes. The following sections show how MESO is used to create the initial prototypes for each class in the training set and also how NUN is used to reduce these initial prototypes. 

\subsection{Creating Initial Prototypes with MESO}

\fig{meso}, displays the algorithm for creating sensitivity spheres (clusters) in MESO. The growth function used is shown as equation [h]. As described in [meso ref], the algorithm takes each instance and its closest sphere mean vector is located. If the distance between them is less than or equal to \begin{math}\delta \end{math} then the instance is added to the sphere and the sphere mean is recalculated. If however the distance between the instance and the sphere is greater than \begin{math}\delta \end{math} then \begin{math}\delta \end{math} is grown using the growth function [ref eq] and the instance forms a new sphere with itself as the initial sphere mean vector. Indept details of this algorithm is not presented in this work, however the reader can further investigate the Kasten's algorithm in his paper, ``MESO: Supporting Online Decision Making in Autonomic Computing Systems" \cite{Kasten2007}.


\begin{figure}[ht]
	\begin{center}
\begin{tabular}{ | p{8cm} | }
\hline

\begin{tabbing}
Initialize \= \begin{math} \delta \end{math} = 0, \begin{math} \mu \end{math} = x1, s1 \\
For \= each xj sample do \\
\> Find \= the nearest \begin{math} \mu \end{math} for xj \\
\> \> if \= distance from \begin{math} \mu \end{math} to xj <= \begin{math} \delta \end{math} \\
\> \>	\>			(i) \= add xj to si \\
\> \>	\>			(ii) \= recompute \begin{math} \mu \end{math} using samples in si \\
\>	\>		else \\
\> \>	\>			(i) \= let \begin{math} \delta \end{math} = grows \\
\> \>	\>			(ii) \= create new si + 1 \\
\> \>	\>			(iii) \= add xj to si + 1 \\
\> \>	\>		  (iv) let \begin{math} \mu \end{math} = xj \\ 
\end{tabbing} 
\\ \hline
\end{tabular} 
   \caption{Sphere Creation Algorithm in MESO (adapted from \cite{Kasten2007})}
		\label{fig:meso}
	
	\end{center}
\end{figure}	

The main advantages of using MESO \cite{Kasten2007} to generate our initial prototypes are (1. the user does not need to decided on the number of initial prototypes to generate, the algorithm does this automatically and (2. the distance value which determines the size of a sphere is realized from the training set. With the task of choosing values for these variables taken care of by MESO, we focus on generating prototype for each class in our training set. First, the instances in the data set are grouped by their class label. Sensitivity spheres are then created for each of these groups. Once this step is completed, three instances from each sphere are selected as initial prototypes. The criteria for selecting the prototypes is as follows:

\begin{itemize}
\item For each sphere the instance closest to the centroid is chosen. 
\item The other two (2) instances are chosen as the furthest points away from the centroid of a sphere. This is done by first finding the instance, ia, furthest away from the centroid, then finding the instance furthest from ia. 
\end{itemize}

Recall that one disadvantage of using a NNC is that if the classes in a data set are non-separable or overlapping, training samples in a local neighbourhood may come from different classes. As a result, test data may be misclassified using a NNC. Further, since the spheres created here by MESO is done on a class by class basis, the other classes do not have a say in the positioning of the resulting spheres. It is for these reasons that the \emph{reduction} step of MARS is performed. 

\subsection{Reduction by Removing Confusing Prototypes}

The purpose of removing confusing prototypes is to reduce the misclassification rate by an NNC. \fig{nun} clearly features the basic algorithm used to accomplish this. \fig{reduction} shows the general prototype reduction at each level of a data set. A few data sets such as Lymph and Audio show a very small reduction from the original number of prototypes while others such as Breast Cancer, Vote and Tic-Tac-Toe show a radical reduction to less than 10\% of the original data set. Please note that since MESO is order dependent, the reduction rate differs once the data set is shuffled.

\begin{figure}[h!]
	\begin{center}
\begin{tabular}{ | p{8cm} | }
\hline
\begin{tabbing}
1. Choose \= initial prototypes for each class using SSC from MESO \\
2. Take \= each prototype and find the distance (d1) of its NUN, \\ 
3. Then \=  find the distance (d2) of its nearest like neighbour (NLN). \\
    \> If \= d1 \begin{math} \leq \end{math} d2 , remove the prototypes \\
    \> If \= d1 \begin{math} > \end{math} d2 , the prototype is approved and kept \\
4. Repeat 2 and 3 until no more prototypes can be removed   \\
\end{tabbing} 
\\ \hline	   
\end{tabular}
   \caption{Reduction with NUN Algorithm}
		\label{fig:nun}
	\end{center}
\end{figure}	

\begin{figure}[h!]
	\begin{center}
    \begin{tabular}{ | l | l | l | l |}
    \hline
    Data Set      & All prototypes & Initial-Prototypes & Final Prototypes \\ \hline
    Lymph         & 147 & 132 & 125 \\ \hline
    Iris          & 150 &  63 &  57 \\ \hline
    Breast Cancer & 286 &  24 &  11 \\ \hline
    Heart         & 297 &  81 &  75 \\ \hline
    Tumor         & 339 &  75 &  63 \\ \hline
    Vote          & 430 &  18 &   8 \\ \hline
    Diabetes      & 768 & 129 &  92 \\ \hline
    Tic-Tac-Toe   & 958 &  21 &   4 \\ \hline
    Sonar         & 208 & 102 &  75 \\ \hline
    Balance Scale & 226 & 177 & 134 \\
    \hline
    \end{tabular}
    \caption{Reduction Level of Data Sets with MARS}
		\label{fig:reduction}
	\end{center}
\end{figure}





