<jupyter_start><jupyter_text>A simple implementation of Decision Trees to understand the functionality A decision tree in simple terms tries to compute all possible choises and the gain we can attain by choosing each of these options. The decision tree uses greedy algorithm and just decides which choice maximises the gain for a split. It chooses the split and repeats this process until we are able to solve our query.<jupyter_code>import pandas as pd
import numpy as np
data = pd.read_csv('C:/Users/Kiran/Desktop/Pending/week8/ML/tennisPlay.csv')
data = data[:14]
data = data[['Day', 'Outlook', 'Temp', 'Humidity', 'Wind', 'PlayTennis']]
data<jupyter_output><empty_output><jupyter_text>Please make use of https://en.wikipedia.org/wiki/Entropy_(information_theory) link to learn about entropy function used in the code for calculating information gain Creating a simple tree without classes to understand how it works for an iteration<jupyter_code>def get_filtered_level_value(temp, column, target, level, class1, is_verbose):
    
    if(is_verbose):
        print('column = {}\ntarget={}\nlevel = {}\n class1 = {} '.format(column, target, level, class1))
    
    try:
        value = temp[(temp[column] == level) & (temp[target] == class1)].as_matrix().ravel()[-1]
    except IndexError:
        value = 0
    return value

def get_filtered_non_level_value(temp, column, target, level, class1, is_verbose):
    if(is_verbose):
        print('column = {}\ntarget={}\nlevel = {}\n class1 = {} \nrest'.format(column, target, level, class1))
    
    try:
        value = temp[(temp[column] != level) & (temp[target] == class1)].sum().as_matrix().ravel()[-1]
    except IndexError:
        value = 0
    return value

def calc_shannon_entropy(probablity_level_list):
    pi = probablity_level_list[0]
    pj = probablity_level_list[1]
    if(pi == 0 or pj == 0):
        entropy = 0
    else:
        entropy = (- pi * np.log2(pi) - pj * np.log2(pj))
    return entropy

def calc_weighted_entropy(entropy_left, entropy_right, count_total_level, count_total_non_level, count_total):
    return ((count_total_level/count_total) * entropy_left + (count_total_non_level/count_total) * entropy_right)

def get_class_probablity(temp, target, count_total):
    
    classes = temp[target].unique()
    class_probablity_list = []
    for class1 in classes:
        class_probablity_list.append(temp[temp[target] == class1].groupby(target).count().as_matrix().ravel()[-1]/ count_total)
    return class_probablity_list

def calc_information_gain(initial_entropy, wighted_entropy):
    return initial_entropy - wighted_entropy
        
def decision_tree(data, target, exclude_columns = None, distinct_column = None, is_verbose = False):
    columns = list(data.columns)
    columns.remove(exclude_columns)
    columns.remove(target)
    information_gain_list = []
    level_split_list = []
    temp1 = data.copy()
    count_total = len(temp1)
    class_probablity_list = get_class_probablity(temp1, target, count_total)
    initial_entropy = calc_shannon_entropy(class_probablity_list)
    if(is_verbose):
        print('initial_entropy' , initial_entropy)

    for column in columns:
        if(is_verbose):
            print(column)
        temp = pd.DataFrame(temp1[[column, target, distinct_column]].groupby([column, target]).agg(['count'])).copy()
        temp = temp.reset_index()
        levels = temp[column].unique()
        classes = temp[target].unique()
        
        for level in levels:
            
            level_split_list.append(level)
            count_total_level = temp[temp[column] == level].sum().as_matrix().ravel()[-1]
            if(is_verbose):
                print(count_total_level)
            count_total_non_level = temp[temp[column] != level].sum().as_matrix().ravel()[-1]
            probablity_level_list = []
            probablity_non_level_list = []
            
            for class1 in classes:
                
                
                count_level = get_filtered_level_value(temp, column, target, level, class1, is_verbose)
                probablity_level = count_level / count_total_level
                probablity_level_list.append(probablity_level)
                count_non_level = get_filtered_non_level_value(temp, column, target, level, class1, is_verbose)
                probablity_non_level = count_non_level/ count_total_non_level
                probablity_non_level_list.append(probablity_non_level)

            entropy_left = calc_shannon_entropy(probablity_level_list)
            entropy_right = calc_shannon_entropy(probablity_non_level_list)
            wighted_entropy = calc_weighted_entropy(entropy_left, entropy_right, count_total_level, count_total_non_level, count_total)
            infromation_Gain =  calc_information_gain(initial_entropy, wighted_entropy)
            information_gain_list.append(infromation_Gain)
    
    print('\ninformation_gain_list :\n', information_gain_list)
    print('\nlevel_split_list :\n', level_split_list)
    argmax = np.argmax(information_gain_list)
    print('\n\nbest level to split is :{} vs rest, which has an information gain of {}'.format(level_split_list[argmax], information_gain_list[argmax]))
    initial_entropy = information_gain_list[argmax]
#     temp1 = data[[column, target, distinct_column]].groupby([column, target]).agg(['count'])
decision_tree(data, 'PlayTennis', exclude_columns = 'Day', distinct_column = 'Day')<jupyter_output>information_gain_list :
 [0.22600024438491684, 0.0031848530446489942, 0.10224356360985076, 0.014956069928972804, 0.025078173505850621, 0.0013397424044413464, 0.15183550136234159, 0.15183550136234159, 0.048127030408269489, 0.048127030408269489]

level_split_list :
 ['Overcast', 'Rain', 'Sunny', 'Cool', 'Hot', 'Mild', 'High', 'Normal', 'Strong', 'Weak']


best level to split is :Overcast vs rest, which has an information gain of 0.22600024438491684
{'fraction_non_alphanumeric': 0.10588633288227334, 'fraction_numerical': 0.040764546684709066, 'mean_word_length': 3.799512987012987, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 8, 'https://': 1, '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': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '336806', 'license': 'MIT', 'n_tokens_mistral': 2013, 'n_tokens_neox': 1846, 'n_words': 399, 'path': 'Decision Trees/Decision Trees.ipynb', 'repo_name': '18kiran12/MachineLearning', 'size': '5912'}