How are features selected or prioritized in decision tree learning models?
In the examples that we studied in two previous posts, we examined decision
tree and random forest models of survivability of Titanic passengers, a
fairly canonical ML exercise. We have a data set consisting of a line for each
passenger category of Class (first, second, third, crew), Sex (M,F),
Age (Adult, Child), and whether or not they survived (Y,N). A fifth column
gave the frequency of occurrance of each category.

Which of these features is the most significant decider of the final
classification, survivability?

We recast all of the features into a Bernoulli random variable with
outcomes to facilitate the calculations, for example Class
class for yes, in third class, for no,
Sex for yes, for Male, and Age
for yes, for Adult.
The original data file had categories () and a
fifth column giving the number of passengers in each, which we unfolded
into a line per passenger. We can shuffle the lines to facilitate a random
drawing of a passenger, and to divide the dataset into a training and testing
batch.

using RDatasets,DataFrames
titanic=dataset("datasets","Titanic")
classmap2=function(str)
if str=="3rd"
1
else
0
end
end

sexmap=function(str)
if str=="Female" 
1
else
0
end
end

agemap=function(str)
if str=="Child" 
1
else
0
end
end

survivemap=function(str)
if str=="Yes" 
1
else
0
end
end

titanic2=titanic
titanic2=filter(row -> !(row.Freq == 0),  titanic2)
titanic2=transform(titanic2, :Class => ByRow(x -> classmap2(x)) => :Class)
titanic2=transform(titanic2, :Sex => ByRow(x -> sexmap(x)) => :Sex)
titanic2=transform(titanic2, :Age => ByRow(x -> agemap(x)) => :Age)
titanic2=transform(titanic2, :Survived => ByRow(x -> survivemap(x)) => :Survived)
titanic3=DataFrame()
for j in 1:nrow(titanic2)
for i in 1:titanic2.Freq[j]
push!(titanic3,titanic2[j,:])
end
end

Pick a Bernoulli random variable with success probability .
The entropy and Gini impurity are
maximal values of these two information content metrics (sum over
outcomes), if

which indicate that we have no real predictive ability of survivability
based on this feature. On the other hand if

which is very much lower than the extrema in . Extreme values of
mean that this feature is associated with no information gain of predictability,
lower values of mean that this feature makes prediction closer to a
sure thing. Low entropy or low Gini impurity translates into less
randomness of the variable.

Since entropy or Gini impurity are measures of randomness of a variable, we
can construct their values for the whole dataset’s classification variable
which is survivability. Out of passengers, survived.

sum(titanic2.Freq .* titanic2.Survived)
# 711

This is very close to even odds: a randomly selected passenger has just a bit
better than chances. If you wish to predict the survival probability
of a randomly selected passenger, taking no features into account, you would
say , but in fact some categories of passengers had very different
survival rates. How can you do better in your prediction making?
By splitting the data and using the features. Which features are the best
deciders of survival rate?

How many Female passengers were there?

# number of women
sum(titanic2.Freq .* titanic2.Sex)
470
# number of men
sum(titanic2.Freq .* (1 .- titanic2.Sex))
1731

# how many survived?
# number of women surviving
sum(titanic2.Freq .* titanic2.Sex .* titanic2.Survived)
344
# number of men surviving
sum(titanic2.Freq .* (1 .- titanic2.Sex) .* titanic2.Survived)
367

so the probability that a passenger is Female is and
the conditional probability that a passenger is Female and survives is
.

Compute as well the probability that a passenger is Male and
(probability of being Male and surviving)

(lower, predictable) and finally the conditional entropy for
splitting the data by sex

which is a vast improvement over the entropy with no features considered.

Define the information gain for splitting on this feature

Incorporating this feature in the decision process results in an improved
survivability probability prediction.

Let’s write a code to compute the entropy and information gain of a data split.
R has a library “FSelector” for feature selection, but I think that it is
always a good idea to write your own so that you understand underlying
principles.

""" Compute entropy for a vector of attribute numbers, ie include attributes
    1,2 (3rdclass yes, Sex=female yes) entropy([1,2])"""
entropy2=function(attrs:: Array,dataf:: DataFrame)
# how many have all attributes =1
Nattr1=sum(reduce(.* ,[dataf[:,j] for j in attrs]))
# prob that random item has all attribs
Pattr1=Nattr1/nrow(dataf)
# how many have all attributes and are in class=1
Nattr1C=sum(reduce(.* ,[dataf[:,j] for j in attrs]).*dataf[:,4])
# entropy for those with all attribs being in class 1
SCandAttr=-xlogx(Nattr1C/Nattr1)-xlogx(1.0-Nattr1C/Nattr1)
# Number that do not have all attributes
Nattr0=nrow(dataf)-Nattr1
# prob that random does not have all attribs
Pattr0=Nattr0/nrow(dataf)
# how many have none of the attributes and are in class=1
Nattr0C=sum(reduce(.* ,[1 .- dataf[:,j] for j in attrs]).*dataf[:,4])
# entropy for those without all atribs being in class 1
SCandNoAttr=-xlogx(Nattr0C/Nattr0)-xlogx(1.0-Nattr0C/Nattr0)
return Pattr1*SCandAttr+Pattr0*SCandNoAttr
end

""" julia does not give x*log2(x)=0 if x=0"""
xlogx=function(x)
if x==0.0
0.0
else
x*log2(x)
end
end

"""Probability of survival if have atributes attr"""
prob=function(attrs:: Array,dataf:: DataFrame)
Nattr=sum(reduce(.* ,[dataf[:,j] for j in attrs]))
NattrC=sum(reduce(.* ,[dataf[:,j] for j in attrs]) .* dataf[:,4])
return NattrC/Nattr
end


infogain=function(attrs:: Array,dataf:: DataFrame)
Nclass=sum(dataf[:,4])
Pclass=Nclass/nrow(dataf)
entrpy=-xlogx(Pclass)-xlogx(1.0-Pclass)
entrpy-entropy2(attrs,dataf)
end

Let’s use it to see how we should build a decision tree, by ordering the branching
according to information gain, the higher the gain of a split, the closer to
the base node of the tree

# third class is first feature
infogain([1],titanic3)
0.008030400990276632
# sex is second feature
infogain([2],titanic3)
0.14239119454923332
# age is the third feature
infogain([3],titanic3)
0.006410718332584997

so we will get the best/most useful decision tree by first splitting on
sex, the third class, then age. This is actually how we did our tree
in the earlier post, we lucked out.