Learning regression problems by using classifiers

Abstract

Regression via Classification (RvC) is a process to solve a regression problem by using a classifier. An ensemble consists of many models, in which the final result is the combination of the results of these individual models. In this paper, two RvC ensemble methods are proposed. In the first ensemble method, the output of the ensemble method is modified to achieve the final output. A formula is derived in this paper for this purpose. In the second method, a new approach is proposed to compute the output of each model of an ensemble. It is shown that an accurate binary classifier can be transformed into an accurate regression method with the proposed methods. It is also shown experimentally, by using popular Random Forests as a classifier in the proposed ensemble methods against Random Forests as a regression method, the effectiveness of the proposed RvC ensemble methods.

Keywords

Regression ensembles regression trees discretization Randomization

1 Introduction

Regression and classification are two areas of supervised learning, [5, 27]. Both estimate the relationship between a dependent variable and one or more independent variables. The difference between these two problems is that a regression problem has continuous dependent variable, whereas in a classification problem, the dependent variable has categories. There are many methods like Naive Bayes that can handle classification problems easily. Therefore, attempts have been made to solve regression problems by using classifiers [32, 33]. A regression problem can be solved by converting it into a classification problem by using discretization process, the process is called Regression via Classification process (RvC) [32, 33]. These methods have not become very popular as they don’t have any well-defined theory that can show that the particular RvC method will perform well. A very important parameter, the number of bins used to convert a continuous target to a categorical target is generally user defined. Hence, the results may change by changing this parameter.

Ensembles consist of many models [25]; each model contributes to the final result. Halawani et al. [20] suggest an ensemble technique for RvC problems. They show that these ensembles perform better than single model for a regression problem y = x when the number of bins is more than 2. However, their method cannot learn y = x problem accurately with a finite number of bins. Ahmad et al. [2] show that weighting schemes can improve the performance but the zero training error was not achieved with the weighting scheme. However, any solution has not been suggested that shows zero training error for RvC problems. Ahmad et al. [3] show that the model can also be used to show that regression tree ensembles that are created by total randomization process cannot learn y = x problem. In this paper, RvC ensembles are proposed that can learn all kinds of regression functions with accurate binary classifiers. Firstly, two ensemble methods for RvC problems for y = x regression functions are proposed. It is shown theoretically that with the two bins accurate results (zero training error) can be achieved. The proposed RvC ensembles can work with binary classifiers that can learn the decision boundaries created by the discretization process. It is also shown that these results are applicable to all the monotonically increasing or decreasing functions with one variable. It is proposed that these ensemble methods can work for all kinds of regression problems with two bins by using binary classifiers that can learn nonlinear decision boundaries. It is demonstrated that the proposed ensemble methods with Random Forests [7] as a classifier perform similar to or better than Random Forests as a regression method on a number of regression datasets. The similarity between RvC ensemble methods and ensembles of univariate regression trees (split the data only on the basis of a single attribute [9, 30]) is used to study the performance of ensembles of univariate regression trees.

The paper has following contributions;

Two novel RvC ensemble methods are proposed. The effectiveness of these methods is shown theoretically and experimentally. It is shown that an accurate binary classifier method can be used to create an accurate regression method.

In existing RvC ensemble methods, the number of bin is a parameter. The performance of these methods is strongly dependent on the number of bins. The proposed ensemble methods use two bins. In other words, the proposed ensemble methods do not use the number of bins as a parameter.

The proposed RvC ensemble methods can be used to study the performance of ensembles of finite sized univariate regression trees for monotonically increasing or decreasing functions of single variable.

In other words, there are two motivations of the proposed approach, first the proposed approach can have better performance accuracy than related regression method and the second that the proposed models can be used to study the performance of ensembles of finite sized univariate regression trees. The rest of the paper is organized as follows. Section 2 describes the related work. In Section 3, RvC ensemble methods are proposed for monotonically increasing or decreasing functions with one variable which use linear classifiers, like decision stumps as classifiers. Experimental results are also presented in this section. Section 4 describes our proposed RvC ensemble methods for all kinds of regression functions. Results are presented in Section 5. Section 6 has conclusion and future work.

2 Related work

A regression problem has the real-valued target variable, whereas in a classification problem the target variable has categories. A regression problem can be solved by using classifiers [32]. This process is called Regression via Classification (RvC).

The whole process of RvC comprises of two important steps:

Discretization divides the feature values or target values into different bins depending upon intervals they fall into. In the first step, the discretization of the numeric target variable of a regression problem is done to convert the output variable into bins that are treated as classes. Hence, a classifier can learn on the new discretized dataset. Various discretization methods e.g. equal-width, equal-frequency etc. [14] are available in the literature.

The reverse process transforms the class output of the classifier into a continuous value.

Torgo and Gama [33] present a search based approach for discretization step in RvC problems. Indurkhya and Weiss [22] use k-means clustering algorithm to discretize the output variable and solve the resultant classification problem. They use ensembles of decision-rule solutions for the classification problem. Frank and Bouckaert [15] compute conditional density estimates by using a class probability estimator, this estimator is applied to the discretized target variable. The number of bins is an important parameter in RvC problems [22, 23]. If the number of bin is small, it creates an easier classification problem, however, the final output (e.g. the mean of the points in the bins) has more error. The large number of bins make the classification problem very difficult. Hence, the performance of RvC problems is strongly dependent on this parameter. Ensembles of models are used to improve the accuracy of single model [25 , 34]. Accurate ensembles consist of many accurate and diverse models [25]. Halawani et al. [2, 20] propose ensemble methods for RvC problems. In these methods, the discretization process is done randomly, hence, different datasets are created. Models trained on these different datasets are diverse. The results of these models are combined to get the final result. Halawani et al. [2, 20] show that these ensemble methods outperform RvC method with equal width discretization method. In RvC ensemble methods proposed by Halawani et al. [2, 20] the number of bin is a parameter. The performance of RvC ensemble methods changes with this parameter.

In this paper, the RvC ensemble methods of Halawani et al. [2, 20] are extended, hence, these methods are discussed in detail.

2.1 RvC with extreme randomized discretization

Ahmad [1] present a discretization method, Extreme Randomized Discretization (ERD), for creating ensembles of decision trees. In ERD, bin boundaries for the discretization are created randomly. Ahmad et al. [2, 20] use ERD to propose an ensemble method for RvC. They use ERD in stage (i) of RvC. As it creates diverse datasets, diverse classifiers are created. These diverse datasets, in turn, produce diverse classifiers. The combination of these classifiers creates an ensemble. Ahmad et al. [2, 20] present the theoretical study of these ensembles. Ahmad et al. show that RvC ensembles with ERD cannot learn y = x regression problem with a finite number of bins. In y = x regression problem, a value of y is predicted by using a value of x and the value of y is equal to the value of x. However, they don’t present any solution to this problem. This work [2, 20] will be extended to present a solution to this problem. For the sake of completeness, the results of the papers [2, 20] are dicussed.

2.2 Assumptions

It is assumed that a training data D_n = (x₁, y₁) , . . , (x_n, y_n) is given for a regression function r where n goes to ∞ . The regression function is learned by using the data D_n. Following conditions are used for the calculations;

There are ∞ training points. All the output values between y_min and y_max are present once in the training data.

The classification error is 0 for each model.

The mean of target variable values of data points in the predicted bin is the output value of a model. As the target value is uniformly distributed, the center of the bin is the predicted value.

y_p is the actual target value and $y_{p}^{'}$ is the predicted target value of the point p.

The ensemble has ∞ models and each model is created by using different bin boundary.

The mean of all the predictions (by single models) is the final result of an ensemble.

The training error is calculated. In other words, the point which is predicted is available in the training data.

Each model of an ensemble is a trained classifier. Each classifier is trained to learn a decision boundary for a binary classification problem. It is assumed that the trained model can predict all the data points correctly (0 classification error). Depending upon the decision boundaries, an appropriate classifier should be selected. For example, if the decision boundaries are linear (Section 3.3), classifiers which can learn linear can be used, whereas if the decision boundaries are nonlinear (Section 5) only those classifier should be used that can learn nonlinear decision boundaries.

The important point in this calculation is that the center point of a bin is the predicted value of a model. Generally, the mean target values of all points present in the predicted bin is taken as the output of the model, hence, the uniformly distribution assumption is made so that the output of the model is the center of the bin. This assumption is presented as theoretical results by Ahmad et al. [2, 20] are shown by using this assumption. However this assumption will not be used in the proposed methods (please seeSection 4).

2.3 Theoretical results of RvC ensembles with ERD

In this section, theoretical results of RvC ensembles with ERD [2, 20] are discussed. In RvC ensembles, ERD is used to produce different bin boundaries. The prediction for each model is dependent on the bin boundary. Hence, the predictions are different for different models of ensembles. These predictions are combined by taking the mean of these values to get the final result.

The bin boundary (B₁) is between the minimum value (y_min) and the maximum value (y_max) of the target variable (Fig. 1). If the target value we want to predict is y_p, in case y_p at the right side of the bin boundary, the predicted value is (y_max + B₁)/2. Whereas, if y_p is at the left side of the bin boundary, the predicted value is (y_min + B₁)/2. The mean value of all the results (∞ runs) is the final prediction. The predicted value is $\begin{matrix} y_{p}^{'} = \frac{1}{(y_{\max} - y_{\min})} (\int_{y_{\min}}^{y_{p}} (y_{\max} + B_{1}) / 2 {dB}_{1} \\ + \int_{y_{p}}^{y_{\max}} (y_{\min} + B_{1}) / 2 {dB}_{1}) \end{matrix}$ (1) $y_{p}^{'} = y_{p} / 2 + (y_{\min} + y_{\max}) / 4 .$ (2)

Fig.1

In the top figure the target point, the bin boundary, B₁, is at the left of the target data point, y_p, whereas in the bottom figure, the bin boundary B₁, is the right side of the target point, y_p.

Only at y_p = (y_min + y_max)/2, the predicted value, $y_{p}^{'}$ , is equal to target value y_p.

Hence, these RvC ensembles with two bins cannot learn y = x regression problem accurately. They also perform the calculation for more than two bins and find out that with the finite number of bins, y = x regression problem cannot be studied accurately.

Ahmad et al. present [3] the results for RvC ensembles with two bins for y = x problem, however, it can be shown that these results are also true for uniformly monotonically increasing or decreasing functions with one variable like y = x² (x ≥ 0). In RvC ensembles, the results for y = x problems are true for all the functions for which the mean of the target value of points in a bin is the center of the bin. This condition is true for all the monotonically increasing or decreasing functions with one variable (with infinite points of the functions and no duplicate points). Hence, all the results for RvC ensembles with two bins for y = x function are also true for uniformly monotonically increasing or decreasing functions with one variable.

The interesting point is that the predicted output is independent of type of a function. For example, we have different datasets for the different monotonically increasing or decreasing functions with one variable with the same minimum and maximum values of the target value, the prediction of data points with the same target values will be the same for both datasets. In other words, the predicted output is independent of the type of the function. It is only dependent on the target value, and the minimum and the maximum target values of the training dataset.

These results will be extended to show that some modifications in this algorithm can lead to development of more accurate RvC ensembles.

3 The proposed ensemble methods for uniformly monotonically increasing or decreasing functions

In this section, two RvC ensemble methods with ERD will be presented, which use linear classifiers like decision stumps. It will be shown that RvC ensembles with ERD with two bins can accurately learn a uniformly monotonically increasing or decreasing function with one variable. Ahmad el al. [2] show that when the number of bins is increased, the relationship between predicted and actual values becomes complicated, hence, applying the following methods becomes difficult when the number of bins is more than two.

3.1 Modified final output of RvC ensembles with ERD with two bins

Our first solution is based on the modified output to get the correct prediction. As discussed in the previous section, for RvC ensembles with ERD with two bins, the predicted value $y_{p}^{'}$ , and the actual output, y_p, has following relationship for prediction of the points created from y = x function;

$y_{p}^{'} = \frac{y_{p}}{2} + \frac{y_{\min} + y_{\max}}{4} .$ (3)

By rearranging the equation

$y_{p} = 2 (y_{p}^{'} - \frac{y_{\min} + y_{\max}}{4}) .$ (4)

Hence, if the y_min and y_max are known, the actual value y_p can be calculated by the predicted value $y_{p}^{'}$ . As we are interested in training error, y_min and y_max are known. Therefore, the actual value, y_p, can be calculated by the predicted value, $y_{p}^{'}$ . This way there will be no prediction error. Hence, by modifying the final output of RvC ensembles with ERD, y = x function points can be learned by these ensembles. As discussed in Section 2 that the results of y = x are similar to results of monotonically increasing or decreasing functions with one variable, the modified result can be used for these functions also. This method will be called as Method-1 in this paper.

3.2 Modified output of each model for RvC ensembles with ERD with two bins

In RvC ensembles with ERD, the center of a bin is the output of each model. It is proposed that instead of taking the center of the bin as the output of the model, we take the extreme point of the bin as the output of the model. In the case of RvC with two bins (Fig. 1), the output of the left bin will be y_min and the output of the right bin will be y_max. In this case, the average of outputs of all the models will be

$\begin{matrix} y_{p}^{'} = \frac{1}{(y_{\max} - y_{\min})} (\int_{y_{\min}}^{y_{p}} y_{\max} {dB}_{1} \\ + \int_{y_{p}}^{y_{\max}} y_{\min} {dB}_{1}) \end{matrix}$ (5)

$\begin{matrix} y_{p}^{'} = \frac{1}{(y_{\max} - y_{\min})} (y_{\max} (y_{p} - y_{\min}) \\ + y_{\min} (y_{\max} - y_{p})) \end{matrix}$ (6)

$y_{p}^{'} = \frac{1}{(y_{\max} - y_{\min})} (y_{p} (y_{\max} - y_{\min}))$ (7)

$y_{p}^{'} = y_{p}$ (8)

Hence, the predicted value $y_{p}^{'}$ is exactly the same as the actual value y_p. This demonstrates that there will be no prediction error in this case. Therefore, one can conclude that RvC with ERD with 2 bins can learn monotonically increasing or decreasing functions with one variable. This method will be called as Method-2 in this paper.

3.3 Experiments with monotonically increasing functions with one variable

In the experiments, two bins were created for each RvC model. Hence, each model had one bin boundary. We wanted to create uniform bin boundaries. Hence, the bin boundary of i^th model was created by using the formula $\frac{i}{M + 1}$ (y_max - y_min) (1≤i ≤ M), where M is the ensemble size. It is interesting to note that in our experiments there was no randomization process as bin boundaries were created uniformly. Decision stumps were used as classifiers. Decision stumps are decision trees with two leaves. For Method-1, the center of the predicted leaf is taken as the output of the model.

Weka [21] implementation of decision stumps was used in the experiments. For the comparative study, we also did the experiments with two popular regression tree ensemble methods, Decision stump regression ensembles with Bagging and Random Forests [8]. As there is no WEKA implementation of Random Forests (for regression), the R [31] implementation the Random Forests was used in our experiments. In our proposed ensemble methods, all the models of an ensemble are created independently. Whereas, in Boosting, the training of a new member is dependent on the already trained members. Hence, the boosting [18] like methods are not included in the study. As the base classifier for the proposed ensemble method was decision stump, for fair comparative study the experiments were carried out with decision tree ensemble methods.

Three different datasets used in the experiments were created from three different functions; y = x (0≤x≤100), y = x² (0≤x≤10) and y = 100sinx (0≤x≤1.57). The range of target variable, y, was between 0 to 100. The datasets were created in such a way that each point in one dataset had one corresponding point in other dataset such that these points had same y values. It other words, y value was created first and the corresponding x value was created from the y values. For n data points, the y values of data points were created by using a formula, (i/n + 1)(y_max - y_min) (1< = i < = n). There were two goals of selecting these datasets, first these datasets came from monotonically increasing functions, hence, our methods should work on these datasets, the second goal was to show that for the proposed RvC ensemble methods, the predicted output of a test point was independent of the type of datasets (training dataset and testing dataset) generated from uniformly monotonically increasing or decreasing functions. Root mean square error (RMSE) measure was used to compute prediction error. A dataset with 1000 data points was created for each function. Training error was calculated in the experiments.

Results are presented in Table 1 –3. The results suggest the proposed ensemble methods performed much better than decision stump ensembles with Bagging. It is interesting to note that similar to decision stump ensembles with Bagging (it uses decision stumps as a regression method), our proposed methods use decision stumps (it uses decision stumps as a classification method), however, the ways final results are achieved are different. Both proposed RvC ensemble methods gave almost the same results.

Table 1
Training RMSE for different ensembles methods for the dataset with 1000 data points generated from y=x function

The size of ensembles Random Forests Decision Stumps regression ensembles with Bagging Method-1 with Decision Stumps Method-2 with Decision Stumps

100 0.0286 14.2008 0.4047 0.4047

500 0.0251 14.1922 0.0745 0.0745

1000 0.0246 14.1292 0.0289 0.0289

5000 0.0243 14.1446 0.0082 0.0082

The size of ensembles	Random Forests	Decision Stumps regression ensembles with Bagging	Method-1 with Decision Stumps	Method-2 with Decision Stumps
100	0.0286	14.2008	0.4047	0.4047
500	0.0251	14.1922	0.0745	0.0745
1000	0.0246	14.1292	0.0289	0.0289
5000	0.0243	14.1446	0.0082	0.0082

Table 2

Training RMSE for different ensembles methods for the dataset with 1000 data points generated from y = x² function

The size of ensembles	Random Forests	Decision Stumps regression ensembles with Bagging	Method-1 with Decision Stumps	Method-2 with Decision Stumps
100	0.0283	14.2008	0.4047	0.4047
500	0.0249	14.192	0.0745	0.0744
1000	0.0246	14.1292	0.0289	0.0289
5000	0.0241	14.1531	0.0080	0.0081

Table 3

Training RMSE for different ensembles methods for the dataset with 1000 data points generated from y=100sinx function

The size of ensembles	Random Forests	Decision Stumps regression ensembles with Bagging	Method-1 with Decision Stumps	Method-2 with Decision Stumps
100	0.0281	14.1812	0.4038	0.4038
500	0.0252	14.1824	0.0763	0.0763
1000	0.0247	14.1811	0.0291	0.0291
5000	0.0245	14.1352	0.0081	0.0081

Table 1 –3. show that results of RvC are independent of the function. This verifies our theoretical results that for monotonically increasing or decreasing functions with one variable, the predicted results are independent of the function.

Experimental results suggest that with our proposed ensemble methods, as the size of the ensemble is increasing the training error is decreasing. For Random Forests, the error doesn’t change much for the size of the ensembles greater than 500. This indicates that the proposed ensemble methods are able to create diverse models. As a decision stump (a decision tree with two leaves) is used as a base classifier for an ensemble, the individual models are not as accurate as random forests models, hence for smaller sized ensembles (up to 1000), random forests performed better. However, the performance of our methods with the ensemble size 5000 is better than Random Forests. This suggests that the proposed ensemble methods create diverse models, the combination of these diverse models produce excellent results. These results are interesting as the size of the individual tree in Random Forests was between 265-300, whereas in the proposed methods, decision stumps which have only two leaves were used. A question may be asked how 5000 different models were created with 1000 data points with the proposed methods. The answer is that bin boundaries are different for all the models (please see the formula in the first paragraph of this section), hence the output which is the center of the predicted bin is different for all the models for Model-1. Similarly with different bin boundaries, different models are created in Model-2.

Ahmad et al. [2, 3] show that RvC ensembles and infinite sized ensembles, consisting of finite sized univariate regression trees, created by a pure randomized method are similar. Random Forests and Bagging methods represent these kinds of ensemble methods. Results suggest that the performance of these ensembles are almost the same for datasets created by using different types of monotonically increasing or decreasing functions of single variable. This is an interesting observation. It shows that the proposed method can be used to study regression tree ensembles.

It is to be noted that datasets created by monotonically increasing or decreasing functions of single variable belong to a very small subset of regression datasets. The learning of a diagonal decision boundary by univariate tree ensembles has been an important research problem [3, 12]. Ahmad et al. [3] Ahmad et al. [2, 3] show that RvC ensembles and infinite sized ensembles, consisting of finite sized univariate regression trees cannot learn a diagonal decision boundary (y = x). It this section, it is shown that the proposed RvC ensemble methods with decision stumps (trees with two leaves) can outperform Random Forests ensembles consisting of trees having size between 265-300. It is also shown that these results are valid for all monotonically increasing or decreasing functions of single variable.

These are interesting observations, however, for the practical purpose, RvC ensemble methods are required that can learn all kinds of regression functions. In the next section, RvC ensemble methods will be proposed that can learn all kinds of regression functions by using binary classifiers that can learn nonlinear decision boundaries.

4 The proposed method for all regression functions

It will be shown that that proposed RvC ensemble methods can be used to learn all kinds of regression functions provided binary classifiers are available that can learn all kinds of decision boundaries.

In RvC ensembles with ERD with two bins (Section 2), two bins are created for each model with a bin boundary and a classifier is trained on this discretized data by using two bins as two classes. The zero classification error is the main condition that is required to get the theoretical results presented in Section 3. The other condition which is important for the Method-1 is that the final prediction of each model should be the center of each bin. This condition can be achieved easily by taking the center of bin as the predicted value. We are not taking the mean of target variable values of data points in the predicted bin as the output value of a model, hence uniform distribution assumption is not required to achieve the bin center as the predicted output.

The first job of the model is to predict the class (bin) of the testing point then the class (bin) can be converted into a continuous output by using the minimum or maximum of the training data points and the bin boundary. Generally, testing data points and training data points have similar distribution, hence, minimum and maximum of the training data points should be useful for predicting the testing data points. All models in an ensemble give continuous outputs which are combined to get the final result. This suggests that if each model predicts the bins correctly, the minimum and maximum of the function are known, this framework can be applied to any regression function. The problem of RvC ensembles can be considered as deciding in each model that whether the point we want to predict is in the left bin or the right bin, each model will give one output which can be used as proposed in Section 3 to get the final results. The accuracy of the final prediction depends upon the accuracy of the classifiers. The decision boundaries in this case could be non-linear and the number of classes are two, Hence, those binary classifiers are required that can learn non-linear decision boundaries. The detailed algorithm is illustrated in Algorithm 1.

Algorithm 1
The algorithm for RvC ensembles.

Input- Training dataset T, the size of an ensemble M,

y is the target variable. y_max is the maximum value of the target variable whereas y_min is the minimum value of the target variable.

Training Phase

for i=1...Mdo

Discretization of training datasetT

1- Discretize the target variable y of training dataset T into two bins by using the bin boundary given by the expression (i/(M + 1)) (y_max - y_min)

Learning Phase

Learn a classifier D_i on the discretizd data.

end for

Prediction Phase

For a given data point X

for i=1...Mdo

1- Get the classification results by the classifier D_i. Get the output by using the Method-1 or Method-2 given in Section 4.

end for

Combine the results of all the models by using the Method-1 or Method-2 given in Section 4 to get the final result.

This method is similar to Error-correcting codes ensembles [13], both methods covert a learning problem into many binary classification problems, however Error-correcting codes ensembles are for multi-class classification problems whereas the proposed methods are for regression problems.

Method-2 has similarity with the method proposed by Langford and Zandrozny [26] that uses a combination of binary classifiers, created by using different class boundaries for different classifiers, to estimate the class probabilities. In the proposed methods, the binary classifiers are used with different binboundaries.

4.1 Complexity

The essential step in the proposed RvC ensemble methods is to find the maximum and the minimum of the target values of the training dataset. If the number of data points in the training data is n, the complexity of this step will be O (n). For RvC ensembles of size m, m classifiers are trained; one for each model. If the number of steps required to train a classifier and get the classification result for a given point is s. The complexity of this step for the ensemble is O (ms). Hence, the complexity of the proposed RvC ensemble methods for a testing data point is O (n + ms) which is dependent on the size of the training data, the size of the ensemble and the type of the classifier.

5 Experiments with regression datasets

Experiments were carried out with a sinusoidal univariate function, y = 1 + x² - 50xsin (x/2), with x is a real number [16]. This is a highly nonlinear function. 10000 points were generated uniformly with 0 ≤ x ≤ 100. We also did the experiments with different popular regression datasets available withDelve datasets (www.cs.toronto.edu/∼delve/data/datasets.html), UCI data repository [17] and www.dcc.fc.up.pt/∼ltorgo/Regression/DataSets.html. The information about these datasets is presented in Table 4. Random Forests are very accurate ensemble method for classification and regression and do not have a large number of parameters. Hence, in these experiments, we selected Random Forests as classifiers for our methods. Results are compared with Random Forests as regression method. R [31] implementation of Random forests (for regression and for classification) were used in our experiments. The target values of the training data is discretized (two bins) by the method presented in Algorithm 1 to create different datasets. Classifiers (Random forests) were trained on each of these datasets. For each testing point, the classification result (bin) for each classifier was computed. The maximum and minimum values of the target values of the training dataset were used to convert the classification results into a predicted value by using the Method-1 or Method-2 (please see Algorithm 1). The average error measure of testing points is presented as the error measure of the testing data. Following [4], 5x2 fold cross-validation was used in the experiments. Five replications of a two-fold cross-validation were performed. In each replication, the dataset was divided into two random equal-sized sets. Each learning algorithm was trained on one set at a time and its error was estimated on the other set. The average results of these 10 runs were calculated and presented. We carried out with different parameters; the size of RvC ensembles and the size of the Random forests classifier and found that the results with 200 as RvC ensembles size and 50 as size of Random forests classifier were good representation of the proposed ensemble methods. Hence, the size of the ensembles was set to 200, whereas, the size of the Random Forests as classifiers in our methods was set to 50. It is to be noted that in the proposed methods, 200*50=10000 trees are generated against 200 trees in Random Forests as a regression method. To check the effect of more trees, the results for Random Forests as a regression method were also presented with 500 trees. The purpose of using two values for the size of the Random Forests was that we wanted to show that the further increase of the size of the Random Forests did not improve the regression results much. Hence, the results of Random forests with 500 trees were taken as the best results that was achieved with Random Forests as a regression method. These results are used as the benchmark to check how the proposed methods performed against the benchmark.

Table 4
Details of datasets used in the experiments

Name of dataset Number of features Number of data points

Abalone 8 4177

Airfoil Self-Noise 6 1503

Bank8FM 8 8192

Bank32nh 32 8192

Cart 10 40768

Concrete Strength 9 1030

CT slices 386 53500

Fried-delve 10 40768

House(8L) 8 22784

House(16H) 16 22784

Housing(Boston) 13 506

Housing (California) 8 20460

Kin8nm 8 8192

Power Plant(Turkey) 4 9568

Puma8NH 8 8192

Puma32H 32 8192

Stock 10 95

Name of dataset	Number of features	Number of data points
Abalone	8	4177
Airfoil Self-Noise	6	1503
Bank8FM	8	8192
Bank32nh	32	8192
Cart	10	40768
Concrete Strength	9	1030
CT slices	386	53500
Fried-delve	10	40768
House(8L)	8	22784
House(16H)	16	22784
Housing(Boston)	13	506
Housing (California)	8	20460
Kin8nm	8	8192
Power Plant(Turkey)	4	9568
Puma8NH	8	8192
Puma32H	32	8192
Stock	10	95

In the proposed ensemble methods, we solve binary classification problems. We predict the bin, as either left bin or right bin. All the theoretical results are achieved by using this assumption, however, classifiers also give the probability of two classes. In one of the versions of the proposed method, these probabilities are used to get the final results. For the modified version of Method-2, the following equation was used.

$y_{p} = (\sum_{i = 1}^{M} p_{i} y_{\max} + (1 - p_{i}) y_{\min}) / M$ (9)

Where p_i is the probability of predicting the bin for which the y_max is one of the bin boundary. In our theoretical calculation, it is assumed that p_i is either one or zero, however, in the modified version, p_i can take any value between zero and one. Generally, we do not get the zero classification error, so we are taking the output from the wrong bin. To minimize the effect of wrong prediction the proposed modification may be useful. The similar modification was done in Method-1. In other words, the predicted value for each model is calculated from the classification probabilities for each bin and the mid points of the each bin. As both methods (Method-1 and Method-2) were giving the same results, we present the results with the Method-2 and its modification.

The results for nonlinear function are presented in Table 5. When the size of ensemble was small (100), Random Forests performed much better than RvC ensembles. However, as we increased the sizes of ensembles, the results did not improve much for Random Forests, however, there was a large improvement for RvC ensembles (Method-2 and its modified version). Results shows that the best results was achieved with 1000 trees with the proposed method (with probability). In this problem, generally the classification error was small. When, this is the case, one can get a large improvement with large sizes of RvC ensembles, because this condition is near to the condition of the theoretical result (0 classification error) and with this condition, RvC ensembles can achieve a very small error with large sizes.

Table 5

Average RMSE for different ensemble methods for the dataset created from y = 1 + x²- 50xsin (x/2) function, standard deviation is given in brackets. The bold number shows the best result

The size of ensembles	Method-2	Modified Method-2 (with probability)	Random Forests
100	67.8(5.3)	62.6(6.1)	14.9(1.4)
500	20.1(1.9)	16.3(1.6)	14.6(1.3)
1000	16.2(1.6)	12.1(1.1)	14.5(1.3)

The average RMSE for other datasets with different methods is presented in Table 6. It is to be noted that the performance of an ensemble method depends upon its ability to produce accurate and diverse models. It has been shown [19] that generally the performance improvement of an ensemble method occurs for first few models. As the size of an ensemble increases, the new added models are not very diverse, hence they don’t provide large improvement. In the experiments, we carried out the classification process in each model with Random Forests of size 50. Then the results of 200 models were combined. Though 10000 trees are trained, they were not combined together in one step.

Table 6

Average RMSE for different ensemble methods for the different datasets, standard deviation is given in brackets. The bold number shows the best result.‘+/-’ shows that the performance of the algorithm is statistically better/worse than that of Random Forests with 500 trees for that dataset.

Name of dataset	RMSE for Method-2 with 200 models	RMSE for Modified Method-2 with 200 trees	RMSE for Random Forests with 200 trees	RMSE for Random Forests with 500 trees
Abalone	2.19(0.05)	2.14(0.06)	2.15(0.06)	2.15(0.06)
Airfoil	2.55(0.13)(+)	2.49(0.12)(+)	3.83(0.18)	3.80(0.17)
Bank8FM	0.038(0.001)(+)	0.040(0.001)(+)	0.045(0.001)	0.045(0.001)
Bank32nh	0.0944(0.0038)(-)	0.0902(0.0031)	0.0876(0.0041)	0.0875(0.0037)
Cart	1.040(0.022)	1.039(0.021)	1.052(0.023)	1.051(0.022)
CT slices	0.560(0.046)(+)	1.390(0.085)(-)	1.280(0.078)	1.275(0.073)
Concrete Strength	6.15(0.85)	6.32(0.93)	6.29(0.88)	6.29(0.83)
Fried-delve	1.421(0.028)	1.442(0.026)	1.438(0.024)	1.437(0.024)
House(8L)	31146(532)(-)	29897(498)	29989(506)	29917(503)
House(16H)	34634(712)(-)	32665(707)	32386(672)	32264(681)
Housing(Boston)	3.35(0.08)(+)	3.43(0.09)	3.46(0.08)	3.43(0.08)
Housing (California)	52691(248)	52268(273)	52626(257)	52498(253)
Kin8nm	0.143(.011)(+)	0.154(0.014)	0.156(0.015)	0.155(0.014)
Power(Turkey)	3.445(0.332)	3.455(0.299)	3.579(0.351)	3.571(0.348)
Puma8NH	3.325(0.142)	3.355(0.153)	3.358(0.143)	3.353(0.147)
Puma32H	0.0106(0.0005)(+)	0.0166(0.0006)(-)	0.0119(0.0007)	0.0119(0.0007)
Stock	174.05(29.03)	179.81(25.94)	182.67(32.81)	182.46(31.37)

The results for Random Forests as a regression method suggest that there is not much difference between with 200 trees and 500 trees so we can conclude that the results with 500 trees are the almost the best results that can be achieved with Random Forests as regression method. We agree that there is no guarantee that further increase of the size will not improve the performance, however, the comparative study of results suggests (the improvement is less than 1% for different datasets as compared to the performance of ensembles of size 200) that there is a small possibility that the further increase of the size of the ensemble will have the big improvement in the performance of Random Forests as a regression method.

Unpaired t-test with 95% was used to compare the performance of two classifiers [6]. Out of 17 datasets, on 6 datasets (Airfoil, Bank8FM, CT slices,Housing(Boston) Kin8mm and Puma32H) the proposed methods show clear advantage over the other methods, whereas for the other datasets, the proposed methods performed similar to other methods. This shows that the proposed methods are useful for different kinds of regression problems.

6 Conclusion

In this paper, ensemble methods for RvC problems are proposed. It is shown theoretically that these methods give accurate results with accurate binary classifiers. Experiments with different kinds of regression datasets show the effectiveness of the proposed approach. In this paper, most of the experiments were done with Random Forests as classifiers, however, in future, we will do more experiments with different classifiers including deep learning approaches to assess the effectiveness of the proposed ensemble with other classifiers. We will also study for which types of datasets the proposed methods are more useful.

Ensemble pruning [10 , 28] selects a subset of individual classifiers in an ensemble so that the combination of these classifiers produces similar or better performance against the combination of all the classifiers in the ensemble. Ensemble pruning has the advantage of low storage resources. Ensemble pruning is another direction of the future research.

References

Ahmad

, Data Transformation for Decision Tree Ensembles, PhD thesis, School of Computer Science, University of Manchester 2010.

Ahmad

, Halawani

S.M.

and Albidewi

, Novel ensemble methods for regression via classification problems, Expert Systems with Applications 39 (7) (2012), 6396–6401.

Ahmad

, Halawani

S.M.

and Albidewi

, Consistency of randomized and finite sized decision tree ensembles, Pattern Analysis And Applications 17 (1) (2014), 97–104.

Alpaydin

, Combined 5×2 cv f test comparing supervised classification learning algorithms, Neural Computation 11 (8) (1999), 1885–1892.

Bishop

C.M.

, Pattern Recognition and Machine Learning. Springer-Verlag New York Inc, 2008.

Boslaugh

, Statistics in a Nutshell: A Desktop Quick Reference. O’Reilly Media, 2012.

Breiman

, Some Infinite Theory for Predictor Ensembles. Technical Report 577, Statistics Department, UC Berkeley, 2000.

Breiman

, Random forests, Machine Learning 45 (1) (2001), 5–32.

Breiman

, Friedman

, Olshen

, Stone

, Classification and Regression Trees, Wadsworth International Group, CA, 1984.

10.

Dai

, A novel ensemble pruning algorithm based on randomized greedy selective strategy and ballot, Neurocomputing 122 (2013), 258–265.

11.

Dai

and Li

, Introducing randomness into greedy ensemble pruning algorithms, Applied Intelligence 42 (2015), 406–429.

12.

Dietterich

T.G.

, Ensemble methods in machine learning, In Proc of Conf Multiple Classifier Systems, 1857, 2000, pp. 1–15.

13.

Dietterich

T.G.

and Bakiri

, Solving multiclass learning problems via error-correcting output codes, J Artificial Intelligence Research 2 (1995), 263–286.

14.

Dougherty

, Kahavi

and Sahami

, Supervised and unsupervised discretization of continuous features, Proceedings of the Twelth International Conference, In In Machine Learning, 1995.

15.

Frank

E.E.

, Bouckaert

, Conditional density estimation with class probability estimators, In Advances in Machine Learning, Berlin Heidelberg, Springer Heidelberg, 2009, pp. 65–81.

16.

Fan

, McCloskey

and Yu

P.S.

, A General Framework for Accurate and Fast Regression by Data Summarization in Random Decision Trees, In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2006, pp. 136–146.

17.

Frank

and Asuncion

, UCI machine learning repository, 2010.

18.

Freund

and Schapire

R.E.

, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences 55 (1) (1997), 119–139.

19.

Fumera

, Roli

and Serrau

, A theoretical analysis of bagging as a linear combination of classifiers, IEEE Transactions on Pattern Analysis and Machine Intelligence 30 (7) (2008), 1293–1299.

20.

Halawani

S.M.

, Albidewi

I.A.

and Ahmad

, A novel ensemble method for regression via classification problems, Journal of Computer Science 7 (3) (2011), 387–393.

21.

Hall

, Frank

, Holmes

, Pfahringer

, Reutemann

and Witten

I.H.

, The WEKA data mining software: An update, SIGKDD Explorations 11 (1) (2009), 10–18.

22.

Indurkhya

and Weiss

S.M.

, Solving Regression Problems with Rule-based Ensemble Classifiers, In ACM International Conference Knowledge Discovery and Data Mining (KDD01), 2001, pp. 287–292.

23.

Janssen

and Furnkranz

, Heuristic Rule-based Regression via Dynamic Reduction to Classification, In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. 2011, pp. 1330–1335.

24.

Krawczyk

, Wozniak

and Cyganek

, Clustering-based ensembles for one-class classification, Information Sciences 264 (2014), 182–195.

25.

Kuncheva

L.I.

, Combining Pattern Classifiers: Methods and Algorithms, Wiley-Interscience, 2004.

26.

Langford

and Zadrozny

, Estimating Class Membership Probabilities using Classifier Learners, In Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics, 2005, pp. 198–205.

27.

Mitchell

T.M.

, Machine Learning, McGraw-Hill, 1997.

28.

Partalas

, Tsoumakas

and Vlahavas

, Focused Ensemble Selection: A Diversity-based Method for Greedy Enble Selection, Proceedings of the European Conference on Artificial Intelligence, 2008, pp. 117–121.

29.

Polikar

, Ensemble Based Systems in Decision Making, IEEE Circuits and Systems Magazine, Third Quarter, 2006, 21–45.

30.

Quinlan

J.R.

, C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1993.

31.

R Development Core Team. R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria, 2008, ISBN 3-900051-07-0.

32.

Torgo

and Gama

, Regression by Classification, In Advances in Artificial Intelligence, 1996, pp. 51–60.

33.

Torgo

and Gama

, Search-based Class Discretization, In Proceedings of the 9th European Conference on Machine Learning, 1997, PP. 266–273.

34.

Zainal

, Maarof

M.A.

, Hj

S.M.

, Shamsuddin and Abraham

. Ensemble of one-class classifiers for network intrusion detection system, In Proccedings of the Fourth International Conference on Information Assurance and Security, IAS 2008, Napoli, Italy, 2008.