Classification and Regression Trees(contd) Video Lecture | What is Data Analytics? - Data & Analytics

hi so in this module we'll continue
looking at classification and regression
trees so in the previous module we
looked at how to build the tree right
but we never looked at when to stop so
if you continue growing a very large
tree so we might end up making a lot of
decisions and essentially end up
specializing your tree to individual
data points so it will lead to
overfitting of your tree to the data and
that is not a good place to be in on the
other hand if you stop growing your tree
too soon right you might miss out on
finding interesting patterns in the data
right so for example the very famous X
or case right so there is no single
attribute on which you can split and get
any kind of improvement in your
performance because whether you split on
x1 or whether you split on x2 so half
your data is going to be positive the
other half is going to be negative right
so you really cannot hope to get any
improvement by only splitting on one
attribute so you just kind of stop that
saying that hey there is no one
individual attribute that gives me an
improvement in performance and therefore
let me stop so you might lose out on
interesting patterns if you are going to
stop too early right so you cannot leave
a tree that is very very specialized to
small data points and you cannot stop
early as well
so what do we do so you typically grow
the tree until you come to a point where
there are few data points in the leaves
the leaf here would correspond to region
so I keep going the tree until I come to
a point where each region has only a few
data points typically you would like to
have what four or five data points at
least per region right so for using some
of the standard tools say something like
weaker the Vica actually stops by
default when the number of data points
in a region
go down to two so it will stop only at
that point that that's still a
significant overfitting
right so you grew a large tree right
where there are very few points per
region and then you then you prune the
tree you basically start trying to
collapse the internal nodes in the tree
such that they come up with a better
better tree right so we have looked at
how you need a validation set so you
have a training data and you have a
validation data so one way of looking at
pruning is to say that I look at the
performance of the three on the
validation data so look at the
performance of the tree on the
validation data and then I'll start
collapsing some of the internal nodes of
the tree so what do I mean by that
suppose that I have a tree that let's
think of the tree that we had earlier
right so this is the tree that we had
earlier so one way of pruning something
like this could be to say that I am
going to collapse one of the internal
nodes right and replace it with a single
region so that I have proved the tree so
this corresponds in the picture this
corresponds to doing something like
right so that is our four prime now I
can look at the performance of this
pruned tree on the validation data
versus the performance of the original
tree on the validation data so now if
there is not a significant dip in the
performance when I have removed one of
the internal nodes then I am keep this
new tree so that essentially tells me
that whatever I did in terms of the
previous tests on t4 or something that
was peculiar to the training data so I
look at it in the validation set but it
really does not look like I need to make
that split right or on the other hand
there might be a slight decrease in
performance when I go from the original
tree to the prune tree now the question
you have to ask yourself is okay given
the fact that I have reduced the size of
the tree is it okay to pay the penalty
in terms of that slight reduction in
performance so that is this trade-off
right so that is this what would call
the
the cost complexity trade-off so there
is a cost that you incur in terms of the
the miss classification that or the miss
prediction in this case that you are
going to make in terms of the the
reduced reduction in the number of
regions and the complexity is
essentially the number of tests that you
have to perform and the size of the
decision tree that you are operating
with right so this is the cost
complexity trade-off and depending on
which side of the cost complexity
trade-off that you want to be on we can
get more complex or less complex trees
okay so there are many ways in which
this kind of pruning techniques can be
implemented and one simple way is say
since Lee to choose a validation set
right and then have a trade-off between
the prediction error of the prune tree
in the validation set versus some
measure of complexity of the tree so one
measure of complexity of the tree is the
number of internal nodes that you have
in the tree so you can basically
trade-off the two and try to come up
with a good smaller tree so far we have
been talking about regression trees and
so far we have been talking about
regression trees and we looked at how we
would split regions right and once
having split the found the regions how
do you fit what is the best prediction
that you have to make in each of those
regions right and how did we find the
regions we adopted a greedy approach by
picking one variable at a time and then
trying to find out which is the best
point to split the variable right and we
looked at the the square the prediction
error and essentially now if you want to
look at classification trees
don't look at classification trees the
only thing we have to ask ourselves is
what is the appropriate measure that we
will have to look at in the greedy
search procedure right so once we decide
on what the appropriate measure is so
the rest of the framework that we need
to build classification trees is already
in place right so we can do the greedy
algorithm and then once we know what is
the appropriate measure that we are
going to use we can optimize that
measure in the greedy algorithm and we
can use the same setup that we have for
pruning so we have a validation data and
then we have a cost complex free
trade-off but the cost instead of being
measured by the squared error is going
to be measured by whatever metric we
choose for my classification right so I
am going to say that I will build a
classification tree where the prediction
so we will call as P hat
okay
right so so p-hat here is the
probability that a data point in region
M belongs to class K the data point in
region M so one of these regions what is
the probability that this data point
belongs to class K so I am going to look
at all the data points that fall in the
region R M so I am going to look at all
the data points that fall in the region
M and look at whether their class their
class labels in the training data
whether it belongs to class K right so
if a point X I in region M if the label
is K right then this will be 1 so this
summation is essentially going to count
the number of data points in region M
that belongs to class 1 number of data
points in region 1 that belong to class
2 and so on so forth this expression is
for class K right and then I am going to
divide it by the total number of points
that fall in region M so nm is the total
number of points in region M so this
essentially gives me an empirical
estimate of the probability of a data
point falling in region belonging to
class K right and if I am interested in
actually returning the class label then
so the class
in region n I is going to be
so the classes class the class that I
will assign two data points in region is
essentially that K that gives me the
maximum p hat value that makes sense so
look at the different error measures
that we can use so what is the most
popular error measure in classification
or which is the most appropriate error
measure in classification is a simple
thing called a miss classification error
right the misclassification error is
given by
so the number of times the actual label
does not match the prediction that we
make by our classifier so Class M is the
prediction made by our classifier in the
MF region right so for all the data
points in the Emmett region
whenever the class label the true class
label does not match the predicted class
label so I am going to sum it up divide
by the total number of data points in
that region so this gives me the MIS
classification error write this for a
specific region and I can do this over
all regions and that gives me the total
ms classification error so if you think
about it this is essentially so the
number of times this is school should
have been correct is given by P hat m
and the class that I am going to predict
right so this is given this gives me the
maximum from the previous expression
that we had so the total miss
classification error will be 1 minus P
hat m so I can use this as my error
measure so once I estimate P hat the
once I estimate the Arg max over K of P
hat MK then 1 minus that gives me the
miss classification error for that
region I can sum this over all the
regions right but then there are a
couple of slightly more common error
measures that are used especially in the
decision theory this dysentery
literature right so one of these is
called
one of these measure is called cross
entropy or deviance the cleats leads to
something called information gain
measure for looking at the splitting
criterion so the cross entropy is given
by
so this is P hat MK is the label
distribution that we have inferred is a
label distribution that we have inferred
from the data that was given to us but
if we stop and think about it right if
you have sufficient training data so
that P hat MK is actually the true
output label distribution as well right
so so this cross entropy term actually
gives us in some sense the amount of
information that we need to encode the
true label given that you are in the
region M so this gives rise to this
measure called information gain that
tells us that ok if I have not split
into the following set of regions how
much information would I need to
represent the labels of the data versus
having split into all these regions how
much less information do I need right if
I do not know anything right about where
the data point lies on this entire plane
right then I have some amount of
uncertainty about what the label is
right once I know that the data point
lies in r1 or r2 versus the rest of the
plane I have less uncertainty about what
the label should be right and so given
that when I have split the data into two
regions I have gained some information
about what the label should be and that
leads to this notion of an information
gain measure right and so it comes from
this cross entropy term and we can use
this also as a measure for splitting the
tree in the greedy growing stage last
one
is a Guinea index is given by the
expression P hat MK into 1 minus P hat
MK and it is actually a measure of the
the disparity in the population of
distribution of variables right so if
you think about it so this is the
probability that the label K appears in
the distribution in a particular region
m and this is a probability that the
label K does not appear in the
distribution M and this expression will
be maximum when they are equally likely
it's probably the label K appearing and
the label K not appearing in the region
M or equally likely so that is really a
bad situation for us to be in so in some
sense having a high value here
essentially is a indicator that this is
not a great way of splitting the data
into different regions so when you could
use one any of these three measures in
terms of growing addition tree and they
have their own advantages and
disadvantages and so the cross entropy
and the Gini index are more sensitive to
node probabilities than this
classification rate but then quite often
we find that these lead to much better
trees than using the misclassification
rate directly so that brings us to the
end of our discussion on classification
and regression trees but there are a few
points that I would like to make about
the use of tree based classifiers or
regressors so the first thing is I
glossed over a little bit the problem of
handling discrete discrete value
attributes I said you could choose red
or not red but then if you think about
discrete valued attribute that has K
possible values you can think you can
see that there is a combinatorial leave
many ways of dividing these attributes
into two groups right so you need to
have a clever way of handling this and
the many of the decision tree packages
do
handle this in in a remaining --fill way
right the other thing which we have to
be very aware of when you are dealing
with trees is that trees are notoriously
unstable so what do I mean by unstable
is that if there is a very small change
in the training data that you give to
the trees the tree that you build out of
the data could be very different so you
could delete a few data points and you
might end up having a tree that looks
very different though this is in
contrast to some of the earlier things
that we have looked at like logistic
regression or support vector machines
where these things are stable to
deletion of one or two data points but
addition trees can be notoriously
unstable so one way that people get
around this problem of instability in
addition trees is to make sure that you
build many many different decision trees
right with slightly different views of
the data and then combine the
predictions made by all the decision
trees into a single tree so that way we
can actually and make sure that the
classifier that you build the overall
classified that you build is reasonably
stable another point that we have to
look at suppose you are fitting dition
trees using regression so you can see
that for each region will be split with
each region will be outputting a
specific constant value at no point are
we worried about how will the value
change from r1 to r2 right so we are
only worried about what is happening in
r1 and we are fitting a value in r1 and
therefore there is no concern of
smoothness in our fix right and
therefore the the fit that's given by
addition tree can be pretty non smooth
all right so smoothness is a criterion
then we have to either add some more
regularizing factors in tradition trees
which makes it more complicated or we
have to look at other forms of
regressions so just keep in mind so
addition trees are very powerful
classifiers very powerful regressors
they are wonderful in terms of
interpretability but they also come with
their own caveat