数据挖掘导论分类基本概念决策树与模型评估PPT学习教案

1、会计学1数据挖掘导论分类基本概念决策树与模数据挖掘导论分类基本概念决策树与模型评估型评估第1页/共91页第2页/共91页第3页/共91页第4页/共91页第5页/共91页第6页/共91页n：nBPBP算法算法, ,模型表示是前向反馈神经模型表示是前向反馈神经网络模型网络模型n4.4.粗糙集粗糙集(rough set)(rough set)知识表示是知识表示是产生式规则产生式规则第7页/共91页categoricalcategoricalcontinuousclassRefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KSplitti

2、ng Attributes训练数据模型: 决策树第8页/共91页TidRefundMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10categoricalcategoricalcontinuousclassMarStRefundTaxIncYESNONONOYesN

3、oMarried Single, Divorced 80K第9页/共91页第10页/共91页第11页/共91页Decision Tree第12页/共91页categoricalcategoricalcontinuousclassRefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KSplitting Attributes训练数据模型: 决策树第13页/共91页RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KRefund Marital Status Taxabl

4、e Income Cheat No Married 80K ? 10 测试数据Start from the root of tree.第14页/共91页RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KRefund Marital Status Taxable Income Cheat No Married 80K ? 10 测试数据第15页/共91页RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KRefund Marital Status Taxable

5、Income Cheat No Married 80K ? 10 测试数据第16页/共91页RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KRefund Marital Status Taxable Income Cheat No Married 80K ? 10 测试数据第17页/共91页RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KRefund Marital Status Taxable Income Cheat No Married 80K ?

6、10 测试数据第18页/共91页RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KRefund Marital Status Taxable Income Cheat No Married 80K ? 10 测试数据Assign Cheat to “No”第19页/共91页Decision Tree第20页/共91页第21页/共91页Dt?第22页/共91页Dont CheatRefundDont CheatDont CheatYesNoRefundDont CheatYesNoMaritalStatusDont CheatC

7、heatSingle,DivorcedMarriedTaxableIncomeDont Cheat= 80KRefundDont CheatYesNoMaritalStatusDont CheatCheatSingle,DivorcedMarried第23页/共91页第24页/共91页第25页/共91页第26页/共91页CarTypeFamilySportsLuxuryCarTypeFamily, LuxurySportsCarTypeSports, LuxuryFamilyORCarTypeFamily, SportsLuxury 第27页/共91页SizeSmallMediumLargeS

8、izeMedium, LargeSmallSizeSmall, MediumLargeORSizeSmall, LargeMedium第28页/共91页第29页/共91页第30页/共91页第31页/共91页在划分前: 10 个记录 class 0, 10 个记录 class 1第32页/共91页不纯性大不纯性小第33页/共91页B?YesNoNode N3Node N4A?YesNoNode N1Node N2划分前:M0M1M2M3M4M12M34Gain = M0 M12 vs M0 M34第34页/共91页第35页/共91页jtjptGINI2)|(1)(C10C26Gini=0.000

9、C12C24Gini=0.444C13C23Gini=0.500C11C25Gini=0.278第36页/共91页C1 0 C2 6 C1 2 C2 4 C1 1 C2 5 P(C1) = 0/6 = 0 P(C2) = 6/6 = 1Gini = 1 P(C1)2 P(C2)2 = 1 0 1 = 0 jtjptGINI2)|(1)(P(C1) = 1/6 P(C2) = 5/6Gini = 1 (1/6)2 (5/6)2 = 0.278P(C1) = 2/6 P(C2) = 4/6Gini = 1 (2/6)2 (4/6)2 = 0.444第37页/共91页kiisplitiGINInnG

10、INI1)(第38页/共91页l对于二元属性，结点被划分成两个部分l得到的GINI值越小，这种划分越可行.B?YesNoNode N1Node N2 Parent C1 6 C2 6 Gini = 0.500 N1 N2 C1 5 1 C2 2 4 Gini=0.333 Gini(N1) = 1 (5/6)2 (2/6)2 = 0.194 Gini(N2) = 1 (1/6)2 (4/6)2 = 0.528Gini split= 7/12 * 0.194 + 5/12 * 0.528= 0.333第39页/共91页CarTypeSports,LuxuryFamilyC131C224Gini0.

11、400CarTypeSportsFamily,LuxuryC122C215Gini0.419CarTypeFamily Sports LuxuryC1121C2411Gini0.393Multi-way splitTwo-way split (find best partition of values)第40页/共91页第41页/共91页划分点排序后的值第42页/共91页 , , ( )Xq xkx的自信息定义为 因 I()logkkxq 0,1kq 故I()0kx自信息反映了事件 发生所需要的信息量。 值越大说明需要越多的信息才能确定事件 的发生，其随机性也越大，而当 发生时所携带的信息量也

12、越大。反过来， 值越小，需要较少信息量就能确定 的发生，即事件 随机性较小。当其发生时所携信息量就少。 是对不确定性大小的一种刻画 kxI()kxkxkxI()kxkxI()kx熵-定义第43页/共91页 , , ( )Xq xE(I(x)( ) ( )( )log ( )xxq x I xq xq x称为随机变量X的平均自信息，又称X的信息熵或熵记为H(x) 第44页/共91页熵-定义第45页/共91页jtjptjptEntropy)|(log)|()(第46页/共91页C1 0 C2 6 C1 2 C2 4 C1 1 C2 5 P(C1) = 0/6 = 0 P(C2) = 6/6 = 1

13、Entropy = 0 log 0 1 log 1 = 0 0 = 0 P(C1) = 1/6 P(C2) = 5/6Entropy = (1/6) log2 (1/6) (5/6) log2 (1/6) = 0.65P(C1) = 2/6 P(C2) = 4/6Entropy = (2/6) log2 (2/6) (4/6) log2 (4/6) = 0.92jtjptjptEntropy)|(log)|()(2第47页/共91页kiisplitiEntropynnpEntropyGAIN1)()(第48页/共91页SplitINFOGAINGainRATIOSplitsplitkiiinn

14、nnSplitINFO1log第49页/共91页)|(max1)(tiPtErrori第50页/共91页C1 0 C2 6 C1 2 C2 4 C1 1 C2 5 P(C1) = 0/6 = 0 P(C2) = 6/6 = 1Error = 1 max (0, 1) = 1 1 = 0 P(C1) = 1/6 P(C2) = 5/6Error = 1 max (1/6, 5/6) = 1 5/6 = 1/6P(C1) = 2/6 P(C2) = 4/6Error = 1 max (2/6, 4/6) = 1 4/6 = 1/3)|(max1)(tiPtErrori第51页/共91页二元分类问题

15、:第52页/共91页第53页/共91页第54页/共91页第55页/共91页第56页/共91页第57页/共91页第58页/共91页PQRS0101QS001 Same subtree appears in multiple branches第59页/共91页 第60页/共91页x + y 1Class = + Class = 第61页/共91页情况成为模型过分拟合第62页/共91页第63页/共91页过分拟合第64页/共91页第65页/共91页第66页/共91页噪声导致决策边界的改变第67页/共91页第68页/共91页第69页/共91页第70页/共91页第71页/共91页第72页/共91页第73页

16、/共91页第74页/共91页第75页/共91页tkiikiiiNTQTetntQteTe)()()()()()( 11第76页/共91页第77页/共91页第78页/共91页ABA?B?C?1001YesNoB1B2C1C2XyX11X20X30X41Xn1XyX1?X2?X3?X4?Xn?第79页/共91页第80页/共91页n阈值太高，导致拟合不足n阈值太低，导致不能充分解决过分拟合的问题。第81页/共91页第82页/共91页第83页/共91页PREDICTED CLASSACTUALCLASSClass=YesClass=NoClass=Yesa(TP)b(FN)Class=Noc(FP)d

17、(TN)FNFPTNTPTNTPdcbada Accuracy ）准确率（第84页/共91页第85页/共91页TPTPRFPFPRFNFNRTPFNPrecision (p) Recall (r)22*F1F-measure (F)2*TPFNTNTNRTNFPTNFPTPTPFPTPTPFNrpTPrpTPTPFN真正率真负率假正率假负率精度召回率度量第86页/共91页第87页/共91页第88页/共91页l没有哪个模型能够压倒对方lFRR0.36, M2较好lROC曲线下方的面积l理想情况: 面积= 1l随机猜测: 面积 = 0.5第89页/共91页Class + - + - - - + - + +