BACKGROUND
in bioinformatics and related scientific fields, such as statistical genomics and genetic epidemiology, an important task is the prediction of a categorical response variable  based on a large number of predictors.
the aim of this research is on one hand to predict the value of the response variable from the values of the predictors, i.e.
to create a diagnostic tool, and on the other hand to reliably identify relevant predictors from a large set of candidate variables.
from a statistical point of view, one of the challenges in identifying these relevant predictor variables is the so-called "small n large p" problem: usual data sets in genomics often contain hundreds or thousands of genes or markers that serve as predictor variables x <dig> ..., xp, but only for a comparatively small number n of subjects or tissue types.
traditional statistical models used in clinical case control studies for predicting the disease status from selected predictor variables, such as logistic regression, are not suitable for "small n large p" problems  <cit> .
a more appropriate approach from machine learning, that has been proposed recently for prediction and variable selection in various fields related to bioinformatics and computational biology, is the nonlinear and nonparametric random forest method  <cit> .
it also provides variable importance measures for variable selection purposes.
random forests have been successfully applied to various problems in, e.g., genetic epidemiology and microbiology in general within the last five years.
within a very short period of time, random forests have become a major data analysis tool, that performs well in comparison with many standard methods  <cit> .
what has greatly contributed to the popularity of random forests is the fact that they can be applied to a wide range of prediction problems, even if they are nonlinear and involve complex high-order interaction effects, and that random forests produce variable importance measures for each predictor variable.
applications of random forests in bioinformatics include large-scale association studies for complex genetic diseases, as e.g.
lunetta et al.
<cit>  and bureau et al.
<cit> , who detect snp-snp interactions in the case-control context by means of computing a random forest variable importance measure for each polymorphism.
a comparison of the performance of random forests and other classification methods for the analysis of gene expression data is presented by díaz-uriate and alvarez de andrés  <cit> , who propose a new gene selection method based on random forests for sample classification with microarray data.
we refer to  <cit>  for other applications of the random forest methodology to microarray data.
prediction of phenotypes based on amino acid or dna sequence is another important area of application of random forests, since possibly involving many interactions.
for example, segal et al.
<cit>  use random forests to predict the replication capacity of viruses, such as hiv- <dig>  based on amino acid sequence from reverse transcriptase and protease.
cummings and segal  <cit>  link the rifampin resistance in mycobacterium tuberculosis to a few amino acid positions in rpob, whereas cummings and myers  <cit>  predict c-to-u edited sites in plant mitochondrial rna based on sequence regions flanking edited sites and a few other  parameters.
the random forest approach was shown to outperform six other methods in the prediction of protein interactions based on various biological features such as gene expression, gene ontology  features and sequence data  <cit> .
other applications of random forests can be found in fields as different as quantitative structure-activity relationship  modeling  <cit> , nuclear magnetic resonance spectroscopy  <cit> , landscape epidemiology  <cit>  and medicine in general  <cit> .
the scope of this paper is to show that the variable importance measures of breiman's original random forest method  <cit> , based on cart classification trees  <cit> , are a sensible means for variable selection in many of these applications, but are not reliable in situations where potential predictor variables vary in their scale of measurement or their number of categories, as, e.g., when both genetic and environmental variables, individually and in interactions, are considered as potential predictors, or predictor variables of the same type vary in the number of categories present in a certain sample, as is often the case in genomics, bioinformatics and related disciplines.
simulation studies are presented illustrating that variable selection with the variable importance measure of the original random forest method bears the risk that suboptimal predictor variables are artificially preferred in such scenarios.
in an extra section, further details and explanations of the statistical sources underlying the deficiency of the variable importance measures of the original random forest method, namely biased variable selection in the individual classification trees used to build the random forest and effects induced by bootstrap sampling with replacement, are given.
we propose to employ an alternative random forest method, the variable importance measure of which can be employed to reliably select relevant predictor variables in any data set.
the performance of this method is compared to that of the original random forest method in simulation studies, and is illustrated by an application to the prediction of c-to-u edited sites in plant mitochondrial rna, re-analyzing the data of  <cit>  that were previously analyzed with the original random forest method.
methods
here we focus on the use of random forests for classification tasks, rather than regression tasks, for instance for predicting the disease status from a set of selected genetic and environmental risk factors, or for predicting whether a site of interest is edited by means of neighboring sites and other predictor variables as in our application example.
random forests are an ensemble method that combines several individual classification trees in the following way: from the original sample several bootstrap samples are drawn, and an unpruned classification tree is fit to each bootstrap sample.
the variable selection for each split in the classification tree is conducted only from a small random subset of predictor variables, so that the "small n large p" problem is avoided.
from the complete forest the status of the response variable is predicted as an average or majority vote of the predictions of all trees.
random forests can highly increase the prediction accuracy as compared to individual classification trees, because the ensemble adjusts for the instability of the individual trees induced by small changes in the learning sample, that impairs the prediction accuracy in test samples.
however, the interpretability of a random forest is not as straightforward as that of an individual classification tree, where the influence of a predictor variable directly corresponds to its position in the tree.
thus, alternative measures for variable importance are required for the interpretation of random forests.
random forest variable importance measures
a naive variable importance measure to use in tree-based ensemble methods is to merely count the number of times each variable is selected by all individual trees in the ensemble.
more elaborate variable importance measures incorporate a  mean of the individual trees' improvement in the splitting criterion produced by each variable  <cit> .
an example for such a measure in classification is the "gini importance" available in random forest implementations.
the "gini importance" describes the improvement in the "gini gain" splitting criterion.
the most advanced variable importance measure available in random forests is the "permutation accuracy importance" measure.
its rationale is the following: by randomly permuting the predictor variable xj, its original association with the response y is broken.
when the permuted variable xj, together with the remaining unpermuted predictor variables, is used to predict the response, the prediction accuracy  decreases substantially, if the original variable xj was associated with the response.
thus, a reasonable measure for variable importance is the difference in prediction accuracy before and after permuting xj.
for variable selection purposes the advantage of the random forest permutation accuracy importance measure as compared to univariate screening methods is that it covers the impact of each predictor variable individually as well as in multivariate interactions with other predictor variables.
for example, lunetta et al.
<cit>  find that genetic markers relevant in interactions with other markers or environmental variables can be detected more efficiently by means of random forests than by means of univariate screening methods like fisher's exact test.
the gini importance and the permutation accuracy importance measures are employed as variable selection criteria in many recent studies in various disciplines related to bioinformatics, as outlined in the background section.
therefore we want to investigate their reliability as variable importance measures in different scenarios.
in the simulation studies presented in the next section, we compare the behavior of all three random forest variable importance measures, namely the number of times each variable is selected by all individual trees in the ensemble , the "gini importance" and the permutation accuracy importance measure .
simulation studies
the reference implementation of breiman's original random forest method  <cit>  is available in the r system for statistical computing  <cit>  via the randomforest add-on package by liaw and wiener  <cit> .
the behavior of the selection frequency, the gini importance and the permutation importance of the randomforest function is explored in a simulation design where potential predictor variables vary in their scale of measurement and number of categories.
as an alternative, we propose to use the new random forest function cforest available in the r add-on package party  <cit>  in such scenarios.
in contrast to randomforest, the cforest function creates random forests not from cart classification trees based on the gini split criterion  <cit> , that are known to prefer variables with, e.g., more categories in variable selection  <cit> , but from unbiased classification trees based on a conditional inference framework  <cit> .
the problem of biased variable selection in classification trees is covered more thoroughly in a separate section below.
since the cforest function does not employ the gini criterion, we investigate the behavior of the gini importance for the randomforest function only.
the selection frequency and the permutation importance is studied for both functions randomforest and cforest in two ways: either the individual trees are built on bootstrap samples of the original sample size n drawn with replacement, as suggested in  <cit> , or on subsamples drawn without replacement.
for sampling without replacement the subsample size here is set to  <dig>  times the original sample size n, because in bootstrap sampling with replacement about  <dig> % of the data end up in the bootstrap sample.
other fractions for the subsample size are possible, for instance  <dig>  as suggested by friedman and hall  <cit> .
subsampling as an alternative to bootstrap sampling in aggregating, e.g., individual classification trees is investigated further by bühlmann and yu  <cit> , who also coin the term "subagging" as an abbreviation for "subsample aggregating" as opposed to "bagging" for "bootstrap aggregating".
politis, romano and wolf  <cit>  show that, for statistical inference in general, subsampling works under weaker assumptions than bootstrap sampling and even in situations when bootstrap sampling fails.
the simulation design used throughout this paper represents a scenario where a binary response variable y is supposed to be predicted from a set of potential predictor variables that vary in their scale of measurement and number of categories.
the first predictor variable x <dig> is continuous, while the other predictor variables x <dig> ..., x <dig> are categorical  with their number of categories between two and up to twenty.
the simulation designs of both studies are summarized in tables  <dig> and  <dig>  the sample size for all simulation studies was set to n =  <dig>
the predictor variables are sampled independently from the following distributions.
n stands for the standard normal distribution, m stands for the multinomial distribution with values in { <dig> ..., k - 1} and equal probabilities , b stands for the binomial distribution  with probability p, thus m equals b.
the response variable is sampled from binomial  distributions.
the degree of dependence between the response y and x <dig> is regulated by the probability p of the binomial distribution b of y conditional on x <dig>  with the relevance parameter taking values in { <dig> ,  <dig> ,  <dig> ,  <dig> } to model different degrees of dependence.
in the first simulation study, the so-called null case, none of the predictor variables is informative for the response, i.e.
all predictor variables and the response are sampled independently.
in this situation a sensible variable importance measure should not prefer any one predictor variable over any other.
in the second simulation study, the so-called power case, the predictor variable x <dig> is informative for the response, i.e.
the distribution of the response depends on the value of this predictor variable.
the degree of dependence between the informative predictor variable x <dig> and the response y is regulated by the relevance parameter of the conditional distribution of y given x <dig> .
we will later display results for different values of the relevance parameter indicating different degrees of dependence between x <dig> and y. in the power case, a sensible variable importance measure should be able to distinguish the informative predictor variable from its uninformative competitors, and even more so with increasing degree of dependence.
RESULTS
our simulation studies show that for the randomforest function all three variable importance measures are unreliable, and the gini importance is most strongly biased.
for the cforest function reliable results can be achieved both with the selection frequency and the permutation importance if the function is used together with subsampling without replacement.
otherwise the measures are biased as well.
results of the null case simulation study
in the null case, when all predictor variables are equally uninformative, the selection frequencies as well as the gini importance and the permutation importance of all predictor variables are supposed to be equal.
however, as presented in figure  <dig>  the mean selection frequencies  of the predictor variables differ substantially when the randomforest function  or the cforest function with bootstrap sampling  are used.
variables with more categories are obviously preferred.
only when the cforest function is used together with subsampling without replacement  are the variable selection frequencies for the uninformative predictor variables equally low as desired.
it is obvious that variable importance cannot be represented reliably by the selection frequencies, that can be considered as very basic variable importance measures, if the potential predictor variables vary in their scale of measurement or number of categories when the randomforest function or the cforest function with bootstrap sampling is used.
the mean gini importance , that is displayed in figure  <dig>  is biased even stronger.
like the selection frequencies for the randomforest function  the gini importance shows a strong preference for variables with many categories and the continuous variable, the statistical sources of which are explained in the section on variable selection bias in classification trees below.
we conclude that the gini importance cannot be used to reliably measure variable importance in this situation either.
we now consider the more advanced permutation importance measure.
we find that here an effect of the scale of measurement or number of categories of the potential predictor variables is less obvious but still severely affects the reliability and interpretability of the variable importance measure.
the scaled variable importance is the default output of the randomforest function.
however, it has been noted, e.g., by díaz-uriate and alvarez de andrés  <cit>  in their supplementary material, that the scaled variable importance of the randomforest function depends on the number of trees grown in the random forest.
therefore we suggest not to interpret the magnitude of the scaled variable importance of the randomforest function.
the plots show that for the randomforest function  and, less pronounced, for the cforest function with bootstrap sampling , the deviation of the permutation importance measure over the simulation runs is highest for the variable x <dig> with the highest number of categories, and decreases for the variables with less categories and the continuous variable.
this effect is weakened but not substantially altered by scaling the measure .
as opposed to the obvious effect in the selection frequencies and the gini importance, there is no effect in the mean values of the distributions of the permutation importance measures, which are in mean close to zero as expected for uninformative variables.
however, the notable differences in the variance of the distributions for predictor variables with different scale of measurement or number of categories seriously affect the expressiveness of the variable importance measure.
in a single trial this effect may lead to a severe over- or underestimation of the variable importance of variables that have more categories as an artefact of the method, even though they are no more or less informative than the other variables.
only when the cforest function is used together with subsampling without replacement  does the deviation of the permutation importance measure over the simulation runs not increase substantially with the number of categories or scale of measurement of the predictor variables.
thus, only the variable importance measure available in cforest, and only when used together with sampling without replacement, reliably reflects the true importance of potential predictor variables in a scenario where the potential predictor variables vary in their scale of measurement or number of categories.
results of the power case simulation study
in the power case, where only the predictor variable x <dig> is informative, a sensible variable importance measure should be able to distinguish the informative predictor variable.
the following figures display the results of the power case with the highest value  <dig>  of the relevance parameter, indicating a high degree of dependence between x <dig> and the response.
in this setting, each of the variable importance measures should clearly prefer x <dig>  while the respective values for the remaining predictor variables should be equally low.
the mean gini importance, that is displayed in figure  <dig>  again shows a strong bias towards variables with many categories and the continuous variable.
it completely fails to identify the relevant predictor variable, with the mean value for the relevant variable x <dig> only slightly higher than in the null case.
figures  <dig> and  <dig> show boxplots of the distributions of the unscaled and scaled permutation importance measures of both functions.
again for the randomforest function  and, less pronounced, for the cforest function with bootstrap sampling , the deviation of the permutation importance measure over the simulation runs is highest for the variable x <dig> with the highest number of categories, and decreases for the variables with less categories and the continuous variable.
this effect is weakened but not substantially altered by scaling the measure .
as expected the mean value of the permutation importance measure for the informative predictor variable x <dig> is higher than for the uninformative variables.
however, the deviation of the variable importance measure for the uninformative variables with many categories x <dig> and x <dig> is so high that in a single trial these uninformative variables may outperform the informative variable as an artefact of the method.
thus, only the variable importance measure computed with the cforest function, and only when used together with sampling without replacement, is able to reliably detect the informative variable out of a set of uninformative competitors, even if the degree of dependence between x <dig> and the response is high.
the rate at which the informative predictor variable is correctly identified  increases with the degree of dependence between x <dig> and the response.
in table  <dig> the rates of correct identifications  for four different degrees of dependence between x <dig> and the response are summarized for the randomforest and cforest function with different options.
rates of correct identifications of the informative variable with the scaled and unscaled permutation importance of the randomforest method, applied with sampling with and without replacement, as compared to those of the cforest method, applied with sampling with and without replacement, as a function of the degree of dependence  between the informative variable x <dig> and the response.
/1000
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaadagcaaqaaiabdkhayjabgwsixlabcicaoiabigdaxiabgkhitiabdkhayjabcmcapiabc+caviabigdaxiabicdawiabicdawiabicdawawcbeaaaaa@3a1a@.)
for all degrees of dependence between x <dig> and the response y the cforest function detects the informative variable more reliably than the randomforest function, and the cforest function used with subsampling without replacement outperforms the cforest function with bootstrap sampling with replacement.
for the randomforest function scaling the permutation importance measure can slightly increase the rates of correct identifications because, as shown in figures  <dig> and  <dig>  scaling weakens the differences in variance of the permutation importance measure for variables of different scale of measurement and number of categories.
for the cforest function, that is not affected by the scale of measurement and number of categories of the predictor variables, both the unscaled and the scaled permutation importance perform equally well.
so far we have seen that for the assessment of variable importance and variable selection purposes it is important to use a reliable method, that is not affected by other characteristics of the predictor variables.
statistical explanations of our findings are given in a later section.
in addition to its superiority in the assessment of variable importance the cforest method, especially when used together with subsampling without replacement, can also be superior to the randomforest method with respect to classification accuracy in situations like that of the power case simulation study, where uninformative predictor variables with many categories "fool" the randomforest function.
due to its artificial preference for uninformative predictor variables with many categories the randomforest function can produce a higher mean misclassification rate than the cforest function.
the mean misclassification rates  for the randomforest and cforest function, again for four different degrees of dependence and used with sampling with and without replacement, are displayed in table  <dig>
mean misclassification rates of the randomforest method, applied with sampling with and without replacement, as compared to those of the cforest method, applied with sampling with and without replacement, as a function of the degree of dependence  between the informative variable x <dig> and the response.
each method was applied to the same simulated test set in each simulation run.
the test sets were generated from the same data generating process as the learning sets.
we find that for all degrees of dependence between x <dig> and the response y the cforest function, especially with sampling without replacement, outperforms the other methods.
a similar result is obtained in the application to c-to-u conversion data presented in the next section.
the differences in classification accuracy are moderate in the latter case, however one could think of more extreme situations that would produce even greater differences.
this shows that the same mechanisms underlying the variable importance bias can also affect the classification accuracy, e.g.
when suboptimal predictor variables, that do not add to the classification accuracy, are artificially preferred in variable selection merely because they have more categories.
application to c-to-u conversion data
rna editing is the process whereby rna is modified from the sequence of the corresponding dna template  <cit> .
for instance, cytidine-to-uridine conversion  is common in plant mitochondria.
the mechanisms of this conversion remain largely unknown, although the role of neighboring nucleotides is emphasized.
cummings and myers  <cit>  suggest to use information from sequence regions flanking the sites of interest to predict editing in arabidopsis thaliana, brassica napus and oryza sativa based on random forests.
the arabidopsis thaliana data of  <cit>  can be loaded from the journal's homepage.
for each of the  <dig> observations, the data set gives
• the response at the site of interest  and as potential predictor variables
• the  <dig> nucleotides at positions - <dig> to  <dig>  relative to the edited site ,
• the codon position ,
• the estimated folding energy  and
• the difference in estimated folding energy between pre-edited and edited sequences .
we first derive the permutation importance measure for each of the  <dig> potential predictor variables with each method.
as can be seen from the barplot in figure  <dig>  the  variable importance measures largely reflect the results of  <cit>  based on the gini importance measure, but differ slightly for the randomforest and cforest function and the different resampling schemes.
in particular, the variable importance measure of the randomforest function seems to produce more "noise" than that of the cforest function: the contrast of amplitudes between irrelevant and relevant predictors is more pronounced when the cforest function is used.
note, however, that the the permutation importance values for one predictor variable can vary between two computations, because each computation is based on a different random permutation of the variable.
therefore, before interpreting random forest permutation importance values, the analysis should be repeated  to test the stability of the results.
similarly to the simulation study, we also compared the prediction accuracy of the four approaches for this data set.
to do so, we split the original data set into learning and test sets with size ratio 2: <dig> in a standard split-sample validation scheme.
a random forest is grown based on the learning set and subsequently used to predict the observations in the test set.
this procedure is repeated  <dig> times, and the mean misclassification rates over the  <dig> runs are reported in table  <dig>  again we find a slight superiority of the cforest function, especially when sampling is conducted without replacement.
mean misclassification rates of the randomforest method applied with sampling with and without replacement as compared to those of the cforest method applied with sampling with and without replacement.
all function calls and all important options of the randomforest and cforest functions used in the simulation studies and the application to c-to-u conversion data are documented in the supplement .
sources of variable importance bias
the main difference between the randomforest function, based on cart trees  <cit> , and cforest function, based on conditional inference trees  <cit> , is that in randomforest the variable selection in the individual cart trees is biased, so that e.g.
variables with more categories are preferred.
this is illustrated in the next section on variable selection bias in individual classification trees.
however, even if the individual trees select variables in an unbiased way as in the cforest function, we find that the variable importance measures, as well as the selection frequencies of the variables, are affected by the bootstrap sampling with replacement.
this is explained in the section on effects induced by bootstrapping.
variable selection bias in the individual classification trees of a random forest
let us again consider the null case simulation study design, where none of the variables is informative, and thus should be selected with equally low probabilities in a classification tree.
in traditional classification tree algorithms, like cart, for each variable a split criterion like the "gini index" is computed for all possible cutpoints within the range of that variable.
the variable selected for the next split is the one that produced the highest criterion value overall, i.e.
in its best cutpoint.
obviously variables with more potential cutpoints are more likely to produce a good criterion value by chance, as in a multiple testing situation.
therefore, if we compare the highest criterion value of a variable with two categories, say, that provides only one cutpoint from which the criterion was computed, with a variable with four categories, that provides seven cutpoints from which the best criterion value is used, the latter is often preferred.
because the number of cutpoints grows exponentially with the number of categories of unordered categorical predictors we find a preference for variables with more categories in cart-like classification trees.
for further reading on variable selection bias in classification trees see, e.g., the corresponding sections in  <cit> .
since the gini importance measure in randomforest is directly derived from the gini index split criterion used in the underlying individual classification trees, it carries forward the same bias, as was shown in figures  <dig> and  <dig>
conditional inference trees  <cit> , that are used to construct the classification trees in cforest, are unbiased in variable selection.
here, the variable selection is conducted by minimizing the p value of a conditional inference independence test, comparable e.g.
to the χ <dig> test, that incorporates the number of categories of each variable in the degrees of freedom.
the mean selection frequencies  of the five predictor variables of the null case simulation study design for both cart classification trees  and conditional inference trees  are displayed in figure  <dig>  we find that the variable selection with the rpart function is highly biased, while for the ctree function it is unbiased.
the variable selection bias that occurs in every individual tree in the randomforest function also has a direct effect on the variable importance measures of this function.
predictor variables with more categories are artificially preferred in variable selection in each splitting decision.
thus, they are selected in more individual classification trees and tend to be situated closer to the root node in each tree.
the variable selection bias affects the variable importance measures in two respects.
firstly, the variable selection frequencies over all trees are directly affected by the variable selection bias in each individual tree.
secondly, the effect on the permutation importance is less obvious but just as severe.
when permuting the variables to compute their permutation importance measure, the variables that appear in more trees and are situated closer to the root node can affect the prediction accuracy of a larger set of observations, while variables that appear in fewer trees and are situated closer to the bottom nodes affect only small subsets of observations.
thus, the range of possible changes in prediction accuracy in the random forest, i.e.
the deviation of the variable importance measure, is higher for variables that are preferred by the individual trees due to variable selection bias.
we found in figures  <dig> through  <dig>  that the effects induced by the differences in scale of measurement of the predictor variables were more pronounced for the randomforest function, where variable selection in the individual trees is biased, than for the cforest function, where the individual trees are unbiased.
however, we also found that when the cforest function is used with bootstrap sampling, the variable selection frequencies of the categorical predictors still depend on their number of categories , and also the deviation of the permutation importance measure is still affected by the number of categories .
thus, there must be another source of bias, besides the variable selection bias in the individual trees, that affects the selection frequencies and the deviation of the permutation importance measure.
we show in the next section that this additional effect is due to bootstrap sampling with replacement, that is traditionally employed in random forests.
effects induced by bootstrapping
from the comparison of left and right columns  in figures  <dig> and  <dig> we learned that the variable selection frequencies in random forest functions are affected by the resampling scheme.
we found that, even when the cforest function based on unbiased classification trees is used, variables with more categories are preferred when bootstrap sampling is conducted with replacement, while no bias occurs when subsampling is conducted without replacement, as displayed in the bottom right plot in figures  <dig> and  <dig>  thus, the bootstrap sampling induces an effect that is more pronounced for predictor variables with more categories.
for a better understanding of the underlying mechanism let us consider only the categorical predictor variables x <dig> through x <dig> with different numbers of categories from the null case simulation study design.
rather than trying to explain the effect of bootstrap sampling in the complex framework of random forests, we use a much simpler independence test for the explanation.
we consider the p values of χ <dig> tests .
in each simulation run, a χ <dig> test is computed for each predictor variable and the binary response y. remember that the variables in the null case are not informative, i.e.
the response is independent of all variables.
for independent variables the distribution of the p values of the χ <dig> test is supposed to form a uniform distribution.
the left plot in figure  <dig> displays the distribution of the p values of χ <dig> tests from each predictor variable and the response y as boxplots.
we find that the boxplots range from  <dig> to  <dig> with median  <dig>  as expected, because the p values of the χ <dig> test form a uniform distribution when computed before bootstrapping.
however, if in each simulation run we draw a bootstrap sample from the original sample and then again compute the p values based on the bootstrap sample, we find that the distribution of the p values is shifted towards zero as displayed in the right plot in figure  <dig>
obviously, the bootstrap sampling artificially induces an association between the variables.
this effect is always present when statistical inference, such as an association test, is carried out on bootstrap samples: bickel and ren  <cit>  point out that bootstrap hypothesis testing fails whenever the distribution of any statistic in the bootstrap sample, rather than the distribution of the statistic under the null hypothesis, is used for statistical inference.
we found that this issue directly affects variable selection in random forests, because the deviation from the null hypothesis is more pronounced for variables that have more categories.
the reason for the shift in the distribution of the p values displayed in figure  <dig> is that each original sample, even if sampled from theoretically independent distributions, may show some minor variations from the null hypothesis of independence.
these minor variations are aggravated by bootstrap sampling with replacement, because the cell counts in the contingency table are affected by observations that are either not included or are doubled or tripled in the bootstrap sample, and therefore the bootsrap sample deviates notably from the null hypothesis – even if the original sample was generated under the null hypothesis.
this effect is more pronounced for variables with more categories, because in larger tables , the absolute cell counts are smaller than in smaller tables .
with respect to the smaller absolute cell counts, excluding or duplicating an observation produces more severe variations from the null hypothesis.
this effect is not eliminated if the sample size is increased, because in bootstrap sampling the size n of the original sample and the bootstrap sample size n increase simultaneously.
however, if subsamples are drawn without replacement the effect disappears.
the apparent association that is induced by bootstrap sampling, and that is more pronounced for predictor variables with many categories, affects both variable importance measures: the selection frequency is again directly affected, and the permutation importance is affected because variables with many categories are selected more often and gain positions closer to the root node in the individual trees.
together with the mechanisms described in the previous section, this explains our findings.
from our simulation results we can see, however, that the effect of bootstrap sampling is mostly superposed by the much stronger effect of variable selection bias when comparing the conditions of sampling with and without replacement for the randomforest function only .
only when variable selection bias is removed by the cforest function the differences between the conditions of sampling with and without replacement are obvious .
we therefore conclude that in order to be able to reliably interpret the variable importance measures of a random forest, the forest must be built from unbiased classification trees, and sampling must be conducted without replacement.
CONCLUSIONS
random forests are a powerful statistical tool, that has found many applicants in various scientific areas.
it has been applied to such a wide variety of problems as large-scale association studies for complex genetic diseases, the prediction of phenotypes based on amino acid or dna sequences, qsar modeling and clinical medicine, to name just a few.
features that have added to the popularity of random forests especially in bioinformatics and related fields, where identifying a subset of relevant predictor variables from very large sets of candidates is the major challenge, include its ability to deal with critical "small n large p" data sets and the variable importance measures it provides for variable selection purposes.
however, when a method is used for variable selection, rather than prediction only, it is particularly important that the value and interpretation of the variable importance measure actually depict the importance of the variable, and are not affected by any other characteristics.
we found that for the original random forest method the variable importance measures are affected by the number of categories and scale of measurement of the predictor variables, which are no direct indicators of the true importance of the variable.
as long as, e.g., only continuous predictor variables, as in most gene expression studies, or only variables with the same number of categories are considered in the sample, variable selection with random forest variable importance measures is not affected by our findings.
however, in studies where continuous variables, such as the folding energy, are used in combination with categorical information from the neighboring nucleotides, or when categorical predictors, as in amino acid sequence data, vary in their number of categories present in the sample variable selection with random forest variable importance measures is unreliable and may even be misleading.
especially informations on clinical and environmental variables are often gathered by means of questionnaires, where the number of categories can vary between questions.
the number of categories is typically determined by many different factors, but is not necessarily an indicator of variable importance.
similarly, the number of different categories of a predictor actually available in a certain sample is not an indicator of its relevance for predicting the response.
hence, the number of categories of a variable should not influence its estimated importance – otherwise the results of a study could easily be distorted when an irrelevant variable with many categories is included in the study design.
we showed that, due to variable selection bias in the individual classification trees and effects induced by bootstrap sampling, the variable importance measures of the randomforest function are not reliable in many scenarios relevant in applied research.
as an alternative random forest method we propose to use the cforest function, that provides unbiased variable selection in the individual classification trees.
when this method is applied with subsampling without replacement the resulting variable importance measure can be used reliably for variable selection even in situations where the potential predictor variables vary in their scale of measurement or their number of categories.
with respect to computation time the cforest function is more expensive than the randomforest function, because in order to be unbiased split decisions and stopping rely on time-consuming conditional inference.
to give an impression, the computation times of the application to c-to-u conversion data, with  <dig> observations and  <dig> predictor variables, as stated in the supplementary file for the cforest function used with bootstrap sampling with replacement are in the range of  <dig>  sec., while subsampling without replacement is computationally less expensive and in the range of  <dig> .
since we saw that only subsampling without replacement guarantees reliable variable selection and produces unbiased variable importance measures, the faster version without replacement should be preferred anyway.
the computation time for the randomforest function is in the range of  <dig>  sec.
with and  <dig>  sec.
without replacement.
however, we saw that the randomforest function should not be used when the potential predictor variables vary in their scale of measurement or their number of categories.
the aim of this paper was to explore the limits of the empirical measures of variable importance provided for random forests, to understand the underlying mechanisms and to use that understanding to guarantee unbiased and reliable variable selection in random forests.
in a more theoretical work van der laan  <cit>  gives a fundamental definition of variable importance, as well as a statistical inference framework for estimating and testing variable importance.
inspired by this approach, future research on variable importance measures for variable selection with random forests aims at providing further means of statistical inference, that can be used to guide the decision on which and how many predictor variables to select in a certain problem.
authors' contributions
cs first observed the variable selection bias in random forests, set up and performed the simulation experiments, studied the sources of the selection bias and drafted the manuscript.
alb, az and th contributed to the design of the simulation experiments, to theoretical investigations of the problem, and to the manuscript.
th implemented the cforest, ctree and varimp functions.
alb analyzed the c-to-u conversion data.
all authors read and approved the final manuscript.
supplementary material
additional file 1
r source code.
the exemplary r source code includes all function calls and comments on all important options of the randomforest and cforest functions, that were used in the simulation studies and the application to c-to-u conversion data.
please install the latest versions of the packages randomforest and party before use.
click here for file
acknowledgements
cs was supported by the german research foundation , collaborative research center  <dig> "statistical analysis of discrete structures".
th received financial support from dfg grant ho 3242/1– <dig>  the authors would like to thank thomas augustin, friedrich leisch and gerhard tutz for fruitful discussions and for supporting our interest in this field of research, and peter bühlmann, an anonymous referee and a semi-anonymous referee for their helpful suggestions.

 in bioinformatics and related scientific fields, such as statistical genomics and genetic epidemiology, an important task is the prediction of a categorical response variable based on a large number of predictors. the aim of this research is on one hand to predict the value of the response variable from the values of the predictors, i.e. to create a diagnostic tool, and on the other hand to reliably identify relevant predictors from a large set of candidate variables. from a statistical point of view, one of the challenges in identifying these relevant predictor variables is the so-called "small n large p" problem: usual data sets in genomics often contain hundreds or thousands of genes or markers that serve as predictor variables x..., xp, but only for a comparatively small number n of subjects or tissue types. traditional statistical models used in clinical case control studies for predicting the disease status from selected predictor variables, such as logistic regression, are not suitable for "small n large p" problems. a more appropriate approach from machine learning, that has been proposed recently for prediction and variable selection in various fields related to bioinformatics and computational biology, is the nonlinear and nonparametric random forest method. it also provides variable importance measures for variable selection purposes. random forests have been successfully applied to various problems in, e.g., genetic epidemiology and microbiology in general within the last five years. within a very short period of time, random forests have become a major data analysis tool, that performs well in comparison with many standard methods. what has greatly contributed to the popularity of random forests is the fact that they can be applied to a wide range of prediction problems, even if they are nonlinear and involve complex high-order interaction effects, and that random forests produce variable importance measures for each predictor variable. applications of random forests in bioinformatics include large-scale association studies for complex genetic diseases, as e.g. lunetta et al. and bureau et al., who detect snp-snp interactions in the case-control context by means of computing a random forest variable importance measure for each polymorphism. a comparison of the performance of random forests and other classification methods for the analysis of gene expression data is presented by díaz-uriate and alvarez de andrés, who propose a new gene selection method based on random forests for sample classification with microarray data. we refer to for other applications of the random forest methodology to microarray data. prediction of phenotypes based on amino acid or dna sequence is another important area of application of random forests, since possibly involving many interactions. for example, segal et al. use random forests to predict the replication capacity of viruses, such as hiv- based on amino acid sequence from reverse transcriptase and protease. cummings and segal link the rifampin resistance in mycobacterium tuberculosis to a few amino acid positions in rpob, whereas cummings and myers predict c-to-u edited sites in plant mitochondrial rna based on sequence regions flanking edited sites and a few other parameters. the random forest approach was shown to outperform six other methods in the prediction of protein interactions based on various biological features such as gene expression, gene ontology features and sequence data. other applications of random forests can be found in fields as different as quantitative structure-activity relationship modeling, nuclear magnetic resonance spectroscopy, landscape epidemiology and medicine in general. the scope of this paper is to show that the variable importance measures of breiman's original random forest method, based on cart classification trees, are a sensible means for variable selection in many of these applications, but are not reliable in situations where potential predictor variables vary in their scale of measurement or their number of categories, as, e.g., when both genetic and environmental variables, individually and in interactions, are considered as potential predictors, or predictor variables of the same type vary in the number of categories present in a certain sample, as is often the case in genomics, bioinformatics and related disciplines. simulation studies are presented illustrating that variable selection with the variable importance measure of the original random forest method bears the risk that suboptimal predictor variables are artificially preferred in such scenarios. in an extra section, further details and explanations of the statistical sources underlying the deficiency of the variable importance measures of the original random forest method, namely biased variable selection in the individual classification trees used to build the random forest and effects induced by bootstrap sampling with replacement, are given. we propose to employ an alternative random forest method, the variable importance measure of which can be employed to reliably select relevant predictor variables in any data set. the performance of this method is compared to that of the original random forest method in simulation studies, and is illustrated by an application to the prediction of c-to-u edited sites in plant mitochondrial rna, re-analyzing the data of that were previously analyzed with the original random forest method. methods here we focus on the use of random forests for classification tasks, rather than regression tasks, for instance for predicting the disease status from a set of selected genetic and environmental risk factors, or for predicting whether a site of interest is edited by means of neighboring sites and other predictor variables as in our application example. random forests are an ensemble method that combines several individual classification trees in the following way: from the original sample several bootstrap samples are drawn, and an unpruned classification tree is fit to each bootstrap sample. the variable selection for each split in the classification tree is conducted only from a small random subset of predictor variables, so that the "small n large p" problem is avoided. from the complete forest the status of the response variable is predicted as an average or majority vote of the predictions of all trees. random forests can highly increase the prediction accuracy as compared to individual classification trees, because the ensemble adjusts for the instability of the individual trees induced by small changes in the learning sample, that impairs the prediction accuracy in test samples. however, the interpretability of a random forest is not as straightforward as that of an individual classification tree, where the influence of a predictor variable directly corresponds to its position in the tree. thus, alternative measures for variable importance are required for the interpretation of random forests. random forest variable importance measures a naive variable importance measure to use in tree-based ensemble methods is to merely count the number of times each variable is selected by all individual trees in the ensemble. more elaborate variable importance measures incorporate a mean of the individual trees' improvement in the splitting criterion produced by each variable. an example for such a measure in classification is the "gini importance" available in random forest implementations. the "gini importance" describes the improvement in the "gini gain" splitting criterion. the most advanced variable importance measure available in random forests is the "permutation accuracy importance" measure. its rationale is the following: by randomly permuting the predictor variable xj, its original association with the response y is broken. when the permuted variable xj, together with the remaining unpermuted predictor variables, is used to predict the response, the prediction accuracy decreases substantially, if the original variable xj was associated with the response. thus, a reasonable measure for variable importance is the difference in prediction accuracy before and after permuting xj. for variable selection purposes the advantage of the random forest permutation accuracy importance measure as compared to univariate screening methods is that it covers the impact of each predictor variable individually as well as in multivariate interactions with other predictor variables. for example, lunetta et al. find that genetic markers relevant in interactions with other markers or environmental variables can be detected more efficiently by means of random forests than by means of univariate screening methods like fisher's exact test. the gini importance and the permutation accuracy importance measures are employed as variable selection criteria in many recent studies in various disciplines related to bioinformatics, as outlined in the background section. therefore we want to investigate their reliability as variable importance measures in different scenarios. in the simulation studies presented in the next section, we compare the behavior of all three random forest variable importance measures, namely the number of times each variable is selected by all individual trees in the ensemble, the "gini importance" and the permutation accuracy importance measure. simulation studies the reference implementation of breiman's original random forest method is available in the r system for statistical computing via the randomforest add-on package by liaw and wiener. the behavior of the selection frequency, the gini importance and the permutation importance of the randomforest function is explored in a simulation design where potential predictor variables vary in their scale of measurement and number of categories. as an alternative, we propose to use the new random forest function cforest available in the r add-on package party in such scenarios. in contrast to randomforest, the cforest function creates random forests not from cart classification trees based on the gini split criterion, that are known to prefer variables with, e.g., more categories in variable selection, but from unbiased classification trees based on a conditional inference framework. the problem of biased variable selection in classification trees is covered more thoroughly in a separate section below. since the cforest function does not employ the gini criterion, we investigate the behavior of the gini importance for the randomforest function only. the selection frequency and the permutation importance is studied for both functions randomforest and cforest in two ways: either the individual trees are built on bootstrap samples of the original sample size n drawn with replacement, as suggested in, or on subsamples drawn without replacement. for sampling without replacement the subsample size here is set to times the original sample size n, because in bootstrap sampling with replacement about % of the data end up in the bootstrap sample. other fractions for the subsample size are possible, for instance as suggested by friedman and hall. subsampling as an alternative to bootstrap sampling in aggregating, e.g., individual classification trees is investigated further by bühlmann and yu, who also coin the term "subagging" as an abbreviation for "subsample aggregating" as opposed to "bagging" for "bootstrap aggregating". politis, romano and wolf show that, for statistical inference in general, subsampling works under weaker assumptions than bootstrap sampling and even in situations when bootstrap sampling fails. the simulation design used throughout this paper represents a scenario where a binary response variable y is supposed to be predicted from a set of potential predictor variables that vary in their scale of measurement and number of categories. the first predictor variable x is continuous, while the other predictor variables x..., x are categorical with their number of categories between two and up to twenty. the simulation designs of both studies are summarized in tables and the sample size for all simulation studies was set to n = the predictor variables are sampled independently from the following distributions. n stands for the standard normal distribution, m stands for the multinomial distribution with values in {..., k - 1} and equal probabilities, b stands for the binomial distribution with probability p, thus m equals b. the response variable is sampled from binomial distributions. the degree of dependence between the response y and x is regulated by the probability p of the binomial distribution b of y conditional on x with the relevance parameter taking values in {,,, } to model different degrees of dependence. in the first simulation study, the so-called null case, none of the predictor variables is informative for the response, i.e. all predictor variables and the response are sampled independently. in this situation a sensible variable importance measure should not prefer any one predictor variable over any other. in the second simulation study, the so-called power case, the predictor variable x is informative for the response, i.e. the distribution of the response depends on the value of this predictor variable. the degree of dependence between the informative predictor variable x and the response y is regulated by the relevance parameter of the conditional distribution of y given x. we will later display results for different values of the relevance parameter indicating different degrees of dependence between x and y. in the power case, a sensible variable importance measure should be able to distinguish the informative predictor variable from its uninformative competitors, and even more so with increasing degree of dependence.  our simulation studies show that for the randomforest function all three variable importance measures are unreliable, and the gini importance is most strongly biased. for the cforest function reliable results can be achieved both with the selection frequency and the permutation importance if the function is used together with subsampling without replacement. otherwise the measures are biased as well. results of the null case simulation study in the null case, when all predictor variables are equally uninformative, the selection frequencies as well as the gini importance and the permutation importance of all predictor variables are supposed to be equal. however, as presented in figure the mean selection frequencies of the predictor variables differ substantially when the randomforest function or the cforest function with bootstrap sampling are used. variables with more categories are obviously preferred. only when the cforest function is used together with subsampling without replacement are the variable selection frequencies for the uninformative predictor variables equally low as desired. it is obvious that variable importance cannot be represented reliably by the selection frequencies, that can be considered as very basic variable importance measures, if the potential predictor variables vary in their scale of measurement or number of categories when the randomforest function or the cforest function with bootstrap sampling is used. the mean gini importance, that is displayed in figure is biased even stronger. like the selection frequencies for the randomforest function the gini importance shows a strong preference for variables with many categories and the continuous variable, the statistical sources of which are explained in the section on variable selection bias in classification trees below. we conclude that the gini importance cannot be used to reliably measure variable importance in this situation either. we now consider the more advanced permutation importance measure. we find that here an effect of the scale of measurement or number of categories of the potential predictor variables is less obvious but still severely affects the reliability and interpretability of the variable importance measure. the scaled variable importance is the default output of the randomforest function. however, it has been noted, e.g., by díaz-uriate and alvarez de andrés in their supplementary material, that the scaled variable importance of the randomforest function depends on the number of trees grown in the random forest. therefore we suggest not to interpret the magnitude of the scaled variable importance of the randomforest function. the plots show that for the randomforest function and, less pronounced, for the cforest function with bootstrap sampling, the deviation of the permutation importance measure over the simulation runs is highest for the variable x with the highest number of categories, and decreases for the variables with less categories and the continuous variable. this effect is weakened but not substantially altered by scaling the measure. as opposed to the obvious effect in the selection frequencies and the gini importance, there is no effect in the mean values of the distributions of the permutation importance measures, which are in mean close to zero as expected for uninformative variables. however, the notable differences in the variance of the distributions for predictor variables with different scale of measurement or number of categories seriously affect the expressiveness of the variable importance measure. in a single trial this effect may lead to a severe over- or underestimation of the variable importance of variables that have more categories as an artefact of the method, even though they are no more or less informative than the other variables. only when the cforest function is used together with subsampling without replacement does the deviation of the permutation importance measure over the simulation runs not increase substantially with the number of categories or scale of measurement of the predictor variables. thus, only the variable importance measure available in cforest, and only when used together with sampling without replacement, reliably reflects the true importance of potential predictor variables in a scenario where the potential predictor variables vary in their scale of measurement or number of categories. results of the power case simulation study in the power case, where only the predictor variable x is informative, a sensible variable importance measure should be able to distinguish the informative predictor variable. the following figures display the results of the power case with the highest value of the relevance parameter, indicating a high degree of dependence between x and the response. in this setting, each of the variable importance measures should clearly prefer x while the respective values for the remaining predictor variables should be equally low. the mean gini importance, that is displayed in figure again shows a strong bias towards variables with many categories and the continuous variable. it completely fails to identify the relevant predictor variable, with the mean value for the relevant variable x only slightly higher than in the null case. figures and show boxplots of the distributions of the unscaled and scaled permutation importance measures of both functions. again for the randomforest function and, less pronounced, for the cforest function with bootstrap sampling, the deviation of the permutation importance measure over the simulation runs is highest for the variable x with the highest number of categories, and decreases for the variables with less categories and the continuous variable. this effect is weakened but not substantially altered by scaling the measure. as expected the mean value of the permutation importance measure for the informative predictor variable x is higher than for the uninformative variables. however, the deviation of the variable importance measure for the uninformative variables with many categories x and x is so high that in a single trial these uninformative variables may outperform the informative variable as an artefact of the method. thus, only the variable importance measure computed with the cforest function, and only when used together with sampling without replacement, is able to reliably detect the informative variable out of a set of uninformative competitors, even if the degree of dependence between x and the response is high. the rate at which the informative predictor variable is correctly identified increases with the degree of dependence between x and the response. in table the rates of correct identifications for four different degrees of dependence between x and the response are summarized for the randomforest and cforest function with different options. rates of correct identifications of the informative variable with the scaled and unscaled permutation importance of the randomforest method, applied with sampling with and without replacement, as compared to those of the cforest method, applied with sampling with and without replacement, as a function of the degree of dependence between the informative variable x and the response. /1000 mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaadagcaaqaaiabdkhayjabgwsixlabcicaoiabigdaxiabgkhitiabdkhayjabcmcapiabc+caviabigdaxiabicdawiabicdawiabicdawawcbeaaaaa@3a1a@.) for all degrees of dependence between x and the response y the cforest function detects the informative variable more reliably than the randomforest function, and the cforest function used with subsampling without replacement outperforms the cforest function with bootstrap sampling with replacement. for the randomforest function scaling the permutation importance measure can slightly increase the rates of correct identifications because, as shown in figures and scaling weakens the differences in variance of the permutation importance measure for variables of different scale of measurement and number of categories. for the cforest function, that is not affected by the scale of measurement and number of categories of the predictor variables, both the unscaled and the scaled permutation importance perform equally well. so far we have seen that for the assessment of variable importance and variable selection purposes it is important to use a reliable method, that is not affected by other characteristics of the predictor variables. statistical explanations of our findings are given in a later section. in addition to its superiority in the assessment of variable importance the cforest method, especially when used together with subsampling without replacement, can also be superior to the randomforest method with respect to classification accuracy in situations like that of the power case simulation study, where uninformative predictor variables with many categories "fool" the randomforest function. due to its artificial preference for uninformative predictor variables with many categories the randomforest function can produce a higher mean misclassification rate than the cforest function. the mean misclassification rates for the randomforest and cforest function, again for four different degrees of dependence and used with sampling with and without replacement, are displayed in table mean misclassification rates of the randomforest method, applied with sampling with and without replacement, as compared to those of the cforest method, applied with sampling with and without replacement, as a function of the degree of dependence between the informative variable x and the response. each method was applied to the same simulated test set in each simulation run. the test sets were generated from the same data generating process as the learning sets. we find that for all degrees of dependence between x and the response y the cforest function, especially with sampling without replacement, outperforms the other methods. a similar result is obtained in the application to c-to-u conversion data presented in the next section. the differences in classification accuracy are moderate in the latter case, however one could think of more extreme situations that would produce even greater differences. this shows that the same mechanisms underlying the variable importance bias can also affect the classification accuracy, e.g. when suboptimal predictor variables, that do not add to the classification accuracy, are artificially preferred in variable selection merely because they have more categories. application to c-to-u conversion data rna editing is the process whereby rna is modified from the sequence of the corresponding dna template. for instance, cytidine-to-uridine conversion is common in plant mitochondria. the mechanisms of this conversion remain largely unknown, although the role of neighboring nucleotides is emphasized. cummings and myers suggest to use information from sequence regions flanking the sites of interest to predict editing in arabidopsis thaliana, brassica napus and oryza sativa based on random forests. the arabidopsis thaliana data of can be loaded from the journal's homepage. for each of the observations, the data set gives • the response at the site of interest and as potential predictor variables • the nucleotides at positions - to relative to the edited site, • the codon position, • the estimated folding energy and • the difference in estimated folding energy between pre-edited and edited sequences. we first derive the permutation importance measure for each of the potential predictor variables with each method. as can be seen from the barplot in figure the variable importance measures largely reflect the results of based on the gini importance measure, but differ slightly for the randomforest and cforest function and the different resampling schemes. in particular, the variable importance measure of the randomforest function seems to produce more "noise" than that of the cforest function: the contrast of amplitudes between irrelevant and relevant predictors is more pronounced when the cforest function is used. note, however, that the the permutation importance values for one predictor variable can vary between two computations, because each computation is based on a different random permutation of the variable. therefore, before interpreting random forest permutation importance values, the analysis should be repeated to test the stability of the results. similarly to the simulation study, we also compared the prediction accuracy of the four approaches for this data set. to do so, we split the original data set into learning and test sets with size ratio 2: in a standard split-sample validation scheme. a random forest is grown based on the learning set and subsequently used to predict the observations in the test set. this procedure is repeated times, and the mean misclassification rates over the runs are reported in table again we find a slight superiority of the cforest function, especially when sampling is conducted without replacement. mean misclassification rates of the randomforest method applied with sampling with and without replacement as compared to those of the cforest method applied with sampling with and without replacement. all function calls and all important options of the randomforest and cforest functions used in the simulation studies and the application to c-to-u conversion data are documented in the supplement. sources of variable importance bias the main difference between the randomforest function, based on cart trees, and cforest function, based on conditional inference trees, is that in randomforest the variable selection in the individual cart trees is biased, so that e.g. variables with more categories are preferred. this is illustrated in the next section on variable selection bias in individual classification trees. however, even if the individual trees select variables in an unbiased way as in the cforest function, we find that the variable importance measures, as well as the selection frequencies of the variables, are affected by the bootstrap sampling with replacement. this is explained in the section on effects induced by bootstrapping. variable selection bias in the individual classification trees of a random forest let us again consider the null case simulation study design, where none of the variables is informative, and thus should be selected with equally low probabilities in a classification tree. in traditional classification tree algorithms, like cart, for each variable a split criterion like the "gini index" is computed for all possible cutpoints within the range of that variable. the variable selected for the next split is the one that produced the highest criterion value overall, i.e. in its best cutpoint. obviously variables with more potential cutpoints are more likely to produce a good criterion value by chance, as in a multiple testing situation. therefore, if we compare the highest criterion value of a variable with two categories, say, that provides only one cutpoint from which the criterion was computed, with a variable with four categories, that provides seven cutpoints from which the best criterion value is used, the latter is often preferred. because the number of cutpoints grows exponentially with the number of categories of unordered categorical predictors we find a preference for variables with more categories in cart-like classification trees. for further reading on variable selection bias in classification trees see, e.g., the corresponding sections in. since the gini importance measure in randomforest is directly derived from the gini index split criterion used in the underlying individual classification trees, it carries forward the same bias, as was shown in figures and conditional inference trees, that are used to construct the classification trees in cforest, are unbiased in variable selection. here, the variable selection is conducted by minimizing the p value of a conditional inference independence test, comparable e.g. to the χ test, that incorporates the number of categories of each variable in the degrees of freedom. the mean selection frequencies of the five predictor variables of the null case simulation study design for both cart classification trees and conditional inference trees are displayed in figure we find that the variable selection with the rpart function is highly biased, while for the ctree function it is unbiased. the variable selection bias that occurs in every individual tree in the randomforest function also has a direct effect on the variable importance measures of this function. predictor variables with more categories are artificially preferred in variable selection in each splitting decision. thus, they are selected in more individual classification trees and tend to be situated closer to the root node in each tree. the variable selection bias affects the variable importance measures in two respects. firstly, the variable selection frequencies over all trees are directly affected by the variable selection bias in each individual tree. secondly, the effect on the permutation importance is less obvious but just as severe. when permuting the variables to compute their permutation importance measure, the variables that appear in more trees and are situated closer to the root node can affect the prediction accuracy of a larger set of observations, while variables that appear in fewer trees and are situated closer to the bottom nodes affect only small subsets of observations. thus, the range of possible changes in prediction accuracy in the random forest, i.e. the deviation of the variable importance measure, is higher for variables that are preferred by the individual trees due to variable selection bias. we found in figures through that the effects induced by the differences in scale of measurement of the predictor variables were more pronounced for the randomforest function, where variable selection in the individual trees is biased, than for the cforest function, where the individual trees are unbiased. however, we also found that when the cforest function is used with bootstrap sampling, the variable selection frequencies of the categorical predictors still depend on their number of categories, and also the deviation of the permutation importance measure is still affected by the number of categories. thus, there must be another source of bias, besides the variable selection bias in the individual trees, that affects the selection frequencies and the deviation of the permutation importance measure. we show in the next section that this additional effect is due to bootstrap sampling with replacement, that is traditionally employed in random forests. effects induced by bootstrapping from the comparison of left and right columns in figures and we learned that the variable selection frequencies in random forest functions are affected by the resampling scheme. we found that, even when the cforest function based on unbiased classification trees is used, variables with more categories are preferred when bootstrap sampling is conducted with replacement, while no bias occurs when subsampling is conducted without replacement, as displayed in the bottom right plot in figures and thus, the bootstrap sampling induces an effect that is more pronounced for predictor variables with more categories. for a better understanding of the underlying mechanism let us consider only the categorical predictor variables x through x with different numbers of categories from the null case simulation study design. rather than trying to explain the effect of bootstrap sampling in the complex framework of random forests, we use a much simpler independence test for the explanation. we consider the p values of χ tests. in each simulation run, a χ test is computed for each predictor variable and the binary response y. remember that the variables in the null case are not informative, i.e. the response is independent of all variables. for independent variables the distribution of the p values of the χ test is supposed to form a uniform distribution. the left plot in figure displays the distribution of the p values of χ tests from each predictor variable and the response y as boxplots. we find that the boxplots range from to with median as expected, because the p values of the χ test form a uniform distribution when computed before bootstrapping. however, if in each simulation run we draw a bootstrap sample from the original sample and then again compute the p values based on the bootstrap sample, we find that the distribution of the p values is shifted towards zero as displayed in the right plot in figure obviously, the bootstrap sampling artificially induces an association between the variables. this effect is always present when statistical inference, such as an association test, is carried out on bootstrap samples: bickel and ren point out that bootstrap hypothesis testing fails whenever the distribution of any statistic in the bootstrap sample, rather than the distribution of the statistic under the null hypothesis, is used for statistical inference. we found that this issue directly affects variable selection in random forests, because the deviation from the null hypothesis is more pronounced for variables that have more categories. the reason for the shift in the distribution of the p values displayed in figure is that each original sample, even if sampled from theoretically independent distributions, may show some minor variations from the null hypothesis of independence. these minor variations are aggravated by bootstrap sampling with replacement, because the cell counts in the contingency table are affected by observations that are either not included or are doubled or tripled in the bootstrap sample, and therefore the bootsrap sample deviates notably from the null hypothesis – even if the original sample was generated under the null hypothesis. this effect is more pronounced for variables with more categories, because in larger tables, the absolute cell counts are smaller than in smaller tables. with respect to the smaller absolute cell counts, excluding or duplicating an observation produces more severe variations from the null hypothesis. this effect is not eliminated if the sample size is increased, because in bootstrap sampling the size n of the original sample and the bootstrap sample size n increase simultaneously. however, if subsamples are drawn without replacement the effect disappears. the apparent association that is induced by bootstrap sampling, and that is more pronounced for predictor variables with many categories, affects both variable importance measures: the selection frequency is again directly affected, and the permutation importance is affected because variables with many categories are selected more often and gain positions closer to the root node in the individual trees. together with the mechanisms described in the previous section, this explains our findings. from our simulation results we can see, however, that the effect of bootstrap sampling is mostly superposed by the much stronger effect of variable selection bias when comparing the conditions of sampling with and without replacement for the randomforest function only. only when variable selection bias is removed by the cforest function the differences between the conditions of sampling with and without replacement are obvious. we therefore conclude that in order to be able to reliably interpret the variable importance measures of a random forest, the forest must be built from unbiased classification trees, and sampling must be conducted without replacement.  random forests are a powerful statistical tool, that has found many applicants in various scientific areas. it has been applied to such a wide variety of problems as large-scale association studies for complex genetic diseases, the prediction of phenotypes based on amino acid or dna sequences, qsar modeling and clinical medicine, to name just a few. features that have added to the popularity of random forests especially in bioinformatics and related fields, where identifying a subset of relevant predictor variables from very large sets of candidates is the major challenge, include its ability to deal with critical "small n large p" data sets and the variable importance measures it provides for variable selection purposes. however, when a method is used for variable selection, rather than prediction only, it is particularly important that the value and interpretation of the variable importance measure actually depict the importance of the variable, and are not affected by any other characteristics. we found that for the original random forest method the variable importance measures are affected by the number of categories and scale of measurement of the predictor variables, which are no direct indicators of the true importance of the variable. as long as, e.g., only continuous predictor variables, as in most gene expression studies, or only variables with the same number of categories are considered in the sample, variable selection with random forest variable importance measures is not affected by our findings. however, in studies where continuous variables, such as the folding energy, are used in combination with categorical information from the neighboring nucleotides, or when categorical predictors, as in amino acid sequence data, vary in their number of categories present in the sample variable selection with random forest variable importance measures is unreliable and may even be misleading. especially informations on clinical and environmental variables are often gathered by means of questionnaires, where the number of categories can vary between questions. the number of categories is typically determined by many different factors, but is not necessarily an indicator of variable importance. similarly, the number of different categories of a predictor actually available in a certain sample is not an indicator of its relevance for predicting the response. hence, the number of categories of a variable should not influence its estimated importance – otherwise the results of a study could easily be distorted when an irrelevant variable with many categories is included in the study design. we showed that, due to variable selection bias in the individual classification trees and effects induced by bootstrap sampling, the variable importance measures of the randomforest function are not reliable in many scenarios relevant in applied research. as an alternative random forest method we propose to use the cforest function, that provides unbiased variable selection in the individual classification trees. when this method is applied with subsampling without replacement the resulting variable importance measure can be used reliably for variable selection even in situations where the potential predictor variables vary in their scale of measurement or their number of categories. with respect to computation time the cforest function is more expensive than the randomforest function, because in order to be unbiased split decisions and stopping rely on time-consuming conditional inference. to give an impression, the computation times of the application to c-to-u conversion data, with observations and predictor variables, as stated in the supplementary file for the cforest function used with bootstrap sampling with replacement are in the range of sec., while subsampling without replacement is computationally less expensive and in the range of. since we saw that only subsampling without replacement guarantees reliable variable selection and produces unbiased variable importance measures, the faster version without replacement should be preferred anyway. the computation time for the randomforest function is in the range of sec. with and sec. without replacement. however, we saw that the randomforest function should not be used when the potential predictor variables vary in their scale of measurement or their number of categories. the aim of this paper was to explore the limits of the empirical measures of variable importance provided for random forests, to understand the underlying mechanisms and to use that understanding to guarantee unbiased and reliable variable selection in random forests. in a more theoretical work van der laan gives a fundamental definition of variable importance, as well as a statistical inference framework for estimating and testing variable importance. inspired by this approach, future research on variable importance measures for variable selection with random forests aims at providing further means of statistical inference, that can be used to guide the decision on which and how many predictor variables to select in a certain problem. authors' contributions cs first observed the variable selection bias in random forests, set up and performed the simulation experiments, studied the sources of the selection bias and drafted the manuscript. alb, az and th contributed to the design of the simulation experiments, to theoretical investigations of the problem, and to the manuscript. th implemented the cforest, ctree and varimp functions. alb analyzed the c-to-u conversion data. all authors read and approved the final manuscript. supplementary material additional file 1 r source code. the exemplary r source code includes all function calls and comments on all important options of the randomforest and cforest functions, that were used in the simulation studies and the application to c-to-u conversion data. please install the latest versions of the packages randomforest and party before use. click here for file acknowledgements cs was supported by the german research foundation, collaborative research center "statistical analysis of discrete structures". th received financial support from dfg grant ho 3242/1– the authors would like to thank thomas augustin, friedrich leisch and gerhard tutz for fruitful discussions and for supporting our interest in this field of research, and peter bühlmann, an anonymous referee and a semi-anonymous referee for their helpful suggestions.
this is particularly important in genomics and computational biology, where predictors often include variables of different types, for example when predictors include both sequence data and continuous variables such as folding energy, or when amino acid sequence data show different numbers of categories. simulation studies are presented illustrating that, when random forest variable importance measures are used with data of varying types, the results are misleading because suboptimal predictor variables may be artificially preferred in variable selection. variable importance measures for random forests have been receiving increased attention as a means of variable selection in many classification tasks in bioinformatics and related scientific fields, for instance to select a subset of genetic markers relevant for the prediction of a certain disease. we show that random forest variable importance measures are a sensible means for variable selection in many applications, but are not reliable in situations where potential predictor variables vary in their scale of measurement or their number of categories. when this method is applied using subsampling without replacement, the resulting variable importance measures can be used reliably for variable selection even in situations where the potential predictor variables vary in their scale of measurement or their number of categories. we propose to employ an alternative implementation of random forests, that provides unbiased variable selection in the individual classification trees. the usage of both random forest algorithms and their variable importance measures in the r system for statistical computing is illustrated and documented thoroughly in an application re-analyzing data from a study on rna editing. the two mechanisms underlying this deficiency are biased variable selection in the individual classification trees used to build the random forest on one hand, and effects induced by bootstrap sampling with replacement on the other hand.
 variable importance measures for random forests have been receiving increased attention as a means of variable selection in many classification tasks in bioinformatics and related scientific fields, for instance to select a subset of genetic markers relevant for the prediction of a certain disease. we show that random forest variable importance measures are a sensible means for variable selection in many applications, but are not reliable in situations where potential predictor variables vary in their scale of measurement or their number of categories. this is particularly important in genomics and computational biology, where predictors often include variables of different types, for example when predictors include both sequence data and continuous variables such as folding energy, or when amino acid sequence data show different numbers of categories.  simulation studies are presented illustrating that, when random forest variable importance measures are used with data of varying types, the results are misleading because suboptimal predictor variables may be artificially preferred in variable selection. the two mechanisms underlying this deficiency are biased variable selection in the individual classification trees used to build the random forest on one hand, and effects induced by bootstrap sampling with replacement on the other hand.  we propose to employ an alternative implementation of random forests, that provides unbiased variable selection in the individual classification trees. when this method is applied using subsampling without replacement, the resulting variable importance measures can be used reliably for variable selection even in situations where the potential predictor variables vary in their scale of measurement or their number of categories. the usage of both random forest algorithms and their variable importance measures in the r system for statistical computing is illustrated and documented thoroughly in an application re-analyzing data from a study on rna editing. therefore the suggested method can be applied straightforwardly by scientists in bioinformatics research. 