上傳人：1***

認(rèn)證信息

認(rèn)證類型：個人認(rèn)證

認(rèn)證主體：劉**（實名認(rèn)證）

IP屬地：湖北

IP屬地：湖北 上傳時間：2023-10-24 格式：PPT 頁數(shù)：88 大?。?.72MB 積分：6 舉報 版權(quán)申訴

數(shù)據(jù)挖掘?qū)д揚ang-ningTan,MichaelStieinbach,andVipinKumar著PearsonEducationLTD.范明等譯人民郵電出版社第4章分類：基本概念、決策樹

與模型評估引言:預(yù)備知識,解決分類問題的一般方法決策樹歸納模型的過分?jǐn)M合評估分類器的性能引言24十月2023數(shù)據(jù)挖掘?qū)д?分類:定義Givenacollectionofrecords(trainingset)Eachrecordcontainsasetofattributes,oneoftheattributesistheclass.Findamodelforclassattributeasafunctionofthevaluesofotherattributes.Goal:previouslyunseenrecordsshouldbeassignedaclassasaccuratelyaspossible.Atestsetisusedtodeterminetheaccuracyofthemodel.Usually,thegivendatasetisdividedintotrainingandtestsets,withtrainingsetusedtobuildthemodelandtestsetusedtovalidateit24十月2023數(shù)據(jù)挖掘?qū)д?分類:解釋24十月2023數(shù)據(jù)挖掘?qū)д?分類任務(wù)的例子腫瘤：Predictingtumorcellsasbenignormalignant信用卡交易：Classifyingcreditcardtransactions

aslegitimateorfraudulent蛋白質(zhì)結(jié)構(gòu)：Classifyingsecondarystructuresofprotein

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

weather,entertainment,sports,etc24十月2023數(shù)據(jù)挖掘?qū)д?分類:技術(shù)DecisionTreebasedMethodsRule-basedMethodsMemorybasedreasoningNeuralNetworksNa?veBayesandBayesianBeliefNetworksSupportVectorMachines4.3決策樹歸納24十月2023數(shù)據(jù)挖掘?qū)д?24十月2023數(shù)據(jù)挖掘?qū)д?0決策樹:例子categoricalcategoricalcontinuousclassSplittingAttributesTrainingDataModel:DecisionTreeYESNONONOYesNoMarried

Single,Divorced<80K>80KRefundMarStTaxInc24十月2023數(shù)據(jù)挖掘?qū)д?1決策樹樹中包含三種結(jié)點根結(jié)點(rootnode):沒有入邊,有零條或多條出邊內(nèi)部結(jié)點(internalnode):恰有一條入邊和兩條或多條出邊葉結(jié)點(leafnode)或終端結(jié)點(terminalnode):恰有一條入邊，但沒有出邊24十月2023數(shù)據(jù)挖掘?qū)д?2決策樹分類任務(wù):應(yīng)用模型DecisionTree24十月2023數(shù)據(jù)挖掘?qū)д?3決策樹:使用模型TestDataStartfromtherootoftree.YESNONONOYesNoMarried

Single,Divorced<80K>80KRefundMarStTaxInc24十月2023數(shù)據(jù)挖掘?qū)д?4決策樹:使用模型TestDataYESNONONOYesNoMarried

Single,Divorced<80K>80KRefundMarStTaxInc24十月2023數(shù)據(jù)挖掘?qū)д?5決策樹:使用模型TestDataYESNONONOYesNoMarried

Single,Divorced<80K>80KRefundMarStTaxIncRefund

Marital

Status

Taxable

Income

Cheat

No

Married

80K

?

10

24十月2023數(shù)據(jù)挖掘?qū)д?6決策樹:使用模型TestDataYESNONONOYesNoMarried

Single,Divorced<80K>80KRefundMarStTaxIncRefund

Marital

Status

Taxable

Income

Cheat

No

Married

80K

?

10

24十月2023數(shù)據(jù)挖掘?qū)д?7決策樹:使用模型TestDataYESNONONOYesNoMarriedSingle,Divorced<80K>80KRefundMarStTaxIncRefund

Marital

Status

Taxable

Income

Cheat

No

Married

80K

?

10

24十月2023數(shù)據(jù)挖掘?qū)д?8決策樹:使用模型TestDataYESNONONOYesNoMarriedSingle,Divorced<80K>80KRefundMarStTaxIncRefund

Marital

Status

Taxable

Income

Cheat

No

Married

80K

?

10

AssignCheatto“No”24十月2023數(shù)據(jù)挖掘?qū)д?9決策樹分類任務(wù):學(xué)習(xí)模型DecisionTree24十月2023數(shù)據(jù)挖掘?qū)д?0決策樹歸納ManyAlgorithms:Hunt’sAlgorithm(oneoftheearliest)CARTID3,C4.5SLIQ,SPRINT24十月2023數(shù)據(jù)挖掘?qū)д?1Hunt算法的一般結(jié)構(gòu)LetDt

bethesetoftrainingrecordsthatreachanodetGeneralProcedure:IfDt

containsrecordsthatbelongthesameclassyt,thentisaleafnodelabeledasytIfDt

isanemptyset,thentisaleafnodelabeledbythedefaultclass,ydIfDtcontainsrecordsthatbelongtomorethanoneclass,useanattributetesttosplitthedataintosmallersubsets.Recursivelyapplytheproceduretoeachsubset.24十月2023數(shù)據(jù)挖掘?qū)д?2Hunt算法:例Don’tCheatRefundDon’tCheatDon’tCheatYesNoRefundDon’tCheatYesNoMaritalStatusDon’tCheatCheatSingle,DivorcedMarriedTaxableIncomeDon’tCheat<80K>=80KRefundDon’tCheatYesNoMaritalStatusDon’tCheatCheatSingle,DivorcedMarried24十月2023數(shù)據(jù)挖掘?qū)д?3決策樹歸納Greedystrategy.Splittherecordsbasedonanattributetestthatoptimizescertaincriterion.IssuesDeterminehowtosplittherecordsHowtospecifytheattributetestcondition?Howtodeterminethebestsplit?DeterminewhentostopsplittingDiscussabovethreeissuesindetails24十月2023數(shù)據(jù)挖掘?qū)д?4如何指定屬性測試條件DependsonattributetypesNominalOrdinalContinuousDependsonnumberofwaystosplit2-waysplitMulti-waysplit24十月2023數(shù)據(jù)挖掘?qū)д?5劃分:標(biāo)稱屬性Multi-waysplit:Useasmanypartitionsasdistinctvalues.Binarysplit:Dividesvaluesintotwosubsets.Needtofindoptimalpartitionfromallpossiblepartitions.CarTypeFamilySportsLuxuryCarType{Sports,Luxury}{Family}CarType{Family,Luxury}{Sports}CarType{Sports,Family}{Luxury}24十月2023數(shù)據(jù)挖掘?qū)д?6劃分:序數(shù)屬性Multi-waysplit:Useasmanypartitionsasdistinctvalues.Binarysplit:Dividesvaluesintotwosubsets.Needtofindoptimalpartitionfromallpossiblepartitions.Whataboutthissplit?SizeSmallMediumLargeSize{Medium,

Large}{Small}Size{Small,Medium}{Large}Size{Small,Large}{Medium}24十月2023數(shù)據(jù)挖掘?qū)д?7劃分:連續(xù)屬性DifferentwaysofhandlingDiscretizationtoformanordinalcategoricalattributeStatic–discretizeonceatthebeginningCanbetreatedasordinalattributeDynamic–rangescanbefoundbyequalintervalbucketing,equalfrequencybucketing(percentiles),orclustering.BinaryDecision:(A<v)or(Av)considerallpossiblesplitsandfindsthebestcutcanbemorecomputeintensive24十月2023數(shù)據(jù)挖掘?qū)д?8劃分:連續(xù)屬性(續(xù))TaxableIncome>97K?YesNo(ii)BinarysplitTaxableIncome?(i)Multi-waysplit<10K[10K,25K)[25K,50K)[50K,80K)>80K24十月2023數(shù)據(jù)挖掘?qū)д?9如何確定最佳劃分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...c1124十月2023數(shù)據(jù)挖掘?qū)д?0如何確定最佳劃分(續(xù))Greedyapproach:NodeswithhomogeneousclassdistributionarepreferredNeedameasureofnodeimpurityNon-homogeneous,HighdegreeofimpurityHomogeneous,Lowdegreeofimpurity24十月2023數(shù)據(jù)挖掘?qū)д?1結(jié)點的不純度結(jié)點的不純度設(shè)有c個類,t是結(jié)點,p(i|t)表示給定結(jié)點t中屬于類i的記錄所占的比例EntropyGiniIndexMisclassificationerror24十月2023數(shù)據(jù)挖掘?qū)д?2標(biāo)準(zhǔn)比較不同的不純性度量是一致的對于二類問題24十月2023數(shù)據(jù)挖掘?qū)д?3劃分的增益劃分的增益設(shè)結(jié)點parent上有N個記錄設(shè)結(jié)點parent被劃分成k部分,即parent有k個子女v1,…,vk設(shè)I(vj)是結(jié)點vj的不純度,則劃分的增益為其中,N(vj)是結(jié)點vj的記錄數(shù),I(.)可以是entropy(.),Gini(.),error(.)等反映結(jié)點parent劃分為v1,…,vk后不純度的降低越大，越有利于分類信息增益(informationgain)當(dāng)不純度用entropy度量時，稱為信息增益info(Gain)24十月2023數(shù)據(jù)挖掘?qū)д?4如何確定最佳劃分(續(xù))基本思想如果采用二元劃分,則對非二元屬性確定最佳劃分對于分類和序數(shù)屬性,需要考慮所有可能對于連續(xù)屬性,如果不離散化,需要采用二元劃分如何確定最佳劃分點,見后面的例子屬性最佳劃分是不純度最低的劃分對每個屬性的最佳劃分,計算劃分增益結(jié)點的最佳劃分是劃分增益最大的屬性(最佳)劃分24十月2023數(shù)據(jù)挖掘?qū)д?5連續(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.40024十月2023數(shù)據(jù)挖掘?qū)д?6連續(xù)屬性的最佳劃分點(續(xù))確定連續(xù)屬性的最佳劃分點的計算開銷可能很大需要計算k1個可能的劃分點產(chǎn)生的劃分的不純度減少待考察的劃分點方法如果v(i)<v(i+1),但是v(i)和v(i+1),是同類元組的取值,則最佳劃分點一定不在v(i)和v(i+1)之間.SplitPositionsSortedValuesCheatNoNoNoYesYesYesNoNoNoNoTaxableIncome60707585909510012012522055657280879297110122172230<=><=><=><=><=><=><=><=><=><=><=>Yes0303030312213030303030No0716253434343443526170Gini0.3430.30024十月2023數(shù)據(jù)挖掘?qū)д?7增益率熵和Gini指標(biāo)等不純性度量往往有利于具有大量不同值的屬性一個極端的例子:顧客ID（如身份證號）導(dǎo)致最純的劃分，但無助于分類解決方案使用二元劃分使用增益率C0:1C1:0C0:1C1:0C0:0C1:1CostomerID?...c1c10c20C0:0C1:1...c1124十月2023數(shù)據(jù)挖掘?qū)д?8增益率(續(xù))增益率是劃分增益與劃分信息的比GainRatio=/SplitInfo其中劃分信息SplitInfo劃分信息又稱劃分的熵用來克服信息增益的缺點C4.5采用增益率24十月2023數(shù)據(jù)挖掘?qū)д?9停止條件StopexpandinganodewhenalltherecordsbelongtothesameclassStopexpandinganodewhenalltherecordshavesimilarattributevaluesStopexpandinganodewhenthereisnoattributeavailableEarlytermination(tobediscussedlater)24十月2023數(shù)據(jù)挖掘?qū)д?0其他問題：缺失屬性值如何讓處理缺失屬性值Missingvaluesaffectdecisiontreeconstructioninthreedifferentways:AffectshowimpuritymeasuresarecomputedAffectshowtodistributeinstancewithmissingvaluetochildnodesAffectshowatestinstancewithmissingvalueisclassified24十月2023數(shù)據(jù)挖掘?qū)д?1缺失屬性值:計算不純度量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.881324十月2023數(shù)據(jù)挖掘?qū)д?2缺失屬性值:實例分布RefundYesNoProbabilitythatRefund=Yesis3/9ProbabilitythatRefund=Nois6/9Assignrecordtotheleftchildwithweight=3/9andtotherightchildwithweight=6/9YesNoRefund24十月2023數(shù)據(jù)挖掘?qū)д?3缺失屬性值:實例分類MarriedSingleDivorcedTotalClass=No3104Class=Yes6/9112.67Total3.67216.67Newrecord:RefundMarStTaxIncYESNONONOYesNoMarried

Single,

Divorced<80K>80KProbabilitythatMaritalStatus

=Marriedis3.67/6.67ProbabilitythatMaritalStatus={Single,Divorced}is3/6.674.3決策樹歸納24十月2023數(shù)據(jù)挖掘?qū)д?5決策樹歸納算法createdNode()為決策樹建立新結(jié)點決策樹的結(jié)點或者是一個測試條件,記作node.test_cond;或者是一個類標(biāo)號,記作node.labe

find_best_split()確定應(yīng)當(dāng)選擇哪個屬性作為劃分訓(xùn)練記錄的測試條件計算

或GainRatioClassify(t)為葉結(jié)點t確定類標(biāo)號TreeGrowth(E,F)E:當(dāng)前數(shù)據(jù)集,F:當(dāng)前屬性集24十月2023數(shù)據(jù)挖掘?qū)д?6決策樹歸納算法(續(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每個v

Vdo10：Ev={e|root.test_cond(e)=v

并且e

E}11：child=TreeGrowth(Ev,F)12：將child作為root的派生結(jié)點添加到樹中,并將邊(root

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

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

是否是是否否否是否否

否否是否是否否否是是

否否否否否否否否是是

是否是否否否否是是否

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

動物非哺乳

類動物非哺乳

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

類動物是否哺乳類

動物非哺乳

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

類動物24十月2023數(shù)據(jù)挖掘?qū)д?1缺乏代表性樣本導(dǎo)致的過分?jǐn)M合訓(xùn)練樣本太少

缺乏代表性樣本學(xué)習(xí)算法仍然繼續(xù)細(xì)化模型過擬合例:一個小訓(xùn)練集名稱體溫胎生4條腿冬眠哺乳動物蠑螈虹鳉鷹弱夜鷹鴨嘴獸冷血冷血恒溫恒溫恒溫否是否否否是否否否是是否否是是否否否否是24十月2023數(shù)據(jù)挖掘?qū)д?2缺乏代表性樣本(續(xù))基于小樣本的決策樹人、大象和海豚都被誤分類體溫冬眠4條腿是否是否哺乳類

動物非哺乳

類動物非哺乳

類動物恒溫冷血非哺乳

類動物24十月2023數(shù)據(jù)挖掘?qū)д?3過擬合過擬合導(dǎo)致具有不必要的復(fù)雜度的決策樹需要對決策樹剪枝,降低復(fù)雜度如何評估一個分支是否需要剪去估計泛化誤差在訓(xùn)練集上估計使用再代入估計結(jié)合模型復(fù)雜度估計統(tǒng)計上界在確認(rèn)集(validationset)上估計確認(rèn)集是訓(xùn)練集的一部分，不是檢驗集24十月2023數(shù)據(jù)挖掘?qū)д?4Occam剃刀Occam’sRazorGiventwomodelsofsimilargeneralizationerrors,oneshouldpreferthesimplermodeloverthemorecomplexmodelEinsteinEverythingshouldbemadeassimpleaspossible,butnotsimpler.24十月2023數(shù)據(jù)挖掘?qū)д?5估計泛化誤差使用再代入誤差:再代入誤差就是訓(xùn)練誤差假設(shè)訓(xùn)練數(shù)據(jù)集可以很好地代表整體數(shù)據(jù)提供對泛化誤差的樂觀估計,一般很難剪枝24十月2023數(shù)據(jù)挖掘?qū)д?6估計泛化誤差(續(xù))結(jié)合模型復(fù)雜度悲觀誤差評估最小描述長度悲觀誤差評估用訓(xùn)練誤差與模型復(fù)雜度罰項的和估計泛化誤差eg(T)其中，n(t)是結(jié)點t分類的訓(xùn)練記錄數(shù)e(t)是被誤分類的記錄數(shù)k是決策樹的葉結(jié)點數(shù)e(T)決策樹的總訓(xùn)練誤差Nt是訓(xùn)練記錄數(shù)

(ti)是每個結(jié)點ti對應(yīng)的罰項，

(T)是樹的罰項（結(jié)點罰項和）24十月2023數(shù)據(jù)挖掘?qū)д?7悲觀誤差評估:例例：24個記錄，TL有7個樹葉，TR有4個樹葉取

(ti)=0.5意味對于二路劃分，(ti)=0.5意味只要減少一個錯誤就可以劃分一個結(jié)點24十月2023數(shù)據(jù)挖掘?qū)д?8最小描述長度最小描述長度（MinimumDescriptionLength,MDL）原則Cost(Model,Data)=Cost(Data|Model)+Cost(Model)Costisthenumberofbitsneededforencoding.Searchfortheleastcostlymodel.Cost(Data|Model)encodesthemisclassificationerrors.Cost(Model)usesnodeencoding(numberofchildren)plussplittingconditionencodingABA?B?C?1001YesNoB1B2C1C224十月2023數(shù)據(jù)挖掘?qū)д?9使用確認(rèn)集訓(xùn)練數(shù)據(jù)集分為兩個較小的子集，一個子集用于訓(xùn)練，而另一個稱作確認(rèn)集，用于估計泛化誤差典型的做法三分之二的訓(xùn)練集來建立模型三分之一用作誤差估計優(yōu)點：簡單，較好地估計泛化誤差缺點：減少了用于訓(xùn)練的記錄24十月2023數(shù)據(jù)挖掘?qū)д?0處理過擬合:剪枝Pre-Pruning(EarlyStoppingRule)Stopthealgorithmbeforeitbecomesafully-growntreeTypicalstoppingconditionsforanode:StopifallinstancesbelongtothesameclassStopifalltheattributevaluesarethesameMorerestrictiveconditions:Stopifnumberofinstancesislessthansomeuser-specifiedthresholdStopifclassdistributionofinstancesareindependentoftheavailablefeatures(e.g.,using

2test)Stopifexpandingthecurrentnodedoesnotimproveimpuritymeasures(e.g.,Giniorinformationgain).24十月2023數(shù)據(jù)挖掘?qū)д?1處理過擬合:剪枝Post-pruningGrowdecisiontreetoitsentiretyTrimthenodesofthedecisiontreeinabottom-upfashionIfgeneralizationerrorimprovesaftertrimming,replacesub-treebyaleafnode.Classlabelofleafnodeisdeterminedfrommajorityclassofinstancesinthesub-treeCanuseMDLforpost-pruning24十月2023數(shù)據(jù)挖掘?qū)д?2后剪枝:例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?A1A2A3A424十月2023數(shù)據(jù)挖掘?qū)д?3后剪枝:例Web機(jī)器人檢測決策樹的后剪枝子樹提升子樹替換決策樹：簡化后的決策樹：24十月2023數(shù)據(jù)挖掘?qū)д?4評估度量FocusonthepredictivecapabilityofamodelRatherthanhowfastittakestoclassifyorbuildmodels,scalability,etc.Accuracy：Mostwidely-usedmetric被正確分類樣本所占的比例ConfusionMatrix(二類問題)PREDICTEDCLASSACTUAL

CLASSClass=YesClass=NoClass=YesabClass=Nocda:TP(truepositive)b:FN(falsenegative)c:FP(falsepositive)d:TN(truenegative)24十月2023數(shù)據(jù)挖掘?qū)д?5分類準(zhǔn)確率的局限性Considera2-classproblemNumberofClass0examples=9900NumberofClass1examples=100Ifamodelpredictseverythingtobeclass0,itsaccuracyis9900/10000=99%Accuracyismisleadingbecausemodeldoesnotdetectanyclass1exampleWilldiscussinthenextchapter24十月2023數(shù)據(jù)挖掘?qū)д?6評估方法保持（Holdout）方法2/3用于訓(xùn)練,1/3用于檢驗局限性用于訓(xùn)練的被標(biāo)記樣本較少模型可能高度依賴于訓(xùn)練集和檢驗集的構(gòu)成訓(xùn)練集越小,模型的方差越大;如果訓(xùn)練集太大,根據(jù)用較小的檢驗集估計的準(zhǔn)確率又不太可靠隨機(jī)二次抽樣（randomsubsampling）重復(fù)保持方法k次模型準(zhǔn)確率24十月2023數(shù)據(jù)挖掘?qū)д?7評估方法(續(xù))交叉驗證（cross-validation）k-foldcross-validationPartitiondataintokdisjointsubsetsk-fold:trainonk

1partitions,testontheremainingoneThisprocedureisrepeatedktimes,eachpartitionisusedfortestingexactlyonceLeave-one-out:k=nStratifiedk-foldcross-validationTheclassdistributionofsamplesineachfoldisapproximatlythesameasintheinitialdataStratified10-foldcross-validationisrecommendedRelativelylowbiasanvariance24十月2023數(shù)據(jù)挖掘?qū)д?8評估方法(續(xù))自助法（bootstrap）采用有放回抽樣得到自助樣本,作為訓(xùn)練集自助樣本大約包含原始數(shù)據(jù)中63.2%的記錄一個記錄被抽取的概率是1

(1

1/N)N

1

e

1=0.632未抽中的樣本作為檢驗集抽樣過程重復(fù)b次，產(chǎn)生b個自助樣本計算分類準(zhǔn)確率的.632自助法其中,

i是第i個分類器在檢驗集上的分類準(zhǔn)確率,accs是第i個分類器在原數(shù)據(jù)集上的分類準(zhǔn)確率比較分類器的性能24十月2023數(shù)據(jù)挖掘?qū)д?0檢驗的顯著性Giventwomodels:ModelM1:accuracy=85%,testedon30instancesModelM2:accuracy=75%,testedon5000instancesCanwesayM1isbetterthanM2?HowmuchconfidencecanweplaceonaccuracyofM1andM2?Canthedifferenceinperformancemeasurebeexplainedasaresultofrandomfluctuationsinthetestset?24十月2023數(shù)據(jù)挖掘?qū)д?1準(zhǔn)確率的置信區(qū)間PredictioncanberegardedasaBernoullitrialABernoullitrialhas2possibleoutcomesPossibleoutcomesforprediction:correctorwrongCollectionofBernoullitrialshasaBinomialdistribution:xBin(N,p)x:numberofcorrectpredictionse.g:Tossafaircoin50times,howmanyheadswouldturnup?

Expectednumberofheads=N

p=500.5=25Givenx(#ofcorrectpredictions)orequivalently,acc=x/N,andN(#oftestinstances),Canwepredictp(trueaccuracyofmodel)?24十月2023數(shù)據(jù)挖掘?qū)д?2