<jupyter_start><jupyter_text>Helping Implementation<jupyter_code>def split_data(df, percentage=.75):
    T = int(len(df)*percentage)
    return df[:T], df[T:]
def XOR(X):
    if len(X) is 2: return bool(X[0]) != bool(X[1])
    return XOR(X[1:]) != bool(X[0])<jupyter_output><empty_output><jupyter_text>Create Random Data<jupyter_code>N,f, n, p = 20, 6, 1, .5  # number of data instance, feature, trials, probability of each trial
X = np.random.binomial(n, p, [N,f])
y = np.array([int(XOR(x_i)) for x_i in X]).reshape(N,1)
df = pd.DataFrame(data=np.hstack((X,y)), columns=['x%i'%i for i in range(f)]+['y'])
df.head()
df_train, df_test = split_data(df, .80<jupyter_output><empty_output><jupyter_text>Algorithm<jupyter_code>def entropy(probability):
    return sum([-p_x * log2(p_x) for p_x in probability])
def list_entropy(a_list):
    count_values = Counter(x for x in a_list)
    num_instances = len(a_list)
    probability = [x / num_instances for x in count_values.values()]
    return entropy(probability)
def information_gain(df, parent, child , trace=0):
    # Calculate Entropy for Child Attribute, as well as
    # Proprabilty of observations in Each Data-Parent
    
    df_parent = df.groupby(parent)
    
    num_instances = len(df.index)
    df_agg_ent = df_parent.agg({child : [list_entropy, lambda x: len(x)/num_instances] })

    df_agg_ent.columns = ['entropy', 'proprabilty_observations']
    
    # Calculate Information Gain:
    expected_entropy = sum(df_agg_ent['entropy'] * df_agg_ent['proprabilty_observations'])
    entropy = list_entropy(df[child])
    
    return entropy - expected_entropy
def id3(df, target_attribute_name, attribute_names, default_class=None):
    
    # Tally target attribute:
    cnt = Counter(x for x in df[target_attribute_name])# class of YES /NO
    
    # First check: Is this split of the dataset homogeneous?
    if len(cnt) == 1:
        # next input data set, or raises StopIteration when EOF is hit.
        return next(iter(cnt))
    
    # Second check: Is this split of the dataset empty?
    # if yes, return a default value
    elif df.empty or (not attribute_names):
        return default_class  # Return None for Empty Data Set
    
    # Otherwise: This dataset is ready to be devied up!
    else:
        
        # Get Default Value for next recursive call of this function:
        default_class = max(cnt.keys())
        
        # Compute the Information Gain of the attributes:
        gainz = [information_gain(df, attr, target_attribute_name) for attr in attribute_names]
        
        # Index of Best Attribute
        index_of_max = gainz.index(max(gainz)) 
        
        # Choose Best Attribute to split on:
        best_attr = attribute_names[index_of_max]
        
        # Create an empty tree, to be populated in a moment
        tree = {best_attr:{}} # Iniiate the tree with best attribute as a node 
        remaining_attribute_names = [i for i in attribute_names if i != best_attr]

        # Split dataset
        # On each split, recursively call this algorithm.
        # populate the empty tree with subtrees, which are the result of the recursive call
        for attr_val, data_subset in df.groupby(best_attr):
            subtree = id3(data_subset,
                        target_attribute_name,
                        remaining_attribute_names,
                        default_class)
            
            tree[best_attr][attr_val] = subtree
        return tree
def classify(instance, tree, default=None):
    
    attribute = next(iter(tree))
    
    # Value of the attributs in  set of Tree keys
    if instance[attribute] in tree[attribute].keys():  
        result = tree[attribute][instance[attribute]]
        
        # this is a tree, delve deeper
        if isinstance(result, dict): 
            return classify(instance, result)
        else:
            return result
    else:
        return default<jupyter_output><empty_output><jupyter_text>Evaluation<jupyter_code>attribute_names = list(df_train.columns)

tree = id3(df_train, 'y', attribute_names)
df_test['predicted'] = df_test.apply(classify, axis=1, args=(tree,'No')) 
# classify func allows for a default arg: when tree doesn't have answer for a particular
# combitation of attribute-values, we can use 'no' as the default guess 

print('Accuracy : %s'%str(sum(df_test['y']==df_test['predicted'])/len(df_test)))
df_test<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10144600090375057, 'fraction_numerical': 0.004970628106642567, 'mean_word_length': 3.1568075117370893, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 17, 'https://': 0, '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': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '350528', 'license': 'MIT', 'n_tokens_mistral': 1421, 'n_tokens_neox': 1383, 'n_words': 397, 'path': 'ID3/Decision-Tree-ID3.ipynb', 'repo_name': 'SamirMoustafa/Machine-Learning-Implementation', 'size': '4426'}