Decision Tree ExamplesTraining dataDecision Tree 1, Root: studentSlide Number 4Slide Number 5Slide Number 6Slide Number 7Slide Number 8Tree 1 Classifcation rules (Predicate form for testing) Decision Tree 2: Root IncomeSlide Number 11Slide Number 12Slide Number 13Slide Number 14Slide Number 15Tree 2 Classifcation rules (Predicate form for testing) Formulas for information gainCalculations of information gain for Tree 1, Root: StudentCalculations of information gain for Tree 1, Income(Left) nodeCalculations of information gain for Tree 1, Income(Right) nodeCalculations of information gain for Tree 1, age(1) nodeCalculations of information gain for Tree 1, CR(Left) nodeCalculations of information gain for Tree 1, CR(right) nodeCalculations of information gain for Tree 1, age(2) nodeCalculations of information gain for Tree 1, age(3) nodeCalculations of information gain for Tree 1, age(4) nodeInformation gain measure Slide Number 28Tree 3: root student plus majority voting at any node Heuristics: use majority voting at any chosen NODE of the treeSlide Number 30Tree 3 (majority voting) rules and their accuracy (Predicate form for testing) Slide Number 32Slide Number 33Slide Number 34Slide Number 35Tree 4: Classifcation rules and their accuracy (Predicate form for testing) Training data plus (red) test dataTree1 classifcation rules (Predicate form for testing)Book classification rules Book Rules accuracyTree 2 Classifcation rules (Predicate form for testing) Predictive accuracy for (red) test dataTree 3 (majority voting) rules and their accuracyDecision Tree ExamplesProfessor Anita WasilewskaComputer Science DepartmentStony Brook University, NYTraining datarec Age Income Student Credit_rating Buys_computerr1 <=30 High No Fair Nor2 <=30 High No Excellent Nor3 31…40 High No Fair Yesr4 >40 Medium No Fair Yesr5 >40 Low Yes Fair Yesr6 >40 Low Yes Excellent Nor7 31…40 Low Yes Excellent Yesr8 <=30 Medium No Fair Nor9 <=30 Low Yes Fair Yesr10 >40 Medium Yes Fair Yesr11 <-=30 Medium Yes Excellent Yesr12 31…40 Medium No Excellent Yesr13 31…40 High Yes Fair Yesr14 >40 Medium No Excellent NoDecision Tree 1, Root: studentstudentNo YesAge income CR Class>40 Low Fair Yes>40 Low excellent No31…40 Low Excellent Yes<=30 Low Fair Yes>40 Medium Fair Yes<=30 Medium Excellent Yes31…40 high fair yesAge income CR Class<=30 High Fair No<=30 High Excellent No30…40 High Fair Yes>40 Medium Fair Yes<=30 Medium Fair No31…40 Medium Excellent Yes>40 Medium Excellent noDecision Tree 1: income (L) and income (R)studentincomeincomeAge CR class<=30 Fair No<=30 Excellent No31..40 Fair YesAge CR Class>40 Fair Yes<=30 Fair No31..40 Excellent Yes>40 Excellent noAge CR class>40 Fair yes>40 Excellent No31…40 Excellent Yes<=30 fair yesNo YesHigh medium low medium highAge CR Class31…40 Fair yesAge CR class>40 Fair Yes<=30 Excellent YesstudentincomeincomeAge CR class<=30 Fair No<=30 Excellent No31..40 Fair YesAge CR Class>40 Fair Yes<=30 Fair No31..40 Excellent Yes>40 Excellent noAge CR class>40 Fair yes>40 Excellent No31…40 Excellent Yes<=30 fair yesNo YesHigh medium low medium highYesYesDecision Tree 1: next stepstudentIncomeIncomeNo YesHigh Medium Low Medium HighageCR ClassFair NoExcellent NoCr Classfair yesAge Class>40 No31…40 YesAge Class>40 Yes<=30 YesCRAge Class31…40 Yes>40 NoCRAge Class>40 Yes<=30 No<=30 31…40 Fair Excellent Fair ExcellentYesYesDecision Tree 1 : next stepstudentIncomeIncomeNo YesHigh Medium Low Medium HighageAge Class>40 No31...40 YesCRAge Class31…40 Yes>40 NoCRAge Class>40 Yes<=30 No<=30 31…40 Fair Excellent Fair ExcellentYesYesNoYesYesDecision Tree 1: next stepstudentIncomeIncomeNo YesHigh Medium Low Medium HighageCRCR<=30 31…40 Fair Excellent Fair ExcellentYesYesNoYesYesYesNoYes NoAgeAge AgeYes No>40 31...40 31…40 >40>40 <=30Decision Tree 1 : last stepTree 1 Classifcation rules (Predicate form for testing)• 1. student(x,no)^income(x,high)^age(x,<=30) => buys_computer(x,no)• 2. student(x,no)^income(x,high)^age(x,31…40) => buys_computer(x,yes)• 3. student(x,no)^income(medium)^CRx,fair)^age(x,>40) => buys_computer(x,yes)• 4. student(x,no)^income(x,medium)^CR(x,fair)^age(x,b<=30) => buys_computer(x,no)• 5. student(x,no)^income(x,medium)^CRx,(excellent)^age(x,>40) => buys_computer(x,no)• 6. student(x,no)^income(x,medium)^CR(x,excellent)^age(x,31..40) => buys_computer(x,yes)• 7. student(x,yes)^income(low)^CR(x,fair) => buys_computer(x,yes)• 8. student(x,yes)^income(x,low)^CR(x,excellent)^age(x,b31..40) => buys_computer(x,yes)• 9. student(x,yes)^income(x,low)^CR(x,excellent)^age(x,>40) => buys_computer(x,no)• 10. student(x,yes)^income(x,medium)=> buys_computer(x,yes)• 11. student(x,yes)^income(x,high)=> buys_computer(x,yes)Decision Tree 2: Root IncomeIncomeAge Student CR Class<=30 No Fair No<=30 No Excellent No31…40 No Fair Yes31…40 Yes Fair yesHigh Medium LowAge Student CR Class>40 No Fair Yes<=30 No Fair No>40 Yes Fair Yes<=30 Yes Excellent yes31…40 No Excellent yes>40 No Excellent noAge Student CR Class>40 No Fair Yes>40 Yes Excellent No31…40 Yes Excellent Yes<=30 Yes Fair yesAge<=30 31…40Student CR Classno Fair Nono Excellent NoStudent CR ClassNo Fair YesYes Fair yesStudentNo YesAge CR Class>40 Fair Yes<=30 Fair No31…40 Excellent Yes>40 Excellent NoAge CR Class>40 Fair Yes<=30 Excellent YesCRFair excellentAge Student Class>40 No Yes<=30 Yes YesAge Student Class>40 Yes No31…40 Yes YesHigh Medium LowIncomeDecision Tree 2 : next stepAge<=30 31…40StudentNo YesAge CR Class>40 Fair Yes<=30 Fair No31…40 Excellent Yes>40 Excellent NoCRFair excellentAge Student Class>40 Yes No31…40 Yes YesHigh Medium