Content<\/b><\/p>\n <\/p>\n A decision tree is a tree-like structure that is used as a model for classifying data. A decision tree decomposes the data into sub-trees made of other sub-trees and\/or leaf nodes. The question is : How to we build a decision tree? Let’s see!<\/p>\n <\/p>\n Consider the table below. It represent factors that affect whether John would go out to play golf or not. Using the data in the table, build a a decision tree to model that can be used to predict if John would play golf or not.<\/p>\n <\/p>\n This is the algorithm you need to learn, that is applied in creating a decision tree. Although you don’t need to memorize it but just know it. It is called the ID3 algorithm by J. R. Quinlan. The algorithm uses Entropy and Informaiton Gain to build the tree. S = Learning Set Begin<\/span><\/span> (You actually don’t have to worry trying to understand every bit of this algorithm. The application would make is very clear)<\/i><\/p>\n <\/p>\n Here I would give you a simple step by step procedure that is super-easy to follow in creating a decision tree no matter how complex it could be. <\/p>\n Since decision trees are used for clasification, you need to determine the classes which are the basis for the decision. To determine the rootNode we need to compute the entropy. <\/p>\n <\/p>\n In this step, you need to calculate the entropy for the Play Golf column and the calculation step is given below.<\/p>\n <\/i> <\/p>\n For the other four attributes, we need to calculate the entropy after each of the split.<\/p>\n The entropy for two variables\u00a0 is calculated using the formula. <\/p>\n There to calculate E<\/b>(PlayGolf, Outlook), we would use the formula below:<\/p>\n This formula may look unfriendly, but it is quite clear. The easiest way to approach this calculation is to create a frequency table for the two variables, that is PlayGolf and Outlook.<\/p>\n This frequency table is given below:<\/p>\n <\/p>\n Using this table, we can then calculate E(PlayGolf, Outlook), which would then be given by the formula below<\/p>\n <\/p>\n Let’s go ahead to calculate E(3,2) E(4, 0) = 0 <\/p>\n Just for clarification, let’s show the the calculation steps <\/p>\n The calculation step for E(2,3) is given below<\/p>\n Time to put it all together.<\/p>\n We go ahead to calculate the E<\/b>(PlayGolf, Outlook) by substituting the values we calculated from E<\/b>(Sunny), E<\/b>(Overcast) and E<\/b>(Rainy) in the equation:<\/p>\n <\/p>\n E(PlayGolf, Temperature) Calculation<\/b><\/i><\/p>\n Just like in the previous calculation, the calculation of E(PlayGolf, Temperature) is given below. It <\/p>\n <\/p>\n <\/p>\n E(PlayGolf, Humidity) Calculation<\/b><\/i><\/p>\n Just like in the previous calculation, the calculation of E(PlayGolf, Humidity) is given below. It <\/p>\n <\/p>\n E(PlayGolf, Windy) Calculation<\/b><\/i><\/p>\n Just like in the previous calculation, the calculation of E(PlayGolf, Windy) is given below. It <\/p>\n <\/p>\n Wow! That is so much work! So take break, walk around a little and take a glass of cold water. <\/p>\n The next step is to calculate the information gain for each of the attributes. The information gain is calculated from the split using each of the attributes. Then the attribute with the largest information gain is used for the split.<\/p>\n <\/p>\n The information gain is calculated using the formula:<\/p>\n Gain(S,T) = Entropy(S) – Entropy(S,T)<\/i><\/i> Gain(PlayGolf, Outlook) = Entropy(PlayGolf) – Entropy(PlayGolf, Outlook)<\/i><\/p>\n So let’s go ahead to do the calculation<\/p>\n Gain(PlayGolf, Outlook) = Entropy(PlayGolf) – Entropy(PlayGolf, Outlook)<\/i> <\/p>\n Draw the First Split of the Decision Tree<\/strong> From our calculation, the highest information gain comes from Outlook. Therefore the split will look like this:<\/p>\n <\/p>\n <\/p>\n Now that we have the first stage of the decison tree, we see that we have one leaf node. But we still need to split the tree further.<\/p>\n To do that, we need to also split the original table to create sub tables. <\/p>\n <\/p>\n From Table 3, we could see that the Overcast outlook requires no further split because it is just one homogeneous group. So we have a leaf node.<\/p>\n <\/p>\n The Sunny and the Rainy attributes needs to be split<\/p>\n The Rainy\u00a0 outlook can be split using either Temperature, Humidity or Windy.<\/p>\n Quiz 1<\/i>: What attribute would best be used for this split? Why?<\/p>\n Answer<\/i>:\u00a0 Humidity<\/b>. Because it produces homogenous\u00a0 groups.<\/p>\n The Rainy attribute could be split using\u00a0 High and Normal attributes and that would give us the tree below.<\/p>\n <\/p>\n Figure 3:<\/b> Split using the Humidity Attribute<\/p>\n<\/div>\n <\/p>\n Let’t now go ahead to do the same thing for the Sunny outlook <\/p>\n\n
\n
1. What are Decision Trees<\/h3>\n
\nA decision tree is made up of three types of nodes<\/p>\n\n
2. Exercise for this Lesson<\/h3>\n
![](\"https:\/\/2.bp.blogspot.com\/-sD_VfJzi8YY\/WtTygMEGRCI\/AAAAAAAABwA\/mnnX-Q14j3kRoFzbygUrhgDS_DQwSemZQCLcBGAs\/s640\/Decision%2BTree%2BExercise.jpg\")
\u00a0<\/a><\/div>\n3. Algorithm for Building Decision Trees – The ID3 Algorithm(you can skip this!)<\/h3>\n
\nLet:<\/p>\n
\nA = Attibute Set
\nV = Attribute Values<\/p>\n
\n
\nLoad learning sets\u00a0 and create decision tree root node(rootNode), add learning set S into root not as its subset<\/span><\/span>
\nFor rootNode, compute Entropy(rootNode.subset) first<\/span><\/span>
\nIf Entropy(rootNode.subset) == 0 (subset is homogenious)<\/span><\/span>
\n\u00a0\u00a0\u00a0\u00a0\u00a0 return a leaf node<\/span><\/span>
\n
\n<\/span>If Entropy(rootNode.subset)!= 0 (subset is not homogenious)<\/span><\/span>
\n\u00a0\u00a0\u00a0\u00a0 compute Information Gain for each attribute left (not been used for spliting)<\/span><\/span>
\n\u00a0\u00a0\u00a0\u00a0 Find attibute A with Maximum(Gain(S, A))<\/span><\/span>
\n\u00a0\u00a0\u00a0\u00a0 Create child nodes for this root node and add to rootNode in the decision tree<\/span><\/span>
\n
\n<\/span>For each child of the rootNode<\/span><\/span>
\n\u00a0\u00a0 Apply ID3(S, A, V)<\/span><\/span>
\n\u00a0\u00a0 Continue until a node with Entropy of 0 or a leaf node is reached<\/span><\/span>
\nEnd<\/span><\/span><\/p>\n
\n4. Step by Step Procedure for Building a Decision Tree<\/h3>\n
\nStart by determining the root of the tree and the class column<\/p>\nStep 1: Determine the Decision Column<\/h3>\n
\n
\nIn this case, it it the last column, that is Play Golf<\/i> column with classes Yes <\/b><\/i>and No<\/i><\/b>.<\/p>\n
\nTo do this, we create a frequency table for the classes (the Yes\/No column).<\/p>\n![](\"https:\/\/3.bp.blogspot.com\/-sr5Xk0iBLZM\/WtUToEVlKSI\/AAAAAAAABwQ\/914mIDeieOUpVG38pYwx3Q1uVkOBYYXRwCLcBGAs\/s200\/Decistion%2BTree%2B-%2BFrequency%2BTable%2B-%2BPlay%2BGolf.jpg\")
\u00a0<\/a><\/div>\nStep 2: Calculating Entropy for the classes (Play Golf)<\/h3>\n
\n
\n<\/i><\/p>\n![](\"https:\/\/2.bp.blogspot.com\/-nCz0cZ8jYMQ\/WtUWR1NJXdI\/AAAAAAAABww\/qdjyvECbSr4IiBSpYCevuznnKcNNjHmSgCLcBGAs\/s400\/Decistion%2BTree%2B-%2BEntropy%2BCalculation.jpg\")
<\/a><\/div>\nStep 3: Calculate Entropy for Other Attributes After Split<\/h3>\n
\n\n
\n(don’t worry if about this formula, its really easy doing the calculation \u263a<\/p>\n![](\"https:\/\/2.bp.blogspot.com\/-T24C_trBpMk\/WtUb-9eANzI\/AAAAAAAABxA\/6ACcH5f7b1M691AGf9OQOk1bosS2q3OLQCLcBGAs\/s320\/Decistion%2BTree%2B-%2BEntropy%2Bof%2BTwo%2BVariables.jpg\")
<\/a><\/div>\n![](\"https:\/\/4.bp.blogspot.com\/-DM_-HQOvEPY\/WtUiVsMmVMI\/AAAAAAAABxc\/_nJMmx6len4btYASn2hJyMghpIddvHk3gCLcBGAs\/s640\/Decistion%2BTree%2B-%2BEntropy%2Bof%2BTwo%2BVariables2.jpg\")
<\/a>Which is<\/div>\n![](\"https:\/\/4.bp.blogspot.com\/-R2Y6cMoCA2I\/WtUh53NPSxI\/AAAAAAAABxY\/zxCy_7Iz8gI3ha0sthZt_7nvgat42G2-ACLcBGAs\/s320\/Decistion%2BTree%2B-%2BEntropy%2Bof%2BTwo%2BVariables3.jpg\")
\u00a0<\/a><\/div>\n![](\"https:\/\/2.bp.blogspot.com\/-imdc1oWPMe8\/WtUj2JtJNzI\/AAAAAAAABxs\/ch4jn3jU-2UrzM7vgoWOVihVBEhyPsSuQCLcBGAs\/s400\/Decistion%2BTree%2B-%2BEntropy%2Bof%2BTwo%2BVariables4.jpg\")
<\/a><\/div>\n
\nWe would not need to calculate the second and the third terms! This is because<\/p>\n
\nE(2,3) = E(3,2)
\nIsn’t this interesting!!!<\/p>\n![](\"https:\/\/2.bp.blogspot.com\/-HsYFjNR0xdI\/WtUma2vNVHI\/AAAAAAAABx4\/IV0N_y8VlvodugKhxTyaCIatgYVxdRNrQCLcBGAs\/s400\/Decistion%2BTree%2B-%2BEntropy%2Bof%2BTwo%2BVariables5.jpg\")
<\/a><\/div>\n
\nThe calculation steps for E(4,0):<\/p>\n![](\"https:\/\/2.bp.blogspot.com\/-cxGn4uzTrLk\/WtZUyrhFDJI\/AAAAAAAAByI\/NaVe4iGm8AMyWSOZIYOCBxfmMqfGkolCQCLcBGAs\/s320\/Rainy.jpg\")
<\/a><\/div>\n![](\"https:\/\/2.bp.blogspot.com\/-SrB04dFUkZg\/WtZU4Uu16WI\/AAAAAAAAByM\/QX53Nj4Ipq0_aCVJOje1TdI9wXTo5hmrQCLcBGAs\/s320\/Overcast.jpg\")
<\/a><\/div>\n![](\"https:\/\/4.bp.blogspot.com\/-DK4jUKpsE5A\/WtZVqiOqUFI\/AAAAAAAAByc\/KaXYSR50STUYeQ8fwGDiExQEs7CY59PagCLcBGAs\/s400\/Calculating%2BP%2528PlayGolf%252C%2BOutlook%2529.jpg\")
<\/a><\/div>\n
\nIt is easier to do if you form the frequency table for the split for Temperature as shown.<\/p>\n![](\"https:\/\/3.bp.blogspot.com\/-rc3HnCbker4\/WtZWCpgFIXI\/AAAAAAAAByg\/Og2wNOM1eewwu-gdhmAo9ckng6OgQcQwwCLcBGAs\/s320\/Decision_Trees_Temperature.jpg\")
\u00a0<\/a><\/div>\n![](\"https:\/\/2.bp.blogspot.com\/-qbHnJZI0wyM\/WtjT1B1GFII\/AAAAAAAABz4\/HOXdZuurF3wn2OVA0OG6OjxSMShScMK7wCLcBGAs\/s640\/Entropy%2Bfor%2BTemperature.jpg\")
<\/a><\/div>\n
\nIt is easier to do if you form the frequency table for the split for Humidity as shown.<\/p>\n![](\"https:\/\/3.bp.blogspot.com\/-c8GtlQgfO1w\/WtZWVrFwSlI\/AAAAAAAAByo\/7vCeeAs7gJUUluajwqUraoYd1ZpyNtqOACLcBGAs\/s320\/Decision_Trees_Humidity.jpg\")
<\/a><\/div>\n![](\"https:\/\/2.bp.blogspot.com\/-oRbf1GmM9kQ\/WtjVJ7cYgYI\/AAAAAAAAB0E\/sjrabvpFL6I2k6c7LnSdQXkCRVksuLhUwCLcBGAs\/s640\/Entropy%2Bfor%2BHumidity.jpg\")
<\/a><\/div>\n
\nIt is easier to do if you form the frequency table for the split for Windy as shown.<\/p>\n![](\"https:\/\/2.bp.blogspot.com\/-yX0xhO1UgQ0\/WtZWsWFtxJI\/AAAAAAAAByw\/cvp7qED_4xAbn9tc38S_aWnS23GSYDmYgCLcBGAs\/s320\/Decision_Trees_Windy.jpg\")
\u00a0<\/a><\/div>\n![](\"https:\/\/2.bp.blogspot.com\/-4NFnb5Irmsw\/WtjWFpZlpDI\/AAAAAAAAB0Q\/_svnoM6NJCgEjHC4EYW3fqiiMXnj2dD1wCLcBGAs\/s400\/Entropy%2Bfor%2BWindy.jpg\")
<\/a><\/div>\n
\nThen we continue.
\nSo now that we have all the entropies for all the four attributes, let’s go ahead to summarize them as shown in below:<\/p>\n\n
Step 4: Calculating Information Gain for Each Split<\/h3>\n
\n
\n
\n<\/i>For example, the information gain after spliting using the Outlook attibute is given by:<\/p>\n
\n= 0.94 – 0.693 = 0.247<\/b>
\n
\n<\/i>
\n<\/i>Gain(PlayGolf, Temperature) = Entropy(PlayGolf) – Entropy(PlayGolf, Temparature)<\/i>
\n= 0.94 – 0.911 =<\/b> 0.029<\/b><\/i><\/b>
\n<\/i>
\n<\/i>Gain(PlayGolf, Humidity) = Entropy(PlayGolf) – Entropy(PlayGolf, Humidity)<\/i>
\n= 0.94 – 0.788 = 0.152<\/b><\/i><\/b>
\n<\/i>
\n<\/i>Gain(PlayGolf, Windy) = Entropy(PlayGolf) – Entropy(PlayGolf, Windy)<\/i>
\n= 0.94 – 0.892 =<\/b> 0.048<\/b> <\/i>
\n
\n<\/b>Having calculated all the information gain, we now choose the attribute that gives the highest information gain after the split.
\n
\n<\/b>
\n<\/b><\/i><\/p>\nStep 5: Perform the First Split<\/h3>\n
\nNow that we have all the information gain, we then split the tree based on the attribute with the highest information gain.<\/p>\n![](\"https:\/\/3.bp.blogspot.com\/-RBu_zCzBmZc\/WtZbzRVHFuI\/AAAAAAAABzE\/_CWY7woKdnApBTbzx-latDjP3TiTCbUPQCLcBGAs\/s640\/Decision%2BTree%2BStage%2B1.jpg\")
<\/a><\/div>\n
\nThis sub tables are given in below.<\/p>\n![](\"https:\/\/2.bp.blogspot.com\/-o5EUwUj19VA\/WtZkIV-307I\/AAAAAAAABzU\/U3vLsmIaRdg_mmwSaFh3ONgzK3eGR8aXwCLcBGAs\/s640\/Desision%2BTable%2BFirst%2BSplit.jpg\")
<\/a><\/div>\nStep 6: Perform Further Splits<\/h3>\n
\n![](\"https:\/\/1.bp.blogspot.com\/-yn1hXVNIVj8\/WtjiWezBSWI\/AAAAAAAAB00\/Kivy42FD0zkWfw-hkTAVrh0VkbBGYDQ3gCLcBGAs\/s400\/Humidity%2BSplitTable.jpg\")
\u00a0<\/a><\/div>\n![](\"https:\/\/3.bp.blogspot.com\/-AwUteKA-yXw\/WtjYPllqShI\/AAAAAAAAB0c\/fYwB4Q8-nmk_3u9x8r5X7smfWmuMsu_DwCLcBGAs\/s640\/Split%2Bby%2BRainy.jpg\")
<\/a><\/div>\n
\nThe Rainy\u00a0 outlook can be split using either Temperature, Humidity or Windy.
\n<\/b>
\n<\/b>Quiz 2<\/i>: What attribute would best be used for this split? Why?
\nAnswer<\/i>:\u00a0 Windy <\/b>. Because it produces homogeneous\u00a0 groups.<\/p>\n
![](\"https:\/\/2.bp.blogspot.com\/-EexbgEZsjWs\/WtjijSF-ZzI\/AAAAAAAAB04\/uCkfFxo_9XA7XAGwdzMB0ZFO5cYY6qfmQCLcBGAs\/s400\/Windy%2BSplitTable.jpg\")
\u00a0<\/a><\/div>\n![](\"https:\/\/1.bp.blogspot.com\/-vEy0tVpBuQ4\/Wte39ZkiXpI\/AAAAAAAABzk\/8n-CF4cmYnEylEKUKf0-yiJtWmmYy2pSgCLcBGAs\/s640\/Decision-Tree-Final.jpg\")
<\/a><\/div>\n