What is the advantage of bagging for k-NN? Is there an advantage to use bagging with k-NN? I constantly get better performances while doing it. Can it be that it is because of resampling with repeated instances, which will therefore be classified in the same neighborhood?
Is this some kind of cheating or is it legitimate?
 A: If by bagging you mean taking the average over bootstrap-resampled training samples: that's certainly not cheating if you only build them off the single training sample.
As an illustration, let's think about $1$-NN. For a test point $x$, the predicted label for $1$-NN is the label of the nearest training set point. For bagging, let $q_\ell(x)$ denote the $\ell$th nearest neighbor in the training set. Then the expectation of the predicted label is
\begin{align}
\mathbb{E}[\hat{y}(x)]
&=\sum_{\ell=1}^n \Pr(q_1(x), \dots, q_{\ell - 1}(x) \text{ not in sample and } q_\ell(x) \text{ in sample}) \, y_{q_\ell(x)}
\\&= \sum_{\ell=1}^n \underbrace{\left( \frac{n-\ell+1}{n} \right)^n \left( 1 - \left( \frac{n-\ell}{n-\ell+1} \right)^n \right)}_{a_{\ell,n}} y_{q_\ell(x)}
\end{align}
where the coefficients $a_{\ell,n}$ satisfy
$$
a_{\ell,n} \stackrel{n\to\infty}{\longrightarrow} \frac{e - 1}{e^\ell}
.$$
So, this effectively turns the hard-assignment $1$-NN into a soft-assignment approach, weighting the nearest neighbor's labels by $0.63, 0.23, 0.09, 0.03, \dots$. I don't know if there's anything special about those weights, but it makes sense that smoothing out the labels like this would often perform somewhat better than the hard-assignment approach of 1-NN.
The same kind of argument applies to $k > 1$, it's just a little harder to calculate the smoothing weights.
