Data Mining: The Textbook

j = 1;

repeat
Select an algorithm Q_j from A₁ . . . A_r;

Create a new training data set f_j (D) from D;
Apply Q_j to f_j (D) to learn model M_j ;

• 
  = j + 1;
  

until(termination);

report labels of each T ∈ T based on combination of predictions from all learned models M_j ;

end

Figure 11.4: The generic ensemble framework

basic approach of ensemble analysis is to apply the base ensemble learners multiple times by using either different models, or by using the same model on different subsets of the training data. The results from different classifiers are then combined into a single robust prediction.

Although there are significant differences in how the individual learners are constructed and combined by various ensemble models, we start with a very generic description of ensemble algorithms. Later in this section, we will discuss specific instantiations of this broad framework, such as bagging, boosting, and random decision trees. The ensemble approach uses a set of base classification algorithms A₁ . . . A_r. Note that these learners might be completely different algorithms, such as decision trees, SVMs, or the Bayes classifier. In some types of ensembles, such as boosting and bagging, a single learning algorithm is used but with different choices of training data. Different learners are used to leverage the greater robustness of different algorithms in different regions of the data. Let the learning algorithm selected in the jth iteration be denoted by Q_j . It is assumed that Q_j is selected from the base learners. At this point, a derivative training data set f_j (D) from the base training data is selected. This may be a random sample of the training data, as in bagging, or it may be based on the results of the past execution of ensemble components, as in boosting. A model M_j is learned in the jth iteration by applying the selected learning algorithm Q_j to f_j (D). For each test instance T , a prediction is made by combining the results of different models M_j on T . This combination may be performed in various ways. Examples include the use of simple averaging, the use of a weighted vote, or the treatment of the model combination process as a learning problem. The overall ensemble framework is illustrated in Fig. 11.4.

The description of Fig. 11.4 is very generic, and allows significant flexibility in terms of how the ensemble components may be learned and the combination may be performed. The two primary types of ensembles are special cases of the description of Fig. 11.4:

1. 
   Data-centered ensembles: A single base learning algorithm (e.g., an SVM or a decision tree) is used, and the primary variation is in terms of how the derivative data set f_j (D) for the jth ensemble component is constructed. In this case, the input to the algorithm contains only a single learning algorithm A₁. The data set f_j (D) for the jth component of the ensemble may be constructed by sampling the data, focusing on incorrectly classified portions of the training data in previously executed ensemble components, manipulating the features of the data, or manipulating the class labels in the data.