
## P(Y | X, D) P( Y | X,Θ,D) P(Θ | D)Dθ

where y is the predicted class (1, …, C), x = (x1, …, xm) is the m-dimensional vector of input, and D are the given training data.

This integral can be analytically calculated only in simple cases, and in practice part of the integrand, which is the posterior density of  conditioned on the data D, p( **|D)**,
cannot usually be evaluated. However if values (1), …, (N)
are the samples drawn from the posterior distribution p(|D), we can write i N

$\downarrow$ | L. 
( )
p y p y p

## ( | , , ) 1

( | , ) ( | , , ) ( | )
x D x θ D θ D

$$0\approx\sum_{i=1}^{\infty}p(y\mid\mathbf{x},t)$$
i
( )

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

The above integral can be approximated by using Markov Chain Monte Carlo (MCMC) technique [3]. To perform such an approximation, we need to run a Markov Chain until it has converged to a stationary distribution. Then we can collect N random samples from the posterior p**(|D)** to calculate the desired predictive posterior density. 

Using DTs for the classification, we need to find the probability tj with which an input x is assigned by terminal node t = 1, …, k to the jth class, where k is the number of terminal nodes in the DT. The DT parameters are defined as 
 = (si pos, si var, si rule), i = 1, …, k - 1, where si pos, si var and si rule define the *position, predictor* and *rule* of each splitting node, respectively. For these parameters the priors can be specified as follows. First we can define a maximal number of splitting nodes, say, smax = n - 1. Second we draw any of the m predictors from a uniform discrete distribution U(1, 
…, m) and assign 1{ ,..., } var si  m . 

Finally the candidate value for the splitting variable xj = 
si var can be drawn from a discrete distribution U(xj
(1), …, 
xj
(L)), where L is the number of possible splitting rules for variable xj, either categorical or continuous. Such priors allow us to explore DTs which split data in as many ways as possible. However the DTs with different numbers of splitting nodes should be explored in the same proportions [3]. 

To sample DTs of a variable dimensionality, the MCMC 
technique exploits the Reversible Jump extension [3]. To implement the RJ MCMC technique, Denison *et al.* [3] and Chipman *et al.* [6] have suggested exploring the posterior probability by using the following types of moves:

1. *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.

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

3. *Change-split*. Randomly pick a splitting node and assign it a new splitting variable and rule drawn from the corresponding priors. 

4. *Change-rule*. Randomly pick a splitting node and assign it a new rule drawn from a given prior.
The first two moves, *birth* and *death*, are reversible and change the dimensionality of . The remaining moves provide jumps within the current dimensionality of . Note that the *change-split* move is included to make "large" jumps which potentially increase the chance of sampling from a maximal posterior whilst the *change-rule* move does "local" jumps.

The RJ MCMC technique starts drawing samples from a DT consisting of one splitting node whose parameters were randomly assigned within the predefined priors. So we need to run the Markov Chain while a DT grows and its likelihood is unstable. This phase is said *burn-in* and it should be preset enough long in order to stabilize the Markov Chain. When the Markov Chain will be enough stable, we can start sampling. This phase is said *post burn-in*. 

## Iii. The Proposed Method

To test the assumptions made in section I, we propose two methods - the first is based on selection of DTs ensemble, and the second is based on the randomization of variables. The selection technique aims to omit the DTs which use the weakest variable. The randomization technique aims to provide better conditions for mitigating DT ensemble overfitting. In the following sections we test and compare these techniques on the Trauma data. 

## Iv. Experiments And Results A. Trauma Data

The Trauma data collected at the Royal London Hospital comprises 16 screening tests and attributes and the outcome 
(lived or died) for 316 injured patients. Among these variables 5 are continuous and 11 are categorical, see Table 1.

## B. Variable'S Importance

In our experiments we collected 10,000 DTs during post burn-in phase after sampling 200,000 DTs during burn-in phase. The sampling rate for post burn-in phase was 7; the 