# Decision Tree & Ensemble Learning

Classification And Regression Trees (CART for short) is a term introduced by [Leo Breiman](https://en.wikipedia.org/wiki/Leo_Breiman) to refer to Decision Tree algorithms that can be used for classification or regression predictive modeling problems.

In this lab assignment, you will implement various ways to calculate impurity which is used to split data in constructing the decision trees and apply the Decision Tree and ensemble learning algorithms to solve two real-world problems: a classification one and a regression one. 


```python
# import packages
%matplotlib inline
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
import pandas as pd
from matplotlib.legend_handler import HandlerLine2D
from sklearn.metrics import accuracy_score
from sklearn.metrics import confusion_matrix
from sklearn.metrics import mean_squared_error
from sklearn.metrics import mean_absolute_error
from sklearn.tree import DecisionTreeClassifier
from sklearn.tree import DecisionTreeRegressor
from sklearn.model_selection import GridSearchCV
import math as math
from sklearn.ensemble import RandomForestClassifier
from sklearn.ensemble import RandomForestRegressor
from sklearn.ensemble import GradientBoostingClassifier
from sklearn.ensemble import GradientBoostingRegressor
from sklearn.ensemble import AdaBoostClassifier
from sklearn.ensemble import AdaBoostRegressor


# make this notebook's output stable across runs
np.random.seed(0)
```

## Gini impurity and Entropy


#### Gini impurity

The CART algorithm recursively splits the training set into two subsets using a single feature k and a threshold $t_k$. The best feature and threshold are chosen to produce the purest subsets weighted by their size. **Gini impurity** measures the impurity of the data points in a set and is used to evaluate how good a split is when the CART algorithm searches for the best pair of feature and the threshold.

To compute Gini impurity for a set of items with J classes, suppose $i \in \{1, 2, \dots, J\}$ and let $p_i$ be the fraction of items labeled with class i in the set.
\begin{align}
I(p) = 1 - \sum_{i=1}^J p_i^2
\end{align}

The following function calculates the gini impurity for a given set of data points.


```python
def gini_impurity(x):
    """
    This function calculate the Gini impurity for a given set of data points.

    Args:
    x: a numpy ndarray
    """
    unique, counts = np.unique(x, return_counts=True)
    probabilities = counts / sum(counts)
    gini = 1 - sum([p*p for p in probabilities])

    return gini
```


```python
np.testing.assert_equal(0, gini_impurity(np.array([1, 1, 1])))
np.testing.assert_equal(0.5, gini_impurity(np.array([1, 0, 1, 0])))
np.testing.assert_equal(3/4, gini_impurity(np.array(['a', 'b', 'c', 'd'])))
np.testing.assert_almost_equal(2.0/3, gini_impurity(np.array([1, 2, 3, 1, 2, 3])))
```

#### Entropy

Another popular measure of impurity is called **entropy**, which measures the average information content of a message. Entropy is zero when all messages are identical. When it applied to CART, a set's entropy is zero when it contains instances of only one class. Entropy is calculated as follows:
\begin{align}
I(p) = - \sum_{i=1}^J p_i log_2{p_i}
\end{align}

<span style="color:orange">**Question 1: In this exercise, you will implement the entropy function.**


```python
def entropy(x):
    """
    TODO: This function calculate the entropy of an array.

    Args:
    x: a numpy ndarray
    """
    unique, counts = np.unique(x, return_counts=True)
    probabilities = counts / sum(counts)
    e = abs(-(sum(p* math.log(p,2) for p in probabilities)))
    

    return e


```


```python
np.testing.assert_equal(0, entropy(np.array([1, 1, 1])))
np.testing.assert_equal(1.0, entropy(np.array([1, 0, 1, 0])))
np.testing.assert_equal(2.0, entropy(np.array(['a', 'b', 'c', 'd'])))
np.testing.assert_almost_equal(1.58496, entropy(np.array([1, 2, 3, 1, 2, 3])), 4)
```

---

## Iris dataset

The Iris data set contains the morphologic variation of Iris flowers of three related species (Iris setosa, Iris virginica and Iris versicolor). Four features were measured from each observation (see image below):
- Sepal.Length: sepal length in centimeters.
- Sepal.Width: sepal width in centimeters.
- Petal.Length: petal length in centimeters.
- Petal.Width: petal width in centimeters.

<table>
  <tr>
    <td></td>
    <td></td>
    <td></td>
  </tr>
  <tr>
    <td>Iris setosa</td>
    <td>Iris versicolor</td>
    <td>Iris virginica</td>
  </tr>
</table>



```python
# load the iris train and test data from CSV files
train = pd.read_csv('https://raw.githubusercontent.com/zariable/data/master/iris_train.csv')
test = pd.read_csv('https://raw.githubusercontent.com/zariable/data/master/iris_test.csv')

train_x = train.iloc[:,0:4]
train_y = train.iloc[:,4]

test_x = test.iloc[:,0:4]
test_y = test.iloc[:,4]

# print the number of instances in each class
print(train_y.value_counts().sort_index())
print(test_y.value_counts().sort_index())
```

    Iris-setosa        34
    Iris-versicolor    32
    Iris-virginica     39
    Name: species, dtype: int64
    Iris-setosa        16
    Iris-versicolor    18
    Iris-virginica     11
    Name: species, dtype: int64


### Decision Tree Classifier

<span style="color:orange">**In this exercise, we will apply the Decision Tree classifier to classify the Iris flower data.**

#### Train and visualize a simple Decision Tree

<span style="color:orange">**Question 2: create a decision tree with max_depth of 2.**


```python
# TODO: read the scikit-learn doc on DecisionTreeClassifier and train a Decision Tree with max depth of 2
dtc = DecisionTreeClassifier(max_depth=2)
dtc.fit(train_x,train_y)


```




    DecisionTreeClassifier(ccp_alpha=0.0, class_weight=None, criterion='gini',
                           max_depth=2, max_features=None, max_leaf_nodes=None,
                           min_impurity_decrease=0.0, min_impurity_split=None,
                           min_samples_leaf=1, min_samples_split=2,
                           min_weight_fraction_leaf=0.0, presort='deprecated',
                           random_state=None, splitter='best')



Now let's visualize the decision tree we just trained on the iris dataset and see how it makes predictions. Note that if the following code does not work for you because the graphviz is missing, do not worry about it and you should still be able to move on.


```python
from sklearn.externals.six import StringIO  
from IPython.display import Image  
from sklearn.tree import export_graphviz
import pydotplus

dot_data = StringIO()
feature_names = train_x.columns
class_names = train_y.unique()
class_names.sort()
export_graphviz(dtc, out_file=dot_data, feature_names=feature_names, class_names=class_names, filled=True, rounded=True)
graph = pydotplus.graph_from_dot_data(dot_data.getvalue())  
Image(graph.create_png())
```

Decision trees are easy to inteprete and is often referred to as *whitebox* machine learning algorithm. Let's see how this decision tree represented above makes predictions. Suppose you find an iris flower and want to classify it into setosa, versicolor or virginica. You start at the root node (the very top node in the tree). In this node, we check if the flower's patel length is smaller than or equal to 2.35 cm. If it is, we move to the left child and predict setosa to be its class. Otherwise, we move to the right child node. Then similarly we check if the petal length is smaller than or equal to 4.95 cm. If it is, we move to its left child node and predict versicolor to be its class. Otherwise, we move to its right child and predict virginica to be its class. 

#### Prediction with Decision tree

With this simple decision tree above, we can apply it to make predictions on the test dataset and evaluate its performance.

<span style="color:orange">**Question 3: make prediction using the trained decision tree model on the test data.**


```python
# TODO: use the trained decision tree model to make predictions on the test data and evaluate the model performance.
test_z = dtc.predict(test_x)

print("model accuracy: {}".format(accuracy_score(test_y, test_z)))
print("model confusion matrix:\n {}".format(confusion_matrix(test_y, test_z, labels=['Iris-setosa', 'Iris-versicolor', 'Iris-virginica'])))
```

    model accuracy: 0.9111111111111111
    model confusion matrix:
     [[16  0  0]
     [ 0 17  1]
     [ 0  3  8]]


***Ans 3: model accuracy: 0.9111111111111111
model confusion matrix:
 [[16  0  0]
 [ 0 17  1]
 [ 0  3  8]] ***

#### Hyper-parameters

Hyper-parameter controls the complexity of the decision tree model. For example, the deeper the tree is, the more complex patterns the model will be able to capture. In this exercise, we train the decision trees with increasing number of maximum depth and plot its performance. We should see the accuracy of the training data increase as the tree grows deeper, but the accuracy on the test data might not as the model will eventually start to overfit and does not generalize well on the unseen test data.

<span style="color:orange">**Question 4: for each value of max_depth, we train a decision tree model and evaluate its accuracy on both train and test data, and plot both accuracies in the figure.**


```python

```


```python
dtc = DecisionTreeClassifier(max_depth=2)
dtc.fit(train_x,train_y)
test_z = dtc.predict(test_x)

print("model  on train data: {}".format(accuracy_score(train_y, dtc.predict(train_x))))
print("model  on test data: {}".format(accuracy_score(test_y, test_z)))
#print("model confusion matrix:\n {}".format(confusion_matrix(test_y, test_z, labels=['Iris-setosa', 'Iris-versicolor', 'Iris-virginica'])))
dep2_train= round((accuracy_score(train_y, dtc.predict(train_x))*100),2)
dep2_test=round((accuracy_score(test_y, test_z)*100),2)

```

    model  on train data: 0.9619047619047619
    model  on test data: 0.9111111111111111



```python
# TODO: train the decision tree model with various max_depth, make predictions and evaluate on both train and test data.
dtc = DecisionTreeClassifier(max_depth=3)
dtc.fit(train_x,train_y)
test_z = dtc.predict(test_x)

print("model  on train data: {}".format(accuracy_score(train_y, dtc.predict(train_x))))
print("model  on test data: {}".format(accuracy_score(test_y, test_z)))
#print("model confusion matrix:\n {}".format(confusion_matrix(test_y, test_z, labels=['Iris-setosa', 'Iris-versicolor', 'Iris-virginica'])))
dep3_train= round((accuracy_score(train_y, dtc.predict(train_x))*100),2)
dep3_test=round((accuracy_score(test_y, test_z)*100),2)
```

    model  on train data: 0.9809523809523809
    model  on test data: 0.9777777777777777



```python
dtc = DecisionTreeClassifier(max_depth=4)
dtc.fit(train_x,train_y)
test_z = dtc.predict(test_x)
print("model  on train data: {}".format(accuracy_score(train_y, dtc.predict(train_x))))
print("model accuracy: {}".format(accuracy_score(test_y, test_z)))
dep4_train= round((accuracy_score(train_y, dtc.predict(train_x))*100),2)
dep4_test=round((accuracy_score(test_y, test_z)*100),2)

```

    model  on train data: 1.0
    model accuracy: 0.9777777777777777



```python
dtc = DecisionTreeClassifier(max_depth=5)
dtc.fit(train_x,train_y)
test_z = dtc.predict(test_x)
print("model  on train data: {}".format(accuracy_score(train_y, dtc.predict(train_x))))
print("model accuracy: {}".format(accuracy_score(test_y, test_z)))
dep5_train= round((accuracy_score(train_y, dtc.predict(train_x))*100),2)
dep5_test=round((accuracy_score(test_y, test_z)*100),2)
```

    model  on train data: 1.0
    model accuracy: 0.9777777777777777



```python
accuracy_train= {"labels":[2,3,4,5], "accuracy": [dep2_train,dep3_train,dep4_train,dep5_train]}
ax=sns.barplot(x="labels",y="accuracy",data=accuracy_train)
ax.set(title="Train data accuracy",xlabel="Max_depth", ylabel="Accuracy",ylim=(96,100))

```


```python
accuracy_test= {"labels":[2,3,4,5], "accuracy": [dep2_test,dep3_test,dep4_test,dep5_test]}
ax=sns.barplot(x="labels",y="accuracy",data=accuracy_test)
ax.set(title="Test_data accuracy",xlabel="Max_depth", ylabel="Accuracy",ylim=(90,100))
```

*** And 4: With train data, accuracy is at its best 98.09% when max depth is 3 and starts over fitting as max depth goes beyond 3. With test data, accuracy reaches maximum of 97.78% at max depth of 3 and remains constant beyond that ***

#### Fine-tune the decision tree classifier

Decision tree is a very powerful model with very few assumptions about the incoming training data (unlike linear models, which assume the data linear), however, it is more likely to overfit the data and won't generalize well to unseen data. To void overfitting, we need to restrict the decision tree's freedom during training via regularization (e.g. max_depth, min_sample_split, max_leaf_nodes and etc.).

To fine-tune the model and combat overfitting, use grid search with cross-validation (with the help of the GridSearchCV class) to find the best hyper-parameter settings for the DecisionTreeClassifier. In particular, we would like to fine-tune the following hyper-parameters:
- **criteria**: this defines how we measure the quality of a split. we can choose either "gini" for the Gini impurity or "entropy" for the information gain.
- **max_depth**: the maximum depth of the tree. This indicates how deep the tree can be. The deeper the tree, the more splits it has and it captures more information about the data. But meanwhile, deeper trees are more likely to overfit the data. For this practice, we will choose from {1, 2, 3} given there are only 4 features in the iris dataset.
- **min_samples_split**: This value represents the minimum number of samples required to split an internal node. The smaller this value is, the deeper the tree will grow, thus more likely to overfit. On the other hand, if the value is really large (the size of the training data in the extreme case), the tree will be very shallow and could suffer from underfit. In this practice, we choose from {0.01, 0.05, 0.1, 0.2}.

<span style="color:orange">**Question 5: Use grid search with 3-fold cross-validation to fine-tune the decision tree model and output the best hyper-parameters.**


```python
# TODO: fine-tune the model, use grid search with 3-fold cross-validation.
parameters = {"criterion" : ["gini","entropy"],
              "max_depth" : [1,2,3],
              "min_samples_split" : [0.01,0.05,0.1,0.2]   
}


dt = DecisionTreeClassifier()

grid = GridSearchCV(dt, parameters, cv=3)
grid.fit(train_x, train_y)
# summarize the results of the grid search
print("The best score is {}".format(grid.best_score_))
print("The best hyper parameter setting is {}".format(grid.best_params_))
```

    The best score is 0.9619047619047619
    The best hyper parameter setting is {'criterion': 'gini', 'max_depth': 3, 'min_samples_split': 0.01}


*** Ans 5: The best score is 0.9619047619047619
The best hyper parameter setting is {'criterion': 'gini', 'max_depth': 3, 'min_samples_split': 0.01} ***

#### Prediction and Evaluation

Now we have a fine-tuned decision tree classifier based on the training data, let's apply this model to make predictions on the test data and evaluate its performance.


```python
test_z= grid.predict(test_x)

print("model accuracy: {}".format(accuracy_score(test_y, test_z)))
print("model confusion matrix:\n {}".format(confusion_matrix(test_y, test_z, labels=['Iris-setosa', 'Iris-versicolor', 'Iris-virginica'])))
```

    model accuracy: 0.9777777777777777
    model confusion matrix:
     [[16  0  0]
     [ 0 17  1]
     [ 0  0 11]]


### Random Forest

**Question 6: Apply Random Forest together with Gridsearch to the Iris dataset and evaluate its accuracy.**


```python
### TODO

params = {
    "criterion" :['gini', 'entropy'],
    "n_estimators" : [100, 200], 
    "max_depth" : [2,3,4], 
    "min_samples_split" :[0.01,0.05,0.1,0.2]    
}

rfc_grid= GridSearchCV(RandomForestClassifier(), params, cv=3)
rfc_grid.fit(train_x,train_y)
print("The best score is {}".format(rfc_grid.best_score_))
print("The best hyper parameter setting is {}".format(rfc_grid.best_params_))

```

    The best score is 0.9619047619047619
    The best hyper parameter setting is {'criterion': 'gini', 'max_depth': 2, 'min_samples_split': 0.05, 'n_estimators': 100}



```python
test_z=rfc_grid.predict(test_x)

print("model accuracy: {}".format(accuracy_score(test_y, test_z)))
print("model confusion matrix:\n {}".format(confusion_matrix(test_y, test_z, labels=['Iris-setosa', 'Iris-versicolor', 'Iris-virginica'])))
```

    model accuracy: 0.9777777777777777
    model confusion matrix:
     [[16  0  0]
     [ 0 17  1]
     [ 0  0 11]]


*** The best score is 0.9619047619047619
The best hyper parameter setting is {'criterion': 'gini', 'max_depth': 2, 'min_samples_split': 0.05, 'n_estimators': 100}
model accuracy: 0.9777777777777777
model confusion matrix:
 [[16  0  0]
 [ 0 17  1]
 [ 0  0 11]]***

### Adaboost

**Question 7: Apply Adaboost together with Gridsearch to the Iris dataset and evaluate its accuracy.**


```python
### TODO 
paramsada= {"n_estimators" : [100,200],
            "learning_rate" :[ 0.05, 0.1, 0,2]            
}

ada = AdaBoostClassifier(DecisionTreeClassifier(max_depth=4))

adaboost_grid= GridSearchCV(ada, paramsada, cv=3)

adaboost_grid.fit(train_x,train_y)
# summarize the results of the grid search
print("The best score is {}".format(adaboost_grid.best_score_))
print("The best hyper parameter setting is {}".format(adaboost_grid.best_params_))

```

    The best score is 0.9523809523809522
    The best hyper parameter setting is {'learning_rate': 0.05, 'n_estimators': 100}


    /usr/local/lib/python3.7/dist-packages/sklearn/model_selection/_validation.py:536: FitFailedWarning: Estimator fit failed. The score on this train-test partition for these parameters will be set to nan. Details: 
    ValueError: learning_rate must be greater than zero
    
      FitFailedWarning)



```python
test_z=adaboost_grid.predict(test_x)

print("model accuracy: {}".format(accuracy_score(test_y, test_z)))
print("model confusion matrix:\n {}".format(confusion_matrix(test_y, test_z, labels=['Iris-setosa', 'Iris-versicolor', 'Iris-virginica'])))
```

    model accuracy: 0.9777777777777777
    model confusion matrix:
     [[16  0  0]
     [ 0 17  1]
     [ 0  0 11]]


*** The best score is 0.9619047619047619
The best hyper parameter setting is {'learning_rate': 2, 'n_estimators': 200}
Model accuracy: 0.9777777777777777
Model confusion matrix:
 [[16  0  0]
 [ 0 17  1]
 [ 0  0 11]]***

### Gradient Boosting

**Question 8: Apply Boosting together with Gridsearch to the Iris dataset and evaluate its accuracy.**


```python
### TODO 
grd= GradientBoostingClassifier()
parameters1 = {
    "loss":["deviance"],
    "learning_rate": [0.01, 0.1],
    "min_samples_split": [0.01,0.05,0.1,0.2],
    "max_depth":[2, 3, 4],
    "n_estimators":[100]
}


gbc_grid = GridSearchCV(grd, parameters1, cv=3)
gbc_grid.fit(train_x, train_y)

# summarize the results of the grid search
print("The best score is {}".format(gbc_grid.best_score_))
print("The best hyper parameter setting is {}".format(gbc_grid.best_params_))
```

    The best score is 0.9619047619047619
    The best hyper parameter setting is {'learning_rate': 0.01, 'loss': 'deviance', 'max_depth': 2, 'min_samples_split': 0.1, 'n_estimators': 100}



```python
test_z=gbc_grid.predict(test_x)

print("model accuracy: {}".format(accuracy_score(test_y, test_z)))
print("model confusion matrix:\n {}".format(confusion_matrix(test_y, test_z, labels=['Iris-setosa', 'Iris-versicolor', 'Iris-virginica'])))
```

    model accuracy: 0.9777777777777777
    model confusion matrix:
     [[16  0  0]
     [ 0 17  1]
     [ 0  0 11]]


*** The best score is 0.9619047619047619
The best hyper parameter setting is {'learning_rate': 0.01, 'loss': 'deviance', 'max_depth': 2, 'min_samples_split': 0.1, 'n_estimators': 100}
Model accuracy: 0.9777777777777777
Model confusion matrix:
 [[16  0  0]
 [ 0 17  1]
 [ 0  0 11]] ***

---

**BONUS POINT: we will apply the supervised learning models we learnt so far to predict the California housing prices.**

## California Housing Dataset

The California Housing dataset appeared in a 1997 paper titled Sparse Spatial Autoregressions by Pace, R. Kelley and Ronald Barry, published in the Statistics and Probability Letters journal. They built it using the 1990 California census data. It contains one row per census block group. A block group is the smallest geographical unit for which the U.S. Census Bureau publishes sample data (a block group typically has a population of 600 to 3,000 people). 


```python
# Load train and test data from CSV files.
train = pd.read_csv('https://raw.githubusercontent.com/zariable/data/master/housing_train.csv')
test = pd.read_csv('https://raw.githubusercontent.com/zariable/data/master/housing_test.csv')

train_x = train.iloc[:,0:8]
train_y = train.iloc[:,8]

test_x = test.iloc[:,0:8]
test_y = test.iloc[:,8]
```


```python
grd= GradientBoostingRegressor()
parameters1 = {
    "learning_rate": [0.1, 0.2],
    "min_samples_split": [0.01],
    "max_depth":[4,7],
    "n_estimators":[100]
}


gbc_grid = GridSearchCV(grd, parameters1, cv=3)
gbc_grid.fit(train_x, train_y)

# summarize the results of the grid search
print("The best score is {}".format(gbc_grid.best_score_))
print("The best hyper parameter setting is {}".format(gbc_grid.best_params_))
test_z= gbc_grid.predict(test_x)
rsq= sm.r2_score(test_y,test_z)
print(rsq)

```

    The best score is 0.8167181654156304
    The best hyper parameter setting is {'learning_rate': 0.2, 'max_depth': 7, 'min_samples_split': 0.01, 'n_estimators': 100}
    0.8236932422217006



```python
from xgboost import XGBRegressor
xgb= XGBRegressor(objective='reg:squarederror')
params = {"learning_rate" :[0.1,0.2],
          "max_depth" : [5],
          "n_estimators" : [500]
}

xgb_grid = GridSearchCV(xgb,params, cv=2, n_jobs= -1)

xgb_grid.fit(train_x,train_y)
test_z=xgb_grid.predict(test_x)
```


```python
print("The best score is {}".format(xgb_grid.best_score_))
print("The best hyper parameter setting is {}".format(xgb_grid.best_params_))
```

    The best score is 0.8182037370882838
    The best hyper parameter setting is {'learning_rate': 0.1, 'max_depth': 5, 'n_estimators': 500}



```python
rsq= sm.r2_score(test_y,test_z)
print(rsq)
```

    0.8334510273653781


*** XGBRegressor model gives better R squared value compared to other models ***

### End of Assignment 2
---


09fb6b1d3215dfd91a65ef90b91e92a7b043cc43
ipynb
Jupyter Notebook
Iris Dataset Ensemble learning.ipynb
jessiececilya/ensemble-irisdataset
a66de222086b14fd0730d6e57152de5ca48a3d8d
MIT
Iris Dataset Ensemble learning.ipynb
jessiececilya/ensemble-irisdataset
a66de222086b14fd0730d6e57152de5ca48a3d8d
MIT
Iris Dataset Ensemble learning.ipynb
jessiececilya/ensemble-irisdataset
a66de222086b14fd0730d6e57152de5ca48a3d8d
MIT
Qwen/Qwen-72B
1. YES
2. YES