Pr(DIS,)=Pr(w:w2,A,waIS,)=Pr(w,IS Independence Assumption 1 Naive Bayes Classifier argPr(S,7Pm(wlS） 2.Bayesian Network (without independence assumption) SPRINKLER RAIN RAIN T T SPRINKLER RAIN 0.4 0.6 0.20.8 T 0.01 0.99 GRASS WET GRASS WET SPRINKLER RAIN F F F 0.0 1.0 T 0.8 0.2 T F 0.9 0.1 人 人 0.99 0.01
k i D Sj w w wk Sj wi Sj Pr( | ) Pr( , , , | ) Pr( | ) 1 2 Independence Assumption k i j i j j argmaxPr(S ) Pr(w | S ) 1、Naïve Bayes Classifier 2、Bayesian Network (without independence assumption)
3.Decision Tree categorical categorical continuous class Example of a Decision Tree Splitting Attributes Tid Refund Marital Taxable Status Income Cheat Yes Single 125K No 2 No Married 100K No Refund Yes No 3 No Single 70K No 4 Yes Married 120K No NO MarSt 5 No Divorced 95K Yes Single,Divorced Married 6 No Married 60K No 7 Yes Divorced 220K No Taxlnc NO 8 No Single 85K Yes <80K > 80K 9 No Married 75K No NO YES 10 No Single 90K Yes Training Data Model:Decision Tree
Example of a Decision Tree Tid Refund Marital Status Taxable Income Cheat 1 Yes Single 125K No 2 No Married 100K No 3 No Single 70K No 4 Yes Married 120K No 5 No Divorced 95K Yes 6 No Married 60K No 7 Yes Divorced 220K No 8 No Single 85K Yes 9 No Married 75K No 10 No Single 90K Yes 10 Refund MarSt TaxInc NO YES NO NO Yes No Single, Divorced Married < 80K > 80K Splitting Attributes Training Data Model: Decision Tree 3. Decision Tree
Decision Tree Classification Task Tree Tid Attrib1 Attrib2 Attrib3 Class Yes Large 125K No Induction No Medium 100K No algorithm No Small 70K No Yes Medium 120K No Induction No Large 95K Yes 6 No Medium 60K No Yes Large 220K No Learn No Small 85K Yes Model No Medium 75K No 10 No Small 90K Yes Training Set Model Apply Decision Tree Model Tid Attrib1 Attrib2 Attrib3 Class 1 No Small 55K 12 Yes Medium 80K 13 Yes Large 110K Deduction 14 No Small 95K 15 No Large 67K ? Test Set
Decision Tree Classification Task Apply Model Induction Deduction Learn Model Model Tid 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 Test Set Tree Induction algorithm Training Set Decision Tree
Apply Model to Test Data Test Data Start from the root of tree. Refund Marital Taxable Status Income Cheat No Married 80K Refund Yes No NO MarSt Single,Divorced Married Taxlnc NO <80K >80K NO YES
Apply Model to Test Data Refund MarSt TaxInc NO YES NO NO Yes No Single, Divorced Married < 80K > 80K Refund Marital Status Taxable Income Cheat No Married 80K ? 10 Test Data Start from the root of tree
Apply Model to Test Data Test Data Refund Marital Taxable Status Income Cheat No Married 80K Refund Yes No NO MarSt Single,Divorced Married Taxlnc NO <80K >80K NO YES
Apply Model to Test Data Refund MarSt TaxInc NO YES NO NO Yes No Single, Divorced Married < 80K > 80K Refund Marital Status Taxable Income Cheat No Married 80K ? 10 Test Data