7.3 Decision Tree Learning | Measuring purity --[Machine Learning | Andrew Ng]
 In this video, we'll look at a way of measuring the purity of a set of examples. If the examples are all cats or single class, then it's very pure. If it's all not cats, that's also very pure. But if it's somewhere in between, how do you quantify how pure is this set of examples? Let's take a look at the definition of entropy, which is a measure of the impurity of a set of data. Given a set of six examples like this, we have three cats and three dogs. Let's define P1 to be the fraction of examples that are cats. That is the fraction of examples with a label 1. That's what the subscript 1 indicates. And so P1 in this example is equal to 3 out of 6. We're going to measure the impurity of a set of examples using a function called the entropy, which looks like this. The entropy function is conventionally denoted as capital H of this number P1. And the function looks like this curve over here, where the horizontal axis is P1, the fraction of cats in the sample, and the vertical axis is the value of the entropy. So in this example, where P1 is 3 out of 6, or 0.5, the value of the entropy of P1 would be equal to 1. And you notice that this curve is highest when your set of examples is 50-50, so it's most impure as an impurity of 1, or really an entropy of 1, when your set of examples is 50-50. Whereas in contrast, if your set of examples was either all cats or all not cats, then the entropy is 0. Let's just go through a few more examples to gain further intuition about entropy and how it works. Here's a different set of examples with five cats and one dog. So P1, the fraction of positive examples, the fraction of examples labeled 1 is 5-6. And so P1 is about 0.83, and if you read off that value at about 0.83, we find that the entropy of P1 is about 0.65. And here I'm writing it only to two significant digits. And here I'm rounding it off to two decimal points. Here's one more example. This sample of six images has all cats. So P1 is 6 out of 6, because all six are cats. And the entropy of P1 is this point over here, which is 0. And so we see that as you go from 3-6 to 6 out of 6 cats, the impurity decreases from 1 to 0. Or in other words, the purity increases as you go from a 50-50 mix of cats and dogs to all cats. Let's look at a few more examples. Here's another sample with two cats and four dogs. So P1 here is 2-6, which is 1 third. And if you read off the entropy at 0.33, it turns out to be about 0.92. And this is actually quite impure. And in particular, this set is more impure than this set, because it's closer to a 50-50 mix, which is why the impurity here is 0.92 as opposed to 0.65. And finally, one last example. If we have a set of all six dogs, then P1 is equal to 0. And the entropy of P1 is just this number down here, which is equal to 0. So this is a zero impurity, or this would be a completely pure set of all not cats or all dogs. And don't worry, we'll show the equation for the entropy of P1 later in this video. Now let's look at the actual equation for the entropy function, h of P1. Recall that P1 is a fraction of examples that are equal to cats. So if you have a sample that is 2 third cats, then that sample must have 1 third not cats. So let me define P0 to be equal to the fraction of examples that are not cats to be just equal to 1 minus P1. The entropy function is then defined as negative P1 log P1. And by convention, when computing entropy, we take logs to base two, rather than to base E. And then minus P0 log base two of P0. Alternatively, this is also equal to negative P1 log P1 minus 1 minus P1 log 1 minus P1. And if you were to plot this function in a computer, you find that it will be exactly this function on the left. And we take log base two, just to make the peak of this curve equal to one. If you were to take log of base E, or the base of natural logarithms, then that just vertically scales this function. And it'll still work, but the numbers become a bit hard to interpret because the peak of the function is a nice round number like one anymore. One notes on computing this function. If P1 or P0 is equal to zero, then an expression like this will look like zero log of zero. And log of zero is technically undefined, it's actually negative infinity. But by convention, for the purposes of computing entropy, we'll take zero log zero to be equal to zero. And that will correctly compute the entropy as zero or it's one to be equal to zero. If you're thinking that this definition of entropy looks a little bit like the definition of the logistic loss that we learned about in the last course, there is actually a mathematical rationale for why these two formulas look so similar. But you don't have to worry about it, and we won't get into it in this class. But applying this formula for entropy should work just fine when you're building a decision entry. To summarize, the entropy function is a measure of the impurity of a set of data. It starts from zero, goes up to one, and then comes back down to zero as a function of the fraction of positive examples in your sample. There are other functions that look like this that go from zero up to one and then back down. For example, if you look in open source packages, you may also hear about something called the Gini criteria, which is another function that looks a lot like the entropy function, and that will work well as well for building decision trees. But for the sake of simplicity, in these videos, I'm going to focus on using the entropy criteria, which will usually work just fine for most applications. Now that we have this definition of entropy in the next video, let's take a look at how you can actually use it to make decisions as to what feature to split on in the nodes of a decision tree.
[{"start": 0.0, "end": 8.040000000000001, "text": " In this video, we'll look at a way of measuring the purity of a set of examples."}, {"start": 8.040000000000001, "end": 11.68, "text": " If the examples are all cats or single class, then it's very pure."}, {"start": 11.68, "end": 15.6, "text": " If it's all not cats, that's also very pure."}, {"start": 15.6, "end": 21.28, "text": " But if it's somewhere in between, how do you quantify how pure is this set of examples?"}, {"start": 21.28, "end": 26.6, "text": " Let's take a look at the definition of entropy, which is a measure of the impurity of a set"}, {"start": 26.6, "end": 27.6, "text": " of data."}, {"start": 27.6, "end": 33.52, "text": " Given a set of six examples like this, we have three cats and three dogs."}, {"start": 33.52, "end": 38.68, "text": " Let's define P1 to be the fraction of examples that are cats."}, {"start": 38.68, "end": 41.68, "text": " That is the fraction of examples with a label 1."}, {"start": 41.68, "end": 44.2, "text": " That's what the subscript 1 indicates."}, {"start": 44.2, "end": 49.760000000000005, "text": " And so P1 in this example is equal to 3 out of 6."}, {"start": 49.76, "end": 59.76, "text": " We're going to measure the impurity of a set of examples using a function called the entropy,"}, {"start": 59.76, "end": 61.64, "text": " which looks like this."}, {"start": 61.64, "end": 71.84, "text": " The entropy function is conventionally denoted as capital H of this number P1."}, {"start": 71.84, "end": 77.24, "text": " And the function looks like this curve over here, where the horizontal axis is P1, the"}, {"start": 77.24, "end": 84.08, "text": " fraction of cats in the sample, and the vertical axis is the value of the entropy."}, {"start": 84.08, "end": 91.75999999999999, "text": " So in this example, where P1 is 3 out of 6, or 0.5, the value of the entropy of P1 would"}, {"start": 91.75999999999999, "end": 94.11999999999999, "text": " be equal to 1."}, {"start": 94.11999999999999, "end": 101.0, "text": " And you notice that this curve is highest when your set of examples is 50-50, so it's"}, {"start": 101.0, "end": 107.72, "text": " most impure as an impurity of 1, or really an entropy of 1, when your set of examples"}, {"start": 107.72, "end": 108.72, "text": " is 50-50."}, {"start": 108.72, "end": 115.36, "text": " Whereas in contrast, if your set of examples was either all cats or all not cats, then"}, {"start": 115.36, "end": 118.2, "text": " the entropy is 0."}, {"start": 118.2, "end": 122.48, "text": " Let's just go through a few more examples to gain further intuition about entropy and"}, {"start": 122.48, "end": 124.72, "text": " how it works."}, {"start": 124.72, "end": 129.64, "text": " Here's a different set of examples with five cats and one dog."}, {"start": 129.64, "end": 137.6, "text": " So P1, the fraction of positive examples, the fraction of examples labeled 1 is 5-6."}, {"start": 137.6, "end": 147.72, "text": " And so P1 is about 0.83, and if you read off that value at about 0.83, we find that the"}, {"start": 147.72, "end": 152.79999999999998, "text": " entropy of P1 is about 0.65."}, {"start": 152.79999999999998, "end": 156.29999999999998, "text": " And here I'm writing it only to two significant digits."}, {"start": 156.3, "end": 160.24, "text": " And here I'm rounding it off to two decimal points."}, {"start": 160.24, "end": 162.4, "text": " Here's one more example."}, {"start": 162.4, "end": 166.06, "text": " This sample of six images has all cats."}, {"start": 166.06, "end": 170.16000000000003, "text": " So P1 is 6 out of 6, because all six are cats."}, {"start": 170.16000000000003, "end": 175.54000000000002, "text": " And the entropy of P1 is this point over here, which is 0."}, {"start": 175.54000000000002, "end": 183.72000000000003, "text": " And so we see that as you go from 3-6 to 6 out of 6 cats, the impurity decreases from"}, {"start": 183.72000000000003, "end": 184.72000000000003, "text": " 1 to 0."}, {"start": 184.72, "end": 191.64, "text": " Or in other words, the purity increases as you go from a 50-50 mix of cats and dogs to"}, {"start": 191.64, "end": 193.8, "text": " all cats."}, {"start": 193.8, "end": 196.28, "text": " Let's look at a few more examples."}, {"start": 196.28, "end": 200.12, "text": " Here's another sample with two cats and four dogs."}, {"start": 200.12, "end": 204.24, "text": " So P1 here is 2-6, which is 1 third."}, {"start": 204.24, "end": 214.2, "text": " And if you read off the entropy at 0.33, it turns out to be about 0.92."}, {"start": 214.2, "end": 217.67999999999998, "text": " And this is actually quite impure."}, {"start": 217.67999999999998, "end": 226.39999999999998, "text": " And in particular, this set is more impure than this set, because it's closer to a 50-50"}, {"start": 226.39999999999998, "end": 232.79999999999998, "text": " mix, which is why the impurity here is 0.92 as opposed to 0.65."}, {"start": 232.79999999999998, "end": 235.6, "text": " And finally, one last example."}, {"start": 235.6, "end": 241.06, "text": " If we have a set of all six dogs, then P1 is equal to 0."}, {"start": 241.06, "end": 246.16, "text": " And the entropy of P1 is just this number down here, which is equal to 0."}, {"start": 246.16, "end": 252.68, "text": " So this is a zero impurity, or this would be a completely pure set of all not cats or"}, {"start": 252.68, "end": 254.8, "text": " all dogs."}, {"start": 254.8, "end": 259.48, "text": " And don't worry, we'll show the equation for the entropy of P1 later in this video."}, {"start": 259.48, "end": 266.56, "text": " Now let's look at the actual equation for the entropy function, h of P1."}, {"start": 266.56, "end": 273.6, "text": " Recall that P1 is a fraction of examples that are equal to cats."}, {"start": 273.6, "end": 280.9, "text": " So if you have a sample that is 2 third cats, then that sample must have 1 third not cats."}, {"start": 280.9, "end": 287.2, "text": " So let me define P0 to be equal to the fraction of examples that are not cats to be just equal"}, {"start": 287.2, "end": 290.16, "text": " to 1 minus P1."}, {"start": 290.16, "end": 297.24, "text": " The entropy function is then defined as negative P1 log P1."}, {"start": 297.24, "end": 304.36, "text": " And by convention, when computing entropy, we take logs to base two, rather than to base"}, {"start": 304.36, "end": 311.88, "text": " E. And then minus P0 log base two of P0."}, {"start": 311.88, "end": 326.48, "text": " Alternatively, this is also equal to negative P1 log P1 minus 1 minus P1 log 1 minus P1."}, {"start": 326.48, "end": 331.28, "text": " And if you were to plot this function in a computer, you find that it will be exactly"}, {"start": 331.28, "end": 333.96, "text": " this function on the left."}, {"start": 333.96, "end": 338.92, "text": " And we take log base two, just to make the peak of this curve equal to one."}, {"start": 338.92, "end": 344.36, "text": " If you were to take log of base E, or the base of natural logarithms, then that just"}, {"start": 344.36, "end": 347.92, "text": " vertically scales this function."}, {"start": 347.92, "end": 351.96000000000004, "text": " And it'll still work, but the numbers become a bit hard to interpret because the peak of"}, {"start": 351.96000000000004, "end": 357.88, "text": " the function is a nice round number like one anymore."}, {"start": 357.88, "end": 361.72, "text": " One notes on computing this function."}, {"start": 361.72, "end": 372.36, "text": " If P1 or P0 is equal to zero, then an expression like this will look like zero log of zero."}, {"start": 372.36, "end": 378.16, "text": " And log of zero is technically undefined, it's actually negative infinity."}, {"start": 378.16, "end": 384.08000000000004, "text": " But by convention, for the purposes of computing entropy, we'll take zero log zero to be equal"}, {"start": 384.08000000000004, "end": 385.28000000000003, "text": " to zero."}, {"start": 385.28, "end": 392.08, "text": " And that will correctly compute the entropy as zero or it's one to be equal to zero."}, {"start": 392.08, "end": 397.28, "text": " If you're thinking that this definition of entropy looks a little bit like the definition"}, {"start": 397.28, "end": 402.88, "text": " of the logistic loss that we learned about in the last course, there is actually a mathematical"}, {"start": 402.88, "end": 406.91999999999996, "text": " rationale for why these two formulas look so similar."}, {"start": 406.91999999999996, "end": 411.08, "text": " But you don't have to worry about it, and we won't get into it in this class."}, {"start": 411.08, "end": 414.85999999999996, "text": " But applying this formula for entropy should work just fine when you're building a decision"}, {"start": 414.86, "end": 416.32, "text": " entry."}, {"start": 416.32, "end": 422.24, "text": " To summarize, the entropy function is a measure of the impurity of a set of data."}, {"start": 422.24, "end": 427.24, "text": " It starts from zero, goes up to one, and then comes back down to zero as a function of the"}, {"start": 427.24, "end": 431.04, "text": " fraction of positive examples in your sample."}, {"start": 431.04, "end": 434.2, "text": " There are other functions that look like this that go from zero up to one and then back"}, {"start": 434.2, "end": 435.2, "text": " down."}, {"start": 435.2, "end": 439.40000000000003, "text": " For example, if you look in open source packages, you may also hear about something called the"}, {"start": 439.4, "end": 444.84, "text": " Gini criteria, which is another function that looks a lot like the entropy function, and"}, {"start": 444.84, "end": 448.03999999999996, "text": " that will work well as well for building decision trees."}, {"start": 448.03999999999996, "end": 454.47999999999996, "text": " But for the sake of simplicity, in these videos, I'm going to focus on using the entropy criteria,"}, {"start": 454.47999999999996, "end": 458.79999999999995, "text": " which will usually work just fine for most applications."}, {"start": 458.79999999999995, "end": 463.29999999999995, "text": " Now that we have this definition of entropy in the next video, let's take a look at how"}, {"start": 463.29999999999995, "end": 468.0, "text": " you can actually use it to make decisions as to what feature to split on in the nodes"}, {"start": 468.0, "end": 469.52, "text": " of a decision tree."}]