分類基本概念、決策樹與模型評估和科學決策與信息分析

數(shù)據(jù)挖掘

分類：基本概念、決策樹與模型評價分類：基本概念、決策樹與模型評價

分類的是利用一個分類函數(shù)（分類模型、分類器），該模型能把數(shù)據(jù)庫中的數(shù)據(jù)影射到給定類別中的一個。

分類訓練集：數(shù)據(jù)庫中為建立模型而被分析的數(shù)據(jù)元組形成訓練集。訓練集中的單個元組稱為訓練樣本,每個訓練樣本有一個類別標記。一個具體樣本的形式可為:(v1,v2,...,vn;c);其中vi表示屬性值,c表示類別。測試集：用于評估分類模型的準確率數(shù)據(jù)分類——一個兩步過程(1)第一步，建立一個模型，描述預定數(shù)據(jù)類集和概念集假定每個元組屬于一個預定義的類，由一個類標號屬性確定學習模型可以用分類規(guī)則、決策樹或數(shù)學公式的形式提供數(shù)據(jù)分類——一個兩步過程(2)第二步，使用模型，對將來的或未知的對象進行分類首先評估模型的預測準確率對每個測試樣本，將已知的類標號和該樣本的學習模型類預測比較模型在給定測試集上的準確率是正確被模型分類的測試樣本的百分比測試集要獨立于訓練樣本集，否則會出現(xiàn)“過分適應數(shù)據(jù)”的情況如果準確性能被接受，則分類規(guī)則就可用來對新數(shù)據(jù)進行分類有監(jiān)督的學習VS.無監(jiān)督的學習有監(jiān)督的學習（用于分類）模型的學習在被告知每個訓練樣本屬于哪個類的“監(jiān)督”下進行新數(shù)據(jù)使用訓練數(shù)據(jù)集中得到的規(guī)則進行分類無監(jiān)督的學習（用于聚類）每個訓練樣本的類編號是未知的，要學習的類集合或數(shù)量也可能是事先未知的通過一系列的度量、觀察來建立數(shù)據(jù)中的類編號或進行聚類分類模型的構(gòu)造方法1.機器學習方法：決策樹法規(guī)則歸納2.統(tǒng)計方法：知識表示是判別函數(shù)和原型事例貝葉斯法非參數(shù)法(近鄰學習或基于事例的學習)3.神經(jīng)網(wǎng)絡方法：BP算法,模型表示是前向反饋神經(jīng)網(wǎng)絡模型4.粗糙集(roughset)知識表示是產(chǎn)生式規(guī)則一個決策樹的例子categoricalcategoricalcontinuousclassRefundMarStTaxIncYESNONONOYesNoMarried

Single,Divorced<80K>80KSplittingAttributes訓練數(shù)據(jù)模型:決策樹決策樹的另一個例子categoricalcategoricalcontinuousclassMarStRefundTaxIncYESNONONOYesNoMarried

Single,Divorced<80K>80K用決策樹歸納分類什么是決策樹？類似于流程圖的樹結(jié)構(gòu)每個內(nèi)部節(jié)點表示在一個屬性上的測試每個分枝代表一個測試輸出每個樹葉節(jié)點代表類或類分布決策樹的生成由兩個階段組成決策樹構(gòu)建開始時，所有的訓練樣本都在根節(jié)點遞歸的通過選定的屬性，來劃分樣本（必須是離散值）樹剪枝許多分枝反映的是訓練數(shù)據(jù)中的噪聲和孤立點，樹剪枝試圖檢測和剪去這種分枝決策樹的使用：對未知樣本進行分類通過將樣本的屬性值與決策樹相比較為了對未知數(shù)據(jù)對象進行分類識別，可以根據(jù)決策樹的結(jié)構(gòu)對數(shù)據(jù)集中的屬性進行測試，從決策樹的根節(jié)點到葉節(jié)點的一條路徑就形成了相應對象的類別測試。決策樹可以很容易轉(zhuǎn)換為分類規(guī)則決策樹分類任務DecisionTree一個決策樹的例子categoricalcategoricalcontinuousclassRefundMarStTaxIncYESNONONOYesNoMarried

Single,Divorced<80K>80KSplittingAttributes訓練數(shù)據(jù)模型:決策樹應用決策樹進行分類RefundMarStTaxIncYESNONONOYesNoMarried

Single,Divorced<80K>80K測試數(shù)據(jù)Startfromtherootoftree.應用決策樹進行分類RefundMarStTaxIncYESNONONOYesNoMarried

Single,Divorced<80K>80K測試數(shù)據(jù)應用決策樹進行分類RefundMarStTaxIncYESNONONOYesNoMarried

Single,Divorced<80K>80K測試數(shù)據(jù)應用決策樹進行分類RefundMarStTaxIncYESNONONOYesNoMarried

Single,Divorced<80K>80K測試數(shù)據(jù)應用決策樹進行分類RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced<80K>80K測試數(shù)據(jù)應用決策樹進行分類RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced<80K>80K測試數(shù)據(jù)AssignCheatto“No”決策樹分類DecisionTree決策樹有許多決策樹算法:Hunt算法信息增益——Informationgain

（ID3）增益比率——Gainration（C4.5）基尼指數(shù)——Giniindex

(SLIQ，SPRINT)Hunt算法設Dt

是與結(jié)點t相關聯(lián)的訓練記錄集算法步驟:如果Dt

中所有記錄都屬于同一個類yt,則t是葉結(jié)點，用yt標記如果Dt

中包含屬于多個類的記錄，則選擇一個屬性測試條件，將記錄劃分成較小的子集。對于測試條件的每個輸出，創(chuàng)建一個子結(jié)點，并根據(jù)測試結(jié)果將Dt中的記錄分布到子結(jié)點中。然后，對于每個子結(jié)點，遞歸地調(diào)用該算法Dt?Hunt算法Don’tCheatRefundDon’tCheatDon’tCheatYesNoRefundDon’tCheatYesNoMaritalStatusDon’tCheatCheatSingle,DivorcedMarriedTaxableIncomeDon’tCheat<80K>=80KRefundDon’tCheatYesNoMaritalStatusDon’tCheatCheatSingle,DivorcedMarried決策樹Hunt算法采用貪心策略構(gòu)建決策樹.在選擇劃分數(shù)據(jù)的屬性時，采取一系列局部最優(yōu)決策來構(gòu)造決策樹.決策樹歸納的設計問題如何分裂訓練記錄怎樣為不同類型的屬性指定測試條件?怎樣評估每種測試條件?如何停止分裂過程決策樹Hunt算法采用貪心策略構(gòu)建決策樹.在選擇劃分數(shù)據(jù)的屬性時，采取一系列局部最優(yōu)決策來構(gòu)造決策樹.決策樹歸納的設計問題如何分裂訓練記錄怎樣為不同類型的屬性指定測試條件?怎樣評估每種測試條件?如何停止分裂過程怎樣為不同類型的屬性指定測試條件?依賴于屬性的類型標稱序數(shù)連續(xù)依賴于劃分的路數(shù)2路劃分多路劃分基于標稱屬性的分裂多路劃分:

劃分數(shù)（輸出數(shù)）取決于該屬性不同屬性值的個數(shù).二元劃分:

劃分數(shù)為2，這種劃分要考慮創(chuàng)建k個屬性值的二元劃分的所有2k-1-1種方法.CarTypeFamilySportsLuxuryCarType{Family,

Luxury}{Sports}CarType{Sports,Luxury}{Family}ORCarType{Family,

Sports}{Luxury}多路劃分:

劃分數(shù)（輸出數(shù)）取決于該屬性不同屬性值的個數(shù).二元劃分:

劃分數(shù)為2，需要保持序數(shù)屬性值的有序性.基于序數(shù)屬性的劃分SizeSmallMediumLargeSize{Medium,

Large}{Small}Size{Small,Medium}{Large}ORSize{Small,Large}{Medium}基于連續(xù)屬性的劃分多路劃分:vi≤A＜vi+1（i=1,…,k)二元劃分:(A<v)or(Av)考慮所有的劃分點，選擇一個最佳劃分點v基于連續(xù)屬性的劃分決策樹決策樹歸納的設計問題如何分裂訓練記錄怎樣為不同類型的屬性指定測試條件?怎樣評估每種測試條件?如何停止分裂過程怎樣選擇最佳劃分？在劃分前:10個記錄class0,

10個記錄class1怎樣選擇最佳劃分？選擇最佳劃分的度量通常是根據(jù)劃分后子結(jié)點不純性的程度。不純性的程度越低，類分布就越傾斜結(jié)點不純性的度量:不純性大不純性小怎樣找到最佳劃分？B?YesNoNodeN3NodeN4A?YesNoNodeN1NodeN2劃分前:M0M1M2M3M4M12M34Gain=M0–M12vsM0–M34結(jié)點不純性的測量GiniEntropyclassificationerror不純性的測量:GINI給定結(jié)點t的Gini值計算:

(p(j|t)是在結(jié)點t中，類j發(fā)生的概率).當類分布均衡時，Gini值達到最大值(1-1/nc)相反當只有一個類時，Gini值達到最小值0計算GINI的例子P(C1)=0/6=0P(C2)=6/6=1Gini=1–P(C1)2–P(C2)2=1–0–1=0P(C1)=1/6P(C2)=5/6Gini=1–(1/6)2–(5/6)2=0.278P(C1)=2/6P(C2)=4/6Gini=1–(2/6)2–(4/6)2=0.444基于GINI的劃分當一個結(jié)點p分割成k個部分(孩子),劃分的質(zhì)量可由下面公式計算

ni=孩子結(jié)點i的記錄數(shù), n

=父結(jié)點p的記錄數(shù).二元屬性:計算GINI對于二元屬性，結(jié)點被劃分成兩個部分得到的GINI值越小，這種劃分越可行.B?YesNoNodeN1NodeN2Gini(N1)

=1–(5/6)2–(2/6)2

=0.194Gini(N2)

=1–(1/6)2–(4/6)2

=0.528Ginisplit

=7/12*0.194+

5/12*0.528

=0.333標稱屬性:計算Gini多路劃分二元劃分一般多路劃分的Gini值比二元劃分小，這一結(jié)果并不奇怪，因為二元劃分實際上合并了多路劃分的某些輸出，自然降低了子集的純度Multi-waysplitTwo-waysplit(findbestpartitionofvalues)連續(xù)屬性:計算Gini使用二元劃分劃分點v選擇N個記錄中所有屬性值作為劃分點對每個劃分進行類計數(shù),A<vandAv計算每個候選點v的Gini指標，并從中選擇具有最小值的候選劃分點時間復雜度為(n2)連續(xù)屬性:計算Gini...降低計算復雜性的方法,將記錄進行排序從兩個相鄰的排過序的屬性值之間選擇中間值作為劃分點計算每個候選點的Gini值時間復雜度為nlogn劃分點排序后的值

定義：給定一個概率空間事件的自信息定義為

因自信息反映了事件發(fā)生所需要的信息量。值越大說明需要越多的信息才能確定事件的發(fā)生，其隨機性也越大，而當發(fā)生時所攜帶的信息量也越大。反過來，值越小，需要較少信息量就能確定的發(fā)生，即事件隨機性較小。當其發(fā)生時所攜信息量就少。是對不確定性大小的一種刻畫熵---定義熵---定義1.定義：在概率空間上定義的隨機變量I(X)的數(shù)學期望

稱為隨機變量X的平均自信息，又稱X的信息熵或熵記為H(x)非負性：H大于等于0連續(xù)性：H對任意q連續(xù)極值性：當q都等于1\K時H達到最大值logK熵---定義基于InformationGain的劃分給定結(jié)點t的Entropy值計算:(p(j|t)是在結(jié)點t中，類j發(fā)生的概率).當類分布均衡時，Entropy值達到最大值(lognc)相反當只有一個類時，Gini值達到最小值0Entropy與GINI相似計算Entropy的例子P(C1)=0/6=0P(C2)=6/6=1Entropy=–0log0

–1log1=–0–0=0P(C1)=1/6P(C2)=5/6Entropy=–(1/6)log2(1/6)

–(5/6)log2(1/6)=0.65P(C1)=2/6P(C2)=4/6Entropy=–(2/6)log2(2/6)

–(4/6)log2(4/6)=0.92基于InformationGain的劃分...InformationGain:

ni=孩子結(jié)點i的記錄數(shù), n

=結(jié)點p的記錄數(shù). 在ID3andC4.5中使用基于InformationGain的劃分...增益率（GainRatio）:熵和Gini指標等不純性趨向于有利于具有大量不同值的屬性!如：利用雇員id產(chǎn)生更純的劃分，但它卻毫無用處每個劃分相關聯(lián)的記錄數(shù)太少，將不能做出可靠的預測解決該問題的策略有兩種：限制測試條件只能是二元劃分使用增益率。K越大SplitInfo越大增益率越小基于ClassificationError的劃分給定結(jié)點t的ClassificationError值計算

:當類分布均衡時，error值達到最大值(1-1/nc)相反當只有一個類時，error值達到最小值0例子P(C1)=0/6=0P(C2)=6/6=1Error=1–max(0,1)=1–1=0P(C1)=1/6P(C2)=5/6Error=1–max(1/6,5/6)=1–5/6=1/6P(C1)=2/6P(C2)=4/6Error=1–max(2/6,4/6)=1–4/6=1/3不純性度量之間的比較二元分類問題:決策樹Hunt算法采用貪心策略構(gòu)建決策樹.在選擇劃分數(shù)據(jù)的屬性時，采取一系列局部最優(yōu)決策來構(gòu)造決策樹.決策樹歸納的設計問題如何分裂訓練記錄怎樣為不同類型的屬性指定測試條件?怎樣評估每種測試條件?如何停止分裂過程停止分裂過程當所有的記錄屬于同一類時，停止分裂當所有的記錄都有相同的屬性時，停止分裂提前終止樹的生長三種著名的決策樹Cart：基本的決策樹算法Id3：利用增益比不純性，樹采用二叉樹，停止準則為當所有的記錄屬于同一類時，停止分裂，或當所有的記錄都有相同的屬性時，停止分裂C4.5：id3的改進版本，也是最流行的分類數(shù)算法。采用多重分支和剪枝技術(shù)。決策樹特點:決策樹是一種構(gòu)建分類模型的非參數(shù)方法不需要昂貴的的計算代價決策樹相對容易解釋決策樹是學習離散值函數(shù)的典型代表決策數(shù)對于噪聲的干擾具有相當好的魯棒性冗余屬性不會對決策樹的準確率造成不利影響數(shù)據(jù)碎片問題。隨著數(shù)的生長，可能導致葉結(jié)點記錄數(shù)太少，對于葉結(jié)點代表的類，不能做出具有統(tǒng)計意義的判決子樹可能在決策樹中重復多次。使決策樹過于復雜子樹重復問題

Samesubtreeappearsinmultiplebranches決策邊界

斜決策樹x+y<1Class=+

Class=BayesClassifierAprobabilisticframeworkforsolvingclassificationproblemsConditionalProbability:Bayestheorem:ExampleofBayesTheoremGiven:Atorknowsthatmeningitiscausesstiffneck50%ofthetimePriorprobabilityofanypatienthavingmeningitisis1/50,000Priorprobabilityofanypatienthavingstiffneckis1/20Ifapatienthasstiffneck,what’stheprobabilityhe/shehasmeningitis?BayesianClassifiersConsidereachattributeandclasslabelasrandomvariablesGivenarecordwithattributes(A1,A2,…,An)GoalistopredictclassCSpecifically,wewanttofindthevalueofCthatmaximizesP(C|A1,A2,…,An)CanweestimateP(C|A1,A2,…,An)directlyfromdata?BayesianClassifiersApproach:computetheposteriorprobabilityP(C|A1,A2,…,An)forallvaluesofCusingtheBayestheoremChoosevalueofCthatmaximizes

P(C|A1,A2,…,An)

EquivalenttochoosingvalueofCthatmaximizes

P(A1,A2,…,An|C)P(C)HowtoestimateP(A1,A2,…,An|C)?Na?veBayesClassifierAssumeindependenceamongattributesAiwhenclassisgiven:P(A1,A2,…,An|Cj)=P(A1|Cj)P(A2|Cj)…P(An|Cj)

CanestimateP(Ai|Cj)forallAiandCj.NewpointisclassifiedtoCjifP(Cj)

jP(Ai|Cj)=P(Cj)P(A1|Cj)P(A2|Cj)…P(An|Cj)ismaximal.HowtoEstimateProbabilitiesfromData?Class:P(C)=Nc/Ne.g.,P(No)=7/10,

P(Yes)=3/10Fordiscreteattributes:

P(Ai|Ck)=|Aik|/Ncwhere|Aik|isnumberofinstanceshavingattributeAiandbelongstoclassCkExamples:

P(Status=Married|No)=4/7

P(Refund=Yes|Yes)=0kHowtoEstimateProbabilitiesfromData?Forcontinuousattributes:DiscretizetherangeintobinsoneordinalattributeperbinviolatesindependenceassumptionTwo-waysplit:(A<v)or(A>v)chooseonlyoneofthetwosplitsasnewattributeProbabilitydensityestimation:AssumeattributefollowsanormaldistributionUsedatatoestimateparametersofdistribution

(e.g.,meanandstandarddeviation)Onceprobabilitydistributionisknown,canuseittoestimatetheconditionalprobabilityP(Ai|c)HowtoEstimateProbabilitiesfromData?Normaldistribution:Oneforeach(Ai,ci)pairFor(Income,Class=No):IfClass=Nosamplemean=110samplevariance=2975ExampleofNa?veBayesClassifierP(X|Class=No)=P(Refund=No|Class=No)

P(Married|Class=No)

P(Income=120K|Class=No)

=4/74/70.0072=0.0024P(X|Class=Yes)=P(Refund=No|Class=Yes)

P(Married|Class=Yes)

P(Income=120K|Class=Yes)

=101.210-9=0SinceP(X|No)P(No)>P(X|Yes)P(Yes)ThereforeP(No|X)>P(Yes|X)

=>Class=NoGivenaTestRecord:Na?veBayesClassifierIfoneoftheconditionalprobabilityiszero,thentheentireexpressionbecomeszeroProbabilityestimation:c:numberofclassesp:priorprobabilitym:parameterExampleofNa?veBayesClassifierA:attributesM:mammalsN:non-mammalsP(A|M)P(M)>P(A|N)P(N)=>MammalsNa?veBayes(Summary)RobusttoisolatednoisepointsHandlemissingvaluesbyignoringtheinstanceduringprobabilityestimatecalculationsRobusttoirrelevantattributesIndependenceassumptionmaynotholdforsomeattributesNa?veBayesclassifierp(Ck|X)=p(X|Ck)p(Ck)/p(X)C(X)=argmaxkp(Ck|X)=argmaxkp(X|Ck)p(Ck)Na?veBayesassumesindependenceamongallfeatures(lastclass)p(X|Ck)=p(x1|Ck)p(x2|Ck)...p(xd|Ck)模型過分擬合和擬合不足分類模型的誤差大致分為兩種：訓練誤差：是在訓練記錄上誤分類樣本比例泛化誤差：是模型在未知記錄上的期望誤差一個好的分類模型不僅要能夠很好的擬合訓練數(shù)據(jù)，而且對未知樣本也要能準確分類。換句話說，一個好的分類模型必須具有低訓練誤差和低泛化誤差。當訓練數(shù)據(jù)擬合太好的模型，其泛化誤差可能比具有較高訓練誤差的模型高，這種情況成為模型過分擬合模型過分擬合和擬合不足當決策樹很小時，訓練和檢驗誤差都很大，這種情況稱為模型擬合不足。出現(xiàn)擬合不足的原因是模型尚未學習到數(shù)據(jù)的真實結(jié)構(gòu)。隨著決策樹中結(jié)點數(shù)的增加，模型的訓練誤差和檢驗誤差都會隨之下降。當樹的規(guī)模變得太大時，即使訓練誤差還在繼續(xù)降低，但是檢驗誤差開始增大，導致模型過分擬合模型模型過分擬合和擬合不足過分擬合導致過分擬合的原因?qū)е逻^分擬合的原因噪聲導致的過分擬合例子：哺乳動物的分類問題十個訓練記錄中有兩個被錯誤標記：蝙蝠和鯨如果完全擬合訓練數(shù)據(jù)，決策樹1的訓練誤差為0，但它在檢驗數(shù)據(jù)上的誤差達30%.人和海豚，針鼴誤分為非哺乳動物相反，一個更簡單的決策樹2，具有較低的檢驗誤差（10%），盡管它的訓練誤差較高，為20%決策樹1過分擬合了訓練數(shù)據(jù)。因為屬性測試條件4條腿具有欺騙性，它擬合了誤標記的訓練紀錄，導致了對檢驗集中記錄的誤分類噪聲導致的過分擬合（例子）噪聲導致決策邊界的改變?nèi)狈Υ硇詷颖緦е碌倪^分擬合根據(jù)少量訓練記錄做出分類決策的模型也容易受過分擬合的影響。由于訓練數(shù)據(jù)缺乏具有代表性的樣本，在沒有多少訓練記錄的情況下，學習算法仍然細化模型就會產(chǎn)生過分擬合。例子：五個訓練記錄，所有的記錄都是正確標記的，對應的決策樹盡管訓練誤差為0，但檢驗誤差高達30%人、大象和海豚被誤分類，因為決策樹把恒溫但不冬眠的動物分為非哺乳動物。決策樹做出這樣的分類決策是因為只有一個訓練記錄（鷹）具有這些特征。這個例子清楚的表明，當決策樹的葉結(jié)點沒有足夠的代表性樣本時，很可能做出錯誤的預測。過分擬合與多重比較模型的過分擬合可能出現(xiàn)在使用多重比較過程的算法中多重比較的例子：考慮未來十個交易日股市是升還是降一個人十次猜測至少正確預測八次的概率是：0.0547假設從50個股票分析家中選擇一個投資顧問，策略是選擇在未來的十個交易日做出最多正確預測的分析家。該策略的缺點是，即使所有的分析家都用隨機猜測做出預測，至少有一個分析家做出八次正確預測的概率是：1-（1-0.0547）50=0.9399，這一結(jié)果相當高。多重比較過程與模型過分擬合有什么關系？在決策樹增長過程中，可以進行多種測試，以確定哪個屬性能夠最好的劃分訓練數(shù)據(jù)。在這種情況下，算法實際上是使用多重比較過程來決定是否需要擴展決策樹。當候選屬性多，訓練記錄數(shù)少時，這種影響就變得更加明顯。泛化誤差估計過分擬合的主要原因一直是個爭辯的話題，但大家還是普遍同意模型的復雜度對模型的過分擬合有影響。如何確定正確的模型復雜度？理想的復雜度是能產(chǎn)生最低泛化誤差的模型的復雜度。估計泛化誤差的方法使用再代入估計。用訓練誤差提供對泛化誤差的樂觀估計結(jié)合模型復雜度估計統(tǒng)計上界使用確定集結(jié)合模型復雜度奧卡姆剃刀（Occam'sRazor）：給定兩個具有相同泛化誤差的模型，較簡單的模型比復雜的模型更可取

因為復雜模型中的附加成分很大程度上是偶然的擬合。因此，分類模型評估應把模型復雜度考慮進去方法：悲觀誤差估計、最小描述長度原則（MDL）悲觀誤差評估悲觀誤差估計公式：Q(ti)為每個結(jié)點ti的罰分，e(T)為訓練樣本集的錯分樣本數(shù)，Nt為訓練樣本總數(shù)，k為葉結(jié)點數(shù)。例子1：如果罰分等于0.5，訓練樣本集中樣本數(shù)為24個，我們構(gòu)建了7個葉結(jié)點的決策樹，訓練樣本集的錯分樣本數(shù)為4根據(jù)公式我們得e’(T)=(4+7*0.5)/24=0.3125例子2：如果罰分等于0.5，訓練樣本集中樣本數(shù)為24個，我們構(gòu)建了4個葉結(jié)點的決策樹，訓練樣本集的錯分樣本數(shù)為6根據(jù)公式我們得e’(T)=(6+4*0.5)/24=0.3333當罰分等于1時，例1，2為0.458，0.4170.5的罰分項表示只要至少能夠改進一個訓練記錄的分類，結(jié)點就應當擴充，因為擴展一個結(jié)點等價于總誤差增加0.5，代價比犯一個訓練錯誤小最小描述長度(MDL)Cost(Model,Data)=Cost(Data|Model)+Cost(Model)Cost是傳輸總代價.最小化cost值.Cost(Data|Model)是誤分類記錄編碼的開銷.Cost(Model)是模型編碼的開銷.使用確認集該方法中，不是用訓練集估計泛化誤差，而是把原始的訓練數(shù)據(jù)集分為兩個較小的子集，一個子集用于訓練，而另一個稱為確認集，用于估計泛化誤差。該方法為評估模型在未知樣本上的性能提供了較好辦法。處理決策樹中的過分擬合先剪枝(EarlyStoppingRule)樹增長算法在產(chǎn)生完全擬合整個訓練數(shù)據(jù)集的之前就停止決策樹的生長為了做到這一點，需要采用更具限制性的結(jié)束條件:

當結(jié)點的記錄數(shù)少于一定閾值，則停止生長當不純性度量的增益低于某個確定的閾值時，則停止生長(e.g.,informationgain).缺點：很難為提前終止選取正確的閾值:

閾值太高，導致擬合不足閾值太低，導致不能充分解決過分擬合的問題。處理決策樹中的過分擬合…后剪枝在該方法中，初始決策樹按照最大規(guī)模生長，然后進行剪枝的步驟，按照自底向上的方式修剪完全增長的決策樹。修剪有兩種做法:

用新的葉結(jié)點替換子樹，該葉結(jié)點的類標號由子樹下記錄中的多數(shù)類確定用子樹中最常用的分支代替子樹處理決策樹中的過分擬合…與先剪枝相比，后剪枝技術(shù)傾向于產(chǎn)生更好的結(jié)果。因為不像先剪枝，后剪枝是根據(jù)完全增長的決策樹作出的剪枝決策，先剪枝則可能過早終止決策樹的生長。然而，對于后剪枝，當子樹被剪掉后，生長完全決策樹的額外開銷就被浪費了。不平衡類問題PREDICTEDCLASS

ACTUAL

CLASSClass=YesClass=NoClass=Yesa

(TP)b

(FN)Class=Noc

(FP)d

(TN)準確率的缺點考慮2類問題類0的樣本數(shù)=9990類1的樣本數(shù)=10如果模型預測所有的樣本為類0,準確率為9990/10000=99.9%準確率的值具有欺騙性模型并沒有分對類1的任何樣本度量精度確定在分類器斷言為正類的那部分記錄中實際為正類的記錄所占的比例。精度越高，分類器的假正類錯誤率就越低。召回率度量被分類器正確預測的正樣本的比例。具有高召回率的分類器很少將正樣本誤分為負樣本。ROC(ReceiverOperatingCharacteristic)ROC曲線是顯示分類器真正率（TPR）和假正率（FPR）之間折中的一種圖形化方法。ROC曲線上有幾個關鍵點，它們有公認的解釋：（TPR=0，F(xiàn)PR=0）：把每個實例都預測為負類的模型（TPR=1，F(xiàn)PR=1）：把每個實例都預測為正類的模型（TPR=1，F(xiàn)PR=0）：理想模型使用ROC曲線比較模型沒有哪個模型能夠壓倒對方FRR<0.36,M1

較好FRR>0.36,M2較好ROC曲線下方的面積理想情況:

面積=1隨機猜測:

面積=0.5怎樣產(chǎn)生ROC曲線Threshold>=ROC曲線:第3章科學決策與信息分析主要內(nèi)容：信息分析在決策中的作用；各類型決策中的信息保障；信息分析的工作流程。基本要求：了解各類決策中信息利用的重要性；了解不同決策階段信息服務的特點；理解決策對信息的基本要求；掌握信息分析工作的基本流程。3.1信息分析在決策中的作用3.1.1決策活動中的信息利用信息分