## 2 Theoretical Background
### ML Models
#### 2.1.2 k-Nearest Neighbour (kNN)  
The kNN algorithm is a non-parametric, supervised learning method developed by [PERSON] and [PERSON] [87], in which the input is made of the \(k\) closest training samples of a dataset and the output for a classification problem is a class membership: the object is assigned to the class most common among its k nearest neighbours. Given a set of observations \(D\),  
\[D=\{(\mathbf{x}_{1},y_{1}),\ldots,(\mathbf{x}_{N},y_{N})\}\ \ \ \ \ i=1,\ldots,N \tag{9}\]  
where \(\mathbf{x}_{i}\) is the feature vector and \(y_{i}\) is the corresponding class label of the \(i\)-th example. The \((\mathbf{x}_{i},y_{i})\) is assumed to be i.i.d. from some unknown distribution \(P\) of \((\mathbf{x},y)\) on \(R^{d}\times\{\omega_{1},\ldots,\omega_{M}\}\), where \(M\) is the number of classes, and the goal is the design of a classifying function \(\phi_{n}\ :\ R^{d}\rightarrow\{\omega_{1},\ldots,\omega_{M}\}\) that maps a feature vector \(\mathbf{x}\) into its desired class from \(\{\omega_{1},\ldots,\omega_{M}\}\).  
The performance of the classifier is evaluated through the probability error of Equation (10) [88]:  
\[J(\phi_{n})=P\{(\mathbf{x},y):\ \phi_{n}(\mathbf{x})\
eq y\} \tag{10}\]  
where \(J\) is the cost function and \(\phi_{n}\) is the classifying function.  
If the underlying distribution is known, then the optimal decision rule \(\phi^{*}\) that minimises the probability of error is the Bayes decision rule of Equation (11):  
\[\phi^{*}(\mathbf{x})=\text{argmax}P(y|\mathbf{x}) \tag{11}\]  
It can be shown that at any given point, \(\mathbf{x}\), the probability that its nearest neighbour \(\mathbf{x}^{\prime}\) belongs to class \(\omega_{i}\) converges to the corresponding a posteriori probability \(P(\omega_{i}|\mathbf{x}^{\prime})\) as the number of reference observations goes to infinity. It was shown by [PERSON] and [PERSON] [89] that under some continuity conditions on the underlying distribution, the asymptotic probability of error \(L_{NN}\) for a multi-class kNN classifier is bound by the terms reported in Equation (12):  
\[L^{*}\leq L_{NN}\leq L^{*}\bigg{(}2-\frac{M}{M-1}L^{*}\bigg{)} \tag{12}\]where \(L^{*}\) is the optimal Bayes probability of error. Thus, the nearest-neighbour rule is asymptotically optimal when the classes are not overlapping [90].  
In the classification phase, after the constant \(k\) has been defined by the user, an unlabelled vector is classified by assigning the label that is most frequent among the \(k\) training samples that are nearest to that query point. The distance metric could be represented by the Euclidean distance, the Hamming distance, or the correlation coefficients. The value of \(k\) deeply affects the classification performance [40]: larger values reduce the effects of noise but make the boundaries between classes less distinct. The accuracy is also affected by the presence of noisy or irrelevant features, or if the feature scales are not consistent with their importance. Finally, data-reduction is one of the biggest problems when working with huge datasets, because only some of the data points, called prototypes, are needed for accurate classification. A commonly used algorithm for dataset reduction is the Hart algorithm [91].