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

hi and welcome to this module on
classification and regression trees so
today we look at a very simple but
powerful idea for building both
classifiers and regression the basic
idea is that we are going to partition
the input space
we are going to partition the input
space into rectangles
so let us imagine that you have a
two-dimensional imagine that you have a
two-dimensional input space right X 1
next to right so you are going to try
and partition this into rectangles
by drawing axis parallel lines so why
why are we drawing axis parallel lines
here because these lines can be with
specified very easily by just comparing
against one of those dimensions of the
input data right so for example to draw
this line all I need to specify is the
intercept at the X 2 axis so likewise to
draw this line I need to specify the
intercept at the X 1 axis right so one
way of thinking about these kinds of
partitioning of the input space by using
axis parallel lines is to think of
making a series of decisions as to which
side of a specific line is your data
point line right so you can think of
this as following right we will call
this say t1
this point is t2
this point st3
this is t4 these are the intercepts
along the respective X 1 and X 2 axis
right then one way of representing this
is to think of this as a series of tests
or decisions that you are making so I
can start off by asking the question is
X 1 less than or equal to t1 so that is
essentially saying here is a line that
represents x1 equal to t1 that is your
data point light to the left of the line
or to the right of the line right so if
it lies to the left of the line so this
will be NS right then I asked the second
question that is essentially is a x2
lesser than or equal to t2 right so x2
equal to t2 is this line right and I am
asking the question if the data point is
above this line or if the data point is
below this line right so if it is below
the line right so then I get a yes for
this question as one and I will denote
this by r1 so this region is r1 so since
this represents both x1 being less than
T 1 and x2 being less than T 2 it is
essentially bounded in this region so
likewise if X if the point is actually
greater than t2 right so in this case
this will evaluate to no and say I get
our region call r2
so what would this region be if you can
think about it this is essentially the
region where x1 is greater than t1 right
but x1 is lesser than t3
right so I'm going to call this region R
3 so here it is X 1 is greater than t1
but lesser than t3 so that would be R 3
and if X 1 is greater than T 3 so in
this case I am again splitting it into
two regions
so essentially so I am testing on X 2
and T 4
you
so what is it that you notice about this
tree that we have drawn here so at every
point I am asking you a binary question
right is this yes or no right so
essentially it is a binary tree at every
point you divide into two branches right
and once I have divided into one of
these branches once I go down one of
these paths right I am from here on I am
only concerned about data points that
has satisfied the first question that I
asked so from this point on in the tree
right I am only worried about data
points that are to the left side of the
line here at this point in the tree I am
worried about data points that are to
the right of the line here so this is a
couple of distinguishing features of the
decision tree that I am making binary
decisions right and I am also looking at
some kind of a divide and conquer
approach right great so now what we have
done is that we have a representation
that allows us to split the input space
into different regions right so
depending upon the kind of problem that
we are solving whether it is a
classification problem or whether it is
a regression problem so we would like to
fit a single value to each of these
regions right so if it is a regression
problem
so the question problem will be
outputting a single value for the entire
region so if your data point falls in r1
regardless of where in r1 it is falling
it so the data point could fall here it
could fall here it could fall here it
could fall here regardless of where in
r1 the data point Lancer I am going to
predict the same output so it will be
the same same real-valued output for
each region right so in the case of
classification what do you expect it to
be right it will be the same right class
label for a region right so regardless
of where in r1 the data point falls I
will always output the same class label
for the classification problem right so
now so we have two questions that we
have to answer in the case of decision
trees so the first one is how do we form
the region's the second question is
having formed the region's how do I
decide what is the output that I am
going to produce for that region so we
will look at each of these problems in
turn but the first thing which I wanted
to mention before I go on to look at how
we solve them is that decision trees are
fantastic because they are the most
interpretable of all of the classifiers
that we are going to look at even more
so than linear regression at at some
point right because if you think of the
way we constructed the decision tree it
seems like a very natural way to map it
to how humans think about making
decisions right so that that way the
interpretability so the interpretability
of decision trees or very high and in
fact that makes it one of the
classifiers or regressors of choice and
in a wide variety of problems and the
second advantage of decision trees is
that they can work well with mixed-mode
data so here the example I gave you
assume that X 1 and X 2 are actual
numbers and it could pick arbitrary
comparison points X 1 X 2 need not be
numbers they could be a categorical
variable like color right or it could be
age but represented as an old and middle
age it need not necessarily be a number
on which you have to run these kinds of
tests I could compare whether the color
is red or not red or I could look at
whether the person is young or
middle-aged right versus the person is
old so I could have any kind of binary
tests among categorical attributes and
then I can still construct the decision
tree so the first advantage is one of
interpretability the second one
the ease with which you can hand mixed
more data so now let us step at and let
us look at regression trees specifically
so what what we know about regression so
regression the goal of regression is
essentially to minimize some squared
error right so the one of the goals of
regression is to minimize some squared
error we'll stick with that of course
you can build regressors for whatever
objective that you want to optimize so I
want to fit a function f such that I
minimize this sum squared error right
let's suppose that I have a tree that
has split my input space into M regions
which I will denote by R 1 to R M right
so I have M regions in the input space
and then for each of these regions so I
am going to be outputting a specific
value which I will denote by cm right so
cm is the value that I will output for
any data point that lies in region RM
right and I here is an indicator
function that denotes whether the data
point lies in region RM or not so
essentially what this summation tells us
is that with the data point input data
point X that is come to us is going to
lie in one of these regions one to M
right one to capital M so I do not know
which region it is going to line but
this indicator function will tell me
which region it lies in so this
summation will event will be nonzero for
only one term essentially the region in
which the data point lies in and
therefore the output will be the the C
value corresponding to the region in
which the data point lies in suppose the
X lies in r2 then the output will be c2
suppose I am given this tree already
ok this region split has been decided
for me right then we know what is the
best value that we have to output for cm
right so what would be the best value we
had output for cm
essentially I go through my training
data right I pick out all those X's
which lie in the Emeth region and pick
out all the XS that lie in the MF region
look at the corresponding Y's and take
the average of those and that will be
the value that I output if the data
point lies in the region RM right so why
is this a reasonable choice well so one
way to think about it is when I am
trying to minimize the error in a
specific region right when I am trying
to minimize the error in a specific
region that I say are for right I do not
have to worry about any of the training
points that lie outside of r4 because
the value I have to predict for them is
completely independent of right all
these other data points right so I only
have to worry about the data points that
live within our for when I am trying to
make a fit for the value that I'm going
output in r4 right and among all the
data points that lie in r4 right the
best prediction that I can make is
obviously the average in terms of
minimizing the sum squared error so if I
have a different criterion let's say I
want to minimize the median I mean I
want to minimize absolute deviation then
I probably have to predict the median
and not the average right so this part
is fine so we know we have solved one of
the two problems so what are the two
problems one is given the region split
what is the output that I have to
predict for each region right so that we
know how to do that at least in the case
of regression now comes the harder
question how are you going to find the
regions right
right how are you going to find the best
arms in fact finding the best arm right
then finding that the best region split
is actually a combinatorial problem and
it is actually infeasible and it's it's
it's going to take a very very long time
to find the the exactly the right set of
regions so quite often what people do is
they are off the they're out a greedy
approach to finding these regions so
what is the greedy approach to right so
you basically start off by considering
basically start off by considering a
split variable so what is the split
variable so in the case of the example 3
here so the split variable at this level
is x1 all right and the split variable
at here is x2 the split variable here
was again x1
so essentially you consider some split
variable right and then try to find try
to find the best split point right so
what is the split point again so in the
tree that we saw earlier so in the first
level the split point was t1 ok so
likewise so at each level we have to
find out what is the appropriate split
pointers so this just take us a simple
example here so I am going to define
go and defend two sub regions r1 and r2
so r1 is that part of the space where
the variable X the jet coordinate of the
variable X is lesser than or equal to
some chosen value s right
likewise r2 is that sub region where the
jth coordinate of the variable X is
greater than some chosen value s so now
what we are really trying to do is
trying to find J and s such that we can
solve for the best possible split just
to give you an intuition here right so
in this case if you think of the
original data right so I have chosen a
split point which is which is t1 right
so the yes in my choice is t1 right and
this part is wherever X was less than x1
was less than t1 and this part of the
space was wherever x1 was greater than
t1 so in our new terminology this will
correspond to right and this will
correspond to
so the one here is because we are
looking at x1 right and the t1 because
that is the split point that we are
considering so now we have to find J and
yes both such that this expression is
minimized so what does this expression
so we know this so c1 is the prediction
I am going to make if the data point
lies in the sub region r1 right so why I
so these are all data points that lie in
the sub region r1 so either prediction I
will make for this c1 so this is
essentially the squared error for all
the data points that lie in r1 right and
this is likewise the squared error for
all the data points at line r2 so we
already saw that so the mini so you can
basically find the c1 that minimizes
this error
likewise find the c2 that minimizes that
error and now my problem is to find J
and s such that this entire expression
is minimized it sound a little daunting
in the beginning but if you think about
it
it is not that hard why because we are
operating with a finite training set
like the data that is given to us at the
beginning from which we are going to
build this tree is going to be finite
right so what does that tell us
for every XJ that I can choose as my
splitting variable there are only
finitely many points at which I have to
consider a split so that essentially
tells me for every J I choose ok there
are only finitely many yes that I have
to try why is that because there can
only be a finitely many different values
that the variable XJ can take in your
training data so essentially what we do
is that at every level in your decision
tree you basically look at this
expression for all possible split points
for every possible splitting variable
that you have in your data right and
then decide on which is the best
possible splitting point once the best J
and s is found so
what you do next you essentially go
ahead and split the data into two parts
right one corresponding to the our one
of the best JLS other corresponding to
our two of the best J and s and now you
repeat this process in both r1 and r2 so
now if you think about adding a problem
is become much simpler because the
ranges that you have to the number of
data points that you are looking at this
much lesser and so likewise you just
keep going until you come to a point
where you are happy to stop so this
essentially I will stop here as in this
module and the the next mod you will
look at till when do you grow the tree
and how are you going to handle
classification