\subsection{KNN classifier}
Cover and Hart \cite{cover1967nearest} introduced the idea of nearest neighbor pattern classification.In pattern recognition field, KNN is one of the most non-parametric classifiers that is used for a supervised learning algorithm \cite{murphy2012machine,kaghyan2012activity}. % ,murthy2015ann,suguna2010improved}.
KNN searches the K points in the training set that are closest to the test input x which is judged to the highest class probability \cite{murphy2012machine}. Based on the predefined(classified) class labels which is a set of N labeled instances $\{x_i, y_i\}^1_N$, the classifier task is to predict the label of class that has the unknown(unclassified) query vector $x_0$ \cite{song2007iknn}. Using the K …show more content…
%\item Infinity function:
%$ d_\infty(x, y)=max\{|x_i-y_i|, where\ i=1,....,n\}$.

\end{itemize}

Figure \ref{KNN} demonstrates case when k has value of 3. Therefore, the unknown point $X_u$ will be compared with three nearest neighbors. Based on results, it can be supposed as belonging to proper set. In our case, $X_u$ is the test point with unknown template. In this example k=3, euclidean distance between this point and its 3 nearest neighbors is computed. 2 of them belong to $W_1$ while 1 belongs to $W_3$ , so Xu is assigned to $W_1$ set.

On different data sets, many researchers have found that the K-NN algorithm achieves high performance in their experiments \cite{kaghyan2012activity,suguna2010improved}.
%However, it has three limitations: (a) calculation complexity due to the usage of all the training
%samples for classification, (b) the performance is solely dependent on the training set, and (c) there is no weight
%difference between samples \cite{kaghyan2012activity}.
The performance of a KNN classifier depends primarily on both by the choice of K and the metric distance applied.
%\cite{Latourrette, M.: Toward an explanatory similarity measure for …show more content…
In: ECML ’00: Proceedings of the 11th European Conference on
%Machine Learning, London, UK, pp. 238–245. Springer-Verlag, Heidelberg (2000)}.
Broadly, choosing large values for K (a positive integer, typically small) are more immune to noise, however boundaries between classes become more smooth(less distinct) \cite{song2007iknn}. %kaghyan2012activity,
Therefore, using the same value of K is almost impossible for different applications. Based on data and various heuristic techniques, the best choice of k can be selected, for example, cross-validation. The special case is when K=1 which is called the nearest neighbor algorithm. This is where the class is predicted to be the class of the closest training sample. For binary classification problems, it is better to choose an odd number for K as this avoids tied votes