Saturday 21 December 2013

Decision Tree Algorithm


How To Workout Decision Tree Algorithm


Decision Tree Induction is the learning of decision trees from class-labeled training tuples. A decision tree is a flowchart-like tree structure, where each internal node (nonleaf node) denotes a test on an attribute, each branch represents an outcome of the test, and each leaf node (or terminal node) holds a class label. The topmost node in a tree is the root node.

During the late 1970s and early 1980s, J. Ross Quinlan, a researcher in machine learning, developed a decision tree algorithm known as ID3 (Iterative Dichotomiser). This work expanded on earlier work on concept learning systems, described by E. B. Hunt, J. Marin, and P. T. Stone. Quinlan later presented C4.5 (a successor of ID3), which became a benchmark to which newer supervised learning algorithms are often compared. In 1984, a group of statisticians (L. Breiman, J. Friedman, R. Olshen, and C. Stone) published the book Classification and Regression Trees (CART), which described the generation of binary decision trees. ID3 and CART were invented independently of one another at around the same time, yet follow a similar approach for learning decision trees from training tuples. These two cornerstone algorithms spawned a flurry of work on decision tree induction. ID3, C4.5, and CART adopt a greedy (i.e., nonbacktracking) approach in which decision trees are constructed in a top-down recursive divide-and-conquer manner. Most algorithms for decision tree induction also follow such a top-down approach, which tarts with a training set of tuples and their associated class labels. The training set is recursively partitioned into smaller subsets as the tree is being built.

Problem 1:



Iteration 1:

Find gain for class: Play
Calculate the no of yes  and no 
          No – 5
          Yes – 9
Total observation – 14

           Entropy([9,5]) = (-9/14 log 9/14 – 5/14 log 5/14)/log 2 = 0.940


Then find the gain for all instance.

          EntropyOutlook([2,3],[4,0],[3,2]) = 5/14(-2/5 log 2/5 – 3/5 log 3/5) + 4/14(-4/4 log 4/4) + 5/14(-3/5 log 3/5 – 2/5 log 2/5) /log 2

          EntropyTemp([3,1],[4,2],[3,1])/log 2
          EntropyHumidity([4,3],[6,1])/log 2
          EntropyWindy([2,6],[3,3])/log 2

Therefore
          gain(outlook)  = Entropy([9,5]) – EntropyOutlook([2,3],[4,0],[3,2])=0.247
          gain(Temp)       = 0.029
          gain(humidity)   = 0.152
          gain(windy)      = 0.048

Find which is having highest gain and it will be taken as the root node.

So here in overcast all the leaf nodes are yes therefore we don't have a further recursion in that.You can delete the entire row which is having overcast as outlook or else continue with the same table.



Iteration 2:

Now we need to identify what all nodes can come under oulook -> Sunny and outlook -> Rainy.
First look for the case of Sunny. Sort out the master table to a child table which comprises only Sunny entry.



Calculate the no of yes  and no 
          No - 3
          Yes - 2

          Entropy([3,2])        = 0.97095

          gain(Temp)       = 0.57095
          gain(humidity) = 0.97095
          gain(windy)       = 0.419973


Find which is having the highest gain
          gain(humidity) = 0.97095


So humidity comes under Sunny
New tree becomes
 

From the above diagram all leaf node is same . Therefore no iteration with in humidity so remaining left out is Rainy.


Iteration 3:


Now we need to identify what all nodes can come under oulook -> Rainy .
Sort out the master table to a child table which comprises only Rainy entry as done in Iteration 2.



Calculate yes and no
          No -2
          Yes - 3
          Entropy([3,2])    = 0.97095

          gain(Temp)   = 0.02095
         gain(windy) = 0.97095

Highest gain is for windy

therefore it comes under outlook ->rainy .




Now all the leaf is unique so no further iteration.So Temperature will not be taken .

Algorithm


1. Start
2. Get Input
3. Extract class Label col and find TotalEntropy
4. Associate attr with class label and calc Info gain for each attribute
5. Determine the attribute with highest gain
6. If entropy =0 go to step 7 else go to step 3
7. End


ID3 to C4.5


Only difference is we will be considering “Split Info” also. So Gain ratio of each attribute will be gain/split info.Other procedures are same.

ex.Split info = info([5,4,5]) = 5 sunny ,4 overcast and 5 rainy like wise.




Reference:


[1] K.P.Soman,Shyam Diwaker,V.Ajay(2006),Insight into Data Mining Theory And Practice,Prentice-Hall of India Private Limited, New Delhi

3 comments:

  1. Very informative ... High Five

    ReplyDelete
  2. Hi! I understand this is kind of off-topic but I had to ask. Does managing a well-established blog like yours require a lot of work? I am completely new to operating a blog however I do write in my diary daily. I’d like to start a blog so I can share my personal experience and views online. Please let me know if you have any kind of suggestions or tips for new aspiring blog owners. Thankyou!

    What your stating is absolutely genuine. I know that everyone ought to say the identical factor, but I just feel that you set it in a way that absolutely everyone can realize. I also adore the photographs you set in here. They fit so nicely with what youre hoping to say. Im guaranteed youll attain so numerous people today with what youve got to say.

    These moles may possibly be irregular in size and color and that is what can make them this type of wellness danger. When you have been born with this particular problem you might also be more likely to develop Melanoma and so you might have to get the required precautions with regards to protecting your pores and skin and your well being.

    This is such a great post, and was thinking much the same myself. It’s certainly an opinion I agree with.

    Enjoyed this article. I believe that the writer took an rationale perspective and made some pivotale ideas.

    Aw, it was an extremely good post. In notion I must place in writing such as this moreover – spending time and actual effort to make a really good article… but so what can I say… I procrastinate alot and no means apparently go completed.

    You need to experience a tournament for just one of the most effective blogs on the web. I’ll recommend this page!

    Thank you for yet another great informative article, I’m a loyal reader to this blog and I can’t stress enough how much valuable information I’ve learned from reading your content. I really appreciate all the hard work you put into this great site.

    When I originally commented I clicked the -Notify me when new comments are added- checkbox and now when a comment is added I buy four emails concentrating on the same comment. Perhaps there is in any manner you can get rid of me from that service? Thanks!

    ReplyDelete