model which provides the Maximum a Posteriori (MAP) performance [7]. Unfortunately, in most practical cases, a *priori* information on the favored structure of DTs is not available. For this reason, we suggest a new prior on DT models within a sweeping strategy that we described in [8]. 

We also suggest a new procedure for selecting a single DT, described in Section 3. 

This procedure is based on the estimates obtained within the Uncertainty Envelope technique that we described in [9]. An application scenario, which can be implemented within the proposed Bayesian technique, is described in Section 5.

In this Chapter we aim to compare the predictive accuracy of decisions obtained with the suggested Bayesian DT technique and the standard Bayesian DT techniques. The comparison is run on air-traffic control data made available by the National Air Traffic Services (NATS) in the UK. In our experiments, the suggested technique outperforms the existing Bayesian techniques in terms of predictive accuracy. 

## 1. Bayesian Averaging Over Decision Tree Models

In general, a DT is a hierarchical system consisting of splitting and terminal nodes. DTs are binary if the splitting nodes ask a specific question and then divide the data points into two disjoint subsets [3]. The terminal node assigns all data points falling in that node to the class whose points are prevalent. Within a Bayesian framework, the class posterior distribution is calculated for each terminal node, which makes the Bayesian integration computationally expensive [4]. 

To make the Bayesian averaging DTs a feasible approach, Denison *et al.* [5] have suggested the use of the MCMC technique, taking a stochastic sample from the posterior distribution. During sampling, the parameters θ of candidate-models are drawn from the given proposal distributions. The candidate is accepted or rejected accordingly to Bayes rule calculated on the given data D. Thus, for the m-dimensional input vector x, data D and parameters θ , the class posterior distribution p( y | x,D) is 

## N I I P Y N P Y P Y P D 1 ( ) ( | , , ) 1 ( | X,D) ( | X,Θ,D) (Θ | D) Θ X Θ D ,

where p(θ | D) is the posterior distribution of parameters θ conditioned on data D, 
and N is the number of samples taken from the posterior distribution.

Sampling across DT models of variable dimensionality, the above technique exploits a Reversible Jump (RJ) extension suggested by Green [10]. When *priori* information is not distorted and the number of samples is reasonably large, the RJ MCMC technique, making birth, death, change-question, and change-rule moves, explores the posterior distribution and as a result provides accurate estimates of the posterior.

To grow large DTs from real-world data, Denison *et al.* [5] and Chipman *et al.* [6] 
suggested exploring the posterior probability by using the following types of moves:
Birth. Randomly split the data points falling in one of the terminal nodes by a new splitting node with the variable and rule drawn from the corresponding priors.

Death. Randomly pick a splitting node with two terminal nodes and assign it to be a single terminal with the united data points.

2