Predicting with trees

Loading...

Из курса от партнера Johns Hopkins University

Practical Machine Learning

2128 оценки

Johns Hopkins University

Practical Machine Learning

2128 оценки

Курс 8 из 10 — Specialization Data Science

One of the most common tasks performed by data scientists and data analysts are prediction and machine learning. This course will cover the basic components of building and applying prediction functions with an emphasis on practical applications. The course will provide basic grounding in concepts such as training and tests sets, overfitting, and error rates. The course will also introduce a range of model based and algorithmic machine learning methods including regression, classification trees, Naive Bayes, and random forests. The course will cover the complete process of building prediction functions including data collection, feature creation, algorithms, and evaluation.

Из урока

Week 3: Predicting with trees, Random Forests, & Model Based Predictions

This week we introduce a number of machine learning algorithms you can use to complete your course project.

Predicting with trees12:51

Random Forests6:49

Model Based Prediction11:39

Познакомьтесь с преподавателями

Jeff Leek, PhD
Associate Professor, Biostatistics
Bloomberg School of Public Health
Roger D. Peng, PhD
Associate Professor, Biostatistics
Bloomberg School of Public Health
Brian Caffo, PhD
Professor, Biostatistics
Bloomberg School of Public Health

This lecture is about predicting with trees.

The basic idea is that if you have a

bunch of variables that you want to use to predict

an outcome, you can take each of those variables,

and use it to split the outcome into different groups.

And, so as you split the outcomes into different groups, then

you can evaluate the homogeneity of the outcome within each group.

And continue to split again if necessary, and

then, until you get outcomes that are separated

into groups that are homogeneous enough, or that

they are small enough that you need to stop.

The pros of this approach are that it's easy

to interpret right, and you tend to get better

performance in non-linear settings than you do with the

linear regression models we talked about in the previous lectures.

The cons are that without precluding or some

kind of cross-validation, this can lead to overfitting.

And they can be harder to estimate uncertainty than

it can be for the linear regression model setting.

In general the results may be variable depending on exact

values of the parameters, or the variables that you collected.

So here's an example of what a decision

tree looks like after it has already been built.

So this is a decision tree that appeared in the New York Times during the 2008

elections, when Bar, Barack Obama was running against

Hillary Clinton for the Democratic nomination for President.

And they were trying to decide what would be a prediction rule

for whether a county would vote for Obama or for Hillary Clinton.

And, so the way that happened was that they would, build a prediction model that

would ask questions of each of the different

variables that they had in their data set.

So the best split happened to be this variable.

So if the county was more than 20% African American, then

the county was much more likely to vote for, Barack Obama.

If it was less than 20% African American, then it

became more likely that the county would vote for Hilary Clinton.

Then within each of these two subgroups, they went and

looked for other variables that might split those subgroups out.

So, on this branch here, the next question was,

is the high school graduation rate greater than 78%?

If it wasn't, then the county was more likely to vote for Hillary

Clinton, and if it was, then it's more likely to vote for Barack Obama.

And the algorithm continues in that manner until you've split out

into smallest, the smallest subgroups that you are willing to consider.

And, so you see that within each of these

leaves of the tree, the predictions were quite homogeneous.

In other words.

Obama was 383 out of about 450 counties in this case.

And Hilary Clinton won 704 out of about 790 or 800 counties in this ca, case.

In other words, these questions split the

counties into groups that were homogenous within each

leaf their prediction was likely to come true

that, that candidate would win in the election.

So the basic algorithm behind building one of these trees

is, start with all the variables of one big group.

And then, you find the first variable that

best splits the outcomes into two different homogenous groups.

You then divided the data into two groups which we call leaves,

and on, and the split that you just performed is called a node.

Within each split, we then search through all the variables, again.

Including the variable we just split on.

And try to find within that group if there's another variable

or split that separates the outcome, into even more homogeneous groups.

You continue until the groups are too small, or they're sufficiently pure.

In other words, sufficiently homogeneous.

To, stop the algorithm.

So there are different measures of impurity.

And they're all based on basically this probability that you can estimate.

So, within a particular group.

So, in the le, m, m leaf then you have n total objects that you might consider,

and you can count the number of times that a particular class appears in that leaf.

So this is the number of times that class k appears in leaf m.

So that's this probability.

So it's p hat for the mth leaf and the kth class.

The misclassification error is 1 minus the probability that you're

equal to the most common class in that particular leaf.

So for example, if you're if it's a leaf where.

Almost all of the counties would vote for

Barack Obama, then 1 minus the misclassification error is

1 minus the er the misclassification error is 1

minus the probability that you'd vote for Barack Obama.

So zero means perfect purity.

In other words, there's no misclassification error and

all of the counties would go for Barack Obama.

0.5 means no purity because, it, it's not one,

because in any particular leaf if the, counties was overwhelming,

the counties where overwhelming likely to vote for Hilary Clinton

then you would get perfect purity in the other direction.

So it's actually when the leaf is perfectly balanced between the two

different outcomes, that's when you don't

have homogeneity within that particular leaf.

Similarly there's something called the Gini index which is

not to be confused with the Gini coefficient in economics,.

And it's basically 1 minus the sum of the squared

probabilities that you belong to any of the different classes.

So again zero means perfect purity.

In other words the class has one particular class has probability equal

to 1 and all the other classes have probability equal to 0.

0.5 means no purity.

In other words, all of the classes are perfectly balanced within each leaf.

Deviance and information gain is another measure that can be used, and so, it's

called deviance if you use log with base e here, and log base 2 is information gain.

And it's basically minus the sum of the probability.

Of being assigned to class k and leaf m times

the log base 2 or base e, of that same probability.

Value of zero means there is perfect purity within

the leaf, and value of one means there's no purity.

If you go to this link from Wikipedia, you'll have a lot more information about

how these measures of impurity are used to separate the, the values within each leaf.

So here's what they look like for a couple, for an s, for a specific example.

So suppose we had a variable that was trying to

split the dots into the blue and the red dots.

If the variable splitting in the following way were 15 of the dots were blue

in a particular leaf and only one was red, that would be a relatively pure situation.

And so, misclassification rate would be one out

of 16, so that's just this one dot here.

And so it's relatively low value the GinI coefficient would also

be low, because it's one minus 1 divided by 16 squared

plus 15 divided 16 squared which is a relatively small number

and then the information gained is similarly would be, in this case.

&Uh, smaller towards 0, because it's 1 over 16 times log base 2,

1 over 16 plus 15 divided by 16 times log base 2 15 over 16.

So that's the case where there is relatively pure outcome in the two groups.

We can also look at the case where it's not.

So suppose this variable split the outcomes into a leaf where half

of the values were blue, and half of the values were red.

So that wouldn't be a very good split, because it's basically a

coin flip whether you're from one class to the other in that leaf.

And so then this classification right here is .5, it's very large.

The Gini index is also maximized, it's .5,

and the information is also large, it's one.

So, this would be a split that wouldn't be made, because

it wouldn't separate the two groups very well on that particular leaf.

So I'm just going to show you an example with the iris data.

This is a very old data set, but it shows you the idea of how this works.

So, this, I'm loading the data with the command data iris.

And then I'm loading the ggplot2 library for making plots.

So the names of this data set are the

different variables that we're going to be using to predict with.

Here it's sepal length, Sepal.Width, Petal.Length and Petal.Width

and what we're trying to predict is the Species.

So there's 50 of these three different species

that we're trying to predict with those variables.

So again I always separate the data into the training and the test set, and in this

case I have 45 examples in my training set

that I can use to build a prediction model.

And the first thing that I do is, I'm

going to plot the petal width versus the sepal width.

So that's petal width on the x axis, the sepal width on the y axis, and then I'm

going to color it by the different species, and you

can see there are three very distinct clusters here.

So, it's a relatively easy classification problem.

It might be a little bit challenging for a linear model,

but not necessarily challenging for this

more advanced model with classification trace.

So you can fit the model using the train function in caret.

So again, I'm training the model.

The outcome is species.

I'm predicting with all the remaining variables, which is

why I have this tilde and then a dot.

And I'm telling it the method is rpart which is [UNKNOWN]

package for doing regression and classification trees, one of the packages.

And I'm telling you to use the training data.

If I look at the final model, it tells me what all the nodes are and how they're

split and in order to, and what the the

probability of being in each class is for each split.

So, here for example, there's a split that says petal.length is less

than 2.45, and if that happens then you in that case all of the

examples that have pedal length less than 2.45 belong to this bc setosa.

So, you can read those model splits to

tell you, what the classification tree is doing.

You can also make a plot of the classification tree.

And so if you just, plot the final model that's produce what

it will do is it will produce what's called a dandergram, like this.

And so it's a little hard to read, it's cut

off here, but you can see petal length less than 2.45.

Then you're assigned a setosa.

And so you can follow to the left what happens if the petal length is

less than 2.45, and to the right what

happens if petal length isn't less than 2.45.

And then follow the next split here at this node

down to the, see the total classification for any particular example.

A prettier version of that plot can be made with the rattle package.

So, you use the function fancyRpartPlot, and you pass

it the final model that was fit using caret.

And it makes again dentigram, but now it's a

little bit easier to see, so here we see.

That if the petal length is less than 2.5, we move over here to the

left, and if it's greater than 2.5 then we go over here to the right.

And then, within that split, so once you've already made that

decision about those samples, and if the petal length is less

that 4.8 you go down here to the left, and if

the petal length is greater you go over here to the right.

And so this makes it a little bit easier to see what's going on.

You can predict new values using the predict function,

just like you can with the other linear regression models.

Here the prediction is going to be a particular class label,

because the classification tree was built to predict a particular class.

And, so when I pass the new data, testing data, to the model.

It'll actually write out the different categories of species,

because it's actually predicting the class for each variable.

So notes and further resources, classification trees

are non-linear models, so they immediately use

interactions between variables, this is important to

keep in mind, because it's always a

model that's built on the relationship between

multiple variables and if you have a

large number of classes for a particular

variable for example that you're predicting with.

The models can over-fit a little bit.

The data transformations may be a little bit less important.

If you do any monotone transformation of

a continuous variable, in other words, any transformation

that doesn't change the order of the

values, but maybe makes them bigger or smaller.

Then you will get the same data

splits, with the classification or regression trees.

This can make the transformations a little bit less important.

They can also be used for regression problems.

So, I showed measures of misclassifcation impurity, you can also

use root mean squared error as a measure of impurity.

And do a similar classification tree building

procedure for building models for regression as well.

There are multiple tree building options in RR, both in

the caret package, using the party package, the rpart package.

Or you can even use this package tree

which doesn't appear in the caret package, but

I also has a lot of use, useful

functions that can be used when building these models.

For more information you can read in, in these two books,

where there's a lot of good information about classification and regression trees.

Or, in this book about, that's more

specifically targeted to this particular prediction algorithm.

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2018 Все права защищены.

Загрузить из App Store

Загрузить в Google Play