Decision Tree Algorithm In Machine Learning |How Does Decision Tree Algorithm Work? | Simplilearn

Key Takeaways

[music] Hello and welcome to simply learn. My name is Dutindra and today we going to talk about an algorithm called as the decision tree algorithm. So in this course we're going to talk about the following agendas. We'll discuss what is decision tree algorithm. Then we'll talk about the few terminologies that are used in decision trees. We'll then try to work around with how does a decision tree work. We'll do some mathematical calculations. How do we find out the decision tree is created with using the best split method of information gain. Then how is the prediction achieved through decision trees? Then we'll build up a decision tree with a sample example. Then we'll talk about some advantages and disadvantages and real world applications where decision tree concept is used. So let's move on. So we have some quick questions. So what type of machine learning algorithms is a decision tree primarily used for? So what is a decision tree algorithm? When you talk about a decision tree algorithm, it's a kind of process or it's a machine learning modeling strategy that allows us to perform a nonlinear modeling with non-parametric functions. Now when I say nonlinear that means it is an algorithm that can detect a nonlinear patterns in the data as well as it is a non-parametric algorithm wherein it does not assume or it does not require any kind of preassumptions for the data just like we do not require to have a normally distributed data for this or we do not require a standardized data for this. It's fine if the data is not in a proper format or not in a standardized format. It's also you fruitful to work around with this particular algorithm with such type of data. Right? It is more or less a kind of an algorithm which works on the principle of creating up a decision based upon a condition. So every time we have to take a decision and then based on the decision we move on to the next layer or next level of decision-m process until we reach to the final conclusion. So this entire decision making process in the decision tree is divided on the basis of three different uh nomenclatures. I would say that the first or the starting point is called as the root node which is usually representing the entire data set that we have. Then we have some certain decision nodes on which we split the data and create up the sub tree part of it based upon some conditions. And finally we have the leaf nodes which are the final outcomes or the predictions. So you can say that leaf node represents the target variable of the data typically in a classification or a regression problem. Now the question arises how will the decision tree make the learning process. So it does the learning process by taking up the part of data. Now how does it choose the part of data? That's a detailed process. We'll discuss that in further in this lesson. But it divides the data based upon a condition and that condition will try to generate or that division will try to generate the data partition in such a manner that the amount of error or the amount of uncertaintity that we have in a decision making process that uncertaintity gets reduced by further splitting. Now that needs to be explained through an example. The idea is that suppose for an example at one point of time with a full data I am uncertain to take a decision. Maybe the full amount of uncertaintity can vary depending upon problem to problem. But if it is a binary classification problem the amount of uncertaintity can be a maximum of 50% uncertain because if you are 50% uncertain then you have equal mix of the binary class then you will be having a 50% uncertaintity or 0.5 uncertaintity value. We also term that as a genie impurity we'll discuss that later. So that impurity needs to be decreased and we need to reach out to that impurity in decision making process to a level zero. So until we reach the level zero, the decision tree process will keep on continuing splitting my data and tries to reach out to an impurity level zero. And in each step, it looks for the maximum information gain. When it say maximum information gain, the information gain is nothing but the change in impurity or change in indecisiveness uh that we have at one particular level. we will have maximum indecisiveness whatever is possible at the start when we do not we have not done anything with the data set. So we'll have the maximum whatever the information uh loss or or whatever the impurity that we have in the data that would be available at that point of time and we need to further decrease it down to the level zero. Now for this purpose it is always evident that we would require to split our data. Now there would be usually multiple number of features uh in a data set and out of those you need to think of which feature is the feature to start splitting the entire set. So we need to choose out the best possible feature out of the given features and that is done by iteratively calculating the information gain for every single feature and whichever feature gives me the maximum information gain we'll choose that feature. Now how is that information gain calculated? So in order to calculate the information gain we need to measure the impurity on the full data and then find out the impurity when we divide that data based upon a particular feature or a particular condition. When we do that division that each subset of the data that is being created each subset will provide a certain different level of impurity. We'll take the weighted average of the impurity of the number of splits that have been done and we'll check with the uh weighted average of or or rather weighted sum I should say the weighted sum of the impurities at the splitted level to find out what is the impurity at the split level. Once we get the split level impurity and we compare with the impurity without the split that is with the entire set remaining we should see a decrease. Now that is repeated for every single feature and once we see the maximum difference in the change in impurity we choose that particular feature to be our the feature to be splitted at. Now if we are working on the entire set the first split the first feature that we choose to split the data is called as the root node because root node will be the first feature on which we'll split the data. After that we'll get certain number of branches. We'll pictorially look at that after that get certain number of branches. Each branch subset of the data will now act as a sub tree a sub data and we need to repeat that process on that sub data and again considering that particular data point as the entire set find out the impurity on that particular branch and do the split again on any number of the features available. It's a repetitive process. Let's move on and understand the key terminologies like we have root node right. [clears throat] So in every tree we will have a root node, decision node and leak nodes. Root node is the starting point as I've said before that represents the entire set. The splitting process splits the root node or divides any particular node. It can be a root node or a decision node that requires a split. So that root node or decision node will be splitted up and that process is called as the splitting process. Splitting of the tree. Then we have decision nodes where we take up a decisions right. So the decision node are those nodes which are splitted up further as well based upon the decision that has came up. Then we have leaf nodes as I've said before these are terminal nodes or the final nodes in my outcomes and that usually represents the target variable of the data set because of which it is not further splitable. Then another term that is called as pruning. The pruning of the tree means it's a very simple concept uh in decision tree algorithm. It talks about the process of controlling the growth of tree. There are two types of pruning that we do in decision making decision trees. One is called as a pre-p pruning methodology and the other one is called as the post pruning methodology. In pre-p pruning methods, we do not allow the tree to grow itself at initial stage. And in post-p pruning, we take up the process to allow the tree to grow in full and then cut down certain branches of the tree so that my tree is not anymore an overfit. So we try to do the overfit or resolve the overfitting problems using either pre-p pruning or postp pruning. This can be co understood with the concept of early stopping as well. So how does a decision tree work? So we taking a practical example to understand how does my decision tree is going to work. So consider this data set. We have income, credit score and status. So it says that if your income is high, credit score is high, status is approved. Uh so we have two classes here. Target variable class is approved and rejected. If you look at the amount of uncertaintity, you can think in terms of probability of the loans getting approved. Uh irrespective It is out of four cases there are three cases which are getting approved and one case is not getting approved. So the probability of cases getting approved is uh 3x4 and rejected is 1x4. We will utilize these probabilities and find out the amount of impurity based upon either gen impurity or the entropy formula for different features. So at root node we need to think of two features. We have two features either the income or the credits form. So should we split on income or should we split on credit score right? So we need to decide whether should I split on income or should I split on credit score for the decision notes either income is high or the credit score is high that is one decision if the decision income is high credit score is low it's still approved income is low credit score is high it can be approved so these are all decision note criterians these are the four scenarios how will that really so how do we measure the best split on that as I talked about the gen purity so it is a measure of mix of denotes how much impure is my decision making process in the data or in the target variable. Right? In a class typical classification problem, we will have uh let's say if you take a binary class classification problem, you will have two classes. Let's say class A and class B. Now if let's say in our case we have three examples for approved and one example for rejected, right? So we have a 7525 ratio. So there is a possibility of 75% chance of approval and 25% chance of uh rejection. So it's a log measure to be very precise or squared probability measure. So the amount of impurity can be given here as 1 minus to be very precise. Let me just get a hold of a pen. Okay. So I've got a hold of this now paint window so I can try and write down few things. So suppose in my example we had four number of cases. There were four cases out of which there were three cases that were getting approved and there was one cas that was rejected. So when we talk about the probability of being approved that's supposed to be probability of being approved is 3x4 that's the probability of class A approved class is 3x4 and the probability of class R that's the rejection probability is 1 by 4. Now the genie impurity the amount of impurity present or amount of indecisiveness present is given by this formula. The formula is that's going to be 1us sigma i is = 1 to n probability of is class now the whole square. So that's typically the formula for gen purity. So if I have to take that into my consideration in this example that's going to be like 1 minus now we have two probabilities 3x4 and 1x4. So 3x4 squared + 1x 4² that will be your final gen impurity right there that becomes 9x 16 + 1x 16 that's 10 x 16 1 - 10 x 16 is 6x 16 so that is going to be 6x 16 that equals to 3x 8. So that is the amount of uncertaintity that we have 3 by 8 in the given example at that junction that's your initial impurity level good now when we add those examples we had certain cases of high income and low income so if we try to split on income I will consider cases on income if I split on the credit score then I'll have certain impurity score so let's keep this number 3x8 into picture and let's go back to the presentation Okay, here it goes. So that was your information here. High high high will approve. So if I think of dividing the data on high. So we have two high cases and two low cases. It is think of taking income as my root node. So if the income is either high or low. So if the income is high in both the cases I am getting the status is approved. So if you think of taking up a tree so either I can decide. So let me just take this off. Remember that number 3 by h that's the amount of impurity when I have not splitted my data. Let's now look at the cases that we have here. When we had taken on income, we had two total number of cases which are high and there are two cases for low. Now if I think of dividing on income either the income is going to be high or the income is going to be low. But when the income is high we are making up a decision and we are coming to the lease note called as approved. If the income is high irrespective whatever product score is that it is approved. So if you look at this side of subset of the data high side right the entropy value there is zero or the gen impurity is zero. Why? Because we have only one class which is approved. So that will be 1 minus sigma 1 upon 2 the whole square or rather two upon two the whole square we have two two nodes of approved and both the two so that will be sigma 1 upon 2x2 the whole square plus not sigma this 2x2 the whole square sigma term goes off so 2x2 the whole square term and because of which this will finally come out as 1 - 1 which is zero so you'll get zero impurity whereas in the if you think of looking the low side at the low side I still have two samples but one is zero one is one so I get a gen impurity value of 0.5 my impurity value is.5 there because we have equal number of samples we are 50% sure that it's approved 50% unsure it is not approved so we again need to split that data and here we can split that data on credit score maybe and then we can get credit score high and low credit score high credit score low I'll generate high score approved and low score not approved and that's how it works So this how the decision tree is created up in real world practice. Now based upon condition that's what we have looked at same example is given income is less than 0.5 gen impurity samples is five value three and two uproot and so on in a similar term the prediction process in a prediction process once we get the decision tree completed for any random different inputs right right because it follows a path so every particular path leads to a decision it leads to a final decision level so whenever we give a certain set of inputs that follows the decision making process and tries to reach out to one of the branch leaf nodes. Whichever leaf node branch it reaches out to be that becomes the final answer. The same example 70% approved that's 7535. Another measure to measure the impurity. Now I've given you one of the measure called as gen impurity. The next measure that is commonly used in decision tree algorithm or in classification problem is called as entropy. Now entropy is also called as log loss. entropy, logos are similar things. Uh it actually is a quantification of the amount of randomness. When I say those words, what is that means? That means it talks about the amount of certaintity of wrong predictions. Talks about the amount of uncertaintity of wrong prediction. that something uh is based upon the if I make up a particular prediction then that prediction is going to be wrong that's the impurity measure of entropy means so it tries to consider the same thing essentially that can be given by the formula minus of sigma probability of iat class give lock to the base probability of iat class very simple example I'll work back through with this example this is a common data set available that's called as a weather data in the field of machine learning and one of Problem statement says the task is to determine to play tennis. There are 14 instances, nine yes, five nos. It's mixed or pure. Well, besides splitting, we need to think of this. There are nine yes and five nos in the entire data set. So if you think of the probabilities of each class, probability of yes is 9 by 14 and probability of no is 5x 14. You got those approximate probabilities. Then we apply the entropy formula onto that. That's the amount of randomness or disorder in the data. So that is h of s usually h is used or e is used to uh showcase the entropy. So probability of yes log to the base 2 probability of yes plus probability of no log to the base 2 probability of no we'll get certain values 0.94 is the value after we apply the formula. Then how do we interpret this? It's a very high entropy. very high entropy means you will get an entropy value one when you have a equal distribution of the class both the classes are equally distributed so high entropy means a mix and uncertain so we need to split the data so how to choose the best split so in order to do that we need to look at the information gain so the entropy at the node or the last starting stage where we have not split to the test 0.94 now if I change my entropy and if I let's say divide on a particular feature that's child one and child two if I split on feature one I get 0.5 entropy if I split on uh two I get 0.3 entropy right so my average entropy if I split on this is going to change like the average of those considering each of these child one and child two is equal responses so 5 + 3 the average you take up 0.4 4. So from 0.94 I'm coming out to an entropy level or error level of 0.4 that brings my information g value to 0.54. So now that's outlook and then we have five instances two yes three nos that brings entropy level 0.97 I get this much change in weight overcast that much change rate I have that much overcast I have four instances or I belong to four yes so entropy is zero zero entropy means I have a pure node one entropy means completely impure node that's how the tree will look like so outlook sunning humidity high normal uh then wind strong and weak and the overcast condition. Some advantages and disadvantages of decision tree. Decision trees are very easy to interpret and it can be easily understood by anyone because they are based upon the basic fundamental principles of life. Every now and then when we take up a decision in the real world uh it's based upon certain situations and conditions and based upon that we follow the best possible path. That's what decision tree in machine learning also does. Again another advantage it's used for both regression and classification. can handle both categorical and numerical data right no pre-processing as I said that it's a non-parametric algorithm the disadvantages include it's very prone to overfitting why because if you allow the tree to grow in full it will try up to a maximum level to achieve the maximum correct answer so it's very very prone to overfit getting overfitted that's major problem with this decision trees if the data is changing by a very small margin decision tree will entire decision tree might change. So small change can bring up a huge change in the tree and the entire process might change. That's another disadvantage. It can also be biased. If there's a class imbalance, it can get biased. That's another disadvantage. Let's talk about some real world things. In real world, we use decision tree for the loan approval predictions. We have seen that example medical diagnosis or you can use it for breast cancer classification or any kind of you know disease diagnosis that can be used based upon the given inputs of the medical reports. Customer segmentation like for marketing we can use for customer segmentation we can use for product detection marketing analytics uh it can be used up anywhere essentially any kind of classification problem where there is a nonlinear data we can always rely on decision tree the only problem with decision tree is being overfitted so if we apply overfitting measures like pruning of the tree or we can use multiple number of trees algorithms like random forest or gradient boosting or you can use xg boost Ada boost models uh then also that will be very very helpful but decision tree is one of the basic algorithm that is very highly and widely used in advanced level algorithms too. So thank you very much team for giving your time to listening this. If you have further questions we request you to put up your questions and remarks into the comments. Thank you very much. See you soon. Have a good day. Bye-bye.