Decision Tree Solved | Id3 Algorithm (concept and numerical) | Machine Learning (2019)

[Music] another video for dressing and in this video we are going to learn about decision tree and the concept of id3 algorithm by solving a very simple problem then how a decision tree looks like so if I have to form a decision tree off should I accept the new job offer then it looks like this here we can see the logic and how it is making the decision and it is very simple and clear but what is the decision tree well a decision tree is a tree where each node represents a feature on an attribute and each link represents a decision rule and each leaf node represents an outcome a decision tree is a supervised learning algorithm now for now we have a couple of algorithms to form a decision tree but here we will focus on id3 algorithm that uses entropy function and information gain so now let's see this problem we have been given a data set and we have to make a decision tree that predicts whether tennis will be played on the day or not now list let's observe the data set here we have five attributes outlook temperature humidity bindi and play tennis this play tennis is the class attribute there is the final outcome and its value depends on another four attributes now to make a decision tree we have to first choose the root node so how we will choose the root node well the attribute that can best it classifies the training training data you can use this as the attribute of root node but how to choose the best attribute so from here we will use id3 algorithm well I did see algorithm has two important concept that is entropy function and information game entropy tells about the uncertainty in data set what does that means it means the number of positive and number of negative example in for example if we have equal number of positive and negative example that the entropy will equals to zero if we have only positive examples or only negative example and then draw a very close to zero now let's next comes with information gained so information gain is the diff in entropy before and after splitting the data set on interview tape what does that means this is a word data set initially we will calculate the entropy for this entire data set next we will calculate the entropy for this particular attribute out loop then temperature then humidity then wind it then we will sum up this this is notice this average information and this average information we will subtract it from the entropy of the entire data set so that is known as information game so like this this is information again and this is the entropy next that comes is id3 algorithm concept what does id3 algorithm sees so the first step is compute the entropy for the entire dataset as I have told you have to calculate the entropy for the entire dataset now for each and every attribute each and every attribute in the sense this Outlook temperature humidity Wendy for each and every attribute now you have to calculate the entropy and then average information entropy and then what you have to do you have to calculate the gain and then pick the highest again that will be your node and we have to repeat this process until we get the tree how do we know that we get the tree that is the last node should be a leaf node okay so now let's see the problem this is the entire dataset which we had the first step is calculate the number of positive examples and number of negative examples so there are nine positive example that is yes yes yes there are nine years and five negative example five knows entered total is 14 so if you have to calculate the entropy then just to get to the formula how it was minus P upon P plus n where P represent positive end and represent negative make sure here the logarithmic function has base two and P upon P plus n that is a positive value it's not a negative similarly n upon P plus n log two and upon P percent now substitute all the values that will be minus nine upon nine plus five nine positive examples and five negative example you substitute all the values and the value you will get is point nine four zero so this point nine four zero is the entropy of entire data set so that's why it is represented as drop es next we have to do is we have to calculate entropy for each and every attribute so first I am taking Outlook so outlook has how many values sunny rainy overcast three different value we have so we have split our dataset according to those three values so here when outlook is equals to sunny when I want a sequester rainy when outlook is it was too overcast so like this we have now three separate tables now in this three separate tables you will see for sunny how many positive values are there so for sunny we have two positive values so right to now four negative four negative samples how many values are there three so we have three negative example and then we will calculate the entropy how we will calculate the entropy by simply putting substituting the values in the formula similarly for rainy rainy how many positive values are there three so write three how many negative values 2 so entropy is point and 7 and similarly for overcast all the values are positive so 4 and 0 now to calculate the entropy see this is the formula just substitute the values p value n value and you will get the respective answers now the next value next step was to calculate the average information entropy based on the previous formula for the attribute outlook this will be the formula that is for positive examples of sunny plus negative examples of sunny upon P plus and here people descend represents the number of positive examples and number of negative example of the ndaya dataset okay it's not about that particular it's not about this particular attribute we are talking but in state we are talking about this entire dataset okay so here P of sunny that's enough sunny upon P Pleasant and entropy out to get across to sunny then Outlook is equals to rainy so P of any person or any upon P person and then when outlook is equals to overcast then P of overcast percent of overcast upon P plus n so what will be the value how many positive values of sunny are there so in sunny we have two positive values and how many negative value three so like this we will write 3 plus 2 divided by total number of positive value that is nine in total number of negative value is 5 and similarly what is the entropy of Outlook is equal to sorry so that we have seen that is 0.97 month so we were right point nine settlement similarly when outlook is equal to rainy so how many Rainey's are there so for rainy we have three positive and two negative and then drop please point nine seven one so just write the exact same values over here and then further overcast so the value which we caught is 0.693 now the next step that comes is you have to calculate gain and what is gain gain is equals to your total entropy minus whatever the information you have got so and drop your face is point nine four zero that we have calculated it in the first step so gain of outlook will be 0.9 four zero minus point 6 9 3 is equals to 0.2 four seven make sure you try to solve the problem while watching the video itself so that you can have a better understanding of what we are doing over here now the next attribute which we have is temperature again the temperature had three values that is hot mild and two so for hot we have one table then for mild and then per cool again similarly what we will do for hot the number of positive examples are two the number of negates examples are two and then drop it will be one as I've said whenever the number of positive and number of negative examples are same then then drop is equals to 1 similarly for mild we have for positive examples and two negative examples so then drop is point nine one eight and four similarly similarly for cool we have three positive examples and one negative example in the entropy is 0.8 one one you can calculate the entropy simply by substituting the values in the formula if you have any doubts then you can just comment down or you can just ask you know the next step will be obviously to calculate the information entropy for this again the same thing how many values temperature can have hot mild and cool according to that P of 4 plus n of hurt upon P plus n then P of minus n of mile upon be present and P of cool dozen of call divided by P person you can get the respective values from the table over here substitute all the values over here and then you will get the information as point nine one one now what was the next step this system was to calculate the gain so again gain is equals to and drop your face - I of attribute how much the entropy was there a point nine four zero so what will be the gain gain will be point nine four zero - what was the value point nine member is R equals two point zero to nine this is the gain of the temperature now what is the next next attribute is humidity humidity has to review that is high and normal now again we will form a table according to normal and according to height then we will calculate the number of positive example over here is 3 negative of number of negative example over here is 4 this is 4 high that is this table and similarly for normal there are 6 positive examples and one negative example so entropy over here is how much 0.591 now again you will calculate average information entropy and how you will calculate mu it is equals to high so number of positive Heights negative examples of high upon total P plus N and plus entropy community is requesting normal and positive norm positive normal that's negative normal divided by total key person substitute the respective values and you will get 0.788 and in this case the gain will be entropy minus I attribute a similar 0.94 zero minus 0.78 8 and the value will be 0.15 - only now we are left with last attribute that is windy and in this video we have a gain strong and weak so we will make the table with respect to strong and V then we will see how many positive and negative examples are gel and then we will calculate the entropy now after that again average information entropy so when D is equal strong so positive strong the single is strong divided by P plus N and again when D equals to be so positive V there's negative wake up on P plus N and as you know P and n are the values from the original data set and this P we can in week are from this table then now again separate the values and the answer will be here 0.89 2 and then again calculate the gain so again will be 0.9 4 0 minus 0.8 9 to that it will be first to point 0 4 it too much right so many four attributes are there then you have to calculate so much and at last we will compare all the values that is here outlook point 2 4 7 temperature point 0 to 9 your military point 1 5 2 wind eight point zero four eight and the highest value is outlook so we have to pick those with that value and this will be our root node so the root node is outlook so how a decision tree will look like now we have root node as outlook and this outlook have three decision rules that is sunny overcast rainy but in in the overcast all the values are yes so you can directly make a leaf node over here and thus it doesn't require any further splitting but for sunny we have variable values like for some value it is yes for some it is no system we cannot say that we're a sunny will give yes or no so thus we have to do for the splitting for sunny as well as rain so now we will form again new data set this will be with respect to sunny and this will be with respect to rainy we have to perform all the operations on sunny and then we have to perform all the operations on rainy I know it's too much but just a little bit and then it will be over so first of all we will take for sunny ok there's just a little mistake but ok the number of positive examples are how much to a number of negative examples are how many three so just total is five so now the P and value change before that it was nine and five but for this now it we have two and three okay so now the entropy over here will be just substitute the values 2 upon 2 plus 3 and all the values and you will get entropy is point nine seven one make sure you don't make the mistake here the P and n values are two and three this is like a new data set which you are going to solve then after that you have to calculate again for each and every attribute so now we will take humidity but make sure you are taking only the sunny values why because first because now we are calculating for sunny okay so you cannot take values from overcast we have to take values from sunny itself so that's why when you are forming the table make sure that you are taking outlook value as sunny and then you are checking humidity and then we will check play tennis so here the same method timidity high normal number of positive examples how many positive example only for high that is zero and negative examples are three so three and four normal number of positive examples are two a number of negative example is there when high when you omit it is equal to normal that is zero so entropy will be zero again you can calculate the average information entropy try to calculate by yourself natural answer with the slides given over here so information of humidity is equal to zero now you have to calculate the gain so what was gained according to previous formula and drop t minus i of humidity so how much entropy we got that was 0.97 1 and what is the humidity we got 0 so 0.97 1 minus 0 that will be 0.9 7 1 similarly we will calculate for windy now again the outlook value should be sunny now Wendy can have two very strong and weak according to that strong how many positive value burn how many negative value burns and drop is 1 and similarly how many positive value for week 1 and negative value 2 so point nine one eight now you will calculate average information entropy that will be equals two point nine five one and the gain that will be point zero two zero that is point nine seven one - Oh point nine five one that is the cost of point zero two zero similarly you will calculate for temperature make sure outlook values across to sunny you have three values here cool hot mild according to that you form this table calculate the entropy then calculate average information entropy and then calculate game and you take a little time but please make sure you pause the video and calculate all the values and make sure it is correct and if you have any doubt write it and write down in comment then you have to pick the highest gain attribute from this three value for the temperature we got 0.5714 a humidity we've got point nine seven one four Wendy we got point zero two to the highest value over here is community so the next known in sunny that is after sunny will be humidity so it will look like this we have first outlook then we had sunny then in the sunny the next node which we have selected as humidity now see for normal all the values are yes so I can directly write yes over here and for hi I have three value that is no so I can directly like right now so it is the pure leaves and we do not need any further expansions but now the another another decision rule is remaining that is raining so it requires further spitting now again they have to repeat the entire process for rainy so now this is the table for any again the positive the how many positive values are there three how many negative values are there to total five again you will calculate entropy it's the same value here it comes Oh point nine seven one then you have to calculate at each attribute and first of all for humidity make sure here the outlook value is rainy not sunny rainy okay then calculate the humidity calculate the table number of voltage positive examples on how much for high it is one and again for high negative example is one so write one one entropy will be one for normal for normal the number of positive examples are how much to number of negative example is how much fun the center of this point nine minute calculate information that will be how much point nine five one again calculate gain what will be the gain point nine seven one that is this entropy minus the information of humidity so point nine seven one minus point nine five one that is point zero two zero similarly calculate for windy again outlook well it should be rainy so for strong no no positive values but two negative values entropy is zero similarly three positive values no negative values then drop is zero calculate the information for windy then calculate gain is equals to point nine seven one now for temperature same process here if it here we have only two values cool and mild there is no hot so lucky you have to just do only two two values you have to finally for two values calculate entropies then calculate the information then calculate gain and thirst finally the biggest value that is the highest value is for vendee that is point nine seven so the next story in rainy will be what Wendy so the final decision tree will look like something like this we have out loop in the outlook we have three decision row that is sunny overcast and rainy for overcast we can directly write yes but for sunny again you have to check for the midde T if the value is high then it will be know if it's the value of normal then it is yes and similarly for rainy we will check another attribute windy that wind is weak then yes if it is strong then no so this was all about decision tree and id3 algorithm in the next video we are going to see how to implement the same in Python so stay tuned with us do like subscribe share and you can also write a side code reading and read gmail.com so happy learning thank you [Music]

Channel: Code Wrestling

Views: 217,576

Keywords: id3, ID3 Solved, id3 algorithm, id3 example, id3 in data mining, id3 concept, id3 decision tree, id3 algorithm numerical, dwm, decision tree analysis, decision tree, data mining, last moment tuitions, last moment tuition, datawarehouse, decision tree in machine learning, decision tree in big data analytics, classifier, ml, bda, last moment tuition decision tree, apriori algorithm in data mining, lmt, naive bayes classifier, how to draw decision tree

Id: UdTKxGQvYdc

Length: 17min 43sec (1063 seconds)

Published: Thu Apr 18 2019

Reddit Comments

[u/aivideos]

• Original Title: Decision Tree Solved | Id3 Algorithm (concept and numerical) | Machine Learning (2019)
• Author: Code Wrestling
• Description: Decision Tree is a supervised learning method used for classification and regression. It is a tree which helps us by assisting us in decision-making! Decision tree ...
• Youtube URL: https://www.youtube.com/watch?v=UdTKxGQvYdc