<jupyter_start><jupyter_text>Decision Tree for Spambase dataset Spambase Dataset Info:The last column of 'spambase.data' denotes whether the e-mail was considered spam (1) or not (0), i.e. unsolicited commercial e-mail. Most of the attributes indicate whether a particular word or character was frequently occuring in the e-mail. The run-length attributes (55-57) measure the length of sequences of consecutive capital letters. For the statistical measures of each attribute, see the end of this file. Here are the definitions of the attributes: 48 continuous real [0,100] attributes of type word_freq_WORD = percentage of words in the e-mail that match WORD, i.e. 100 * (number of times the WORD appears in the e-mail) / total number of words in e-mail. A "word" in this case is any string of alphanumeric characters bounded by non-alphanumeric characters or end-of-string. 6 continuous real [0,100] attributes of type char_freq_CHAR] = percentage of characters in the e-mail that match CHAR, i.e. 100 * (number of CHAR occurences) / total characters in e-mail 1 continuous real [1,...] attribute of type capital_run_length_average = average length of uninterrupted sequences of capital letters 1 continuous integer [1,...] attribute of type capital_run_length_longest = length of longest uninterrupted sequence of capital letters 1 continuous integer [1,...] attribute of type capital_run_length_total = sum of length of uninterrupted sequences of capital letters = total number of capital letters in the e-mail 1 nominal {0,1} class attribute of type spam = denotes whether the e-mail was considered spam (1) or not (0), i.e. unsolicited commercial e-mail.<jupyter_code>import numpy as np
import pandas as pd
from multiprocessing import Pool, cpu_count
from functools import partial<jupyter_output><empty_output><jupyter_text>Get data<jupyter_code>def get_data(column_names):
    data_frame = pd.read_csv('./data/spambase.txt', sep = ',')
    data_frame.columns = column_names
    
    return data_frame<jupyter_output><empty_output><jupyter_text>Add Column names to the features<jupyter_code>column_names = ['word_freq_make','word_freq_address', 'word_freq_all', 'word_freq_3d', 'word_freq_our', 
               'word_freq_over','word_freq_remove','word_freq_internet','word_freq_order','word_freq_mail',
               'word_freq_receive','word_freq_will','word_freq_people','word_freq_report','word_freq_addresses',
               'word_freq_free', 'word_freq_business', 'word_freq_email', 'word_freq_you',
               'word_freq_credit','word_freq_your','word_freq_font','word_freq_000','word_freq_money',
               'word_freq_hp','word_freq_hpl','word_freq_george','word_freq_650','word_freq_lab',
               'word_freq_labs','word_freq_telnet','word_freq_857','word_freq_data','word_freq_415',
               'word_freq_85','word_freq_technology','word_freq_1999','word_freq_parts','word_freq_pm',
               'word_freq_direct','word_freq_cs','word_freq_meeting','word_freq_original','word_freq_project',
               'word_freq_re','word_freq_edu','word_freq_table','word_freq_conference','char_freq_;',
               'char_freq_(','char_freq_[','char_freq_!','char_freq_$','char_freq_#','capital_run_length_average',
               'capital_run_length_longest','capital_run_length_total','spam_label']
dataframe = get_data(column_names)<jupyter_output><empty_output><jupyter_text>Normalize the dataNormalize all values in the dataset to be between 0 and 1. We use shift/scale normalization explained here: [wikipedia](https://en.wikipedia.org/wiki/Feature_scalingRescaling_(min-max_normalization))<jupyter_code>def normalize(dataset):
    
    maxs = dataset.max()
    mins = dataset.min()
    
    for feature in dataset.columns[:-1]:        
        for i, entry in dataset.iterrows():
            dataset.at[i, feature] = (entry[feature] - mins[feature]) / (maxs[feature] - mins[feature])
            
    return dataset<jupyter_output><empty_output><jupyter_text>Shuffle the data<jupyter_code>dataframe = dataframe.sample(frac = 1)
dataframe = normalize(dataframe)
dataframe.describe()<jupyter_output><empty_output><jupyter_text>Find Thresholds for SplittingWe use simple unique values as thresholds<jupyter_code>def get_thresholds(dataset, feature):       
    return dataset[feature].unique()<jupyter_output><empty_output><jupyter_text>Find Best SplitA split consists of (Feature, Threshold) pair. We select the best (Feature, Threshold) pair by checking the Information Gain. The Split with highest Information Gain is selected.<jupyter_code>def get_best_split(dataset):
    
    best_feature = None
    best_threshold = None
    max_info_gain = 0
    
    gini_before = gini(dataset)
    
    for feature in dataset.columns[:-1]:
        
        thresholds = get_thresholds(dataset, feature)
        
        for threshold in thresholds:
            left, right = split_data(dataset, feature, threshold)
            
            if len(left) == 0 or len(right) == 0:
                continue
                
            left_gini = gini(left)
            right_gini = gini(right)
            
            w = len(left) / len(dataset)
            gini_after = (w * left_gini) + ((1-w) * right_gini)
            
            info_gain = gini_before - gini_after

            if max_info_gain <= info_gain:
                max_info_gain = info_gain
                best_feature = feature
                best_threshold = threshold

    return best_feature, best_threshold, max_info_gain<jupyter_output><empty_output><jupyter_text>Terminal NodeNode which acts as the leaf of the decision tree. These nodes give out the predicted label by finding the majority label in the data at this node.<jupyter_code>class Terminal:

    def __init__(self, dataset):
        self.prediction = dataset.spam_label.mode()[0]

    def predict(self):
        return self.prediction<jupyter_output><empty_output><jupyter_text>NodeNode represents a splitting node which consists of a Feature and a Threshold. The incoming data is split using this nodes (Feature, Threshold) pair.<jupyter_code>class Node:

    def __init__(self, feature, threshold, left_node, right_node):
        self.feature = feature
        self.threshold = threshold
        self.left_node = left_node
        self.right_node = right_node
def get_value_count(dataset):
    return dataset.spam_label.value_counts()<jupyter_output><empty_output><jupyter_text>Gini MeasureGini index is used to measure the node impurity. Follow this [link](https://en.wikipedia.org/wiki/Decision_tree_learningGini_impurity) to learn more about Gini index.<jupyter_code>def gini(dataset):
    counts = get_value_count(dataset)
    
    imp = 1
    for x in counts:
        prob = x / len(dataset)
        imp -= prob**2
        
    return imp<jupyter_output><empty_output><jupyter_text>Split the dataThe data is divided into left and right node in which the left node contains values less than threshold and right node contains all others.<jupyter_code>def split_data(dataset, feature, threshold):    
    
    left = dataset[dataset[feature] < threshold]
    right = dataset[dataset[feature] >= threshold]
    
    return left, right<jupyter_output><empty_output><jupyter_text>Build the Decision TreeWe build the decision tree by recursively calling the function until we reach a point where the Information Gain is 0 or when we have reached max depth.<jupyter_code>def build_tree(max_depth, depth, dataset):
    
    best_feature, best_threshold, info_gain = get_best_split(dataset)
    
    if info_gain == 0 or depth >= max_depth:
        return Terminal(dataset)
    
    left_data, right_data = split_data(dataset, best_feature, best_threshold)

    left_node = build_tree(max_depth, depth+1, left_data)
    right_node = build_tree(max_depth, depth+1, right_data)

    return Node(best_feature, best_threshold, left_node, right_node)<jupyter_output><empty_output><jupyter_text>Cross Validation We use Cross Validation to perform hyperparameter tuning. Follow this [link](http://cs231n.github.io/classification/val) to learn more about Cross-Validation.<jupyter_code>def get_kfold(dataframe, num_folds):
    
    test_data_size = int(20 * len(dataframe) / 100)
    test_data = dataframe[:test_data_size]
    
    train_data = dataframe[test_data_size:]
    
    fold_size = int(len(train_data) / num_folds)
    folds = []
    
    start = 0
    
    for fold in range(num_folds):
        folds.append(train_data[start:start+fold_size])
        start += fold_size
    
    return folds, train_data, test_data
folds, train_data, test_data = get_kfold(dataframe, num_folds = 5)
def train_folds(folds, max_depth):
    
    acc = []
    training_input = []
    validate_input = []
    
    for k in range(len(folds)):
        validate = folds[k]
            
        train = pd.DataFrame()
        
        for f in folds:
            if not f.equals(validate):
                train = pd.concat([train, f])
        
        training_input.append(train)
        validate_input.append(validate)
    
    with Pool(cpu_count()) as pool:
        func = partial(build_tree, max_depth, 0)
        models = pool.map(func, training_input)
        
        pool.close()
        pool.join()
    
    for i,val in enumerate(validate_input):
        acc.append(test_model(models[i], val))
        
    return acc, models<jupyter_output><empty_output><jupyter_text>PredictionPredict label for the data by using the Decision Tree model we trained.<jupyter_code>def predict(root, entry):
    
    if isinstance(root, Terminal):
        return root.predict()
    
    if entry[root.feature] < root.threshold:
        result = predict(root.left_node, entry)
    else:
        result = predict(root.right_node, entry)
        
    return result
def test_model(model, test_data):
    
    predictions = []
    
    for i, entry in test_data.iterrows():
        predictions.append(predict(model, entry))
    
    correct_count = 0
    
    for i,p in enumerate(predictions):
        if test_data.iloc[i]['spam_label'] == p:
            correct_count += 1
        
    return correct_count / len(test_data)
def test_all_models(models, test_data):
    accs = []
    for model in models:
        accs.append(test_model(model, test_data))
        
    return np.mean(accs), accs
def conf_matrix(model, test_data):
    test_labels = test_data['spam_label'].values
    
    predictions = []
    
    for i, entry in test_data.iterrows():
        predictions.append(predict(model, entry))
        
    tp = 0
    fp = 0
    tn = 0
    fn = 0
    
    for i in range(len(predictions)):
        p = predictions[i]
        if p == test_labels[i]:
            if p == 1:
                tp += 1
            else:
                tn += 1
        else:
            if p == 1:
                fp += 1
            else:
                fn += 1
    
    conf = np.array([[tp, fp], [fn, tn]])
    return conf
acc, models = train_folds(folds, 7)
avg_accuracy = np.mean(acc)
print('Cross-Validation models accuracy: {}'.format(acc))
print('Average Accuracy on Validation Folds: {}'.format(avg_accuracy))
model_acc, a = test_all_models(models, test_data)
print('Accuracy of all models on Actual Test Data: {}'.format(a))
print('Average Accuracy on Actual Test Data: {} %'.format(model_acc))
final_model = build_tree(7, 0, train_data)
print('Final Accuracy on actual Test data: {}'.format(test_model(final_model, test_data)))<jupyter_output>Final Accuracy on actual Test data: 0.9043478260869565<jupyter_text>Confusion Matrix<jupyter_code>conf = conf_matrix(final_model, test_data)
print('Confusion Matrix')
print(conf)<jupyter_output>Confusion Matrix
[[325  45]
 [ 43 507]]
{'fraction_non_alphanumeric': 0.09417193642112459, 'fraction_numerical': 0.01042556827892668, 'mean_word_length': 3.4770466717674062, 'pattern_counts': {'":': 0, '<': 62, '<?xml version=': 0, '>': 61, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '15', 'dir': 'jupyter-structured-clean-dedup', 'id': '422045', 'license': 'MIT', 'n_tokens_mistral': 3664, 'n_tokens_neox': 3506, 'n_words': 936, 'path': 'Decision Tree/Decision_Tree.ipynb', 'repo_name': 'prasad-madhale/machine-learning', 'size': '11702'}