<jupyter_start><jupyter_text>test python files here<jupyter_code>from hw1_knn import KNN
from data import data_processing
Xtrain, ytrain, Xval, yval, Xtest, ytest = data_processing()

Xtrain, ytrain
len(Xtrain), len(ytrain)
KNN.train(Xtrain, ytrain)
model = KNN(1,null)
import numpy as np
from typing import List
point1 = [1,2,3,4]
point2 = [5,6,7,8]
real_labels = [0,1,1,0,1]
predicted_labels = [1,1,1,1,1]
print(set(zip(point1,point2)))<jupyter_output>{(1, 5), (2, 6), (3, 7), (4, 8)}<jupyter_text>utils.py<jupyter_code>import utils
utils.euclidean_distance(point1,point2)
utils.inner_product_distance(point1,point2)
def euclidean_distance(point1: List[float], point2: List[float]) -> float:
    return np.sqrt(sum([(a - b)**2 for a,b in zip(point1,point2)]))    
def gaussian_kernel_distance(point1: List[float], point2: List[float]) -> float:
    return  -1*np.exp(-1/2*(euclidean_distance(point1,point2)**2))
def inner_product_distance(point1: List[float], point2: List[float]) -> float:
    return sum(a*b for a,b in zip(point1,point2))
gaussian_kernel_distance(point1,point2)
def cosine_sim_distance(point1: List[float], point2: List[float]) -> float:
    return inner_product_distance(point1,point2)/(np.sqrt(sum(a**2 for a in point1)) * np.sqrt(sum(b**2 for b in point2)))
cosine_sim_distance(point1,point2)
np.sqrt(sum(a**2 for a in point1)) * np.sqrt(sum(b**2 for b in point2))
def f1_score(real_labels: List[int], predicted_labels: List[int]) -> float:
    """
    f1 score: https://en.wikipedia.org/wiki/F1_score
    """
    assert len(real_labels) == len(predicted_labels)

    return 2*sum(a*b for a,b in zip(real_labels,predicted_labels))/(sum(real_labels)+sum(predicted_labels))
f1_score(real_labels,predicted_labels)<jupyter_output><empty_output><jupyter_text>KNN Class<jupyter_code># for auto-reloading external modules
# see http://stackoverflow.com/questions/1907993/autoreload-of-modules-in-ipython
%load_ext autoreload
%autoreload 2
import numpy as np
from hw1_knn import KNN
from utils import euclidean_distance, gaussian_kernel_distance, inner_product_distance, cosine_sim_distance, f1_score
#from utils import f1_score, model_selection_without_normalization, model_selection_with_transformation
distance_funcs = {
    'euclidean': euclidean_distance,
    'gaussian': gaussian_kernel_distance,
    'inner_prod': inner_product_distance,
    'cosine_dist': cosine_sim_distance,
}
from data import data_processing
Xtrain, ytrain, Xval, yval, Xtest, ytest = data_processing()

Xtrain, ytrain
Xtrain[:10]
ytrain[:10]
distance_list = zip(Xtrain[:20],ytrain[:20])
k = 5
k_min_distance = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
print(list(zip(k_min_distance,ytrain[:10])))
sample = list(zip(k_min_distance,ytrain[:10]))
sample
sample[:-1]
for k in range(len(sample)):
    print(-k)
min_number = None
min_index = None
for length in range(len(sample)):
    index = length
    for a,b in sample[length:]:
        if max_number is None or max_number < a:
            if max_number is not None and max_number < a:
                sample[max_index], sample[index] = sample[index], sample[max_index]
            max_number = a
            max_index = index
        index += 1
sample.sort()
sample[:10]
k_min_distance[:10]
k_min_distance
distance_list.index(max(distance_list))
from __future__ import division, print_function

from typing import List, Callable

import numpy as np
import scipy
from collections import Counter


############################################################################
# DO NOT MODIFY ABOVE CODES
############################################################################

class KNN:

    def __init__(self, k: int, distance_function):
        self.k = k
        self.distance_function = distance_function

        

    #TODO: Complete the training function
    def train(self, features: List[List[float]], labels: List[int]):
        #raise NotImplementedError
        
        assert len(features) == len(labels)
        
        #store data only
        self.model_features = features
        self.model_labels = labels

        #print(self.model_features, model_lables)
     
    
    #TODO: Complete the prediction function
    def predict(self, features: List[List[float]]) -> List[int]:
        #raise NotImplementedError
        results:List[int] = []
        for single_point in features:
            single_predict = self.get_k_neighbors(single_point)
            if sum(single_predict)/len(single_predict) >= 0.5:
                results.append(1)
            else:
                results.append(0)
        
        return results
            
            
        
    #TODO: Complete the get k nearest neighbor function
    def get_k_neighbors(self, point: List[float]) -> List[int]:
        #raise NotImplementedError
        distance_list = []
        
        for single_point,single_label in zip(self.model_features,self.model_labels):
            distance_list.append([self.distance_function(point,single_point),single_label])
        
        distance_list.sort()
        results:List[int] = []
        for a,label in distance_list[:self.k]:
            results.append(label)
        return results
    
    #TODO: Complete the model selection function where you need to find the best k
    def model_selection_without_normalization(distance_funcs, Xtrain, ytrain, Xval, yval):
            
            #Dont change any print statement
            print('[part 1.1] {name}\tk: {k:d}\t'.format(name=name, k=k) + 
                      'train: {train_f1_score:.5f}\t'.format(train_f1_score=train_f1_score) +
                      'valid: {valid_f1_score:.5f}'.format(valid_f1_score=valid_f1_score))
    
            print()
            print('[part 1.1] {name}\tbest_k: {best_k:d}\t'.format(name=name, best_k=best_k) +
                  'test f1 score: {test_f1_score:.5f}'.format(test_f1_score=test_f1_score))
            print()
            return best_model, best_k, best_func
        

if __name__ == '__main__':
    print(np.__version__)
    print(scipy.__version__)

import utils
knn_model = KNN(10,utils.euclidean_distance)
from data import data_processing
Xtrain, ytrain, Xval, yval, Xtest, ytest = data_processing()

Xtrain[0]
sum(ytrain), len(ytrain)
Xtest[0], ytest
knn_model.train(Xtrain,ytrain)
knn_model.get_k_neighbors(Xtest[0])
knn_model.predict(Xtest)
for k in range(1,30,2):
    print(k)
from utils import euclidean_distance, gaussian_kernel_distance, inner_product_distance, cosine_sim_distance
from utils import f1_score
distance_funcs = {
    'euclidean': euclidean_distance,
    'gaussian': gaussian_kernel_distance,
    'inner_prod': inner_product_distance,
    'cosine_dist': cosine_sim_distance,
}
for key,fun in distance_funcs.items():
    print()
    print(fun)
def model_selection_without_normalization(distance_funcs, Xtrain, ytrain, Xval, yval):
    
    #In this part, you should try different distance function you implemented in part 1.1, and find the best k.
    #Use k range from 1 to 30 and increment by 2. We will use f1-score to compare different models.
    
    #Note: When there is a tie, chose model based on the following priorities:
    #Then check distance function [euclidean > gaussian > inner_prod > cosine_dist];
    #If they have same distance fuction, choose model who have a less k.
    
    # distance_funcs: dictionary of distance funtion
    # Xtrain: List[List[int]] train set
    # ytrain: List[int] train labels
    # Xval: List[List[int]] validation set
    # yval: List[int] validation labels
    # return best_model: an instance of KNN
    # return best_k: best k choosed for best_model
    # return best_func: best function choosed for best_model
    
    # raise NotImplementedError
    
    distance_funcs_pri = {
        'euclidean': 4,
        'gaussian': 3,
        'inner_prod': 2,
        'cosine_dist': 1,
    }
    
    best_model = None
    best_model_perf = None
    best_model_func = None
    
    for dis_name,dis_func in distance_funcs.items():
        
        for k in range(1,min(len(Xtrain),30),2):
        
            cur_model = KNN(k,dis_func)
            cur_model.train(Xtrain,ytrain)
            model_predict = cur_model.predict(Xval)
            cur_model_perf = f1_score(yval, model_predict)
            
            #TODO: check wether F1 score is better with higger
            #TODO: realize priority order           
            if best_model is None or best_model_perf < cur_model_perf: 
                best_model = cur_model
                best_model_perf = cur_model_perf
                best_model_func = dis_name
            elif best_model_perf == cur_model_perf:
                if distance_funcs_pri[best_model_func] < distance_funcs_pri[dis_name]:
                    best_model = cur_model
                    best_model_perf = cur_model_perf
                    best_model_func = dis_name
                elif distance_funcs_pri[best_model_func] == distance_funcs_pri[dis_name] and best_model.k > cur_model.k:
                    best_model = cur_model
                    best_model_perf = cur_model_perf
                    best_model_func = dis_name
                
                
            

    return best_model, best_model.k, best_model.distance_function
best_model, best_k, best_function = model_selection_without_normalization(distance_funcs, Xtrain, ytrain, Xval, yval)
best_model, best_k, best_function
sample
for single_data in sample:
    for a in single_data:
        vec_len = np.sqrt(sum(a**2))
    single_data = single_data / vec_len    
#not in use
for single_data in sample:
    sum_vec = 0
    for a in single_data:
        sum_vec += a**2
    for a in single_data:
        if(sum_vec != 0):
            a = a / np.sqrt(sum_vec)
sample = [[2, -1], [-1, 5], [0, 0]]
        results:List[List[float]] = []
        for single_data in sample:
            single:List[float] = []
            for a in single_data:
                if(inner_product_distance(single_data,single_data) != 0):
                   single.append(a / np.sqrt(inner_product_distance(single_data,single_data)))
                else:
                    single.append(a)
            results.append(single)
        print(results)
        left:List[float] = []
        right:List[float] = []
        results:List[List[float]]=[]
        for a,b in sample:
           left.append(a)
           right.append(b) 
        for a,b in sample:
            results.append([(a - min(left))/(max(left)-min(left)), (b-min(right))/(max(right)-min(right))])
        print(results)
min(left), max(left), min(right),max(right)
class MinMaxScaler:
    """
    You should keep some states inside the object.
    You can assume that the parameter of the first __call__
        must be the training set.

    Hints:
        1. Use a variable to check for first __call__ and only compute
            and store min/max in that case.

    Note:
        1. You may assume the parameters are valid when __call__
            is being called the first time (you can find min and max).

    Example:
        train_features = [[0, 10], [2, 0]]
        test_features = [[20, 1]]

        scaler = MinMaxScale()
        train_features_scaled = scaler(train_features)
        # now train_features_scaled should be [[0, 1], [1, 0]]

        test_features_sacled = scaler(test_features)
        # now test_features_scaled should be [[10, 0.1]]

        new_scaler = MinMaxScale() # creating a new scaler
        _ = new_scaler([[1, 1], [0, 0]]) # new trainfeatures
        test_features_scaled = new_scaler(test_features)
        # now test_features_scaled should be [[20, 1]]
    """
    
    def __init__(self):
        #for a,b in sample:
        #    results.append([(a - min(left))/(max(left)-min(left)), (b-min(right))/(max(right)-min(right))])
        self.first_time = True
        self.scaling:List[List[float]] = []

    def __call__(self, features: List[List[float]]) -> List[List[float]]:
        """
        normalize the feature vector for each sample . For example,
        if the input features = [[2, -1], [-1, 5], [0, 0]],
        the output should be [[1, 0], [0, 1], [0.333333, 0.16667]]
        """
        
        rotated = list(zip(*reversed(Xtrain)))
            

        
        if(self.first_time):
            for index in range(len(rotated)):
                self.scaling.append([min(rotated[index]),max(rotated[index])])
                self.first_time = False
        
        results = []
        for single_point in features:
            result = []
            for index, item in enumerate(single_point, start=0):   # default is zero
                if(self.scaling[index][1] == self.scaling[index][0]):
                    result.append(item)
                else:
                    result.append((item - self.scaling[index][0])/(self.scaling[index][1]-self.scaling[index][0]))
            results.append(result)
        return results
        #raise NotImplementedError
mmsc = MinMaxScaler()
Xtrain[0]
result = mmsc(Xtrain)
result
test = [[20,1]]
result = mmsc(sample)
print(result)
result = mmsc(test)
        train_features = [[0, 10], [2, 0]]
        test_features = [[20, 1]]    
    
        scaler = MinMaxScaler()
        train_features_scaled = scaler(train_features)
        print(train_features_scaled)
        # now train_features_scaled should be [[0, 1], [1, 0]]

        test_features_sacled = scaler(test_features)
        print(test_features_sacled)
        # now test_features_scaled should be [[10, 0.1]]

        new_scaler = MinMaxScaler() # creating a new scaler
        _ = new_scaler([[1, 1], [0, 0]]) # new trainfeatures
        test_features_scaled = new_scaler(test_features)
        print(test_features_scaled)
        # now test_features_scaled should be [[20, 1]]
class NormalizationScaler:
    def __init__(self):
        pass

    #TODO: normalize data
    def __call__(self, features: List[List[float]]) -> List[List[float]]:
        """
        normalize the feature vector for each sample . For example,
        if the input features = [[3, 4], [1, -1], [0, 0]],
        the output should be [[0.6, 0.8], [0.707107, -0.707107], [0, 0]]
        """
        results:List[List[float]] = []
        for single_data in features:
            single:List[float] = []
            for a in single_data:
                if(inner_product_distance(single_data,single_data) != 0):
                   single.append(a / np.sqrt(inner_product_distance(single_data,single_data)))
                else:
                    single.append(a)
            results.append(single)
        return results
features = [[3, 4], [1, -1], [0, 0]]
norm_dic = {
    'normalize': NormalizationScaler,
    'min_max_scale': MinMaxScaler,
}
scaler = norm_dic['min_max_scale']()
results = scaler(features)
results
for norm_class in norm_dic:
    scaler = norm_dic[norm_class]()
    results = scaler(features)
    print(results)
rotated = list(zip(*reversed(Xtrain)))
min(rotated[1]),max(rotated[1])
for a in range(len(rotated)):
    print(a)
# TODO: select an instance of KNN with the best f1 score on validation dataset, with normalized data
def model_selection_with_transformation(distance_funcs, scaling_classes, Xtrain, ytrain, Xval, yval):
    # distance_funcs: dictionary of distance funtion
    # scaling_classes: diction of scalers
    # Xtrain: List[List[int]] train set
    # ytrain: List[int] train labels
    # Xval: List[List[int]] validation set
    # yval: List[int] validation labels
    # return best_model: an instance of KNN
    # return best_k: best k choosed for best_model
    # return best_func: best function choosed for best_model
    # return best_scaler: best function choosed for best_model
    distance_funcs_pri = {
        'euclidean': 4,
        'gaussian': 3,
        'inner_prod': 2,
        'cosine_dist': 1,
    }
    normalizaion_pri = {
        'min_max_scale':2,
        'normalize':1,
    }
    
    best_model = None
    best_model_perf = None
    best_model_func = None
    best_scaler = None

    for norm_class in scaling_classes:
        scaler = scaling_classes[norm_class]()
        Xtrain_scaled = scaler(Xtrain)
        Xval_scaled = scaler(Xval)

        for dis_name,dis_func in distance_funcs.items():
        
            for k in range(1,min(len(Xtrain),30),2):
        
                cur_model = KNN(k,dis_func)
                cur_model.train(Xtrain_scaled,ytrain)
                model_predict = cur_model.predict(Xval_scaled)
                cur_model_perf = f1_score(yval, model_predict)

                if best_model is None or best_model_perf < cur_model_perf: 
                    best_model = cur_model
                    best_model_perf = cur_model_perf
                    best_model_func = dis_name
                    best_model_scaler = norm_class

                elif best_model_perf == cur_model_perf:
                    if normalizaion_pri[norm_class] > normalizaion_pri[best_model_scaler]:
                        best_model = cur_model
                        best_model_perf = cur_model_perf
                        best_model_func = dis_name
                        best_model_scaler = norm_class

                    elif normalizaion_pri[norm_class] == normalizaion_pri[best_model_scaler] and distance_funcs_pri[best_model_func] < distance_funcs_pri[dis_name]:
                        best_model = cur_model
                        best_model_perf = cur_model_perf
                        best_model_func = dis_name
                        best_model_scaler = norm_class
                        
                    elif normalizaion_pri[norm_class] == normalizaion_pri[best_model_scaler] and distance_funcs_pri[best_model_func] == distance_funcs_pri[dis_name] and best_model.k > cur_model.k:
                        best_model = cur_model
                        best_model_perf = cur_model_perf
                        best_model_func = dis_name
                        best_model_scaler = norm_class
    
    return best_model, best_model.k, best_model.distance_function, best_scaler
Parent_Entropy = 10 #?
Braches_Sample = [[6,7,7,2,10,8,6], [2,0,6,10,4,0,0]]
#assumption data is S,Brach(List[List[int]])
#Brach should be like [ [32,70], [30,60], [40,40]]
#which have first arg as number of instances and second arg as number of instances this brach has
# TODO: Information Gain function
def Information_Gain(S, branches):
    # S: float
    # branches: List[List[int]] num_branches * num_cls
    # return: float
    def entropy(branch:List[int]) -> List[float]:
        result:List[float] = []
        b = sum(branch)
        for a in branch:
            if(a/b == 0):
                result.append(0)
            else:
                result.append(-1*(a/b)*np.log2(a/b))
        return result
    
    
    entropy_list:List[List[float]] = []
    sum_of_instances:List[int] = []
    
    for branch in branches:
        entropy_list.append(entropy(branch))
        sum_of_instances.append(sum(branch))
    sum_of_all_cases = sum(sum_of_instances)
    
    result = S
    for entropy_row, num_of_case in zip(entropy_list, sum_of_instances):
        result -= sum(entropy_row) * num_of_case / sum_of_all_cases 

    return result
    #raise NotImplementedError
Information_Gain(Parent_Entropy,Braches_Sample)
class TreeNode(object):
    def __init__(self, features, labels, num_cls):
        # features: List[List[any]], labels: List[int], num_cls: int

        # parametes given with initialization
        # self.cls_max is for specific label with most counts
        # self.splittable is whether still able for further split

        # following is parameters need to be applied
        # self.dim_split is index of feature to be split
        # self.feature_uniq_split are boundray value of feature
        
        ###
        # Note: self.feature_uniq_split must be sorted in any cases

        self.features = features
        self.labels = labels
        self.children = []
        self.num_cls = num_cls
        # find the most common labels in current node
        count_max = 0
        for label in np.unique(labels):
            if self.labels.count(label) > count_max:
                count_max = labels.count(label)
                self.cls_max = label
                # splitable is false when all features belongs to one class
        if len(np.unique(labels)) < 2:
            self.splittable = False
        else:
            self.splittable = True

        self.dim_split = None  # the index of the feature to be split

        # list of candidate feature values
        # if test data has value out of this list then choose majority of class
        self.feature_uniq_split = None  # the possible unique values of the feature to be split

    #TODO: try to split current node

    # In the TreeNode class, the features variable means all the points in current TreeNode,
    # and the labels variable means the corresponding labels for all data.
    # The children variable is a list of TreeNode after split the current node based on the best attributs.
    # This should be a recursive process that once we call the split function, the TreeNode will keep spliting 
    # untill we get the whole tree structure.
    def split(self):
        
        if not self.splittable:
            # this case for only one class (self.cls_max)
            # set all split as default and return self.cls_max as result
            return self
        elif len(self.features) == 0 and self.num_cls != 0:
            # this case for no more features available
            # choose majority of classes as result self.cls_max
            return self
        
        elif len(self.features) == 0 and self.num_cls == 0:
            # this case return majority of classes with parent node
            # !!! Consider when predicating parent result should be hold
            return self
        
        
        #TODO: produce specifc feature brach result    
        candidate_value_list:List[List[any]] = []
        
        tmp = np.sort(np.array(self.features).transpose())
        for row in tmp:
            candidate_value_list.append(np.unique(row))
            
        Entropy_for_Features:List[float] = []
        for index,candidate_feature in enumerate(candidate_value_list, start=0):
            tmp_branch_data:List[any] = []
            class_dic = {}
            for current_value in candidate_feature:
                #choose instances with specific feature value and return as branch set,
                #this branch set should have deleted specific locaiton feature
                for row in self.features:
                    if row[index] == current_value:
                        tmp = row
                        tmp_branch_data.append(tmp.pop(index))
                
                #entropy for a specifc feature
            Entropy_for_Features.append(-1*Util.Information_Gain(0,tmp_branch_data))
        
        #get a entropy list in Entropy_for_Features:List[float]
        #consider when have same entropy value and how to compare
        # find index of all max entropy
        candidate_features:List[int] = []
        for index, entropy in enumerate(Entropy_for_Features, start=0):
            if entropy == max(Entropy_for_Features):
                candidate_features.append(index)
        # if only one maximum entropy
        if len(candidate_features) == 1:
            self.dim_split = candidate_features[0]
        # more than one maximum entropy
        # init: transpose features matrix for picking up data line
        transpose_features = np.array(self.features).transpose()
        # storage for best candidate
        if len(candidate_features) > 1:
            best_candidate_index = len(transpose_features)+1
            best_unique_number = 0
            for candidate_feature_index in candidate_features:
                unique_feature_number = len(np.unique(transpose_features[candidate_feature_index]))
                if unique_feature_number > best_unique_number:
                    best_candidate_index = candidate_feature_index
                    best_unique_number = unique_feature_number
                elif (unique_feature_number == best_unique_number) and (best_candidate_index > candidate_feature_index):
                    best_candidate_index = candidate_feature_index
                    best_unique_number = unique_feature_number
            self.dim_split = best_candidate_index
        # dimension has been chosen
        
        #####
        # TODO: check variable
        # put candidate unique values into self.feature_uniq_split
        # self.feature_uniq_split = np.unique(transpose_features[self.dim_split])
        #####
        
        # initialize treenode and put in self.children
        # features, labels, num_cls are required parameters
        # pick up data row with specific value
        # feature value from min to max
        feature_values = transpose_features[self.dim_split].sort()
        for cur_value in feature_values:
            children_features:List[any] = []
            children_labels:List[int] = []
            for index,feature_row in enumerate(self.features, start=0):
                if feature_row[self.dim_split] == cur_value:
                    #features with specific value has been taken out
                    #labels for that position
                    children_features.append(feature_row[self.dim_split].pop(index))
                    children_labels.append(self.labels[index])
            # num_cls for new node
            children_num_cls = len(np.unique(children_labels))
            self.children.append(TreeNode(children_features, children_labels, children_num_cls))
            self.feature_uniq_split.append(cur_value)
 

        #raise NotImplementedError
    
    # TODO: predict the branch or the class
    def predict(self, feature):
        # feature: List[any]
        # return: int predicated class
        
        # reach leaf
        if len(self.children) == 0:
            return self.cls_max
        
        for index, boundary in enumerate(self.feature_uniq_split,start=0):
            if feature[self.dim_split] <= boundary:
                # hit the branch, return branch result but features has to be removed on specific column
                return self.predict(feature.pop(index))
        
        #raise NotImplementedError
        

label_sample = [1,0]
len(np.unique(label_sample))
for a in range(min(label_sample),max(label_sample)+1):
    print(a)
for a in range(2):
    print(a)
Braches_Sample = [[6,7,7,10,10,8,6], [2,0,6,10,10,0,0]]
result = []
tmp = np.sort(np.array(Braches_Sample).transpose())
for row in tmp:
    result.append(np.unique(row))
print(result)
np.array(Braches_Sample).transpose()
Braches_Sample[0].pop(0)
Braches_Sample
test:List[any] = [['b', 'a', 'c'], [3,1,2]]
print(test)
print(sorted(test,key=lambda x: (x[0],x[1])))
print(test)
Counter([1,1,1,1,2,3,3,5])
def call_return():
    if True:
        return
    print('not return')
call_return()
length_test = [6,7,7,10,10,8,6]
length_test[:2]
pyList = ['P', 'y', 't', 'h', 'o', 'n','P', 'y', 't']
print(len(pyList))

step = int(np.ceil((len(pyList)/5)))
data_folds:List[List[any]] = []

if len(pyList) % 2 == 1:

    for a in range(step, len(pyList)+step, step):
        sObject = slice(a - step, a, 1)
        data_folds.append(list(pyList[sObject]))
    
if len(pyList) % 2 == 0:

    for a in range(step, len(pyList)+step, step):
        sObject = slice(a - step, a, 1)
        data_folds.append(list(pyList[sObject]))

print(data_folds)


# TODO: implement reduced error prunning function, pruning your tree on this function
def reduced_error_prunning(decisionTree, X_test, y_test):
    # decisionTree trained based on training data set.
    # X_test: List[List[any]] test data, num_cases*num_attributes
    # y_test: List test labels, num_cases*1

    #     Reduced Error Pruning
    # 0. Split data into training and validation sets.
    # 1. Do until further pruning is harmful:
    # 2. Evaluate impact on validation set of pruning each possible node (plus those below it)
    # 3. Greedily remove the one that most improves validation set accuracy
    # - Produces smallest version of most accurate subtree.
    # - Requires that a lot of data be available.

    # step 0 split data into training and validation
    # 5flod-cross validation
    # objective: separate main function with two parts,
    # one for data flow made and one for further prunning
    
    NO_FOLDS = 5
    ori_trainning_set = decisionTree.features
    #split data into 5 fold
    
    step = int(np.ceil((len(ori_trainning_set)/NO_FOLDS)))
    data_folds:List[List[any]] = []

    if len(ori_trainning_set) % 2 == 1:

        for a in range(step, len(ori_trainning_set)+step, step):
            sObject = slice(a - step, a, 1)
            data_folds.append(list(ori_trainning_set[sObject]))
    
    if len(ori_trainning_set) % 2 == 0:

        for a in range(step, len(ori_trainning_set)+step, step):
            sObject = slice(a - step, a, 1)
            data_folds.append(list(ori_trainning_set[sObject]))

    #data_folds are 5 folds of training dataset
    
    for index in range(NO_FOLDS):
        # index from 0 - 4
        validation_set = data_folds[index]
        for i in range(NO_FOLDS):
            if i != index:
                trainning_set.extend(data_folds[i])
    
    print(validation_set, trainning_set)


    raise NotImplementedError
# TODO: implement reduced error prunning function, pruning your tree on this function
def reduced_error_prunning(decisionTree, X_test, y_test):
    # decisionTree trained based on training data set.
    # X_test: List[List[any]] test data, num_cases*num_attributes
    # y_test: List test labels, num_cases*1

    #     Reduced Error Pruning
    # 0. Split data into training and validation sets.
    # 1. Do until further pruning is harmful:
    # 2. Evaluate impact on validation set of pruning each possible node (plus those below it)
    # 3. Greedily remove the one that most improves validation set accuracy
    # - Produces smallest version of most accurate subtree.
    # - Requires that a lot of data be available.

    # step 0 split data into training and validation
    # 5flod-cross validation
    # objective: separate main function with two parts,
    # one for data flow made and one for further prunning
    
    # NO_FOLDS = 5
    # ori_trainning_set = decisionTree.root_node.features
    # #split data into 5 fold
    
    # step = int(np.ceil((len(ori_trainning_set)/NO_FOLDS)))
    # data_folds:List[List[any]] = []

    # if len(ori_trainning_set) % 2 == 1:
        
    #     #original is len(ori_trainning_set)+step+1
    #     for a in range(step, len(ori_trainning_set)+step, step):
    #         sObject = slice(a - step, a, 1)
    #         data_folds.append(list(ori_trainning_set[sObject]))
    
    # if len(ori_trainning_set) % 2 == 0:

    #     for a in range(step, len(ori_trainning_set)+step, step):
    #         sObject = slice(a - step, a, 1)
    #         data_folds.append(list(ori_trainning_set[sObject]))

    # #data_folds are 5 folds of training dataset
    
    # for flod_index in range(NO_FOLDS):
    #     # index from 0 - 4
    #     validation_set = []
    #     trainning_set = []
        
    #     validation_set = data_folds[flod_index]
    #     for i in range(NO_FOLDS):
    #         if i != flod_index:
    #             trainning_set.extend(data_folds[i-1])
        
    #     #data ready
    #     #step 1 Evaluate impact on validation set of pruning each possible node (plus those below it)
    #     # TODO: consider use recursive function to prun node until no harm
    #     # Note: try to swtich harm critea between acc harm is 0 and not
    #     #





    # orginal length has 1107
    # trainig length has 885
    # validation length has 219
    # total has 1104 
    # lost is 3
    ########################
    # assuming lose is acceptable

    #print('training set is:' + str(trainning_set))
    #print('validation set is:' + str(validation_set))
    # print('length of ori:'+str(len(ori_trainning_set)))
    # print('length of training:'+str(len(trainning_set)))
    # print('length of validaiton:'+str(len(validation_set)))
    # print('length of both train and validaiton:'+str(len(trainning_set)+len(validation_set)))

    #step 0 use Xtest and ytest as validation dataset
    validation_set = X_test
    real_labels = y_test
    
    #prediction labels
    est_labels:List[int] = []
    
    dummy_root = decisionTree.root_node
    
    # what is prun? make node without children ues cls_max as its prediction result
    # assuming prun from bot to top because too deep make tree overfitting,
    # but shallow will make underfitting.
    # pruninig every level or 

for a in range(5):
    print(a)
test_example = [0]
test_example.append(1)
test_example<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10031595576619273, 'fraction_numerical': 0.01446105237574432, 'mean_word_length': 2.601422319474836, 'pattern_counts': {'":': 0, '<': 20, '<?xml version=': 0, '>': 33, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '637089', 'license': 'MIT', 'n_tokens_mistral': 10392, 'n_tokens_neox': 9958, 'n_words': 2645, 'path': 'PA1/Untitled.ipynb', 'repo_name': 'Magicicesea/Python-Machine-Learning-algorithm-implement', 'size': '32916'}