# Decision Tree

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 algorithm 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

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

## Gini impurity and Entropy

<span style="color:orange">**Coding Part 1: Implement the functions to calculate Gini impurity and entropy.**</span> 

#### 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}

In this exercise, you will implement the function to calculate gini impurity.


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

    Args:
    x: a numpy ndarray
    """
    gini = 0
    return gini = 0
```


```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}

Here, you will implement entropy impurity function.


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

    Args:
    x: a numpy ndarray
    """
    e = 0

    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)
```

---

## Decision Tree Classifier

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

### 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("iris_train.csv")
test = pd.read_csv("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())
```

### Train and visualize a simple Decision Tree


```python
# TODO: read the scikit-learn doc on DecisionTreeClassifier and train a Decision Tree with max depth of 2
dtc = None
```

Now let's visualize the decision tree we just trained on the iris dataset and see how it makes predictions.


```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.


```python
# TODO: use the trained decision tree model to make predictions on the test data and evaluate the model performance
#       using evaluate(y, z) above.

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'])))
```

### 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.


```python
max_depths = np.linspace(1, 8, 8, endpoint=True)
train_results = []
test_results = []

for max_depth in max_depths:
    # TODO: train the decision tree model with various max_depth, make predictions and evaluate on both train and test data.
    dt = DecisionTreeClassifier(max_depth=max_depth)
    dt.fit(train_x, train_y)
   
    train_z = dt.predict(train_x)
    train_accuracy = accuracy_score(train_y, train_z)
    train_results.append(train_accuracy)

    test_z = dt.predict(test_x)
    test_accuracy = accuracy_score(test_y, test_z)
    test_results.append(test_accuracy)

# plot the accuracy on train and test data
line1, = plt.plot(max_depths, train_results, 'b', label="Train Accuracy")
line2, = plt.plot(max_depths, test_results, 'r', label="Test Accuracy")
plt.legend(handler_map={line1: HandlerLine2D(numpoints=2)})
plt.ylabel("Accuracy")
plt.xlabel("Max Depth")
plt.show()
```

### 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.05, 0.1, 0.2}


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

dt = DecisionTreeClassifier()
grid = # TODO
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_))
```

### 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
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'])))
```

---

## Decision Tree Regressor

<span style="color:orange">**Coding Part 3: In this exercise, we will apply the Decision Tree classifier to predict the California housing prices.**</span> 

### 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("housing_train.csv")
test = pd.read_csv("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
# TODO: fine-tune the model, use grid search with cross-validation.
parameters = {
    'max_depth': [4, 8, 16, 32], 
    'min_samples_split': [0.001, 0.01, 0.05, 0.1, 0.2],
    'max_features': [2, 4, 8]
}

dtr = # TODO
grid = # TODO
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_))
```


```python
# Use the fine-tuned model to make predictions on the test data
test_z = grid.predict(test_x)

print("model Root Mean Squared Error: {}".format(np.sqrt(mean_squared_error(test_y, test_z))))
print("model Mean Absolute Error: {}".format(mean_absolute_error(test_y, test_z)))
```

### End of ML 310 Lab Assignment 2
---


d746a47a5942cca26604bcfa062c353e69b7e763
ipynb
Jupyter Notebook
module02/resources/HW02.ipynb
kegedy/MLEARN520
d6f1f73a4985db217457ca53756e9828cf59d831
MIT
module02/resources/HW02.ipynb
kegedy/MLEARN520
d6f1f73a4985db217457ca53756e9828cf59d831
MIT
module02/resources/HW02.ipynb
kegedy/MLEARN520
d6f1f73a4985db217457ca53756e9828cf59d831
MIT
Qwen/Qwen-72B
1. YES
2. YES