# Data Reduction in the String Space for Efficient kNN Classification Through Space Partitioning
## 4 Experimentation
### Corpora  
Regarding the different corpora for the experimentation, we considered three different datasets of handwritten characters publicly available as images: the United States Postal Service (USPS) dataset of handwritten digits [25] whose images have a resolution of \(16\times 16\) pixels; the NIST SPECIAL DATABASE (NIST) of handwritten characters [26] in images of \(28\times 28\) pixels; and the MNIST collection of isolated handwritten digits [27] which is also distributed as images of \(28\times 28\) pixels.  
In order to extract a string-based representation, all these images have undergone a process of contour extraction as the one described in [28] which is later encoded as a Freeman Chain Code [29]. Note that in no case we are claiming that this representation is the most suitable for these datasets but it allowed us to perform the considered experimentation. Figure 2 shows an example of this codification process.  
So as to obtain the feature-based representations we have resorted to the RandomC strategy previously introduced. Several values were tested to tune the \(c\) parameter of the number of pivots per class taking as a reference value the performance of the Nearest Neighbor classifier in the target space. Nevertheless, as no significant differences were observed, we considered the value of \(c=5\). This particular value constitutes the lowest one tested in our tuning experimentation and implies the least number of features in the statistical space.  
As of data partitions, the sets have been distributed in five different folds maintaining the same class distribution as the complete set. It must be mentioned that, for a fair comparison between the two representation spaces, the different folds in both structural and statistical representation contain the exact same instances with the sole different of the encoding type considered.  
Finally, Table 1 summarizes the details of the different data collections considered providing a description about the length of the string samples obtained after the aforementioned encoding processes from the images as well as the number of features after the RandomC stage.  
\begin{table}
\begin{tabular}{l c c c c c c c} \hline \hline \multirow{2}{*}{**Dataset**} & \multirow{2}{*}{**Instances**} & \multirow{2}{*}{**Classes**} & \multicolumn{5}{c}{**String Length**} & \multirow{2}{*}{**Feature Space Size**} \\ \cline{3-3} \cline{5-7}  & & & **Min** & **Q1** & **Med** & **Q3** & **Max** \\ \hline NIST & 5200 & 26 & 11 & 153 & 190 & 232 & 674 & 130 \\ \hline MNIST & 10,000 & 10 & 15 & 53 & 59 & 69 & 115 & 50 \\ \hline USPS & 8684 & 10 & 13 & 42 & 46 & 51 & 78 & 50 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Description of the data collections considered in terms of number of instances, classes, and sample sizes in both the initial string and the Dissimilarity Space (feature-based) one using RandomC. _Min_, _Med_, and _Max_ stand for the minimum, median, and maximum datum length while _Q1_ and _Q3_ denote the first and third quartiles, respectively.  
Figure 2: Example of a contour and string codification of a sample from the USPS corpus representing the digit 7. (**a**) Original image; (**b**) Extracted contour; (**c**) String representation using Freeman Chain Codes.