Decision Trees are **non-parametric**, since we are not making any assumptions about the underlying function $$f$$. Consequently, decision trees have very low structural error (bias). By averaging the output of many trees in a random forest, we are lowering the variance of the model, while keeping the bias the same. 


Why Random Forests?

*Random forests* is quite similar to *bagging* with *decision trees* except that there is an improvement on spliting trees. They both use bootstrapped subset of training oberservations for a tree and repeated that process several times for the average/most common result. 

The difference lies in that, random forest only use randomly selected subsets of all predictors for spliting trees. This improvement *decorrelates* the trees and solves the problem of bagging that,  if there is a very strong predictor, most bagged trees might look similar and averaging could not reduce much variance for the highly correlated quantities. However, this can be addressed by decorrelating the trees thus reducing the variance and making the trees more reliable.

Random Forests vs. Bagging with Decision Trees

A study on different data sizes and different forest sizes (# of attributes) found that at a certian point, increasing the forest size becomes much more computationally expensive without any significant performance gain. 

The study found using between 64 and 128 attributes was an optimal number, with fewer being less accurate, and more slower with similar accuracy. 

Random Forests: Selecting Number of Trees

Basic algorithm:

1. Pick N random records from the dataset. 

2. Build a decision tree based on these N records. 

3. Choose the number of trees you want in your algorithm and repeat steps 1 and 2. 

4. In case of a regression problem, for a new record, each tree in the forest predicts a value for Y (output). The final value can be calculated by taking the average of all the values predicted by all the trees in the forest. Or, in the case of a classification problem, each tree in the forest predicts the category to which the new record belongs. Finally, the new record is assigned to the category that wins the majority vote. 

How Random Forest work?

A really good paper, that explains random forests very well : 
[www.stat.berkeley.edu/~breiman/randomforest2001.pdf](https://www.stat.berkeley.edu/~breiman/randomforest2001.pdf) 

Random Forests

```python
from sklearn.metrics import accuracy_score
import sklearn.ensemble as skens

# build a random forest
rf_model = skens.RandomForestClassifier(n_estimators=10,oob_score=True, criterion='entropy')
rf_model.fit(df_iris_train.ix[:,:4],df_iris_train.species)

# predict the model 
predicted_labels = rf_model.predict(df_iris_test.ix[:,:4])
df_iris_test['predicted_rf_tree'] = predicted_labels

# find accuracy score
accuracy = accuracy_score(df_iris_test.species, predicted_labels)

# utility class to compare the predictions versus ground truth
def comparePlot(input_frame,real_column,predicted_column):
    df_a = input_frame.copy()
    df_b = input_frame.copy()
    df_a['label_source'] = 'Species'
    df_b['label_source'] = 'Classifier'
    df_a['label'] = df_a[real_column]
    df_b['label'] = df_b[predicted_column].apply(lambda x: 'Predict %s'%x)
    df_c = pd.concat((df_a, df_b), axis=0, ignore_index=True)
    sns.lmplot(x='sepal_length', y='sepal_width', col='label_source',
               hue='label', data=df_c, fit_reg=False, size=4);

# compare plot
comparePlot(df_iris_test,"species","predicted_rf_tree")
```

Random Forest Python Code

Below is a representation of under and overfitting of the boundaries of U.S. sates. The data comes from the US Census Bureau. In its original format, the data is a single Keyhole Markup Language (KML) file which contains latitude and longitude coordinates of the borders of US states. The necessary latitude, longitude, and label (state) data were parsed from the KML files using a simple Python script. The main idea here is to understand the bias-variance trade-off and how that relates to under and overfitting. 

Additionally there are two examples of ways they avoided under and overfitting and created a much more accurate map using (gradient) boosting and random forest classifiers.

A Visual Look at Under and Overfitting using U.S. States

The Random Forest is a model made up of many decision trees. It trains each one on a slightly different set of the observations, splitting nodes in each tree considering a limited number of the features. The final predictions of the random forest are made by averaging the predictions of each individual tree. In random forest algorithm, we do not need to do pruning for each "weak" decision tree. 

Advantage of Random Forest:
- Less overfitting
- Parallel implementation

University of Michigan - Ann Arbor

Approaches for improving decision trees' predictions 

Weakness of Trees model is predictive accuracy compared to other models. We can tackle this weakness of Trees by:

 - Bagging
 - Random Forrests
 - Boosting

How to improve the weakness of Trees model

- Generalized Additive Models
- Trees
- Random Forests
- Boosting
- Support Vector Machines
- Naive Bayes Classifier

Computer Intensive Classifiers

James, G., Witten, D., Hastie, T., & Tibshirani, R. (2013). An introduction to statistical learning (Vol. 112, pp. 3-7). New York: springer.

An Introduction to Statistical Learning with Applications in R

Bootstrap aggregation, or bagging, is a way to help construct more powerful prediction models by reducing high variance of a statistical learning method. It is often used to improve the performance of decision trees. In order to reduce the variance, $B$ different bootstrapped training data sets are produced (typically taken from a single training data set). It then uses the $b$th bootstrapped training data set to train the method to produce  $\hat{f}^{*b}(x)$. Afterwards, all the predictions are then averaged in order to get  $\hat{f}_{bag}(x) =  \frac{1}{B} \sum_{b=1}^B \hat{f}^{*b}(x)$. 

Bagging

Random Forest

Boosting is another approach that can be used for both classification and regression. Boosting improves predictions of a decision tree by learning slowly. Unlike bagging, boosting works sequentially, where each tree grown uses the information from those created before it, and works on modified versions of the original data set. Boosting combines a large number of trees ($\hat{f}^{1}, ...,  \hat{f}^{B}$). Decision trees are fitted based on the residuals of the model rather than the response (Y), then update the residuals by adding it to the fitted function. This means that each model created is slowly reducing the error of the previous ones. This causes an improvement of $\hat{f}$, particularly in places where it does not do as well as others. Decision trees using boosting tend to be very small.


Boosting

Pruning decision trees is the process of removing certain branches which are not beneficial towards the model’s goal. Decision trees frequently over-fit, which leads to an excess of branches. As a result, a decision tree performs extremely well on the training set, but is over-fitting leading to poor test set performance. To prevent this, individuals can ‘prune’ the decision tree leading to fewer branches preventing over-fitting. Types of pruning include minimum error, smallest tree, and early stopping.

Pruning Decision Trees

Support Vector Machines are intended for binary classification (cases where there are two classes). The main goal is to find a hyperplane that best divides a dataset into two classes. This is quantified by achieving the maximum distance between data points of both classes separated by the hyperplane. The further away the data points are from the hyperplane, the more confidently we are able to classify future data points into their respective class.

Support Vector Machines

A decision tree divides the prediction space into a series of simple regions according to the stratifying criteria. Decision trees can be applied to both regression and classification problems and can thus be of two types.

Decision Tree

Tree based methods aims to stratify or segment the predictor space (two predictors expressed in x y plane) into several simple regions. We can make a prediction for an observation by taking the mean or mode of the training observations in the region to which the observation belongs.

Tree based methods can be used both for 
-	Regression 
-	Classification


        


Tree-based Methods 

Generalized Additive Models (GAMs), similar to multiple linear regression models, attempt to predict a response value (Y) with many predictor variables ($X_1,...,X_p$). GAMs maintain their additivity by applying separate non-linear functions to predictor variables ($f_j(X_j)$) and adding them together. They can be further broken down into quantitative and qualitative responses.

Generalized Additive Models

Artificial Neural Networks are built to resemble neurons in the human brain. The idea behind neural networks is to understand the pattern behind terms through examples rather than through task-specific rules.

Artificial Neural Networks

Reference to Artificial Neural Networks

A method of supervised classification that takes many features, assumed to be independent, and uses Bayes' Theorem to determine given those independent variables how likely the likelihood of another event occurring.

It's called "Naive" because it assumes that features are conditionally independent, given the class, i.e., for all instances of a given class, the features have little or no correlation with each other.

Learn Before

Related

Learn After