Click to Flip Card
Decision Tree
How is probability defined in general terms? Is Entropy a measure of how mixed a collection is? What does Probability Distribution represents? What does Information Gain measure?
Probability
Probability is the chance of something to happen. When you flip a coin, there is a probability of 0.5 (or 50% chance) to land on heads. It's like asking, "What are the chances of something to happen?" Probability is a number between 0 and 1, where 0 means "no way" and 1 means "definitely happening". $$ P(\text{Heads}) = \frac{1}{2} = 0.5 $$
# Coin Flip events
events = ['head', 'tail']
# Probability distribution (coin flip):
print('Head =', 1/2)
print('Tail =', 1/len(events))
"""
Head = 0.5
Tail = 0.5
"""
Probability Distribution
Now, imagine you're not just flipping a coin but rolling a dice. There are more outcomes (1 through 6), each with its own probability. A probability distribution is a list with all these probabilities. It's like a map with all the possible outcomes and how likely they are. $$ P(\text{Rolling a 4}) = \frac{1}{6} $$
import pandas as pd
from icecream import ic
# Datasets
A = ['apple']*1 + ['orange']*2 + ['banana']*2
B = ['apple']*5 + ['orange']*2 + ['banana']*0
ic(A, B)
# Probability distribution (by hand)
P1 = [{'apple': 1/5}, {'orange': 2/5}, {'banana': 2/5}]
P2 = [{'apple': 5/7}, {'orange': 2/7}]
ic(P1, P2)
# With pandas
P1 = pd.Series(A).value_counts(normalize=True)
P2 = pd.Series(B).value_counts(normalize=True)
ic(P1, P2);
"""
ic| A: ['apple', 'orange', 'orange', 'banana', 'banana']
B: ['apple', 'apple', 'apple', 'apple', 'apple', 'orange', 'orange']
ic| P1: [{'apple': 0.2}, {'orange': 0.4}, {'banana': 0.4}]
P2: [{'apple': 0.7142857142857143}, {'orange': 0.2857142857142857}]
ic| P1: orange 0.4
banana 0.4
apple 0.2
dtype: float64
P2: apple 0.714286
orange 0.285714
dtype: float64
"""
Entropy
Entropy is a measure of how disordered a collection is. The more impure the feature is, the higher the entropy. Probability distribution is the frequency of the unique values. It turns out that a logarithm of the number of states is perfect for compute entropy. $$ H(X) = -\sum_{i=1}^{n} P(x_i) \log_2 P(x_i) $$
import pandas as pd
import numpy as np
from icecream import ic
# Set the initial traning data
A = ['apple']*1 + ['orange']*2 + ['banana']*2
B = ['apple']*5 + ['orange']*2 + ['banana']*0
ic(A, B)
# Probability
P1 = pd.Series(A).value_counts(normalize=True)
P2 = pd.Series(B).value_counts(normalize=True)
ic(P1, P2)
# Entropy (Shannon model)
P1 = P1.values
P2 = P2.values
H1 = -1 * np.sum(P1 * np.log2(P1))
H2 = -1 * np.sum(P2 * np.log2(P2))
ic(H1, H2);
assert H1 > H2
ic("A entropy > B entropy | There is more disorder in A than B")
ic("Assertion passed");
"""
ic| A: ['apple', 'orange', 'orange', 'banana', 'banana']
B: ['apple', 'apple', 'apple', 'apple', 'apple', 'orange', 'orange']
ic| P1: orange 0.4
banana 0.4
apple 0.2
dtype: float64
P2: apple 0.714286
orange 0.285714
dtype: float64
ic| H1: 1.5219280948873621, H2: 0.863120568566631
ic| 'A entropy > B entropy | There is more disorder in A than B'
ic| 'Assertion passed'
"""
Information gain
Information gain is a measure of the reduction in entropy. As the entropy of an attribute increases, the information gain decreases. $$ \text{IG}(X, A) = \text{H}(X) - \sum_{v \in \text{Values}(A)} \frac{|X_v|}{|X|} \cdot \text{H}(X_v) $$
""" Decision Trees / Info Gain
Target: Play Tennis or not
Information gain example (for feature 'wind'):
IG = H - (8/14)H_weak - (6/14)H_strong
IG = 0.940 - (8/14)0.811 - (6/14)1.00 = 0.048
"""
import numpy as np
import pandas as pd
import pathlib
# Load the dataset from a CSV file
DIR = pathlib.Path(__file__).resolve().parent
df = pd.read_csv(DIR / 'data/play_tennis.csv')
# Split the dataset into features (X) and target (y), play tennis yes/no
X = df.drop(['play'], axis=1)
y = df['play']
# Total entropy
def dataset_entropy(df):
E = 0
N = df['play'].value_counts() # yes: 9, no: 5
values = df['play'].unique()
for v in values: # yes/no
P = N[v]/len(df['play']) # probability
E += -P*np.log2(P)
return E
# Entropy for each attribute
def attribute_entropy(attr):
E = 0
eps = np.finfo(float).eps # machine epsilon for the float
targets = df.play.unique()
values = df[attr].unique()
for v in values: # cool/hot
ent = 0
for t in targets: # yes,no
num = len(df[attr][df[attr] == v][df.play == t]) # numerator
den = len(df[attr][df[attr] == v])
fraction = num/(den + eps)
ent += -fraction*np.log2(fraction + eps) # entropy for one feature
E += -(den/len(df))*ent # sum of all entropies
return abs(E)
total_entropy = dataset_entropy(df)
# Get the names of attributes (excluding the target variable)
attributes = df.keys()[:-1]
# Calculate entropy for each attribute and store it in a dictionary
E = {}
for k in attributes:
E[k] = attribute_entropy(k)
# Calculate information gain for each attribute and store it in a dictionary
IG = {}
for k in E:
IG[k] = total_entropy - E[k]
# Asserts
assert E['outlook'] < E['humidity']
assert IG['outlook'] > IG['humidity']
# Output results
print("\n Dataset:"); print(df)
print("\n Describe:"); print(df.describe())
print("\n Entropy:"); print(total_entropy)
print("\n AttrEntropy:"); print(E)
print("\n Information gains:"); print(IG)
"""
Dataset:
outlook temp humidity windy play
0 sunny hot high False no
1 sunny hot high True no
2 overcast hot high False yes
3 rainy mild high False yes
4 rainy cool normal False yes
5 rainy cool normal True no
6 overcast cool normal True yes
7 sunny mild high False no
8 sunny cool normal False yes
9 rainy mild normal False yes
10 sunny mild normal True yes
11 overcast mild high True yes
12 overcast hot normal False yes
13 rainy mild high True no
Describe:
outlook temp humidity windy play
count 14 14 14 14 14
unique 3 3 2 2 2
top sunny mild high False yes
freq 5 6 7 8 9
Entropy:
0.9402859586706311
AttrEntropy:
{'outlook': 0.6935361388961914,
'temp': 0.9110633930116756,
'humidity': 0.7884504573082889,
'windy': 0.892158928262361}
Information gains:
{'outlook': 0.24674981977443977,
'temp': 0.029222565658955535,
'humidity': 0.15183550136234225,
'windy': 0.048127030408270155}
"""
Decision Tree ID3
We build a decision tree recursively giving priority to the attributes with the higher IG. Iterative Dichotomiser 3 is a classification algorithm. It follows a greedy approach of building a decision tree. It gives priority to the attributes with the higher information gain.
""" Decision Trees / ID3 Algorithm
1. Calculate entropy for dataset
2. For each attribute:
Calculate entropy for all categorical values
Calculate information gain for the current attribute
3. Find the feture with maximum information gain
4. Repeat
For example, the `outlook` has the highest info gain (0.24).
It we will select it as the root node for the start level of splitting.
"""
import numpy as np
import pandas as pd
import pathlib
from sklearn import tree
# Dataset
DIR = pathlib.Path(__file__).resolve().parent
df = pd.read_csv(DIR / 'data/play_tennis.csv')
# Training data
X = df.drop(['play'], axis=1)
y = df['play']
# Total entropy (for current dataframe)
def dataset_entropy(df):
E = 0
N = df['play'].value_counts() # yes: 9, no: 5
values = df['play'].unique()
for v in values: # yes/no
P = N[v]/len(df['play']) # probability
E += -P*np.log2(P)
return E
# Entropy for each attribute
def attribute_entropy(df, attr):
E = 0
eps = np.finfo(float).eps # machine epsilon for the float
targets = df.play.unique()
values = df[attr].unique()
for v in values: # cool/hot
ent = 0
for t in targets: # yes,no
num = len(df[attr][df[attr] == v][df.play == t]) # numerator
den = len(df[attr][df[attr] == v])
fraction = num/(den + eps)
ent += -fraction*np.log2(fraction + eps) # entropy for one feature
E += -(den/len(df))*ent # sum of all entropies
return abs(E)
# Find attribute with maximum information gain
def find_winner(df):
IG = {}
attributes = df.keys()[:-1]
# Loop for attributes in dataframe and compute info gains
for attr in attributes:
IG[attr] = dataset_entropy(df) - attribute_entropy(df, attr)
winner = attributes[np.argmax(IG)] # maxim info gains
return winner
# Construct the decision tree (dictionary)
def buildTree(df):
tree = {}
# Target column
Class = df.keys()[-1] # play
# Maximum info gain
node = find_winner(df) # outlook
tree[node] = {}
# Distinct values
values = np.unique(df[node]) # overcast/rain
# Loop throw the attribute values
for value in values:
subtable = df[df[node] == value].reset_index(drop=True)
attr_values, counts = np.unique(subtable[Class], return_counts=True)
if len(counts) == 1: # pure subset
tree[node][value] = attr_values[0]
else:
subtable = subtable.drop(node, axis=1)
tree[node][value] = buildTree(subtable) # Recursive case
return tree
decision_tree = buildTree(df)
# Print dictionary tree (recursion in case of subtrees)
def print_tree(tree, attr=None, i=0):
if not attr:
attr = next(iter(tree)) # attrribute in the current tree node
for key, subval in tree[attr].items():
if isinstance(subval, str): # Base case
print(i*" ", attr, "=", key, ":", subval)
continue
print(i*" ", attr, "=", key, ":")
print_tree(subval, i=i+1) # Recursive
return
# Predict unknow (only for cases included in the train dataset)
def predict(X, tree):
key = next(iter(tree))
val = X[key]
subval = tree[key][val]
if isinstance(subval, str): # Base case
return subval
subval = predict(X, subval) # Recursive
return subval
print("\n Decistion Tree:")
print(decision_tree, "\n")
print_tree(decision_tree)
print("\n Example usage 1:")
x = {'outlook': 'sunny', 'temp': 'mild', 'humidity': 'high', 'windy': False}
y = predict(x, decision_tree)
print("Attributes:", x)
print("Prediction:", y)
print("\n Example usage 2:")
x = {'outlook': 'rainy', 'temp': 'mild', 'humidity': 'normal', 'windy': True}
y = predict(x, decision_tree)
print("Attributes:", x)
print("Prediction:", y)
"""
Decistion Tree:
{'outlook': {'overcast': 'yes', 'rainy': {'temp': {'cool': {'humidity': ...
outlook = overcast: yes
outlook = rainy:
temp = cool:
humidity = normal:
windy = False: yes
windy = True: no
temp = mild:
humidity = high:
windy = False: yes
windy = True: no
humidity = normal: yes
outlook = sunny:
temp = cool: yes
temp = hot: no
temp = mild:
humidity = high: no
humidity = normal: yes
Example usage 1:
Attributes: {
'outlook': 'sunny',
'temp': 'mild',
'humidity': 'high',
'windy': False}
Prediction: no
Example usage 2:
Attributes: {
'outlook': 'rainy',
'temp': 'mild',
'humidity': 'normal',
'windy': True}
Prediction: yes
"""
Last update: 218 days ago
