# Combining Prototype Selection with Local Boosting

Christos K. Aridas, Sotiris B. Kotsiantis, Michael N. Vrahatis

► To cite this version:

Christos K. Aridas, Sotiris B. Kotsiantis, Michael N. Vrahatis. Combining Prototype Selection with Local Boosting. 12th IFIP International Conference on Artificial Intelligence Applications and Innovations (AIAI), Sep 2016, Thessaloniki, Greece. pp.94-105, 10.1007/978-3-319-44944-9_9. hal-01557610

HAL Id: hal-01557610

https://inria.hal.science/hal-01557610

Submitted on 6 Jul 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Combining Prototype Selection with Local Boosting

Christos K. Aridas, Sotiris B. Kotsiantis, and Michael N. Vrahatis

Department of Mathematics
University of Patras
GR-26110 Patras, Greece
{char,sotos,vrahatis}@math.upatras.gr

**Abstract.** Real life classification problems require an investigation of relationships between features in heterogeneous data sets, where different predictive models can be more proper for different regions of the data set. A solution to this problem is the application of the local boosting of weak classifiers ensemble method. A main drawback of this approach is the time that is required at the prediction of an unseen instance as well as the decrease of the classification accuracy in the presence of noise in the local regions. In this research work, an improved version of the local boosting of weak classifiers, which incorporates prototype selection, is presented. Experimental results on several benchmark real-world data sets show that the proposed method significantly outperforms the local boosting of weak classifiers in terms of predictive accuracy and the time that is needed to build a local model and classify a test instance.

**Keywords:** local boosting, weak learning, prototype selection; pattern classification

## 1 Introduction

In machine learning, instance-based (or memory-based) learners classify an un-
seen object by comparing it to a database of pre-classified objects. The funda-
mental assumption is that similar instances will share similar class labels.

Machine learning models' assumptions would not necessarily hold globally. Local learning [1] methods come to solve this problem. The latter allow to extend learning algorithms, that are designed for simple models, to the case of complex data, for which the models' assumptions are valid only locally. The most common case is the assumption of linear separability, which is usually not fulfilled globally in classification problems. Despite this, any supervised learning algorithm that is able to find only a linear separation, can be used inside a local learning process, producing a model that is able to model complex non-linear class boundaries.

A technique of boosting local weak classifiers, that is based on a reduced training set after the usage of prototype selection [11], is proposed. It is common that boosting algorithms are well-known to be susceptible to noise [2]. In the case of local boosting, the algorithm should manage reasonable noise and be at least
as good as boosting, if not better. For the experiments, we used two variants
of Decision Trees [21] as weak learning models: one-level Decision Trees, which
are known as Decision Stumps [12] and two-level Decision Trees. An extensive
comparison over several data sets was performed and the results show that the
proposed method outperforms simple and local boosting in terms of classification
accuracy.

In the next Section, specifically in subsection 2.1, the localized experts are discussed, while boosting approaches are described in subsection 2.2. In Section 3 the proposed method is presented. Furthermore, in Section 4 the results of the experiments on several UCI data sets, after being compared with standard boosting and local boosting, are portrayed and discussed. Finally, Section 5 concludes the paper and suggests further directions in current research.

## 2 Background Material

For completeness purposes, local weighted learning, prototype selection methods
as well as boosting classifier techniques are briefly described in the following
subsections.

2.1 Local Weighted Learning and Prototype Selection

Supervised learning algorithms are considered global if they use all available
training sets, in order to build a single predictive model, that will be applied
in any unseen test instance. On the other hand, a method is considered local if
only the nearest training instances around the testing instance contribute to the
class probabilities.

When the size of the training data set is small in contrast to the complexity
of the classifier, the predictive model frequently overfits the noise in the train-
ing data. Therefore, the successful control of the complexity of a classifier has a
high impact in accomplishing good generalization. Several theoretical and exper-
imental results [23] indicate that a local learning algorithm provides a reasonable
solution to this problem.

In local learning [1], each local model is built completely independent of all
other models in a way that the total number of local models in the learning
method indirectly influences how complex a function can be estimated - com-
plexity can only be controlled by the level of adaptability of each local model.
This feature prevents overfitting if a strong learning pattern exists for training
each local model.

Prototype selection is a technique that aims to decrease the training size
without surfacing the prediction performance of a memory based learner [18].
Besides this, by reducing the training set size it might decrease the computational
cost that will be applied in the prediction phase.

Prototype selection techniques can be grouped in three categories: preserva-
tion techniques, which aim to find a consistent subset from the training data set,
ignoring the presence of noise, noise removal techniques, which aim to remove
noise, and hybrid techniques, which perform both objectives concurrently [22].
## 2.2 Boosting Classifiers

Experimental research works have proven that ensemble methods usually perform better, in terms of classification accuracy, than the individual base classifier [2], and lately, several theoretical explanations have been advised to explain the success of some commonly used ensemble methods [13]. In this work, a local boosting technique that is based on a reduced training set, after the usage of prototype selection [11], is proposed and for this reason this section introduces the boosting approach.

Boosting constructs the ensemble of classifiers by subsequently tweaking the distribution of the training set based on the accuracy of the previously created classifiers. There are several boosting variants. These methods assign a weight to each training instance. Firstly, all instances are equally weighted. In each iteration a new classification model, named base classifier, is generated using the base learning algorithm. The creation of the base classifier has to consider the weight distribution. Then, the weight of each instance is adjusted, depending on the accuracy of the prediction of the base classifier for that instance. Thus, Boosting attempts to construct new classification models that are able to better classify the “hard” instances for the previous ensemble members. The final classification is obtained from a weighted vote of the base classifiers. AdaBoost [8] is the most well-known boosting method and the one that is used over the experimental analysis that is presented in Section 3.

Adaboost is able to use weights in two ways to generate a new training data set to provide to the base classifier. In boosting by sampling, the training instances are sampled with replacement with probability relative to their weights. In [26] authors showed empirically that a local boosting-by-resampling technique is more robust to noise than the standard AdaBoost. The authors of [17] proposed a Boosted k-NN algorithm that creates an ensemble of models with locally modified distance weighting that has increased generalization accuracy and never performs worse than standard k-NN. In [10] the authors present a novel method for instance selection based on boosting instance selection algorithms in the same way boosting is applied to classification.

# 3 The Proposed Algorithm

Two main disadvantages of simple local boosting are: i) When the amount of noise is large, simple local boosting does not have the same performance [26] as Bagging [3] and Random Forest [4]. ii) Saving the data for each pattern increases storage complexity. This might restrict the use of this method to limited training sets [21]. The proposed algorithm incorporates prototype selection to handle, among others, the two previous problems. In the learning phase, a prototype selection [11] method based on the Edited Nearest Neighbor (ENN) [24] technique reduces the training set by removing the training instances that do not agree with the majority of the k nearest neighbors. In the application phase, it constructs a model for each test instance to be estimated, considering only a subset of the training instances. This subset is selected according to the distance
between the testing sample and the available training samples. For each testing instance, a boosting ensemble of a weak learner is built using only the training instances that are lying close to the current testing instance. The prototype selection aims to improve the classification accuracy as well as the time that is needed to build a model for each test instance at the prediction.

The proposed ensemble method has some free parameters, such as the number of neighbors ($k_1$) to be considered when the prototype selection is executed, the number of neighbors ($k_2$) to be selected in order to build the local model, the distance metric and the weak learner. In the experiments, the most well-known Euclidean similarity function was used as a distance metric.

In general, the distance between points x and y in a Euclidean space $R^n$ is given by (1).

$$d(x, y) = \|x - y\|_2 = \sqrt{\sum_{i=1}^{n} |x_i - y_i|^2} \quad (1)$$

The most common value for the nearest neighbor rule is 5. Thus, the $k_1$ was set to 5 and $k_2=50$. since at about this size of instances, it is appropriate for a simple algorithm to build a precise model [14]. The proposed method is presented in Algorithm 1.

<caption>**Algorithm 1 PSLB(k₁, k₂, distanceMetric, weakLearner)**</caption>

procedure TRAINING(k₁, distanceMetric)
    for each training instance do
        Find the k₁ nearest neighbors using the selected distanceMetric
        if instance does not agree with the majority of the k₁ then
            Remove this instance from the training set
        end if
    end for
end procedure
procedure CLASSIFICATION(k₂, distanceMetric, weakLearner)
    for each testing instance do
        Find the k₂ nearest neighbors using the selected distanceMetric
        Apply boosting to the base weakLearner using the k₂ nearest neighbors
        The answer of the boosting ensemble is the prediction for the testing instance
    end for
end procedure

# 4 Numerical Experiments

In order to evaluate the performance of the proposed method, an initial version was implemented<fnref n="1" /> and a number of experiments were conducted using several

<footnote n="1">¹ https://bitbucket.org/chkoar/pslb</footnote>
data sets from different domains. From the UCI repository [16] several data sets were chosen. Discrete features transformed to numeric by using a simple quantization. Each feature is scaled to have zero mean and standard deviation one. Also all missing values were treated as zero. In Table 1 the name, the number of patterns, the attributes, as well as the number of different classes for each data set are shown.

<table><caption>**Table 1.** Benchmark data sets used in the experiments</caption><thead><tr><th>Data Set</th><th>#patterns</th><th>#attribuies</th><th>#classes</th></tr></thead><tbody><tr><td>cardiotocography</td><td>2126</td><td>21</td><td>10</td></tr><tr><td>cylinder-bands</td><td>512</td><td>25</td><td>2</td></tr><tr><td>dermatology</td><td>366</td><td>24</td><td>6</td></tr><tr><td>ecoli</td><td>336</td><td>7</td><td>8</td></tr><tr><td>energy-y1</td><td>768</td><td>8</td><td>3</td></tr><tr><td>glass</td><td>214</td><td>9</td><td>6</td></tr><tr><td>low-res-spect</td><td>531</td><td>100</td><td>9</td></tr><tr><td>magic</td><td>19020</td><td>10</td><td>2</td></tr><tr><td>musk-1</td><td>476</td><td>166</td><td>2</td></tr><tr><td>ozone</td><td>2536</td><td>72</td><td>2</td></tr><tr><td>page-blocks</td><td>5473</td><td>10</td><td>5</td></tr><tr><td>pima</td><td>768</td><td>8</td><td>2</td></tr><tr><td>synthetic-control</td><td>600</td><td>60</td><td>6</td></tr><tr><td>tic-tac-toe</td><td>958</td><td>9</td><td>2</td></tr></tbody></table>

All experiments were run on an Intel Core i3-3217U machine at 1.8GHz, with 8GB of RAM, running Linux Mint 17.3 64bit using Python and the scikit-learn [19] library.

For the experiments, we used two variants of Decision Trees [25] as weak learners. One-level Decision Trees [12], also known as Decision Stumps, and two-level Decision Trees [20]. We used the Gini Impurity [5] as criterion to measure the quality of the splits in both algorithms. The boosting process for all classifiers performed using the AdaBoost algorithm with 25 iterations in each model. In order to calculate the classifiers accuracy, the whole data set was divided into five mutually exclusive folds and for each fold the classifier was trained on the union of all of the other folds. Then, cross-validation was run five times for each algorithm and the mean value of the five folds was calculated.

## 4.1 Prototype Selection

The prototype selection process is independent of the base classifier and it takes place once in the training phase of the proposed algorithm. It depends only on the $k_1$ parameter. The number of neighbors to be considered when the prototype selection is executed. In Table 2 the average of training patterns, the average of the removed patterns as well as the average reduction of each data set is
presented. The average refers to the average of all training folds during the 5-fold cross-validation.

<table><caption>**Table 2.** Average reduction</caption><thead><tr><th>Dataset</th><th>#avg training patterns</th><th>#avg removed patterns</th><th>%avg reduction</th></tr></thead><tbody><tr><td>cardiotocography</td><td>1701</td><td>268</td><td>15,73</td></tr><tr><td>cylinder-bands</td><td>410</td><td>60</td><td>14,60</td></tr><tr><td>dermatology</td><td>293</td><td>7</td><td>02,53</td></tr><tr><td>ecoli</td><td>269</td><td>29</td><td>10,86</td></tr><tr><td>energy-y1</td><td>614</td><td>17</td><td>02,77</td></tr><tr><td>glass</td><td>171</td><td>40</td><td>23,13</td></tr><tr><td>lowresspect</td><td>425</td><td>47</td><td>11,11</td></tr><tr><td>magic</td><td>15216</td><td>1798</td><td>11,81</td></tr><tr><td>musk-1</td><td>381</td><td>24</td><td>06,25</td></tr><tr><td>ozone</td><td>2029</td><td>50</td><td>02,48</td></tr><tr><td>page-blocks</td><td>4378</td><td>111</td><td>02,53</td></tr><tr><td>pima</td><td>614</td><td>109</td><td>17,77</td></tr><tr><td>synthetic-control</td><td>480</td><td>8</td><td>01,67</td></tr><tr><td>tic-tac-toe</td><td>766</td><td>1</td><td>00,13</td></tr></tbody></table>

## 4.2 Using Decision Stump as base classifier

In the first part of the experiments, Decision Stumps [12] were used as weak learning classifiers. Decision Stumps (DS) are one-level Decision Trees that classify instances based on the value of just a single input attribute. Each node in a decision stump represents a feature in an instance to be classified and each branch represents a value that the node can take. Instances are classified starting at the root node and are sorted based on their attribute values. In the worst case, a Decision Stump will behave as a base line classifier and will possibly perform better, if the selected attribute is particularly informative.

The proposed method, denoted as PSLBDS, is compared with the Boosting Decision Stumps, denoted as BDS and the Local Boosting of Decision Stumps, denoted as LBDS. Since the proposed method uses fifty neighbors, a 50-Nearest Neighbors (50NN) classifier has included in the comparisons. In Table 3 the average accuracy of the compared methods is presented. Table 3 indicates that the hypotheses generated by PSLBDS are apparently better since the PSLBDS algorithm has the best mean accuracy score in nearly all cases.

Demšar [6] suggests that the non-parametric tests should be preferred over the parametric in the context of machine learning problems, since they do not assume normal distributions or homogeneity of variance. Therefore, in the direction of validating the significance of the results, the Friedman test [9], which is a rank-based non-parametric test for comparing several machine learning algorithms on multiple data sets, was used, having as a control method the PSLBDS
<table><caption>**Table 3.** Average accuracy of the compared algorithms using an one-level decision tree as base classifier</caption><thead><tr><th>Data set</th><th>PSLBDS</th><th>BDS</th><th>LBDS</th><th>50NN</th></tr></thead><tbody><tr><td>cardiotocography</td><td><strong>0.682</strong>±0.028</td><td>0.548±0.088</td><td>0.659±0.015</td><td>0.607±0.029</td></tr><tr><td>cylinder-bands</td><td><strong>0.613</strong>±0.030</td><td>0.560±0.037</td><td>0.584±0.014</td><td>0.582±0.017</td></tr><tr><td>dermatology</td><td><strong>0.942</strong>±0.027</td><td>0.641±0.142</td><td>0.940±0.022</td><td>0.902±0.020</td></tr><tr><td>ecoli</td><td><strong>0.821</strong>±0.029</td><td>0.622±0.129</td><td>0.794±0.026</td><td>0.780±0.050</td></tr><tr><td>energy-y1</td><td><strong>0.844</strong>±0.090</td><td>0.706±0.050</td><td>0.836±0.092</td><td>0.822±0.091</td></tr><tr><td>glass</td><td><strong>0.582</strong>±0.085</td><td>0.285±0.094</td><td>0.568±0.065</td><td>0.446±0.169</td></tr><tr><td>low-res-spect</td><td>0.850±0.025</td><td>0.584±0.069</td><td>0.846±0.012</td><td><strong>0.851</strong>±0.023</td></tr><tr><td>magic</td><td><strong>0.849</strong>±0.005</td><td>0.828±0.005</td><td>0.834±0.005</td><td>0.828±0.004</td></tr><tr><td>musk-1</td><td><strong>0.727</strong>±0.096</td><td><strong>0.727</strong>±0.052</td><td>0.718±0.085</td><td>0.618±0.096</td></tr><tr><td>ozone</td><td>0.966±0.008</td><td>0.960±0.010</td><td>0.887±0.133</td><td><strong>0.971</strong>±0.001</td></tr><tr><td>page-blocks</td><td><strong>0.954</strong>±0.012</td><td>0.853±0.163</td><td>0.950±0.013</td><td>0.942±0.007</td></tr><tr><td>pima</td><td><strong>0.757</strong>±0.028</td><td>0.755±0.024</td><td>0.685±0.024</td><td>0.749±0.017</td></tr><tr><td>synthetic-control</td><td><strong>0.947</strong>±0.011</td><td>0.472±0.074</td><td>0.943±0.020</td><td>0.887±0.030</td></tr><tr><td>tic-tac-toe</td><td><strong>0.884</strong>±0.084</td><td>0.733±0.034</td><td>0.882±0.083</td><td>0.747±0.101</td></tr></tbody></table>

algorithm. The null hypothesis of the test states that all the methods perform equivalently and thus their ranks should be equivalent. The average rankings, according to the Friedman test, are presented in Table 4.

<table><caption>**Table 4.** Average rankings of Friedman test (DS)</caption><thead><tr><th>Algorithm</th><th>Ranking</th></tr></thead><tbody><tr><td>PSLBDS</td><td>1.1429</td></tr><tr><td>LBDS</td><td>2.4286</td></tr><tr><td>50NN</td><td>2.8571</td></tr><tr><td>BDS</td><td>3.5714</td></tr><tr><td>Statistic</td><td>26.228571</td></tr><tr><td>p-value</td><td>0.000009</td></tr></tbody></table>

Assuming a significance level of 0.05 in Table 4, the *p*-value of the Friedman test indicates that the null hypothesis has to be rejected. So, there is at least one method that performs statistically different from the proposed method. With the intention of investigating the aforementioned, Finner's [7] and Li's [15] post hoc procedures were used.

In Table 5 the *p*-value obtained by applying post hoc procedures over the results of the Friedman statistical test are presented. Finner's and Li's procedure rejects those hypotheses that have a *p*-value ≤ 0.05. That said, the adjusted *p*-values obtained through the application of the post hoc procedures are presented in Table 6. Hence, both post hoc procedures agree that the PSLBDS algorithm performs significantly better than the BDS, the LBDS as well as the 50NN rule.
<table><caption>**Table 5.** Post hoc comparison for the Friedman Test (DS)</caption><thead><tr><th>i</th><th>Algorithm</th><th>z = (R<sub>0</sub> - R<sub>i</sub>)/SE</th><th>p</th><th>Finner</th><th>Li</th></tr></thead><tbody><tr><td>3</td><td>BDS</td><td>4.97709</td><td>0.000001</td><td>0.016952</td><td>0.052189</td></tr><tr><td>2</td><td>50NN</td><td>3.51324</td><td>0.000443</td><td>0.033617</td><td>0.052189</td></tr><tr><td>1</td><td>LBDS</td><td>2.63493</td><td>0.008415</td><td>0.05</td><td>0.05</td></tr></tbody></table>

<table><caption>**Table 6.** Adjusted p-values (DS)</caption><thead><tr><th>i</th><th>Algorithm</th><th>p<sub>Unadjusted</sub></th><th>p<sub>Finner</sub></th><th>p<sub>Li</sub></th></tr></thead><tbody><tr><td>3</td><td>BDS</td><td>0.000001</td><td>0.000002</td><td>0.000001</td></tr><tr><td>2</td><td>50NN</td><td>0.000443</td><td>0.000664</td><td>0.000446</td></tr><tr><td>1</td><td>LBDS</td><td>0.008415</td><td>0.008415</td><td>0.008415</td></tr></tbody></table>

## 4.3 Using two-level Decision Tree as a base classifier

Afterwards, two-level Decision Trees were used as weak learning base classifiers. A two-level Decision Tree is a tree with max depth=2. The proposed method, denoted as PSLBDT, is compared to the Boosting Decision Tree, denoted as BDT and the Local Boosting of Decision Trees, denoted as LBDT. Since the proposed method uses fifty neighbors a 50-Nearest Neighbors (50NN) classifier has included in the comparisons. In Table 7 the average accuracy of the compared methods is presented. Table 7 indicates that the hypotheses generated by PSLBDT are apparently better, since the PSLBDT algorithm has the best mean accuracy score in most cases.

<table><caption>**Table 7.** Average accuracy of the compared algorithms using a two-level decision tree as base classifier</caption><thead><tr><th>Data set</th><th>PSLBDT</th><th>BDT</th><th>LBDT</th><th>50NN</th></tr></thead><tbody><tr><td>cardiotocography</td><td>0.683±0.020</td><td>0.584±0.072</td><td><strong>0.686±0.017</strong></td><td>0.607±0.029</td></tr><tr><td>cylinder-bands</td><td><strong>0.609±0.049</strong></td><td>0.608±0.034</td><td>0.564±0.025</td><td>0.582±0.017</td></tr><tr><td>dermatology</td><td><strong>0.958±0.040</strong></td><td>0.800±0.041</td><td>0.951±0.020</td><td>0.902±0.020</td></tr><tr><td>ecoli</td><td><strong>0.813±0.032</strong></td><td>0.753±0.036</td><td>0.800±0.030</td><td>0.780±0.050</td></tr><tr><td>energy-y1</td><td><strong>0.845±0.060</strong></td><td>0.830±0.064</td><td>0.844±0.071</td><td>0.822±0.091</td></tr><tr><td>glass</td><td>0.608±0.048</td><td>0.569±0.112</td><td><strong>0.652±0.057</strong></td><td>0.446±0.169</td></tr><tr><td>low-res-spect</td><td><strong>0.877±0.042</strong></td><td>0.573±0.136</td><td>0.872±0.023</td><td>0.851±0.023</td></tr><tr><td>magic</td><td>0.849±0.006</td><td><strong>0.856±0.007</strong></td><td>0.841±0.006</td><td>0.828±0.004</td></tr><tr><td>musk-1</td><td>0.738±0.072</td><td><strong>0.752±0.024</strong></td><td>0.746±0.074</td><td>0.618±0.096</td></tr><tr><td>ozone</td><td>0.967±0.008</td><td>0.925±0.064</td><td>0.888±0.132</td><td><strong>0.971±0.001</strong></td></tr><tr><td>page-blocks</td><td><strong>0.960±0.010</strong></td><td>0.924±0.023</td><td>0.956±0.010</td><td>0.942±0.007</td></tr><tr><td>pima</td><td><strong>0.763±0.023</strong></td><td>0.742±0.014</td><td>0.730±0.018</td><td>0.749±0.017</td></tr><tr><td>synthetic-control</td><td>0.950±0.011</td><td>0.830±0.036</td><td><strong>0.953±0.016</strong></td><td>0.887±0.030</td></tr><tr><td>tic-tac-toe</td><td><strong>0.893±0.078</strong></td><td>0.665±0.126</td><td>0.889±0.081</td><td>0.747±0.101</td></tr></tbody></table>

The average rankings, according to the Friedman test, are presented in Table 8. The proposed algorithm was ranked in the first place again. Assuming
significance level of 0.05 in Table 8, the *p*-value of the Friedman test indicates that the null hypothesis has to be rejected. So, there is at least one method that performs statistically different from the proposed method. Aiming to investigate the aforesaid, Finner's and Li's post hoc procedures were used again.

<table><caption>**Table 8.** Average rankings of Friedman test (two-level Tree)</caption><thead><tr><th>Algorithm</th><th>Ranking</th></tr></thead><tbody><tr><td>PSLBDT</td><td>1.5</td></tr><tr><td>LBDT</td><td>2.2857</td></tr><tr><td>50NN</td><td>3.0714</td></tr><tr><td>BDT</td><td>3.1429</td></tr><tr><td>Statistic</td><td>15</td></tr><tr><td><i>p</i>-value</td><td>0.001817</td></tr></tbody></table>

In Table 9 the *p*-value obtained by applying post hoc procedures over the results of Friedman's statistical test are presented. Finner's and Li's procedure rejects those hypotheses that have a *p*-value ≤ 0.05. That said, the adjusted *p*-values obtained through the application of the post hoc procedures are presented in Table 10. Both post hoc procedures agree that the PSLBDT algorithm performs significantly better than the BDT and the 50NN rule but not significantly better than the LBDT as far as the tested data sets are concerned.

<table><caption>**Table 9.** Post hoc comparison for the Friedmans Test (two-level Tree)</caption><thead><tr><th><i>i</i></th><th>Algorithm</th><th><i>z</i> = (<i>R</i><sub>0</sub> − <i>R</i><sub><i>i</i></sub>)/SE</th><th><i>p</i></th><th>Finner</th><th>Li</th></tr></thead><tbody><tr><td>3</td><td>BDT</td><td>3.366855</td><td>0.00076</td><td>0.016952</td><td>0.046982</td></tr><tr><td>2</td><td>50NN</td><td>3.22047</td><td>0.00128</td><td>0.033617</td><td>0.046982</td></tr><tr><td>1</td><td>LBDT</td><td>1.610235</td><td>0.107347</td><td>0.05</td><td>0.05</td></tr></tbody></table>

<table><caption>**Table 10.** Adjusted *p*-values (two-level Tree)</caption><thead><tr><th><i>i</i></th><th>Algorithm</th><th><i>p</i><sub>Unadjusted</sub></th><th><i>p</i><sub>Finner</sub></th><th><i>p</i><sub>Li</sub></th></tr></thead><tbody><tr><td>3</td><td>BDT</td><td>0.00076</td><td>0.002279</td><td>0.000851</td></tr><tr><td>2</td><td>50NN</td><td>0.00128</td><td>0.002279</td><td>0.001432</td></tr><tr><td>1</td><td>LBDT</td><td>0.107347</td><td>0.107347</td><td>0.107347</td></tr></tbody></table>

## 4.4 Time Analysis

One of the two contributions of this study was to improve the classification time over the local boosting approach. In order to prove this, the total time that is
required to predict all instances in the test folds was recorded. Specifically, the prediction of each test fold was executed three times and the minimum time was recorded for each fold. Then, the average of all folds was calculated. In Table 11 the average prediction time in seconds of LBDS, PSLBDS, LBDT and PSLBDTS is presented. In the case of one-level decision trees (LBDS, PSLBDS) the proposed method reduced the expected prediction time in more than 15% in 6 of 14 cases, while in the case of two-level decision trees (LBDT, PSLBDT) the proposed method reduced the expected prediction time in more than 15% in 7 of 14 cases. In Figure 1 the absolute percentage changes are presented.

<table><caption>**Table 11.** Average prediction times, in seconds</caption><thead><tr><th>Data set</th><th>LBDS</th><th>PSLBDS</th><th>LBDT</th><th>PSLBDT</th></tr></thead><tbody><tr><td>cardiotocography</td><td>33.89</td><td>33.26</td><td>32.43</td><td>29.20</td></tr><tr><td>cylinder-bands</td><td>8.16</td><td>8.07</td><td>8.45</td><td>7.86</td></tr><tr><td>dermatology</td><td>3.56</td><td>3.52</td><td>3.28</td><td>3.20</td></tr><tr><td>ecoli</td><td>5.00</td><td>3.61</td><td>4.66</td><td>2.92</td></tr><tr><td>energy-y1</td><td>8.58</td><td>7.19</td><td>7.59</td><td>6.25</td></tr><tr><td>glass</td><td>3.39</td><td>3.37</td><td>3.46</td><td>3.16</td></tr><tr><td>low-res-spect</td><td>6.74</td><td>6.38</td><td>5.77</td><td>3.77</td></tr><tr><td>magic</td><td>257.14</td><td>160.31</td><td>213.59</td><td>107.98</td></tr><tr><td>musk-1</td><td>9.53</td><td>9.50</td><td>8.80</td><td>7.99</td></tr><tr><td>ozone</td><td>14.84</td><td>4.89</td><td>7.24</td><td>1.69</td></tr><tr><td>page-blocks</td><td>17.27</td><td>9.34</td><td>12.28</td><td>4.27</td></tr><tr><td>pima</td><td>11.72</td><td>8.90</td><td>11.07</td><td>7.56</td></tr><tr><td>synthetic-control</td><td>6.32</td><td>6.12</td><td>3.89</td><td>3.76</td></tr><tr><td>tic-tac-toe</td><td>13.56</td><td>13.56</td><td>12.18</td><td>12.00</td></tr></tbody></table>

# 5 Synopsis and Future Work

Local memory-based techniques delay the processing of the training set until they receive a request for an action like classification or local modelling. A data set of observed training examples is always retained and the estimate for a new test instance is obtained from an interpolation based on a neighborhood of the query instance.

In this research work at hand, a local boosting after prototype selection method is presented. Experiments on several data sets show that the proposed method significantly outperforms the boosting and local boosting method, in terms of classification accuracy and the time that is required to build a local model and classify a test instance. Typically, boosting algorithms are well known to be subtle to noise [2]. In the case of local boosting, the algorithm should handle sufficient noise and be at least as good as boosting, if not better. By means of the promising results obtained from performed experiments, one can assume that the proposed method can be successfully applied to the classification task
<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Percentage change of prediction time between Local Boosting and the proposed method</figcaption></figure>

in the real world case with more accuracy than the compared machine learning approaches.

In a following work the proposed method will be investigated as far as regression problems are concerned as well as the problem of reducing the size of the stored set of instances, by also applying feature selection instead of simple prototype selection.

## References

1. Atkeson, C.G., Schaal, S., Moore, A.W.: Locally weighted learning. Artificial Intelligence Review 11(1), 11–73 (1997)

2. Bauer, E., Kohavi, R.: An Empirical Comparison of Voting Classification Algorithms: Bagging, Boosting, and Variants. Machine Learning 36(1), 105–139 (1999)

3. Breiman, L.: Bagging predictors. Machine Learning 24(2), 123–140 (Aug 1996)

4. Breiman, L.: Random Forests. Machine Learning 45(1), 5–32 (2001)

5. Breiman, L., Friedman, J., Stone, C., Olshen, R.: Classification and regression trees. Chapman & Hall, New York (1993)

6. Demar, J.: Statistical Comparisons of Classifiers over Multiple Data Sets. J. Mach. Learn. Res. 7, 1–30 (2006)

7. Finner, H.: On a Monotonicity Problem in Step-Down Multiple Test Procedures. Journal of the American Statistical Association 88(423), 920–923 (Sep 1993)

8. Freund, Y., Schapire, R.E., others: Experiments with a new boosting algorithm. In: ICML. vol. 96, pp. 148–156 (1996)
9. Friedman, M.: The Use of Ranks to Avoid the Assumption of Normality Implicit in the Analysis of Variance. Journal of the American Statistical Association 32(200), 675 (Dec 1937)

10. Garca-Pedrajas, N., de Haro-Garca, A.: Boosting instance selection algorithms. Knowledge-Based Systems 67, 342–360 (Sep 2014)

11. Garcia, S., Derrac, J., Cano, J.R., Herrera, F.: Prototype Selection for Nearest Neighbor Classification: Taxonomy and Empirical Study. IEEE Transactions on Pattern Analysis and Machine Intelligence 34(3), 417–435 (Mar 2012)

12. Iba, W., Langley, P.: Induction of One-Level Decision Trees. In: Proceedings of the Ninth International Workshop on Machine Learning. pp. 233–240. ML ’92, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (1992)

13. Kleinberg, E.M.: A Mathematically Rigorous Foundation for Supervised Learning. In: Goos, G., Hartmanis, J., van Leeuwen, J. (eds.) Multiple Classifier Systems, vol. 1857, pp. 67–76. Springer Berlin Heidelberg, Berlin, Heidelberg (2000)

14. Kotsiantis, S.B., Kanellopoulos, D., Pintelas, P.E.: Local Boosting of Decision Stumps for Regression and Classification Problems. Journal of Computers 1(4) (Jul 2006)

15. Li, J.: A two-step rejection procedure for testing multiple hypotheses. Journal of Statistical Planning and Inference 138(6), 1521–1527 (Jul 2008)

16. Lichman, M.: UCI Machine Learning Repository (2013)

17. Neo, T.K.C., Ventura, D.: A direct boosting algorithm for the k-nearest neighbor classifier via local warping of the distance metric. Pattern Recognition Letters 33(1), 92–102 (Jan 2012)

18. Olvera-Lpez, J.A., Carrasco-Ochoa, J.A., Martnez-Trinidad, J.F., Kittler, J.: A review of instance selection methods. Artificial Intelligence Review 34(2), 133–143 (Aug 2010)

19. Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., Duchesnay, d.: Scikit-learn: Machine Learning in Python. J. Mach. Learn. Res. 12, 2825–2830 (Nov 2011)

20. Quinlan, J.R.: Induction of decision trees. Machine Learning 1(1), 81–106 (Mar 1986)

21. Rokach, L.: Ensemble-based classifiers. Artificial Intelligence Review 33(1-2), 1–39 (Feb 2010)

22. Segata, N., Blanzieri, E., Delany, S.J., Cunningham, P.: Noise reduction for instance-based learning with a local maximal margin approach. Journal of Intelligent Information Systems 35(2), 301–331 (Oct 2010)

23. Vapnik, V.N.: Statistical learning theory. Adaptive and learning systems for signal processing, communications, and control, Wiley, New York (1998)

24. Wilson, D.L.: Asymptotic Properties of Nearest Neighbor Rules Using Edited Data. IEEE Transactions on Systems, Man, and Cybernetics 2(3), 408–421 (1972)

25. Witten, I.H., Frank, E., Hall, M.A.: Data mining: practical machine learning tools and techniques. Morgan Kaufmann series in data management systems, Morgan Kaufmann, Burlington, MA, 3rd ed edn. (2011)

26. Zhang, C.X., Zhang, J.S.: A local boosting algorithm for solving classification problems. Computational Statistics & Data Analysis 52(4), 1928–1941 (Jan 2008)