第4章_分類基本概念、決策樹(shù)與模型評(píng)估ppt課件

1、數(shù)據(jù)發(fā)掘 分類：根本概念、決策樹(shù)與模型評(píng)價(jià)第4章 分類：根本概念、決策樹(shù)與模型評(píng)價(jià) 分類的是利用一個(gè)分類函數(shù)分類模型、分類器，該模型能把數(shù)據(jù)庫(kù)中的數(shù)據(jù)影射到給定類別中的一個(gè)。 分類訓(xùn)練集：數(shù)據(jù)庫(kù)中為建立模型而被分析的數(shù)據(jù)元組構(gòu)成訓(xùn)練集。訓(xùn)練集中的單個(gè)元組稱為訓(xùn)練樣本,每個(gè)訓(xùn)練樣本有一個(gè)類別標(biāo)志。一個(gè)詳細(xì)樣本的方式可為:( v1, v2, ., vn; c );其中vi表示屬性值,c表示類別。測(cè)試集：用于評(píng)價(jià)分類模型的準(zhǔn)確率數(shù)據(jù)分類一個(gè)兩步過(guò)程 (1)第一步，建立一個(gè)模型，描畫(huà)預(yù)定數(shù)據(jù)類集和概念集假定每個(gè)元組屬于一個(gè)預(yù)定義的類，由一個(gè)類標(biāo)號(hào)屬性確定學(xué)習(xí)模型可以用分類規(guī)那么、決策樹(shù)或數(shù)學(xué)公式的方式

2、提供數(shù)據(jù)分類一個(gè)兩步過(guò)程 (2)第二步，運(yùn)用模型，對(duì)未來(lái)的或未知的對(duì)象進(jìn)展分類首先評(píng)價(jià)模型的預(yù)測(cè)準(zhǔn)確率對(duì)每個(gè)測(cè)試樣本，將知的類標(biāo)號(hào)和該樣本的學(xué)習(xí)模型類預(yù)測(cè)比較模型在給定測(cè)試集上的準(zhǔn)確率是正確被模型分類的測(cè)試樣本的百分比測(cè)試集要獨(dú)立于訓(xùn)練樣本集，否那么會(huì)出現(xiàn)“過(guò)分順應(yīng)數(shù)據(jù)的情況假設(shè)準(zhǔn)確性能被接受，那么分類規(guī)那么就可用來(lái)對(duì)新數(shù)據(jù)進(jìn)展分類 有監(jiān)視的學(xué)習(xí) VS. 無(wú)監(jiān)視的學(xué)習(xí)有監(jiān)視的學(xué)習(xí)用于分類模型的學(xué)習(xí)在被告知每個(gè)訓(xùn)練樣本屬于哪個(gè)類的“監(jiān)視下進(jìn)展新數(shù)據(jù)運(yùn)用訓(xùn)練數(shù)據(jù)集中得到的規(guī)那么進(jìn)展分類無(wú)監(jiān)視的學(xué)習(xí)用于聚類每個(gè)訓(xùn)練樣本的類編號(hào)是未知的，要學(xué)習(xí)的類集合或數(shù)量也能夠是事先未知的經(jīng)過(guò)一系列的度量、察看來(lái)建

3、立數(shù)據(jù)中的類編號(hào)或進(jìn)展聚類分類模型的構(gòu)造方法1.機(jī)器學(xué)習(xí)方法：決策樹(shù)法規(guī)那么歸納2.統(tǒng)計(jì)方法：知識(shí)表示是判別函數(shù)和原型事例貝葉斯法非參數(shù)法(近鄰學(xué)習(xí)或基于事例的學(xué)習(xí)) 3.神經(jīng)網(wǎng)絡(luò)方法：BP算法,模型表示是前向反響神經(jīng)網(wǎng)絡(luò)模型4.粗糙集(rough set)知識(shí)表示是產(chǎn)生式規(guī)那么一個(gè)決策樹(shù)的例子categoricalcategoricalcontinuousclassRefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KSplitting Attributes訓(xùn)練數(shù)據(jù)模型: 決策樹(shù)決策樹(shù)的另一個(gè)例子categoricalcateg

4、oricalcontinuousclassMarStRefundTaxIncYESNONONOYesNoMarried Single, Divorced 80K用決策樹(shù)歸納分類什么是決策樹(shù)？類似于流程圖的樹(shù)構(gòu)造每個(gè)內(nèi)部節(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試每個(gè)分枝代表一個(gè)測(cè)試輸出每個(gè)樹(shù)葉節(jié)點(diǎn)代表類或類分布決策樹(shù)的生成由兩個(gè)階段組成決策樹(shù)構(gòu)建開(kāi)場(chǎng)時(shí)，一切的訓(xùn)練樣本都在根節(jié)點(diǎn)遞歸的經(jīng)過(guò)選定的屬性，來(lái)劃分樣本 必需是離散值樹(shù)剪枝許多分枝反映的是訓(xùn)練數(shù)據(jù)中的噪聲和孤立點(diǎn)，樹(shù)剪枝試圖檢測(cè)和剪去這種分枝決策樹(shù)的運(yùn)用：對(duì)未知樣本進(jìn)展分類經(jīng)過(guò)將樣本的屬性值與決策樹(shù)相比較 為了對(duì)未知數(shù)據(jù)對(duì)象進(jìn)展分類識(shí)別，可以根據(jù)決策樹(shù)的構(gòu)

5、造對(duì)數(shù)據(jù)集中的屬性進(jìn)展測(cè)試，從決策樹(shù)的根節(jié)點(diǎn)到葉節(jié)點(diǎn)的一條途徑就構(gòu)成了相應(yīng)對(duì)象的類別測(cè)試。決策樹(shù)可以很容易轉(zhuǎn)換為分類規(guī)那么決策樹(shù)分類義務(wù)Decision Tree一個(gè)決策樹(shù)的例子categoricalcategoricalcontinuousclassRefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KSplitting Attributes訓(xùn)練數(shù)據(jù)模型: 決策樹(shù)運(yùn)用決策樹(shù)進(jìn)展分類RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80K測(cè)試數(shù)據(jù)Start from t

6、he root of tree.運(yùn)用決策樹(shù)進(jìn)展分類RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80K測(cè)試數(shù)據(jù)運(yùn)用決策樹(shù)進(jìn)展分類RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80K測(cè)試數(shù)據(jù)運(yùn)用決策樹(shù)進(jìn)展分類RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80K測(cè)試數(shù)據(jù)運(yùn)用決策樹(shù)進(jìn)展分類RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80K

7、測(cè)試數(shù)據(jù)運(yùn)用決策樹(shù)進(jìn)展分類RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80K測(cè)試數(shù)據(jù)Assign Cheat to “No決策樹(shù)分類Decision Tree決策樹(shù)有許多決策樹(shù)算法:Hunt算法信息增益Information gain ID3增益比率Gain rationC4.5基尼指數(shù)Gini index (SLIQ，SPRINT) Hunt 算法設(shè) Dt 是與結(jié)點(diǎn) t相關(guān)聯(lián)的訓(xùn)練記錄集算法步驟:假設(shè)Dt 中一切記錄都屬于同一個(gè)類 yt, 那么t是葉結(jié)點(diǎn)，用yt標(biāo)志假設(shè) Dt 中包含屬于多個(gè)類的記錄，那么選擇一個(gè)屬性測(cè)試條件

8、，將記錄劃分成較小的子集。對(duì)于測(cè)試條件的每個(gè)輸出，創(chuàng)建一個(gè)子結(jié)點(diǎn)，并根據(jù)測(cè)試結(jié)果將Dt中的記錄分布到子結(jié)點(diǎn)中。然后，對(duì)于每個(gè)子結(jié)點(diǎn)，遞歸地調(diào)用該算法Dt?Hunt算法Dont CheatRefundDont CheatDont CheatYesNoRefundDont CheatYesNoMaritalStatusDont CheatCheatSingle,DivorcedMarriedTaxableIncomeDont Cheat= 80KRefundDont CheatYesNoMaritalStatusDont CheatCheatSingle,DivorcedMarried決策樹(shù)Hun

9、t算法采用貪婪戰(zhàn)略構(gòu)建決策樹(shù).在選擇劃分?jǐn)?shù)據(jù)的屬性時(shí)，采取一系列部分最優(yōu)決策來(lái)構(gòu)造決策樹(shù).決策樹(shù)歸納的設(shè)計(jì)問(wèn)題如何分裂訓(xùn)練記錄怎樣為不同類型的屬性指定測(cè)試條件?怎樣評(píng)價(jià)每種測(cè)試條件?如何停頓分裂過(guò)程決策樹(shù)Hunt算法采用貪婪戰(zhàn)略構(gòu)建決策樹(shù).在選擇劃分?jǐn)?shù)據(jù)的屬性時(shí)，采取一系列部分最優(yōu)決策來(lái)構(gòu)造決策樹(shù).決策樹(shù)歸納的設(shè)計(jì)問(wèn)題如何分裂訓(xùn)練記錄怎樣為不同類型的屬性指定測(cè)試條件?怎樣評(píng)價(jià)每種測(cè)試條件?如何停頓分裂過(guò)程怎樣為不同類型的屬性指定測(cè)試條件?依賴于屬性的類型標(biāo)稱序數(shù)延續(xù)依賴于劃分的路數(shù)2路劃分多路劃分基于標(biāo)稱屬性的分裂多路劃分: 劃分?jǐn)?shù)輸出數(shù)取決于該屬性不同屬性值的個(gè)數(shù). 二元?jiǎng)澐? 劃分?jǐn)?shù)為2，

10、這種劃分要思索創(chuàng)建k個(gè)屬性值的二元?jiǎng)澐值囊磺?k-1-1種方法.CarTypeFamilySportsLuxuryCarTypeFamily, LuxurySportsCarTypeSports, LuxuryFamilyORCarTypeFamily, SportsLuxury 多路劃分: 劃分?jǐn)?shù)輸出數(shù)取決于該屬性不同屬性值的個(gè)數(shù).二元?jiǎng)澐? 劃分?jǐn)?shù)為2，需求堅(jiān)持序數(shù)屬性值的有序性.基于序數(shù)屬性的劃分SizeSmallMediumLargeSizeMedium, LargeSmallSizeSmall, MediumLargeORSizeSmall, LargeMedium基于延續(xù)屬性的劃分

11、多路劃分:viAvi+1i=1,k) 二元?jiǎng)澐? (A v) or (A v)思索一切的劃分點(diǎn)，選擇一個(gè)最正確劃分點(diǎn)v基于延續(xù)屬性的劃分決策樹(shù)決策樹(shù)歸納的設(shè)計(jì)問(wèn)題如何分裂訓(xùn)練記錄怎樣為不同類型的屬性指定測(cè)試條件?怎樣評(píng)價(jià)每種測(cè)試條件?如何停頓分裂過(guò)程怎樣選擇最正確劃分？在劃分前: 10 個(gè)記錄 class 0, 10 個(gè)記錄 class 1怎樣選擇最正確劃分？選擇最正確劃分的度量通常是根據(jù)劃分后子結(jié)點(diǎn)不純性的程度。不純性的程度越低，類分布就越傾斜 結(jié)點(diǎn)不純性的度量:不純性大不純性小怎樣找到最正確劃分？B?YesNoNode N3Node N4A?YesNoNode N1Node N2劃分前:M

12、0M1M2M3M4M12M34Gain = M0 M12 vs M0 M34結(jié)點(diǎn)不純性的丈量GiniEntropyclassification error不純性的丈量: GINI給定結(jié)點(diǎn)t的Gini值計(jì)算 :(p( j | t) 是在結(jié)點(diǎn)t中，類j發(fā)生的概率).當(dāng)類分布平衡時(shí)，Gini值到達(dá)最大值 (1 - 1/nc) 相反當(dāng)只需一個(gè)類時(shí)，Gini值到達(dá)最小值0計(jì)算 GINI的例子P(C1) = 0/6 = 0 P(C2) = 6/6 = 1Gini = 1 P(C1)2 P(C2)2 = 1 0 1 = 0 P(C1) = 1/6 P(C2) = 5/6Gini = 1 (1/6)2 (5/

13、6)2 = 0.278P(C1) = 2/6 P(C2) = 4/6Gini = 1 (2/6)2 (4/6)2 = 0.444基于 GINI的劃分當(dāng)一個(gè)結(jié)點(diǎn) p 分割成 k 個(gè)部分 (孩子), 劃分的質(zhì)量可由下面公式計(jì)算 ni = 孩子結(jié)點(diǎn) i的記錄數(shù), n = 父結(jié)點(diǎn) p的記錄數(shù).二元屬性: 計(jì)算 GINI對(duì)于二元屬性，結(jié)點(diǎn)被劃分成兩個(gè)部分得到的GINI值越小，這種劃分越可行.B?YesNoNode N1Node N2Gini(N1) = 1 (5/6)2 (2/6)2 = 0.194 Gini(N2) = 1 (1/6)2 (4/6)2 = 0.528Gini split= 7/12 *

14、 0.194 + 5/12 * 0.528= 0.333標(biāo)稱屬性:計(jì)算Gini多路劃分二元?jiǎng)澐制胀ǘ嗦穭澐值腉ini值比二元?jiǎng)澐中?，這一結(jié)果并不奇異，由于二元?jiǎng)澐謱?shí)踐上合并了多路劃分的某些輸出，自然降低了子集的純度Multi-way splitTwo-way split (find best partition of values)延續(xù)屬性: 計(jì)算 Gini運(yùn)用二元?jiǎng)澐謩澐贮c(diǎn)v選擇N個(gè)記錄中一切屬性值作為劃分點(diǎn)對(duì)每個(gè)劃分進(jìn)展類計(jì)數(shù), A v and A v計(jì)算每個(gè)候選點(diǎn)v的Gini目的，并從中選擇具有最小值的候選劃分點(diǎn)時(shí)間復(fù)雜度為(n2)延續(xù)屬性: 計(jì)算 Gini.降低計(jì)算復(fù)雜性的方法,將記錄

15、進(jìn)展排序從兩個(gè)相鄰的排過(guò)序的屬性值之間選擇中間值作為劃分點(diǎn)計(jì)算每個(gè)候選點(diǎn)的Gini值時(shí)間復(fù)雜度為nlogn劃分點(diǎn)排序后的值 定義：給定一個(gè)概率空間 事件的自信息定義為 因 自信息反映了事件 發(fā)生所需求的信息量。 值越大闡明需求越多的信息才干確定事件 的發(fā)生，其隨機(jī)性也越大，而當(dāng) 發(fā)生時(shí)所攜帶的信息量也越大。反過(guò)來(lái)， 值越小，需求較少信息量就能確定 的發(fā)生，即事件 隨機(jī)性較小。當(dāng)其發(fā)生時(shí)所攜信息量就少。 是對(duì)不確定性大小的一種描寫(xiě) 熵-定義熵-定義1.定義：在概率空間 上定義的隨機(jī)變量 I( X)的數(shù)學(xué)期望 稱為隨機(jī)變量X的平均自信息，又稱X的信息熵或熵記為H(x) 非負(fù)性：H大于等于0 延續(xù)性

16、：H對(duì)恣意q延續(xù)極值性：當(dāng)q都等于1K時(shí) H到達(dá)最大值logK熵-定義基于 Information Gain的劃分給定結(jié)點(diǎn)t的 Entropy值計(jì)算 :(p( j | t) 是在結(jié)點(diǎn)t中，類j發(fā)生的概率).當(dāng)類分布平衡時(shí)， Entropy值到達(dá)最大值 (log nc)相反當(dāng)只需一個(gè)類時(shí)，Gini值到達(dá)最小值0Entropy 與 GINI類似計(jì)算 Entropy的例子P(C1) = 0/6 = 0 P(C2) = 6/6 = 1Entropy = 0 log 0 1 log 1 = 0 0 = 0 P(C1) = 1/6 P(C2) = 5/6Entropy = (1/6) log2 (1/6)

17、 (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.92基于 Information Gain的劃分.Information Gain: ni = 孩子結(jié)點(diǎn) i的記錄數(shù), n = 結(jié)點(diǎn) p的記錄數(shù). 在 ID3 and C4.5中運(yùn)用基于 Information Gain的劃分.增益率Gain Ratio: 熵和Gini目的等不純性趨向于有利于具有大量不同值的屬性!如：利用雇員id產(chǎn)生更純的劃分，但它卻毫無(wú)用途每個(gè)劃分相關(guān)聯(lián)的記錄數(shù)太少，將不能做出可靠的預(yù)測(cè)

18、處理該問(wèn)題的戰(zhàn)略有兩種：限制測(cè)試條件只能是二元?jiǎng)澐诌\(yùn)用增益率。K越大Split Info越大增益率越小基于 Classification Error的劃分給定結(jié)點(diǎn)t的 Classification Error值計(jì)算 :當(dāng)類分布平衡時(shí)， error值到達(dá)最大值 (1 - 1/nc) 相反當(dāng)只需一個(gè)類時(shí)， error值到達(dá)最小值0例子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

19、 P(C2) = 4/6Error = 1 max (2/6, 4/6) = 1 4/6 = 1/3不純性度量之間的比較二元分類問(wèn)題:決策樹(shù)Hunt算法采用貪婪戰(zhàn)略構(gòu)建決策樹(shù).在選擇劃分?jǐn)?shù)據(jù)的屬性時(shí)，采取一系列部分最優(yōu)決策來(lái)構(gòu)造決策樹(shù).決策樹(shù)歸納的設(shè)計(jì)問(wèn)題如何分裂訓(xùn)練記錄怎樣為不同類型的屬性指定測(cè)試條件?怎樣評(píng)價(jià)每種測(cè)試條件?如何停頓分裂過(guò)程停頓分裂過(guò)程當(dāng)一切的記錄屬于同一類時(shí)，停頓分裂當(dāng)一切的記錄都有一樣的屬性時(shí)，停頓分裂提早終止樹(shù)的生長(zhǎng)三種著名的決策樹(shù)Cart：根本的決策樹(shù)算法Id3：利用增益比不純性，樹(shù)采用二叉樹(shù)，停頓準(zhǔn)那么為當(dāng)一切的記錄屬于同一類時(shí)，停頓分裂，或當(dāng)一切的記錄都有一樣的屬

20、性時(shí)，停頓分裂C4.5：id3的改良版本，也是最流行的分類數(shù)算法。采用多重分支和剪枝技術(shù)。決策樹(shù)特點(diǎn):決策樹(shù)是一種構(gòu)建分類模型的非參數(shù)方法不需求昂貴的的計(jì)算代價(jià)決策樹(shù)相對(duì)容易解釋決策樹(shù)是學(xué)習(xí)離散值函數(shù)的典型代表決策數(shù)對(duì)于噪聲的干擾具有相當(dāng)好的魯棒性冗余屬性不會(huì)對(duì)決策樹(shù)的準(zhǔn)確率呵斥不利影響數(shù)據(jù)碎片問(wèn)題。隨著數(shù)的生長(zhǎng)，能夠?qū)е氯~結(jié)點(diǎn)記錄數(shù)太少，對(duì)于葉結(jié)點(diǎn)代表的類，不能做出具有統(tǒng)計(jì)意義的判決子樹(shù)能夠在決策樹(shù)中反復(fù)多次。使決策樹(shù)過(guò)于復(fù)雜子樹(shù)反復(fù)問(wèn)題 Same subtree appears in multiple branches決策邊境 斜決策樹(shù)x + y 1Class = + Class = 模型

21、過(guò)分?jǐn)M合和擬合缺乏分類模型的誤差大致分為兩種：訓(xùn)練誤差：是在訓(xùn)練記錄上誤分類樣本比例泛化誤差：是模型在未知記錄上的期望誤差一個(gè)好的分類模型不僅要可以很好的擬合訓(xùn)練數(shù)據(jù)，而且對(duì)未知樣本也要能準(zhǔn)確分類。換句話說(shuō)，一個(gè)好的分類模型必需具有低訓(xùn)練誤差和低泛化誤差。當(dāng)訓(xùn)練數(shù)據(jù)擬合太好的模型，其泛化誤差能夠比具有較高訓(xùn)練誤差的模型高，這種情況成為模型過(guò)分?jǐn)M合模型過(guò)分?jǐn)M合和擬合缺乏當(dāng)決策樹(shù)很小時(shí)，訓(xùn)練和檢驗(yàn)誤差都很大，這種情況稱為模型擬合缺乏。出現(xiàn)擬合缺乏的緣由是模型尚未學(xué)習(xí)到數(shù)據(jù)的真實(shí)構(gòu)造。隨著決策樹(shù)中結(jié)點(diǎn)數(shù)的添加，模型的訓(xùn)練誤差和檢驗(yàn)誤差都會(huì)隨之下降。當(dāng)樹(shù)的規(guī)模變得太大時(shí)，即使訓(xùn)練誤差還在繼續(xù)降低，但是

22、檢驗(yàn)誤差開(kāi)場(chǎng)增大，導(dǎo)致模型過(guò)分?jǐn)M合模型模型過(guò)分?jǐn)M合和擬合缺乏過(guò)分?jǐn)M合導(dǎo)致過(guò)分?jǐn)M合的緣由導(dǎo)致過(guò)分?jǐn)M合的緣由噪聲導(dǎo)致的過(guò)分?jǐn)M合例子：哺乳動(dòng)物的分類問(wèn)題十個(gè)訓(xùn)練記錄中有兩個(gè)被錯(cuò)誤標(biāo)志：蝙蝠和鯨假設(shè)完全擬合訓(xùn)練數(shù)據(jù)，決策樹(shù)1的訓(xùn)練誤差為0，但它在檢驗(yàn)數(shù)據(jù)上的誤差達(dá)30%.人和海豚，針鼴誤分為非哺乳動(dòng)物相反，一個(gè)更簡(jiǎn)單的決策樹(shù)2，具有較低的檢驗(yàn)誤差10%，雖然它的訓(xùn)練誤差較高，為20%決策樹(shù)1過(guò)分?jǐn)M合了訓(xùn)練數(shù)據(jù)。由于屬性測(cè)試條件4條腿具有欺騙性，它擬合了誤標(biāo)志的訓(xùn)練紀(jì)錄，導(dǎo)致了對(duì)檢驗(yàn)集中記錄的誤分類噪聲導(dǎo)致的過(guò)分?jǐn)M合例子噪聲導(dǎo)致決策邊境的改動(dòng)缺乏代表性樣本導(dǎo)致的過(guò)分?jǐn)M合根據(jù)少量訓(xùn)練記錄做出分類決策的模型

23、也容易受過(guò)分?jǐn)M合的影響。由于訓(xùn)練數(shù)據(jù)缺乏具有代表性的樣本，在沒(méi)有多少訓(xùn)練記錄的情況下，學(xué)習(xí)算法依然細(xì)化模型就會(huì)產(chǎn)生過(guò)分?jǐn)M合。例子：五個(gè)訓(xùn)練記錄，一切的記錄都是正確標(biāo)志的，對(duì)應(yīng)的決策樹(shù)雖然訓(xùn)練誤差為0，但檢驗(yàn)誤差高達(dá)30%人、大象和海豚被誤分類，由于決策樹(shù)把恒溫但不冬眠的動(dòng)物分為非哺乳動(dòng)物。決策樹(shù)做出這樣的分類決策是由于只需一個(gè)訓(xùn)練記錄鷹具有這些特征。這個(gè)例子清楚的闡明，當(dāng)決策樹(shù)的葉結(jié)點(diǎn)沒(méi)有足夠的代表性樣本時(shí)，很能夠做出錯(cuò)誤的預(yù)測(cè)。過(guò)分?jǐn)M合與多重比較模型的過(guò)分?jǐn)M合能夠出如今運(yùn)用多重比較過(guò)程的算法中多重比較的例子：思索未來(lái)十個(gè)買(mǎi)賣(mài)日股市是升還是降一個(gè)人十次猜測(cè)至少正確預(yù)測(cè)八次的概率是：0.0547

24、假設(shè)從50個(gè)股票分析家中選擇一個(gè)投資顧問(wèn)，戰(zhàn)略是選擇在未來(lái)的十個(gè)買(mǎi)賣(mài)日做出最多正確預(yù)測(cè)的分析家。該戰(zhàn)略的缺陷是，即使一切的分析家都用隨機(jī)猜測(cè)做出預(yù)測(cè)，至少有一個(gè)分析家做出八次正確預(yù)測(cè)的概率是：1-1-0.054750=0.9399，這一結(jié)果相當(dāng)高。多重比較過(guò)程與模型過(guò)分?jǐn)M合有什么關(guān)系？在決策樹(shù)增長(zhǎng)過(guò)程中，可以進(jìn)展多種測(cè)試，以確定哪個(gè)屬性可以最好的劃分訓(xùn)練數(shù)據(jù)。在這種情況下，算法實(shí)踐上是運(yùn)用多重比較過(guò)程來(lái)決議能否需求擴(kuò)展決策樹(shù)。當(dāng)候選屬性多，訓(xùn)練記錄數(shù)少時(shí)，這種影響就變得更加明顯。泛化誤差估計(jì)過(guò)分?jǐn)M合的主要緣由不斷是個(gè)爭(zhēng)辯的話題，但大家還是普遍贊同模型的復(fù)雜度對(duì)模型的過(guò)分?jǐn)M合有影響。如何確定正確

25、的模型復(fù)雜度？理想的復(fù)雜度是能產(chǎn)生最低泛化誤差的模型的復(fù)雜度。估計(jì)泛化誤差的方法運(yùn)用再代入估計(jì)。用訓(xùn)練誤差提供對(duì)泛化誤差的樂(lè)觀估計(jì)結(jié)合模型復(fù)雜度估計(jì)統(tǒng)計(jì)上界運(yùn)用確定集結(jié)合模型復(fù)雜度奧卡姆剃刀 Occams Razor ：給定兩個(gè)具有一樣泛化誤差的模型，較簡(jiǎn)單的模型比復(fù)雜的模型更可取 由于復(fù)雜模型中的附加成分很大程度上是偶爾的擬合。因此，分類模型評(píng)價(jià)應(yīng)把模型復(fù)雜度思索進(jìn)去方法：悲觀誤差估計(jì)、最小描畫(huà)長(zhǎng)度原那么MDL悲觀誤差評(píng)價(jià)悲觀誤差估計(jì)公式：Q(ti)為每個(gè)結(jié)點(diǎn)ti的罰分，e(T)為訓(xùn)練樣本集的錯(cuò)分樣本數(shù)，Nt為訓(xùn)練樣本總數(shù)，k為葉結(jié)點(diǎn)數(shù)。例子1：假設(shè)罰分等于0.5，訓(xùn)練樣本集中樣本數(shù)為24個(gè)

26、，我們構(gòu)建了7個(gè)葉結(jié)點(diǎn)的決策樹(shù)，訓(xùn)練樣本集的錯(cuò)分樣本數(shù)為4根據(jù)公式我們得e(T)=(4+7*0.5)/24=0.3125例子2：假設(shè)罰分等于0.5，訓(xùn)練樣本集中樣本數(shù)為24個(gè)，我們構(gòu)建了4個(gè)葉結(jié)點(diǎn)的決策樹(shù)，訓(xùn)練樣本集的錯(cuò)分樣本數(shù)為6根據(jù)公式我們得e(T)=(6+4*0.5)/24=0.3333當(dāng)罰分等于1時(shí)，例1，2為0.458，0.4170.5的罰分項(xiàng)表示只需至少可以改良一個(gè)訓(xùn)練記錄的分類，結(jié)點(diǎn)就該當(dāng)擴(kuò)展，由于擴(kuò)展一個(gè)結(jié)點(diǎn)等價(jià)于總誤差添加0.5，代價(jià)比犯一個(gè)訓(xùn)練錯(cuò)誤小最小描畫(huà)長(zhǎng)度 (MDL)Cost(Model,Data) = Cost(Data|Model) + Cost(Model)Cost 是傳輸總代價(jià).最小化cost值.Cost(Data|Model) 是誤分類記錄編碼的開(kāi)銷.Cost(Model) 是模型編碼的開(kāi)銷 .運(yùn)用確認(rèn)集該方法中，不是用訓(xùn)練集估計(jì)泛化誤差，而是把原始的訓(xùn)練數(shù)據(jù)集分為兩個(gè)較小的子集，一個(gè)子集用于訓(xùn)練，而另一個(gè)稱為確認(rèn)集，用于估計(jì)泛化誤差。該方法為評(píng)價(jià)模型在未知樣本上的性能提供了較好方法。處置決策樹(shù)中的過(guò)分?jǐn)M合先剪枝 (Early Stopping Rule)樹(shù)增長(zhǎng)算法在產(chǎn)生完全擬合整個(gè)訓(xùn)練數(shù)據(jù)集的之前就停頓決策樹(shù)的生長(zhǎng)為了做到這一點(diǎn)，需求采用更具限制性的終了條件: 當(dāng)結(jié)點(diǎn)的記錄數(shù)少于一定閾值，