<jupyter_start><jupyter_text>What is a Decision Tree?In order to understand a random forest, some general background on decision trees is needed.Classification and Regression Tree models, or CART models, were introduced by `Breimen et al.` In these models, a top down approach is applied to observation data. The general idea is that given a set of observations, the following question is asked: is every target variable in this set the same (or nearly the same)? If yes, label the set of observations with the most frequent class; if no, find the best rule that splits the observations into the purest set of observations.  How It WorksHere is an example as applied to the [iris](https://en.wikipedia.org/wiki/Iris_flower_data_set) data set:<jupyter_code>from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier,export_graphviz
import graphviz

iris_data = load_iris()
model = DecisionTreeClassifier()
model.fit(iris_data.data, iris_data.target)

dot = export_graphviz(model, 
                        out_file=None,
                        feature_names=iris_data.feature_names,
                        class_names=iris_data.target_names,
                        filled=True,
                        impurity=None,
                        )

graph = graphviz.Source(dot)
graph.render("iris_decision_tree")<jupyter_output><empty_output><jupyter_text>To read this tree, start from the top white node, using the first line to determine how the decision was made to split the current observations into two new nodes. Now, we can use this decision tree to classify new observations.**Observation 1**A flower with a petal width of 0.7 , petal length of 1.0, and a sepal width of 3.0.From the root node :- Is the petal width < 0.8 ?    - Yes -> go left.The flower is from the species setosa.**Observation 2**A flower with a petal width of 0.9 , petal length of 1.0, and a sepal width of 3.0.SolutionFrom the root node :- Is the petal width less than or equal to 0.8 ?    - No -> go right.- Is the petal width less than or equal to 1.75 ?    - Yes -> go left.- Is the petal length less than or equal to 4.95 ?    - Yes -> go left.- Is the petal width less than or equal to 1.65 ?    - Yes -> go leftThe flower is from species versicolor.  Limitations to Decision TreesWhile great for producing models that are easy to understand and implement, decision trees also tend to overfit on their training data—making them perform poorly if data shown to them later don’t closely match to what they were trained on.In the special case of regression trees, they also can only predict within the range of labels that they’ve seen before, which means that they have explicit upper and lower bounds on the numbers they can produce.  Ensemble MethodsEnsemble methods are algorithms that combine multiple algorithms into a single predictive model in order to decrease variance, decrease bias, or improve predictions.Ensemble methods are usually broken into two categories:- **Parallel**: An ensemble method where the models that make up the building blocks of the larger methods are generated independent of each other (i.e., they can be trained/generated as trivially parallel problems applied to the dataset).- **Sequential**: An ensemble methods where the learners are generated in a sequential order and are dependent on each other (i.e., they can only be trained one at a time, as the next model will require information from the training upstream of it).The random forest algorithm relies on a parallel ensemble method called `bagging` to generate its weak classifiers. BaggingBagging is a colloquial term for bootstrap aggregation. Bootstrap aggregation is a method that allows us to decrease the variance of an estimate by averaging multiple estimates that are measured from random subsamples of a population. Bootstrap Sampling [Boosting]The first portion of bagging is the application of bootstrap sampling to obtain subsets of the data. These subsets are then fed into one model that will comprise the final ensemble method. This is a straightforward process, given a set of observation data, n observations are selected at random and with replacement to form the subsample. This subsample is what is then fed into the machine learning algorithm of choice to train the model. AggregationAfter all of the models have been built, their outputs must be aggregated into a single coherent prediction for the larger model. In the case of a classifier model, this is usually just a winners take all strategy—whichever category receives the most votes is the final outcome predicted. In the case of a regression problem, a simple average of predicted outcome values is used. Feature BaggingFeature bagging (or the random subspace method) is a type of ensemble method that is applied to the features (columns) of a dataset instead of to the observations (rows). It is used as a method of reducing the correlation between features by training base predictors on random subsets of features instead of the complete feature space each time.  The Random ForestBased on what was previously covered in decision trees and ensemble methods, it should come as little surprise as to where the random forest gets its name or how they’re constructed at a high-level, but let’s go over it anyways.A random forest is comprised of a set of decision trees, each of which is trained on a random subset of the training data. These trees predictions can then be aggregated to provide a single prediction from a series of predictions. Building a Random ForestA random forest is built using the following procedure:- Choose the number of trees you’d like in your forest (M)- Choose the number of samples you’d like for each tree (n)- Choose the number of features you’d like in each tree (f)For each tree in M:- Select n samples with replacement from all observations- Select f features at random- Train a decision tree using the data set of n samples with f features- Save the decision tree  How a Random Forest makes a predictionGiven an observation (o).For each tree (t) in the model:- predict the outcome (p) using t applied to o- store p in list P- If the model is a classifier:    return max_count(p)- If the model is a regressor:    return avg(p)RF-predict  Training a Random ForestWhile you might be able to implement your own random forest from the ground up after going through this material, we will instead be using the scikit-learn implementation to go over how to train, make a prediction, and compare our random forest to a decision tree.Note: The iris dataset doesn’t have enough variance to make a random forest a better model than just a simple decision tree so for this example we’ll be using the breast cancer dataset instead.<jupyter_code>from sklearn.tree     import DecisionTreeClassifier
from sklearn.ensemble import RandomForestClassifier
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.metrics import classification_report, confusion_matrix
 

bc = load_breast_cancer()
X = bc.data
y = bc.target

# Create our test/train split
X_train, X_test, y_train, y_test = train_test_split(X,y, random_state=42)


## build our models 
decision_tree = DecisionTreeClassifier()
random_forest = RandomForestClassifier(n_estimators=100)

## Train the classifiers
decision_tree.fit(X_train, y_train)
random_forest.fit(X_train, y_train)

# Create Predictions
dt_pred = decision_tree.predict(X_test)
rf_pred = random_forest.predict(X_test)

# Check the performance of each model 
print('Decision Tree Model')
print(classification_report(y_test, dt_pred, target_names=bc.target_names))

print('Random Forest Model')
print(classification_report(y_test, rf_pred, target_names=bc.target_names))

#Graph our confusion matrix
dt_cm = confusion_matrix(y_test, dt_pred)
rf_cm = confusion_matrix(y_test, rf_pred)<jupyter_output>Decision Tree Model
              precision    recall  f1-score   support

   malignant       0.91      0.94      0.93        54
      benign       0.97      0.94      0.95        89

    accuracy                           0.94       143
   macro avg       0.94      0.94      0.94       143
weighted avg       0.94      0.94      0.94       143

Random Forest Model
              precision    recall  f1-score   support

   malignant       0.96      0.94      0.95        54
      benign       0.97      0.98      0.97        89

    accuracy                           0.97       143
   macro avg       0.96      0.96      0.96       143
weighted avg       0.97      0.97      0.96       143<jupyter_text>It appears that based on common metrics of classification model performance, the random forest outperforms the decision tree. As you can see, we’re able to increase the number of correctly predicted benign tumors and decrease the number of benign tumors that are predicted as malignant. By using a random forest, we can more accurately predict the state of a tumor, potentially decreasing the amount of unneeded procedures performed on patients and decreasing patient stress about their diagnosis.At this point, you’d usually start investigating `hyperparameter tuning`. This is a crucial part of the modeling process in order to ensure that your model is optimal. However, it is outside the scope of this article.  Feature ImportanceFeature importance is used to describe how much impact a feature (column) has on how the model makes decisions. They’re used in order to help guide future work by concentrating on things we are certain will have impact and perhaps ignoring things that don’t, for simplifying models and preventing overfitting by removing columns that aren’t impactful enough to be generalized, and for helping explain why a model is making the decisions it does.There are multiple methods for determining feature importance from a model. We’ll be covering how its calculated in the scikit-learn implementation. This method is popular because it's cheap to compute, does a reasonably good job of determining importance, and is already implemented.Unsurprisingly, in order to calculate the feature importance of the forest, we need to calculate the feature importance of the individual trees and then find a way to combine them.  Gini ImpurityGini impurity is a measure of the chance that a new observation when randomly classified would be incorrect. It is bounded between 0 and 1 (0 being impossible to be wrong and 1 being guaranteed to be wrong).Gini impurity of a node is calculated with the following equation : G(k)=∑i=1nP(i)×(1−P(i))where ii is a predicted category and P(i)P(i) is the probability of a record being assigned to class ii at random.<jupyter_code># Getting Feature Importance via sklearn 
from sklearn.ensemble import RandomForestClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

iris = load_iris()
X = iris.data
y = iris.target

# Create our test/train split
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=42)

# build our model
random_forest = RandomForestClassifier(n_estimators=100)

# Train the classifier
random_forest.fit(X_train, y_train)

# Get our features and weights
feature_list = sorted(zip(map(lambda x: round(x, 2), random_forest.feature_importances_), iris.feature_names),
             reverse=True)

# Print them out
print('feature\t\timportance')
print("\n".join(['{}\t\t{}'.format(f,i) for i,f in feature_list]))
print('total_importance\t\t',  sum([i for i,f in feature_list]))<jupyter_output>feature		importance
petal length (cm)		0.45
petal width (cm)		0.43
sepal length (cm)		0.1
sepal width (cm)		0.03
total_importance		 1.01
{'fraction_non_alphanumeric': 0.0477171301064195, 'fraction_numerical': 0.014074836937864744, 'mean_word_length': 3.9418999151823577, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 16, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '85963', 'license': 'MIT', 'n_tokens_mistral': 3059, 'n_tokens_neox': 2886, 'n_words': 1583, 'path': 'ML/DecisionTreeRandomForest/DecisionTreeRandomForest.ipynb', 'repo_name': 'pratikbarjatya/INSAID-Assignment', 'size': '11652'}