{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"# Information and Entropy\n",
"\n",
"Welcome! This workshop is from [WinderResearch.com](https://WinderResearch.com/?utm_source=winderresearch&utm_medium=notebook&utm_campaign=workshop&utm_term=individual). Sign up to receive more free workshops, training and videos.\n",
"\n",
"Remember the goal of data science. The goal is to make a decision based upon some data. The quality of that decision depends on our information. If we have good, clear information then we can make well informed decisions. If we have bad, messy data then our decisions will be poor.\n",
"\n",
"## Classification\n",
"\n",
"In the context of classification, which is the the attempt to predict which _class_ an observation belongs to, we can be more certain about a result if our algorithm is able to separate the classes _cleanly_.\n",
"\n",
"One measure of how _clean_ or _pure_ a collection of classes are is Entropy.\n",
"\n",
"In this workshop we will mathematically define entropy, which is a measure of the amount of information that can be stored in a limited number of bits."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"import numpy as np # Numpy is a general purpose mathematical library for Python. \n",
" # Most higher level data science libraries use Numpy under the bonnet."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"14.2857142857\n",
"1225.06122449\n"
]
}
],
"source": [
"X = np.array([0, 0, 1, 1, -1, -1, 100]) # Create an array. All numpy funcitons expect the data in a Numpy array.\n",
"print(np.mean(X))\n",
"print(np.var(X))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Entropy\n",
"\n",
"Remember entrpopy is defined as:\n",
"\n",
"$$H=-\\sum(p_i \\log_2 (p_i))$$\n",
"\n",
"Where \\\\(p_i\\\\) is the probability that the observation belongs to class \\\\(i\\\\). (i.e. $p(y==c)/n$, where y is the target, c is the class of interest and n is the total number of samples)\n",
"\n",
"For example, if we have two classes:\n",
"\n",
"$$H=-p_1 \\log_2 (p_1)-p_2 \\log_2 (p_2)$$\n",
"\n",
"\n",
"### Task\n",
"\n",
"- Read through this code and understand what is going on.\n",
"- Try calculating the entropy of another array of values. What happens when you add more values? Change values?"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"X = np.array([[4.2, 92], [6.4, 102], [3.5, 3], [4.7, 10]]) # Numpy arrays are general purpose mathematical arrays\n",
"y = np.array([0, 0, 1, 1]) # They implement all kinds of useful operators, like the == operator."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def entropy(y):\n",
" probs = [] # Probabilities of each class label\n",
" for c in set(y): # Set gets a unique set of values. We're iterating over each value\n",
" num_same_class = sum(y == c) # Remember that true == 1, so we can sum.\n",
" p = num_same_class / len(y) # Probability of this class label\n",
" probs.append(p)\n",
" return np.sum(-p * np.log2(p) for p in probs)"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1.0\n"
]
}
],
"source": [
"print(entropy(y)) # Should be 1.0"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Information gain\n",
"\n",
"Imagine we had some data like that of `X` and `y` above, where `X` are the fetures and `y` are the class labels.\n",
"\n",
"We could propose a threshold or a rule that would split the data in `X` to separate the classes. How would we quantify which was the best split?\n",
"\n",
"What we can do is compare the entropy of the parent before the split against the weighted combination of the entropy after the split. I.e. if three observations end up in the left bucket and one in the right, then the left bucket will account for three quarters of the child's entropy.\n",
"\n",
"If we subtract the parent entropy from the weighted child's entroy, we're left with a measure of _improvement_. This is called the _information gain_.\n",
"\n",
"The information gain is defined as the parent entropy minus the weighted entropy of the subgroups.\n",
"\n",
"$$\n",
"\\begin{align}\n",
"IG(parent, children) = & entropy(parent) - \\nonumber \\\\\\\\\n",
"& \\left(p(c_1)entropy(c_1) + p(c_2)entropy(c_2) + ...\\right)\n",
"\\end{align}\n",
"$$\n",
"\n",
"### Tasks:\n",
"\n",
"- Given the following `information_gain` function (understand it) pick some splits and calculate the information gain. Which is better?"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def information_gain(parent, left_split, right_split):\n",
" return entropy(parent) - (len(left_split) / len(parent)) * entropy(left_split) - (len(right_split) / len(parent)) * entropy(right_split)"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0.31\n"
]
}
],
"source": [
"# Make a split around the first column, < 5.0:\n",
"split1 = information_gain(y, y[X[:, 0] < 5.0], y[X[:, 0] > 5.0])\n",
"print(\"%0.2f\" % split1) # Should be 0.31"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1.0\n",
"Split 2 is better\n"
]
}
],
"source": [
"# Make a split around the second column, < 50.0:\n",
"split2 = information_gain(y, y[X[:, 1] < 50], y[X[:, 1] > 50])\n",
"print(split2) # Should be 1.0\n",
"print(\"Split %d is better\" % ((split1 < split2) + 1)) # Split 2 should be better, higher information gain"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.2"
}
},
"nbformat": 4,
"nbformat_minor": 1
}