<reponame>aditya30394/Benign-vs-Malignant-tumors
# -*- coding: utf-8 -*-
"""ML_HW2_decision_tree.ipynb

Automatically generated by Colaboratory.

Original file is located at
    https://colab.research.google.com/drive/1uB9Yz9QYx5Dci6JWWxs9awETGaAK9-vJ
"""

# Importing the libraries
# https://github.com/random-forests/tutorials/blob/master/decision_tree.ipynb
# https://medium.com/deep-math-machine-learning-ai/chapter-4-decision-trees-algorithms-b93975f7a1f1
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
from sklearn.metrics import accuracy_score

from google.colab import files
uploaded = files.upload()

from __future__ import print_function
# Import the dataset
dataset = pd.read_csv('hw2_question1.csv', header=None)
full_dataset = dataset.iloc[:, :].values
import collections
class_column = full_dataset[:,9]
class_summary = collections.Counter(class_column)

benign = class_summary[2]
malignant = class_summary[4]

total_samples = len(dataset)

print('Total number of samples is {}'.format(total_samples))
print('Input shape is {}'.format(dataset.shape))
print('Number of samples belonging to the benign case is {}'.format(benign))
print('Number of samples belonging to the malignant case is {}'.format(malignant))

dataset.head(10)

benign_samples = dataset[dataset[9] == 2]
malignant_samples = dataset[dataset[9] == 4]

benign_samples.shape

malignant_samples.shape

benign_samples.head(5)

malignant_samples.head(5)

total_train_samples = (int)((2/3)*total_samples)
total_test_samples = total_samples - total_train_samples

print('Total number of training samples is {}'.format(total_train_samples))
print('Total number of test samples is {}'.format(total_test_samples))

# Reference used:
# https://stackoverflow.com/questions/29576430/shuffle-dataframe-rows
# https://pandas.pydata.org/Pandas_Cheat_Sheet.pdf

# shuffle the samples
benign_samples = benign_samples.sample(frac=1, random_state=8765).reset_index(drop=True)
malignant_samples = malignant_samples.sample(frac=1, random_state=8734).reset_index(drop=True)

benign_samples.head(5)

malignant_samples.head(5)

# get benign samples
train_benign_samples = (int)((2/3)*benign)
test_benign_samples = benign - train_benign_samples

train_benign = benign_samples.head(train_benign_samples)
test_benign = benign_samples.tail(test_benign_samples)

train_benign.shape

test_benign.shape

# get malignant samples
train_malignant_samples = (int)((2/3)*malignant)
test_malignant_samples = malignant - train_malignant_samples

train_malignant = malignant_samples.head(train_malignant_samples)
test_malignant = malignant_samples.tail(test_malignant_samples)

train_malignant.shape

test_malignant.shape

final_train_set = pd.concat([train_benign, train_malignant])
final_train_set = final_train_set.sample(frac=1).reset_index(drop=True)
print(final_train_set.shape)
print(final_train_set.head(5))

final_test_set = pd.concat([test_benign, test_malignant])
final_test_set = final_test_set.sample(frac=1).reset_index(drop=True)
print(final_test_set.shape)
print(final_test_set.head(5))

# Decision Tree Code starts from here
# List of references used:
# https://acadgild.com/blog/decision-tree-python-code
# (Main) https://github.com/random-forests/tutorials/blob/master/decision_tree.ipynb
# https://machinelearningmastery.com/implement-decision-tree-algorithm-scratch-python/
# https://medium.com/@rakendd/decision-tree-from-scratch-9e23bcfb4928

def class_counts(X):
    """Counts the number samples belonging to each class for given set of samples"""
    class_column = X[9]
    class_summary = collections.Counter(class_column)
    return class_summary

print(class_counts(final_train_set))
print(class_counts(final_test_set))

class SplitAttribute:
    
    def __init__(self, column, value):
        self.column = column
        self.value = value
    """ go to left if true and right otherwise"""
    def compare(self, sample):
        val = sample[self.column]
        return val < self.value
    
    def __repr__(self):
        return "Is the value in column %s < %s?" % (
            str(self.column), str(self.value))

def GenerateSubsets(rows, split_attribute):
    
    if(len(rows) != 0 and split_attribute != None):
        column = split_attribute.column
        value = split_attribute.value
        left_rows = rows[rows[column] < value]
        right_rows = rows[rows[column] >= value]
        return left_rows, right_rows
    
    return pd.DataFrame(), pd.DataFrame()

import math

def info_content(rows):
    class_summary = class_counts(rows)
    class_benign = class_summary[2]
    class_malignant = class_summary[4]
    first_term = 0.0
    second_term = 0.0
    if(class_benign != 0):
        first_term = -1.0 * float(class_benign/float(class_benign+class_malignant)) * math.log(float(class_benign/ float(class_benign+class_malignant)), 2)
        
    if(class_malignant != 0):
        second_term = -1.0 * float(class_malignant/ float(class_benign+class_malignant)) * math.log(float(class_malignant/ float(class_benign+class_malignant)), 2)
    
    if(first_term == 0 and second_term==0):
        return 0
    
    return float(first_term + second_term)

def Entropy(left, right, all_data):
    info_content_left = info_content(left)
    info_content_right = info_content(right)
    entrofy_of_attribute = float(len(left)/float(len(all_data)))*info_content_left + float(len(right)/float(len(all_data)))*info_content_right 
    gain = info_content(all_data) - entrofy_of_attribute
    # using the information gain method which uses entropy
    return gain

# https://github.com/random-forests/tutorials/blob/master/decision_tree.ipynb
def gini(rows):
    """Calculate the Gini Impurity for a list of rows.
    https://en.wikipedia.org/wiki/Decision_tree_learning#Gini_impurity
    """
    counts = class_counts(rows)
    impurity = 1
    for lbl in counts:
        prob_of_lbl = counts[lbl] / float(len(rows))
        impurity -= prob_of_lbl**2
    return impurity

def gini_index(left, right, all_data):
    current_uncertainty = gini(all_data)
    p = float(len(left)) / (len(left) + len(right))
    return current_uncertainty - p * gini(left) - (1 - p) * gini(right)

def find_split_attribute(rows, method='Entropy'):
    
    max_gain = 0.0  
    split_attribute_selected = None  
    shape = rows.shape
    n_samples = shape[0]
    # we have to try these splits for each feature and see which one is giving the best result
    split_values = np.array([1.5, 2.5, 3.5, 4.5, 5.5, 6.5, 7.5, 8.5, 9.5])
    # for each column
    column_list = list(rows)
    # remove the "class" column for the frature list
    column_list.remove(9)
    for col in column_list:  

        for split_value in split_values:  # for each split value

            split_attribute = SplitAttribute(col, split_value)

            # split the dataset arounf the split_value
            left_rows, right_rows = GenerateSubsets(rows, split_attribute)

            if len(left_rows) == 0 or len(right_rows) == 0:
                continue

            # Calculate the information gain from this split
            if(method=='Entropy'):
                gain = Entropy(left_rows, right_rows, rows)
            else:
                gain = gini_index(left_rows, right_rows, rows)

            if gain >= max_gain:
                max_gain, split_attribute_selected = gain, split_attribute

    return max_gain, split_attribute_selected

class Leaf:
    """A Leaf node classifies data.
    """
    def __init__(self, rows):
        self.predictions = class_counts(rows)

class Decision_Node:
    """A Decision Node.
    This holds a reference to the splitting atribute, and to the two child nodes.
    """

    def __init__(self,
                 split_attribute,
                 true_branch,
                 false_branch):
        self.split_attribute = split_attribute
        self.true_branch = true_branch
        self.false_branch = false_branch

def build_tree(rows, method='Entropy', depth=100, theta=0.0, debug=True):
    gain, split_attribute = find_split_attribute(rows, method)

    # Base case: no further gain or we reached max depth
    # Since we can ask no further questions,
    # we'll return a leaf.
    if debug == True:
        print('Gain is {}'.format(gain))
        print('split_attribute is {}'.format(split_attribute))
    
    if depth==0 or gain <= theta  :
        return Leaf(rows)

    # If we reach here, we have found a useful feature / value
    # to partition on.
    true_rows, false_rows = GenerateSubsets(rows, split_attribute)
    
    if(split_attribute != None):
        true_rows.drop(columns=[split_attribute.column])
        false_rows.drop(columns=[split_attribute.column])
    
    # Recursively build the true branch.
    true_branch = build_tree(true_rows, method, depth-1, theta, debug)

    # Recursively build the false branch.
    false_branch = build_tree(false_rows, method, depth-1, theta, debug)
    
    # Return a Question node.
    # This records the best feature / value to ask at this point,
    # as well as the branches to follow
    # dependingo on the answer.
    if debug == True:
        print("----------------------------------------------\n")
    
    return Decision_Node(split_attribute, true_branch, false_branch)

# NOT MY CODE: https://github.com/random-forests/tutorials/blob/master/decision_tree.ipynb
def print_tree(node, spacing=""):
    """World's most elegant tree printing function."""

    # Base case: we've reached a leaf
    if isinstance(node, Leaf):
        print (spacing + "Predict", node.predictions)
        return

    # Print the question at this node
    print (spacing + str(node.split_attribute))

    # Call this function recursively on the true branch
    print (spacing + '--> True:')
    print_tree(node.true_branch, spacing + "  ")

    # Call this function recursively on the false branch
    print (spacing + '--> False:')
    print_tree(node.false_branch, spacing + "  ")

my_tree = build_tree(final_train_set)

print_tree(my_tree)
print(my_tree.split_attribute)

def classify(row, node):
    # Base case: we've reached a leaf
    if isinstance(node, Leaf):
        predictions = node.predictions
        mode = max(predictions, key=predictions.get)
        return mode

    # Decide whether to follow the true-branch or the false-branch.
    # Compare the feature / value stored in the node,
    # to the example we're considering.
    column = node.split_attribute.column
    value = node.split_attribute.value
    
    if row[column] < value:
        return classify(row, node.true_branch)
    else:
        return classify(row, node.false_branch)

targets, preds = [], []
for index, row in final_test_set.iterrows():
    prediction = classify(row, my_tree)
    targets.append(row[9])
    preds.append(prediction)
    
print(accuracy_score(targets, preds))

final_test_set.shape

targets, preds = [], []
for index, row in final_train_set.iterrows():
    prediction = classify(row, my_tree)
    targets.append(row[9])
    preds.append(prediction)

print(accuracy_score(targets, preds))

my_tree = build_tree(final_train_set, method='gini index', depth=100)

print_tree(my_tree)
print(my_tree.split_attribute)

targets, preds = [], []
for index, row in final_test_set.iterrows():
    prediction = classify(row, my_tree)
    targets.append(row[9])
    preds.append(prediction)

print(accuracy_score(targets, preds))

targets, preds = [], []
for index, row in final_train_set.iterrows():
    prediction = classify(row, my_tree)
    targets.append(row[9])
    preds.append(prediction)

print(accuracy_score(targets, preds))

test_entropy = []
train_entropy = []

DEPTH = range(1,11)
method='Entropy'
    
print('Method used is {}'.format(method))
for depth in DEPTH:
    # build a tree
    my_tree = build_tree(final_train_set, method, depth)

    targets, preds = [], []
    for index, row in final_test_set.iterrows():
        prediction = classify(row, my_tree)
        targets.append(row[9])
        preds.append(prediction)
    test_accuracy = accuracy_score(targets, preds)
    test_entropy.append(test_accuracy*100)

    targets, preds = [], []
    for index, row in final_train_set.iterrows():
        prediction = classify(row, my_tree)
        targets.append(row[9])
        preds.append(prediction)
    train_accracy = accuracy_score(targets, preds)
    train_entropy.append(train_accracy*100)

    print('Depth is {} | Training Accuracy is {} | Test Accuracy is {} '.format(depth, train_accracy, test_accuracy))

plt.plot(DEPTH, train_entropy, 'b', label='Accuracy on training set')
plt.plot(DEPTH, test_entropy, 'r', label='Accuracy on test set')
plt.title('Number of nodes (Depth) VS Accuracy graph - (Entropy Method)')
plt.xlabel('Depth/number of nodes')
plt.ylabel('Accuracy')
plt.legend()

plt.show()

fig = plt.figure()
ax = fig.add_subplot(111)

A = DEPTH
B = train_entropy

plt.plot(A, B, 'b', label='Accuracy on training set')
for xy in zip(A, B):                                       # <--
    ax.annotate('(%s, %.2f)' % xy, xy=xy, textcoords='data') # <--

B = test_entropy
plt.plot(A, B, 'r', label='Accuracy on test set')
for xy in zip(A, B):                                       # <--
    ax.annotate('(%s, %.2f)' % xy, xy=xy, textcoords='data') # <--

plt.title('Number of nodes (Depth) VS Accuracy graph - (Entropy Method)')
plt.xlabel('Depth/number of nodes')
plt.ylabel('Accuracy')
plt.legend()
plt.grid()
plt.show()

test_gini = []
train_gini = []

DEPTH = range(1,11)

method = 'Gini Index'
    
print('Method used is {}'.format(method))
for depth in DEPTH:
    my_tree = build_tree(final_train_set, method, depth)
    if method != 'Entropy':
        targets, preds = [], []
        for index, row in final_test_set.iterrows():
            prediction = classify(row, my_tree)
            targets.append(row[9])
            preds.append(prediction)
        test_accuracy = accuracy_score(targets, preds)
        test_gini.append(test_accuracy*100)

        targets, preds = [], []
        for index, row in final_train_set.iterrows():
            prediction = classify(row, my_tree)
            targets.append(row[9])
            preds.append(prediction)
        train_accracy = accuracy_score(targets, preds)
        train_gini.append(train_accracy*100)

    print('Depth is {} | Training Accuracy is {} | Test Accuracy is {} '.format(depth, train_accracy, test_accuracy))

plt.plot(DEPTH, train_gini, 'b', label='Accuracy on training set')
plt.plot(DEPTH, test_gini, 'r', label='Accuracy on test set')
plt.title('Number of nodes (Depth) VS Accuracy graph - (Gini Index Method)')
plt.xlabel('Depth/number of nodes')
plt.ylabel('Accuracy')
plt.legend()

plt.show()

fig = plt.figure()
ax = fig.add_subplot(111)

A = DEPTH
B = train_gini

plt.plot(A, B, 'b', label='Accuracy on training set')
for xy in zip(A, B):                                       # <--
    ax.annotate('(%s, %.2f)' % xy, xy=xy, textcoords='data') # <--

B = test_gini
plt.plot(A, B, 'r', label='Accuracy on test set')
for xy in zip(A, B):                                       # <--
    ax.annotate('(%s, %.2f)' % xy, xy=xy, textcoords='data') # <--

plt.title('Number of nodes (Depth) VS Accuracy graph - (Gini Index Method)')
plt.xlabel('Depth/number of nodes')
plt.ylabel('Accuracy')
plt.legend()
plt.grid()
plt.show()

plt.plot(DEPTH, train_entropy, 'b', label='Accuracy on training set')
plt.plot(DEPTH, test_entropy, 'r', label='Accuracy on test set')
plt.plot(DEPTH, train_gini, 'g', label='Accuracy on training set')
plt.plot(DEPTH, test_gini, 'y', label='Accuracy on test set')
plt.xlabel('Depth')
plt.ylabel('Accuracy')
plt.title('Number of nodes (Depth) VS Accuracy graph')
plt.show();

# Pre-pruning test
test_entropy = []
train_entropy = []

THETAS = [1e-4, 3e-4, 9e-4, 1e-3, 3e-3, 9e-3, 0.01, 0.03, 0.09, 0.1, 0.3, 0.9, 1, 3 ]
method='Entropy'
    
print('Method used is {}'.format(method))
for theta in THETAS:
    # build a tree
    my_tree = build_tree(final_train_set, method, 100, theta, False)

    targets, preds = [], []
    for index, row in final_test_set.iterrows():
        prediction = classify(row, my_tree)
        targets.append(row[9])
        preds.append(prediction)
    test_accuracy = accuracy_score(targets, preds)
    test_entropy.append(test_accuracy*100)

    targets, preds = [], []
    for index, row in final_train_set.iterrows():
        prediction = classify(row, my_tree)
        targets.append(row[9])
        preds.append(prediction)
    train_accracy = accuracy_score(targets, preds)
    train_entropy.append(train_accracy*100)

    print('Threshold is {} | Training Accuracy is {} | Test Accuracy is {} '.format(theta, train_accracy, test_accuracy))

plt.plot(np.log2(THETAS), train_entropy, 'bo', label='Accuracy on training set')
plt.plot(np.log2(THETAS), test_entropy, 'ro', label='Accuracy on test set')
plt.title('Threshold VS Accuracy graph - (Entropy Method)')
plt.xlabel('Threshold values (log 2 values)')
plt.ylabel('Accuracy')
plt.legend()
plt.show()

test_gini = []
train_gini = []

THETAS = [1e-4, 3e-4, 9e-4, 1e-3, 3e-3, 9e-3, 0.01, 0.03, 0.09, 0.1, 0.3, 0.9, 1, 3 ]
method = 'Gini Index'
    
print('Method used is {}'.format(method))
for theta in THETAS:
    # build a tree
    my_tree = build_tree(final_train_set, method, 100, theta, False)

    targets, preds = [], []
    for index, row in final_test_set.iterrows():
        prediction = classify(row, my_tree)
        targets.append(row[9])
        preds.append(prediction)
    test_accuracy = accuracy_score(targets, preds)
    test_gini.append(test_accuracy*100)

    targets, preds = [], []
    for index, row in final_train_set.iterrows():
        prediction = classify(row, my_tree)
        targets.append(row[9])
        preds.append(prediction)
    train_accracy = accuracy_score(targets, preds)
    train_gini.append(train_accracy*100)
    print('Threshold is {} | Training Accuracy is {} | Test Accuracy is {} '.format(theta, train_accracy, test_accuracy))

plt.plot(np.log2(THETAS), train_gini, 'bo', label='Accuracy on training set')
plt.plot(np.log2(THETAS), test_gini, 'ro', label='Accuracy on test set')
plt.title('Threshold VS Accuracy graph - (Gini Index Method)')
plt.xlabel('Threshold values (log 2 values)')
plt.ylabel('Accuracy')
plt.legend()
plt.show()

