數據挖掘導論Pang-ningTan,MichaelStieinbach,andVipinKumar著PearsonEducationLTD.范明等譯人民郵電出版社數據挖掘導論Pang-ningTan,MichaelS1第4章分類：基本概念、決策樹

與模型評估引言:預備知識,解決分類問題的一般方法決策樹歸納模型的過分擬合評估分類器的性能第4章分類：基本概念、決策樹

與模型評估引言:預備知識,2引言引言308八月2023數據挖掘導論4分類:定義Givenacollectionofrecords(trainingset)Eachrecordcontainsasetofattributes,oneoftheattributesistheclass.Findamodelforclassattributeasafunctionofthevaluesofotherattributes.Goal:previouslyunseenrecordsshouldbeassignedaclassasaccuratelyaspossible.Atestsetisusedtodeterminetheaccuracyofthemodel.Usually,thegivendatasetisdividedintotrainingandtestsets,withtrainingsetusedtobuildthemodelandtestsetusedtovalidateit01八月2023數據挖掘導論4分類:定義Givena408八月2023數據挖掘導論5分類:解釋01八月2023數據挖掘導論5分類:解釋508八月2023數據挖掘導論6分類任務的例子腫瘤：Predictingtumorcellsasbenignormalignant信用卡交易：Classifyingcreditcardtransactions

aslegitimateorfraudulent蛋白質結構：Classifyingsecondarystructuresofprotein

asalpha-helix,beta-sheet,orrandomcoil新聞：Categorizingnewsstoriesasfinance,

weather,entertainment,sports,etc01八月2023數據挖掘導論6分類任務的例子腫瘤：Pre608八月2023數據挖掘導論7分類:技術DecisionTreebasedMethodsRule-basedMethodsMemorybasedreasoningNeuralNetworksNa?veBayesandBayesianBeliefNetworksSupportVectorMachines01八月2023數據挖掘導論7分類:技術Decision74.3決策樹歸納4.3決策樹歸納808八月2023數據挖掘導論901八月2023數據挖掘導論9908八月2023數據挖掘導論10決策樹:例子categoricalcategoricalcontinuousclassSplittingAttributesTrainingDataModel:DecisionTreeYESNONONOYesNoMarried

Single,Divorced<80K>80KRefundMarStTaxInc01八月2023數據挖掘導論10決策樹:例子categ1008八月2023數據挖掘導論11決策樹樹中包含三種結點根結點(rootnode):沒有入邊,有零條或多條出邊內部結點(internalnode):恰有一條入邊和兩條或多條出邊葉結點(leafnode)或終端結點(terminalnode):恰有一條入邊，但沒有出邊01八月2023數據挖掘導論11決策樹樹中包含三種結點1108八月2023數據挖掘導論12決策樹分類任務:應用模型DecisionTree01八月2023數據挖掘導論12決策樹分類任務:應用模1208八月2023數據挖掘導論13決策樹:使用模型TestDataStartfromtherootoftree.YESNONONOYesNoMarried

Single,Divorced<80K>80KRefundMarStTaxInc01八月2023數據挖掘導論13決策樹:使用模型Tes1308八月2023數據挖掘導論14決策樹:使用模型TestDataYESNONONOYesNoMarried

Single,Divorced<80K>80KRefundMarStTaxInc01八月2023數據挖掘導論14決策樹:使用模型Tes1408八月2023數據挖掘導論15決策樹:使用模型TestDataYESNONONOYesNoMarried

Single,Divorced<80K>80KRefundMarStTaxIncRefund

Marital

Status

Taxable

Income

Cheat

No

Married

80K

?

10

01八月2023數據挖掘導論15決策樹:使用模型Tes1508八月2023數據挖掘導論16決策樹:使用模型TestDataYESNONONOYesNoMarried

Single,Divorced<80K>80KRefundMarStTaxIncRefund

Marital

Status

Taxable

Income

Cheat

No

Married

80K

?

10

01八月2023數據挖掘導論16決策樹:使用模型Tes1608八月2023數據挖掘導論17決策樹:使用模型TestDataYESNONONOYesNoMarriedSingle,Divorced<80K>80KRefundMarStTaxIncRefund

Marital

Status

Taxable

Income

Cheat

No

Married

80K

?

10

01八月2023數據挖掘導論17決策樹:使用模型Tes1708八月2023數據挖掘導論18決策樹:使用模型TestDataYESNONONOYesNoMarriedSingle,Divorced<80K>80KRefundMarStTaxIncRefund

Marital

Status

Taxable

Income

Cheat

No

Married

80K

?

10

AssignCheatto“No”01八月2023數據挖掘導論18決策樹:使用模型Tes1808八月2023數據挖掘導論19決策樹分類任務:學習模型DecisionTree01八月2023數據挖掘導論19決策樹分類任務:學習模型1908八月2023數據挖掘導論20決策樹歸納ManyAlgorithms:Hunt’sAlgorithm(oneoftheearliest)CARTID3,C4.5SLIQ,SPRINT01八月2023數據挖掘導論20決策樹歸納ManyAl2008八月2023數據挖掘導論21Hunt算法的一般結構LetDt

bethesetoftrainingrecordsthatreachanodetGeneralProcedure:IfDt

containsrecordsthatbelongthesameclassyt,thentisaleafnodelabeledasytIfDt

isanemptyset,thentisaleafnodelabeledbythedefaultclass,ydIfDtcontainsrecordsthatbelongtomorethanoneclass,useanattributetesttosplitthedataintosmallersubsets.Recursivelyapplytheproceduretoeachsubset.01八月2023數據挖掘導論21Hunt算法的一般結構L2108八月2023數據挖掘導論22Hunt算法:例Don’tCheatRefundDon’tCheatDon’tCheatYesNoRefundDon’tCheatYesNoMaritalStatusDon’tCheatCheatSingle,DivorcedMarriedTaxableIncomeDon’tCheat<80K>=80KRefundDon’tCheatYesNoMaritalStatusDon’tCheatCheatSingle,DivorcedMarried01八月2023數據挖掘導論22Hunt算法:例Don2208八月2023數據挖掘導論23決策樹歸納Greedystrategy.Splittherecordsbasedonanattributetestthatoptimizescertaincriterion.IssuesDeterminehowtosplittherecordsHowtospecifytheattributetestcondition?Howtodeterminethebestsplit?DeterminewhentostopsplittingDiscussabovethreeissuesindetails01八月2023數據挖掘導論23決策樹歸納Greedy2308八月2023數據挖掘導論24如何指定屬性測試條件DependsonattributetypesNominalOrdinalContinuousDependsonnumberofwaystosplit2-waysplitMulti-waysplit01八月2023數據挖掘導論24如何指定屬性測試條件De2408八月2023數據挖掘導論25劃分:標稱屬性Multi-waysplit:Useasmanypartitionsasdistinctvalues.Binarysplit:Dividesvaluesintotwosubsets.Needtofindoptimalpartitionfromallpossiblepartitions.CarTypeFamilySportsLuxuryCarType{Sports,Luxury}{Family}CarType{Family,Luxury}{Sports}CarType{Sports,Family}{Luxury}01八月2023數據挖掘導論25劃分:標稱屬性Mult2508八月2023數據挖掘導論26劃分:序數屬性Multi-waysplit:Useasmanypartitionsasdistinctvalues.Binarysplit:Dividesvaluesintotwosubsets.Needtofindoptimalpartitionfromallpossiblepartitions.Whataboutthissplit?SizeSmallMediumLargeSize{Medium,

Large}{Small}Size{Small,Medium}{Large}Size{Small,Large}{Medium}01八月2023數據挖掘導論26劃分:序數屬性Mult2608八月2023數據挖掘導論27劃分:連續(xù)屬性DifferentwaysofhandlingDiscretizationtoformanordinalcategoricalattributeStatic–discretizeonceatthebeginningCanbetreatedasordinalattributeDynamic–rangescanbefoundbyequalintervalbucketing,equalfrequencybucketing(percentiles),orclustering.BinaryDecision:(A<v)or(Av)considerallpossiblesplitsandfindsthebestcutcanbemorecomputeintensive01八月2023數據挖掘導論27劃分:連續(xù)屬性Diff2708八月2023數據挖掘導論28劃分:連續(xù)屬性(續(xù))TaxableIncome>97K?YesNo(ii)BinarysplitTaxableIncome?(i)Multi-waysplit<10K[10K,25K)[25K,50K)[50K,80K)>80K01八月2023數據挖掘導論28劃分:連續(xù)屬性(續(xù))T2808八月2023數據挖掘導論29如何確定最佳劃分BeforeSplitting:10recordsofclass0,

10recordsofclass1Whichtestconditionisthebest?OwnCar?C0:6C1:4C0:4C1:6C0:1C1:3C0:8C1:0C0:1C1:7CarType?YesNoFamilySportsLuxuryC0:1C1:0C0:1C1:0C0:0C1:1StudentID?...c1c10c20C0:0C1:1...c1101八月2023數據挖掘導論29如何確定最佳劃分Befo2908八月2023數據挖掘導論30如何確定最佳劃分(續(xù))Greedyapproach:NodeswithhomogeneousclassdistributionarepreferredNeedameasureofnodeimpurityNon-homogeneous,HighdegreeofimpurityHomogeneous,Lowdegreeofimpurity01八月2023數據挖掘導論30如何確定最佳劃分(續(xù))G3008八月2023數據挖掘導論31結點的不純度結點的不純度設有c個類,t是結點,p(i|t)表示給定結點t中屬于類i的記錄所占的比例EntropyGiniIndexMisclassificationerror01八月2023數據挖掘導論31結點的不純度結點的不純度3108八月2023數據挖掘導論32標準比較不同的不純性度量是一致的對于二類問題01八月2023數據挖掘導論32標準比較不同的不純性度量3208八月2023數據挖掘導論33劃分的增益劃分的增益設結點parent上有N個記錄設結點parent被劃分成k部分,即parent有k個子女v1,…,vk設I(vj)是結點vj的不純度,則劃分的增益為其中,N(vj)是結點vj的記錄數,I(.)可以是entropy(.),Gini(.),error(.)等反映結點parent劃分為v1,…,vk后不純度的降低越大，越有利于分類信息增益(informationgain)當不純度用entropy度量時，稱為信息增益info(Gain)01八月2023數據挖掘導論33劃分的增益劃分的增益3308八月2023數據挖掘導論34如何確定最佳劃分(續(xù))基本思想如果采用二元劃分,則對非二元屬性確定最佳劃分對于分類和序數屬性,需要考慮所有可能對于連續(xù)屬性,如果不離散化,需要采用二元劃分如何確定最佳劃分點,見后面的例子屬性最佳劃分是不純度最低的劃分對每個屬性的最佳劃分,計算劃分增益結點的最佳劃分是劃分增益最大的屬性(最佳)劃分01八月2023數據挖掘導論34如何確定最佳劃分(續(xù))基3408八月2023數據挖掘導論35連續(xù)屬性的最佳劃分點確定最佳劃分點把屬性值由小到大排序v(1)

v(2)…

v(k)(取相鄰值的中點為劃分點:如果v(i)<v(i+1),則取(v(i)+v(i+1))/2為劃分點評估每個劃分點，選取不純度最低的劃分SplitPositionsSortedValuesCheatNoNoNoYesYesYesNoNoNoNoTaxableIncome60707585909510012012522055657280879297110122172230<=><=><=><=><=><=><=><=><=><=><=>Yes0303030312213030303030No0716253434343443526170Gini0.4000.3750.3430.4170.4000.3000.3430.3750.40001八月2023數據挖掘導論35連續(xù)屬性的最佳劃分點確定3508八月2023數據挖掘導論36連續(xù)屬性的最佳劃分點(續(xù))確定連續(xù)屬性的最佳劃分點的計算開銷可能很大需要計算k1個可能的劃分點產生的劃分的不純度減少待考察的劃分點方法如果v(i)<v(i+1),但是v(i)和v(i+1),是同類元組的取值,則最佳劃分點一定不在v(i)和v(i+1)之間.SplitPositionsSortedValuesCheatNoNoNoYesYesYesNoNoNoNoTaxableIncome60707585909510012012522055657280879297110122172230<=><=><=><=><=><=><=><=><=><=><=>Yes0303030312213030303030No0716253434343443526170Gini0.3430.30001八月2023數據挖掘導論36連續(xù)屬性的最佳劃分點(續(xù)3608八月2023數據挖掘導論37增益率熵和Gini指標等不純性度量往往有利于具有大量不同值的屬性一個極端的例子:顧客ID（如身份證號）導致最純的劃分，但無助于分類解決方案使用二元劃分使用增益率C0:1C1:0C0:1C1:0C0:0C1:1CostomerID?...c1c10c20C0:0C1:1...c1101八月2023數據挖掘導論37增益率熵和Gini指標等3708八月2023數據挖掘導論38增益率(續(xù))增益率是劃分增益與劃分信息的比GainRatio=/SplitInfo其中劃分信息SplitInfo劃分信息又稱劃分的熵用來克服信息增益的缺點C4.5采用增益率01八月2023數據挖掘導論38增益率(續(xù))增益率3808八月2023數據挖掘導論39停止條件StopexpandinganodewhenalltherecordsbelongtothesameclassStopexpandinganodewhenalltherecordshavesimilarattributevaluesStopexpandinganodewhenthereisnoattributeavailableEarlytermination(tobediscussedlater)01八月2023數據挖掘導論39停止條件Stopexp3908八月2023數據挖掘導論40其他問題：缺失屬性值如何讓處理缺失屬性值Missingvaluesaffectdecisiontreeconstructioninthreedifferentways:AffectshowimpuritymeasuresarecomputedAffectshowtodistributeinstancewithmissingvaluetochildnodesAffectshowatestinstancewithmissingvalueisclassified01八月2023數據挖掘導論40其他問題：缺失屬性值如何40缺失屬性值:計算不純度量SplitonRefund:

Entropy(Refund=Yes)=0Entropy(Refund=No)

=–(2/6)log(2/6)–(4/6)log(4/6)=0.9183Entropy(Children)

=0.3(0)+0.6(0.9183)=0.551Gain=0.9(0.8813–0.551)=0.3303MissingvalueBeforeSplitting:

Entropy(Parent)

=–0.3log(0.3)–

(0.7)log(0.7)=0.88132023/8/841數據挖掘導論缺失屬性值:計算不純度量SplitonRefund:M08八月2023數據挖掘導論42缺失屬性值:實例分布RefundYesNoProbabilitythatRefund=Yesis3/9ProbabilitythatRefund=Nois6/9Assignrecordtotheleftchildwithweight=3/9andtotherightchildwithweight=6/9YesNoRefund01八月2023數據挖掘導論42缺失屬性值:實例分布Re42缺失屬性值:實例分類MarriedSingleDivorcedTotalClass=No3104Class=Yes6/9112.67Total3.67216.67Newrecord:RefundMarStTaxIncYESNONONOYesNoMarried

Single,

Divorced<80K>80KProbabilitythatMaritalStatus

=Marriedis3.67/6.67ProbabilitythatMaritalStatus={Single,Divorced}is3/6.672023/8/843數據挖掘導論缺失屬性值:實例分類MarriedSingleDivorce4.3決策樹歸納4.3決策樹歸納4408八月2023數據挖掘導論45決策樹歸納算法createdNode()為決策樹建立新結點決策樹的結點或者是一個測試條件,記作node.test_cond;或者是一個類標號,記作node.labe

find_best_split()確定應當選擇哪個屬性作為劃分訓練記錄的測試條件計算或GainRatioClassify(t)為葉結點t確定類標號TreeGrowth(E,F)E:當前數據集,F:當前屬性集01八月2023數據挖掘導論45決策樹歸納算法creat4508八月2023數據挖掘導論46決策樹歸納算法(續(xù))算法4.1決策樹歸納算法的框架TreeGrowth(E,F)1：ifstopping_cond(E,F)=truethen2：leaf=createNode()3：leaf.label=Classify(E)4：returnleaf

5：else6：root=createNode()7：root.test_cond=find_best_split(E,F)8：令V={v|v是root.test_cond的一個可能的輸出}9：for每個vVdo10：Ev={e|root.test_cond(e)=v

并且e

E}11：child=TreeGrowth(Ev,F)12：將child作為root的派生結點添加到樹中,并將邊(rootchild)標記為v13：endfor14：endif15：returnroot01八月2023數據挖掘導論46決策樹歸納算法(續(xù))算法4608八月2023數據挖掘導論47決策樹:例WebRobot/CrawlerDetection建立分類模型,區(qū)分人類用戶與Web機器人有Web服務器日志導出Web會話記錄Web會話記錄包含12個屬性（見下頁）數據集包含2916個記錄Web機器人（類1）和人類用戶（類2）會話的個數相等10%的數據用于訓練90%的數據用于檢驗01八月2023數據挖掘導論47決策樹:例WebRob4708八月2023數據挖掘導論48決策樹:例(續(xù))由Web服務器日志導出的Web會話記錄屬性描述totalPages一次Web會話提取的頁面總數ImagePages一次Web會話提取的圖像頁總數TotalTime網站訪問者所用的時間RepeatedAccess一次Web會話多次請求同一頁面ErrorRequest請求網頁的錯誤GET使用GET方式提出的請求百分比POST使用POST方式提出的請求百分比HEAD使用HEAD方式提出的請求百分比BreadthWeb遍歷的寬度DepthWeb遍歷的深度MultiIP使用多個IP地址的會話MultiAgent使用多個代理的會話01八月2023數據挖掘導論48決策樹:例(續(xù))由Web4808八月2023數據挖掘導論49決策樹:例(續(xù))決策樹01八月2023數據挖掘導論49決策樹:例(續(xù))決策樹4908八月2023數據挖掘導論50決策樹:例(續(xù))從以下4個方面區(qū)分出Web機器人和人類用戶：Web機器人的訪問傾向于寬而淺，而人類用戶訪問比較集中（窄而深）與人類用戶不同，Web機器人很少訪問與Web文檔相關的圖片頁Web機器人的會話的長度趨于較長，包含了大量請求頁面Web機器人更可能對相同的文檔發(fā)出重復的請求，因為人類用戶訪問的網頁常常會被瀏覽器保存01八月2023數據挖掘導論50決策樹:例(續(xù))從以下45008八月2023數據挖掘導論51決策樹歸納的特點一般特點構建分類模型的非參數方法不要求任何先驗假設,不假定類和其他屬性服從一定的概率分布貪心的、自頂向下的遞歸劃分策略建立決策樹找到最佳的決策樹是NP完全問題決策邊界是直線(平面),平行于“坐標軸”01八月2023數據挖掘導論51決策樹歸納的特點一般特5108八月2023數據挖掘導論52決策樹歸納的特點(續(xù))優(yōu)點快速建立模型,快速分類如果數據集可以放在內存，建立決策樹很快分類時間復雜度：最壞情況下為O(w)，其中w是樹的最大深度分類準確率高特別適合包含固定屬性（維度不高）的記錄數據決策樹相對容易解釋小型決策樹容易解釋對于噪聲的干擾具有相當好的魯棒性可以采用避免過擬合的方法不受冗余屬性、不相關屬性影響自動選擇最好的屬性進行劃分01八月2023數據挖掘導論52決策樹歸納的特點(續(xù))優(yōu)5208八月2023數據挖掘導論53決策樹歸納的特點(續(xù))存在問題數據碎片（datafragmentation）問題在葉結點,記錄可能太少,對于葉結點代表的類,不能做出具有統(tǒng)計意義的判決子樹可能在決策樹中重復多次使得決策樹過于復雜,難以解釋01八月2023數據挖掘導論53決策樹歸納的特點(續(xù))存5308八月2023數據挖掘導論54決策樹歸納的特點(續(xù))其他問題平行于坐標軸的邊界限制了決策樹的能力一個需要斜邊界的例子使用斜邊界x+y<1更好01八月2023數據挖掘導論54決策樹歸納的特點(續(xù))其544.4模型的過分擬合4.4模型的過分擬合5508八月2023數據挖掘導論56概述訓練誤差vs泛化誤差訓練誤差(trainingerror)又稱再代入誤差(resubstitutionerror),表現誤差(apparenterror)模型在訓練集上誤分類樣本所占的比例泛化誤差(generalizationerror)模型在未知記錄上的期望誤差通常在檢驗集上估計，因此又稱檢驗誤差欠擬合vs過擬合欠擬合(underfitting):訓練和檢驗誤差都很大過擬合(overfitting):訓練誤差小，但檢驗誤差大01八月2023數據挖掘導論56概述訓練誤差vs泛化5608八月2023數據挖掘導論57概述(續(xù))訓練誤差和檢驗誤差與模型復雜度的關系訓練誤差檢驗誤差誤差率結點數01八月2023數據挖掘導論57概述(續(xù))訓練誤差和檢驗5708八月2023數據挖掘導論58噪聲導致的過擬合哺乳動物的分類問題訓練集中，蝙蝠和鯨被錯誤地標記為非哺乳類動物這類錯誤可以視為噪聲名稱體溫胎生4條腿冬眠哺乳動物豪豬貓蝙蝠鯨蠑螈科莫多巨蜥蟒蛇鮭魚鷹虹鳉恒溫恒溫恒溫恒溫冷血冷血冷血冷血恒溫冷血是是是是否否否否否是是是否否是是否否否否是否是否是否是否否否是是否*否*否否否否否否01八月2023數據挖掘導論58噪聲導致的過擬合哺乳動5808八月2023數據挖掘導論59噪聲導致的過擬合(續(xù))檢驗數據集名稱體溫胎生4條腿冬眠哺乳動物人鴿子象豹紋鯊海龜企鵝鰻海豚針鼴希拉毒蜥

恒溫恒溫恒溫冷血冷血冷血冷血恒溫恒溫冷血

是否是是否否否是否否

否否是否是否否否是是

否否否否否否否否是是

是否是否否否否是是否

01八月2023數據挖掘導論59噪聲導致的過擬合(續(xù))檢5908八月2023數據挖掘導論60噪聲導致的過擬合(續(xù))基于含噪聲訓練數據建立的決策樹左:訓練誤差為0,但在檢驗集上,人和海豚都被誤分類為非哺乳類動物.針鼴是個例外,其檢驗記錄中的類標號與訓練集中相似的記錄的類標號相反右:訓練誤差20%,檢驗誤差10%體溫胎生4條腿是否是否哺乳類

動物非哺乳

類動物非哺乳

類動物恒溫冷血胎生非哺乳

類動物是否哺乳類

動物非哺乳

類動物體溫恒溫冷血非哺乳

類動物01八月2023數據挖掘導論60噪聲導致的過擬合(續(xù))基6008八月2023數據挖掘導論61缺乏代表性樣本導致的過分擬合訓練樣本太少缺乏代表性樣本學習算法仍然繼續(xù)細化模型過擬合例:一個小訓練集名稱體溫胎生4條腿冬眠哺乳動物蠑螈虹鳉鷹弱夜鷹鴨嘴獸冷血冷血恒溫恒溫恒溫否是否否否是否否否是是否否是是否否否否是01八月2023數據挖掘導論61缺乏代表性樣本導致的過分6108八月2023數據挖掘導論62缺乏代表性樣本(續(xù))基于小樣本的決策樹人、大象和海豚都被誤分類體溫冬眠4條腿是否是否哺乳類

動物非哺乳

類動物非哺乳

類動物恒溫冷血非哺乳

類動物01八月2023數據挖掘導論62缺乏代表性樣本(續(xù))基于6208八月2023數據挖掘導論63過擬合過擬合導致具有不必要的復雜度的決策樹需要對決策樹剪枝,降低復雜度如何評估一個分支是否需要剪去估計泛化誤差在訓練集上估計使用再代入估計結合模型復雜度估計統(tǒng)計上界在確認集(validationset)上估計確認集是訓練集的一部分，不是檢驗集01八月2023數據挖掘導論63過擬合過擬合導致具有不必6308八月2023數據挖掘導論64Occam剃刀Occam’sRazorGiventwomodelsofsimilargeneralizationerrors,oneshouldpreferthesimplermodeloverthemorecomplexmodelEinsteinEverythingshouldbemadeassimpleaspossible,butnotsimpler.01八月2023數據挖掘導論64Occam剃刀Occa6408八月2023數據挖掘導論65估計泛化誤差使用再代入誤差:再代入誤差就是訓練誤差假設訓練數據集可以很好地代表整體數據提供對泛化誤差的樂觀估計,一般很難剪枝01八月2023數據挖掘導論65估計泛化誤差使用再代入誤6508八月2023數據挖掘導論66估計泛化誤差(續(xù))結合模型復雜度悲觀誤差評估最小描述長度悲觀誤差評估用訓練誤差與模型復雜度罰項的和估計泛化誤差eg(T)其中，n(t)是結點t分類的訓練記錄數e(t)是被誤分類的記錄數k是決策樹的葉結點數e(T)決策樹的總訓練誤差Nt是訓練記錄數(ti)是每個結點ti對應的罰項，(T)是樹的罰項（結點罰項和）01八月2023數據挖掘導論66估計泛化誤差(續(xù))結合模6608八月2023數據挖掘導論67悲觀誤差評估:例例：24個記錄，TL有7個樹葉，TR有4個樹葉取(ti)=0.5意味對于二路劃分，(ti)=0.5意味只要減少一個錯誤就可以劃分一個結點01八月2023數據挖掘導論67悲觀誤差評估:例例：26708八月2023數據挖掘導論68最小描述長度最小描述長度（MinimumDescriptionLength,MDL）原則Cost(Model,Data)=Cost(Data|Model)+Cost(Model)Costisthenumberofbitsneededforencoding.Searchfortheleastcostlymodel.Cost(Data|Model)encodesthemisclassificationerrors.Cost(Model)usesnodeencoding(numberofchildren)plussplittingconditionencodingABA?B?C?1001YesNoB1B2C1C201八月2023數據挖掘導論68最小描述長度最小描述長度6808八月2023數據挖掘導論69使用確認集訓練數據集分為兩個較小的子集，一個子集用于訓練，而另一個稱作確認集，用于估計泛化誤差典型的做法三分之二的訓練集來建立模型三分之一用作誤差估計優(yōu)點：簡單，較好地估計泛化誤差缺點：減少了用于訓練的記錄01八月2023數據挖掘導論69使用確認集訓練數據集分6908八月2023數據挖掘導論70處理過擬合:剪枝Pre-Pruning(EarlyStoppingRule)Stopthealgorithmbeforeitbecomesafully-growntreeTypicalstoppingconditionsforanode:StopifallinstancesbelongtothesameclassStopifalltheattributevaluesarethesameMorerestrictiveconditions:Stopifnumberofinstancesislessthansomeuser-specifiedthresholdStopifclassdistributionofinstancesareindependentoftheavailablefeatures(e.g.,using2test)Stopifexpandingthecurrentnodedoesnotimproveimpuritymeasures(e.g.,Giniorinformationgain).01八月2023數據挖掘導論70處理過擬合:剪枝Pre7008八月2023數據挖掘導論71處理過擬合:剪枝Post-pruningGrowdecisiontreetoitsentiretyTrimthenodesofthedecisiontreeinabottom-upfashionIfgeneralizationerrorimprovesaftertrimming,replacesub-treebyaleafnode.Classlabelofleafnodeisdeterminedfrommajorityclassofinstancesinthesub-treeCanuseMDLforpost-pruning01八月2023數據挖掘導論71處理過擬合:剪枝Pos71后剪枝:例Class=Yes20Class=No10Error=10/30TrainingError(Beforesplitting)=10/30Pessimisticerror=(10+0.5)/30=10.5/30TrainingError(Aftersplitting)=9/30Pessimisticerror(Aftersplitting) =(9+40.5)/30=11/30

PRUNE!Class=Yes8Class=No4Class=Yes3Class=No4Class=Yes4Class=No1Class=Yes5Class=No1A?A1A2A3A42023/8/872數據挖掘導論后剪枝:例Class=Yes20Class=No108八月2023數據挖掘導論73后剪枝:例Web機器人檢測決策樹的后剪枝子樹提升子樹替換決策樹：簡化后的決策樹：01八月2023數據挖掘導論73后剪枝:例Web機器人7308八月2023數據挖掘導論74評估度量FocusonthepredictivecapabilityofamodelRatherthanhowfastittakestoclassifyorbuildmodels,scalability,etc.Accuracy：Mostwidely-usedmetric被正確分類樣本所占的比例ConfusionMatrix(二類問題)PREDICTEDCLASSACTUAL

CLASSClass=YesClass=NoClass=YesabClass=Nocda:TP(truepositive)b:FN(falsenegative)c:FP(falsepositive)d:TN(truenegative)01八月2023數據挖掘導論74評估度量Focuson7408八月2023數據挖掘導論75分類準確率的局限性Considera2-classproblemNumberofClass0examples=9900NumberofClass1examples=100Ifamodelpredictseverythingtobeclass0,itsaccuracyis9900/10000=99%Accuracyismisleadingbecausemodeldoesnotdetectanyclass1exampleWilldiscussinthenextchapter01八月2023數據挖掘導論75分類準確率的局限性Con7508八月2023數據挖掘導論76評估方法保持（Holdout）方法2/3用于訓練,1/3用于檢驗局限性用于訓練的被標記樣本較少模型可能高度依賴于訓練集和檢驗集的構成訓練集越小,模型的方差越大;如果訓練集太大,根據用較小的檢驗集估計的準確率又不太可靠隨機二次抽樣（randomsubsampling）重復保持方法k次模型準確率01八月2023數據挖掘導論76評估方法保持（Holdo7608八月2023數據挖掘導論77評估方法(續(xù))交叉驗證（cross-validation）k-foldcross-validationPartitiondataintokdisjointsubsetsk-fold:trainonk1partitions,testontheremainingoneThisprocedureisrepeatedktimes,eachpartitionisusedfortestingexactlyonceLeave-one-out:k=nStratifiedk-foldcross-validationTheclassdistributionofsamplesineachfoldisapproximatlythesameasintheinitialdataStratified10-foldcross-validationisrecommendedRelativelylowbiasanvariance01八月2023數據挖掘導論77評估方法(續(xù))交叉驗證（7708八月2023數據挖掘導論78評估方法(續(xù))自助法（bootstrap）采用有放回抽樣得到自助樣本,作為訓練集自助樣本大約包含原始數據中63.2%的記錄一個記錄被抽取的概率是1(11/N)N1

e1=0.632未抽中的樣本作為檢驗集抽樣過程重復b次，產生b個自助樣本計算分類準確率的.632自助法其中,i是第i個分類器在檢驗集上的分類準確率,accs是第i個分類器在原數據集上的分類準確率01八月2023數據挖掘導論78評估方法(續(xù))自助法（b78比較分類器的性能比較分類器的性能7908八月2023數據挖掘導論80檢驗的顯著性Giventwomodels:ModelM1:accuracy=85%,testedon30instancesModelM2:accuracy=75%,testedon5000instancesCanwesayM1isbetterthanM2?HowmuchconfidencecanweplaceonaccuracyofM1andM2?Canthedifferenceinperformancemeasurebeexplainedasaresultofrandomfluctuationsinthetestset?01八月2023數據挖掘導論80檢驗的顯著性Given8008八月2023數據挖掘導論81準確率的置信區(qū)間PredictioncanberegardedasaBernoullitrialABernoullitrialhas2possibleoutcomesPossibleoutcomesforprediction:correctorwrongCollectionofBernoullitrialshasaBinomialdistribution:xBin(N,p)x:numberofcorrectpredictionse.g:Tossafaircoin50times,howmanyheadswouldturnup?

Expectednumberofheads=Np=500.5=25Givenx(#ofcorrectpredictions)orequivalently,acc=x/N,andN(#oftestinstances),Canwepredictp(trueaccuracyofmodel)?01八月2023數據挖掘導論81準確率的置信區(qū)間