import graphlab

"""
Explanation: Decision Trees in Practice

Implement binary decision trees with different early stopping methods.
Compare models with different stopping parameters.
Visualize the concept of overfitting in decision trees.

Fire up GraphLab Create
End of explanation
"""


loans = graphlab.SFrame('lending-club-data.gl/')

"""
Explanation: Load LendingClub Dataset
End of explanation
"""


loans['safe_loans'] = loans['bad_loans'].apply(lambda x : +1 if x==0 else -1)
loans = loans.remove_column('bad_loans')

"""
Explanation: reassign the labels to have +1 for a safe loan, and -1 for a risky (bad) loan.
End of explanation
"""


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]]

"""
Explanation: use 4 categorical features: 
1. grade of the loan 
2. the length of the loan term
3. the home ownership status: own, mortgage, rent
4. number of years of employment.
In the dataset, each of these features is a categorical feature. I will convert this to binary data in a subsequent section using 1-hot encoding.
End of explanation
"""


safe_loans_raw = loans[loans[target] == 1]
risky_loans_raw = loans[loans[target] == -1]

percentage = len(risky_loans_raw)/float(len(safe_loans_raw))
safe_loans = safe_loans_raw.sample(percentage, seed = 1)
risky_loans = risky_loans_raw
loans_data = risky_loans.append(safe_loans)

print "Percentage of safe loans                 :", len(safe_loans) / float(len(loans_data))
print "Percentage of risky loans                :", len(risky_loans) / float(len(loans_data))
print "Total number of loans in our new dataset :", len(loans_data)

"""
Explanation: Subsample dataset to make sure classes are balanced
undersample the larger class (safe loans) in order to balance out our dataset.
End of explanation
"""


loans_data = risky_loans.append(safe_loans)
for feature in features:
    loans_data_one_hot_encoded = loans_data[feature].apply(lambda x: {x: 1})    
    loans_data_unpacked = loans_data_one_hot_encoded.unpack(column_name_prefix=feature)
    # Change None's to 0's
    for column in loans_data_unpacked.column_names():
        loans_data_unpacked[column] = loans_data_unpacked[column].fillna(0)
    loans_data.remove_column(feature)
    loans_data.add_columns(loans_data_unpacked)

"""
Explanation: Transform categorical data into binary features
End of explanation
"""


features = loans_data.column_names()
features.remove('safe_loans')  # Remove the response variable
features

"""
Explanation: The feature columns now look like this:
End of explanation
"""


train_data, validation_set = loans_data.random_split(.8, seed=1)

"""
Explanation: Train-Validation split
I split the data into a train-validation split with 80% of the data in the training set and 20% of the data in the validation set.
End of explanation
"""


def reached_minimum_node_size(data, min_node_size):
    if len(data)<=min_node_size:
        return True
    else:
        return False

"""
Explanation: Early stopping methods for decision trees
3 early stopping methods:

Reached a maximum depth. (set by parameter max_depth).
Reached a minimum node size. (set by parameter min_node_size).
Don't split if the gain in error reduction is too small. (set by parameter min_error_reduction).

Early stopping condition 1: Maximum depth
Early stopping condition 2: Minimum node size
The function reached_minimum_node_size takes 2 arguments:

The data (from a node)
The minimum number of data points that a node is allowed to split on, min_node_size.

This function simply calculates whether the number of data points at a given node is less than or equal to the specified minimum node size. This function will be used to detect this early stopping condition in the decision_tree_create function.
End of explanation
"""


def error_reduction(error_before_split, error_after_split):
    return error_before_split-error_after_split

"""
Explanation: Early stopping condition 3: Minimum gain in error reduction
The function error_reduction takes 2 arguments:

The error before a split, error_before_split.
The error after a split, error_after_split.

This function computes the gain in error reduction, i.e., the difference between the error before the split and that after the split. This function will be used to detect this early stopping condition in the decision_tree_create function.
End of explanation
"""


def intermediate_node_num_mistakes(labels_in_node):
    if len(labels_in_node) == 0:
        return 0
    no_safe_loans = (labels_in_node == 1).sum()
    no_risky_loans = (labels_in_node == -1).sum()
    if no_safe_loans > no_risky_loans :
        return no_risky_loans
    else:
        return no_safe_loans

def best_splitting_feature(data, features, target):
    best_feature = None
    best_error = 10 
    num_data_points = float(len(data))  
    for feature in features:
        left_split = data[data[feature] == 0]
        right_split =  data[data[feature] == 1]
        left_mistakes = intermediate_node_num_mistakes(left_split[target])             
        right_mistakes = intermediate_node_num_mistakes(right_split[target])
        error = (left_mistakes+right_mistakes)/num_data_points
        if error < best_error:
            best_error = error
            best_feature = feature
    return best_feature 

def create_leaf(target_values):
    leaf = {'splitting_feature' : None,
            'left' : None,
            'right' : None,
            'is_leaf': None,
            'prediction' : None}
    num_ones = len(target_values[target_values == +1])
    num_minus_ones = len(target_values[target_values == -1])
    if num_ones > num_minus_ones:
        leaf['prediction'] = 1          
    else:
        leaf['prediction'] = -1     
    leaf['is_leaf'] = True     
    return leaf 

"""
Explanation: Binary decision tree helper functions
End of explanation
"""


def decision_tree_create(data, features, target, current_depth = 0, 
                         max_depth = 10, min_node_size=1, 
                         min_error_reduction=0.0):
    remaining_features = features[:]
    target_values = data[target]
    print "--------------------------------------------------------------------"
    print "Subtree, depth = %s (%s data points)." % (current_depth, len(target_values))
      
    # Stopping condition 1: All nodes are of the same type.
    if intermediate_node_num_mistakes(target_values) == 0:
        print "Stopping condition 1 reached. All data points have the same target value."                
        return create_leaf(target_values)
    
    # Stopping condition 2: No more features to split on.
    if remaining_features == []:
        print "Stopping condition 2 reached. No remaining features."                
        return create_leaf(target_values)    
    
    # Early stopping condition 1: Reached max depth limit.
    if current_depth >= max_depth:
        print "Early stopping condition 1 reached. Reached maximum depth."
        return create_leaf(target_values)
    
    # Early stopping condition 2: Reached the minimum node size.
    if reached_minimum_node_size(data,min_node_size):   
        print "Early stopping condition 2 reached. Reached minimum node size."
        return create_leaf(target_values)
    
    splitting_feature = best_splitting_feature(data, features, target) 
    left_split = data[data[splitting_feature] == 0]
    right_split = data[data[splitting_feature] == 1]
    error_before_split = intermediate_node_num_mistakes(target_values) / float(len(data))
    left_mistakes = intermediate_node_num_mistakes(left_split[target])
    right_mistakes = intermediate_node_num_mistakes(right_split[target])
    error_after_split = (left_mistakes + right_mistakes) / float(len(data))
    if error_reduction(error_before_split,error_after_split)<=min_error_reduction:    
        print "Early stopping condition 3 reached. Minimum error reduction."
        return  create_leaf(target_values)    
    remaining_features.remove(splitting_feature)
    print "Split on feature %s. (%s, %s)" % (\
                      splitting_feature, len(left_split), len(right_split))
    left_tree = decision_tree_create(left_split, remaining_features, target, 
                                     current_depth + 1, max_depth, min_node_size, min_error_reduction)        
    right_tree = decision_tree_create(right_split, remaining_features, target, 
                                     current_depth + 1, max_depth, min_node_size, min_error_reduction) 
    return {'is_leaf'          : False, 
            'prediction'       : None,
            'splitting_feature': splitting_feature,
            'left'             : left_tree, 
            'right'            : right_tree}

def count_nodes(tree):
    if tree['is_leaf']:
        return 1
    return 1 + count_nodes(tree['left']) + count_nodes(tree['right'])

"""
Explanation: Incorporating new early stopping conditions in binary decision tree implementation
End of explanation
"""


my_decision_tree_new = decision_tree_create(train_data, features, 'safe_loans', max_depth = 6, 
                                min_node_size = 100, min_error_reduction=0.0)

my_decision_tree_old = decision_tree_create(train_data, features, 'safe_loans', max_depth = 6, 
                                min_node_size = 0, min_error_reduction=-1)

"""
Explanation: Build a tree.
End of explanation
"""


def classify(tree, x, annotate = False):   
    if tree['is_leaf']:
        if annotate: 
            print "At leaf, predicting %s" % tree['prediction']
        return tree['prediction'] 
    else:
        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)

validation_set[0]

print 'Predicted class: %s ' % classify(my_decision_tree_new, validation_set[0])

classify(my_decision_tree_new, validation_set[0], annotate = True)

classify(my_decision_tree_old, validation_set[0], annotate = True)

"""
Explanation: Making predictions
End of explanation
"""


def evaluate_classification_error(tree, data):
    prediction = data.apply(lambda x: classify(tree, x))
    mistakes = (prediction!=data['safe_loans']).sum()
    return mistakes/float(len(data))

evaluate_classification_error(my_decision_tree_new, validation_set)

evaluate_classification_error(my_decision_tree_old, validation_set)

"""
Explanation: Evaluating the model
End of explanation
"""


model_1 = decision_tree_create(train_data, features, 'safe_loans', max_depth = 2,
                               min_node_size = 0, min_error_reduction=-1)
model_2 = decision_tree_create(train_data, features, 'safe_loans', max_depth = 6,
                               min_node_size = 0, min_error_reduction=-1)
model_3 = decision_tree_create(train_data, features, 'safe_loans', max_depth = 14,
                               min_node_size = 0, min_error_reduction=-1)

"""
Explanation: Exploring the effect of max_depth
End of explanation
"""


print "Training data, classification error (model 1):", evaluate_classification_error(model_1, train_data)
print "Training data, classification error (model 2):", evaluate_classification_error(model_2, train_data)
print "Training data, classification error (model 3):", evaluate_classification_error(model_3, train_data)

print "Training data, classification error (model 1):", evaluate_classification_error(model_1, validation_set)
print "Training data, classification error (model 2):", evaluate_classification_error(model_2, validation_set)
print "Training data, classification error (model 3):", evaluate_classification_error(model_3, validation_set)

"""
Explanation: Evaluating the models
End of explanation
"""


def count_leaves(tree):
    if tree['is_leaf']:
        return 1
    return count_leaves(tree['left']) + count_leaves(tree['right'])

print count_leaves(model_1),count_leaves(model_2),count_leaves(model_3)

"""
Explanation: Measuring the complexity of the tree
complexity(T) = number of leaves in the tree T
End of explanation
"""


model_4 = decision_tree_create(train_data, features, 'safe_loans', max_depth = 6,
                               min_node_size = 0, min_error_reduction=-1)
model_5 = decision_tree_create(train_data, features, 'safe_loans', max_depth = 6,
                               min_node_size = 0, min_error_reduction=0)
model_6 = decision_tree_create(train_data, features, 'safe_loans', max_depth = 6,
                               min_node_size = 0, min_error_reduction=5)

print "Validation data, classification error (model 4):", evaluate_classification_error(model_4, validation_set)
print "Validation data, classification error (model 5):", evaluate_classification_error(model_5, validation_set)
print "Validation data, classification error (model 6):", evaluate_classification_error(model_6, validation_set)

print count_leaves(model_4),count_leaves(model_5),count_leaves(model_6)

"""
Explanation: Exploring the effect of min_error
End of explanation
"""


model_7 = decision_tree_create(train_data, features, 'safe_loans', max_depth = 6,
                               min_node_size = 0, min_error_reduction=-1)
model_8 = decision_tree_create(train_data, features, 'safe_loans', max_depth = 6,
                               min_node_size = 2000, min_error_reduction=-1)
model_9 = decision_tree_create(train_data, features, 'safe_loans', max_depth = 6,
                               min_node_size = 50000, min_error_reduction=-1)

print "Validation data, classification error (model 7):", evaluate_classification_error(model_7, validation_set)
print "Validation data, classification error (model 8):", evaluate_classification_error(model_8, validation_set)
print "Validation data, classification error (model 9):", evaluate_classification_error(model_9, validation_set)

print count_leaves(model_7),count_leaves(model_8),count_leaves(model_9)

"""
Explanation: Exploring the effect of min_node_size
End of explanation
"""


