Random Forest
Random forest is an ensemble tool which takes a subset of observations(rows) and subset of variables(columns) to build decision trees
GETTING THEROTICAL
To classify a new object from an input vector, put the input vector down each of the trees in the forest. Each tree gives a classification, and we say the tree "votes" for that class. The forest chooses the classification having the most votes
Each tree is grown as follows:
If the number of cases in the training set is N, sample N cases at random - but with replacement, from the original data. This sample will be the training set for growing the tree.
If there are M input variables, a number m<<M is specified such that at each node, m variables are selected at random out of the M and the best split on these m is used to split the node. The value of m is held constant during the forest growing.
Each tree is grown to the largest extent possible. There is no pruning.
The forest error rate depends on two things:
The correlation between any two trees in the forest. Increasing the correlation increases the forest error rate.
The strength of each individual tree in the forest. A tree with a low error rate is a strong classifier. Increasing the strength of the individual trees decreases the forest error rate.
Reducing m reduces both the correlation and the strength. Less m, means the tree has less variables to choose from, and the chances of having the same variables between two trees is very less. More m, means the tree has a wide spectrum of variables to choose from, and the chances of correlation between two trees is very high. Meanwhile, reducing m decreases the tree strength, which increases the error rate, and makes it a weak classifier. Therefore, strength and correlation are inversely proportional to each other Somewhere in between is an "optimal" range of m - usually quite wide. Using the oob error rate a value of m in the range can quickly be found. This is the only adjustable parameter to which random forests is somewhat sensitive.
Features of Random Forests
It runs efficiently on large data bases.
It can handle thousands of input variables without variable deletion.
It gives estimates of what variables are important in the classification.
It generates an internal unbiased estimate of the generalization error as the forest building progresses.
It has an effective method for estimating missing data and maintains accuracy when a large proportion of the data are missing.
It has methods for balancing error in class population unbalanced data sets.
It computes proximities between pairs of cases that can be used in clustering, locating outliers, or (by scaling) give interesting views of the data.
The capabilities of the above can be extended to unlabeled data, leading to unsupervised clustering, data views and outlier detection.
When the training set for the current tree is drawn by sampling with replacement, about one-third of the cases are left out of the sample. This oob (out-of-bag) data is used to get a running unbiased estimate of the classification error as trees are added to the forest. It is also used to get estimates of variable importance.
After each tree is built, all of the data are run down the tree, and proximities are computed for each pair of cases. If two cases occupy the same terminal node, their proximity is increased by one. At the end of the run, the proximities are normalized by dividing by the number of trees. Proximities are used in replacing missing data, locating outliers, and producing illuminating low-dimensional views of the data.
The out-of-bag (oob) error estimate
In random forests, there is no need for cross-validation or a separate test set to get an unbiased estimate of the test set error. It is estimated internally, during the run, as follows:
Each tree is constructed using a different bootstrap sample from the original data. About one-third of the cases are left out of the bootstrap sample and not used in the construction of the kth tree.
Put each case left out in the construction of the kth tree down the kth tree to get a classification. In this way, a test set classification is obtained for each case in about one-third of the trees. At the end of the run, take j to be the class that got most of the votes every time case n was oob. The proportion of times that j is not equal to the true class of n averaged over all cases(where case was n) is the oob error estimate. This has proven to be unbiased in many tests.
Variable importance
In every tree grown in the forest, put down the oob cases and count the number of votes cast for the correct class. Now randomly permute the values of variable m in the oob cases and put these cases down the tree. Subtract the number of votes for the correct class in the variable-m-permuted oob data from the number of votes for the correct class in the untouched oob data. The average of this number over all trees in the forest is the raw importance score for variable m. Here, correct class in variable-m permuted oob data are the classes which are predicted correctly independent of the variable,m. Therefore, subtracting that from the total correct class in untouched data gives us the number of cases where correct class was predicted because of variable m
If the values of this score from tree to tree are independent, then the standard error can be computed by a standard computation. The correlations of these scores between trees have been computed for a number of data sets and proved to be quite low, therefore we compute standard errors in the classical way, divide the raw score by its standard error to get a z-score, and assign a significance level to the z-score assuming normality.
If the number of variables is very large, forests can be run once with all the variables, then run again using only the most important variables from the first run.
Gini importance
Every time a split of a node is made on variable m the gini impurity criterion for the two descendent nodes is less than the parent node. Adding up the gini decreases for each individual variable over all trees in the forest gives a fast variable importance that is often very consistent with the permutation importance measure.
Interactions
The operating definition of interaction used is that variables m and k interact if a split on one variable, say m, in a tree makes a split on k either systematically less possible or more possible. The implementation used is based on the gini values g(m) for each tree in the forest. These are ranked for each tree and for each two variables, the absolute difference of their ranks are averaged over all trees. This number is also computed under the hypothesis that the two variables are independent of each other and the latter subtracted from the former. A large positive number implies that a split on one variable inhibits a split on the other and conversely.
Proximities
These are one of the most useful tools in random forests. The proximities originally formed a NxN matrix. After a tree is grown, put all of the data, both training and oob, down the tree. If cases k and n are in the same terminal node increase their proximity by one. At the end, normalize the proximities by dividing by the number of trees.
Prototypes
Prototypes are a way of getting a picture of how the variables relate to the classification. For the jth class, we find the case that has the largest number of class j cases among its k nearest neighbors (basically a cluster of cases based on class j), determined using the proximities. Among these k cases we find the median, 25th percentile, and 75th percentile for each variable. The medians are the prototype for class j and the quartiles give an estimate of is stability. For the second prototype, we repeat the procedure but only consider cases that are not among the original k, and so on.
Missing value replacement for the training set
Random forests has two ways of replacing missing values. The first way is fast. If the mth variable is not categorical, the method computes the median of all values of this variable in class j(filter all cases based on class j, filter based on variable m, and compute the median with the values), then it uses this value to replace all missing values of the mth variable in class j. If the mth variable is categorical, the replacement is the most frequent non-missing value in class j. These replacement values are called fills.
The second way of replacing missing values is computationally more expensive but has given better performance than the first, even with large amounts of missing data. It replaces missing values only in the training set. It begins by doing a rough and inaccurate filling in of the missing values. Then it does a forest run and computes proximities.
If x(m,n) i.e, mth variable, nth case is a missing continuous value, estimate its fill as an average over the non-missing values of the mth variables(of all cases in the training set) weighted by the proximities between the nth case and the non-missing value case. If it is a missing categorical variable, replace it by the most frequent non-missing value in the training set, where frequency is weighted by proximity.
Now iterate-construct a forest again using these newly filled in values, find new fills and iterate again. Our experience is that 4-6 iterations are enough.
Missing value replacement for the test set
When there is a test set, there are two different methods of replacement depending on whether labels exist for the test set.
If they do, then the fills derived from the training set are used as replacements. If labels no not exist, then each case in the test set is replicated nclass times (nclass= number of classes). The first replicate of a case is assumed to be class 1 and the class one fills are used to replace missing values. The 2nd replicate is assumed class 2 and the class 2 fills used on it.
This augmented test set is run down the tree. In each set of replicates, the one receiving the most votes determines the class of the original case.
Outliers
Outliers are generally defined as cases that are removed from the main body of the data. Translate this as: outliers are cases whose proximities to all other cases in the data are generally small. A useful revision is to define outliers relative to their class. Thus, an outlier in class j is a case whose proximities to all other class j cases are small.
Define the average proximity from case n in class j to the rest of the training data class j as:
The raw outlier measure for case n is defined as
This will be large if the average proximity is small. Within each class find the median of these raw measures, and their absolute deviation from the median. Subtract the median from each raw measure, and divide by the absolute deviation to arrive at the final outlier measure.
Unsupervised learning
In unsupervised learning the data consist of a set of x -vectors of the same dimension with no class labels or response variables. There is no figure of merit to optimize, leaving the field open to ambiguous conclusions. The usual goal is to cluster the data - to see if it falls into different piles, each of which can be assigned some meaning.
The approach in random forests is to consider the original data as class 1 and to create a synthetic second class of the same size that will be labeled as class 2. The synthetic second class is created by sampling at random from the univariate distributions of the original data.
Thus, class two has the distribution of independent random variables, each one having the same univariate distribution as the corresponding variable in the original data. Class 2 thus destroys the dependency structure in the original data. But now, there are two classes and this artificial two-class problem can be run through random forests. This allows all of the random forests options to be applied to the original unlabeled data set.
If the oob misclassification rate in the two-class problem is, say, 40% or more, it implies that the x -variables look too much like independent variables to random forests. The dependencies do not have a large role and not much discrimination is taking place. If the misclassification rate is lower, then the dependencies are playing an important role.
Formulating it as a two class problem has a number of payoffs. Missing values can be replaced effectively. Outliers can be found. Variable importance can be measured. Scaling can be performed (in this case, if the original data had labels, the unsupervised scaling often retains the structure of the original scaling). But the most important payoff is the possibility of clustering.
Balancing prediction error
Prediction error occurs usually when one class is much larger than another. Then random forests, trying to minimize overall error rate, will keep the error rate low on the large class while letting the smaller classes have a larger error rate(larger error rate will be more focused during back propagation) For instance, in drug discovery, where a given molecule is classified as active or not, it is common to have the actives outnumbered by 10 to 1, up to 100 to 1. In these situations the error rate on the interesting class (actives) will be very high.
The user can detect the imbalance by outputs of the error rates for individual classes.
There is a low overall test set error (3.73%) but class 2 has over 3/4 of its cases misclassified (which is bad) The error balancing can be done by setting different weights for the classes.The higher the weight a class is given, the more its error rate is decreased. A guide as to what weights to give is to make them inversely proportional to the class populations. Using different weights, the overall error rate goes up. This is the usual result - to get better balance, the overall error rate will be increased.
SOME POINTERS
The individual trees in Random Forest are called weak learners. It builds multiple such decision tree and amalgamate them together to get a more accurate and stable prediction
When there's only one decision tree, there is high variance, because it sees the whole data at once. When multiple trees see subset of data and the prediction being mean/average of all individual predictions, the prediction turns out to be more stable
Decision tree splits the nodes on all available variables and then selects the split which results in most homogeneous sub-nodes.
Training set for the tree is drawn by sampling with replacement
Average when it is regression, Voting mechanism when it is classification
There are many hyper parameters that can be tuned.
max_features: Maximum number of features Random Forest is allowed to try in an individual tree. Increasing max_features generally improves the performance of the model as at each node now we have a higher number of options to be considered. However, this is not necessarily true as this decreases the diversity of individual tree which is the USP of random forest. But, for sure, you decrease the speed of algorithm by increasing the max_features. Hence, you need to strike the right balance and choose the optimal max_features
n_estimators: This is the number of trees you want to build before taking the maximum voting or averages of predictions. Higher number of trees give you better performance but makes your code slower. You should choose as high value as your processor can handle because this makes your predictions stronger and more stable.
min_leaf_size: A smaller leaf makes the model more prone to capturing noise in train data. A bigger leaf makes the model prone to overfitting
Algorithms for finding the best variable to split the node:
Gini impurity
Gini index says, if we select two items from a population at random then they must be of same class. Probability for this is 1 if population is pure. Divide number of people that belong to one class by the total number of people in that population. This gives the probability
Calculate Gini for sub-nodes, using formula sum of square of probability for success and failure (p^2+q^2)
Calculate Gini for split using weighted Gini score of each node of that split
The higher the Gini impurity, the better (homogenous) the split. Gini impurity of 1 = best
Information Gain
Degree of disorganization in a system is known as Entropy
Perfect Split = Lesser Entropy = More information gain
Entropy of 0, means perfect homogeneity.
It chooses the split which has lowest entropy compared to parent node and other splits.
Overfitting is a challange in Decision trees. In training, it will give 100% training accuracy, but it will end up making 1 leaf for every observation.
To overcome overfitting, 2 ways are suggested:
Setting constraints on tree size
Tree pruning:
Let the decision tree grow to a large depth
Then start at the bottom and start removing leaves which are giving negetive results, when compared to the top
This works well in the case: Suppose a split is giving us a gain of say -10 (loss of 10) and then the next split on that gives us a gain of 20. A simple decision tree will stop at step 1 but in pruning, we will see that the overall gain is +10 and keep both leaves.
Like every other model, a tree based model also suffers from the plague of bias and variance. Bias means, how much on an average are the predicted values different from the actual value. Variance means, how different will the predictions of the model be at the same point if different samples are taken from the same population.
Bias-variance intuition
Underfitting : High Bias - Low variance Overfitting : Low Bias - High Variance A champion model should maintain a balance between these two types of errors. This is known as the trade-off management of bias-variance errors.
There are two ways to overcome bias-variance tradeoff. 1. Bagging 2. Boosting
Bagging:
Bagging is a technique used to reduce the variance of our predictions by combining the result of multiple classifiers modeled on different sub-samples of the same data set.
Random Forest uses Bagging technique.
Create Multiple DataSets:
Sampling is done with replacement on the original data and new datasets are formed.
The new data sets can have a fraction of the columns as well as rows, which are generally hyper-parameters in a bagging model
Taking row and column fractions less than 1 helps in making robust models, less prone to overfitting
Build Multiple Classifiers:
Classifiers are built on each data set.
Generally the same classifier is modeled on each data set and predictions are made.
Combine Classifiers:
The predictions of all the classifiers are combined using a mean, median or mode value depending on the problem at hand.
The combined values are generally more robust than a single model.
Ex : Random Forest
Assume number of cases in the training set is N. Then, sample of these N cases is taken at random but with replacement. This sample will be the training set for growing the tree.
If there are M input variables, a number m<M is specified such that at each node, m variables are selected at random out of the M. The best split on these m is used to split the node. The value of m is held constant while we grow the forest.
Each tree is grown to the largest extent possible and there is no pruning.
Predict new data by aggregating the predictions of the ntree trees (i.e., majority votes for classification, average for regression).
XGBoost vs GBM
XGBoost supports Parallel processing
XGBoost allow users to define custom optimization objectives and evaluation criteria.
XGBoost has an in-built routine to handle missing values.
A GBM would stop splitting a node when it encounters a negative loss in the split. Thus it is more of a greedy algorithm. XGBoost on the other hand make splits upto the max_depth specified and then start pruning the tree backwards and remove splits beyond which there is no positive gain.
XGBoost allows user to run a cross-validation at each iteration of the boosting process
Variable Importance:
One of the byproducts of trying lots of decision tree variations is that you can examine which variables are working best/worst in each tree.
When a certain tree uses one variable and another doesn't, you can compare the value lost or gained from the inclusion/exclusion of that variable.
References
http://www.stat.berkeley.edu/~breiman/RandomForests/cc_home.htm
https://stackoverflow.com/questions/15810339/how-are-feature-importances-in-randomforestclassifier-determined
https://github.com/llSourcell/random_forests