Megha Dubey

Xavier Sauvage
email: xavier.sauvage@univ-rouen.fr

Fabien Cuvilly

Samuel Jouen

Béatrice Hannoyer

Atomic scale characterization of the nucleation and growth of SnO2 particles in oxidized CuSn alloys

Keywords: Internal oxidation, copper alloy, SnO 2, orientation relationship, TEM

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

At elevated temperatures (i.e. in a range of 500°C to 800°C), the oxidation of pure copper is characterized by the formation of a double oxide layer of Cu 2 O and CuO [1][2][3][4], in ratio that depends on the temperature [5] and pressure [6]. Cu 2 O being a metal-deficient oxide in which the lattice diffusion of copper ions is several orders of magnitude faster than oxygen diffusion, the rate of growth of the cuprous oxide sublayer is controlled by outward diffusion of copper cations via metal vacancies [7,8]. In the top CuO layer, there are no vacancies available for fast diffusion of reacting species and hence the growth rate remains very low as compared to Cu 2 O [9,10]. The presence of impurities in copper plays a very important role on the oxidation mechanisms and kinetics. Zhu et al. suggested that impurities could explain the discrepancies in the literature data reported for the copper oxidation kinetics [11]. Impurities impede the lateral growth of both Cu 2 O [11] and CuO grains [2,9] that favors grain boundary diffusion of Cu, faster than lattice diffusion, and consequently leads to an increased oxidation rate. Alloying element in solid solution in the fcc-Cu phase can also strongly affect the oxidation kinetics. Depending on the alloying element diffusivity in both the alloy and metal oxides, various scenarios are reported. For example, in the case of oxidized Cu-Si alloys, a continuous SiO 2 layer appears at the Cu/Cu 2 O interface. This layer significantly reduces the oxidation rate which is explained by the lower diffusion rate of copper ions in SiO 2 than in Cu 2 O [12,13]. For other alloys like Cu-Ti [14] or Cu-Ni [15], internal oxidation of the alloying element was reported. The nucleation of oxide particles inside the matrix is promoted by the oxygen diffusion [14,16] and these particles could exhibit various shapes and sizes depending on misfits and interfacial energies [17,18]. Their influence on the overall oxidation rate of the alloys is however not fully understood and could be rather complex. The case of CuSn alloys is of particular interest because a small amount of Sn slows down the oxidation kinetic, thus this element has a protective effect against oxidation. Internal oxidation of Sn was reported in 3 to 13wt% Sn alloys oxidized in 1 atm. O 2 [19] and in 8.2 wt% alloy oxidized in 1 atm. laboratory air [20]. This phenomenon is attributed to the relatively low mobility of Sn. However, depending of the concentration and of the oxidation temperature, SnO 2 particles are detected in an inner mixed oxide layer of Cu 2 O and SnO 2 or accumulated close to the alloy/scale interface [19][20][21][START_REF] Mathis | Copper-Proceedings of International Conference Copper '06[END_REF]. The aim of the present work was to clarify the exact role of tin in the oxidation kinetics of Cu-Sn alloys with a special emphasis on the nucleation and growth of SnO 2 nanoparticles precipitated internally in the fcc-Cu matrix.

Two model monophase CuSn alloys were prepared by cast melting (provided by KME Corporation), containing 4.2 and 8.2 wt. % Sn respectively (Cu balance). In the following, they are referred as CuSn4 and CuSn8 respectively. Samples for oxidation experiments were cut in coupons of size ~15x10x0.8 mm and homogenized under vacuum (~5x10 -5 mbar) at 600°C for 4 hr. Then, they were mechanically polished and finally cleaned with isopropanol and dried before oxidation. Oxidations were performed under laboratory static air in a muffle furnace maintained at 600°C (±2%) during four hours. After such a treatment, samples typically exhibit external multilayered oxide scales on the surface and an internal oxidation zone as discussed in [20]. To characterize the internally oxidized area, Transmission Electron Microscopy (TEM) samples were prepared from the specimen cross-section by site specific Focused Ion Beam (FIB) lift out technique [START_REF] Stevie | [END_REF] in a cross-beam NVISION-40 ZEISS ®. Samples were then observed in a probe corrected JEOL® ARM200F TEM operated at 200kV. Energy Filtered images were recorded using a Gatan® Imaging Filter (GIF Quantum). High Angle Annular Dark Field (HAADF) images were recorded in the scanning mode (STEM) with a 0.1 nm probe having a convergence angle of 30mrad. The collection angle on the HAADF detector was in a range of 50 to 180 mrad.

In the internal oxidation zone, the Sn in solid solution is oxidized giving rise to a two phase mixture formed by a fcc-Cu matrix and a significant volume fraction of SnO 2 . The number density of SnO 2 particle is rather low, and these particles are plate shaped as observed in the internal oxidation zone of the CuSn8 alloy (Fig. 1(a)). The thickness of these platelets is in the range of 10 to 50nm, the length up to few micrometers and the width in a range of 50 to 100nm (not shown here). There is a large distribution in the inter-plate spacing, from 100 to 500nm. Energy Filtered (EF) TEM confirms that these platelets are embedded in the Cu matrix and are rich in Sn and O (Fig. 1(a)-inset). Beside, using electron diffraction, the crystallographic structure of the internal oxide platelets was identified; it matches the expected rutile structure of SnO 2 [24]. A diffraction pattern was recorded in the [110] zone axis of the fcc-Cu (Fig. 1 (b)), and it is interesting to note that it also fits the [1][2][3][4][5][6][7][8][9][10] It is interesting to note that the lattice mismatch along this interface, between (002) SnO 2 and (220) Cu planes is positive (meaning that the matrix is in tension and the precipitate in compression) and relatively large 25%.

The microstructure in the internal oxide zone of the CuSn4 alloy looks very similar, i.e. there is a significant volume fraction of SnO 2 elongated plates. The diffraction pattern displayed on Fig. 3(c) shows that the OR between Cu and SnO 2 is similar to the OR found in the CuSn8 alloy. A platelet is imaged using high resolution HAADF STEM in the [-110] zone axis of Cu, also corresponding to the [001] zone axis of SnO 2 (Fig. 3 (a)). The imaging is thus performed parallel to the growth direction of the plate. However, there are two different habit planes:

(002) Cu for the long horizontal interface and (-2-20) Cu for the short vertical interface. For the first habit plane, the lattice mismatch between (-220) SnO 2 and (-2-20) Cu is very large (31%) and positive, whilst for the second, the misfit between (220) SnO 2 and (002) Cu is negative and much smaller ( -7%). These misfits are compensated by dislocations lying at the interface as underlined on Fig. 4.

It is interesting to note that these large misfits do not inhibit the nucleation of the SnO 2 phase but surprisingly the thinnest dimension of SnO 2 plates does correspond to the lowest misfit.

Two Sn oxides are reported in the literature, namely SnO and SnO 2 . The free energy of formation of SnO 2 is much lower than that of SnO (-396 kJ/mol vs. -197 kJ/mol at 600°C [18]), so it was rather logical to observe only the SnO 2 phase even if in some cases the metastable SnO phase could be obtained [25]. Beside, the low number density of particles observed by TEM clearly indicates that the nucleation rate should be rather low. This is probably due to the large misfits creating large elastic distortions. Once nucleated, SnO 2 particles grow in the direction of the Sn rich bulk, thus the internal oxidation kinetics is obviously mostly controlled by the growth and not the nucleation. SnO 2 particles are plate shaped indicating that there is also some lateral growth. Indeed, while growing, these particles transform into elongated plates where the largest habit plane (002) Cu // (220) SnO 2 (marked (1) in Fig. 3 (a) and (b)) combines the stronger misfits between the fcc-Cu matrix and the SnO 2 tetragonal phase (+25% and +31%) as demonstrated by our experimental data.

Metal-oxide interfaces have been investigated theoretically and experimentally (using High

Resolution TEM) in various systems [26,27]. It has been shown that misfit dislocations along such interfaces are not defects like bulk dislocations but an integral part of the interface structure that is determined by the interaction between misfit and bonding. Thus, in the present case, the growth of SnO 2 plates is also controlled by these interactions across the new interface that is created. HAADF HR-STEM images provide directly both chemical (Z contrast) and structural information. Overlapping the metal-oxide interfaces with Cu and SnO 2 crystal structures clearly exhibit along the two major habit planes (marked ( 1) and (2) on Fig. 3) a polar oxide interface terminated by a pure oxygen layer (red dots). Thus, the main difference between the two habits planes shown in the Fig. 3 is the misfit and it is rather surprising that the largest dimension of SnO 2 plates corresponds to the direction with the highest misfits and thus the highest elastic interaction. However, one should note that these misfits are largely positive, building up some tensile stresses in the copper matrix. Since the growth of SnO 2 particles requires some significant volume expansion (about 7% for CuSn4 and about 13% for CuSn8), and even if part of it is probably compensated by the outward diffusion of copper; this may favor a growth with some preferred habit planes leading to a compressive state in the SnO 2 particles.

In conclusion, large misfits between the tetragonal SnO 2 and the fcc-Cu phases give rise to a low nucleation rate. In combination with the tin gradient that builds up during the internal oxidation process, this lead to the formation of plate shaped SnO 2 particles. The internal oxidation kinetic is controlled by the growth of theses plates. No significant differences were observed for the two alloys considered (CuSn4 and CuSn8). HR-STEM HAADF images directly show that polar oxide interface planes terminating by a pure oxygen plane are favored. However, elastic stresses play also an important role. Indeed, the elongation of the SnO 2 particles is promoted along directions where misfits lead a tensile state in the matrix to compensate the volume expansion required for the internal oxidation of Sn. This feature promotes the plate shape growth of SnO 2 .

Figure Captions

  zone axis of SnO 2 . Obviously, platelets are elongated along the Cu [-110] and the SnO 2 [001] directions. Internal oxides particles were also characterized in STEM. Since the average atomic number in the SnO 2 structure is lower than that of Cu, oxide platelets appear dark on HAADF images as shown on Fig. 2(a). The internal oxidation front is clearly exhibited on this image where platelets are growing from the top left corner down to the bottom right. The high resolution STEM-HAADF image (Fig. 2(b)) was obtained along the Cu [110] zone axis. On this image, only Cu and Sn rich atomic columns are brightly imaged. The Cu/SnO 2 interface (arrowed) appears edge-on and the orientation relationship (OR) between Cu and SnO 2 is thus given by: (002) Cu // (220) SnO 2 (habit planes) and [-110] Cu // [001] SnO 2 .

Figure 1 :

 1 Figure 1: CuSn8 oxidized at 600°C for 4 hr (a) BF-TEM image showing SnO 2 platelets (arrowed) within the Cu matrix ; inset: EFTEM image (Cu red, Sn blue and O green), confirming that the platelets are Sn and O rich (tin oxide). (b) Corresponding SAED pattern, spots are indexed: subscript 'm' referring to the fcc-Cu matrix in [110] zone axis and subscript 'p', referring to the tetragonal SnO 2 oxide platelets in [1-10] zone axis.

Figure 2 :

 2 Figure 2: CuSn8 oxidized at 600°C for 4 hr (a) low magnification HAADF-STEM images showing several parallel SnO 2 plates growing in the fcc-Cu matrix. (b) High magnification HAADF-STEM filtered image showing the atomic structure of the Cu/SnO 2 interface in [110] fcc-Cu and [1-10] SnO 2 zone axes.

Figure 3 :

 3 Figure 3: CuSn4 oxidized at 600°C for 4 h. (a) HAADF HR-STEM image (unfiltered) of SnO 2 precipitate in [001] and [-110] fcc-Cu zone axes, where Sn and Cu rich columns are imaged.(b) Zooms of selected regions marked (1) and (2) in Fig.3 (a) showing the two Cu/SnO 2 interfaces with the overlap of Cu and SnO 2 crystal structures (Cu green, Sn blue, O red). The arrows indicate the termination plane in the SnO 2 phase, being in both case pure O. (c) SAED pattern giving the OR between the SnO 2 platelet 'p' and the fcc-Cu matrix 'm' of Fig. 3(a).

Figure 4

 4 Figure 4 CuSn4 alloy oxidized at 600°C for 4 h-HR-STEM HAADF unfiltered image showing the two habit planes between Cu and SnO 2 particles. Misfit dislocations are indicated by T-shaped symbols in the SnO 2 phase and by arrows in the Cu matrix. Interfaces and growth ledges are highlighted by the dashed lines.

Figure 1 Figure 2

 12 Figure 1

Acknowledgements

Authors would like to thank the Region Haute Normandie for the financial support of this work (research grant attributed to M. Dubey). M. Dubey would also like to thank N.

Masquelier for fruitful discussions.


Robin Genuer
email: robin.genuer@math.u-psud.fr

Jean-Michel Poggi

Christine Tuleau-Malot

Variable Selection using Random Forests

Keywords: Random Forests, Regression, Classification, Variable Importance, Variable Selection, High Dimensional Data 2010 MSC: 62G09, 62H30, 62G08

This paper proposes, focusing on random forests, the increasingly used statistical method for classification and regression problems introduced by Leo Breiman in 2001, to investigate two classical issues of variable selection. The first one is to find important variables for interpretation and the second one is more restrictive and try to design a good prediction model. The main contribution is twofold: to provide some insights about the behavior of the variable importance index based on random forests and to propose a strategy involving a ranking of explanatory variables using the random forests score of importance and a stepwise ascending variable introduction strategy.

Introduction

This paper is primarily interested in random forests for variable selection. Mainly methodological the main contribution is twofold: to provide some insights about the behavior of the variable importance index based on random forests and to use it to propose a two-steps algorithm for two classical problems of variable selection starting from variable importance ranking. The first problem is to find important variables for interpretation and the second one is more restrictive and try to design a good prediction model. The general strategy involves a ranking of explanatory variables using the random forests score of importance and a stepwise ascending variable introduction strategy. Let us mention that we propose an heuristic strategy which does not depend on specific model hypotheses but based on datadriven thresholds to take decisions.

Before entering into details, let us shortly present in the sequel of this introduction the three main topics addressed in this paper: random forests, variable importance and variable selection.

Random forests

Random forests (RF henceforth) is a popular and very efficient algorithm, based on model aggregation ideas, for both classification and regression problems, introduced by [START_REF] Breiman | Random Forests[END_REF]. It belongs to the family of ensemble methods, appearing in machine learning at the end of nineties (see for example [START_REF] Dietterich | An experimental comparison of three methods for constructing ensembles of decision trees: Bagging, Boosting and randomization[END_REF] and [START_REF] Dietterich | Ensemble Methods in Machine Learning[END_REF]). Let us briefly recall the statistical framework by considering a learning set L = {(X 1 , Y 1 ), . . . , (X n , Y n )} made of n i.i.d. observations of a random vector (X, Y). Vector X = (X1 , ..., X p ) contains predictors or explanatory variables, say X ∈ R p , and Y ∈ Y where Y is either a class label or a numerical response. For classification problems, a classifier t is a mapping t : R p → Y while for regression problems, we suppose that Y = s(X) + ε with E[ε|X] = 0 and s the so-called regression function. For more background on statistical learning, see e.g. [START_REF] Hastie | The Elements of Statistical Learning[END_REF]. Random forests is a model building strategy providing estimators of either the Bayes classifier, which is the mapping minimizing the classification error P(Y t(X)), or the regression function.

The principle of random forests is to combine many binary decision trees built using several bootstrap samples coming from the learning sample L and choosing randomly at each node a subset of explanatory variables X. More precisely, with respect to the well-known CART model building strategy (see [START_REF] Breiman | Classification And Regression Trees[END_REF]) performing a growing step followed by a pruning one, two differences can be noted. First, at each node, a given number (denoted by mtry) of input variables are randomly chosen and the best split is calculated only within this subset. Second, no pruning step is performed so all the trees of the forest are maximal trees.

In addition to CART, bagging, another well-known related tree-based method, is to be mentioned (see [START_REF] Breiman | Bagging predictors[END_REF]). Indeed random forests with mtry = p reduce simply to unpruned bagging. The associated R 1 packages are respectively randomForest (intensively used in the sequel of the paper), rpart and ipred for CART and bagging respectively (cited here for the sake of completeness).

RF algorithm becomes more and more popular and appears to be very powerful in a lot of different applications (see for example Díaz- [START_REF] Díaz-Uriarte | Gene Selection and classification of microarray data using random forest[END_REF] for gene expression data analysis) even if it is not clearly elucidated from a mathematical point of view (see the recent paper by [START_REF] Biau | Consistency of random forests and other averaging classifiers[END_REF] about purely random forests and [START_REF] Bühlmann | Analyzing Bagging[END_REF] about bagging). Nevertheless, [START_REF] Breiman | Random Forests[END_REF] sketches an explanation of the good performance of random forests related to the good quality of each tree (at least from the bias point of view) together with the small correlation among the trees of the forest, where the correlation between trees is defined as the ordinary correlation of predictions on so-called out-of-bag (OOB henceforth) samples. The OOB sample which is the set of observations which are not used for building the current tree, is used to estimate the prediction error and then to evaluate variable importance.

The R package about random forests is based on the seminal contribution of [START_REF] Breiman | Random Forests[END_REF] and is described in [START_REF] Liaw | Classification and Regression by randomForest[END_REF]. In this paper, we focus on the randomForest procedure. The two main parameters are mtry, the number of input variables randomly chosen at each split and ntree, the number of trees in the forest. Some details about numerical and sensitivity experiments can be found in [START_REF] Genuer | Random Forests: some methodological insights[END_REF]).

In addition, let us mention we will concentrate on the prediction performance of RF focusing on out-of-bag (OOB) error (see [START_REF] Breiman | Random Forests[END_REF]). We use this kind of prediction error estimate for three reasons: the main is that we are mainly interested in comparing models instead of assessing models, the second is that it gives fair estimation compared to the usual alternative test set error even if it is considered as a little bit optimistic and the last one, is that it is a default output of the randomForest procedure, so it is used by almost all users.

Variable importance

The quantification of the variable importance (VI henceforth) is an important issue in many applied problems complementing variable selection by interpretation issues. In the linear regression framework it is examined for example by [START_REF] Grömping | Estimators of Relative Importance in Linear Regression Based on Variance Decomposition[END_REF], making a distinction between various variance decomposition based indicators: "dispersion importance", "level importance" or "theoretical importance" quantifying explained variance or changes in the response for a given change of each regressor. Various ways to define and compute using R such indicators are available (see [START_REF] Grömping | Relative Importance for Linear Regression in R: The Package relaimpo[END_REF]).

In the random forests framework, the most widely used score of importance of a given variable is the increasing in mean of the error of a tree (MSE for regression and misclassification rate for classification) in the forest when the observed values of this variable are randomly permuted in the OOB samples (let us mention that it could be slightly negative). Often, such random forests VI is called permutation importance indices in opposition to total decrease of node impurity measures already introduced in the seminal book about CART by [START_REF] Breiman | Classification And Regression Trees[END_REF].

Even if only little investigation is available about RF variable importance, some interesting facts are collected for classification problems when this index is based on the average loss of entropy criterion, like the Gini entropy used for growing classification trees. Let us cite two remarks. The first one is that the RF Gini importance is not fair in favor of predictor variables with many categories (see [START_REF] Strobl | Bias in random forest variable importance measures: illustrations, sources and a solution[END_REF]) while the RF permutation importance is a more reliable indicator. So we restrict our attention to this last one. The second one is that it seems that permutation importance overestimates the variable importance of highly correlated variables and a conditional variant is proposed by [START_REF] Strobl | Conditional variable importance for Random Forests[END_REF]. Let us mention that, in this paper, we do not diagnose such a critical phenomenon for variable selection. The recent paper by [START_REF] Archer | Empirical characterization of random forest variable importance measures[END_REF], focusing more specifically on the VI topic is also of interest. We address two crucial questions about the variable importance behavior: the importance of a group of variables and its behavior in presence of highly correlated variables. This is the first goal of this paper.

Variable selection

Many variable selection procedures are based on the cooperation of variable importance for ranking and model estimation to generate, evaluate and compare a family of models. Following [START_REF] Kohavi | Wrappers for Feature Subset Selection[END_REF] and [START_REF] Guyon | An introduction to variable and feature selection[END_REF]), it is usual to distinguish three types of variable selection methods: "filter" for which the score of variable importance does not depend on a given model design method; "wrapper" which include the prediction performance in the score calculation; and finally "embedded" which intricate more closely variable selection and model estimation.

Let us briefly mention some of them, in the classification case, which are potentially competing tools, of course the wrapper methods based on VI coming from CART, and from random forests. Then some examples of embedded methods: [START_REF] Poggi | Classification supervisée en grande dimension. Application à l'agrément de conduite automobile[END_REF] propose a method based on CART scores and using stepwise ascending procedure with elimination step; [START_REF] Guyon | Gene selection for cancer classification using support vector machines[END_REF] and Rakotomanonjy (2003), propose methods based on SVM scores and using descending elimination. More recently, Ben [START_REF] Ishak | Sélection de variables pour la classification binaire en grande dimension : comparaisons et application aux données de biopuces[END_REF] propose a stepwise variant while [START_REF] Park | An L1 regularization-path algorithm for generalized linear models[END_REF] propose a "LARS" type strategy (see [START_REF] Efron | Least angle regression[END_REF]) for classification problems. Finally let us mention a mixed approach, see [START_REF] Fan | Sure independence screening for ultra-high dimensional feature space[END_REF] in regression, ascending in order to avoid to select redundant variables or, for the case n << p, descending first using a screening procedure to reach a classical situation n ∼ p, and then ascending using LASSO or SCAD, see [START_REF] Fan | Variable selection via nonconcave penalized likelihood and its oracle properties[END_REF]. We propose in this paper, a two-steps procedure, the second one depends on the objective (interpretation or prediction) while the first one is common. The key point is that it is entirely based on random forests, so fully non parametric and then free from the usual linar framework.

A typical situation

Let us close this section by introducing a typical situation which can be useful to capture the main ideas of this paper. Let us consider a high dimensional (n << p) classification problem for which the predictor variables are associated to a pixel in an image or a 3D location in the brain like in fMRI brain activity classification problems. In such situations, of course it is clear that there is a lot of useless variables and that there exist a lot a highly correlated groups of predictors corresponding to brain regions. We emphasize that two distinct objectives about variable selection can be identified: (1) to find important variables highly related to the response variable for interpretation purpose; (2) to find a small number of variables sufficient for a good prediction of the response variable. Key tools combine variable importance thresholding, variable ranking and stepwise introduction of variables. Turning back to our typical example, an example of the first kind of problem is the determination of entire regions in the brain or a full parcel in an image while an instance of the second one is to exhibit a sufficient subset of the most discriminant variables within the previously highlighted groups.

Outline

The paper is organized as follows. After this introduction, Section 2 proposes to study the behavior of the RF variable importance, especially in the presence of groups of highly correlated explanatory variables. Section 3 investigates the two classical issues of variable selection using the permutation based random forests score of importance. Section 4 examines some experimental results, by focusing mainly on high dimensional classification datasets and, in order to illustrate the general value of the strategy it is applied to a standard (n >> p) regression dataset. Finally Section 5 opens discussion about future work.

Variable importance

The quantification of the variable importance (abbreviated VI) is a crucial issue not only for ranking the variables before a stepwise estimation model but also to interpret data and understand underlying phenomenons in many applied problems.

In this section, we examine the RF variable importance behavior according to three different issues. The first one deals with the sensitivity to the sample size n and the number of variables p. The second examines the sensitivity to method parameters mtry and ntree. The third one deals with the variable importance in presence of groups of highly correlated variables.

As a result, a good choice of parameters of RF can help to better discriminate between important and useless variables. In addition, it can increase the stability of VI scores.

To illustrate this discussion, let us examine a simulated dataset for the case n << p, introduced by [START_REF] Weston | Use of the zero norm with linear models and kernel methods[END_REF] and called "toys data" in the sequel. It is an equiprobable twoclass problem, Y ∈ {-1, 1}, with 6 true variables, the others being some noise. This example is interesting since it constructs two near independent groups of 3 significant variables (highly, moderately and weakly correlated with response Y) and an additional group of noise variables, uncorrelated with Y. A forward reference to the plots on the left side of Figure 1 allow to see the variable importance picture and to note that the importance of the variables 1 to 3 is much higher than the one of variables 4 to 6. More precisely, the model is defined through the conditional distribution of the X i for Y = y:

• for 70% of data, X i ∼ yN(i, 1) for i = 1, 2, 3 and X i ∼ yN(0, 1) for i = 4, 5, 6.

• for the 30% left, X i ∼ yN(0, 1) for i = 1, 2, 3 and X i ∼ yN(i -3, 1) for i = 4, 5, 6.

• the other variables are noise, X i ∼ N(0, 1) for i = 7, . . . , p.

After simulation, the obtained variables are finally standardized.

Let us consider the toys data and compute the variable importance.

Remark 2.1. Let us mention that variable importance is computed conditionally to a given realization even for simulated datasets. This choice which is criticizable if the objective is to reach a good estimation of an underlying constant, is consistent with the idea of staying as close as possible to the experimental situation dealing with a given dataset. In addition, the number of permutations of the observed values in the OOB sample, used to compute the score of importance is set to the default value 1. On each row, the first plot is the reference one for which we observe a convenient picture of the relative importance of the initial variables. Then, when p increases tremendously, we try to check if: (1) the situation between the two groups remains readable; (2) the situation within each group is stable; (3) the importance of the additional dummy variables is close to 0.

Sensitivity to n and p

The situation n = 500 (graphs at the top of the figure) corresponds to an "easy" case, where a lot of data are available and n = 100 (graphs at the bottom) to a harder one. For each value of n, three values of p are considered: 6, 200 and 500. When p = 6 only the 6 true variables are present. Then two very difficult situations are considered: p = 200 with a lot of noisy variables and p = 500 is even harder. Graphs are truncated after the 16th variable for readability (importance of noisy variables left are of the same order of magnitude as the last plotted).

Let us comment on graphs on the first row (n = 500). When p = 6 we obtain concentrated boxplots and the order is clear, variables 2 and 6 having nearly the same importance. When p increases, the order of magnitude of importance decreases (note that the y-axis scale is different for p = 6 and for p 6). The order within the two groups of variables (1 -3 and 4 -6) remains the same, while the overall order is modified (variable 6 is now less important than variable 2). In addition, variable importance is more unstable for huge values of p. But what is remarkable is that all noisy variables have a zero VI. So one can easily recover variables of interest.

In the second row (n = 100), we note a greater instability since the number of observations is only moderate, but the variable ranking remains quite the same. What differs is that in the difficult situations (p = 200, 500) importance of some noisy variables increases, and for example variable 4 cannot be highlighted from noise (even variable 5 in the bottom right graph). This is due to the decreasing behavior of VI with p growing, coming from the fact that when p = 500 the algorithm randomly choose only 22 variables at each split (with the mtry default value). The probability of choosing one of the 6 true variables is really small and the less a variable is chosen, the less it can be considered as important. We will see the benefits of increasing mtry in the next paragraph.

In addition, let us remark that the variability of VI is large for true variables with respect to useless ones. This remark can be used to build some kind of test for VI (see [START_REF] Strobl | Bias in random forest variable importance measures: illustrations, sources and a solution[END_REF]) but of course ranking is better suited for variable selection.

We now study how this VI index behaves when changing values of the main method parameters.

Sensitivity to mtry and ntree

The choice of mtry and ntree can be important for the VI computation. Let us fix n = 100 and p = 200. In Figure 2 we plot variable importance obtained using three values of mtry (14 the default, 100 and 200) and two values of ntree (500 the default, and 2000). The effect of taking a larger value for mtry is obvious. Indeed the magnitude of VI is more than doubled starting from mtry = 14 to mtry = 100, and it again increases whith mtry = 200. The effect of ntree is less visible, but taking ntree = 2000 leads to better stability. What is interesting in the bottom right graph is that we get the same order for all true variables in every run of the procedure. In top left situation the mean OOB error rate is about 5% and in the bottom right one it is 3%. The gain in error may not be considered as large, but what we get in VI is interesting.

Sensitivity to highly correlated predictors

Let us now address an important issue: how does variable importance behave in presence of several highly correlated variables? We take as basic framework the previous context with n = 100, p = 200, ntree = 2000 and mtry = 100. Then we add to the dataset highly correlated replications of some of the 6 true variables. The replicates are inserted between the true variables and the useless ones. The first graph of Figure 3 is the reference one: the situation is the same as previously. Then for the three other cases, we simulate 1, 10 and 20 variables with a correlation of 0.9 with variable 3 (the most important one). These replications are plotted between the two vertical lines.

The magnitude of importance of the group 1, 2, 3 is steadily decreasing when adding more replications of variable 3. On the other hand, the importance of the group 4, 5, 6 is unchanged. Notice that the importance is not divided by the number of replications. Indeed in our example, even with 20 replications the maximum importance of the group containing variable 3 (that is variable 1, 2, 3 and all replications of variable 3) is only three times lower than the initial importance of variable 3. Finally, note that even if some variables in this group have low importance, they cannot be confused with noise.

Let us briefly comment on similar experiments (see Figure 4) but perturbing the basic situation not only by introducing highly correlated versions of the third variable but also of the sixth, leading to replicate the most important of each group. Again, the first graph is the reference one. Then we simulate 1, 5 and 10 variables of correlation about 0.9 with variable 3 and the same with variable 6. Replications of variable 3 are plotted between the first vertical line and the dashed line, and replications of variable 6 between the dashed line and the second vertical line.

The magnitude of importance of each group (1, 2, 3 and 4, 5, 6 respectively) is steadily decreasing when adding more replications. The relative importance between the two groups is preserved. And the relative importance between the two groups of replications is of the same order than the one between the two initial groups.

Prostate data variable importance

To end this section, we illustrate the behavior of variable importance on a high dimensional real dataset: the microarray data called Prostate, for which n = 102 and p = 6033 (see [START_REF] Singh | Gene expression correlates of clinical prostate cancer behavior[END_REF] for a detailed presentation). The global picture is the following: two hugely important variables, about twenty moderately important variables and the others of small importance. So, more precisely Figure 5 compares VI obtained for parameters set to their default values (graphs of the left column) and those obtained for ntree = 2000 and mtry = p/3 (graphs of the right column). Graphs are truncated after the 250th variable for readability (importance of noisy variables left are of the same order of magnitude as the last plotted).

Let us comment on Figure 5. For the two most important variables (first row), the magnitude of importance obtained with ntree = 2000 and mtry = p/3 is much larger than to the one obtained with default values. In the second row, the increase of magnitude is still noticeable from the third to the 9th most important variables and from the 10th to the 20th most important variables, VI is quite the same for the two parameter choices. In the third row, we get VI closer to zero for the variables with ntree = 2000 and mtry = p/3 than with default values. In addition, note that for the less important variables, boxplots are larger for default values, especially for unimportant variables (from the 200th to the 250th).

Variable selection

We distinguish two variable selection objectives:

1. to find important variables highly related to the response variable for interpretation purpose; 2. to find a small number of variables sufficient to a good prediction of the response variable.

The first is to magnify all the important variables, even with high redundancy, for interpretation purpose and the second is to find a sufficient parsimonious set of important variables for prediction.

As mentioned at the end of the introduction, we are guided in this paper by a typical situation matching two characteristics. The first one is high dimensionality, or at least when the number of true variables is much less than p, and the second one is the presence of groups of highly correlated predictors. They are also specifically addressed in two earlier works by Díaz-Uriarte et al. ( 2006) and Ben [START_REF] Ishak | Sélection de variables pour la classification binaire en grande dimension : comparaisons et application aux données de biopuces[END_REF]. Let us briefly recall these contributions.

Díaz-Uriarte, Alvarez de Andrés propose a strategy based on recursive elimination of variables. More precisely, they first compute RF variable importance. Then, at each step, they eliminate the 20% of the variables having the smallest importance and build a new forest with the remaining variables. They finally select the set of variables leading to the smallest OOB error rate. The proportion of variables to eliminate is an arbitrary parameter of their method and does not depend on the data.

Ben Ishak, Ghattas choose an ascendant strategy based on a sequential introduction of variables. First, they compute some SVM-based variable importance. Then, they build a sequence of SVM models invoking at the beginning the k most important variables, by step of 1. When k becomes too large, the additional variables are invoked by packets. They finally select the set of variables leading to the model of smallest error rate. The way to introduce variables is not data-driven since it is fixed before running the procedure. They also compare their procedure with a similar one using RF instead of SVM.

Procedure

We propose the following two-steps procedure, the first one is common while the second one depends on the objective:

Step 1. Preliminary elimination and ranking:

• Compute the RF scores of importance, cancel the variables of small importance; • Order the m remaining variables in decreasing order of importance.

Step 2. Variable selection:

• For interpretation: construct the nested collection of RF models involving the k first variables, for k = 1 to m and select the variables involved in the model leading to the smallest OOB error; • For prediction: starting from the ordered variables retained for interpretation, construct an ascending sequence of RF models, by invoking and testing the variables stepwise. The variables of the last model are selected.

Of course, this is a sketch of procedure and more details are needed to be effective. The next paragraph answer this point but we emphasize that we propose an heuristic strategy which does not depend on specific model hypotheses but based on datadriven thresholds to take decisions.

Remark 3.1. Since we want to treat in an unified way all the situations, we will use for finding prediction variables the somewhat crude strategy previously defined. Nevertheless, starting from the set of variables selected for interpretation (say of size K), a better strategy could be to examine all, or at least a large part, of the 2 K possible models and to select the variables of the model minimizing the OOB error. But this strategy becomes quickly unrealistic for high dimensional problems so we prefer to experiment a strategy designed for small n and large K which is not conservative and even possibly leads to select fewer variables.

Starting example

To both illustrate and give more details about this procedure, we apply it on a simulated learning set of size n = 100 from the classification toys data model with p = 200. The results are summarized in Figure 6. The true variables (1 to 6) are respectively represented by (⊲, △, •, ⋆, ⊳, ). We compute, thanks to the learning set, 50 forests with ntree = 2000 and mtry = 100, which are values of the main parameters previously considered as well adapted for VI calculations (see Section 2.2).

Let us detail the main stages of the procedure together with the results obtained on toys data:

• Variable ranking.

First we rank the variables by sorting the VI (averaged from the 50 runs) in descending order.

The result is drawn on the top left graph for the 50 most important variables (the other noisy variables having an importance very close to zero too). Note that true variables are significantly more important than the noisy ones. We keep this order in mind and plot the corresponding standard deviations of VI. We use this graph to estimate some threshold for importance, and we keep only the variables of importance exceeding this level. More precisely, we select the threshold as the minimum prediction value given by a CART model fitting this curve (see Figure 7). This rule is, in general conservative and leads to retain more variables than necessary in order to make a careful choice later. The standard deviations of VI can be found in the top right graph. We can see that true variables standard deviation is large compared to the noisy variables one, which is close to zero. The threshold leads to retain 33 variables.

• Variable selection procedure for interpretation.

Then, we compute OOB error rates of random forests (using default parameters) of the nested models starting from the one with only the most important variable, and ending with the one involving all important variables kept previously. The variables of the model leading to the smallest OOB error are selected.

Note that in the bottom left graph the error decreases quickly and reaches its minimum when the first 4 true variables are included in the model. Then it remains constant. We select the model containing 4 of the 6 true variables.

More precisely, we select the variables involved in the first model almost leading to the smallest OOB error. The actual minimum is reached with 24 variables.

The expected behavior is non-decreasing as soon as all the "true" variables have been selected. It is then difficult to treat in a unified way nearly constant of or slightly increasing. In fact, we propose to use an heuristic rule similar to the 1 SE rule of [START_REF] Breiman | Classification And Regression Trees[END_REF] used for selection in the cost-complexity pruning procedure.

• Variable selection procedure for prediction.

We perform a sequential variable introduction with testing: a variable is added only if the error gain exceeds a threshold. The idea is that the error decrease must be significantly greater than the average variation obtained by adding noisy variables.

The bottom right graph shows the result of this step, the final model for prediction purpose involves only variables 3, 6 and 5. The threshold is set to the mean of the absolute values of the first order differentiated OOB errors between the model with p interp = 4 variables (the first model after the one we selected for interpretation, see the bottom left graph) and the one with all the p elim = 33 variables :

1 p elim -p interp p elim -1 j=p interp | OOB( j + 1) -OOB( j) | .
It should be noted that if one wants to estimate the prediction error, since ranking and selection are made on the same set of observations, of course an error evaluation on a test set or using a cross validation scheme should be preferred. It is taken into account in the next section when our results are compared to others.

To evaluate fairly the different prediction errors, we prefer here to simulate a test set of the same size than the learning set. The test error rate with all (200) variables is about 6% while the one with the 4 variables selected for interpretation is about 4.5%, a little bit smaller. The model with prediction variables 3, 6 and 5 reaches an error of 1%. Repeating the global procedure 10 times on the same data always gave the same interpretation set of variables and the same prediction set, in the same order.

Highly correlated variables

Let us now apply the procedure on toys data with replicated variables: a first group of variables highly correlated with variable 3 and a second one replicated from variable 6 (the most number of interpretation prediction replications set set 1 3 7 3 2 6 5 3 6 5 5 3 2 7 3 10 3 6 11 3 5 12 6 3 6 5 10 3 14 3 8 3 2 15 3 6 5 10 3 13 3 20 6 3 6 5 10 3

Table 1: Variable selection procedure in presence of highly correlated variables (augmented toys data) where the expression i j means that variable i is a replication of variable j important variable of each group). The situations of interest are the same as those considered to produce Figure 4.

Let us comment on Table 1, where the expression i j means that variable i is a replication of variable j.

Interpretation sets do not contain all variables of interest. Particularly we hardly keep replications of variable 6. The reason is that even before adding noisy variables to the model the error rate of nested models do increase (or remain constant): when several highly correlated variables are added, the bias remains the same while the variance increases. However the prediction sets are satisfactory: we always highlight variables 3 and 6 and at most one correlated variable with each of them.

Even if all the variables of interest do not appear in the interpretation set, they always appear in the first positions of our ranking according to importance. More precisely the 16 most important variables in the case of 5 replications are: (3 2 7 3 10 3 6 11 3 5 12 6 8 3 13 6 16 6 1 15 6 14 6 9 3 4), and the 26 most important variables in the case of 10 replications are: (3 14 3 8 3 2 15 3 6 5 10 3 13 3 20 6 21 6 11 3 12 3 18 6 1 24 6 7 3 26 6 23 6 16 3 25 6 22 6 17 6 19 6 4 9 3 ). Note that the order of the true variables (3 2 6 5 1 4) remains the same in all situations.

Experimental results

In this section we experiment the proposed procedure on four high dimensional classification datasets and then finally we examine the results on a standard regression problem to illustrate the versatility of the procedure.

Prostate data

We apply the variable selection procedure on Prostate data (for which n = 102 and p = 6033, see [START_REF] Singh | Gene expression correlates of clinical prostate cancer behavior[END_REF]). The graphs of Figure 8 are obtained as those of Figure 6, except that for the RF procedure, we use ntree = 2000, mtry = p/3 and for the bottom left graph, we only plot the 100 most important variables for visibility. The procedure leads to the same picture as previously, except for the OOB rate along the nested models which is less regular. The first point is to notice that the elimination step leads to keep only 270 variables. The key point is that the procedure selects 9 variables for interpretation, and 6 variables for prediction. The number of selected variables is then very much smaller than p = 6033.

In addition, to examine the variability of the interpretation and prediction sets the global procedure is repeated five times on the entire Prostate dataset. The five prediction sets are very close to each other. The number of prediction variables fluctuates between 6 and 10, and 5 variables appear in all sets. Among the five interpretation sets, 2 are identical and made of 9 variables and the 3 other are made of 25 variables. The 9 variables of the smallest sets are present in all sets and the biggest sets (of size 25) have 23 variables in common.

So, although the sets of variables are not identical for each run of the procedure, the most important variables are included in all of the sets.

Four high dimensional classification datasets

Let us consider the four well known high dimensional real datasets called Colon (n = 62, p = 2000), see [START_REF] Alon | Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide arrays[END_REF], Leukemia (n = 38, p = 3051), see [START_REF] Golub | Molecular classification of cancer: Class discovery and class prediction by gene expression monitoring[END_REF], Lymphoma (n = 62, p = 4026), see Alizahed (2000) and Prostate (n = 102, p = 6033), see [START_REF] Singh | Gene expression correlates of clinical prostate cancer behavior[END_REF]. We apply the global variable selection procedure on these four well known high dimensional real datasets, and we want to get an estimation of prediction error rates. Since these datasets are of small size and in order to be comparable with the previous results, we use a 5-fold cross-validation to estimate the error rate. So we split the sample in 5 stratified parts, each part is successively used as a test set, and the remaining of the data is used as a learning set. Note that the set of variables selected vary from one fold to another. So, we give in Table 2 the misclassification error rate, given by the 5-fold cross-validation, for interpretation and prediction sets of variables respectively. The number into brackets is the average number of selected variables. In addition, one can find the original error which stands for the misclassification rate given by the 5-fold cross-validation achieved with random forests using all variables. This error is calculated using the same partition in 5 parts and again we use ntree = 2000 and mtry = p/3 for all datasets.

The number of interpretation variables is hugely smaller than p, at most tens to be compared to thousands. The number of prediction variables is very small (always smaller than 12) and the reduction can be very important with respect to the interpretation set size. The errors for the two variable selection proce- 2008)) which have compared their method with 5 competitors (mentioned in the introduction) for classification problems on these four datasets. Error rates are comparable. With the prediction procedure, as already noted in the introductory remark, we always select fewer variables than their procedures (except for their method GLMpath which select less than 3 variables for all datasets).

Let us notice that the results for the dataset Prostate differ from Section 4.1 to Section 4.2. This difference can mainly be explained by the use of 5-fold cross-validation in Section 4.2. Indeed the fact that n is very small (n = 62) makes the method quite unstable with respect to resampling.

Ozone data

Before ending the paper, let us consider a standard regression dataset. Since it is far from matching the two main characteristics which have guided the algorithm principle , it allows us to check that it still work well. We apply the entire procedure to the easy to interpret ozone dataset (it can be retrieved from the R package mlbench and detailed information can be found in the corresponding description file). It consists of n = 366 observations of the daily maximum one-hour-average ozone together with p = 12 meteorologic explanatory variables. Let us first examine, in Figure 9 the VI obtained with RF procedure using mtry = p/3 = 4 and ntree = 2000. From the left to the right, the 12 explanatory variables are 1-Month, 2-Day of month, 3-Day of week, 5-Pressure height, 6-Wind speed, 7-Humidity, 8-Temperature (Sandburg), 9-Temperature (El Monte), 10-Inversion base height, 11-Pressure gradient, 12-Inversion base temperature, 13-Visibility. Let us mention that the variables are numbered exactly as in mlbench, so the 4th variable is the response one.

Three very sensible groups of variables appear from the most to the least important. First, the two temperatures (8 and 9), the inversion base temperature (12) known to be the best ozone predictors, and the month (1), which is an important predictor since ozone concentration exhibits an heavy seasonal component. A second group of clearly less important meteorological variables: pressure height (5), humidity (7), inversion base height (10), pressure gradient (11) and visibility (13). Finally three unimportant variables: day of month (2), day of week (3) of course and more surprisingly wind speed (6). This last fact is classical: wind enter in the model only when ozone pollution arises, otherwise wind and pollution are weakly correlated (see for example [START_REF] Cheze | Partial and Recombined Estimators for Nonlinear Additive Models[END_REF] highlighting this phenomenon using partial estimators).

Let us now examine the results of the selection procedures. After the first elimination step, the 2 variables of negative importance are canceled, as expected.

Therefore we keep 10 variables for interpretation step and then the model with 7 variables is then selected and it contains all the most important variables: (9 8 12 1 11 7 5).

For the prediction procedure, the model is the same except one more variable is eliminated: humidity (7) .

In addition, when different values for mtry are considered, the most important 4 variables (9 8 12 1) highlighted by the VI index, are selected and appear in the same order. The variable 5 also always appears but another one can appear after of before.

Discussion

Of course, one of the main open issue about random forests is to elucidate from a mathematical point of view its exceptionally attractive performance. In fact, only a small number of references deal with this very difficult challenge and, in addition to bagging theoretical examination by [START_REF] Bühlmann | Analyzing Bagging[END_REF], only purely random forests, a simple version of random forests, is considered. Purely random forests have been introduced by [START_REF] Cutler | Pert -Perfect random tree ensembles[END_REF] for classification problems and then studied by [START_REF] Breiman | Consistency for a simple model of Random Forests[END_REF], but the results are somewhat preliminary. More recently [START_REF] Biau | Consistency of random forests and other averaging classifiers[END_REF] obtained the first well stated consistency type results.

From a practical perspective, surprisingly, this simplified and essentially not data-driven strategy seems to perform well, at least for prediction purpose (see [START_REF] Cutler | Pert -Perfect random tree ensembles[END_REF]) and, of course, can be handled theoretically in a easier way. Nevertheless, it should be interesting to check that the same conclusions hold for variable importance and variable selection tasks.

In addition, it could be interesting to examine some variants of random forests which, at the contrary, try to take into account more information. Let us give for example two ideas. The first is about pruning: why pruning is not used for individual trees? Of course, from the computational point of view the answer is obvious and for prediction performance, averaging eliminate the negative effects of individual overfitting. But from the two other previously mentioned statistical problems, prediction and variable selection, it remains unclear. The second remark is about the random feature selection step. The most widely used version of RF selects randomly mtry input variables according to the discrete uniform distribution. Two variants can be suggested: the first is to select random inputs according to a distribution coming from a preliminary ranking given by a pilot estimator; the second one is to adaptively update this distribution taking profit of the ranking based on the current forest which is then more and more accurate.

Finally, let us mention an application currently in progress for fMRI brain activity classification (see Genuer et al. (2010)). This is a typical situation where n << p, with a lot of highly correlated variables and where the two objectives have to be addressed: find the most activated (whole) regions of the brain, and build a predictive model involving only a few voxels of the brain. An interesting aspect for us will be the feedback given by specialists, needed to interpret the set of variables found by our algorithm. In addition a lot of well known methods have already been used for these data, so fair comparisons will be easy.

Figure 1 Figure 1 :

 11 Figure 1: Variable importance sensitivity to n and p (toys data)

Figure 2 :

 2 Figure 2: Variable importance sensitivity to mtry and ntree (toys data)

Figure 3 :

 3 Figure 3: Variable importance of a group of correlated variables (augmented toys data)

Figure 4 :

 4 Figure 4: Variable importance of two groups of correlated variables (augmented toys data)

Figure 5 :

 5 Figure 5: Variable importance for Prostate data (using ntree = 2000 and mtry = p/3, on the right and using default values on the left)

Figure 6 :

 6 Figure 6: Variable selection procedures for interpretation and prediction for toys data

Figure 7 :

 7 Figure 7: Selecting the threshold for variable elimination using CART. Bold line refers to the CART estimation of the dotted line and the horizontal dashed line indicates the threshold (the bottom graph being a zoom of the top one)

Figure 8 :

 8 Figure 8: Variable selection procedures for interpretation and prediction for Prostate data

Figure 9 :

 9 Figure 9: Variable importance for ozone data

Figure 10 :

 10 Figure 10: Variable selection procedures for interpretation and prediction for ozone data

Table 2 :

 2 Variable selection procedure for four high dimensional real datasets. CV-error rate and into brackets the average number of selected variables dures are of the same order of magnitude as the original error (but a little bit larger).We compare these results with the results obtained by Ben[START_REF] Ishak | Sélection de variables pour la classification binaire en grande dimension : comparaisons et application aux données de biopuces[END_REF] (see tables 9 and 11 in BenIshak et al. (

	Dataset	interpretation prediction original
	Colon	0.16 (35)	0.20 (8)	0.14
	Leukemia	0 (1)	0 (1)	0.02
	Lymphoma	0.08 (77)	0.09 (12)	0.10
	Prostate	0.085 (33)	0.075 (8)	0.07

see http://www.r-project.org/ Preprint submitted to Pattern Recognition Letters September 8,