import numpy as np

from collections import Counter

from sklearn import datasets, model$\_$selection

# No other libraries will be imported

# load the Iris Dataset, which contains $150$ samples.

# each sample has $4$ features.

# the dataset contains $3$ classes of $50$ instances each, where each class refers to a type of iris plant.

iris $=$ datasets.load$\_$iris$()$

X $=$ np$.$array$($iris$.$data$)$ # features, numeric attributes. $[$Sepal length, Sepal Width, Petal length, Petal width$]$

Y $=$ np$.$array$($iris$.$target$)$ # labels: class$-0,$ class$-1,$ class$-2$

X$\_$train, X$\_$test, Y$\_$train, Y$\_$test $=$ model$\_$selection.train$\_$test$\_$split$($X$,$ Y$,$ test$\_$size$=0\mathrm{.}25,$ random$\_$state$=0)$

print$("$Train Shape:", X$\_$train.shape$)$

print$("$Train Shape:", X$\_$test.shape$)$

$3.$ Calculate Information Gain for each attribute $($numeric$),$ and show the feature that should be used first when build a decision tree.

step$-1$: find the best cutpoint for each attribute. $($find value to split the data$)$

step$-2$: calculate the information gain for each attribute. $($decide the order of attributes when build DT$)$

#$--------------------$ Some helper functions $------------------------------$

# calculate Entropy for a given distribution H$($X$).$

def entropy$($probabilities: list$)->$ float:

return sum$([-$p $*$ np$.$log$2($p$)$ for p in probabilities if p$>0])$

# given a list of labels, return the probability for each class P$($Y$).$

def class$\_$probabilities$($labels: list$)->$ list:

total$\_$count $=$ len$($labels$)$

return $[$label$\_$count $/$ total$\_$count for label$\_$count in Counter$($labels$).$values$()]$

# calculate the Entropy H$($Y$)$ for a given list of labels.

def data$\_$entropy$($labels: list$)->$ float:

return entropy$($class$\_$probabilities$($labels$))$

# split data into two sub$-$groups $[$group$1,$ goup$2]$ based on attribute $[$feature$\_$idx$]$ and value $[$feature$\_$val$]$

# if sample$[$feature$\_$idx$]<$ feature$\_$val:

# group$1<-$ sample

# else:

# group$2<-$ sample

def split$\_$data$($data: np$.$array, feature$\_$idx: int, feature$\_$val: float$)->$ tuple:

mask$\_$below$\_$threshold $=$ data$[$:$,$ feature$\_$idx$]<$ feature$\_$val

group$1=$ data$[$mask$\_$below$\_$threshold$]$

group$2=$ data$[$~mask$\_$below$\_$threshold$]$

return group$1,$ group$2$

# calculate the entropy for current partition. H$($Y$|$X$=$feature$\_$val$)$

def partition$\_$entropy$($g$1\_$labels: list, g$2\_$labels:list$)->$ float:

total$\_$count $=$ len$($g$1\_$labels$)+$ len$($g$2\_$labels$)$

#weighted combination of conditional entropy in both group$1$ and group$2.$

return data$\_$entropy$($g$1\_$labels$)*($len$($g$1\_$labels$)/$total$\_$count$)+$ data$\_$entropy$($g$2\_$labels$)*($len$($g$2\_$labels$)/$total$\_$count$)$

#$-----------------------------------------------------------------------------------------$

#$----------------------------$ Examples to use the Helper functions $-----------------------$

# calculate the H$($Y$)$ for the train and test data:

print$($data$\_$entropy$($Y$\_$train$))$

print$($data$\_$entropy$($Y$\_$test$))$

## to split the data based on feature$\_$idx and feature$\_$val:

train$\_$data $=$ np$.$concatenate$(($X$\_$train, np$.$reshape$($Y$\_$train, $(-1,1))),$ axis$=1)$ # concatenate $[$X$\_$train, Y$\_$train$]$

print$($train$\_$data.shape$)$

# split the data into two subgroups

g$1,$ g$2=$ split$\_$data$($train$\_$data, feature$\_$idx$=1,$ feature$\_$val$=3)$

print$($g$1.$shape$)$

print$($g$2.$shape$)$

# calculate the weighted entropy for the current split.

print$($partition$\_$entropy$($g$1[$:$,-1],$ g$2[$:$,-1]))$

#$-----------------------------------------------------------------------------------------$

#$--------------------------------$ Your implementation $------------------------------------$

# Initialize variables to store the best cutpoint and information gain for each attribute

#$-----------------------------------------------------------------------------------------$

#$-----------------------------------$ Printing $--------------------------------------------$

#print the calculated cutpoint $[$feature$\_$val$]$ and information gain for each attribute.

# print the feature should be used first when build decision tree.

Please help me complete this code