Aprendizaje supervisado mediante random forests

TRABAJO FIN DE MÁSTER Aprendizaje Supervisado mediante Random Forests Presented by: María Cristina Molero del Río Supervisors: DR. RAFAEL BLANQUERO BRAVO DR. EMILIO CARRIZOSA PRIEGO FACULTAD DE MATEMÁTICAS Departamento de Estadística e Investigación Operativa Sevilla, Junio 2017 Contents Resumen 5 Introduction 7 1 Supervised Classification 9 1.1 Scoringfunctions............................ 9 1.2 Validation techniques and performance criteria . . . . . . . . . . . . 10 1.3 Supervised regression . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2 Classification trees 15 2.1 Getting familiar with classification trees . . . . . . . . . . . . . . . . 16 2.2 Topology and type of splitting . . . . . . . . . . . . . . . . . . . . . 18 2.3 Splittingcriteria............................. 19 2.3.1 Impurity functions . . . . . . . . . . . . . . . . . . . . . . . 22 2.3.1.1 Classification error rate . . . . . . . . . . . . . . . 22 2.3.1.2 Giniindex...................... 22 2.3.1.3 Cross-entropy . . . . . . . . . . . . . . . . . . . . 22 2.3.2 Gainratio............................ 23 2.4 Stoppingcriteria............................. 24 2.5 Labeling terminal nodes . . . . . . . . . . . . . . . . . . . . . . . . 25 2.6 Classification tree step by step . . . . . . . . . . . . . . . . . . . . . 26 2.7 TreePruning .............................. 31 2.8 Regressiontrees............................. 32 3 Ensembling trees: Random Forests 33 3.1 Random forests. Influences and definition. . . . . . . . . . . . . . . . 33 3.1.1 Background........................... 33 3.1.2 Definition............................ 34 3.1.2.1 Parameters tuning . . . . . . . . . . . . . . . . . . 35 3.2 Properties of Random Forests . . . . . . . . . . . . . . . . . . . . . . 37 3.2.1 Variable importance . . . . . . . . . . . . . . . . . . . . . . 37 3.2.1.1 Mean Decrease Accuracy . . . . . . . . . . . . . . 37 3 4 Contents 3.2.1.2 Mean Decrease Impurity . . . . . . . . . . . . . . 39 3.2.2 Proximity measure . . . . . . . . . . . . . . . . . . . . . . . 40 3.2.2.1 Data visualization . . . . . . . . . . . . . . . . . . 41 3.2.2.2 Outliers detection . . . . . . . . . . . . . . . . . . 42 3.2.2.3 Missing values imputation . . . . . . . . . . . . . . 42 3.2.2.4 Prototypes search . . . . . . . . . . . . . . . . . . 43 3.3 Regression Random Forests . . . . . . . . . . . . . . . . . . . . . . . 44 4 Random Forests in R 45 4.1 Random Forests and properties . . . . . . . . . . . . . . . . . . . . . 46 4.2 Feature Selection based on Random Forests . . . . . . . . . . . . . . 52 Bibliography 60 Resumen Muchos problemas de la vida real pueden modelarse como problemas de clasificación, tales como la detección temprana de enfermedades o la concesión de crédito a un cierto individuo. La Clasificación Supervisada [9] se encarga de este tipo de problemas: aprende de una muestra con el objetivo final de inferir observaciones futuras. Hoy en día, existe una amplia gama de técnicas de Clasificación Supervisada. En este trabajo nos centramos en los bosques aleatorios (Random Forests, [4]). El Random Forests es una técnica de clasificación que consiste en construir una colección de árboles de decisión individuales [8] sobre los cuales se aplica aleatoriedad de cierta manera. Es conocido que esta técnica proporciona un buen rendimiento, incluso cuando trata con problemas de gran escala como los que se tienen en la actualidad. Sin embargo, existe una pequeña brecha entre la teoría relacionada con esta técnica y la experiencia empírica de la misma. El Random Forests también es útil en otros campos del Aprendizaje Automático: da medidas de importancia de las variables, que podrían utilizarse en la Selección de Atributos, y una matriz de proximidades entre las observaciones, lo que permite al analista detectar valores atípicos, reemplazar valores perdidos, buscar prototipos y obtener una visualización comprensible de los datos. Estas últimas propiedades hacen que el Random Forests sea una técnica aún más atractiva. En este trabajo se hace, en primer lugar, una breve descripción de la Clasificación Supervisada, incluyendo las principales técnicas de validación y los criterios de rendimiento más relevantes. En segundo lugar, se explica en detalle la construcción de un árbol de clasificación. Seguidamente, se presenta el Random Forests y se revisan las propiedades principales del mismo. Por último, se muestran resultados experimentales en R. 5 Introduction Many problems in the real life can be modelled as classification problems: the early detection of diseases or the granting of credit to a certain individual, among others. Supervised Classification [9] handles this issue by learning from a sample in order to infer forthcoming observations. Nowadays, there exist a wide range of Supervised Classification techniques. Along this work, we will focus on Random Forests classification method [4]. Random forests is a collection of individual decision trees [8] on which randomness is applied somehow. This classification technique is well-known for providing great performance, even with large-scale problems. Nevertheless, there is a little gap between theory and empirical experience in this scheme. Random Forests are also useful for other fields in Machine Learning: they give measures of variables importance, which could be used in Feature Selection, and proximities between observations, which allows the analyst to detect outliers, replace missing values, search prototypes and obtain a comprehensive visualization of the data. These latter properties make Random Forests even more attractive. This work is organised as follows. Chapter 1 introduces to the Supervised Classification, including the most relevant validation techniques and performace criteria. Next, in Chapter 2, the construction of a classification decision tree is addressed in detail. Then, Chapter 3 is enterely devoted to Random Forests. The main properties of Random Forests are reviewed. Last, in Chapter 4, computational experience with Random Forests is reported. The code in Rsoftware is also displayed. 7 Chapter 1 Supervised Classification Supervised Learning is one of the most relevant tasks in Machine Learning and Data Mining. The general idea in Supervised Learning is to infer a function which is known only for some examples, with the final goal of mapping new forthcoming examples. Depending on the range of the inferred function, one can distinguish between Supervised Classification and Supervised Regression. Along this text we will mainly focus on Supervised Classification and briefly survey the regression case. The aim of Supervised Classification is to seek procedures for classifying objects in a set Ωinto a finite set Cof nominal values or classes. Each object uin Ωhas associated a pair (xu, yu), where xu, the predictor vector, takes values on a set X, usually assumed to be a subset of Rp, and yu∈Cis the class membership of the object. Henceforce, each component of the predictor vector and ywill be named predictor and response variables, respectively. The whole information about all the objects in Ωis not available as a rule. Instead, we assume we are given a sample Dn={(x1, y1),...,(xn, yn)}of independent random variables distributed as the independent prototype pair (X, C). The goal is to use the data set Dnto construct a classifier, i.e., an estimate mn:X−→ Cof the function m(x), which gives to each xthe class minimizing the misclassification cost. 1.1 Scoring functions Actually, classifiers are based on scoring functions fc:X→Rbuilt for each class c∈C. These functions are in charge of ranking a forthcoming object: they indicate, in a certain sense, the likelihood that an object represented by xbelongs to each class. In this way, the classifier will be given by the function mn(x)∈arg max c∈Cfc(x)∀x∈X. (1.1) These scoring functions have a particular property: if every fcis replaced by fc+h for a common h, the same classifier mnis obtained. This property is interesting in 9 16 2.1. Getting familiar with classification trees tree-based decision making at the same level as other powerful techniques. In the remainder of this chapter, the goal is to provide an understandable description of the construction of a classification tree, with main focus on the CART model. Finally, we will slightly move on to regression trees. 2.1 Getting familiar with classification trees Prior to formally tackling the construction of a classification tree, some general notions will be provided to readers. The main elements of a tree are presented too. Figure 2.1 depicts an example of a diagram tree for a hypothetical two-class classification problem, C={Positive,Negative}. Figure 2.1: A diagram tree. As it can be seen in Figure 2.1, a classification tree is a classifier that involves the partitioning of Ω, carried out by consecutive and descendant divisions of disjoint subsets of Ω. For instance, t21 and t22 are disjoint and add up the total previous subset, t13 =t21 tt22. Subsets are known as nodes. The root node is the one that appears the highest, representing Ωitself. Non-split subsets, indicated by rectangular boxes, are called Chapter 2. Classification trees 17 terminal nodes and they form a partition of Ω, Ω = t11 tt31 tt32 tt33 tt21 tt22. The rest of nodes are non-terminal nodes. A class label of Cis assigned to each terminal node in such a way that there may be more than one terminal node with the same class label. The way to do this assignment is yet to be defined. Besides nodes, branches are another element of a tree. They indicate the different decision options that can be taken in each split. Splits are due to conditions on the variables in x= (x1, . . . , xp). For example, Split 2 into t21 and t22 could be of the form t21 ={x∈t13 :x2+x4≤3} t22 ={x∈t13 :x2+x4>3}(2.1) or Split 3 into t31,t32 and t33: t31 ={x∈t12 :x5=Blue} t32 ={x∈t12 :x5=Pink} t33 ={x∈t12 :x5=Grey}. In order to predict the class of a given object making use of the classification tree in the Figure 2.1, the procedure is to start by the first split and take the branch containing the condition satisfied by the object. In this way, the object gets to another node from with the same procedure is to be done and repeated until a terminal node is reached. The predicted class for the object will be given by the class label attached to that terminal node. According to this brief introduction to classification trees, it follows that the growth of a tree depends on four basic ingredients: •Topology of the tree and type of splittings. First of all, the topology of the tree is to be chosen, that is, the number of branches allowed in splits. In most cases, trees are assumed to be binary. The kind of conditions on splitting have to be decided too. •Splitting criterion. At each non-terminal node, not any split works. It is necessary to define a splitting criterion from which the selected split makes prediction accuracy improves among the rest. •Stopping criterion. Deciding when to continue splitting or declare a node terminal is another task that should be taken into account. •Classes assignment. Finally, once the terminal nodes have been located, the last step is to assign a class label to each one of these nodes. The essence of the problem is, therefore, how to address these issues to obtain an accurate classifier. This will be discussed in the next sections. 18 2.2. Topology and type of splitting 2.2 Topology and type of splitting The topology or shape of a decision tree comprises, as advanced before, the determination of how many different branches or options there are when a split is carried out to create new nodes. There exist binary splitting and multi-splitting. Let us address separately the cases in agreement with the type of variable under consideration. Recall that working with both, categorical and continuous variables, is feasible in this framework. Let us start with categorical variables. Suppose we depart from a node t. Let xm,1≤m≤p, be a categorical variable, taking values, say, in {b1, . . . , bQ}. For binary splitting, two alternatives are frequently considered. For i= 1, . . . , Q the first alternative is to consider only as possible splits the following subsets: tL={u∈t:xu m=bi} tR={u∈t:xu m6=bi}, denoting tLand tRthe left and right new subsets. Qpossible splits are done in this way. The second alternative is to consider every possible subset of {b1, . . . , bQ}, that is, tL={u∈t:xu m∈S} tR={u∈t:xu m6∈ S}, where Sranges over all subsets of {b1, . . . , bQ}. In this case, since tLand tRgenerate the same subsets with Land Rreversed, 2Q−1−1splits are necessary. For multi-splitting, a new branch per each i,1≤i≤Q, is created, subdividing the current node into ti={u∈t:xu m=bi}.(2.2) Let xm,1≤m≤p, be continuous now, so we have from Dnnreal values of xm. Assuming that these values are in order from lowest to highest, at most n−1 different divisions can be done for binary splitting at most, by separating the lfirst objects, already ordered up to xm, and the remaining n−l, with l= 1, . . . , n −1, i.e.: tL={u∈t:xu m≤cl} tR={u∈t:xu m> cl}(2.3) where the cutpoint clis the halfway between consecutive data values of xm. However, not every divisions must be considered; those splits in which there is not a change of class are dominated by the others. Anyway, the bigger is n, the bigger is the number of potential cutoffs to be taken into consideration, which is time-consuming. In order to reduce the computational burden, continuous variables can be discretized in a previous step. Multi-splitting in continuous variables is not of interest because it has been proved that there is not any advantage in prediction accuracy over binary splitting, [27]. Chapter 2. Classification trees 19 The process explained above is actually applied to univariate splits, that is, splits defined by one single predictor variable. Nevertheless, this consideration can be extended to multivariate splits, splits in which several predictor variables take part, see (2.1). This extension seems to be plausible in terms of accuracy. Linear splits are the most popular multivariate splits. Aside from heuristic algorithms, they can be performed by using Linear Discriminant Analisis or the linear SVM, to name a couple of them. The simplest topology of a decision tree is when treating with univariate splits and binary splittings. This method is known as recursive binary splitting. 2.3 Splitting criteria The problem of building an optimal binary tree is NP-complete. Due to the complexity of this elementary tree, all trees are constructed by a greedy procedure: at each nonterminal node, all possible splits are generated and the best of them at the current step, according to a splitting criterion, is selected. However, this election could not be optimal for future steps. In this section, the splitting criterion par excellence is described. Assuming that the set Sof possible splits is already computed for a particular non-terminal node, the issue is to decide which of them is the best option in order to improve the classifier accuracy. First of all, some definitions and notations are needed. Remind the general framework: we are giving a sample Dn={(x1, y1),...,(xn, yn)}with xi∈Xand yi∈C={C1, . . . , Ck},1≤i≤n. Denote njthe number of observations in Dn that belong to the same class Cj, for 1≤j≤k. Prior class probabilities πjcan be then estimated from the sample as follows πj=nj n. Given a node t, let nj(t)be the number of observations in tthat belong to the same class Cj,1≤j≤k, and n(t)the total numbers of observations that have fallen into node t; the proportion of examples belonging to Cjfixed an arbitrary node tis given by πj(t) = nj(t) n(t).(2.4) Then, an estimation of the probability that an example reaches the node tand belongs to class jcan be deduced: P(Cj, t) = πjπj(t). On another hand, the marginal probability that an observation reaches the node tis 20 2.3. Splitting criteria given by P(t) = k X j=1 P(Cj, t). The probability that an observation belongs to class jgiven that it falls into node tis defined by P(Cj|t) = P(Cj, t) P(t). When πjare estimated using (2.4), one has P(Cj|t) = nj(t) n(t), so these probabilities are the relative proportions of class jin node t. The above definitions will help us to understand the splitting criteria. The way par excellence to select the best split, according to the types introduced in Section 2.2, is to choose the split that best separate the objects in the training sample up to their classes, that is, that produces the maximum reduction in the diversity or impurity of objects associated to resultant nodes. To better see this idea, imagine a four-classes binary tree. The proportions of the classes in the initial node are equal, i.e., P(j|t0= Ω) = 1/4∀j= 1,...,4. A good splitting criterion would be to take the split that leads to two new descendant nodes in which there are only the half of the classes, as shown in Figure 2.2. A quantitative measure of the effectiveness of a split in this sense Figure 2.2: First split of a four-classes binary tree. The frequencies of classes that fall into each node appear next. is obtained by the concept of impurity. Chapter 2. Classification trees 21 Definition 2.3.1 (Impurity function).Let Φ : P−→ Rwhere P=((p1, . . . , pm) : m X j=1 pj= 1, pj≥0, j = 1, . . . , m). Φis an impurity function if it verifies (1) Φreaches its unique maximum at the point (1 m,..., 1 m). (2) Φachieves its minima exclusively at the points (1,0,...,0),(0,1,0,...,0),. . . , (0,...,0,1). (3) Φis a symmetric function of p1, . . . , pm, i.e., if there is a permutation of the variables pj,Φwill remain constant. Definition 2.3.2 (Impurity measure).Let Φbe an impurity function. An impurity measure i(t)of any node tis defined as i(t) = Φ (P(C1|t), . . . , P(Ck|t)) , where P(Cj|t)is the estimated probability of class jwithin node t. In this way, the impurity measure will achieve its maximum when every classes in node tare in the same proportion, and its minimum when there is only one class in node t. Since the fundamental idea is to produce purer nodes, the selection of the split of a parent node will be done in terms of a new concept: the information gain, which measures somehow the purity gained when a node is split into descendant nodes according to a type of splitting. In what follows, this concept is formally defined. Definition 2.3.3 (Information gain).Let s∈Sbe a possible split, let rbe the number of branches considered in the growth of the tree and let ibe an impurity function. The information gain of srelative to node tis defined as the average reduction of impurity obtained by splitting the observations within node tup to s G(t, s) = i(t)− r X j=1 qji(tj),(2.5) where tjis each descendant node originated in the splitting and qjthe proportion of observations (within node t) that become elements from new node tj. By virtue of the above definition, the selected split over the current set of nodes Ωc will be the one that maximizes the corresponding information gain: G(t∗, s∗) = max t∈Ωc,s∈S{G(t, s)}.(2.6) 22 2.3. Splitting criteria It is not hard to see from (2.5) that maximizing the information gain when there is one single node tis equivalent to minimizing the term that is substracted in the formula, i.e., minimizing the weighted average impurity of the possible new descendant nodes of t. Therefore, once an impurity function is chosen, the selection criterion is perfectly defined. 2.3.1 Impurity functions Common impurity functions are introduced now, that is, functions that present the desirable properties listed in Definition 2.3.1. They are: the classification error rate or misclassification rate, the Gini index and the cross-entropy. 2.3.1.1 Classification error rate Given the vector (p1, . . . , pm)∈P, the classification error rate (CER) is defined as Φ(p1, . . . , pm) = 1 −max 1≤j≤m{pj}. In the field of decision trees, the elements pjare assumed to be P(Cj|t)according to Definition 2.3.2, thus, CER would be the fraction of observations in node tthat do not belong to the most common class. It seems that CER has the deficiency of not being sensitive enough for the overall tree-growing procedure. For further details, the reader is refered to [8]. The following impurity functions are preferable instead. 2.3.1.2 Gini index Given the vector (p1, . . . , pm)∈P, the Gini index is defined as Φ(p1, . . . , pm) = m X j=1 pj(1 −pj)=1− m X j=1 p2 j. When pj=P(Cj|t), the Gini index measures the total variance across all the kclasses. By the way this index is defined, it takes smaller values if every pjin node tis close to zero or one. In this sense, node impurity is perfectly measured: a small value will indicate that the node is dominated by a single class. 2.3.1.3 Cross-entropy Given the vector (p1, . . . , pm)∈P, the cross-entropy is defined as Φ(p1, . . . , pm) = − m X j=1 pjlog2(pj) Chapter 2. Classification trees 23 Figure 2.3: Impurity functions for two classes. with the agreement 0 log20=0. The negative sign is due to the p0 js: in this field, they represent probabilities and it follows that log pj<0when 0≤pj≤1. The interpretation with pj=P(Cj|t)is quite similar to the Gini index: if a node is pure, the cross-entropy will take a small value. In fact, the Gini index and the crossentropy are usually alike numerically. Actually, the concept of entropy was first introduced in Information Theory. In this way, it can be seen as the minimum number of information bits needed to encode the classification of any object in a particular node. For instance, Φ (1,0,...,0) = 0 since the given object belongs to C1undoubtedly, with no need for any message or any bit to transmit its information. In Figure 2.3, these three impurity functions are shown for a two-class problem. 2.3.2 Gain ratio In the case of non-binary trees, the information gain is a measure that gives advantage to those variables that have a lot of categories when deciding the splitting. To deal with this problem, alternative measures for the selection of the splitting variable have been proposed. One of them is the gain ratio, which penalizes variables with many categories by means of the information value. 24 2.4. Stopping criteria Definition 2.3.4 (Information value).Let Abe a variable with rpossible categories. Let mj(t)be the number of examples of category jthat fall into node t. Then, the information value Iv(A, t)of Ainto tis defined as IV (A, t) = − r X j=1 mj(t) n(t)log mj(t) n(t).(2.7) The information gain is nothing more than the cross-entropy defined above but, instead of considering the outputs of the classification, the categories of variable Aare now adressed. From the information gain, the gain rate is defined. Definition 2.3.5 (Gain rate).Let tbe a node and Aa particular variable. The gain rate of Ain node tis: GR (A, t) = G(A, t) IV (A, t)(2.8) where Gand IV refer to the information gain and variable, respectively. The gain rate presents an issue: its denominator can be near zero if mj(t)and n(t)are closer to each other for some category. A heuristic rule can be adopted: first, the information gain is computed for each variable candidate to the splitting and then, making use of the same selection rule based on the gain rate (2.6), the splitting is chosen. The only difference is that only those variables whose gain is above average will be considered. 2.4 Stopping criteria In the previous section, the methodology for evaluating the quality of a particular split has been analyzed. The following step is to decide when to declare a node terminal. The process of growing a tree could continue until every node contains one single observation. In this way, there will be one terminal node per observation in the given sample, so each one will be labelled with the class of its corresponding observation. This proposal can present serious deficiencies in practice, ending up in the great problem of Machine Learning: the overfitting. The overfitting is the effect of getting any learning algorithm that has learned too much from the training sample and is not able to generalize and predict new examples, see Figure 2.4. Several criteria that help to avoid overfitting are usually taken. A first criterion is not to split a node tif the maximum information gain that one would obtain by making the split is lower than some pre-set threshold β: max s∈SG(s, t)≤β. Although this rule seems to be quite reasonable, it may not provide satisfactory outcomes: if βis too small, the resulting tree may be too complex and overfit the training Chapter 2. Classification trees 25 Figure 2.4: Overfitting. data; if βincreases, it takes chances of stopping splitting nodes with low maximum information gain, but whose descendant nodes would do suffer splits with a high maximum information gain. Another rule that is also used is the one based on stopping the subdivision of a node if it does not present a minimum number of training examples. 1, 5 or 10 are typical values. Finally, a criterion based on statistic tests exists and it is due to [25]. The idea is to continue splitting until the class distribution of the available observations is independent to the variables in the predictor vector. For categorical variables, one can use the χ2test; for continuous ones, the F−Student test. Actually, an alternative of these rules is done in practice. Instead of stopping the growth of the tree, a very large tree is built and properly pruned later so that the branches that explain worse are eliminated. This process of pruning a tree is developed in Section 2.7. 2.5 Labeling terminal nodes Once terminal nodes are declared by means of a stopping criterion, the class labels assignment is still left. Recall from Section 2.1 that the set of terminal nodes Tinduces a partition of Ω. Let t∈Tbe a terminal node. The assignment rule is A:T→C t7→ arg max Cj nj(t),(2.9) 32 2.8. Regression trees where Φusually denotes the fraction of cases in the training sample that are misclassified, but any impurity function can be used. R(T)is called the resubstitution error of T. So, given a real number α, the total cost Rα(T)of tree T is defined as Rα(T) = R(T) + α|T|.(2.10) The parameter αis the penalty imposed over the complexity (size) of the tree; while small values of αwill originate trees with a huge number of terminal nodes, big values of αwill originate trees with few terminal nodes. The basic idea given in [8] is to select a subtree T(α), with the same root node that Tmax, that minimizes (2.10). 2.8 Regression trees For regression trees, the construction is quite similar. In fact, Sections 2.2 and 2.4 can be applied to the regression case without change. Regarding splitting criteria, the split is selected by minimizing the Residual Sum of Squares (RSS). The residual of each observation is computed as the difference of its value in the response variable and the mean value of all observations in the same node. By last, as expected, the prediction or value associated to each terminal node is usually the mean of the response variable in every training object that has fallen into the same terminal node. Chapter 3 Ensembling trees: Random Forests Random forests (RFs) are a state of the art prediction method. RFs are known for usually providing great predictions and being flexible enough to deal with large-scale problems, even in settings where the number of variables is much larger than the number of observations. Despite being widely used, RFs’ performance is not supported by many theoretical results. There is, therefore, a little gap between theory and empirical experience in this scheme. Even so, along this chapter, the most celebrated theoretical results of RFs will be sketched out. A random forest is a collection of individual decision trees, reviewed in Chapter 2, each of which is constructed by applying randomness twice: first, a training sample is selected randomly for each tree and, secondly, randomness is injected somehow in the split selection process. The term random forest is attributed to Breiman, who first introduced it in [4]. RFs inherit the properties from decision trees, which were named in the introduction of Chapter 2: they give measures of variables importance and proximities between observations, mainly. The extension of these properties to RFs usually makes the conclusions more reliable since a collection of different predictors are now taken into account. In addition to others, these properties are fully discussed afterwards. 3.1 Random forests. Influences and definition. 3.1.1 Background First of all, the road to RFs is introduced to the reader in this first section. Decision trees, discussed in Chapter 2, are known to suffer from high variance. This means that if two decision trees are grown over two disjoint subsamples from the training data, they may lead to quite different results. A general procedure for reducing variance of any learning method is bagging [3], which has already been presented in Chapter 1. The idea of bagging given in Chapter 1 was to give a technique for handling 33 34 3.1. Random forests. Influences and definition. small datasets. In this context, using bagged trees is based on the statistical result outlined in Note 3.1.1. Note 3.1.1. Given Bindependent observations, each with variance σ2, the variance of the mean of these observations is reduced to σ2/B. So, considering a collection of decision trees is translated into a reduction of variance, which directly leads to an increase of prediction accuracy. The random subspace method was also proposed for constructing decision forests [21]. This method aims to reduce correlation between trees by randomizing the predictor variables to use in each individual tree. The next stop to RFs is random split selection [16], which uses bagging with the only difference that at each node, among the kbest potential splits, the final split is chosen in a random way. Breiman emphasizes that the key paper, the one that was really decisive to develop random forests, was [1], in which a random selection of features at each split is done for a particular problem. And this is how the Random Forests grew up [4]. 3.1.2 Definition Random forests share common characteristics with bagging: Bdecision trees are grown over Bbootstrapped training samples and the prediction is the class with majority vote too; but, at each time a split is considered, a random sample of mpredictor variables is chosen randomly among the pinitial predictor variables. Remember from Chapter 1 that the observations not appearing in the bootstrap sample are called OOB observations. At first sight, this randomization of bagged trees seems not to make sense but it helps to “decorrelate” trees. In order to understand how it decorrelates trees we will use the explanation given in [24], which is quite simple. Consider a dataset that contains a very strong predictor variable together with other moderately strong predictor variables. Then, although the number of decision trees is large, most of them will locate the strong predictor variable in the top split. In consequence, every decision tree will look quite similar to each other, and predictions in all the trees will be highly correlated. This fact would imply that the reduction in variance will not be as important as expected. Definition 3.1.1 (Random forests’ prediction).Let {mn(X, θb)}1≤b≤Bbe a family of Bindividual decision trees, built as in Algorithm 2. Given an unlabeled observation x, its predicted class using RFs is mn(x, θ1, . . . , θB) = arg max Cj B X b=1 I{mn(x,θb)=Cj}, where I(·)is the indicator function. Chapter 3. Ensembling trees: Random Forests 35 Algorithm 2: RF’s construction. Input: inputs in Algorithm 1, the number of trees Band the number of predictor variables to select randomly at each split p. for b∈ {1, . . . , B}do Generate a bootstrap sample of Dn,Dn(θb). Store the OOB observations in Dn(θb). Construct an individual decision tree according to Algorithm 1 over Dn(θb). Compute the bootstrap error for the tree, i.e., eboot(b) = P(x,y)∈Dn(θb)I{mn(x;θb)6=y} |Dn(θb)|. end Obtain the bootstrap error by averaging over all the trees, i.e., eboot =1 B B X b=1 eboot(b). Output: The collection of individual decision trees for RFs, {mn(X, θb)}1≤b≤B, and the bootstrap error, eboot. 3.1.2.1 Parameters tuning Research in parameters tuning is scarce in RFs. Article [15] handles these issues. The first parameter is the size of the forest, that is, the number Bof individual decision trees to be grown. Breiman [4] introduces an interesting result for B: RFs do not overfit as larger Bis, but yield a limiting value of the generalization error. Theorem 3.1.1 picks up this result. Two previous definitions are needed. Definition 3.1.2 (Margin function).Let {mn(X, θb)}1≤b≤Bbe a family of Bindividual decision trees. The margin function mg(·)is defined as mg(X, Y ) = 1 B B X b=1 I{mn(X,θb)=Y}!−max j6=Y 1 B B X b=1 I{mn(X,θb)6=j}! where I(·)is the indicator function. According to Definition 3.1.2, the margin function measures how much (in frequency) objects correctly classified exceed objects misclassified in any other class. Thus, the larger this margin function is, the more confidence in the prediction. 36 3.1. Random forests. Influences and definition. Definition 3.1.3 (Generalization error).The generalization error of a random forest is defined as the probability that the margin function is negative, i.e.: PE∗=P(X,Y )[mg(X, Y )<0] . Theorem 3.1.1. The generalization error PE∗converges almost surely to P(X,Y )Pθ(mn(X, θ) = Y)−max j6=Y(mn(X, θ) = j)<0. The proof of Theorem 3.1.1 follows directly from the Strong Law of Large Numbers and it can be found in [4]. Actually, this result can be extended to any ensemble of classifiers. One consequence of Theorem 3.1.1 is that one does not require to compute a very large number of decision trees, since, from a value B∗on, the predictive power of the model will stay the same. In this context, Latinne el al. propose in [28] an approach for determining a priori the number Bin order to obtain an accuracy similar to the one obtained with a larger B. This approach is based on a non-parametric test, the McNemar test [29]. Given two random forests RFmand RFnof size mand n, respectively, the McNemar test compares the number of examples misclassified by RFmbut not by RFn(labeled Mmn) and the number of examples misclassified by RFnbut not by RFm(labeled Mnm), i.e., informally, the test is H0:There is no difference between RF0 nand RF0 mpredictions. There are three possible answers when computing the McNemar test: to reject H0with Mmn > Mnm, in this case the conclusion is that combining ndecision trees yields a significant improvement in performance than combining mdecision trees, and the procedure should carry on with a Blarger than m; to reject H0with Mnm > Mmn, here the procedure must stop and use B=m; or not to have significant evidence for rejecting H0, which means that there is not significant difference between growing n or mdecicion trees, so the final decision must be to construct the minimum classifiers as possible: B=m. Experimental results in [28] show that Bcan be limited significantly. Nevertheless, authors in general, included [15], believe that the parameter B is irrelevant and opt not to tune it, as long as they take it large enough for getting the stability (Breiman [6] proposes B= 1000 or B= 5000) but for computations to be completed within a reasonable time. The second parameter is m, the number of predictor variables taking part in each split. Breiman in [5] found m=d√peto be a good choice since he obtained generally near optimum results. His advice is to grow three random forests with m=d√pe, m= 2d√peand m=1 2d√pe, respectively, and observe the one that performs the best and move around that value. Breiman also points out that a higher mworks better when noise predictor variables are present. In [15], they conclude, again, that tuning this parameter is not an interesting task. Chapter 3. Ensembling trees: Random Forests 37 Aside from choosing Band m, the elements of each tree have to be decided, that is, the topology of the trees, the types of splitting, the splitting criterion, the stopping criterion and if they are pruned trees or not. So far, the proposed RFs’ are collections of unpruned trees. The elements named are the ones that differentiate between trees. For instance, Breiman’s original forest uses CARTs: unpruned trees with univariate splits, binary splitting, the information gain as a splitting criterion and the nodesize criterion. In the Rpackage randomForest,1is set as a default value of nodesize, and 5 for regression. These values are reported to be a good choice in [15]. 3.2 Properties of Random Forests During the construction of the individual trees the OOB observations can be used to measure the performance of the forest without requering an independent validation set (as we could appreciate in Algorithm 2), as well as obtaining some information about the data. Also, the output of the individual trees give us some interesting information. Hereafter, the main properties of RFs are being reviewed. 3.2.1 Variable importance RFs provide variable importance measures, making them very interesting since a hierarchy of the predictor variables can be obtained from the model, that is, it can be measured how related each predictor variable is to the response variable. Moreover, these measures help with another appealing task in Machine Learning: Feature Selection. Feature Selection is the process of discarding irrelevant or redundant predictor variables, without losing power in prediction. In this way, the robustness of the classifier may be improved and computing time will be reduced. Two embedded methods for measuring variable importance are described: the Mean Decrease Accuracy (MDA, [4]) and the Mean Decrease Impurity (MDI, [5]). They are called embedded because they are specific for RFs and are computed during the training process. Note 3.2.1. Breiman [5] proposed to grow more than the usual number of trees if one searches for some auxiliary information like variable importance measures or proximities (which will be seen later), to make these measures stable. In [15], Breiman’s thesis is supported experimentally: as Bgrows, the variable importance measures start to be stable. 3.2.1.1 Mean Decrease Accuracy The Mean Decrease Accuracy (MDA, [4]), also known as the permutation importance measure, is one of the most common variable importance measures. MDA is based on the following principle: if a variable is not influential in the model, rearranging the 38 3.2. Properties of Random Forests values it takes should not degrade prediction accuracy. If the predictor variable brings nothing but random noise, the prediction accuracy will like not to be affected after the permutation. OOB observations will be the main characters in MDA. Every time an individual tree is grown over a bootstrap sample, accuracy in OOB observations is going to be computed. Also, accuracy in OOB observations after permuting the values of some variable will be computed. The MDA of that variable is obtained by averaging over all trees the differences of both accuracies. See Algorithm 3. Algorithm 3: Computing MDA. Input: inputs in Algorithm 2. for b∈ {1, . . . , B}do Generate a bootstrap sample of Dn,Dn(θb). Store the OOB observations in Dn(θb). Construct an individual decision tree according to Algorithm 2 over Dn(θb). Compute the number of correctly classified samples in Dn(θb),i.e., Accb=X (x,y)∈Dn(θb) I{mn(x;θb)=y}. for j∈ {1, . . . , p}do Permute randomly the values that predictor variable jtakes on the set Dn(θb), yielding a sample Dn(θb)j. Compute the number of correctly classified samples in Dn(θb)j,i.e., Accjb =X (x,y)∈Dn(θb)j I{mn(x;θb)=y}. Compute difjb =Accb−Accjb. end end for j∈ {1, . . . , p}do MDA(X(j)) = 1 B B X b=1 difjb. end Output: Mean Decrease Accuracy (MDA) for each predictor variable. Therefore, the larger the MDA, the better the associated predictor variable. Note 3.2.2. If permutations are done over OOB observations in the same class, a measure of variable importance over each class is obtained. Chapter 3. Ensembling trees: Random Forests 39 3.2.1.2 Mean Decrease Impurity Another way for ranking predictor variables is Mean Decrease Impurity (MDI, [5]). Recall that the splitting criterion used for growing a decision tree, extensively explained in Section 2.3, was to select among every non-terminal node that split that maximizes the information gain. This means that if a variable appears in a given node is because, among the other mpreselected variables, it is the one that best separates between classes. As a result, the MDI is based on that idea: given a predictor variable Xj, its corresponging MDI is obtained by averaging over all the trees in the forest the decrease of impurity (or, equivalently, information gain in our language) corresponding to splits along that variable, which is weighted with the fraction of examples falling in that node. As we can see, here the OOB observations do not take part, only the bootstrapped training samples are used. See Algorithm 4. When the impurity function is the Gini index, this measure is commonly called Gini importance. Algorithm 4: Computing MDI. Input: inputs in Algorithm 2. for b∈ {1, . . . , B}do Generate a bootstrap sample of Dn,Dn(θb). Construct an individual decision tree according to Algorithm 2 over Dn(θb). Initialize WIG as the null vector of dimension p. for j∈ {1, . . . , p}do for t∈ {1, . . . , number.of.non.terminal.nodes}do if jpartitions node tthen WIG(Xj) = WIG(Xj) + Nt NIG(t, s) end end end end for j∈ {1, . . . , p}do MDI(Xj) = 1 B B X b=1 WIG(Xj). end Output: Mean Decrease Impurity (MDI) for each predictor variable. Note 3.2.3. The importance of a predictor variable is usually given by its relative influence, which is simply the fraction of its importance measure over the sum of the 40 3.2. Properties of Random Forests importance measures of all variables: RIM(Xj) = IM(Xj) Pp i=1 IM(Xi), where RIM is the abbreviation of Relative Importance Measure, IM is the Importance Measure that can be any of MDA and MDI and Xjrefers to the j-th predictor variable. 3.2.2 Proximity measure A proximity measure quantifies the similarity or dissimilarity of pairs of objects. RFs give a novel and embedded way to obtain a similarity measure between objects. The standard proximity measure was proposed by Breiman [5] and is computed as follows. Let iand jbe two objects, the similarity measure between both, δij, is the proportion of trees that the RF places both in the same terminal node. Starting with δij = 0, object iand object jare applied down each tree and, each time they end up in the same terminal node, δij is increased by one. Finally, this measure is normalized by the number of trees B. Usually, this proximity measure is calculated while the construction of RF taking use of the OOB observations. Now, it is not normalized by Bbut by the number of trees where each pair of OOB observations concur. Proximities are represented by an object-by-object matrix, ∆=(δij), which is symmetric. Every δij takes values on the closed interval [0,1].δij near to one means that objects iand jare alike; so, the main diagonal only contains ones since any object is trivially similar (equal) to itself. As consequence, the closer δij is to zero, the more dissimilar objects iand jare. Recall that Breiman in [4] and authors in [15] find it necessary to take a large number of trees to get stable estimates of data proximity. In [18], a new proximity measure when few trees are grown is proposed: δij =1 BX b∈B 1 ew·gijb , where gijb is the number of branches between the two terminal nodes where iand j have fallen in tree b, and wis an arbitrary parameter that controls the influence of the distance between both terminal nodes. To know how gworks, go to Figure 2.1 and check that gt11,t21,1= 3. In this way, given a tree b, if iand jend up in the same terminal node, gi,j,b = 0 and δij will be increased by one as in the original proximity measure. In addition to give a different proximity measure using RFs, in [18] an approach for assessing the quality of data proximity matrices is proposed: to use them as kernel matrices in a Support Vector Machine (SVM) classifier. The best data proximity matrix will be the one that gives the highest classification accuracy. Both proximity measures, Chapter 3. Ensembling trees: Random Forests 41 the standard and the new ones, are compared thereby. An SVM based on the radial basis function kernel is also used. Experimental results across four data sets show that the proposed measure improves the data proximity estimate, especially when RFs are made of a small number of trees. Furthermore, an SVM exploiting the suggested proximity matrix kernel has been able to outperform an SVM based on the standard radial basis function kernel in many cases. A data proximity matrix is an important information source from which RFs can take sides for many relevant tasks in data mining: data visualization via scaling, outlier detection, missing values imputation and prototypes search; some of them specific for RFs’ similarities and others, more general. A review of how the proximity matrix obtained with RF can be applied to these fields is done next, [7]. 3.2.2.1 Data visualization Data visualization includes every technique that helps to uncover hidden patterns in data by means of pictures. In order to provide a visual representation of the pattern of proximities, RF’s similarity measure in our case, the classical approach used for this is MultiDimensional Scaling (MDS, [13]). MDS is similar to Principal Component Analysis (PCA) with the main difference that PCA uses as input the correlation matrix and MDS, any proximity matrix (dissimilarity matrices, generally). The RF’s dissimilarity matrix is defined as ¯ ∆ = (¯ δij), where ¯ δij =p1−δij. Without going into much detail, the main idea of the MDS is, given ¯ ∆, to construct nvectors, v1, . . . , vn∈Rm, as many as observations in the sample, such that kvi− vjk ≃ ¯ δij ∀i, j = 1, . . . , n, where k·kis an arbitrary norm. When this norm is the Euclidean one, the MDS is known as the Classical MDS (CMDS). In other words, if we are dealing with CMDS, for instance, the method returns a set of points in a low dimensional Euclidean space such that the Euclidean distances between the points are preserved. The mnew coordenates are ordered in the sense that for i<j, the i-th coordenate explains more about the proximity of data than the j-th coordenate, ∀i, j = 1, . . . , m. For this reason, the first two coordinates of all new points v1, . . . , vnare usually projected down into the two dimensional plane and if points of different classes are also coloured differently, an overview of how separated the classes are can be observed. In this way, this picture would allow analysts to decide if the model explains the response variable properly or, by contrast, the information obtained is confusing. The way of interpreting this graph is: the closer the distance between points, the closer the similarity between their corresponding objects. In Chapter 2 of [13], a practical algorithm for the CMDS and its theoretical development can be found. 48 4.1. Random Forests and properties ## Sepal.Length 8.916362 10.098419 12.051028 ## Sepal.Width 6.624870 1.037431 8.454989 ## Petal.Length 30.762171 46.828426 39.621372 ## Petal.Width 32.085780 46.794090 44.675201 ## MeanDecreaseAccuracy MeanDecreaseGini ## Sepal.Length 15.506218 9.976061 ## Sepal.Width 8.264094 2.454234 ## Petal.Length 46.363973 42.803821 ## Petal.Width 47.402607 44.058583 The previous table shows the measures of importance of each variable. Let us see it graphically. varImpPlot(iris.rf) Sepal.Width Sepal.Length Petal.Length Petal.Width 10 20 30 40 MeanDecreaseAccuracy Sepal.Width Sepal.Length Petal.Length Petal.Width 0 10 20 30 40 MeanDecreaseGini iris.rf Both measures of variable importance reviewed are represented in the picture above: on the left side, the MDA; on the right side, the MDI using the Gini index as the impurity function. On this occasion, there is no discrepancy between both measures since they point out that the predictor variables Petal.Width and Petal.Length are the most important. Next, following the same order than in Section 3.2, let us obtain the standard proximity matrix. Again, the same forest is built, now adding proximity = TRUE. set.seed(1349187) iris.rf = randomForest(Species∼., data=iris, ntree=1000, mtry=2,proximity=TRUE) A matrix of dimension 150 by 150 is obtained. Let us see, for example, the measure of proximity for the first five observations, which correspond to flowers of the species Setosa. Chapter 4. Random Forests in R 49 iris.rf$proximity[1:5,1:5] ## 12345 ## 1 1.0000000 0.9683544 0.9931973 0.9930070 1.0000000 ## 2 0.9683544 1.0000000 0.9877301 0.9790210 0.9791667 ## 3 0.9931973 0.9877301 1.0000000 1.0000000 0.9925373 ## 4 0.9930070 0.9790210 1.0000000 1.0000000 0.9913043 ## 5 1.0000000 0.9791667 0.9925373 0.9913043 1.0000000 It is observed that the first five cases are closely related. Also, remember that they are part of the species that our model classifies best. From now on, we exploit the ability of the proximity matrix. Data visualization MDSplot(iris.rf,iris$Species,pch=19,cex=1.1, palette=c(3,5,6),main="Multidimensional Scaling") legend(-0.55,0.44,col=c(3,5,6),pch=19, legend=levels(iris$Species),cex=1.1) −0.6 −0.4 −0.2 0.0 0.2 −0.4 −0.2 0.0 0.2 0.4 Multidimensional Scaling Dim 1 Dim 2 setosa versicolor virginica This graph shows that the Setosa species is clearly distinguished from the other two species, as the confusion matrix advanced. 50 4.1. Random Forests and properties Outliers detection out_measure = outlier(iris.rf) plot(out_measure,type="h",col=c("green","red","blue"), [as.numeric(iris$Species)]) 0 50 100 150 0 50 100 200 300 Index out_measure The species Setosa does not present huge levels of outlyingness, compared to species Versicolor and the Virginica, being the latter the one with more outliers. Missing values imputation Iris database does not present missing values; however, we will do an experiment in order to see how good the imputation method provided by random forests is when replacing missing values. Suppose we do not know the values of the variable Sepal.Length of flowers 1(Setosa), 51 (Versicolor) and 101 (Virginica). The algorithm of imputation of lost values will be applied and, later, the difference between the predicted and the real values of the predictor variable Sepal.Length for the three flowers is going to be computed. iris.na = iris iris.na[1,"Sepal.Length"]=NA iris.na[51,"Sepal.Length"]=NA iris.na[101,"Sepal.Length"]=NA set.seed(1349187) iris.imputed = rfImpute(Species∼., iris.na) Chapter 4. Random Forests in R 51 (dif1 = iris.imputed[1,"Sepal.Length"] -iris[1,"Sepal.Length"]) ## [1] -0.1046023 (dif51 = iris.imputed[51,"Sepal.Length"] -iris[51,"Sepal.Length"]) ## [1] -1.125318 (dif101 = iris.imputed[101,"Sepal.Length"] -iris[101,"Sepal.Length"]) ## [1] 0.4308188 Except for the flower 51, the method has a proper performance. Prototypes search Last, a representative instance for each species is being computed. x = iris[,names(iris)!="Species"] label =iris$Species (iris.prot=classCenter(x,label,iris.rf$proximity)) ## Sepal.Length Sepal.Width Petal.Length ## setosa 5.0 3.4 1.5 ## versicolor 5.8 2.8 4.3 ## virginica 6.5 3.0 5.6 ## Petal.Width ## 0.20 ## 1.30 ## 2.05 For every species, the previous table shows the medioid, i.e., the instance that best represents its class. We will represent the prototypes together with the observations over the predictor variables related to the petals. 52 4.2. Feature Selection based on Random Forests 1 2 3 4 5 6 7 0.5 1.0 1.5 2.0 2.5 Observations and prototypes Petal.Length Petal.Width setosa versicolor virginica 4.2 Feature Selection based on Random Forests RFs provide two measures of variable importance: the MDA and the MDI, previously reviewed in Subsection 3.2.1. In this section, the purpose is to use these measures as Feature Selection techniques and investigate their performance. Given a data set, the idea is to train different classifiers with different techniques of Feature Selection in the current literature (including those for RFs’ variable importance measures) and check which technique performs best in terms of the accuracy over a test set, totally independent from the training set. The technique that gives the highest accuracy over the whole set of classifiers will be considered as the best. Remember from Chapter 1 that the accuracy is defined as the proportion of observations correctly classified by a given classifier. The package randomForest will be used for computing MDA and MDI. The other techniques will be taken from the package FSelector, which contains some functions for selecting attributes from a given dataset. Among them, the functions cfs,chi.squared,oneR,relief and consistency are used. While the techniques cfs and consistency give a subset of predictor variables to consider, the techniques chi.squared, oneR and relief perform similar to MDA and MDI: their outcoming is a ranking of the predictor variables, so the size of the subset of predictor variables is to be chosen. In this study, around the 25% of the whole set of predictor variables is taken. The classifiers to be used in this study are: Naive Bayes (NB), Radial Basis Function (RBF) SVM and of course Random Forests (RF). Chapter 4. Random Forests in R 53 An outline of the experiment can be seen in Algorithm 7. Algorithm 7: Comparison of Feature Selection techniques. Given a data set: Step 1. Split the sample into a training sample (70%) and a test sample (30%). Step 2. Obtain the subset of predictor variables considered for every Feature Selection technique using the training sample. Step 3. • Train the different classifiers making their corresponding parameters tuning for every subset of predictor variables obtained in Step 2. The training sample is used. • Measure the performance (accuracy) over the test sample of every pair Feature Selection technique - Classifier. Step 4. Get conclusions. Three different data sets are used for this task: Breast Cancer Wisconsin, Ionosphere and Spam data sets: • Breast Cancer Wisconsin, which consists of a sample of size 569 on which 30 continuous features are computed from a digitized image of a fine needle aspirate (FNA) of a breast mass. They describe characteristics of the cell nuclei present in the image. Moreover, there is a variable that identifies every observation, which is out of the study, and the response variable malignant that takes the value 1if the cell is malignant and 0, otherwise. • Ionosphere, which comprises 351 observations (electrons in the ionosphere) on which 35 variables were measured. The first 34 variables are predictor and continuous, except two of them that have been removed from the study; the last one is the response variable and takes good if returns are those showing evidence of some type of structure in the ionosphere and bad, if returns are those that do not; their signals pass through the ionosphere. • Spam, which contains a sample of 4601 e-mails spam and non-spam so the response variable takes one of these values. In addition to this class label there are 57 predictor variables indicating the frequency of certain words and characters in the e-mail. The code used in R for the Spam dataset will be displayed next. For Breast Cancer Wisconsin and Ionosphere data sets, the procedure is the same. First, the data set Spam is loaded from the library kernlab. During the experiment, when dealing with randomness, seeds are going to be set in order to make the results reproducible at any code line. 54 4.2. Feature Selection based on Random Forests library(kernlab) data(spam) Step 1 set.seed(123) n <- nrow(spam) trainindex <- sample(1:n, size = floor(0.7*n)) spam.train <- spam[trainindex,] spam.test <- spam[-trainindex,] Step 2 At the same time each subset of predictor variables is obtained for a given Feature Selection technique, the training and the test samples for that restricted set of predictor variables are going to be stored. MDA and MDI The way of obtaining both variable importance measures provided by RF is based on Breiman’s advice: Bis taken large enough in order to get stable measures, B= 5000, and mis tuned between m1=d√pe,m2=1 2d√peand m3= 2d√pe. The chosen value of mwill be the one that give the low error rate in the OOB observations. For the MDI, the Gini index is taken as the impurity function. library(randomForest) p <- ncol(spam)-1 m1 <- round(sqrt(p)) m2 <- 0.5*m1 m3 <- 2*m1 set.seed(123) RFm1 <- randomForest(type∼., data=spam.train, ntree=5000, mtry=m1) print(RFm1) ## ## Call: ## randomForest(formula = type ~ ., data = spam.train, ## ntree = 5000, mtry = m1) ## Type of random forest: classification Chapter 4. Random Forests in R 55 ## Number of trees: 5000 ## No. of variables tried at each split: 8 ## ## OOB estimate of error rate: 4.63% ## Confusion matrix: ## nonspam spam class.error ## nonspam 1897 60 0.03065917 ## spam 89 1174 0.07046714 set.seed(123) RFm2 <- randomForest(type∼., data=spam.train, ntree=5000, mtry=m2) print(RFm2) ## ## Call: ## randomForest(formula = type ~ ., data = spam.train, ## ntree = 5000, mtry = m2) ## Type of random forest: classification ## Number of trees: 5000 ## No. of variables tried at each split: 4 ## ## OOB estimate of error rate: 5% ## Confusion matrix: ## nonspam spam class.error ## nonspam 1899 58 0.02963720 ## spam 103 1160 0.08155186 set.seed(123) RFm3 <- randomForest(type∼., data=spam.train, ntree=5000, mtry=m3) print(RFm3) ## ## Call: ## randomForest(formula = type ~ ., data = spam.train, ## ntree = 5000, mtry = m3) ## Type of random forest: classification ## Number of trees: 5000 ## No. of variables tried at each split: 16 ## ## OOB estimate of error rate: 4.88% 56 4.2. Feature Selection based on Random Forests ## Confusion matrix: ## nonspam spam class.error ## nonspam 1892 65 0.03321410 ## spam 92 1171 0.07284244 According to the results, m=m1: set.seed(123) RF <- randomForest(type∼., data=spam.train, ntree=5000, mtry=m1, importance=TRUE) names <- colnames(spam) size <- ceiling(0.25*p) subsetMDA <- names[order(RF$importance[,"MeanDecreaseAccuracy"], decreasing = TRUE)][1:size] trainMDA <- spam.train[,c(subsetMDA,"type")] testMDA <- spam.test[,c(subsetMDA,"type")] subsetMDGini <- names[order(RF$importance[,"MeanDecreaseGini"], decreasing = TRUE)][1:size] trainMDGini <- spam.train[,c(subsetMDGini,"type")] testMDGini <- spam.test[,c(subsetMDGini,"type")] Now, from FSelector package. library(FSelector) library(RWeka) CFS subsetCFS <- cfs(type∼., spam.train) trainCFS <- spam.train[,c(subsetCFS,"type")] testCFS <- spam.test[,c(subsetCFS,"type")] chi.squared weightsChi <- chi.squared(type∼.,spam.train) subsetChi <- cutoff.k(weightsChi, size) trainChi <- spam.train[,c(subsetChi,"type")] testChi <- spam.test[,c(subsetChi,"type")] oneR Chapter 4. Random Forests in R 57 weightsOneR <- oneR(type∼.,spam.train) subsetOneR <- cutoff.k(weightsOneR,size) trainoneR <- spam.train[,c(subsetoneR,"type")] testoneR <- spam.test[,c(subsetoneR,"type")] relief weightsRelief <- relief(type ., spam.train, neighbours.count = 5,sample.size = 20) subsetRelief <- cutoff.k(weightsRelief, size) trainrelief <- spam.train[,c(subsetrelief,"type")] testrelief <- spam.test[,c(subsetrelief,"type")] Consistency subsetConsistency <- consistency(type∼., spam.train) trainConsistency <- spam.train[,c(subsetConsistency,"type")] testConsistency <- spam.test[,c(subsetConsistency,"type")] Step 3 In this step every classifier has to be trained with the training sample of each Feature Selection technique and, then, be evaluated over their corresponding test sample. Here, the pairs NB-MDA, RBF SVM-MDA and RF-MDA are displayed. Nonetheless, all the pairs have been computed and are shown in Table 4.1. NB NB does not require any tuning procedure, which speeds up the experiment. library(e1071) NBMDA <- naiveBayes(type∼.,data = trainMDA) preditestNBMDA <- predict(NBMDA,testMDA[,-ncol(trainMDA)]) confutestNBMDA <- table(testMDA[,ncol(trainMDA)], preditestNBMDA) (NBMDAaccuracy <- 100*(confutestNBMDA[1,1]+ confutestNBMDA[2,2])/sum(confutestNBMDA)) ## [1] 82.26 RBF SVM The RBF SVM has two parameters to tune. The same parameters grid has been made for all cases and the pair of parameters that give the best performance is chosen.