7.2 Decision Trees | Learning Process --[Machine Learning | Andrew Ng]
 The process of building a decision tree, given a training set, has a few steps. In this video, let's take a look at the overall process of what you need to do to build a decision tree. Given a training set of 10 examples of cats and dogs, like you saw in the last video, the first step of decision tree learning is we have to decide what feature to use at the root node that is the first node at the very top of the decision tree. Via an algorithm that we'll talk about in the next few videos, let's say that we decide to pick as the feature in the root node the ear shape feature. What that means is we will decide to look at all of our training examples, all 10 training examples shown here, and split them according to the value of the ear shape feature. In particular, let's pick out the five examples with pointy ears and move them over down to the left, and let's pick the five examples with floppy ears and move them down to the right. The second step is focusing just on the left part, or sometimes called the left branch of the decision tree, to decide what node to put over there. And in particular, what feature do we want to split on, or what feature do we want to use next. Via an algorithm that again we'll talk about later this week, let's say you decide to use the face shape feature there. What we'll do now is take these five examples and split these five examples into two subsets based on their value of the face shape. So we'll take the four examples, all of these five with a round face shape, and move them down to the left, and the one example with a not round face shape and move it down to the right. And finally we notice that these four examples are all cats, four of the four of them are cats, and so rather than splitting further, we create a leaf node that makes a prediction that things that get down to that node are cats. And over here we notice that none of the examples, zero of the one examples are cats, or alternatively 100% of the examples here are dogs. And so we can create a leaf node here that makes a prediction of not cat. Having done this on the left part, or the left branch of this decision tree, we now repeat a similar process on the right part, or the right branch of this decision tree, and focus attention on just these five examples, which contains one cat and four dogs. And we would have to pick some feature over here to use to split these five examples further. If we end up choosing the whiskers feature, we would then split these five examples based on whether whiskers are present or absent, like so. And you notice that one of the one examples on the left are cats, and zero of the four are cats. So each of these nodes is completely pure, meaning that it's all cats or all not cats, and there's no longer a mix of cats and dogs. And so we can create these leaf nodes, making a cat prediction on the left and a not cat prediction here on the right. So this is a process of building a decision tree. Through this process, there were a couple key decisions that we had to make at various steps during the algorithm. Let's talk through what those key decisions were, and we'll keep on flashing of the details of how to make these decisions in the next few videos. The first key decision was, how do you choose what feature to use to split on at each node? So at the root node, as well as on the left branch and the right branch of the decision tree, we had to decide if there were a few examples at that node, comprising a mix of cats and dogs, do you want to split on the ear shape feature or the face shape feature or the whiskers feature? We'll see in the next video that decision trees will choose what feature to split on in order to try to maximize purity. And by purity, I mean, you want to get to what subsets which are as close as possible to all cats or all dogs. For example, if we had a feature that said, does this animal have cat DNA? We don't actually have this feature, but if we did, we could have split on this feature at the root node, which would have resulted in five out of five cats in the left branch and zero out of five cats in the right branch. And both these left and right subsets of the data are completely pure, meaning that there's only one class, either cats only or not cats only in both of these left and right sub branches, which is why the cat DNA feature, if we had this feature, would have been a great feature to use. But with the features that we actually have, we had to decide whether to split on ear shape, which results in four out of five examples on the left being cats and one of the five examples on the right being cats or face shape, which resulted in four out of seven on the left and one of the three on the right or whiskers, which resulted in three out of four examples being cats on the left and two of the six being not cats on the right. And so the decision tree learning algorithm has to choose between ear shape, face shape and whiskers, which of these features results in the greatest purity of the labels on the left and right sub branches, because it is if you can get to a highly pure subset of examples, then you can either predict cat or predict not cat and get it mostly right. So the next video on entropy will talk about how to estimate impurity and how to minimize impurity. So the first decision we have to make when learning a decision tree is how to choose which feature to split on in each node. The second key decision you need to make when building a decision tree is to decide when do you stop splitting. The criteria that we use just now was until a node is either 100% all cats or 100% all dogs or not cats, because at that point it seems natural to build a leaf node that just makes a classification prediction. Alternatively, you might also decide to stop splitting when splitting a node further will result in the tree exceeding a maximum depth, where the maximum depth that you allow the tree to grow to is a parameter that you could decide. In a decision tree, the depth of a node is defined as the number of hops that it takes to get from the root node, that is the node at the very top to that particular node. So the root node takes zero hops to get to itself and is at depth zero. The nodes below it are at depth one and the nodes below it would be at depth two. And so if you had decided that the maximum depth of the decision tree is say two, then you would decide not to split any nodes below this level so that the tree never gets to depth three. And one reason you might want to limit the depth of the decision tree is to make sure first the tree doesn't get too big and unwieldy. And second, by keeping the tree small, it makes it less prone to overfitting. Another criteria you might use to decide to stop splitting might be if the improvements in the purity score, which you see in a later video, are below a certain threshold. So if splitting a node results in minimum improvements to purity, or you see later it actually decreases in impurity, but if the gains are too small, then you might not bother. Again, both to keep the tree smaller and to reduce the risk of overfitting. And finally, if the number of examples at a node is below a certain threshold, then you might also decide to stop splitting. So for example, if at the root node we had split on the face shape feature, then the right branch would have had just three training examples with one cat and two dogs. And rather than splitting this into even smaller subsets, if you decided not to split further sets of examples with just three or fewer examples, then you would just create a decision node. And because there are mainly dogs, two out of three are dogs here, this would be a node that makes a prediction of not cat. And again, one reason you might decide this is not worth splitting on is to keep the tree smaller and to avoid overfitting. When I look at decision tree learning algorithms myself, sometimes I feel like, boy, there are a lot of different pieces, a lot of different things going on in this algorithm. Part of the reason it might feel like that is in the evolution of decision trees, there was one researcher that proposed a basic version of decision trees, and then a different researcher said, oh, we can modify this thing this way, such as here's a new criteria for splitting. Then a different researcher comes up with a different thing, like, oh, maybe we should stop splitting when it reaches a certain maximum depth. And over the years, different researchers came up with different refinements to the algorithm. As a result of that, it does work really well. But when you look at all the details of how to implement a decision tree, it feels like a lot of different pieces, such as why there's so many different ways to decide when to stop splitting. So if it feels like a somewhat complicated, messy algorithm to you, it does to me too. But these different pieces, they do fit together into a very effective learning algorithm. And what you learn in this course is the key, most important idea is how to make it work well. And then at the end of this week, I'll also share with you some guidance, some suggestions for how to use open source packages so that you don't have to have too complicated a procedure for making all these decisions, like how do I decide to stop splitting, so that you really get these algorithms to work well for yourself. But I want to reassure you that if this algorithm seems complicated and messy, it frankly does to me too, but it does work well. Now the next key decision that I want to dive more deeply into is how do you decide how to split at a node. So in the next video, let's take a look at this definition of entropy, which would be a way for us to measure purity or more precisely impurity in a node. Let's go on to the next video.
[{"start": 0.0, "end": 6.96, "text": " The process of building a decision tree, given a training set, has a few steps."}, {"start": 6.96, "end": 11.48, "text": " In this video, let's take a look at the overall process of what you need to do to build a"}, {"start": 11.48, "end": 13.36, "text": " decision tree."}, {"start": 13.36, "end": 19.88, "text": " Given a training set of 10 examples of cats and dogs, like you saw in the last video,"}, {"start": 19.88, "end": 27.92, "text": " the first step of decision tree learning is we have to decide what feature to use at the"}, {"start": 27.92, "end": 33.04, "text": " root node that is the first node at the very top of the decision tree."}, {"start": 33.04, "end": 37.72, "text": " Via an algorithm that we'll talk about in the next few videos, let's say that we decide"}, {"start": 37.72, "end": 43.120000000000005, "text": " to pick as the feature in the root node the ear shape feature."}, {"start": 43.120000000000005, "end": 48.56, "text": " What that means is we will decide to look at all of our training examples, all 10 training"}, {"start": 48.56, "end": 54.96, "text": " examples shown here, and split them according to the value of the ear shape feature."}, {"start": 54.96, "end": 62.6, "text": " In particular, let's pick out the five examples with pointy ears and move them over down to"}, {"start": 62.6, "end": 68.56, "text": " the left, and let's pick the five examples with floppy ears and move them down to the"}, {"start": 68.56, "end": 69.64, "text": " right."}, {"start": 69.64, "end": 74.88, "text": " The second step is focusing just on the left part, or sometimes called the left branch"}, {"start": 74.88, "end": 81.32, "text": " of the decision tree, to decide what node to put over there."}, {"start": 81.32, "end": 87.32, "text": " And in particular, what feature do we want to split on, or what feature do we want to"}, {"start": 87.32, "end": 88.63999999999999, "text": " use next."}, {"start": 88.63999999999999, "end": 94.16, "text": " Via an algorithm that again we'll talk about later this week, let's say you decide to use"}, {"start": 94.16, "end": 96.78, "text": " the face shape feature there."}, {"start": 96.78, "end": 102.96, "text": " What we'll do now is take these five examples and split these five examples into two subsets"}, {"start": 102.96, "end": 106.08, "text": " based on their value of the face shape."}, {"start": 106.08, "end": 112.8, "text": " So we'll take the four examples, all of these five with a round face shape, and move them"}, {"start": 112.8, "end": 118.03999999999999, "text": " down to the left, and the one example with a not round face shape and move it down to"}, {"start": 118.03999999999999, "end": 120.08, "text": " the right."}, {"start": 120.08, "end": 126.08, "text": " And finally we notice that these four examples are all cats, four of the four of them are"}, {"start": 126.08, "end": 132.24, "text": " cats, and so rather than splitting further, we create a leaf node that makes a prediction"}, {"start": 132.24, "end": 135.56, "text": " that things that get down to that node are cats."}, {"start": 135.56, "end": 142.68, "text": " And over here we notice that none of the examples, zero of the one examples are cats, or alternatively"}, {"start": 142.68, "end": 146.2, "text": " 100% of the examples here are dogs."}, {"start": 146.2, "end": 151.68, "text": " And so we can create a leaf node here that makes a prediction of not cat."}, {"start": 151.68, "end": 155.96, "text": " Having done this on the left part, or the left branch of this decision tree, we now"}, {"start": 155.96, "end": 160.84, "text": " repeat a similar process on the right part, or the right branch of this decision tree,"}, {"start": 160.84, "end": 167.16, "text": " and focus attention on just these five examples, which contains one cat and four dogs."}, {"start": 167.16, "end": 173.8, "text": " And we would have to pick some feature over here to use to split these five examples further."}, {"start": 173.8, "end": 180.72, "text": " If we end up choosing the whiskers feature, we would then split these five examples based"}, {"start": 180.72, "end": 187.0, "text": " on whether whiskers are present or absent, like so."}, {"start": 187.0, "end": 192.16, "text": " And you notice that one of the one examples on the left are cats, and zero of the four"}, {"start": 192.16, "end": 193.48, "text": " are cats."}, {"start": 193.48, "end": 201.12, "text": " So each of these nodes is completely pure, meaning that it's all cats or all not cats,"}, {"start": 201.12, "end": 203.72, "text": " and there's no longer a mix of cats and dogs."}, {"start": 203.72, "end": 209.4, "text": " And so we can create these leaf nodes, making a cat prediction on the left and a not cat"}, {"start": 209.4, "end": 211.7, "text": " prediction here on the right."}, {"start": 211.7, "end": 215.84, "text": " So this is a process of building a decision tree."}, {"start": 215.84, "end": 221.0, "text": " Through this process, there were a couple key decisions that we had to make at various"}, {"start": 221.0, "end": 223.96, "text": " steps during the algorithm."}, {"start": 223.96, "end": 227.98000000000002, "text": " Let's talk through what those key decisions were, and we'll keep on flashing of the details"}, {"start": 227.98000000000002, "end": 231.4, "text": " of how to make these decisions in the next few videos."}, {"start": 231.4, "end": 238.94, "text": " The first key decision was, how do you choose what feature to use to split on at each node?"}, {"start": 238.94, "end": 244.52, "text": " So at the root node, as well as on the left branch and the right branch of the decision"}, {"start": 244.52, "end": 251.16000000000003, "text": " tree, we had to decide if there were a few examples at that node, comprising a mix of"}, {"start": 251.16000000000003, "end": 255.92000000000002, "text": " cats and dogs, do you want to split on the ear shape feature or the face shape feature"}, {"start": 255.92000000000002, "end": 257.96000000000004, "text": " or the whiskers feature?"}, {"start": 257.96000000000004, "end": 262.88, "text": " We'll see in the next video that decision trees will choose what feature to split on"}, {"start": 262.88, "end": 266.12, "text": " in order to try to maximize purity."}, {"start": 266.12, "end": 271.2, "text": " And by purity, I mean, you want to get to what subsets which are as close as possible"}, {"start": 271.2, "end": 274.04, "text": " to all cats or all dogs."}, {"start": 274.04, "end": 279.64000000000004, "text": " For example, if we had a feature that said, does this animal have cat DNA?"}, {"start": 279.64000000000004, "end": 283.48, "text": " We don't actually have this feature, but if we did, we could have split on this feature"}, {"start": 283.48, "end": 289.32000000000005, "text": " at the root node, which would have resulted in five out of five cats in the left branch"}, {"start": 289.32000000000005, "end": 291.92, "text": " and zero out of five cats in the right branch."}, {"start": 291.92, "end": 297.36, "text": " And both these left and right subsets of the data are completely pure, meaning that there's"}, {"start": 297.36, "end": 305.6, "text": " only one class, either cats only or not cats only in both of these left and right sub branches,"}, {"start": 305.6, "end": 310.6, "text": " which is why the cat DNA feature, if we had this feature, would have been a great feature"}, {"start": 310.6, "end": 311.6, "text": " to use."}, {"start": 311.6, "end": 318.48, "text": " But with the features that we actually have, we had to decide whether to split on ear shape,"}, {"start": 318.48, "end": 323.7, "text": " which results in four out of five examples on the left being cats and one of the five"}, {"start": 323.7, "end": 329.88, "text": " examples on the right being cats or face shape, which resulted in four out of seven on the"}, {"start": 329.88, "end": 334.76, "text": " left and one of the three on the right or whiskers, which resulted in three out of four"}, {"start": 334.76, "end": 340.03999999999996, "text": " examples being cats on the left and two of the six being not cats on the right."}, {"start": 340.03999999999996, "end": 346.65999999999997, "text": " And so the decision tree learning algorithm has to choose between ear shape, face shape"}, {"start": 346.66, "end": 355.04, "text": " and whiskers, which of these features results in the greatest purity of the labels on the"}, {"start": 355.04, "end": 362.56, "text": " left and right sub branches, because it is if you can get to a highly pure subset of"}, {"start": 362.56, "end": 370.44000000000005, "text": " examples, then you can either predict cat or predict not cat and get it mostly right."}, {"start": 370.44, "end": 377.76, "text": " So the next video on entropy will talk about how to estimate impurity and how to minimize"}, {"start": 377.76, "end": 379.44, "text": " impurity."}, {"start": 379.44, "end": 384.44, "text": " So the first decision we have to make when learning a decision tree is how to choose"}, {"start": 384.44, "end": 388.2, "text": " which feature to split on in each node."}, {"start": 388.2, "end": 393.04, "text": " The second key decision you need to make when building a decision tree is to decide when"}, {"start": 393.04, "end": 395.84, "text": " do you stop splitting."}, {"start": 395.84, "end": 402.59999999999997, "text": " The criteria that we use just now was until a node is either 100% all cats or 100% all"}, {"start": 402.59999999999997, "end": 409.71999999999997, "text": " dogs or not cats, because at that point it seems natural to build a leaf node that just"}, {"start": 409.71999999999997, "end": 412.12, "text": " makes a classification prediction."}, {"start": 412.12, "end": 418.2, "text": " Alternatively, you might also decide to stop splitting when splitting a node further will"}, {"start": 418.2, "end": 423.76, "text": " result in the tree exceeding a maximum depth, where the maximum depth that you allow the"}, {"start": 423.76, "end": 427.8, "text": " tree to grow to is a parameter that you could decide."}, {"start": 427.8, "end": 435.15999999999997, "text": " In a decision tree, the depth of a node is defined as the number of hops that it takes"}, {"start": 435.15999999999997, "end": 440.64, "text": " to get from the root node, that is the node at the very top to that particular node."}, {"start": 440.64, "end": 446.03999999999996, "text": " So the root node takes zero hops to get to itself and is at depth zero."}, {"start": 446.03999999999996, "end": 453.24, "text": " The nodes below it are at depth one and the nodes below it would be at depth two."}, {"start": 453.24, "end": 459.56, "text": " And so if you had decided that the maximum depth of the decision tree is say two, then"}, {"start": 459.56, "end": 468.48, "text": " you would decide not to split any nodes below this level so that the tree never gets to"}, {"start": 468.48, "end": 471.48, "text": " depth three."}, {"start": 471.48, "end": 476.96000000000004, "text": " And one reason you might want to limit the depth of the decision tree is to make sure"}, {"start": 476.96000000000004, "end": 480.64, "text": " first the tree doesn't get too big and unwieldy."}, {"start": 480.64, "end": 486.52, "text": " And second, by keeping the tree small, it makes it less prone to overfitting."}, {"start": 486.52, "end": 491.03999999999996, "text": " Another criteria you might use to decide to stop splitting might be if the improvements"}, {"start": 491.03999999999996, "end": 496.36, "text": " in the purity score, which you see in a later video, are below a certain threshold."}, {"start": 496.36, "end": 502.76, "text": " So if splitting a node results in minimum improvements to purity, or you see later it"}, {"start": 502.76, "end": 510.2, "text": " actually decreases in impurity, but if the gains are too small, then you might not bother."}, {"start": 510.2, "end": 515.92, "text": " Again, both to keep the tree smaller and to reduce the risk of overfitting."}, {"start": 515.92, "end": 523.04, "text": " And finally, if the number of examples at a node is below a certain threshold, then"}, {"start": 523.04, "end": 525.8, "text": " you might also decide to stop splitting."}, {"start": 525.8, "end": 532.12, "text": " So for example, if at the root node we had split on the face shape feature, then the"}, {"start": 532.12, "end": 539.16, "text": " right branch would have had just three training examples with one cat and two dogs."}, {"start": 539.16, "end": 545.92, "text": " And rather than splitting this into even smaller subsets, if you decided not to split further"}, {"start": 545.92, "end": 551.36, "text": " sets of examples with just three or fewer examples, then you would just create a decision"}, {"start": 551.36, "end": 552.52, "text": " node."}, {"start": 552.52, "end": 558.4, "text": " And because there are mainly dogs, two out of three are dogs here, this would be a node"}, {"start": 558.4, "end": 561.52, "text": " that makes a prediction of not cat."}, {"start": 561.52, "end": 566.12, "text": " And again, one reason you might decide this is not worth splitting on is to keep the tree"}, {"start": 566.12, "end": 569.16, "text": " smaller and to avoid overfitting."}, {"start": 569.16, "end": 573.08, "text": " When I look at decision tree learning algorithms myself, sometimes I feel like, boy, there"}, {"start": 573.08, "end": 578.04, "text": " are a lot of different pieces, a lot of different things going on in this algorithm."}, {"start": 578.04, "end": 583.36, "text": " Part of the reason it might feel like that is in the evolution of decision trees, there"}, {"start": 583.36, "end": 588.5600000000001, "text": " was one researcher that proposed a basic version of decision trees, and then a different researcher"}, {"start": 588.5600000000001, "end": 594.16, "text": " said, oh, we can modify this thing this way, such as here's a new criteria for splitting."}, {"start": 594.16, "end": 597.28, "text": " Then a different researcher comes up with a different thing, like, oh, maybe we should"}, {"start": 597.28, "end": 600.3199999999999, "text": " stop splitting when it reaches a certain maximum depth."}, {"start": 600.3199999999999, "end": 603.92, "text": " And over the years, different researchers came up with different refinements to the"}, {"start": 603.92, "end": 605.4, "text": " algorithm."}, {"start": 605.4, "end": 608.24, "text": " As a result of that, it does work really well."}, {"start": 608.24, "end": 611.8399999999999, "text": " But when you look at all the details of how to implement a decision tree, it feels like"}, {"start": 611.8399999999999, "end": 617.12, "text": " a lot of different pieces, such as why there's so many different ways to decide when to stop"}, {"start": 617.12, "end": 618.1999999999999, "text": " splitting."}, {"start": 618.1999999999999, "end": 624.06, "text": " So if it feels like a somewhat complicated, messy algorithm to you, it does to me too."}, {"start": 624.06, "end": 629.0, "text": " But these different pieces, they do fit together into a very effective learning algorithm."}, {"start": 629.0, "end": 634.0799999999999, "text": " And what you learn in this course is the key, most important idea is how to make it work"}, {"start": 634.0799999999999, "end": 635.28, "text": " well."}, {"start": 635.28, "end": 639.68, "text": " And then at the end of this week, I'll also share with you some guidance, some suggestions"}, {"start": 639.68, "end": 645.88, "text": " for how to use open source packages so that you don't have to have too complicated a procedure"}, {"start": 645.88, "end": 650.0, "text": " for making all these decisions, like how do I decide to stop splitting, so that you really"}, {"start": 650.0, "end": 652.92, "text": " get these algorithms to work well for yourself."}, {"start": 652.92, "end": 657.24, "text": " But I want to reassure you that if this algorithm seems complicated and messy, it frankly does"}, {"start": 657.24, "end": 660.8399999999999, "text": " to me too, but it does work well."}, {"start": 660.8399999999999, "end": 667.02, "text": " Now the next key decision that I want to dive more deeply into is how do you decide how"}, {"start": 667.02, "end": 668.5999999999999, "text": " to split at a node."}, {"start": 668.5999999999999, "end": 673.0799999999999, "text": " So in the next video, let's take a look at this definition of entropy, which would be"}, {"start": 673.0799999999999, "end": 678.48, "text": " a way for us to measure purity or more precisely impurity in a node."}, {"start": 678.48, "end": 684.32, "text": " Let's go on to the next video."}]