# U of M CS 5541 - Decision Trees (32 pages)

Previewing pages 1, 2, 15, 16, 31, 32 of 32 page document
View Full Document

## Decision Trees

Previewing pages 1, 2, 15, 16, 31, 32 of actual document.

View Full Document
View Full Document

## Decision Trees

75 views

Pages:
32
School:
University of Minnesota- Twin Cities
Course:
Cs 5541 - Artificial Intelligence
##### Artificial Intelligence Documents
• 20 pages

• 19 pages

• 3 pages

• 5 pages

• 15 pages

• 16 pages

• 7 pages

• 34 pages

• 29 pages

• 22 pages

Unformatted text preview:

Decision Trees Decision tree representation ID3 learning algorithm Entropy Entropy Information gain Overfitting CS 5541 Chapter 3 Decision Tree Learning 1 Another Example Problem Positive Examples Negative Examples CS 5751 Machine Learning Chapter 3 Decision Tree Learning 2 A Decision Tree Type Car SUV Minivan Doors 2 CS 5751 Machine Learning 4 Tires Blackwall Chapter 3 Decision Tree Learning Whitewall 3 Decision Trees Decision tree representation Each internal node tests an attribute Each branch corresponds to an attribute value Each leaf node assigns a classification How would you represent XOR A B C D E M of N CS 5751 Machine Learning Chapter 3 Decision Tree Learning 4 When to Consider Decision Trees Instances describable by attribute value pairs Target function is discrete valued Disjunctive hypothesis may be required Possibly noisy training data Examples Equipment or medical diagnosis Credit risk analysis Modeling calendar scheduling preferences CS 5751 Machine Learning Chapter 3 Decision Tree Learning 5 Top Down Induction of Decision Trees Main loop 1 A the best decision attribute for next node 2 Assign A as decision attribute for node 3 For each value of A create descendant of node 4 Divide training examples among child nodes 5 If training examples perfectly classified STOP El iterate Else i over new leaf l f nodes d 29 35 29 35 A1 A2 Whichh attribute Whi ib is best 21 5 21 5 CS 5751 Machine Learning 8 30 8 30 Chapter 3 Decision Tree Learning 18 33 11 2 18 33 11 2 6 Entropy S sample of training examples 1 p proportion of Entropy S S 0 8 positive examples in S 06 0 6 p proportion of negative examples in S 0 4 Entropy measures the 0 2 impurity of S 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 1 0 Probability CS 5751 Machine Learning Entropy S p log l 2 p p log l 2 p Chapter 3 Decision Tree Learning 7 Entropy Entropy S expected number of bits need to encode class or of randomlyy drawn member of S using an optimal shortest length code Why Information theory optimal length code assigns log2p bits to message having probability p S expected So t d number b off bit bits to t encode d or off random d member of S pp log 2 p p log 2 p Entropy S pp log 2 p p log 2 p CS 5751 Machine Learning Chapter 3 Decision Tree Learning 8 Information Gain Gain S A expected reduction in entropy due to sortingg on A Gain S A Entropy S Sv v Values A S Entropy S v 29 29 35 35 0 994 log 2 log 2 64 64 64 64 5 5 21 21 Entropy 21 5 log 2 log 2 0 706 26 26 26 26 Entropy 8 30 0 742 26 Gain S A1 0 994 Entropy 21 5 64 38 Entropy 8 30 0 266 64 Entropy 18 33 0 937 Entropy 11 2 0 619 Gain S A2 0 121 Entropy 29 35 29 35 A1 21 5 8 30 A2 18 33 11 2 18 33 11 2 CS 5751 Machine Learning Chapter 3 Decision Tree Learning 9 Car Examples Color Red ue Blue Green Red Green Green Blue Blue Red Blue Green Red Green Green Type SUV Minivan a Car Minivan Car SUV SUV Car SUV Car SUV Car SUV Minivan CS 5751 Machine Learning Doors 2 4 4 4 2 4 2 2 2 4 4 2 2 4 Tires Whitewall Whitewall te a Whitewall Blackwall Blackwall Blackwall Blackwall Whitewall Blackwall Blackwall Whitewall Blackwall Blackwall Whitewall Chapter 3 Decision Tree Learning Class 10 Selecting Root Attribute M Minivn r Ca V Blue SU Re S 5 9 E 0 940 Type en re G d S 5 9 E 0 940 Color Gain S Color 940 4 14 1 0 4 14 811 6 14 918 0 029 CS 5751 Machine Learning Gain S Type 940 940 5 14 971 5 14 971 3 14 0 6 14 0 918 6 14 0 918 0 200 Chapter 3 Decision Tree Learning 11 Selecting Root Attribute cont S 5 9 E 0 940 Tires ac kw 2 Bl 4 al l W hi te w al l S 5 9 E 0 940 Doors Gain S Doors G i S D 940 7 14 0 985 7 14 0 592 0 152 Gain S Type G i S T 940 6 14 1 0 8 14 811 0 048 Best attribute Type Gain 0 200 CS 5751 Machine Learning Chapter 3 Decision Tree Learning 12 Selecting Next Attribute Minivn n Ca V SCar SU r Type SSUV S 3 2 S 0 3 E 0 971 E 0 0 CS 5751 Machine Learning S 2 4 E 0 918 Gain SCar Color 971 1 5 0 0 2 5 1 0 2 5 1 0 171 971 1 5 0 0 2 5 1 0 2 5 1 0 171 Gain SCar Doors 971 3 5 0 0 2 5 0 0 971 Gain SCar Tires 971 2 5 1 0 3 5 918 020 Gain SSUV Color 918 2 6 1 0 1 6 0 0 3 6 918 126 Gain SSUV Doors 918 4 6 811 2 6 1 0 044 Gain SSUV Tires 918 2 6 0 0 4 6 0 0 918 2 6 0 0 4 6 0 0 918 Chapter 3 Decision Tree Learning 13 Resulting Tree Type Car SUV Minivan Doors 2 CS 5751 Machine Learning 4 Tires Blackwall Chapter 3 Decision Tree Learning Whitewall 14 Hypothesis Space Search by ID3 A2 A1 A2 A1 A2 A3 CS 5751 Machine Learning Chapter 3 Decision Tree Learning 15 Hypothesis Space Search by ID3 Hypothesis space is complete Target g function is in there but will we find it Outputs a single hypothesis which one Cannot play 20 questions No back tracing Local minima possible Statistically based search choices Robust to noisy data Inductive bias approximately prefer shortest tree CS 5751 Machine Learning Chapter 3 Decision Tree Learning 16 Inductive Bias in ID3 Note H is the power set of instances X Unbiased Not really trees and for those with high Preference for short trees information gain attributes near the root Bias is a preference for some hypotheses rather than a restriction of hypothesis space H Occam s razor pprefer the shortest hypothesis yp that fits the data CS 5751 Machine Learning Chapter 3 Decision Tree Learning 17 Occam s Razor Why prefer short hypotheses Argument in favor Fewer short hypotheses than long hypotheses short hyp that fits data unlikely to be coincidence long hyp that fits data more likely to be coincidence Argument opposed There are many ways to define small sets of hypotheses e g all trees with a prime number of nodes that use attributes tt ib t beginning b i i with ith Z What is so special about small sets based on size of yp hypothesis CS 5751 Machine Learning Chapter 3 Decision Tree Learning 18 Overfitting in Decision Trees …

View Full Document

Unlocking...