# Decision Tree Induction with scikit-learn

**CS5483 Data Warehousing and Data Mining**
___


```python
%reset -f
%matplotlib inline
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn import datasets, tree
# produce vector inline graphics
from IPython.display import set_matplotlib_formats
set_matplotlib_formats('svg')
```

## Decision Tree Induction

We first import the [*iris dataset*](https://en.wikipedia.org/wiki/Iris_flower_data_set) from [`sklearn.datasets` package](https://scikit-learn.org/stable/datasets/index.html) 


```python
from sklearn import datasets
import pandas as pd

iris = datasets.load_iris()
```

Recall that the classification task is to train a model that can classify the spieces (*target*) automatically based on the lengths and widths of the petals and sepals (*input features*).

To build a decision tree, we simply create a tree using `DecisionTreeClassifier` from `sklearn.tree` and apply its method `fit` on the training set.


```python
clf_gini = tree.DecisionTreeClassifier(random_state=0).fit(iris.data, iris.target)
```

To display the decision tree, we can use the function `plot_tree` from `sklearn.tree`:


```python
# to make the tree look better
options = {'feature_names': iris.feature_names, 
           'class_names': iris.target_names,
           'filled': True,
           'node_ids': True,
           'rounded': True,
           'fontsize': 6}

plt.figure(figsize=(9,6))
tree.plot_tree(clf_gini, **options)
plt.show()
```

For each node:
- `___ <= ___` is the splitting criterion for internal nodes, satisfied only by samples going left.
- `gini = ...` shows the impurity index. By default, the algorithm uses Gini impurity index to find the best binary split. Observe that the index decreases down the tree towards the leafs.
- `value = [_, _, _]` shows the number of examples for each of the three classes, and `class = ...` indicates a majority class, which may be used as the decision for a leaf node. The majority classes are also color coded. Observe that the color gets lighter towards the root, as the class distribution is more impure. 

In particular, check that iris setosa is distinguished immediately after checking the petal width/length.

All the information of the decision is stored in the `tree_` attribute of the classifer. For more details:


```python
help(clf_gini.tree_)
```

**Exercise** Assign to `clf_entropy` the decision tree classifier created using *entropy* as the impurity measure. You can do so with the keyword argument `criterion='entropy'` in `DecisionTreeClassifier`. Furthermore, Use `random_state=0` and fit the classifier on the entire iris dataset. Check whether the resulting decision tree same as the one created using the Gini impurity index.


```python
# YOUR CODE HERE
raise NotImplementedError()

plt.figure(figsize=(9, 6))
tree.plot_tree(clf_entropy, **options)
plt.show()
```

YOUR ANSWER HERE

It is important to note that, although one can specify whether to use Gini impurity or entropy, `sklearn` implements neither C4.5 nor CART algorithms. In particular, it supports only binary splits on numeric input attributes, unlike C4.5 which supports multi-way splits using information gain ratio.  
(See some [workarounds][categorical].)

[categorical]: https://stackoverflow.com/questions/38108832/passing-categorical-data-to-sklearn-decision-tree

## Compute Splitting Criterion

To understand how the decision tree is generated, we will implements the computation of the splitting criterion.

### Basic data analysis using `pandas`

To have an idea of qualities of the features, create a [`pandas`](https://pandas.pydata.org/docs/user_guide/index.html) [`DataFrame`](https://pandas.pydata.org/docs/reference/api/pandas.DataFrame.html?highlight=dataframe#pandas.DataFrame) 
to operate on the dataset.


```python
# write the input features first
iris_df = pd.DataFrame(data=iris.data, columns=iris.feature_names)

# append the target values to the last column
iris_df['target'] = iris.target
iris_df.target = iris_df.target.astype('category')
iris_df.target.cat.categories = iris.target_names
iris_df
```

To display some statistics of the input features for different classes:


```python
iris_df.groupby('target').boxplot(rot=90, layout=(1,3))
iris_df.groupby('target').agg(['mean','std']).round(2)
```

**Exercise** Identify good feature(s) based on the above statistics. Does you choice agree with the decision tree generated by `DecisionTreeClassifier`?

YOUR ANSWER HERE

### Compute impurity

Given a distribution $\boldsymbol{p}=(p_1,p_2,\dots)$ where $p_k\in [0,1]$ and $\sum_k p_k =1$, the Gini impurity index is defined as:

\begin{align}
\operatorname{Gini}(\boldsymbol{p}) = \operatorname{Gini}(p_1,p_2,\dots) &:= \sum_k p_k(1-p_k)\\
&= 1- \sum_k p_k^2.
\end{align}

We can represent a distribution simply as a `numpy` array. To return the empirical class distributions of the iris dataset:


```python
def dist(values):
    '''Returns the empirical distribution of the given 1D array of values as a 
    1D array of probabilites.'''
    counts = np.unique(values, return_counts=True)[-1]
    return counts / counts.sum()


print(f"Distribution of target: {dist(iris.target).round(4)}")
```

The Gini impurity index can be computed as follows:


```python
def gini(p):
    '''Returns the Gini impurity of distribution p.'''
    return 1 - (p**2).sum()

print(f"Gini impurity of target: {gini(dist(iris.target)):.4g}")
```

**Exercise** Complete the following function to compute the entropy of a distribution:

\begin{align}
h(\boldsymbol{p}) = h(p_1,p_2,\dots) &= \sum_k - p_k \log_2 p_k\\
&= \sum_{k:p_k>0} - p_k \log_2 p_k.
\end{align}

You may use the function `log2` from `numpy` to calculate the logarithm base 2. Note that logarithm of $0$ is undefined, we use the last expression of the entropy to avoid taking the limit $\lim_{p\to 0} p\log p=0$.

You solution should look like:
```Python
def entropy(p):
    ...
    return (p * ___ * ___).sum()
```


```python
def entropy(p):
    '''Returns the entropy of distribution p.'''
    p = np.array(p)
    p = p[(p > 0) & (p < 1)]  # 0 log 0 = 1 log 1 = 0
    # YOUR CODE HERE
    raise NotImplementedError()
```


```python
# tests
assert np.isclose(entropy([1/2, 1/2]), 1)
assert np.isclose(entropy([1, 0]), 0)
```

### Compute drop in impurity and best split

Now, to compute the drop in impurity for given splitting criterion:

\begin{align}
\Delta \operatorname{Gini}_{X\leq s}(Y) = \operatorname{Gini}(P_Y) - \left[\Pr\{X\leq s\} \operatorname{Gini}(P_{Y|X\leq s}) + \Pr\{X> s\}\operatorname{Gini}(P_{Y|X> s})\right]
\end{align}


```python
def drop_in_gini(X, Y, split_pt):
    '''Returns the drop in Gini impurity of Y for the split X <= split_pt.
    
    Parameters
    ----------
    X: 1D array the values of a feature for different instances
    Y: 1D array of the corresponding target values
    split_pt: the value of the split point
    '''
    S = X <= split_pt
    q = S.mean()
    return gini(dist(Y)) - q * gini(dist(Y[S])) - (1 - q) * gini(dist(Y[~S]))

X, Y = iris_df['petal width (cm)'], iris_df.target
print(f"Drop in Gini: {drop_in_gini(X, Y, 0.8):.4g}")
```

To compute the best split point for a feature, we check every consecutive mid-points of the possible feature values:


```python
def find_best_split_pt(X, Y, gain_function):
    '''Return the best split point s and the maximum gain evaluated using 
    gain_function for the split X <= s and target Y.
    
    Parameters
    ----------
    X: 1D array the values of a feature for different instances
    Y: 1D array of the corresponding target values
    gain_function: a function such as drop_in_gini for evaluating a split
    
    Returns
    -------
    A tuple (s, g) where s is the best split point and g is the maximum gain.
    
    See also
    --------
    drop_in_gini
    '''
    values = np.sort(np.unique(X))
    split_pts = (values[1:] + values[:-1]) / 2
    gain = np.array([gain_function(X, Y, s) for s in split_pts])
    max_index = np.argmax(gain)
    return split_pts[max_index], gain[max_index]


print('''Best split point: {0:.4g}
Maximum gain: {1:.4g}'''.format(*find_best_split_pt(X, Y, drop_in_gini)))
```

The following ranks the features according to the gains of their best binary splits:


```python
rank_by_gini = pd.DataFrame({
    'feature': feature,
    **(lambda s, g: {
        'split point': s,
        'gain': g
    })(*find_best_split_pt(iris_df[feature], iris_df.target, drop_in_gini))
} for feature in iris.feature_names).sort_values(by='gain', ascending=False)
rank_by_gini
```

**Exercise** Complete the following function to calculate the *information gain* for a binary split $X\leq s$ and target $Y$:

\begin{align}
\operatorname{Gain}_{X\leq s}(Y) := h(P_Y) - \left[\Pr(X\leq s) h(P_{Y|X\leq s}) + \Pr(X> s) h(P_{Y|X> s})\right].
\end{align}

You may use `dist` and `entropy` defined previously.


```python
def info_gain(X, Y, split_pt):
    '''Returns the information Gain of Y for the split X <= split_pt.
    
    Parameters
    ----------
    X: 1D array the values of a feature for different instances
    Y: 1D array of the corresponding target values
    split_pt: the value of the split point
    '''
    S = X <= split_pt
    q = S.mean()
    # YOUR CODE HERE
    raise NotImplementedError()
    
print(f"Information gain: {info_gain(X, Y, 0.8):.4g}")
```


```python
# tests
rank_by_entropy = pd.DataFrame({
    'feature':
    feature,
    **(lambda s, g: {
        'split point': s,
        'gain': g
    })(*find_best_split_pt(iris_df[feature], iris_df.target, info_gain))
} for feature in iris.feature_names).sort_values(by='gain', ascending=False)
rank_by_entropy
```

**Exercise** Complete the following function to calculate the *information gain ratio* for a binary split $X\leq s$ and target $Y$:

\begin{align}
\operatorname{GainRatio}_{X\leq s}(Y) &:= \frac{\operatorname{Gain}_{X\leq s}(Y)}{\operatorname{SplitInfo}(X\leq s)} \qquad\text{where}\\
\operatorname{SplitInfo}(X\leq s) &:= h(\Pr(X\leq s),\Pr(X> s)).
\end{align}

You may use `entropy` and `info_gain` defined previously.


```python
def info_gain_ratio(X, Y, split_pt):
    S = X <= split_pt
    q = S.mean()
    # YOUR CODE HERE
    raise NotImplementedError()
```


```python
# tests
rank_by_info_gain_ratio = pd.DataFrame({
    'feature':
    feature,
    **(lambda s, g: {
        'split point': s,
        'gain': g
    })(*find_best_split_pt(iris_df[feature], iris_df.target, info_gain_ratio))
} for feature in iris.feature_names).sort_values(by='gain', ascending=False)
rank_by_info_gain_ratio
```

**Exercise** Does the information gain ratio give a different ranking of the features? Why?

Information gain ratio gives the same ranking as information gain in this case. This is because the split is restricted to be binary and so the normalization by split information has less effect on the ranking.

537f45220557173a893743c217756172a7dbccee
ipynb
Jupyter Notebook
Tutorial3/Decision Tree Induction with scikit-learn.ipynb
ccha23/cs5483
e8fa9d9b8a0545696958ca87c2c9a8a133109191
MIT
Tutorial3/Decision Tree Induction with scikit-learn.ipynb
ccha23/cs5483
e8fa9d9b8a0545696958ca87c2c9a8a133109191
MIT
2021-04-19T09:21:04.000Z
2021-04-19T09:21:06.000Z
Tutorial3/Decision Tree Induction with scikit-learn.ipynb
ccha23/cs5483
e8fa9d9b8a0545696958ca87c2c9a8a133109191
MIT
2022-03-20T05:25:45.000Z
2022-03-20T05:25:45.000Z
Qwen/Qwen-72B
1. YES
2. YES