7.1 Decision Trees | Decision Tree Model -[Machine Learning | Andrew Ng]
 Welcome to the final week of this course on advanced learning algorithms. One of the learning algorithms that's very powerful, widely used in many applications, also used by many to win machine learning competitions is decision trees and tree ensembles. Despite all the successes of decision trees, they somehow haven't received that much attention in academia and so you may not hear about decision trees nearly that much, but it is a tool well worth having in your toolbox. So in this week, we'll learn about decision trees and you'll see how to get them to work for yourself. Let's dive in. To explain how decision trees work, I'm going to use as a running example this week a cat classification example. You're running a cat adoption center and given a few features, you want to train a classifier to quickly tell you if an animal is a cat or not. I have here 10 training examples and associated with each of these 10 examples, we're going to have features regarding the animal's ear shape, face shape, whether it has whiskers and then the ground truth label that you want to predict is this animal cat. So the first example has pointy ears, round face, whiskers are present and it is a cat. The second example has floppy ears, the face shape is not round, whiskers are present and yes that is a cat and so on for the rest of the examples. This data set has five cats and five dogs in it and the input features X are these three columns and the target output that you want to predict Y is this final column of is this a cat or not. In this example the features X take on categorical values. In other words the features take on just a few discrete values. Ear shapes are either pointy or floppy, the face shape is either round or not round and whiskers are either present or absent and this is a binary classification task because the labels are also one or zero. So now each of the features X1, X2 and X3 take on only two possible values. We'll talk about features that can take on more than two possible values as well as continuous value features later in this week. So what is a decision tree? Here's an example of a model that you might get after training a decision tree learning algorithm on the data set that you just saw. The model that is output by the learning algorithm looks like a tree and a picture like this is what computer scientists call a tree. If it looks nothing like the biological trees that you see out there to you it's okay, don't worry about it. We'll go through an example to make sure that this computer science definition of a tree makes sense to you as well. Maybe one of these ovals or rectangles is called a node in the tree. If you haven't seen computer scientists' definitions of trees before, it may seem non-intuitive that the roots of the tree is at the top and the leaves of the tree are down at the bottom. Maybe one way to think about this is this is more akin to an indoor hanging plant which is why the roots are up top and then the leaves tend to fall down to the bottom of the tree. The way this model works is if you have a new test example. She has a cat where the ear shape is pointy, face shape is round and whiskers are present. The way this model will look at this example and make a classification decision is we'll start with this example at this topmost node of the tree. This is called the root node of the tree and we will look at the feature written inside which is ear shape. Based on the value of the ear shape of this example, we'll either go left or go right. The value of the ear shape of this example is pointy and so we'll go down the left branch of the tree like so and end up at this oval node over here. We then look at the face shape of this example which turns out to be round and so we will follow this arrow down over here and the algorithm will make an inference that it thinks this is a cat. And so you get to this node and the algorithm will make a prediction that this is the cat. What I've shown on this slide is one specific decision tree model. To introduce a bit more terminology, this topmost node in the tree is called the root node and all of these nodes, that is all of these oval shapes but excluding the boxes at the bottom, all of these are called decision nodes. And the decision nodes because they look at a particular feature and then based on the value of the feature, causes you to decide whether to go left or right down the tree. Finally, these nodes at the bottom, these rectangular boxes are called leaf nodes and they make a prediction. We'll start at this node here at the top. In this slide I've shown just one example of a decision tree. Here are a few others. This is a different decision tree for trying to classify cat versus not cat. In this tree, to make a classification decision, you would again start at this topmost root node and depending on the ear shape of an example, you go either left or right. If the ear shape is pointy, then you look at the whiskers feature and depending on whether whiskers are present or absent, you go left or right again and classify cat versus not cat. And just for fun, here's a second example of a decision tree. Here's a third one and here's a fourth one. And among these different decision trees, some will do better and some will do worse on the training sets or on the cross validation and the test sets. So the job of the decision tree learning algorithm is out of all possible decision trees to try to pick one that hopefully does well on the training set and that also ideally generalizes well to new data such as to your cross validation and test sets as well. So seems like there are a lot of different decision trees one could build for a given application. How do you get an algorithm to learn a specific decision tree based on a training set? Let's take a look at that in the next video.
[{"start": 0.0, "end": 6.8, "text": " Welcome to the final week of this course on advanced learning algorithms."}, {"start": 6.8, "end": 11.64, "text": " One of the learning algorithms that's very powerful, widely used in many applications,"}, {"start": 11.64, "end": 18.52, "text": " also used by many to win machine learning competitions is decision trees and tree ensembles."}, {"start": 18.52, "end": 24.2, "text": " Despite all the successes of decision trees, they somehow haven't received that much attention"}, {"start": 24.2, "end": 28.76, "text": " in academia and so you may not hear about decision trees nearly that much, but it is"}, {"start": 28.76, "end": 31.720000000000002, "text": " a tool well worth having in your toolbox."}, {"start": 31.720000000000002, "end": 35.64, "text": " So in this week, we'll learn about decision trees and you'll see how to get them to work"}, {"start": 35.64, "end": 36.64, "text": " for yourself."}, {"start": 36.64, "end": 37.64, "text": " Let's dive in."}, {"start": 37.64, "end": 41.6, "text": " To explain how decision trees work, I'm going to use as a running example this week a cat"}, {"start": 41.6, "end": 43.96, "text": " classification example."}, {"start": 43.96, "end": 50.040000000000006, "text": " You're running a cat adoption center and given a few features, you want to train a classifier"}, {"start": 50.040000000000006, "end": 54.88, "text": " to quickly tell you if an animal is a cat or not."}, {"start": 54.88, "end": 62.56, "text": " I have here 10 training examples and associated with each of these 10 examples, we're going"}, {"start": 62.56, "end": 68.8, "text": " to have features regarding the animal's ear shape, face shape, whether it has whiskers"}, {"start": 68.8, "end": 73.46000000000001, "text": " and then the ground truth label that you want to predict is this animal cat."}, {"start": 73.46000000000001, "end": 79.78, "text": " So the first example has pointy ears, round face, whiskers are present and it is a cat."}, {"start": 79.78, "end": 85.36, "text": " The second example has floppy ears, the face shape is not round, whiskers are present and"}, {"start": 85.36, "end": 89.94, "text": " yes that is a cat and so on for the rest of the examples."}, {"start": 89.94, "end": 98.84, "text": " This data set has five cats and five dogs in it and the input features X are these three"}, {"start": 98.84, "end": 105.72, "text": " columns and the target output that you want to predict Y is this final column of is this"}, {"start": 105.72, "end": 107.6, "text": " a cat or not."}, {"start": 107.6, "end": 112.28, "text": " In this example the features X take on categorical values."}, {"start": 112.28, "end": 117.6, "text": " In other words the features take on just a few discrete values."}, {"start": 117.6, "end": 123.67999999999999, "text": " Ear shapes are either pointy or floppy, the face shape is either round or not round and"}, {"start": 123.67999999999999, "end": 130.6, "text": " whiskers are either present or absent and this is a binary classification task because"}, {"start": 130.6, "end": 134.2, "text": " the labels are also one or zero."}, {"start": 134.2, "end": 142.92, "text": " So now each of the features X1, X2 and X3 take on only two possible values."}, {"start": 142.92, "end": 148.76, "text": " We'll talk about features that can take on more than two possible values as well as continuous"}, {"start": 148.76, "end": 152.73999999999998, "text": " value features later in this week."}, {"start": 152.73999999999998, "end": 155.72, "text": " So what is a decision tree?"}, {"start": 155.72, "end": 161.92, "text": " Here's an example of a model that you might get after training a decision tree learning"}, {"start": 161.92, "end": 165.55999999999997, "text": " algorithm on the data set that you just saw."}, {"start": 165.55999999999997, "end": 171.67999999999998, "text": " The model that is output by the learning algorithm looks like a tree and a picture like this"}, {"start": 171.67999999999998, "end": 174.64, "text": " is what computer scientists call a tree."}, {"start": 174.64, "end": 180.23999999999998, "text": " If it looks nothing like the biological trees that you see out there to you it's okay, don't"}, {"start": 180.23999999999998, "end": 182.2, "text": " worry about it."}, {"start": 182.2, "end": 186.14, "text": " We'll go through an example to make sure that this computer science definition of a tree"}, {"start": 186.14, "end": 188.5, "text": " makes sense to you as well."}, {"start": 188.5, "end": 195.64, "text": " Maybe one of these ovals or rectangles is called a node in the tree."}, {"start": 195.64, "end": 202.96, "text": " If you haven't seen computer scientists' definitions of trees before, it may seem non-intuitive"}, {"start": 202.96, "end": 209.68, "text": " that the roots of the tree is at the top and the leaves of the tree are down at the bottom."}, {"start": 209.68, "end": 215.4, "text": " Maybe one way to think about this is this is more akin to an indoor hanging plant which"}, {"start": 215.4, "end": 222.16, "text": " is why the roots are up top and then the leaves tend to fall down to the bottom of the tree."}, {"start": 222.16, "end": 227.0, "text": " The way this model works is if you have a new test example."}, {"start": 227.0, "end": 231.76, "text": " She has a cat where the ear shape is pointy, face shape is round and whiskers are present."}, {"start": 231.76, "end": 238.68, "text": " The way this model will look at this example and make a classification decision is we'll"}, {"start": 238.68, "end": 244.28, "text": " start with this example at this topmost node of the tree."}, {"start": 244.28, "end": 252.36, "text": " This is called the root node of the tree and we will look at the feature written inside"}, {"start": 252.36, "end": 253.36, "text": " which is ear shape."}, {"start": 253.36, "end": 261.24, "text": " Based on the value of the ear shape of this example, we'll either go left or go right."}, {"start": 261.24, "end": 269.42, "text": " The value of the ear shape of this example is pointy and so we'll go down the left branch"}, {"start": 269.42, "end": 275.92, "text": " of the tree like so and end up at this oval node over here."}, {"start": 275.92, "end": 281.48, "text": " We then look at the face shape of this example which turns out to be round and so we will"}, {"start": 281.48, "end": 289.56, "text": " follow this arrow down over here and the algorithm will make an inference that it thinks this"}, {"start": 289.56, "end": 291.36, "text": " is a cat."}, {"start": 291.36, "end": 296.6, "text": " And so you get to this node and the algorithm will make a prediction that this is the cat."}, {"start": 296.6, "end": 302.36, "text": " What I've shown on this slide is one specific decision tree model."}, {"start": 302.36, "end": 310.6, "text": " To introduce a bit more terminology, this topmost node in the tree is called the root"}, {"start": 310.6, "end": 317.26000000000005, "text": " node and all of these nodes, that is all of these oval shapes but excluding the boxes"}, {"start": 317.26000000000005, "end": 322.36, "text": " at the bottom, all of these are called decision nodes."}, {"start": 322.36, "end": 326.84000000000003, "text": " And the decision nodes because they look at a particular feature and then based on the"}, {"start": 326.84000000000003, "end": 333.12, "text": " value of the feature, causes you to decide whether to go left or right down the tree."}, {"start": 333.12, "end": 340.96000000000004, "text": " Finally, these nodes at the bottom, these rectangular boxes are called leaf nodes and"}, {"start": 340.96000000000004, "end": 343.40000000000003, "text": " they make a prediction."}, {"start": 343.40000000000003, "end": 346.08000000000004, "text": " We'll start at this node here at the top."}, {"start": 346.08000000000004, "end": 350.64, "text": " In this slide I've shown just one example of a decision tree."}, {"start": 350.64, "end": 352.24, "text": " Here are a few others."}, {"start": 352.24, "end": 358.26, "text": " This is a different decision tree for trying to classify cat versus not cat."}, {"start": 358.26, "end": 363.48, "text": " In this tree, to make a classification decision, you would again start at this topmost root"}, {"start": 363.48, "end": 369.48, "text": " node and depending on the ear shape of an example, you go either left or right."}, {"start": 369.48, "end": 373.02, "text": " If the ear shape is pointy, then you look at the whiskers feature and depending on whether"}, {"start": 373.02, "end": 378.24, "text": " whiskers are present or absent, you go left or right again and classify cat versus not"}, {"start": 378.24, "end": 379.76, "text": " cat."}, {"start": 379.76, "end": 382.88, "text": " And just for fun, here's a second example of a decision tree."}, {"start": 382.88, "end": 386.92, "text": " Here's a third one and here's a fourth one."}, {"start": 386.92, "end": 391.24, "text": " And among these different decision trees, some will do better and some will do worse"}, {"start": 391.24, "end": 395.5, "text": " on the training sets or on the cross validation and the test sets."}, {"start": 395.5, "end": 400.62, "text": " So the job of the decision tree learning algorithm is out of all possible decision trees to try"}, {"start": 400.62, "end": 407.52, "text": " to pick one that hopefully does well on the training set and that also ideally generalizes"}, {"start": 407.52, "end": 412.56, "text": " well to new data such as to your cross validation and test sets as well."}, {"start": 412.56, "end": 416.79999999999995, "text": " So seems like there are a lot of different decision trees one could build for a given"}, {"start": 416.79999999999995, "end": 418.15999999999997, "text": " application."}, {"start": 418.15999999999997, "end": 423.2, "text": " How do you get an algorithm to learn a specific decision tree based on a training set?"}, {"start": 423.2, "end": 438.64, "text": " Let's take a look at that in the next video."}]