Decision trees: entropy and information gain
A decision tree classifies an example by asking a series of questions about its features, following a branch for each answer until it reaches a leaf with a prediction. The tree is learned from data by choosing, at each node, the question that best separates the classes.
Python
import math
rows = [
("sunny", False, "no"),
("sunny", True, "no"),
("overcast", False, "yes"),
("rain", False, "yes"),
("rain", False, "yes"),
("rain", True, "no"),
("overcast", True, "yes"),
("sunny", False, "no"),
]
def entropy(labels):
total = len(labels)
return -sum((labels.count(v) / total) * math.log2(labels.count(v) / total) for v in set(labels))
def gain(rows, index):
remainder = 0.0
for value in set(row[index] for row in rows):
subset = [row[-1] for row in rows if row[index] == value]
remainder += len(subset) / len(rows) * entropy(subset)
return entropy([row[-1] for row in rows]) - remainder
print(round(entropy([row[-1] for row in rows]), 3))
gains = {"outlook": gain(rows, 0), "windy": gain(rows, 1)}
print({name: round(value, 3) for name, value in gains.items()})
print(max(gains, key=gains.get))