<jupyter_start><jupyter_text>Preliminaries<jupyter_code># import modules
import numpy as np
from sklearn.datasets import load_digits
... # your code here
# base classes

class Node:
    pass

class Tree:
    def __init__(self):
        self.root = Node()
    
    def find_leaf(self, x):
        node = self.root
        while hasattr(node, "feature"):
            j = node.feature
            if x[j] <= node.threshold:
                node = node.left
            else:
                node = node.right
        return node<jupyter_output><empty_output><jupyter_text>Density Tree<jupyter_code>class DensityTree(Tree):
    def __init__(self):
        super(DensityTree, self).__init__()
        
    def train(self, data, prior, n_min=10):
        '''
        data: the feature matrix for the digit under consideration
        prior: the prior probability of this digit
        n_min: termination criterion (don't split if a node contains fewer instances)
        '''
        self.prior = prior
        N, D = data.shape
        D_try = int(np.sqrt(D)) # number of features to consider for each split decision

        # find and remember the tree's bounding box, 
        # i.e. the lower and upper limits of the training feature set
        m, M = np.min(data, axis=0), np.max(data, axis=0)
        self.box = m.copy(), M.copy()
        
        # identify invalid features and adjust the bounding box
        # (If m[j] == M[j] for some j, the bounding box has zero volume, 
        #  causing divide-by-zero errors later on. We must exclude these
        #  features from splitting and adjust the bounding box limits 
        #  such that invalid features have no effect on the volume.)
        valid_features   = np.where(m != M)[0]
        invalid_features = np.where(m == M)[0]
        M[invalid_features] = m[invalid_features] + 1

        # initialize the root node
        self.root.data = data
        self.root.box = m.copy(), M.copy()

        # build the tree
        stack = [self.root]
        while len(stack):
            node = stack.pop()
            n = node.data.shape[0] # number of instances in present node
            if n >= n_min:
                # Call 'make_density_split_node()' with 'D_try' randomly selected 
                # indices from 'valid_features'. This turns 'node' into a split node
                # and returns the two children, which must be placed on the 'stack'
                
                #Split two nodes
                left, right = make_density_split_node(node,N,np.random.choice(valid_features, D_try))
                stack.append(left)
                stack.append(right)
            else:
                # Call 'make_density_leaf_node()' to turn 'node' into a leaf node.
                make_density_leaf_node(node, N)# your code here

    def predict(self, x):
        m, M = self.box
        leaf = self.find_leaf(x)
        p = leaf.response*self.prior
        if (np.all(x<=M) and np.all(x>=m)):
            return p
        else:
            return 0
        # return p(x | y) * p(y) if x is within the tree's bounding box 
        # and return 0 otherwise
def make_density_split_node(node, N, feature_indices):
    '''
    node: the node to be split
    N:    the total number of training instances for the current class
    feature_indices: a numpy array of length 'D_try', containing the feature 
                     indices to be considered in the present split
    '''
    n, D = node.data.shape
    m, M = node.box
    
    #Volume of the Parent Node
    V = np.product(M-m)

    # find best feature j (among 'feature_indices') and best threshold t for the split
    e_min = float("inf")
    j_min, t_min = None, None
    
    for j in feature_indices:
        # Hint: For each feature considered, first remove duplicate feature values using 
        # 'np.unique()'. Describe here why this is necessary.
        data_unique = np.sort(np.unique(node.data[:, j]))
        # Compute candidate thresholds
        tj = (data_unique[1:] + data_unique[:-1])/2.0
        
        #Nl = len(np.where(data_unique < tj)[0])
        #Nr = len(np.where(data_unique > tj)[0])
        
        
        # Illustration: for loop - hint: vectorized version is possible
        for t in tj:
            #Compute number of instances left and right of threshold t
            Nl = len(data_unique[data_unique<t])
            Nr = len(data_unique[data_unique>t])
            
            #Compute volume of threshold
            Vl = V*(t-m[j])/(M[j]-m[j])
            Vr = V - Vl
            
            #Compute LOO error for both left and right children and add them
            loo_error = (Nl/(N*Vl))*(Nl/N - 2.0*(Nl-1)/(N-1)) + (Nr/(N*Vr))*(Nr/N - 2.0*(Nr-1)/(N-1))
            
            # choose the best threshold that minimi
            if loo_error < e_min:
                e_min = loo_error
                j_min = j
                t_min = t
                
                
    # create children
    left = Node()
    right = Node()
    
    X = node.data[:,j_min]
    M_left = M.copy()
    m_right = m.copy()
    
    M_left[j_min] = t_min
    m_right[j_min] = t_min
    
    # initialize 'left' and 'right' with the data subsets and bounding boxes
    # according to the optimal split found above
    left.data = node.data[X<t_min,:] # store data in left node -- for subsequent splits
    left.box = m, M_left # store bounding box in left node
    right.data = node.data[X>t_min,:]
    right.box = m_right, M

    # turn the current 'node' into a split node
    # (store children and split condition)
    node.left = left
    node.right = right
    node.feature = j_min
    node.threshold = t_min

    # return the children (to be placed on the stack)
    return left, right
def make_density_leaf_node(node, N):
    '''
    node: the node to become a leaf
    N:    the total number of training instances for the current class
    '''
    # compute and store leaf response
    m, M = node.box
    n = node.data.shape[0]
    v = np.product(M-m)
    node.response = n/(v*N)<jupyter_output><empty_output><jupyter_text>Decision Tree<jupyter_code>class DecisionTree(Tree):
    def __init__(self):
        super(DecisionTree, self).__init__()
        
    def train(self, data, labels, n_min=20):
        '''
        data: the feature matrix for all digits
        labels: the corresponding ground-truth responses
        n_min: termination criterion (don't split if a node contains fewer instances)
        '''
        N, D = data.shape
        D_try = int(np.sqrt(D)) # how many features to consider for each split decision

        # initialize the root node
        self.root.data = data
        self.root.labels = labels
        
        stack = [self.root]
        while len(stack):
            node = stack.pop()
            n = node.data.shape[0] # number of instances in present node
            if n >= n_min and not node_is_pure(node):
                # Call 'make_decision_split_node()' with 'D_try' randomly selected 
                # feature indices. This turns 'node' into a split node
                # and returns the two children, which must be placed on the 'stack'.
                ... # your code here
            else:
                # Call 'make_decision_leaf_node()' to turn 'node' into a leaf node.
                ... # your code here
                
    def predict(self, x):
        leaf = self.find_leaf(x)
        # compute p(y | x)
        return ... # your code here
def make_decision_split_node(node, feature_indices):
    '''
    node: the node to be split
    feature_indices: a numpy array of length 'D_try', containing the feature 
                     indices to be considered in the present split
    '''
    n, D = node.data.shape

    # find best feature j (among 'feature_indices') and best threshold t for the split
    ... # your code here

    # create children
    left = Node()
    right = Node()
    
    # initialize 'left' and 'right' with the data subsets and labels
    # according to the optimal split found above
    left.data = ... # data in left node
    left.labels = ... # corresponding labels
    right.data = ...
    right.labels = ...

    # turn the current 'node' into a split node
    # (store children and split condition)
    node.left = left
    node.right = right
    node.feature = ...
    node.threshold = ...

    # return the children (to be placed on the stack)
    return left, right    
def make_decision_leaf_node(node):
    '''
    node: the node to become a leaf
    '''
    # compute and store leaf response
    node.N = ...
    node.response = ... # your code here
def node_is_pure(node):
    '''
    check if 'node' ontains only instances of the same digit
    '''
    return ... # your code here<jupyter_output><empty_output><jupyter_text>Evaluation of Density and Decision Tree<jupyter_code># read and prepare the digits data
digits = load_digits()
data = digits["data"]
target = digits["target"]
labels = [0,1,2,3,4,5,6,7,8,9]
# your code here
# train trees, plot training error confusion matrices, and comment on your results
prediction = np.zeros(len(target))
posterior = np.zeros(len(target))
for l in labels:
    Density = DensityTree()
    data_l = data[target == l]
    prior_l = len(data_l)/len(data)
    Density.train(data_l,prior_l)
    for i in range(data.shape[0]):
        x = data[i,:]
        p = Density.predict(x)
        if p>posterior[i]:
            posterior[i] = p
            prediction[i] = l
print(np.sum(1*(prediction != target))/len(data))
    
        
# your code here<jupyter_output>0.2854757929883139<jupyter_text>Density and Decision Forest<jupyter_code>class DensityForest():
    def __init__(self, n_trees):
        # create ensemble
        self.trees = [DensityTree() for i in range(n_trees)]
    
    def train(self, data, prior, n_min=20):
        for tree in self.trees:
            # train each tree, using a bootstrap sample of the data
            ... # your code here

    def predict(self, x):
        # compute the ensemble prediction
        return ... # your code here
class DecisionForest():
    def __init__(self, n_trees):
        # create ensemble
        self.trees = [DecisionTree() for i in range(n_trees)]
    
    def train(self, data, labels, n_min=0):
        for tree in self.trees:
            # train each tree, using a bootstrap sample of the data
            ... # your code here

    def predict(self, x):
        # compute the ensemble prediction
        return ... # your code here<jupyter_output><empty_output><jupyter_text>Evaluation of Density and Decision Forest<jupyter_code># train forests (with 20 trees per forest), plot training error confusion matrices, and comment on your results
... # your code here<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09763121226196006, 'fraction_numerical': 0.00575940548072457, 'mean_word_length': 2.107070707070707, 'pattern_counts': {'":': 0, '<': 30, '<?xml version=': 0, '>': 31, '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': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '505106', 'license': 'MIT', 'n_tokens_mistral': 3270, 'n_tokens_neox': 3146, 'n_words': 1064, 'path': 'ex04/.ipynb_checkpoints/tree-methods-stubs-checkpoint.ipynb', 'repo_name': 'Osburg/Fundamentals-of-Machine-Learning', 'size': '10765'}