So, given that so far we looked at how to build a decision tree kind of in theory.
And we, we ignored the data size.
Let's now talk about the algorithm that
does the decision tree building using MapReduce.
So the problem we are looking is how do I build a tree using a giant,
giant dataset that, that lives on top of MapReduce.
So the idea is given a large dataset, I want to build a decision tree.
What are some general considerations that I want to take, un, in to account.
So the first one is if the, the, the, the whole tree will be relatively small.
What I mean by this the data is big, but the tree itself is relatively small.
So imagine it's like ten levels deep.
If it's a binary tree this means it will have 2,000 nodes or something.
So it's a small thing.
So tree itself fits into memory, but the data is very big.
So, the data set is too large for keeping memory and
the data set is too big to scan to scan over it on a single machine.
So really we want to have these data set be distributed across a large
number of machines.
And the idea is that because the data set needs to be distributed,
we'll be using the MapReduce framework.
Just to remind you how MapReduce works, the i,
the idea is that we have our input file split into the chunks.
Then we have a input, the chunks of the input file through a set of mappers,
mappers extract, extract key value pairs.
Right, we have our set of keys and we have a corresponding set of values.
Then this data gets sorted.
And it gets passed towards the reducers where all the key
value pairs that belong to the same key.
For example here,
everything that has the key B, goes to the, goes to the first reducer.
And everything that has a key value A goes to the second reducer.
And for example, also all the Cs go to the first reducer.
Right. So the idea is
that there is a shuffling step and
then the reducers collect the values and each reducer produces its own output.
So the question is, how can we use this kind of MapReduce computational
infrastructure to learn how to build trees?
So the particular approach we will be looking at is called PLANET.
And this was, a pap,
a research paper published, by Google, a few years ago, so three, four years ago.
And what PLANET is, it's simply a sequence of MapReduce jobs.
That builds a decision tree.
Our setting in this case is the following, we will kind of focus on,
on a subset of all possible, you know, categorical attributes and so on.
We will only consider, numerical attributes.
We can think of them as discreet, meaning integers, or
continuous like real values, but we have no categorical attributes.
We will we will think of predicting the target variable y to be,
to be a continuous value or a numerical value.
So we will think about regression and we will limit ourselves some binary splits.
All right, so our decisions will be of the forum is x less than value v and
then if yes go to the left, if no go to the right.
As I mentioned, our decisions tree is small enough so
mapper can keep it in memory, but the data is too large to be kept in memory.
So our overall system architecture will be something like this, right?
We will want to have a sequence of MapReduce jobs that create the input data
and process it.
We will also have the master node that keeps track, of everything.
And, we will also keep separately in the memory,
the model that we have so far, we will keep some attribute metadata information.
And the master is also responsible for saving intermediate results.
What the MapReduce will do is it will do in particular two things.
It will try to help us find the, the best attribute and the best value to split on.
So, we will call this Find Best Split and
it will also kind of keep building the thing.
So, the expansive part here, or the part that is
computationally very expansive is finding what is the best split.
And we want to utilize MapReduce to help us find the best split.
The way we will build the tree is we will build it in levels.
So we'll first build the first level and
then we'll build the second level and so on.
And at every level for all, for
all the nodes we'll want to decide what is the best attribute to split upon.
So lets think about building the tree.
Right, as I said we are building the tree level by level,
where we will have one MapReduce steps to build one level of the tree.
So if you want to build tree that is ten levels deep,
we need ten MapReduce, jobs, or steps or iterations of it.
And in particular, kind of at high level,
the mapper, what it will do it will consider a number of possible splits.
And on, on a given subset of data and for each split it kind of stores
the partial statistics, so that then the partial statistic is sent to the reducer.
The reducer collects the partial statistics and determines the best split.
So basically, the idea is that,
given the particular feature in a particular split value.
If I have our big input file that is split into chunks,
each chunk is sent to the, to the, to a separate mapper.
This mapper will compute some statistics of how this given attribute and
this given value, how, what is the quality of the split?
All, all these partial statistics will be sent to the reducer, who will then output
the final score or the final quality of the, of the given split.
And then master then decides which split to take and
grows the tree by additional level.
So this is generally the idea.
The mapper will allow us to take this big data file,
split into chunks, compute subsets.
Statistics of hidden subsets of the data.
Reducer collects the thing, and lets the Master know to makes the final decision.
So the, in terms of the overall infrastructure,
the mapper loads the modeling into the modeling been so far into the memory.
And then, also information on which attribute splits to consider.
And then, a given mapper only sees a subset of data.
The mapper drops each, data point to the appropriate leaf node L.
And for each leaf node L, it keeps statistics about what is the data that
reached L, and what is the data that is in the left and right sub tree.
Under, under the given split, right?
So, the mapper sees a set of splits S sees a subset of the, of our dataset.
And then for each leaf node it keeps track of which data goes to the left,
kind of left of the leaf node.
And what data goes to the right of the given leaf node.
And then as I mentioned,
the reducer will take all this partial information combine it.
And determine the best split for
each node in the tree at the given level that we are currently building right?
So the idea is that we are currently looking let's say under third level or
fourth level of the tree.
So the way now that I told you about what the mapper is doing and
what the reducer is doing at one level of the tree.
Now, how are we kind of building the whole tree?
The whole procedure breaks down into three types of MapReduce jobs.
First is the mapr, MapReduce job that we call initialization.
We call this once at the beginning of the building procedure.
And basically, the idea here is, for
each attribute to identify values to be considered for splits.
Then we will have a sequence of MapReduce jobs that
are basically finding the best splits.
So we have one MapReduce job for every level of the tree.
Here, the idea is that we want to find the best split when there is too
much data to fit in memory.
And then you, also, have this last part review called InMemoryBuild.
This is a thing you want to run at least once, where basically it's
similar thing to BuildSubTree function I already showed you.
And this idea, the idea here is as long as the data is small enough,
you just want to go and build in the whole subtree at once