Identifying predictive hubs to condense the training set of $k$-nearest neighbour classifiers

Abstract

The $k$-Nearest Neighbour classifier is widely used and popular due to its inherent simplicity and the avoidance of model assumptions. Although the approach has been shown to yield a near-optimal classification performance for an infinite number of samples, a selection of the most decisive data points can improve the classification accuracy considerably in real settings with a limited number of samples. At the same time, a selection of a subset of representative training samples reduces the required amount of storage and computational resources. We devised a new approach that selects a representative training subset on the basis of an evolutionary optimization procedure. This method chooses those training samples that have a strong influence on the correct prediction of other training samples, in particular those that have uncertain labels. The performance of the algorithm is evaluated on different data sets. Additionally, we provide graphical examples of the selection procedure.

Appendix

The accuracy term $A$ given in Eq. 10 is inspired by the idea of sample compression bounds (Littlestone and Warmuth 1986). These bounds can be used to give an upper limit to the true classification error probability $\mathcal{E }$ of a data-dependent classifier $c$. A classifier is called data-dependent if it can be reconstructed directly from a certain subset of training samples $\mathcal{R } \subseteq \mathcal{T }$ (called a compression set in this context), i.e. $c_\mathcal{R } = c_\mathcal{T }$. This is clearly true for $k$-NN-like classifiers following Eq. 3, as they can be reconstructed from their reference set. A sample compression bound estimates the true error probability $\mathcal{E }$ from the empirical error rate E calculated on the remaining samples $\mathcal T {\setminus }\mathcal{R }$.

Theorem 1

(e.g. Langford 2005) For a random sample $\mathcal{T }$ of iid examples drawn from an arbitrary, but fixed distribution $\mathcal{D }$ and for all $\delta \in \left(0,1\right]$,

$$\begin{aligned}&\mathop {\text{ Pr}}\limits _{\mathcal{T } \sim \mathcal{D }^{|\mathcal{T }|}} \left( \forall \mathcal{R } \subseteq \mathcal{T }\, with\, c \!=\! k\text{ NN}(x, \mathcal{R }): \mathcal{E }_\mathcal{D }(c) \le \mathrm{{\overline{Bin}}} \left(\text{ E}(c, \mathcal{T }{\setminus } \mathcal{R }), \frac{\delta }{|\mathcal{T }| \genfrac(){0.0pt}{}{|\mathcal{T }|}{|\mathcal{T }\setminus \mathcal{R }|}} \right) \right)\ge 1-\delta \nonumber \end{aligned}$$

Proof

Theorem 1 is a direct application of the sample compression bound given in Langford (2005). $\square$

The term $\mathrm{{\overline{Bin}}}$ in Theorem 1 denotes the binomial tail inversion.

Figure 3 shows an application of the sample compression bound on a training set of size $|\mathcal{T }|=100.$ The bound is shown for fixed empirical error rates of 0.01, 0.05 and 0.1. The bound suggests that of all $k$-NN classifiers achieving the same empirical error, the classifier with the smallest reference set is most reliable.

Fig. 3

The figure shows the sample compression bounds for a $k$-NN experiment with $|\mathcal{T }|=100$ examples. We assume that empirical error rates of 0.01, 0.05 and 0.1 were measured for different compression set sizes $|\mathcal{R }|$