Instance reduction methods are popular methods that reduce the size of the datasets to possibly improve the classification accuracy. We present a method that reduces the size of the dataset based on the percentile of the dataset partitions which we call IPRed. We evaluate our and other popular instance reduction methods from a classification perspective by 1-nearest neighbor algorithm on many real datasets. Our experimental evaluation on the datasets shows that our method yields the minimum average error with statistical significance.
Instance reduction methods are popular methods used in
machine learning and data mining that reduce the size of
the datasets to possibly improve the classification
accuracy of the classification algorithms
In this paper we consider approach that partitions the dataset into training partitions Sk for k = 1:::9 and a validation partition V to compute the sum of minimum distances between the validation partition V and each training partition Sk. We then construct reduced training set Z by selecting the training partitions that are less than the pth percentile of all the training partitions for specific p value. The goal is to select the training partitions that contain similar instances to the validation instances and remove those with dissimilar instances. The idea behind the strategy is that instances dissimilar with validation instances will have little, if not adverse, effect on predicting validation instances, and thus can be removed with little, if not positive, effect on classification. An example in real life is that a professor gives students a take-home exam (i.e. validation set without labels) and students will look for chapters (i.e. training partitions) of the book (i.e. training set) which contain similar information (i.e. instances of the training partitions) to the exam questions (i.e. instances of the validation set) and skip irrelevant chapters. For given reduced training set Z the prediction is given by using 1NN(Equation 1). Compared to other popular instance reduction methods our experimental evaluation on 30 datasets shows that our method IPRed yields the minimum average error with statistical significance.
The rest of this paper is organized as follows. In section II we review related work. In section III we present our method IPRed. Following that we present experimental evaluation and discussion before concluding.
The CNN outlined in Algorithm 1 works as
follows
Algorithm 1 Condensed Nearest Neighbor algorithm (CNN) 1: CNN(S,Z) 2: Z ; 3: P re add 4: do 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15:
1 add 0 for all instances in training set S do
Randomly select x from S Find zc 2 Z such that D(x; zc) = minj D(x; zj ) if label(x) 6= label(zc) then
Z Z [ x add 1 end if end for while (P re add == add) return (Z)
The reduced nearest neighbor(RNN)
The generalized condensed nearest neighbor(GCNN)
As shown in Algorithm 2 the DP algorithm receives as an input a dataset D 2 Rk d+1 of size k where the label associated to the instance xk 2 Rd is yk(line 1). In line 2 we divide the dataset size k by 10 and take the floor of the result. Lines 3-4 initialize the variables. The for loop of lines 5-18 creates 9 training partitions Pk for k = 1:::9 by taking subsamples without replacement from dataset D where the size of each Pk is the same. The for loop of lines 20-28 creates the validation partition V1 by taking the remaining subsamples without replacement from the dataset D. Line 29 assigns the 9 training partitions to S. In line 30 we assign the validation partition V1 to V . In line 31 our algorithm outlined in Algorithm 3 is called by taking partitions in S and V as inputs. IPRed algorithm outputs a training set Z of reduced size to guide the 1NN algorithm for better classification performance on the validation set V . The IPRed algorithm which is outlined in Algorithm 3 works as follows. Line 2 stores the size of the validation partition V1. The for loop of lines 3-12 iterates 9 times to store the sum of the minimum euclidean distances(line 11) between the partitions as follows. At each iteration of the for loop of lines 5-10 we store the computed euclidean distances(line 7) between the nth instance in V1[n; j] and each instance i in the kth partition Pk[i; j] for i = 1:::p size and j = 1:::d(for loop of lines 6-8).
Algorithm 2 Dataset Partitioning algorithm (DP) 1: DP(D = f(x1; y1); :::; (xk; yk)g) 2: size b 1k0 c 3: b 1 4: c size 5: for k = 1 to 9 do 6: q 1 7: r 1 8: for i = b to size do 9: for j = 1 to d do 10: Pk[q; r] x[i; j] 11: r r + 1 12: end for 13: Pk[q; r] y[i] 14: q q + 1 15: end for 16: b b + c 17: size size + c 18: end for 19: q 1 20: for i = b to k do 21: r 1 22: for j = 1 to d do 23: V1[q; r] x[i; j] 24: r r + 1 25: end for 26: V1[q; r] y[i] 27: q q + 1 28: end for 29: S fP1; P2; :::; P9g 30: V fV1g 31: Z IP Red(S; V ) We then store the minimum distance(line 9). After the for loop of lines 5-10 terminates, we store the sum of the minimum distances between the kth partition Pk and V1(line 11). Thus, the for loop of lines 3-12 iterates 9 times to store the results for the 9 training partitions(line 11). In line 13 we use the percentile as a robust measurement of the location of the data to store the 75th percentile of all training partitions. Line 14 initializes j to 1. The for loop of lines 15-20 selects the ith training partition that is less than 75th percentile of all training partitions for i = 1:::9. We store the index of the ith training partition that satisfies the condition(line 16) in P artitions index(line 17). After the for loop of lines 22-31 terminates we return the reduced training set Z(line 32) which contains the selected training partitions in P artitions index. Prediction on the validation set V is given by 1NN(Equation 1) using Z.
Algorithm 3 IPRed algorithm
We experimentally evaluate the performance of our instance
reduction algorithm and compare it against others from a
classification perspective
Code Dataset Classes Dimensions Instances methodology, then presents the experimental results.
We use 30 real datasets in our experiments for classification.
The information on datasets is tabulated in Table 1 which
are ordered in terms of increasing number of instances. The
datasets are obtained from three different sources. The
appendicitis and saheart are obtained from KEEL-dataset
repository
We evaluate four classification algorithms: IPRed+1NN, CNN+1NN, RNN+1NN, and 1NN where the four algorithms are 1-nearest neighbor applied to IPRed, 1-nearest neighbor applied to condensed nearest neighbor, 1-nearest neighbor applied to reduced nearest neighbor, and 1-nearest neighbor respectively. We use the 10-fold cross-validation on each dataset ensuring the same splits for each algorithm. For each instance reduction method we reduce the size k on the original training set from S 2 Rk d+1 to Z 2 Rk0 d+1 where k0 < k . We then apply 1NN for the given Z on the validation set. Recall that 1NN is given by y0 = argmax I (r = y1)(Equation 1). We wrote our code in r % % %
For each training-validation split in our classifications tasks we measure the error on the validation split as the number of instances incorrectly predicted divided by the number of instances. We then take the average result of 10 folds to be average cross-validation error. For each dataset we measure the storage percentage as the number of instances in the reduced training set divided by the number of instances in the training set and take the average result of 10 trials in the cross-validation to be average storage percentage. In Table 2 we tabulate average cross-validation error and average storage percentage % results on each dataset.
Over the 30 datasets IPRed+1NN yields the minimum average error of 24.701% and has the minimum error in 14 out of 30 datasets. The second best is 1NN that gives an average error of 25.662% and has the minimum error in 6 out of 30 datasets. The third best is CNN+1NN that gives higher average error of 27.253% and has the minimum error in 1 out of 30 datasets. RNN+1NN gives an average error of 27.92% and has the minimum error in 2 out of 30 datasets. RNN+1NN has the best average storage requirements of 32.3585%. The second best is CNN+1NN that gives average storage requirements of 36.0894%. The third best is IPRed which gives average storage requirements of 60.1881%. 1NN uses the original training set. Thus, 1NN gives average storage requirements of 100%.
To verify that differences in classification accuracy on
the datasets are statistically significant we use Wilcoxon
rank test
IPRed+1NN divides the training set into 9 partitions each of the same size. For each training partition obtained from the training set we store the sum of the minimum distances between the training partition and the validation partition. We then construct the reduced dataset from the selected training partitions that are less than 75th percentile of all the training partitions. Finally, we measure the performance of 1NN on the validation set using the given reduced training set. This approach outperforms CNN+1NN and RNN+1NN in terms of accuracy(results shown in Table 2 and Table 3).
In this study we chose 1NN as a classification algorithm
due to its popularity and its efficiency for CNN and RNN
algorithms. Other classifiers such as support vector
machine(SVM) can be used which may outperform 1NN.
However, optimizing SVM by performing cross-validation to
select the best parameters increases the runtime. IPRed+1NN
gives higher average storage percentage than CNN+1NN
and RNN+1NN on the datasets except for steel plates faults
and contraceptive datasets(results shown in Table 3). Thus,
It is the slowest algorithm in the conducted experiments
but still computationally tractable for the large real
datasets. However, It gives better classification accuracy than the
other methods most of the time. We used the standard
package for CNN+1NN and RNN+1NN in R
We present instance reduction algorithm based on the percentile of the partitions that outputs dataset of reduced size used by 1-nearest neighbor algorithm for classification. Our algorithm leads to better classification performance than the other popular methods by obtaining the minimum average error with statistical significance on many real datasets.