The goal of this notebook is to implement your own binary decision tree classifier. You will:
Important Note: In this assignment, we will focus on building decision trees where the data contain only binary (0 or 1) features. This allows us to avoid dealing with:
In [97]:
import json
import numpy as np
import pandas as pd
import matplotlib as mpl
import matplotlib.pyplot as plt
import seaborn as sns
sns.set_style('darkgrid')
%matplotlib inline
We will be using a dataset from the LendingClub. A parsed and cleaned form of the dataset is availiable here. Make sure you download the dataset before running the following command.
In [98]:
loans = pd.read_csv("lending-club-data_assign_2.csv")
The target column (label column) of the dataset that we are interested in is called bad_loans. In this column 1 means a risky (bad) loan 0 means a safe loan.
In order to make this more intuitive and consistent with the lectures, we reassign the target to be:
We put this in a new column called safe_loans.
In [99]:
# safe_loans = 1 => safe
# safe_loans = -1 => risky
loans['safe_loans'] = loans['bad_loans'].apply(lambda x : +1 if x==0 else -1)
loans = loans.drop('bad_loans', 1)
Unlike the previous assignment where we used several features, in this assignment, we will just be using 4 categorical features:
Since we are building a binary decision tree, we will have to convert these categorical features to a binary representation in a subsequent section using 1-hot encoding.
In [100]:
features = ['grade', # grade of the loan
'term', # the term of the loan
'home_ownership', # home_ownership status: own, mortgage or rent
'emp_length', # number of years of employment
]
target = 'safe_loans'
loans = loans[features + [target]]
Now, let's look at the head of the dataset.
In [101]:
loans.head(5)
Out[101]:
Before performing analysis on the data, we need to perform one-hot encoding for all of the categorical data. Once the one-hot encoding is performed on all of the data, we will split the data into a training set and a validation set.
In [102]:
loans_one_hot_enc = pd.get_dummies(loans)
Let's explore what the "grade_A" column looks like.
In [103]:
loans_one_hot_enc["grade_A"].head(5)
Out[103]:
This column is set to 1 if the loan grade is A and 0 otherwise.
Loading the JSON files with the indicies from the training data and the test data into a list.
In [104]:
with open('module-5-assignment-2-train-idx.json', 'r') as f:
train_idx_lst = json.load(f)
train_idx_lst = [int(entry) for entry in train_idx_lst]
In [105]:
with open('module-5-assignment-2-test-idx.json', 'r') as f:
test_idx_lst = json.load(f)
test_idx_lst = [int(entry) for entry in test_idx_lst]
Using the list of the training data indicies and the test data indicies to get a DataFrame with the training data and a DataFrame with the test data.
In [106]:
train_data = loans_one_hot_enc.ix[train_idx_lst]
test_data = loans_one_hot_enc.ix[test_idx_lst]
In this section, we will implement binary decision trees from scratch. There are several steps involved in building a decision tree. For that reason, we have split the entire assignment into several sections.
Recall from the lecture that prediction at an intermediate node works by predicting the majority class for all data points that belong to this node.
Now, we will write a function that calculates the number of missclassified examples when predicting the majority class. This will be used to help determine which feature is the best to split on at a given node of the tree.
Note: Keep in mind that in order to compute the number of mistakes for a majority classifier, we only need the label (y values) of the data points in the node.
Steps to follow :
Now, let us write the function intermediate_node_num_mistakes which computes the number of misclassified examples of an intermediate node given the set of labels (y values) of the data points contained in the node. Fill in the places where you find ## YOUR CODE HERE. There are three places in this function for you to fill in.
In [107]:
def intermediate_node_num_mistakes(labels_in_node):
# Corner case: If labels_in_node is empty, return 0
if len(labels_in_node) == 0:
return 0
# Count the number of 1's (safe loans)
N_count_plu_1 = (labels_in_node == 1).sum()
# Count the number of -1's (risky loans)
N_count_neg_1 = (labels_in_node == -1).sum()
# Return the number of mistakes that the majority classifier makes.
return min(N_count_plu_1, N_count_neg_1)
Because there are several steps in this assignment, we have introduced some stopping points where you can check your code and make sure it is correct before proceeding. To test your intermediate_node_num_mistakes function, run the following code until you get a Test passed!, then you should proceed. Otherwise, you should spend some time figuring out where things went wrong.
In [108]:
# Test case 1
example_labels = np.array([-1, -1, 1, 1, 1])
if intermediate_node_num_mistakes(example_labels) == 2:
print 'Test passed!'
else:
print 'Test 1 failed... try again!'
# Test case 2
example_labels = np.array([-1, -1, 1, 1, 1, 1, 1])
if intermediate_node_num_mistakes(example_labels) == 2:
print 'Test passed!'
else:
print 'Test 2 failed... try again!'
# Test case 3
example_labels = np.array([-1, -1, -1, -1, -1, 1, 1])
if intermediate_node_num_mistakes(example_labels) == 2:
print 'Test passed!'
else:
print 'Test 3 failed... try again!'
The function best_splitting_feature takes 3 arguments:
The function will loop through the list of possible features, and consider splitting on each of them. It will calculate the classification error of each split and return the feature that had the smallest classification error when split on.
Recall that the classification error is defined as follows: $$ \mbox{classification error} = \frac{\mbox{# mistakes}}{\mbox{# total examples}} $$
Follow these steps:
This may seem like a lot, but we have provided pseudocode in the comments in order to help you implement the function correctly.
Note: Remember that since we are only dealing with binary features, we do not have to consider thresholds for real-valued features. This makes the implementation of this function much easier.
Fill in the places where you find ## YOUR CODE HERE. There are five places in this function for you to fill in.
In [109]:
def best_splitting_feature(data, features, target):
best_feature = None # Keep track of the best feature
best_error = 10 # Keep track of the best error so far
# Note: Since error is always <= 1, we should intialize it with something larger than 1.
# Convert to float to make sure error gets computed correctly.
num_data_points = float(len(data))
# Loop through each feature to consider splitting on that feature
for feature in features:
# The left split will have all data points where the feature value is 0
left_split = data[data[feature] == 0]
# The right split will have all data points where the feature value is 1
right_split = data[data[feature] == 1]
# Calculate the number of misclassified examples in the left split.
# Remember that we implemented a function for this! (It was called intermediate_node_num_mistakes)
left_mistakes = intermediate_node_num_mistakes(left_split[target].values)
# Calculate the number of misclassified examples in the right split.
right_mistakes = intermediate_node_num_mistakes(right_split[target].values)
# Compute the classification error of this split.
# Error = (# of mistakes (left) + # of mistakes (right)) / (# of data points)
error = (left_mistakes + right_mistakes)/num_data_points
# If this is the best error we have found so far, store the feature as best_feature and the error as best_error
if error < best_error:
best_error = error
best_feature = feature
return best_feature # Return the best feature we found
Now, creating a list of the features we are considering for the decision tree to test the above function. Not including the 0th element on the list since it corresponds to the "safe loans" column, the label we are trying to predict.
In [110]:
feature_lst = train_data.columns.values.tolist()[1:]
print feature_lst
To test your best_splitting_feature function, run the following code:
In [111]:
if best_splitting_feature(train_data, feature_lst, 'safe_loans') == 'term_ 36 months':
print 'Test passed!'
else:
print 'Test failed... try again!'
With the above functions implemented correctly, we are now ready to build our decision tree. Each node in the decision tree is represented as a dictionary which contains the following keys and possible values:
{
'is_leaf' : True/False.
'prediction' : Prediction at the leaf node.
'left' : (dictionary corresponding to the left tree).
'right' : (dictionary corresponding to the right tree).
'splitting_feature' : The feature that this node splits on.
}
First, we will write a function that creates a leaf node given a set of target values. Fill in the places where you find ## YOUR CODE HERE. There are three places in this function for you to fill in.
In [112]:
def create_leaf(target_values):
# Create a leaf node
leaf = {'splitting_feature' : None,
'left' : None,
'right' : None,
'is_leaf': True }
# Count the number of data points that are +1 and -1 in this node.
num_ones = (target_values == 1).sum()
num_minus_ones = (target_values == -1).sum()
# For the leaf node, set the prediction to be the majority class.
# Store the predicted class (1 or -1) in leaf['prediction']
if num_ones > num_minus_ones:
leaf['prediction'] = 1
else:
leaf['prediction'] = -1
# Return the leaf node
return leaf
We have provided a function that learns the decision tree recursively and implements 3 stopping conditions:
Now, we will write down the skeleton of the learning algorithm. Fill in the places where you find ## YOUR CODE HERE. There are seven places in this function for you to fill in.
In [113]:
def decision_tree_create(data, features, target, current_depth = 0, max_depth = 10):
remaining_features = features[:] # Make a copy of the features.
target_values = data[target].values
print "--------------------------------------------------------------------"
print "Subtree, depth = %s (%s data points)." % (current_depth, len(target_values))
# Stopping condition 1
# (Check if there are mistakes at current node.
# Recall you wrote a function intermediate_node_num_mistakes to compute this.)
if intermediate_node_num_mistakes(target_values) == 0: ## YOUR CODE HERE
print "Stopping condition 1 reached."
# If not mistakes at current node, make current node a leaf node
return create_leaf(target_values)
# Stopping condition 2 (check if there are remaining features to consider splitting on)
if remaining_features == 0: ## YOUR CODE HERE
print "Stopping condition 2 reached."
# If there are no remaining features to consider, make current node a leaf node
return create_leaf(target_values)
# Additional stopping condition (limit tree depth)
if current_depth >= max_depth : ## YOUR CODE HERE
print "Reached maximum depth. Stopping for now."
# If the max tree depth has been reached, make current node a leaf node
return create_leaf(target_values)
# Find the best splitting feature (recall the function best_splitting_feature implemented above)
splitting_feature = best_splitting_feature(data, remaining_features, target)
# Split on the best feature that we found.
left_split = data[data[splitting_feature] == 0]
right_split = data[data[splitting_feature] == 1]
remaining_features.remove(splitting_feature)
print "Split on feature %s. (%s, %s)" % (\
splitting_feature, len(left_split), len(right_split))
# Create a leaf node if the split is "perfect"
if len(left_split) == len(data):
print "Creating leaf node."
return create_leaf(left_split[target])
if len(right_split) == len(data):
print "Creating leaf node."
return create_leaf(right_split[target])
# Repeat (recurse) on left and right subtrees
left_tree = decision_tree_create(left_split, remaining_features, target, current_depth + 1, max_depth)
right_tree = decision_tree_create(right_split, remaining_features, target, current_depth + 1, max_depth)
return {'is_leaf' : False,
'prediction' : None,
'splitting_feature': splitting_feature,
'left' : left_tree,
'right' : right_tree}
Here is a recursive function to count the nodes in your tree:
In [114]:
def count_nodes(tree):
if tree['is_leaf']:
return 1
return 1 + count_nodes(tree['left']) + count_nodes(tree['right'])
Run the following test code to check your implementation. Make sure you get 'Test passed' before proceeding.
In [115]:
small_data_decision_tree = decision_tree_create(train_data, feature_lst, 'safe_loans', max_depth = 3)
if count_nodes(small_data_decision_tree) == 13:
print 'Test passed!'
else:
print 'Test failed... try again!'
print 'Number of nodes found :', count_nodes(small_data_decision_tree)
print 'Number of nodes that should be there : 13'
In [116]:
my_decision_tree = decision_tree_create(train_data, feature_lst, 'safe_loans', max_depth = 6)
As discussed in the lecture, we can make predictions from the decision tree with a simple recursive function. Below, we call this function classify, which takes in a learned tree and a test point x to classify. We include an option annotate that describes the prediction path when set to True.
Fill in the places where you find ## YOUR CODE HERE. There is one place in this function for you to fill in.
In [117]:
def classify(tree, x, annotate = False):
# if the node is a leaf node.
if tree['is_leaf']:
if annotate:
print "At leaf, predicting %s" % tree['prediction']
return tree['prediction']
else:
# split on feature.
split_feature_value = x[tree['splitting_feature']]
if annotate:
print "Split on %s = %s" % (tree['splitting_feature'], split_feature_value)
if split_feature_value == 0:
return classify(tree['left'], x, annotate)
else:
return classify(tree['right'], x, annotate)
Now, let's consider the first example of the test set and see what my_decision_tree model predicts for this data point.
In [118]:
test_data.iloc[0]
Out[118]:
In [119]:
print 'Predicted class: %s ' % classify(my_decision_tree, test_data.iloc[0])
Let's add some annotations to our prediction to see what the prediction path was that lead to this predicted class:
In [120]:
classify(my_decision_tree, test_data.iloc[0], annotate=True)
Out[120]:
Quiz question: What was the feature that my_decision_tree first split on while making the prediction for test_data.iloc[0]?
In [121]:
print "term_ 36 months"
Quiz question: What was the first feature that lead to a right split of test_data[0]?
In [122]:
print "grade_D"
Quiz question: What was the last feature split on before reaching a leaf node for test_data[0]?
In [123]:
print "grade_D"
Now, we will write a function to evaluate a decision tree by computing the classification error of the tree on the given dataset.
Again, recall that the classification error is defined as follows: $$ \mbox{classification error} = \frac{\mbox{# mistakes}}{\mbox{# total examples}} $$
Now, write a function called evaluate_classification_error that takes in as input:
tree (as described above)data (an SFrame)This function should return a prediction (class label) for each row in data using the decision tree. Fill in the places where you find ## YOUR CODE HERE. There is one place in this function for you to fill in.
In [124]:
def evaluate_classification_error(tree, data):
# Apply the classify(tree, x) to each row in your data
predictions = data.apply(lambda x: classify(tree, x, annotate=False) , axis = 1)
# Once you've made the predictions, calculate the classification error and return it
number_mistakes = (predictions != data['safe_loans'].values).sum()
total_examples = float(len(predictions))
classification_error = number_mistakes/total_examples
return classification_error
Now, let's use this function to evaluate the classification error on the test set.
In [125]:
evaluate_classification_error(my_decision_tree, test_data)
Out[125]:
Quiz Question: Rounded to 2nd decimal point, what is the classification error of my_decision_tree on the test_data?
In [126]:
print "Classification error of my_decision_tree on \
the test_data: %.2f" %(evaluate_classification_error(my_decision_tree, test_data))
As discussed in the lecture, we can print out a single decision stump (printing out the entire tree is left as an exercise to the curious reader).
In [127]:
def print_stump(tree, name = 'root'):
split_name = tree['splitting_feature'] # split_name is something like 'term. 36 months'
if split_name is None:
print "(leaf, label: %s)" % tree['prediction']
return None
split_feature, split_value = split_name.split('_')
print ' %s' % name
print ' |---------------|----------------|'
print ' | |'
print ' | |'
print ' | |'
print ' [{0} == 0] [{0} == 1] '.format(split_name)
print ' | |'
print ' | |'
print ' | |'
print ' (%s) (%s)' \
% (('leaf, label: ' + str(tree['left']['prediction']) if tree['left']['is_leaf'] else 'subtree'),
('leaf, label: ' + str(tree['right']['prediction']) if tree['right']['is_leaf'] else 'subtree'))
In [128]:
print_stump(my_decision_tree)
Quiz Question: What is the feature that is used for the split at the root node?
In [129]:
print "term_ 36 months"
In [130]:
print_stump(my_decision_tree['left'], my_decision_tree['splitting_feature'])
In [131]:
print_stump(my_decision_tree['left']['left'], my_decision_tree['left']['splitting_feature'])
Quiz question: What is the path of the first 3 feature splits considered along the left-most branch of my_decision_tree?
In [132]:
print "term_ 36 months, grade_A, grade_B"
Quiz question: What is the path of the first 3 feature splits considered along the right-most branch of my_decision_tree?
In [133]:
print_stump(my_decision_tree['right'], my_decision_tree['splitting_feature'])
In [134]:
print_stump(my_decision_tree['right']['right'], my_decision_tree['right']['splitting_feature'])
In [135]:
print "term_ 36 months, grade_D, no third feature because second split resulted in leaf"
In [ ]: