BACKGROUND
in bioinformatics and related fields, such as statistical genomics and genetic
epidemiology, data are often highly correlated, heterogeneous and high-dimensional,
with the number of predictors, also known as features or descriptors, exceeding the
number of observations.
the random forest  approach developed by leo breiman in
<dig>  <cit>  is particularly appropriate to
handle such complex data  <cit> .
in
bioinformatics, rf is a commonly used tool for classification or regression purposes
as well as for ranking candidate predictors through its inbuilt variable importance
measures .
it has been used in many applications involving high-dimensional
data.
as a nonparametric method rf can deal with nonlinearity, interactions,
correlated predictors and heterogeneity, which makes it attractive in genetic
epidemiology  <cit> .
however
in the context of classification, i.e.
when the response to be predicted is a class
membership, classification performance of rf has been shown to be suboptimal in case
of strongly unbalanced data  <cit> , i. e. when class sizes differ
considerably.
in epidemiology, unbalanced data are observed, e.g., in population-based studies
where only a small number of subjects develop a certain disease over time, while
most subjects remain healthy.
unbalanced data are also common in screening studies,
where most of the screened persons are negative, as well as in subclass analyses,
e.g., if one wants to differentiate between different subtypes of cancer.
usually
some subclasses are more common than other subclasses leading to an imbalance in
class sizes.
studies on rare diseases are a further example of unbalanced data
settings in medicine.
data can be obtained only from few persons having the specific
rare disease, while samples from healthy control persons are much easier to obtain.
of course unbalanced data are also relevant in various other areas of application
beyond the biomedical field, e.g., the prediction of creditworthiness of a
bank’s costumers  <cit> , the detection
of fraudulent telephone calls  <cit>  or the
detection of oil spills in satellite radar images  <cit> , just to name a few examples.
unbalanced data may arise
whenever the class memberships are observed after data collection.
like many other classification methods rf produces classification rules that do not
accurately predict the minority class if data are unbalanced.
the rf classifier
allocates new observations more often to the majority class unless the difference
between the classes is large and classes are well separable.
for extreme class
imbalances, e.g.
if the minority class includes only 5% of the observations, it
might happen that the rf classifier allocates every observation to the majority
class independently of the predictors, yielding a minimal error rate of 5%.
although
this error rate of 5% is very small, such a trivial classification is of no
practical use.
some suggestions have been made to yield a useful classification based either on
sampling procedures  <cit>  or on cost
sensitivity analyses  <cit> .
sampling
procedures create an artificial balance between two or more classes by oversampling
the minority class and/or downsampling the majority class.
cost sensitivity analyses
attribute a higher cost to the misclassification of an observation from the minority
class to impede the trivial systematic classification to the larger class.
both
aspects have been widely discussed in the literature with respect to rf’s
classification performance  <cit> .
recent simulation studies
<cit>  have shown that the performance
of rf classification for unbalanced data depends on  the imbalance ratio,
the class overlap and  the sample size.
the impact of class imbalance on the rf vim, however, has to our knowledge not yet
been examined in the literature.
in this article we focus on the permutation vim
which is known to be almost unbiased and more reliable than the gini vim.
the latter
has been shown to have a preference for certain types of predictors  <cit>  and therefore its rankings have to be treated
with caution.
we concentrate on the class imbalance problem for two response classes
with respect to the permutation vim.
we investigate the mechanisms of changes in
performance for unbalanced data settings and motivate the use of a new permutation
vim which is not based on the error rate but on the area under the curve .
the
auc can be seen as an accuracy measure putting the same weight on both classes
– in contrast to the error rate which essentially gives more weight to the
majority class.
as such, the auc is a particularly appropriate prediction accuracy
measure in unbalanced data settings  <cit> .
a
permutation vim in which the error rate is replaced by the auc is therefore a
promising alternative to the standard permutation vim.
we performed extensive
simulation studies to explore and compare the behaviour of both permutation vims for
different class imbalance levels, effect sizes and sample sizes.
methods
the rf algorithm is a classification and regression method often used for
high-dimensional data settings where the number of predictors exceeds the number of
observations.
note that throughout this article we use the term predictors which is
equivalent to features or descriptors denoting variables that are used to
discriminate the response classes.
in the rf algorithm several individual decision
trees are combined to make a final prediction.
the final prediction is then the
average  or the majority vote  of the
predictions of all trees in the forest.
each tree is fitted to a random sample of
observations  from the original sample.
observations
not used to construct a tree are termed out-of-bag  observations for that tree.
for each split in each tree a randomly drawn subset of predictors is assessed as
candidates for splitting and the predictor yielding the best split is finally chosen
for the split.
in the original version of rf developed by leo breiman  <cit> , the selected split is the split with the
largest decrease in gini impurity.
in a later version of rf, conditional inference
tests are used for selecting the best split in an unbiased way  <cit> .
for each split in a tree, each candidate
predictor from the randomly drawn subset is globally tested for its association with
the response, yielding a global p-value.
the predictor with the smallest p-value is
selected, and within this globally selected predictor the best split is finally
chosen for the split.
both forest versions implement so called variable importance measures which can be
used to get a ranking of the predictors according to their association with the
response.
in the following, we briefly introduce the standard permutation vim as
well as our novel permutation vim, which is based on the area under the curve.
random forest variable importance measures
rf’s variable importance measures are often used for feature selection for
high-dimensional data settings which makes it especially attractive for
bioinformatics and related fields, where identifying a subset of relevant
predictors from a large set of candidate predictors is a major challenge .
the two standard vims for feature
selection with rf are the gini vim and the permutation vim.
roughly speaking the
gini vim of a predictor of interest is the sum over the forest of the decreases
of gini impurity generated by this predictor whenever it was selected for
splitting, scaled by the number of trees.
this measure has been shown to prefer
certain types of predictors  <cit> .
the resulting predictor ranking should therefore be treated with caution.
that
is why in this paper we focus on the permutation vim that gives essentially
unbiased error rate rankings of the predictors.
error-rate-based permutation vim
from now on, we denote the standard permutation vim as “error-rate-based
permutation vim”, since it is based on the oob error rate, as outlined
below.
more precisely, it measures the difference between the oob error rate
after and before permuting the values of the predictor of interest.
the
error-rate-based permutation variable importance  for predictor j is defined
by:
vijer=1ntree∑t=1ntreeertj˜−ertj
where
•ntree denotes the number of trees in the forest,
•ertj denotes the mean error rate over all oob
observations in tree t before permuting predictor j,
•ertj denotes the mean error rate over all oob
observations in tree t after randomly permuting predictor j.
the idea underlying this vim is the following: if the predictor is not associated
with the response, the permutation of its values has no influence on the
classification, and thus also no influence on the error rate.
the error rate of
the forest is not substantially affected by the permutation and the vi of the
predictor takes a value close to zero, indicating no association between the
predictor and the response.
in contrast, if response and predictor are
associated, the permutation of the predictor values destroys this association.
“knocking out” this predictor by permuting its values results in a
worse classification leading to an increased error rate.
the difference in error
rates before and after randomly permuting the predictor thus takes a positive
value reflecting the high importance of this predictor.
a novel auc-based permutation vim
our new auc-based permutation vim is closely related to the error-rate-based
permutation vim.
they only differ with respect to the prediction accuracy
measure: in a nutshell, the error rate of a tree involved in  is replaced by
the area under the curve   <cit> .
we
define the auc-based permutation vi for predictor j as:
vijauc=1ntree*∑t=1ntree∗auctj-auctj˜
•ntree∗ denotes the number of trees in the
forest whose oob observations include observations from both classes,
•auctj denotes the area under the curve computed from
the oob observations in tree t before permuting predictor j,
•auctj denotes the area under the curve computed from
the oob observations in tree t after randomly permuting predictor j.
instead of computing the error rate for each tree after and before permuting a
predictor, the auc is computed.
the auc for a tree is based on the so-called
class probabilities, i.e.
the estimated probability of each observation to
belong to the class y =  <dig> or y =  <dig>  respectively.
the class probabilities of an
observation are determined by the relative amount of training observations
belonging to the corresponding class in the terminal node in which an
observation falls into.
if one considers an oob observation with y =  <dig> and an
oob observation with y =  <dig>  a “good tree” is expected to assign a
larger class probability for class y =  <dig> to the observation truly belonging to
class y =  <dig> than to the observation belonging to class y =  <dig>  the auc for a tree
corresponds to the proportion of pairs for which this is the case.
it can be
seen as an estimator of the probability that a randomly chosen observation from
class y =  <dig> receives a higher class probability for class y =  <dig> than a randomly
chosen observation from class y =  <dig>  note that with the use of the auc, the
information contained in the class probabilities returned by a tree are
adequately exploited.
this is not the case for the error rate, that requires a
dichotomization of class probabilities.
from a practical point of view, the auc
is computed by making use of its equivalence with the mann–whitney-u
statistic.
the mann–whitney-u statistic is solely based on the rankings of
two independent samples.
auc values of  <dig> correspond to a perfect tree
classifier, since a perfect classifier would attribute each observation from one
class a higher probability to belong to this class than any observation from the
other class.
auc values of  <dig>  correspond to a useless tree classifier that
randomly allocates class probabilities to the observations.
in this case in
about half the cases a randomly drawn observation from one class receives a
higher probability of belonging to that class than a randomly drawn observation
from the other class.
the novel auc-based permutation vim is implemented in the package party for the
unbiased rf variant based on conditional inference trees.
note that the
discrepancy in performance between the standard permutation vim and the
auc-based permutation vim is transferable to the original version of rf since
the vi ranking mechanism is completely independent from the construction of the
trees.
comparison studies
the behavior of the two introduced permutation vims is expected to be different
in the presence of unbalanced data.
the auc is a prediction accuracy measure
which puts the same weight on both classes independently of their sizes
<cit> .
the error rate, in
contrast, gives essentially more weight to the majority class because it does
not take class affiliations into account and regards all misclassifications
equally important.
in the results section we try to explain the consequences for
the performance of the permutation vims for unbalanced data settings and provide
evidence for our supposition.
we performed studies on simulated and on real data
to explore and contrast the performance of both permutation vims.
using
simulated data we aim to see whether total sample size and effect size play a
role for the class imbalance problem.
we explored this by varying the total
number of observations and by simulating predictors with different effect sizes.
furthermore we conducted analyses based on real data to provide additional
evidence based on realistic data structures which usually incorporate complex
interdependencies.
our comparison studies on simulated and on real data were
conducted using the unbiased rf variant based on conditional inference trees.
the implementation of this unbiased rf variant is available in the r system for
statistical computing via the package party  <cit> .
simulated data
the considered simulation design represents a scenario where the predictors
associated with the response variable y  are to be identified from a set
of continuous predictors.
we performed simulations for varying imbalance levels:
50% corresponding to a completely balanced sample, 40%, 30%, 20%, 10%, 5% and 1%
corresponding to different imbalance levels from slight to very extreme class
imbalances.
the simulation setting comprises both predictors not associated with
the response and associated predictors with three different levels of effect
sizes.
table  <dig> presents the data setting used
throughout this simulation.
the first five predictors x <dig>  .
.
., x <dig> differ strongly
between classes with mean μ <dig> =  <dig> in one class and mean
μ <dig> =  <dig> in the other class.
the predictors x <dig>  .
.
., x <dig> have a moderate mean difference between the two classes with
μ <dig> =  <dig>  and μ <dig> =  <dig>  for x <dig>  .
.
., x <dig> there is only a small difference between the classes with
μ <dig> =  <dig>  and μ <dig> =  <dig>  we simulated 50
additional predictors following a standard normal distribution with no
association to the response variable .
we performed analyses with varying sample sizes and report the results for total
sample sizes of n =  <dig>  n =  <dig> and n =  <dig>  for each parameter combination,
i.e.
imbalance level and sample size, we simulated  <dig> datasets and computed
auc-based and error-rate-based permutation vis for each dataset.
note that for a
sample size of n =  <dig> an imbalance of 1% is not meaningful since there is only
one observation in the minority class.
forest and tree parameters were held fixed.
the parameter ntree denoting the
number of trees in a forest was set to  <dig>  the parameter for the number of
candidate splits mtry was set to the default value of  <dig>  we used subsampling
instead of bootstrap sampling for constructing the trees, i.e.
setting the
parameter replace to false  <cit> .
conditional inference trees were grown to maximal possible depth, i.e.
setting
the parameters minsplit, minbucket and mincriterion in the cforest function to
zero.
real data
we also investigated the performance of the error-rate-based and the auc-based
permutation vim on real data including complex dependencies
and predictors of different scales.
the dataset is about rna editing in land
plants  <cit> .
rna editing is the
modification of the rna sequence from the corresponding dna template.
it occurs
e.g.
in plant mitochondria where some cytidines are converted to uridines before
translation .
the dataset
comprises a total of  <dig> predictors:  <dig> categorical predictors  and two continuous predictors .
it includes
<dig> observations, where exactly one half has an edited site and the other half
has a non-edited site.
the data are publicly available from the journal’s
homepage.
after excluding observations with missing values, a total of 2613
observations were left, where  <dig> had a non-edited site and  <dig> observations
had an edited site.
we used this balanced dataset to explore the performance of
er- and auc-based permutation vim for varying class imbalances – but now
with realistic dependencies and predictors of different scales.
for this
purpose, we artificially created different imbalance levels by drawing random
subsets from the class with edited sites.
application of the standard permutation vim to the data using the 2613
observations without missing values gave vis greater than zero for all 43
predictors for different random seeds , indicating that all predictors seem to have at least a
small predictive power .
we generated and added additional
predictors without any effect  in
order to evaluate the performance of error-rate-based and auc-based permutation
vims.
provided that there is a higher association between the response and any
of the original predictors than between the response and any of the simulated
noise predictors, a well performing vim would attribute a higher vi to original
predictors than to simulated noise predictors.
the noise predictors were
generated by randomly permuting the values of the original predictors.
each
original predictor was permuted once, resulting in a total of  <dig> noise
predictors.
the whole process consisting of  creating  <dig> noise predictors,
merging them to the original dataset,  randomly subsampling to create an
unbalanced dataset and  computing the error-rate-based and auc-based
permutation vis, was repeated  <dig> times for each imbalance level to get stable
results for the vim performance.
to check the assumption that there is a higher
association between the response and any of the original predictors than between
the response and any of the simulated predictors, we computed the mean vi over
<dig> completely balanced datasets that had been extended by noise predictors.
figure  <dig> shows that all mean vis of the original
predictors are higher than any mean vi of a simulated noise predictor and hence
confirms our first impression.
the balanced modified c-to-u conversion dataset.
mean vis
were obtained by averaging the vis  over  <dig> extended versions of the c-to-u conversion
dataset.
performance evaluation criteria
vims give a ranking of the predictors according to their association with the
response.
to evaluate the quality of the rankings by the permutation vims the
auc was used as performance measure.
the auc was computed to assess the ability
of a vim to differentiate between associated predictors and predictors not
associated with the response.
auc values of  <dig> mean that each associated
predictor receives a higher vi than any noise predictor, thus indicating a
perfect discrimination.
auc values of  <dig>  mean that a randomly drawn associated
predictor receives a higher vi than a randomly drawn noise predictor in only
half of the cases, indicating no discriminative ability.
for our comparison studies we defined the two classes which are to be
differentiated by a vim in the following way.
in the first instance of our
studies on simulated data, all predictors which are associated with the response
formed one class and noise predictors built the other class.
in more detailed
subsequent analyses we then explored the ability of the vims to discriminate
between predictors with the same effect size and predictors without an effect.
for this analysis one class comprised the noise predictors while the other class
comprised only predictors with the same effect.
for the studies on real data it
was not possible to conduct such detailed analyses because the true ordering of
the predictors according to their association with the response is not known.
hence in the analysis on real data we restricted our analysis to the
discrimination between original predictors forming one class and simulated noise
predictors forming the other class.
RESULTS
why may the error-rate-based permutation vim fail in case of class
imbalance?
the prioritisation of the majority class in unbalanced data settings is well
known in the context of rf classification and can easily be seen from trees
constructed on unbalanced data.
trees trained on unbalanced data more often
predict the majority class, which leads to the minimization of the overall error
rate.
but how does this affect the performance of the permutation vims?
and why
is the auc-based permutation vim expected to be more robust towards class
imbalance than the commonly used error-rate-based permutation vim?
to answer these questions we consider an extremely unbalanced data setting and
illustrate what happens in a tree when permuting the values of an associated
predictor.
we will first have a look at observations from the majority class.
for this class nearly all observations are correctly classified by a tree which
has been trained on extremely unbalanced data.
if we now permute the values of
an associated predictor, this does generally not result in a classification into
the minority class since a classification into the minority class is an unlikely
event – even for an observation from this class.
a very specific data
pattern is required for an observation to be classified into the minority class.
it is unlikely that a random permutation of an associated predictor results in
such a specific data pattern just by chance.
thus, for the majority class we
expect hardly any observation to be incorrectly classified to the minority class
after the permutation of an associated predictor.
thus the error rate does not
considerably increase after the permutation of an associated predictor, finally
leading to a rather low contribution to the vi.
now let us consider the classifications by a tree for observations from the
minority class.
for an extreme class imbalance most of the observations from the
minority class are falsely classified to the majority class due to the above
described focus on the majority class.
it might be the case that some
observations from the minority class are correctly classified by the tree
because these observations have that specific pattern of predictor values which
is required for an observation to be classified into the minority class.
it is
likely that a permutation of the values of an associated predictor might then
destroy that specific pattern so that after the permutation, these observations
are not identified anymore to be in the minority class.
thus a misclassification
due to the elimination of an associated predictor is much more likely to appear
in observations from the minority class than in observations from the majority
class.
note that only a small number of observations from the minority class are
affected since most of the observations from the minority class are classified
into the majority class anyway .
the
change in error rates is thus expected to be rather small – albeit it is
more pronounced than the change in error rates in the majority class.
note that the error-rate-based permutation vim does not take class affiliations
into account.
thus the change in error rates is actually not computed separately
for each class.
yet, in order to better understand the behavior of the vim, it
may help to point out that if the class proportions were the same in all oob
samples, the vi of a predictor could be directly derived as the weighted average
of the class specific differences in the error rates.
the weights would
correspond to the proportion of observations from the respective class.
in
practice the class frequencies will not be equal in all oob samples, but the
concept of a weighted average of the class specific error rates illustrates the
fact that for unbalanced data settings the vi is mainly driven by the change in
error rates derived from observations from the majority class.
since the change
in error rates in the majority class is expected to be much smaller compared to
the change in error rates in the minority class, the computed vis are rather
low.
this results in low vis even for associated predictors and in a poor
differentiation of associated predictors and predictors not associated with the
response.
class specific vis
this theory is supported by computing class specific vis .
computing class specific vis was done using the r package randomforest
implementing the standard rf algorithm.
the importance function of this package
provides permutation vis computed separately for each class .
the class specific vis for a
total sample size of n =  <dig> and an imbalance level of 5% are shown in
figure  <dig>  where predictors x <dig> to
x <dig> have an effect while the remaining  <dig> predictors do not have
an effect, corresponding to the simulation setting previously described in
table  <dig> in the context of the comparison study
.
different sample sizes and
imbalance levels give similar results .
they confirm our
argumentation that the change in the error rates computed from oob observations
from the majority class is smaller than the change in error rates computed from
oob observations from the minority class.
this results in an underestimation of
the actual permutation vi due to a much higher weighting of the majority class
in the computation of the vi .
the discrepancy between the vis
computed from observations of the minority class and vis computed from
observations of the majority class depends on the class imbalance and is more
pronounced for more extreme class imbalances.
from oob observations of the majority class  and from all
oob observations .
the first  <dig> predictors are
associated with the response while the remaining predictors are noise
predictors.
vis are shown for a total sample size of n =  <dig> and an
imbalance level of 5%.
this motivates the use of an alternative accuracy measure which better
incorporates the minority class.
while the error rate gives the same weight to
all observations, therefore focusing more on the majority class, the auc is a
measure which does not prefer one class over the other but instead puts exactly
the same weight on both classes.
therefore the auc-based permutation vim is
expected to detect changes in tree predictions for observations from the
minority class, which might not be grasped by the error-rate-based permutation
vim due to a much higher weighting of the majority class.
the vis for associated
predictors obtained by the auc-based permutation vim are thus expected to be
comparatively higher than the vis obtained by the error-rate-based permutation
vim.
this would result in a better differentiation of associated and noise
predictors by the auc-based permutation vim.
these conjectures are assessed in
the comparison study presented in the next section.
comparison study with simulated data
the performance of the error-rate-based and auc-based vims as measured by the auc
is shown in figure  <dig> for the three different total
sample sizes with n =  <dig> , n =  <dig>  and n = 1000
observations  and different class imbalance levels.
filled boxes
correspond to the auc-based permutation vim and unfilled boxes correspond to the
error-rate-based permutation vim.
figure  <dig> shows
that the performance of both vims decreases with an increasing class imbalance
for all sample sizes.
note that the decrease in performance for both vims is not
solely attributable to the imbalance ratio per se but also to the reduced number
of observations in the minority class with an increasing class imbalance.
this
is induced by the simulation setting since we held the total number of
observations fixed and varied the number of observations in both classes to
create different class imbalances.
if there are only few observations in one
class then the tree predictions are less accurate.
however the performance of
the auc-based permutation vim decreases less dramatically than the performance
of the error-rate-based permutation vim.
the discrepancy in performances between
the vims increases with increasing imbalance level and is maximal for the most
extreme class imbalance.
while for a sample size of n =  <dig> the error-rate-based
permutation vim is no longer able to discriminate between associated and noise
predictors  for the most extreme class
imbalance of 1%, the auc-based permutation vim still is, showing that it can be
used to identify associated predictors even if the minority class comprises only
few observations.
it can be ruled out that the better performance of the
auc-based permutation vim is due to chance since the distributions of auc values
significantly differ.
furthermore this difference in performances between both
vims becomes even larger for larger sample sizes.
and error-rate-based  permutation vims for
different class imbalances.
the auc is used to assess the
ability of a vim to discriminate between predictors with an effect and
predictors without an effect.
distributions are shown for total sample
sizes of n =  <dig> , n =  <dig>  and n = 1000
.
in a nutshell, in this first simulation the auc-based permutation vim performed
better in case of class imbalance.
the following subsections focus on the
influence of sample size and effect size on the respective performance of both
permutation vims in unbalanced data settings.
influence of sample size
in figure  <dig>  the performance of both vims improves
with an increased total sample size for a fixed imbalance level since an
increase in the sample size results in more accurate tree predictions.
the right
panel of figure  <dig> shows that both permutation vims
are hardly affected by class imbalances up to 10% when the sample size is rather
large .
if the sample size is smaller , however, the
performance of the vims is considerably decreased for a 10% imbalance level.
a
decrease in performance for a 10% imbalance level is also observed for a sample
size of n =  <dig>  especially for error-rate-based permutation vim.
in a nutshell,
class imbalance seems to be more problematic for the permutation vims if the
total sample size is small.
influence of effect size
we now explore the ability of the permutation vims to identify predictors with
different effect sizes in presence of unbalanced data.
the auc was again used as
an evaluation criterion to compare the ability of the auc-based and
error-rate-based permutation vims to discriminate between associated and
non-associated predictors.
here the evaluation was done for each effect size
separately meaning that one class comprised all the noise predictors while the
other class comprised only predictors with the considered effect size .
figure  <dig> shows the
results for the setting with n =  <dig>  the results for other sample sizes are
shown in additional file  <dig>  the left panel of
figure  <dig> shows the performance of both
permutation vims according to their ability to discriminate between predictors
with weak effects and predictors without an effect.
the middle panel corresponds
to the auc values for predictors with a moderate effect versus noise predictors
and the right panel corresponds to the auc values for predictors with a strong
effect versus noise predictors.
and error-rate-based  permutation vims for
different class imbalances.
the auc is used to assess the
ability of a vim to discriminate between noise predictors and predictors
with a weak , moderate  and strong  effect.
distributions are shown for a total sample size of n =
<dig>
unsurprisingly, for both permutation vims predictors having only a weak effect
are less discriminable from noise predictors than predictors with stronger
effects.
for imbalances up to 20% both vims identify nearly all predictors with
a strong effect.
obviously there are unbalanced data settings where the standard
permutation vim still perfectly separates between noise predictors and
predictors with pronounced effects.
we conclude that class imbalance is more
problematic if predictors with weak effects are to be identified while it plays
a minor role if the classes are well separable.
comparison study with real data
figure  <dig> shows the distribution of auc values for 100
modified c-to-u conversion datasets for varying imbalance levels.
for the
balanced dataset and for slight class imbalances up to 40% both vims have a
perfect discriminative ability since all associated predictors receive a higher
vi than any noise predictor.
overall the performance of both vims decreases with
an increasing class imbalance.
note that the decreasing performance for
increasing class imbalances might be partly attributable to the reduced total
sample size as the class imbalance was created by randomly subsampling
observations from the class with the edited sites.
when comparing both vims the
auc-based permutation vim significantly outperformed the standard permutation
vim.
for an imbalance of 30% the auc-based permutation vim clearly identified
more associated predictors than the error-rate-based permutation vim.
the
superiority of the auc-based permutation vim over the standard permutation vim
increased with an increasing class imbalance.
for imbalances between 15% and 5%
the discrepancy between the performance of auc-based and standard permutation
vim was maximal.
permutation vims for different class imbalances derived
from  <dig> modified datasets from c-to-u conversion data.
the auc
is used to assess the ability of a vim to discriminate between
associated predictors and predictors not associated with the
response.
overall, this study on real data impressively shows that the auc-based
permutation vim also works for complex real data and outperforms the standard
permutation vim in almost all class imbalance settings.
CONCLUSIONS
the problem of unbalanced data has been widely discussed in the literature for
diverse classifiers including random forests.
many approaches have been developed to
improve the predictive ability of rf classifiers for unbalanced data settings.
however less attention has been paid to the behaviour of random forests’
variable importance measures for unbalanced data.
in this paper we explored the
performance of the permutation vim for different class imbalances and proposed an
alternative permutation vim which is based on the auc.
our studies on simulated as well as on real data show that the commonly used
error-rate-based permutation vim loses its ability to discriminate between
associated predictors and predictors not associated with the response for increasing
class imbalances.
this is particularly crucial for small sample sizes and if
predictors with weak effects are to be detected.
the decreasing performance of the
standard permutation vim results from two sources: the class imbalance on the
training data level leading to trees more often predicting the majority class and
the class imbalance at the oob data level leading to blurred vis due to a much
higher weighting of error rate differences in the majority class.
a higher weighting
of the majority class in the vi calculation is problematic because the difference in
error rates is shown to be less pronounced in the majority class than in the
minority class.
note that in some cases it might be interesting to assess the
increase in error rate obtained when a certain predictor is removed.
in this case
the error-rate-based permutation vim can be considered.
if the goal is to rank the
predictors according to their discrimination power, however, the auc-based
permutation vim should be preferred.
the problem of imbalance at the oob data level is directly addressed with the use of
a novel auc-based permutation vim.
this vim puts the same weight on both classes by
measuring the difference in aucs instead of the difference in error rates.
it is
thus able to detect changes in tree predictions when permuting associated predictors
which might not be grasped by the standard permutation vim.
in contrast, the
imbalance on training data level is not addressed by the auc-based permutation vim,
meaning that the structure of a tree remains untouched.
on the one hand this is a
drawback since class predictions before and after permuting a predictor are similar
even if the respective predictor is associated with the response, resulting in a
reduced change in the aucs.
on the other hand preserving the tree structure can be
regarded as an advantage since a change in tree structure might open space for new
unexpected behaviours.
it is a major advantage of our novel auc-based permutation
vim that it is based on exactly the same principle and differs from the standard
permutation vim only with respect to the accuracy measurement.
it is thus expected
to share the advantages of the standard permutation vim and its properties and
behaviours discovered in recent years .
our studies on simulated as well as on real data show that the auc-based permutation
vim outperforms the commonly used error-rate-based permutation vim as well as the
error-rate-based permutation vim computed only using observations from the minority
class in case of unbalanced data settings .
the difference in
performance between our novel auc-based permutation vim and the standard permutation
vim can be substantial, especially for extremely unbalanced data settings.
but even
for slight class imbalances the auc-based permutation vim has shown to be superior
to the standard permutation vim.
we conclude from our studies that the auc-based
permutation vim should be preferred to the standard permutation vim whenever two
response classes have different class sizes and the aim is to identify relevant
predictors.
availability and requirements
the auc-based permutation vim is implemented in the new version of the party
package for the freely-available statistical software r
.
it can
be applied via the function varimpauc.
all codes implementing our studies on simulated and on real data are available
under
http://www.ibe.med.uni-muenchen.de/organisation/mitarbeiter/070_drittmittel/janitza/index.html
for reproducibility purposes.
abbreviations
auc: area under curve; oob: out-of-bag; rf: random forest; vim: variable importance
measure; vi: variable importance.
competing interests
the authors declare that they have no competing interests.
authors’ contributions
sj wrote the paper and conducted all analyses.
sj and alb developed and implemented
the new vim.
all authors contributed to the design of the analyses and substantially
edited the manuscript.
supplementary material
additional file 1
this file shows the results of the performance comparison between the
auc-based permutation vim and the error-rate-based permutation vim
computed using only observations from the minority class.
click here for file
additional file 2:
this file shows the distribution of auc-values  for sample sizes n =
<dig> and n =  <dig>
click here for file
acknowledgements
sj was supported by the german science foundation .
the authors thank torsten hothorn for integrating the
implementation of the auc-based permutation vim into the new version of the
party package.

 in bioinformatics and related fields, such as statistical genomics and genetic epidemiology, data are often highly correlated, heterogeneous and high-dimensional, with the number of predictors, also known as features or descriptors, exceeding the number of observations. the random forest approach developed by leo breiman in is particularly appropriate to handle such complex data. in bioinformatics, rf is a commonly used tool for classification or regression purposes as well as for ranking candidate predictors through its inbuilt variable importance measures. it has been used in many applications involving high-dimensional data. as a nonparametric method rf can deal with nonlinearity, interactions, correlated predictors and heterogeneity, which makes it attractive in genetic epidemiology. however in the context of classification, i.e. when the response to be predicted is a class membership, classification performance of rf has been shown to be suboptimal in case of strongly unbalanced data, i. e. when class sizes differ considerably. in epidemiology, unbalanced data are observed, e.g., in population-based studies where only a small number of subjects develop a certain disease over time, while most subjects remain healthy. unbalanced data are also common in screening studies, where most of the screened persons are negative, as well as in subclass analyses, e.g., if one wants to differentiate between different subtypes of cancer. usually some subclasses are more common than other subclasses leading to an imbalance in class sizes. studies on rare diseases are a further example of unbalanced data settings in medicine. data can be obtained only from few persons having the specific rare disease, while samples from healthy control persons are much easier to obtain. of course unbalanced data are also relevant in various other areas of application beyond the biomedical field, e.g., the prediction of creditworthiness of a bank’s costumers, the detection of fraudulent telephone calls or the detection of oil spills in satellite radar images, just to name a few examples. unbalanced data may arise whenever the class memberships are observed after data collection. like many other classification methods rf produces classification rules that do not accurately predict the minority class if data are unbalanced. the rf classifier allocates new observations more often to the majority class unless the difference between the classes is large and classes are well separable. for extreme class imbalances, e.g. if the minority class includes only 5% of the observations, it might happen that the rf classifier allocates every observation to the majority class independently of the predictors, yielding a minimal error rate of 5%. although this error rate of 5% is very small, such a trivial classification is of no practical use. some suggestions have been made to yield a useful classification based either on sampling procedures or on cost sensitivity analyses. sampling procedures create an artificial balance between two or more classes by oversampling the minority class and/or downsampling the majority class. cost sensitivity analyses attribute a higher cost to the misclassification of an observation from the minority class to impede the trivial systematic classification to the larger class. both aspects have been widely discussed in the literature with respect to rf’s classification performance. recent simulation studies have shown that the performance of rf classification for unbalanced data depends on the imbalance ratio, the class overlap and the sample size. the impact of class imbalance on the rf vim, however, has to our knowledge not yet been examined in the literature. in this article we focus on the permutation vim which is known to be almost unbiased and more reliable than the gini vim. the latter has been shown to have a preference for certain types of predictors and therefore its rankings have to be treated with caution. we concentrate on the class imbalance problem for two response classes with respect to the permutation vim. we investigate the mechanisms of changes in performance for unbalanced data settings and motivate the use of a new permutation vim which is not based on the error rate but on the area under the curve. the auc can be seen as an accuracy measure putting the same weight on both classes – in contrast to the error rate which essentially gives more weight to the majority class. as such, the auc is a particularly appropriate prediction accuracy measure in unbalanced data settings. a permutation vim in which the error rate is replaced by the auc is therefore a promising alternative to the standard permutation vim. we performed extensive simulation studies to explore and compare the behaviour of both permutation vims for different class imbalance levels, effect sizes and sample sizes. methods the rf algorithm is a classification and regression method often used for high-dimensional data settings where the number of predictors exceeds the number of observations. note that throughout this article we use the term predictors which is equivalent to features or descriptors denoting variables that are used to discriminate the response classes. in the rf algorithm several individual decision trees are combined to make a final prediction. the final prediction is then the average or the majority vote of the predictions of all trees in the forest. each tree is fitted to a random sample of observations from the original sample. observations not used to construct a tree are termed out-of-bag observations for that tree. for each split in each tree a randomly drawn subset of predictors is assessed as candidates for splitting and the predictor yielding the best split is finally chosen for the split. in the original version of rf developed by leo breiman, the selected split is the split with the largest decrease in gini impurity. in a later version of rf, conditional inference tests are used for selecting the best split in an unbiased way. for each split in a tree, each candidate predictor from the randomly drawn subset is globally tested for its association with the response, yielding a global p-value. the predictor with the smallest p-value is selected, and within this globally selected predictor the best split is finally chosen for the split. both forest versions implement so called variable importance measures which can be used to get a ranking of the predictors according to their association with the response. in the following, we briefly introduce the standard permutation vim as well as our novel permutation vim, which is based on the area under the curve. random forest variable importance measures rf’s variable importance measures are often used for feature selection for high-dimensional data settings which makes it especially attractive for bioinformatics and related fields, where identifying a subset of relevant predictors from a large set of candidate predictors is a major challenge. the two standard vims for feature selection with rf are the gini vim and the permutation vim. roughly speaking the gini vim of a predictor of interest is the sum over the forest of the decreases of gini impurity generated by this predictor whenever it was selected for splitting, scaled by the number of trees. this measure has been shown to prefer certain types of predictors. the resulting predictor ranking should therefore be treated with caution. that is why in this paper we focus on the permutation vim that gives essentially unbiased error rate rankings of the predictors. error-rate-based permutation vim from now on, we denote the standard permutation vim as “error-rate-based permutation vim”, since it is based on the oob error rate, as outlined below. more precisely, it measures the difference between the oob error rate after and before permuting the values of the predictor of interest. the error-rate-based permutation variable importance for predictor j is defined by: vijer=1ntree∑t=1ntreeertj˜−ertj where •ntree denotes the number of trees in the forest, •ertj denotes the mean error rate over all oob observations in tree t before permuting predictor j, •ertj denotes the mean error rate over all oob observations in tree t after randomly permuting predictor j. the idea underlying this vim is the following: if the predictor is not associated with the response, the permutation of its values has no influence on the classification, and thus also no influence on the error rate. the error rate of the forest is not substantially affected by the permutation and the vi of the predictor takes a value close to zero, indicating no association between the predictor and the response. in contrast, if response and predictor are associated, the permutation of the predictor values destroys this association. “knocking out” this predictor by permuting its values results in a worse classification leading to an increased error rate. the difference in error rates before and after randomly permuting the predictor thus takes a positive value reflecting the high importance of this predictor. a novel auc-based permutation vim our new auc-based permutation vim is closely related to the error-rate-based permutation vim. they only differ with respect to the prediction accuracy measure: in a nutshell, the error rate of a tree involved in is replaced by the area under the curve. we define the auc-based permutation vi for predictor j as: vijauc=1ntree*∑t=1ntree∗auctj-auctj˜ •ntree∗ denotes the number of trees in the forest whose oob observations include observations from both classes, •auctj denotes the area under the curve computed from the oob observations in tree t before permuting predictor j, •auctj denotes the area under the curve computed from the oob observations in tree t after randomly permuting predictor j. instead of computing the error rate for each tree after and before permuting a predictor, the auc is computed. the auc for a tree is based on the so-called class probabilities, i.e. the estimated probability of each observation to belong to the class y = or y = respectively. the class probabilities of an observation are determined by the relative amount of training observations belonging to the corresponding class in the terminal node in which an observation falls into. if one considers an oob observation with y = and an oob observation with y = a “good tree” is expected to assign a larger class probability for class y = to the observation truly belonging to class y = than to the observation belonging to class y = the auc for a tree corresponds to the proportion of pairs for which this is the case. it can be seen as an estimator of the probability that a randomly chosen observation from class y = receives a higher class probability for class y = than a randomly chosen observation from class y = note that with the use of the auc, the information contained in the class probabilities returned by a tree are adequately exploited. this is not the case for the error rate, that requires a dichotomization of class probabilities. from a practical point of view, the auc is computed by making use of its equivalence with the mann–whitney-u statistic. the mann–whitney-u statistic is solely based on the rankings of two independent samples. auc values of correspond to a perfect tree classifier, since a perfect classifier would attribute each observation from one class a higher probability to belong to this class than any observation from the other class. auc values of correspond to a useless tree classifier that randomly allocates class probabilities to the observations. in this case in about half the cases a randomly drawn observation from one class receives a higher probability of belonging to that class than a randomly drawn observation from the other class. the novel auc-based permutation vim is implemented in the package party for the unbiased rf variant based on conditional inference trees. note that the discrepancy in performance between the standard permutation vim and the auc-based permutation vim is transferable to the original version of rf since the vi ranking mechanism is completely independent from the construction of the trees. comparison studies the behavior of the two introduced permutation vims is expected to be different in the presence of unbalanced data. the auc is a prediction accuracy measure which puts the same weight on both classes independently of their sizes. the error rate, in contrast, gives essentially more weight to the majority class because it does not take class affiliations into account and regards all misclassifications equally important. in the results section we try to explain the consequences for the performance of the permutation vims for unbalanced data settings and provide evidence for our supposition. we performed studies on simulated and on real data to explore and contrast the performance of both permutation vims. using simulated data we aim to see whether total sample size and effect size play a role for the class imbalance problem. we explored this by varying the total number of observations and by simulating predictors with different effect sizes. furthermore we conducted analyses based on real data to provide additional evidence based on realistic data structures which usually incorporate complex interdependencies. our comparison studies on simulated and on real data were conducted using the unbiased rf variant based on conditional inference trees. the implementation of this unbiased rf variant is available in the r system for statistical computing via the package party. simulated data the considered simulation design represents a scenario where the predictors associated with the response variable y are to be identified from a set of continuous predictors. we performed simulations for varying imbalance levels: 50% corresponding to a completely balanced sample, 40%, 30%, 20%, 10%, 5% and 1% corresponding to different imbalance levels from slight to very extreme class imbalances. the simulation setting comprises both predictors not associated with the response and associated predictors with three different levels of effect sizes. table  presents the data setting used throughout this simulation. the first five predictors x..., x differ strongly between classes with mean μ = in one class and mean μ = in the other class. the predictors x..., x have a moderate mean difference between the two classes with μ = and μ = for x..., x there is only a small difference between the classes with μ = and μ = we simulated 50 additional predictors following a standard normal distribution with no association to the response variable. we performed analyses with varying sample sizes and report the results for total sample sizes of n = n = and n = for each parameter combination, i.e. imbalance level and sample size, we simulated datasets and computed auc-based and error-rate-based permutation vis for each dataset. note that for a sample size of n = an imbalance of 1% is not meaningful since there is only one observation in the minority class. forest and tree parameters were held fixed. the parameter ntree denoting the number of trees in a forest was set to the parameter for the number of candidate splits mtry was set to the default value of we used subsampling instead of bootstrap sampling for constructing the trees, i.e. setting the parameter replace to false. conditional inference trees were grown to maximal possible depth, i.e. setting the parameters minsplit, minbucket and mincriterion in the cforest function to zero. real data we also investigated the performance of the error-rate-based and the auc-based permutation vim on real data including complex dependencies and predictors of different scales. the dataset is about rna editing in land plants. rna editing is the modification of the rna sequence from the corresponding dna template. it occurs e.g. in plant mitochondria where some cytidines are converted to uridines before translation. the dataset comprises a total of predictors: categorical predictors and two continuous predictors. it includes observations, where exactly one half has an edited site and the other half has a non-edited site. the data are publicly available from the journal’s homepage. after excluding observations with missing values, a total of 2613 observations were left, where had a non-edited site and observations had an edited site. we used this balanced dataset to explore the performance of er- and auc-based permutation vim for varying class imbalances – but now with realistic dependencies and predictors of different scales. for this purpose, we artificially created different imbalance levels by drawing random subsets from the class with edited sites. application of the standard permutation vim to the data using the 2613 observations without missing values gave vis greater than zero for all 43 predictors for different random seeds, indicating that all predictors seem to have at least a small predictive power. we generated and added additional predictors without any effect in order to evaluate the performance of error-rate-based and auc-based permutation vims. provided that there is a higher association between the response and any of the original predictors than between the response and any of the simulated noise predictors, a well performing vim would attribute a higher vi to original predictors than to simulated noise predictors. the noise predictors were generated by randomly permuting the values of the original predictors. each original predictor was permuted once, resulting in a total of noise predictors. the whole process consisting of creating noise predictors, merging them to the original dataset, randomly subsampling to create an unbalanced dataset and computing the error-rate-based and auc-based permutation vis, was repeated times for each imbalance level to get stable results for the vim performance. to check the assumption that there is a higher association between the response and any of the original predictors than between the response and any of the simulated predictors, we computed the mean vi over completely balanced datasets that had been extended by noise predictors. figure  shows that all mean vis of the original predictors are higher than any mean vi of a simulated noise predictor and hence confirms our first impression. the balanced modified c-to-u conversion dataset. mean vis were obtained by averaging the vis over extended versions of the c-to-u conversion dataset. performance evaluation criteria vims give a ranking of the predictors according to their association with the response. to evaluate the quality of the rankings by the permutation vims the auc was used as performance measure. the auc was computed to assess the ability of a vim to differentiate between associated predictors and predictors not associated with the response. auc values of mean that each associated predictor receives a higher vi than any noise predictor, thus indicating a perfect discrimination. auc values of mean that a randomly drawn associated predictor receives a higher vi than a randomly drawn noise predictor in only half of the cases, indicating no discriminative ability. for our comparison studies we defined the two classes which are to be differentiated by a vim in the following way. in the first instance of our studies on simulated data, all predictors which are associated with the response formed one class and noise predictors built the other class. in more detailed subsequent analyses we then explored the ability of the vims to discriminate between predictors with the same effect size and predictors without an effect. for this analysis one class comprised the noise predictors while the other class comprised only predictors with the same effect. for the studies on real data it was not possible to conduct such detailed analyses because the true ordering of the predictors according to their association with the response is not known. hence in the analysis on real data we restricted our analysis to the discrimination between original predictors forming one class and simulated noise predictors forming the other class.  why may the error-rate-based permutation vim fail in case of class imbalance? the prioritisation of the majority class in unbalanced data settings is well known in the context of rf classification and can easily be seen from trees constructed on unbalanced data. trees trained on unbalanced data more often predict the majority class, which leads to the minimization of the overall error rate. but how does this affect the performance of the permutation vims? and why is the auc-based permutation vim expected to be more robust towards class imbalance than the commonly used error-rate-based permutation vim? to answer these questions we consider an extremely unbalanced data setting and illustrate what happens in a tree when permuting the values of an associated predictor. we will first have a look at observations from the majority class. for this class nearly all observations are correctly classified by a tree which has been trained on extremely unbalanced data. if we now permute the values of an associated predictor, this does generally not result in a classification into the minority class since a classification into the minority class is an unlikely event – even for an observation from this class. a very specific data pattern is required for an observation to be classified into the minority class. it is unlikely that a random permutation of an associated predictor results in such a specific data pattern just by chance. thus, for the majority class we expect hardly any observation to be incorrectly classified to the minority class after the permutation of an associated predictor. thus the error rate does not considerably increase after the permutation of an associated predictor, finally leading to a rather low contribution to the vi. now let us consider the classifications by a tree for observations from the minority class. for an extreme class imbalance most of the observations from the minority class are falsely classified to the majority class due to the above described focus on the majority class. it might be the case that some observations from the minority class are correctly classified by the tree because these observations have that specific pattern of predictor values which is required for an observation to be classified into the minority class. it is likely that a permutation of the values of an associated predictor might then destroy that specific pattern so that after the permutation, these observations are not identified anymore to be in the minority class. thus a misclassification due to the elimination of an associated predictor is much more likely to appear in observations from the minority class than in observations from the majority class. note that only a small number of observations from the minority class are affected since most of the observations from the minority class are classified into the majority class anyway. the change in error rates is thus expected to be rather small – albeit it is more pronounced than the change in error rates in the majority class. note that the error-rate-based permutation vim does not take class affiliations into account. thus the change in error rates is actually not computed separately for each class. yet, in order to better understand the behavior of the vim, it may help to point out that if the class proportions were the same in all oob samples, the vi of a predictor could be directly derived as the weighted average of the class specific differences in the error rates. the weights would correspond to the proportion of observations from the respective class. in practice the class frequencies will not be equal in all oob samples, but the concept of a weighted average of the class specific error rates illustrates the fact that for unbalanced data settings the vi is mainly driven by the change in error rates derived from observations from the majority class. since the change in error rates in the majority class is expected to be much smaller compared to the change in error rates in the minority class, the computed vis are rather low. this results in low vis even for associated predictors and in a poor differentiation of associated predictors and predictors not associated with the response. class specific vis this theory is supported by computing class specific vis. computing class specific vis was done using the r package randomforest implementing the standard rf algorithm. the importance function of this package provides permutation vis computed separately for each class. the class specific vis for a total sample size of n = and an imbalance level of 5% are shown in figure  where predictors x to x have an effect while the remaining predictors do not have an effect, corresponding to the simulation setting previously described in table  in the context of the comparison study. different sample sizes and imbalance levels give similar results. they confirm our argumentation that the change in the error rates computed from oob observations from the majority class is smaller than the change in error rates computed from oob observations from the minority class. this results in an underestimation of the actual permutation vi due to a much higher weighting of the majority class in the computation of the vi. the discrepancy between the vis computed from observations of the minority class and vis computed from observations of the majority class depends on the class imbalance and is more pronounced for more extreme class imbalances. from oob observations of the majority class and from all oob observations. the first predictors are associated with the response while the remaining predictors are noise predictors. vis are shown for a total sample size of n = and an imbalance level of 5%. this motivates the use of an alternative accuracy measure which better incorporates the minority class. while the error rate gives the same weight to all observations, therefore focusing more on the majority class, the auc is a measure which does not prefer one class over the other but instead puts exactly the same weight on both classes. therefore the auc-based permutation vim is expected to detect changes in tree predictions for observations from the minority class, which might not be grasped by the error-rate-based permutation vim due to a much higher weighting of the majority class. the vis for associated predictors obtained by the auc-based permutation vim are thus expected to be comparatively higher than the vis obtained by the error-rate-based permutation vim. this would result in a better differentiation of associated and noise predictors by the auc-based permutation vim. these conjectures are assessed in the comparison study presented in the next section. comparison study with simulated data the performance of the error-rate-based and auc-based vims as measured by the auc is shown in figure  for the three different total sample sizes with n =, n = and n = 1000 observations and different class imbalance levels. filled boxes correspond to the auc-based permutation vim and unfilled boxes correspond to the error-rate-based permutation vim. figure  shows that the performance of both vims decreases with an increasing class imbalance for all sample sizes. note that the decrease in performance for both vims is not solely attributable to the imbalance ratio per se but also to the reduced number of observations in the minority class with an increasing class imbalance. this is induced by the simulation setting since we held the total number of observations fixed and varied the number of observations in both classes to create different class imbalances. if there are only few observations in one class then the tree predictions are less accurate. however the performance of the auc-based permutation vim decreases less dramatically than the performance of the error-rate-based permutation vim. the discrepancy in performances between the vims increases with increasing imbalance level and is maximal for the most extreme class imbalance. while for a sample size of n = the error-rate-based permutation vim is no longer able to discriminate between associated and noise predictors for the most extreme class imbalance of 1%, the auc-based permutation vim still is, showing that it can be used to identify associated predictors even if the minority class comprises only few observations. it can be ruled out that the better performance of the auc-based permutation vim is due to chance since the distributions of auc values significantly differ. furthermore this difference in performances between both vims becomes even larger for larger sample sizes. and error-rate-based permutation vims for different class imbalances. the auc is used to assess the ability of a vim to discriminate between predictors with an effect and predictors without an effect. distributions are shown for total sample sizes of n =, n = and n = 1000. in a nutshell, in this first simulation the auc-based permutation vim performed better in case of class imbalance. the following subsections focus on the influence of sample size and effect size on the respective performance of both permutation vims in unbalanced data settings. influence of sample size in figure  the performance of both vims improves with an increased total sample size for a fixed imbalance level since an increase in the sample size results in more accurate tree predictions. the right panel of figure  shows that both permutation vims are hardly affected by class imbalances up to 10% when the sample size is rather large. if the sample size is smaller, however, the performance of the vims is considerably decreased for a 10% imbalance level. a decrease in performance for a 10% imbalance level is also observed for a sample size of n = especially for error-rate-based permutation vim. in a nutshell, class imbalance seems to be more problematic for the permutation vims if the total sample size is small. influence of effect size we now explore the ability of the permutation vims to identify predictors with different effect sizes in presence of unbalanced data. the auc was again used as an evaluation criterion to compare the ability of the auc-based and error-rate-based permutation vims to discriminate between associated and non-associated predictors. here the evaluation was done for each effect size separately meaning that one class comprised all the noise predictors while the other class comprised only predictors with the considered effect size. figure  shows the results for the setting with n = the results for other sample sizes are shown in additional file the left panel of figure  shows the performance of both permutation vims according to their ability to discriminate between predictors with weak effects and predictors without an effect. the middle panel corresponds to the auc values for predictors with a moderate effect versus noise predictors and the right panel corresponds to the auc values for predictors with a strong effect versus noise predictors. and error-rate-based permutation vims for different class imbalances. the auc is used to assess the ability of a vim to discriminate between noise predictors and predictors with a weak, moderate and strong effect. distributions are shown for a total sample size of n = unsurprisingly, for both permutation vims predictors having only a weak effect are less discriminable from noise predictors than predictors with stronger effects. for imbalances up to 20% both vims identify nearly all predictors with a strong effect. obviously there are unbalanced data settings where the standard permutation vim still perfectly separates between noise predictors and predictors with pronounced effects. we conclude that class imbalance is more problematic if predictors with weak effects are to be identified while it plays a minor role if the classes are well separable. comparison study with real data figure  shows the distribution of auc values for 100 modified c-to-u conversion datasets for varying imbalance levels. for the balanced dataset and for slight class imbalances up to 40% both vims have a perfect discriminative ability since all associated predictors receive a higher vi than any noise predictor. overall the performance of both vims decreases with an increasing class imbalance. note that the decreasing performance for increasing class imbalances might be partly attributable to the reduced total sample size as the class imbalance was created by randomly subsampling observations from the class with the edited sites. when comparing both vims the auc-based permutation vim significantly outperformed the standard permutation vim. for an imbalance of 30% the auc-based permutation vim clearly identified more associated predictors than the error-rate-based permutation vim. the superiority of the auc-based permutation vim over the standard permutation vim increased with an increasing class imbalance. for imbalances between 15% and 5% the discrepancy between the performance of auc-based and standard permutation vim was maximal. permutation vims for different class imbalances derived from modified datasets from c-to-u conversion data. the auc is used to assess the ability of a vim to discriminate between associated predictors and predictors not associated with the response. overall, this study on real data impressively shows that the auc-based permutation vim also works for complex real data and outperforms the standard permutation vim in almost all class imbalance settings.  the problem of unbalanced data has been widely discussed in the literature for diverse classifiers including random forests. many approaches have been developed to improve the predictive ability of rf classifiers for unbalanced data settings. however less attention has been paid to the behaviour of random forests’ variable importance measures for unbalanced data. in this paper we explored the performance of the permutation vim for different class imbalances and proposed an alternative permutation vim which is based on the auc. our studies on simulated as well as on real data show that the commonly used error-rate-based permutation vim loses its ability to discriminate between associated predictors and predictors not associated with the response for increasing class imbalances. this is particularly crucial for small sample sizes and if predictors with weak effects are to be detected. the decreasing performance of the standard permutation vim results from two sources: the class imbalance on the training data level leading to trees more often predicting the majority class and the class imbalance at the oob data level leading to blurred vis due to a much higher weighting of error rate differences in the majority class. a higher weighting of the majority class in the vi calculation is problematic because the difference in error rates is shown to be less pronounced in the majority class than in the minority class. note that in some cases it might be interesting to assess the increase in error rate obtained when a certain predictor is removed. in this case the error-rate-based permutation vim can be considered. if the goal is to rank the predictors according to their discrimination power, however, the auc-based permutation vim should be preferred. the problem of imbalance at the oob data level is directly addressed with the use of a novel auc-based permutation vim. this vim puts the same weight on both classes by measuring the difference in aucs instead of the difference in error rates. it is thus able to detect changes in tree predictions when permuting associated predictors which might not be grasped by the standard permutation vim. in contrast, the imbalance on training data level is not addressed by the auc-based permutation vim, meaning that the structure of a tree remains untouched. on the one hand this is a drawback since class predictions before and after permuting a predictor are similar even if the respective predictor is associated with the response, resulting in a reduced change in the aucs. on the other hand preserving the tree structure can be regarded as an advantage since a change in tree structure might open space for new unexpected behaviours. it is a major advantage of our novel auc-based permutation vim that it is based on exactly the same principle and differs from the standard permutation vim only with respect to the accuracy measurement. it is thus expected to share the advantages of the standard permutation vim and its properties and behaviours discovered in recent years. our studies on simulated as well as on real data show that the auc-based permutation vim outperforms the commonly used error-rate-based permutation vim as well as the error-rate-based permutation vim computed only using observations from the minority class in case of unbalanced data settings. the difference in performance between our novel auc-based permutation vim and the standard permutation vim can be substantial, especially for extremely unbalanced data settings. but even for slight class imbalances the auc-based permutation vim has shown to be superior to the standard permutation vim. we conclude from our studies that the auc-based permutation vim should be preferred to the standard permutation vim whenever two response classes have different class sizes and the aim is to identify relevant predictors. availability and requirements the auc-based permutation vim is implemented in the new version of the party package for the freely-available statistical software r. it can be applied via the function varimpauc. all codes implementing our studies on simulated and on real data are available under http://www.ibe.med.uni-muenchen.de/organisation/mitarbeiter/070_drittmittel/janitza/index.html for reproducibility purposes. abbreviations auc: area under curve; oob: out-of-bag; rf: random forest; vim: variable importance measure; vi: variable importance. competing interests the authors declare that they have no competing interests. authors’ contributions sj wrote the paper and conducted all analyses. sj and alb developed and implemented the new vim. all authors contributed to the design of the analyses and substantially edited the manuscript. supplementary material additional file 1 this file shows the results of the performance comparison between the auc-based permutation vim and the error-rate-based permutation vim computed using only observations from the minority class. click here for file additional file 2: this file shows the distribution of auc-values for sample sizes n = and n = click here for file acknowledgements sj was supported by the german science foundation. the authors thank torsten hothorn for integrating the implementation of the auc-based permutation vim into the new version of the party package.
novel auc-based permutation vim for different class imbalance levels using curve that is expected to be more robust towards class imbalance. random forestconditional inference treesvariable importance measurefeature selectionunbalanced dataclass imbalancearea under the curve. permutation vim outperforms the standard permutation vim for unbalanced data high dimensional data as well as for ranking candidate predictors based on we investigated the performance of the standard permutation vim and of our the standard permutation vim loses its ability to discriminate between the results suggest that the new auc-based explore the performance of the permutation vim for unbalanced data settings and introduce an alternative permutation vim based on the area under the settings while both permutation vims have equal performance for balanced permutation vim for unbalanced data settings, while the performance of both classification performance of rf is known to be suboptimal in case of is implemented in the r package party for the unbiased rf variant based on been examined in the case of unbalanced response classes. the so-called random forest variable importance measures.
 the random forest method is a commonly used tool for classification with high dimensional data as well as for ranking candidate predictors based on the so-called random forest variable importance measures. however the classification performance of rf is known to be suboptimal in case of strongly unbalanced data, i.e. data where response class sizes differ considerably. suggestions were made to obtain better classification performance based either on sampling procedures or on cost sensitivity analyses. however to our knowledge the performance of the vims has not yet been examined in the case of unbalanced response classes. in this paper we explore the performance of the permutation vim for unbalanced data settings and introduce an alternative permutation vim based on the area under the curve that is expected to be more robust towards class imbalance.  we investigated the performance of the standard permutation vim and of our novel auc-based permutation vim for different class imbalance levels using simulated data and real data. the results suggest that the new auc-based permutation vim outperforms the standard permutation vim for unbalanced data settings while both permutation vims have equal performance for balanced data settings.  the standard permutation vim loses its ability to discriminate between associated predictors and predictors not associated with the response for increasing class imbalance. it is outperformed by our new auc-based permutation vim for unbalanced data settings, while the performance of both vims is very similar in the case of balanced classes. the new auc-based vim is implemented in the r package party for the unbiased rf variant based on conditional inference trees. the codes implementing our study are available from the companion website: http://www.ibe.med.uni-muenchen.de/organisation/mitarbeiter/070_drittmittel/janitza/index.html. random forestconditional inference treesvariable importance measurefeature selectionunbalanced dataclass imbalancearea under the curve. 