<jupyter_start><jupyter_text>Decision Tree Algorithm * Implemented From Scratch<jupyter_code>import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
import random<jupyter_output><empty_output><jupyter_text>Data Loading & Preparation<jupyter_code>df=pd.read_csv('iris.csv')
df.rename(columns={'Name':'Label'},inplace=True)
df.head()
sns.lmplot(x='PetalWidth', y='PetalLength', data=df,
           fit_reg=False, # No regression line
           hue='Label')   #<jupyter_output><empty_output><jupyter_text>Using sklearn for train test split<jupyter_code>X = df.iloc[:,:4].values
y = df['Label'].values
## Spliting your data into training set and test set
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X,y,test_size=0.3,random_state=42)
data=np.hstack([X_train,y_train[:,np.newaxis]]) ## Numpy train Data with label
# Converting train data into dataframe & naming as train_df
train_df=pd.DataFrame(data,columns=['SepalLength','SepalWidth','PetalLength','PetalWidth','Label'])
train_df.head()
test=np.hstack([X_test,y_test[:,np.newaxis]]) # Numpy test Data with label
# Converting test into dataframe & naming as test_df
test_df=pd.DataFrame(test,columns=['SepalLength','SepalWidth','PetalLength','PetalWidth','Label'])
test_df.head()<jupyter_output><empty_output><jupyter_text>Helping Functions    * All the functions below are written for 2D array input data.<jupyter_code>data[:5] # Displaying first five rows of Train data in numpy array format<jupyter_output><empty_output><jupyter_text>1. Checking Purity of Data    Always make  label column as last column.<jupyter_code>def check_purity(data): ## 2D array Data as input 
    label_column=data[:,-1]
    unique_classes=np.unique(label_column)
    if len(unique_classes)==1:
        return True
    else:
        return False
check_purity(data)
data[train_df.PetalWidth<0.8] # Pure data --> contains only one class
## Checking purity
check_purity(data[train_df.PetalWidth<0.8])<jupyter_output><empty_output><jupyter_text>2.  Classify<jupyter_code>def classify_data(data): # 2D array Data as input 
    label_column=data[:,-1]
    unique_classes,counts_unique_classes=np.unique(label_column,return_counts=True)
    index=counts_unique_classes.argmax()
    classification=unique_classes[index]
    return classification
data[(train_df.PetalWidth>0.8) & (train_df.PetalWidth<2)]
## Checking the function
classify_data(data[(train_df.PetalWidth>0.8) & (train_df.PetalWidth<2)])<jupyter_output><empty_output><jupyter_text>3. Potential Split* Different values in each feature where checking for best spliting is done and best split value is determined.* Find the unique values in each feature column.* take mean of each two corresponding values in feature column and store in dictionary like* D={'f1':[...,...,...] , 'f2':[...,...,...] , 'f3':[...,...,...] , ....,...}* Where list contains the calculated means of each two corresponding values of each feature<jupyter_code>train_df.head()
data[:5]
def get_potential_splits(data):                     # Note data is 2D NumPy array
    
    potential_splits = {}
    _, n_columns = data.shape
    for column_index in range(n_columns - 1):        # excluding the last column which is the label
        potential_splits[column_index] = []
        values = data[:, column_index]
        unique_values = np.unique(values)

        for index in range(len(unique_values)):
            if index != 0:
                current_value = unique_values[index]
                previous_value = unique_values[index - 1]
                potential_split = (current_value + previous_value) / 2
                
                potential_splits[column_index].append(potential_split)
    
    return potential_splits
potential_splits=get_potential_splits(data)
# potential_splits ## Check by unhashing it
#potential_splits[0]  ## Check all 
#potential_splits[1]
#potential_splits[2]
#potential_splits[3]
print(len(potential_splits[0]))
print(len(potential_splits[1]))
print(len(potential_splits[2]))
print(len(potential_splits[3]))
## Visualization of potential split points of sepal leght feature
sns.lmplot(x='SepalLength', y='PetalLength', data=train_df,
           fit_reg=False, # No regression line
           hue='Label',height=6, aspect=1.5) 
plt.vlines(x=potential_splits[0],ymin=1,ymax=7)# petal width
#plt.hlines(y=potential_splits[2],xmin=0,xmax=2.5)#petal lenght<jupyter_output><empty_output><jupyter_text>4. Split Data<jupyter_code>def split_data(data, split_column, split_value):
    split_column_values = data[:, split_column]
    data_left = data[split_column_values >  split_value]
    data_right = data[split_column_values <= split_value]
    return data_left, data_right<jupyter_output><empty_output><jupyter_text>* Checking above function<jupyter_code>split_column=3
split_value=1
split_column_values=data[:,split_column]
split_column_values
split_column_values<=split_value
data_left=data[split_column_values>split_value]
#data_left
data_right=data[split_column_values<=split_value]
#data_right
## Checking above functions # compare above two result with the result from this fucntion unhshing them
dl,dr=split_data(data,3,1)
#print(dl,'\n')
#print(dr)
## plotting above two dataframes>  check putting --> data= db and then data=da
sns.lmplot(data=train_df,x='PetalWidth', y='PetalLength',
           fit_reg=False, # No regression line
           height=6, aspect=1.5) 
plt.vlines(x=split_value,ymin=1,ymax=7)<jupyter_output><empty_output><jupyter_text>5. Calculating Entropy & Gini as Impurity* Any one of them can be used. Both gives almost same result.* Gini impurity is slightly faster to compute.  Gini Impurity:![Gini.png](attachment:Gini.png)<jupyter_code>def calculate_gini(data):
    
    label_column = data[:, -1]
    _, counts = np.unique(label_column, return_counts=True)

    probabilities = counts / counts.sum()
    gini = 1-sum(probabilities**2)
     
    return gini<jupyter_output><empty_output><jupyter_text>Entropy:![Entropy.JPG](attachment:Entropy.JPG)<jupyter_code>def calculate_entropy(data):
    
    label_column = data[:, -1]
    _, counts = np.unique(label_column, return_counts=True)
    probabilities = counts / counts.sum()
    entropy = sum(probabilities * -np.log2(probabilities))
     
    return entropy
### Testing function
calculate_entropy(dl)
calculate_entropy(dr)            
calculate_entropy(data)<jupyter_output><empty_output><jupyter_text>6. CART cost function for classification![CART%20for%20Classification.png](attachment:CART%20for%20Classification.png)* G --> Inpurity ; Any one of Gini or Entropy can be used Cost is calculated as overall_entropy:<jupyter_code>def calculate_overall_entropy(data_left,data_right):
    n_data_points=len(data_left)+len(data_right) # m
    p_data_right=len(data_right)/n_data_points   # m_right/m
    p_data_left=len(data_left)/n_data_points     # m_left/m
    overall_entropy= p_data_right* calculate_entropy(data_right)+ p_data_left* calculate_entropy(data_left)
    return overall_entropy
    ## For Gini use function --> 'calculate_Gini'  instead of --> 'calculate_entropy'
calculate_overall_entropy(dl,dr)<jupyter_output><empty_output><jupyter_text>7.  Determining best split<jupyter_code>### Determining best split
def determine_best_split(data,potential_splits):
    overall_entropy=999
    for column_index in potential_splits:
        for value in potential_splits[column_index]:
            data_left,data_right=split_data(data,split_column=column_index,split_value=value)
            current_overall_entropy=calculate_overall_entropy(data_left,data_right)

            if current_overall_entropy<=overall_entropy:
                overall_entropy=current_overall_entropy
                best_split_column=column_index
                best_split_value=value
    
    return best_split_column,best_split_value
potential_splits=get_potential_splits(data) ## Getting potential split 
determine_best_split(data,potential_splits) ## finding best split point from potential split<jupyter_output><empty_output><jupyter_text>8. Decision Tree Algorithm* Recursion implementation<jupyter_code>question = "{} <= {}".format(split_column, split_value)
question
sub_tree = {"question": ["yes_answer", "no_answer"]}
def decision_tree_algorithm(df, counter=0, min_samples=2, max_depth=5):
    
    # data preparations
    if counter == 0:
        global COLUMN_HEADERS
        COLUMN_HEADERS = df.columns
        data = df.values
    else:
        data = df           
    
    
    # base cases
    if (check_purity(data)) or (len(data) < min_samples) or (counter == max_depth):
        classification = classify_data(data)
        
        return classification

    
    # recursive part
    else:    
        counter += 1

        # helper functions 
        potential_splits = get_potential_splits(data)
        split_column, split_value = determine_best_split(data, potential_splits)
        data_left, data_right = split_data(data, split_column, split_value)
        
        # instantiate sub-tree
        feature_name = COLUMN_HEADERS[split_column]
        question = "{} <= {}".format(feature_name, split_value)
        sub_tree = {question: []}
        
        # find answers (recursion)
        yes_answer = decision_tree_algorithm(data_right, counter, min_samples, max_depth) #recursion
        no_answer = decision_tree_algorithm(data_left, counter, min_samples, max_depth)   # recursion
        
        # If the answers are the same, then there is no point in asking the qestion.
        # This could happen when the data is classified even though it is not pure
        # yet (min_samples or max_depth base cases).
        if yes_answer == no_answer:
            sub_tree = yes_answer
        else:
            sub_tree[question].append(yes_answer)
            sub_tree[question].append(no_answer)
        
        return sub_tree
tree = decision_tree_algorithm(train_df, max_depth=10)
tree
## Above tree has been  copied here to uderstand the segrregate the different block for understanding the tree.
{'PetalWidth <= 0.8': ['Iris-setosa',
                       {'PetalLength <= 5.15': [{'PetalWidth <= 1.65': [{'SepalWidth <= 2.25': ['Iris-virginica',
                                                                                                'Iris-versicolor']},
                                                                        {'SepalWidth <= 2.9': ['Iris-virginica',
                                                                                               {'PetalLength <= 5.05': ['Iris-versicolor',
                                                                                                                        'Iris-virginica']}]}]},
                                                'Iris-virginica']}]}<jupyter_output><empty_output><jupyter_text>9.  Classification<jupyter_code>def classify_example(example, tree):
    question = list(tree.keys())[0]
    feature_name, comparison_operator, value = question.split()

    # ask question
    if example[feature_name] <= float(value):
        answer = tree[question][0]
    else:
        answer = tree[question][1]

    # base case
    if not isinstance(answer, dict):
        return answer
    
    # recursive part
    else:
        residual_tree = answer
        return classify_example(example, residual_tree)
example = test_df.iloc[7]
example
classify_example(example, tree)<jupyter_output><empty_output><jupyter_text>10. Accuracy<jupyter_code>def calculate_accuracy(df, tree):

    df["classification"] = df.apply(classify_example, axis=1, args=(tree,))
    df["classification_correct"] = df["classification"] == df["Label"]
    
    accuracy = df["classification_correct"].mean()
    
    return accuracy
accuracy = calculate_accuracy(test_df, tree)
accuracy<jupyter_output><empty_output><jupyter_text>11. Few Changes in Regression  CART for Regression:![regression-cart.jpg](attachment:regression-cart.jpg)  Inplace of classification we calculate leaf i.e. mean of that groupe<jupyter_code>def create_leaf(data):
    
    label_column = data[:, -1]
    leaf = np.mean(label_column)
        
    return leaf<jupyter_output><empty_output><jupyter_text>Inplace of entropy we calculater mean square Error<jupyter_code>def calculate_mse(data):
    actual_values = data[:, -1]
    if len(actual_values) == 0:   # empty data
        mse = 0
        
    else:
        prediction = np.mean(actual_values)
        mse = np.mean((actual_values - prediction) **2)
    
    return mse
def get_potential_splits(data):
    
    potential_splits = {}
    _, n_columns = data.shape
    for column_index in range(n_columns - 1):          # excluding the last column which is the label
        values = data[:, column_index]
        unique_values = np.unique(values)
        
        potential_splits[column_index] = unique_values
    
    return potential_splits
def split_data(data, split_column, split_value):
    
    split_column_values = data[:, split_column]

    type_of_feature = FEATURE_TYPES[split_column]
    if type_of_feature == "continuous":
        data_below = data[split_column_values <= split_value]
        data_above = data[split_column_values >  split_value]
    
    # feature is categorical   
    else:
        data_below = data[split_column_values == split_value]
        data_above = data[split_column_values != split_value]
    
    return data_below, data_above<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10324352408520746, 'fraction_numerical': 0.008980924812588139, 'mean_word_length': 3.638209982788296, 'pattern_counts': {'":': 2, '<': 92, '<?xml version=': 0, '>': 84, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 18, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '18', 'dir': 'jupyter-structured-clean-dedup', 'id': '73744', 'license': 'MIT', 'n_tokens_mistral': 4296, 'n_tokens_neox': 4174, 'n_words': 871, 'path': '.ipynb_checkpoints/Decision Tree-checkpoint.ipynb', 'repo_name': 'Rami-RK/Machine-Learning-From-Scratch', 'size': '13473'}