2-16. Decision Trees

Well, it seems that the first bucket is the best one, because no matter what we do, we’ll always pick red, red, red, red so we’ll win every time. We can see that although it’s not very easy to win in any of the other two, it’s easier to pick red, red, red, blue in … Read more

In order to cook up a formula for entropy, we’ll consider the following game. In this game, we’ll start with a configuration of balls; say red, red, red, and blue, and we’ll put them inside the bucket. Now, what we do is we pick four balls out of this bucket with repetition and we try … Read more

Now in order to go further with Decision Trees, we need to learn an important concept called entropy. Entropy comes from physics and to explain it, we’ll use the example of the three states of water. These are solid, which is ice, liquid, and gas, which is water vapor. Let’s think of the particles inside … Read more

Well, let’s try both. The best horizontal line would be somewhere around here. It does an okay job, but it doesn’t really separate the points that well, at least a lot of blue points in the red area and vice versa. So, what happens if we try a vertical line? Well, it seems that the … Read more

Now, in the last example, we constructed a tree with categorical features, namely gender and occupation, but we can also create a tree with continuous features. Let’s go to this example, which you may see in other parts of this class. The example is an Admissions Office which takes two pieces of data from the … Read more

Okay. Well, let’s see what happens if we split them by gender. If we split them by gender, we see that the women downloaded WhatsApp and Pokemon Go, while the men downloaded Snapchat and Pokemon Go. This tells us a bit, but not much. On the other hand, if split by occupation, we can see … Read more

Well, let’s see. A woman who works at an office. In the table, there’s two women who work and both downloaded WhatsApp. So, let’s say, it’s safe to assume that recommending WhatsApp to this new person is the best idea. Now, for the man who works at a factory, we’ll see that there’s another man … Read more

So, let’s start with an example. Let’s say we’re in charge of writing the recommendation engine for the App Store or for Google play. Our task is to recommend to people the app they’re most likely to download, and we should do this based on previous data. Our previous data is this table with six … Read more

Okay, so now, let’s go ahead and build a Decision Tree. Our algorithm will be very simple. Look at the possible splits that each column gives, calculate the information gain, and pick the largest one. So, let’s calculate the entropy of the parent, which is this data. We’ll calculate the entropy of the column of … Read more

Correct. The first way to split them does not help us at all. We ended up with very similar sets of red and blue points and we learn nothing about the data. The second way did a decent job. We managed to get most of the blue ones on one side and most of the … Read more

Okay, so now, we’ll use what we know about entropy and information gain to build Decision Trees. Let’s say, we have our data in the form of these red and blue points and we want to split it into two. So, I’ll show you three ways of splitting it, and here are the three ways. … Read more

Correct logarithm is the answer since it satisfies that beautiful identity that says, the logarithm of a product is the sum of the logarithms. Thus, our product numbers becomes a sum of the logarithms of the numbers. In this case, we get minus 3.245. Now in this class, we’ll be using log as a logarithm … Read more

Hello, and welcome to the Decision Trees section. Let me introduce the concept of decision trees by playing this fun game on the Internet. It’s called the Akinator. And the way it works is the genie will ask you questions about some character, and based on these questions, it’ll guess who it is. The questions, … Read more