1Machine LearningMachine Learning1010--701/15701/15--781, Spring 2008781, Spring 2008Decision TreesDecision TreesEric XingEric XingLecture 6, February 4, 2008Reading: Chap. 1.6, CB & Chap 3, TMLearning non-linear functionsf: X Æ Yz X (vector of) continuous and/or discrete varsz Y discrete varsz Linear separator z f might be non-linear functionThe XOR gateSpeech recognition2A hypothesis for TaxFraudz Input: a vector of attributes z X=[Refund,MarSt,TaxInc]zOutput: z Y= Cheating or NotzH as a procedure:z Each internal node: test one attribute Xiz Each branch from a node: selects one value for Xiz Each leaf node: predict YRefundMarStTaxIncYESNONONOYes NoMarriedSingle, Divorced< 80K > 80KApply Model to Query DataRefundMarStTaxIncYESNONONOYes NoMarriedSingle, Divorced< 80K > 80KRefund Marital Status Taxable Income Cheat No Married 80K ? 10 Query DataStart from the root of tree.3Apply Model to Test DataRefundMarStTaxIncYESNONONOYes NoMarriedSingle, Divorced< 80K > 80KRefund Marital Status Taxable Income Cheat No Married 80K ? 10 Query DataApply Model to Test DataRefundMarStTaxIncYESNONONOYes NoMarriedSingle, Divorced< 80K > 80KRefund Marital Status Taxable Income Cheat No Married 80K ? 10 Query Data4Apply Model to Test DataRefundMarStTaxIncYESNONONOYes NoMarriedSingle, Divorced< 80K > 80KRefund Marital Status Taxable Income Cheat No Married 80K ? 10 Query DataApply Model to Test DataRefundMarStTaxIncYESNONONOYes NoMarried Single, Divorced< 80K > 80KRefund Marital Status Taxable Income Cheat No Married 80K ? 10 Query Data5Apply Model to Test DataRefundMarStTaxIncYESNONONOYes NoMarried Single, Divorced< 80K > 80KRefund Marital Status Taxable Income Cheat No Married 80K ? 10 Query DataAssign Cheat to “No”A Tree to Predict C-Section Riskz Learned from medical records of 1000 wonmanNegative examples are C-sections6Expressivenessz Decision trees can express any function of the input attributes.z E.g., for Boolean functions, truth table row → path to leaf:z Trivially, there is a consistent decision tree for any training set with one path to leaf for each example (unless f nondeterministic in x) but it probably won't generalize to new examplesz Prefer to find more compact decision treesHypothesis spacesHow many distinct decision trees with n Boolean attributes?= number of Boolean functions= number of distinct truth tables with 2nrows = 22nzE.g., with 6 Boolean attributes, there are 18,446,744,073,709,551,616 trees7Hypothesis spacesHow many distinct decision trees with n Boolean attributes?= number of Boolean functions= number of distinct truth tables with 2nrows = 22nzE.g., with 6 Boolean attributes, there are 18,446,744,073,709,551,616 treesHow many purely conjunctive hypotheses (e.g., Hungry ∧¬Rain)?z Each attribute can be in (positive), in (negative), or out⇒ 3ndistinct conjunctive hypothesesz More expressive hypothesis spacez increases chance that target function can be expressedz increases number of hypotheses consistent with training set⇒ may get worse predictionsDecision Tree LearningApply ModelLearn ModelTid Attrib1 Attrib2 Attrib3 Class 1 Yes Large 125K No 2 No Medium 100K No 3 No Small 70K No 4 Yes Medium 120K No 5 No Large 95K Yes 6 No Medium 60K No 7 Yes Large 220K No 8 No Small 85K Yes 9 No Medium 75K No 10 No Small 90K Yes 10 Tid Attrib1 Attrib2 Attrib3 Class 11 No Small 55K ? 12 Yes Medium 80K ? 13 Yes Large 110K ? 14 No Small 95K ? 15 No Large 67K ? 10 Decision Tree8Example of a Decision TreeTidRefund MaritalStatusTaxableIncomeCheat1 Yes Single 125KNo2 No Married 100KNo3 No Single 70KNo4 Yes Married 120KNo5 No Divorced 95KYes6 No Married 60KNo7 Yes Divorced 220KNo8 No Single 85KYes9 No Married 75KNo10 No Single 90KYes10categoricalcategoricalcontinuousclassRefundMarStTaxIncYESNONONOYes NoMarriedSingle, Divorced< 80K > 80KSplitting AttributesTraining DataModel: Decision TreeAnother Example of Decision TreeMarStRefundTaxIncYESNONONOYesNoMarriedSingle, Divorced< 80K > 80KThere could be more than one tree that fits the same data!TidRefund MaritalStatusTaxableIncomeCheat1 Yes Single 125KNo2 No Married 100KNo3 No Single 70KNo4 Yes Married 120KNo5 No Divorced 95KYes6 No Married 60KNo7 Yes Divorced 220KNo8 No Single 85KYes9 No Married 75KNo10 No Single 90KYes10categoricalcategoricalcontinuousclassTraining Data9Top-Down Induction of DTTree Inductionz Greedy strategy.z Split the records based on an attribute test that optimizes certain criterion.zIssuesz Determine how to split the recordsz How to specify the attribute test condition?z How to determine the best split?z Determine when to stop splitting10Tree Inductionz Greedy strategy.z Split the records based on an attribute test that optimizes certain criterion.zIssuesz Determine how to split the recordsz How to specify the attribute test condition?z How to determine the best split?z Determine when to stop splittingHow to Specify Test Condition?z Depends on attribute typesz Nominalz Ordinalz ContinuouszDepends on number of ways to splitz 2-way splitz Multi-way split11CarTypeFamilySportsLuxuryCarType{Family, Luxury}{Sports}CarType{Sports, Luxury}{Family}ORz Multi-way split: Use as many partitions as distinct values. z Binary split: Divides values into two subsets. Need to find optimal partitioning.Splitting Based on Nominal AttributesSizeSmallMediumLargeSize{Medium, Large}{Small}Size{Small, Medium}{Large}ORSize{Small, Large}{Medium}Splitting Based on Ordinal Attributesz Multi-way split: Use as many partitions as distinct values. z Binary split: Divides values into two subsets. Need to find optimal partitioning.z What about this split?12Splitting Based on Continuous Attributesz Different ways of handlingz Discretization to form an ordinal categorical attributez Static – discretize once at the beginningz Dynamic – ranges can be found by equal interval bucketing, equal frequency bucketing (percentiles), or clustering.z Binary Decision: (A < v) or (A ≥ v)z consider all possible splits and finds the best cutz can be more compute intensiveSplitting Based on Continuous Attributes13Tree Inductionz Greedy strategy.z Split the records based on an attribute test that optimizes certain criterion.zIssuesz Determine how to split the recordsz How to specify the attribute test condition?z How to determine the best split?z Determine when to stop splittingHow to determine the Best Splitz Idea: a good attribute splits the examples into subsets that are(ideally)
View Full Document
Unlocking...