分類基本概念、決策樹與模型評(píng)估.ppt

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

2、學(xué)公式的形式提供,數(shù)據(jù)分類一個(gè)兩步過程 (2),第二步，使用模型，對(duì)將來的或未知的對(duì)象進(jìn)行分類 首先評(píng)估模型的預(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)“過分適應(yīng)數(shù)據(jù)”的情況 如果準(zhǔn)確性能被接受，則分類規(guī)則就可用來對(duì)新數(shù)據(jù)進(jìn)行分類,有監(jiān)督的學(xué)習(xí) VS. 無監(jiān)督的學(xué)習(xí),有監(jiān)督的學(xué)習(xí)（用于分類） 模型的學(xué)習(xí)在被告知每個(gè)訓(xùn)練樣本屬于哪個(gè)類的“監(jiān)督”下進(jìn)行 新數(shù)據(jù)使用訓(xùn)練數(shù)據(jù)集中得到的規(guī)則進(jìn)行分類 無監(jiān)督的學(xué)習(xí)（用于聚類） 每個(gè)訓(xùn)練樣本的類編號(hào)是未知的，要學(xué)習(xí)的類集合或數(shù)量也

3、可能是事先未知的 通過一系列的度量、觀察來建立數(shù)據(jù)中的類編號(hào)或進(jìn)行聚類,分類模型的構(gòu)造方法,1.機(jī)器學(xué)習(xí)方法： 決策樹法 規(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è)決策樹的例子,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K, 80K,Splitting Attributes,訓(xùn)練數(shù)據(jù),模型: 決策樹,決策樹的另一個(gè)例子,ca

4、tegorical,categorical,continuous,class,MarSt,Refund,TaxInc,YES,NO,NO,Yes,No,Married,Single, Divorced, 80K, 80K,用決策樹歸納分類,什么是決策樹？ 類似于流程圖的樹結(jié)構(gòu) 每個(gè)內(nèi)部節(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試 每個(gè)分枝代表一個(gè)測(cè)試輸出 每個(gè)樹葉節(jié)點(diǎn)代表類或類分布 決策樹的生成由兩個(gè)階段組成 決策樹構(gòu)建 開始時(shí)，所有的訓(xùn)練樣本都在根節(jié)點(diǎn) 遞歸的通過選定的屬性，來劃分樣本 （必須是離散值） 樹剪枝 許多分枝反映的是訓(xùn)練數(shù)據(jù)中的噪聲和孤立點(diǎn)，樹剪枝試圖檢測(cè)和剪去這種分枝 決策樹的使用：對(duì)未知樣本進(jìn)

5、行分類 通過將樣本的屬性值與決策樹相比較,為了對(duì)未知數(shù)據(jù)對(duì)象進(jìn)行分類識(shí)別，可以根據(jù)決策樹的結(jié)構(gòu)對(duì)數(shù)據(jù)集中的屬性進(jìn)行測(cè)試，從決策樹的根節(jié)點(diǎn)到葉節(jié)點(diǎn)的一條路徑就形成了相應(yīng)對(duì)象的類別測(cè)試。決策樹可以很容易轉(zhuǎn)換為分類規(guī)則,決策樹分類任務(wù),Decision Tree,一個(gè)決策樹的例子,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K, 80K,Splitting Attributes,訓(xùn)練數(shù)據(jù),模型: 決策樹,應(yīng)用決策樹進(jìn)行分類,測(cè)試數(shù)據(jù),Start from the root of tree.,應(yīng)用決策樹進(jìn)行分類

6、,測(cè)試數(shù)據(jù),應(yīng)用決策樹進(jìn)行分類,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K, 80K,測(cè)試數(shù)據(jù),應(yīng)用決策樹進(jìn)行分類,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K, 80K,測(cè)試數(shù)據(jù),應(yīng)用決策樹進(jìn)行分類,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K, 80K,測(cè)試數(shù)據(jù),應(yīng)用決策樹進(jìn)行分類,Refund,MarSt,T

7、axInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K, 80K,測(cè)試數(shù)據(jù),Assign Cheat to “No”,決策樹分類,Decision Tree,決策樹,有許多決策樹算法: Hunt算法 信息增益Information gain （ID3） 增益比率Gain ration（C4.5） 基尼指數(shù)Gini index (SLIQ，SPRINT),Hunt 算法,設(shè) Dt 是與結(jié)點(diǎn) t相關(guān)聯(lián)的訓(xùn)練記錄集 算法步驟: 如果Dt 中所有記錄都屬于同一個(gè)類 yt, 則t是葉結(jié)點(diǎn)，用yt標(biāo)記 如果 Dt 中包含屬于多個(gè)類的記錄，則選擇一個(gè)屬

8、性測(cè)試條件，將記錄劃分成較小的子集。對(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 Cheat,決策樹,Hunt算法采用貪心策略構(gòu)建決策樹. 在選擇劃分?jǐn)?shù)據(jù)的屬性時(shí)，采取一系列局部最優(yōu)決策來構(gòu)造決策樹. 決策樹歸納的設(shè)計(jì)問題 如何分裂訓(xùn)練記錄 怎樣為不同類型的屬性指定測(cè)試條件? 怎樣評(píng)估每種測(cè)試條件? 如何停止分裂過程,決策樹,Hunt算法采用貪心策略構(gòu)建決策樹. 在選擇劃分?jǐn)?shù)據(jù)的屬性時(shí)，采取一系列局部最優(yōu)決策來構(gòu)造決策樹. 決策樹歸納的設(shè)計(jì)問題 如何分裂訓(xùn)練記錄 怎樣為不同類型的屬性

9、指定測(cè)試條件? 怎樣評(píng)估每種測(cè)試條件? 如何停止分裂過程,怎樣為不同類型的屬性指定測(cè)試條件?,依賴于屬性的類型 標(biāo)稱 序數(shù) 連續(xù) 依賴于劃分的路數(shù) 2路劃分 多路劃分,基于標(biāo)稱屬性的分裂,多路劃分: 劃分?jǐn)?shù)（輸出數(shù)）取決于該屬性不同屬性值的個(gè)數(shù). 二元?jiǎng)澐? 劃分?jǐn)?shù)為2，這種劃分要考慮創(chuàng)建k個(gè)屬性值的二元?jiǎng)澐值乃?k-1-1種方法.,OR,多路劃分: 劃分?jǐn)?shù)（輸出數(shù)）取決于該屬性不同屬性值的個(gè)數(shù). 二元?jiǎng)澐? 劃分?jǐn)?shù)為2，需要保持序數(shù)屬性值的有序性.,基于序數(shù)屬性的劃分,OR,基于連續(xù)屬性的劃分,多路劃分:viAvi+1（i=1,k) 二元?jiǎng)澐? (A v) or (A v) 考慮所有的劃分

10、點(diǎn)，選擇一個(gè)最佳劃分點(diǎn)v,基于連續(xù)屬性的劃分,決策樹,決策樹歸納的設(shè)計(jì)問題 如何分裂訓(xùn)練記錄 怎樣為不同類型的屬性指定測(cè)試條件? 怎樣評(píng)估每種測(cè)試條件? 如何停止分裂過程,怎樣選擇最佳劃分？,在劃分前: 10 個(gè)記錄 class 0, 10 個(gè)記錄 class 1,怎樣選擇最佳劃分？,選擇最佳劃分的度量通常是根據(jù)劃分后子結(jié)點(diǎn)不純性的程度。不純性的程度越低，類分布就越傾斜 結(jié)點(diǎn)不純性的度量:,不純性大,不純性小,怎樣找到最佳劃分？,B?,Yes,No,Node N3,Node N4,A?,Yes,No,Node N1,Node N2,劃分前:,Gain = M0 M12 vs M0 M34,結(jié)點(diǎn)

11、不純性的測(cè)量,Gini Entropy classification error,不純性的測(cè)量: 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 = 1 Gini = 1 P(C1)2 P(C2)2 = 1 0 1 = 0,P(C1) = 1/6 P(C2) = 5/6 Gini = 1 (1/6)2 (5/6)2 = 0.278,P(C1) = 2/6 P(C2)

12、 = 4/6 Gini = 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?,Yes,No,Node N1,Node N2,Gini(N1) = 1 (5/6)2 (2/6)2 = 0.194 Gini(N2) = 1 (1/6)2 (4/6)2 = 0.528,Gini split= 7/12 * 0.194 + 5/12 *

13、 0.528= 0.333,標(biāo)稱屬性:計(jì)算Gini,多路劃分 二元?jiǎng)澐?一般多路劃分的Gini值比二元?jiǎng)澐中。@一結(jié)果并不奇怪，因?yàn)槎獎(jiǎng)澐謱?shí)際上合并了多路劃分的某些輸出，自然降低了子集的純度,Multi-way split,Two-way split (find best partition of values),連續(xù)屬性: 計(jì)算 Gini,使用二元?jiǎng)澐?劃分點(diǎn)v選擇 N個(gè)記錄中所有屬性值作為劃分點(diǎn) 對(duì)每個(gè)劃分進(jìn)行類計(jì)數(shù), A v and A v 計(jì)算每個(gè)候選點(diǎn)v的Gini指標(biāo)，并從中選擇具有最小值的候選劃分點(diǎn) 時(shí)間復(fù)雜度為(n2),連續(xù)屬性: 計(jì)算 Gini.,降低計(jì)算復(fù)雜性的方法, 將記

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

15、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á)到最小值0 Entropy 與 GINI相似,計(jì)算 Entropy的例子,P(C1) = 0/6 = 0 P(C2) = 6/6 = 1 Entropy = 0 log 0 1 log 1 = 0 0 = 0,P(C1) = 1/6 P(C2) = 5/6 Entropy = (1/6)

16、 log2 (1/6) (5/6) log2 (1/6) = 0.65,P(C1) = 2/6 P(C2) = 4/6 Entropy = (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中使用,基于 Information Gain的劃分.,增益率（Gain Ratio）: 熵和Gini指標(biāo)等不純性趨向于有利于具有大量不同值的屬性!如：利用雇員id產(chǎn)生更純的劃分，但它卻毫無用處 每個(gè)劃分

17、相關(guān)聯(lián)的記錄數(shù)太少，將不能做出可靠的預(yù)測(cè) 解決該問題的策略有兩種： 限制測(cè)試條件只能是二元?jiǎng)澐?使用增益率。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 = 1 Error = 1 max (0, 1) = 1 1 = 0,P(C1) = 1/6 P(C2) = 5/6 Error = 1 max (1/6,

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

19、比不純性，樹采用二叉樹，停止準(zhǔn)則為當(dāng)所有的記錄屬于同一類時(shí)，停止分裂，或當(dāng)所有的記錄都有相同的屬性時(shí)，停止分裂 C4.5：id3的改進(jìn)版本，也是最流行的分類數(shù)算法。采用多重分支和剪枝技術(shù)。,決策樹,特點(diǎn): 決策樹是一種構(gòu)建分類模型的非參數(shù)方法 不需要昂貴的的計(jì)算代價(jià) 決策樹相對(duì)容易解釋 決策樹是學(xué)習(xí)離散值函數(shù)的典型代表 決策數(shù)對(duì)于噪聲的干擾具有相當(dāng)好的魯棒性 冗余屬性不會(huì)對(duì)決策樹的準(zhǔn)確率造成不利影響 數(shù)據(jù)碎片問題。隨著數(shù)的生長(zhǎng)，可能導(dǎo)致葉結(jié)點(diǎn)記錄數(shù)太少，對(duì)于葉結(jié)點(diǎn)代表的類，不能做出具有統(tǒng)計(jì)意義的判決 子樹可能在決策樹中重復(fù)多次。使決策樹過于復(fù)雜,子樹重復(fù)問題,Same subtree appe

20、ars in multiple branches,決策邊界,斜決策樹,Bayes Classifier,A probabilistic framework for solving classification problems Conditional Probability: Bayes theorem:,Example of Bayes Theorem,Given: A doctor knows that meningitis causes stiff neck 50% of the time Prior probability of any patient having meningiti

21、s is 1/50,000 Prior probability of any patient having stiff neck is 1/20 If a patient has stiff neck, whats the probability he/she has meningitis?,Bayesian Classifiers,Consider each attribute and class label as random variables Given a record with attributes (A1, A2,An) Goal is to predict class C Sp

22、ecifically, we want to find the value of C that maximizes P(C| A1, A2,An ) Can we estimate P(C| A1, A2,An ) directly from data?,Bayesian Classifiers,Approach: compute the posterior probability P(C | A1, A2, , An) for all values of C using the Bayes theorem Choose value of C that maximizes P(C | A1,

23、A2, , An) Equivalent to choosing value of C that maximizes P(A1, A2, , An|C) P(C) How to estimate P(A1, A2, , An | C )?,Nave Bayes Classifier,Assume independence among attributes Ai when class is given: P(A1, A2, , An | Cj ) = P(A1| Cj) P(A2| Cj) P(An| Cj) Can estimate P(Ai| Cj) for all Ai and Cj. N

24、ew point is classified to Cj if P(Cj) j P(Ai| Cj)= P(Cj) P(A1| Cj) P(A2| Cj) P(An| Cj) is maximal.,How to Estimate Probabilities from Data?,Class: P(C) = Nc/N e.g., P(No) = 7/10, P(Yes) = 3/10 For discrete attributes: P(Ai | Ck) = |Aik|/ Nc where |Aik| is number of instances having attribute Ai and

25、belongs to class Ck Examples: P(Status=Married|No) = 4/7P(Refund=Yes|Yes)=0,k,How to Estimate Probabilities from Data?,For continuous attributes: Discretize the range into bins one ordinal attribute per bin violates independence assumption Two-way split: (A v) choose only one of the two splits as ne

26、w attribute Probability density estimation: Assume attribute follows a normal distribution Use data to estimate parameters of distribution (e.g., mean and standard deviation) Once probability distribution is known, can use it to estimate the conditional probability P(Ai|c),How to Estimate Probabilit

27、ies from Data?,Normal distribution: One for each (Ai,ci) pair For (Income, Class=No): If Class=No sample mean = 110 sample variance = 2975,Example of Nave Bayes Classifier,P(X|Class=No) = P(Refund=No|Class=No) P(Married| Class=No) P(Income=120K| Class=No) = 4/7 4/7 0.0072 = 0.0024 P(X|Class=Yes) = P

28、(Refund=No| Class=Yes) P(Married| Class=Yes) P(Income=120K| Class=Yes) = 1 0 1.2 10-9 = 0 Since P(X|No)P(No) P(X|Yes)P(Yes) Therefore P(No|X) P(Yes|X) = Class = No,Given a Test Record:,Nave Bayes Classifier,If one of the conditional probability is zero, then the entire expression becomes zero Probab

29、ility estimation:,c: number of classes p: prior probability m: parameter,Example of Nave Bayes Classifier,A: attributes M: mammals N: non-mammals,P(A|M)P(M) P(A|N)P(N) = Mammals,Nave Bayes (Summary),Robust to isolated noise points Handle missing values by ignoring the instance during probability est

30、imate calculations Robust to irrelevant attributes Independence assumption may not hold for some attributes,Nave Bayes classifier,p(Ck | X) = p(X | Ck) p(Ck) /p(X) C(X) = argmaxk p(Ck | X) = argmaxk p(X | Ck) p(Ck) Nave Bayes assumes independence among all features (last class) p(X | Ck) = p(x1 | Ck

31、) p(x2 | Ck) . . . p(xd | Ck),模型過分?jǐn)M合和擬合不足,分類模型的誤差大致分為兩種： 訓(xùn)練誤差：是在訓(xùn)練記錄上誤分類樣本比例 泛化誤差：是模型在未知記錄上的期望誤差 一個(gè)好的分類模型不僅要能夠很好的擬合訓(xùn)練數(shù)據(jù)，而且對(duì)未知樣本也要能準(zhǔn)確分類。 換句話說，一個(gè)好的分類模型必須具有低訓(xùn)練誤差和低泛化誤差。 當(dāng)訓(xùn)練數(shù)據(jù)擬合太好的模型，其泛化誤差可能比具有較高訓(xùn)練誤差的模型高，這種情況成為模型過分?jǐn)M合,模型過分?jǐn)M合和擬合不足,當(dāng)決策樹很小時(shí)，訓(xùn)練和檢驗(yàn)誤差都很大，這種情況稱為模型擬合不足。出現(xiàn)擬合不足的原因是模型尚未學(xué)習(xí)到數(shù)據(jù)的真實(shí)結(jié)構(gòu)。 隨著決策樹中結(jié)點(diǎn)數(shù)的增加，模型的訓(xùn)

32、練誤差和檢驗(yàn)誤差都會(huì)隨之下降。 當(dāng)樹的規(guī)模變得太大時(shí)，即使訓(xùn)練誤差還在繼續(xù)降低，但是檢驗(yàn)誤差開始增大，導(dǎo)致模型過分?jǐn)M合,模型模型過分?jǐn)M合和擬合不足,過分?jǐn)M合,導(dǎo)致過分?jǐn)M合的原因,導(dǎo)致過分?jǐn)M合的原因,噪聲導(dǎo)致的過分?jǐn)M合 例子：哺乳動(dòng)物的分類問題 十個(gè)訓(xùn)練記錄中有兩個(gè)被錯(cuò)誤標(biāo)記：蝙蝠和鯨 如果完全擬合訓(xùn)練數(shù)據(jù)，決策樹1的訓(xùn)練誤差為0，但它在檢驗(yàn)數(shù)據(jù)上的誤差達(dá)30%.人和海豚，針鼴誤分為非哺乳動(dòng)物 相反，一個(gè)更簡(jiǎn)單的決策樹2，具有較低的檢驗(yàn)誤差（10%），盡管它的訓(xùn)練誤差較高，為20% 決策樹1過分?jǐn)M合了訓(xùn)練數(shù)據(jù)。因?yàn)閷傩詼y(cè)試條件4條腿具有欺騙性，它擬合了誤標(biāo)記的訓(xùn)練紀(jì)錄，導(dǎo)致了對(duì)檢驗(yàn)集中記錄的誤分

33、類,噪聲導(dǎo)致的過分?jǐn)M合（例子）,噪聲導(dǎo)致決策邊界的改變,缺乏代表性樣本導(dǎo)致的過分?jǐn)M合,根據(jù)少量訓(xùn)練記錄做出分類決策的模型也容易受過分?jǐn)M合的影響。 由于訓(xùn)練數(shù)據(jù)缺乏具有代表性的樣本，在沒有多少訓(xùn)練記錄的情況下，學(xué)習(xí)算法仍然細(xì)化模型就會(huì)產(chǎn)生過分?jǐn)M合。,例子：五個(gè)訓(xùn)練記錄，所有的記錄都是正確標(biāo)記的，對(duì)應(yīng)的決策樹盡管訓(xùn)練誤差為0，但檢驗(yàn)誤差高達(dá)30% 人、大象和海豚被誤分類，因?yàn)闆Q策樹把恒溫但不冬眠的動(dòng)物分為非哺乳動(dòng)物。決策樹做出這樣的分類決策是因?yàn)橹挥幸粋€(gè)訓(xùn)練記錄（鷹）具有這些特征。 這個(gè)例子清楚的表明，當(dāng)決策樹的葉結(jié)點(diǎn)沒有足夠的代表性樣本時(shí)，很可能做出錯(cuò)誤的預(yù)測(cè)。,過分?jǐn)M合與多重比較,模型的過分?jǐn)M

34、合可能出現(xiàn)在使用多重比較過程的算法中 多重比較的例子：考慮未來十個(gè)交易日股市是升還是降 一個(gè)人十次猜測(cè)至少正確預(yù)測(cè)八次的概率是：0.0547 假設(shè)從50個(gè)股票分析家中選擇一個(gè)投資顧問，策略是選擇在未來的十個(gè)交易日做出最多正確預(yù)測(cè)的分析家。 該策略的缺點(diǎn)是，即使所有的分析家都用隨機(jī)猜測(cè)做出預(yù)測(cè)，至少有一個(gè)分析家做出八次正確預(yù)測(cè)的概率是：1-（1-0.0547）50=0.9399，這一結(jié)果相當(dāng)高。,多重比較過程與模型過分?jǐn)M合有什么關(guān)系？ 在決策樹增長(zhǎng)過程中，可以進(jìn)行多種測(cè)試，以確定哪個(gè)屬性能夠最好的劃分訓(xùn)練數(shù)據(jù)。 在這種情況下，算法實(shí)際上是使用多重比較過程來決定是否需要擴(kuò)展決策樹。 當(dāng)候選屬性多，

35、訓(xùn)練記錄數(shù)少時(shí)，這種影響就變得更加明顯。,泛化誤差估計(jì),過分?jǐn)M合的主要原因一直是個(gè)爭(zhēng)辯的話題，但大家還是普遍同意模型的復(fù)雜度對(duì)模型的過分?jǐn)M合有影響。 如何確定正確的模型復(fù)雜度？理想的復(fù)雜度是能產(chǎn)生最低泛化誤差的模型的復(fù)雜度。 估計(jì)泛化誤差的方法 使用再代入估計(jì)。用訓(xùn)練誤差提供對(duì)泛化誤差的樂觀估計(jì) 結(jié)合模型復(fù)雜度 估計(jì)統(tǒng)計(jì)上界 使用確定集,結(jié)合模型復(fù)雜度,奧卡姆剃刀 （Occams Razor ）：給定兩個(gè)具有相同泛化誤差的模型，較簡(jiǎn)單的模型比復(fù)雜的模型更可取 因?yàn)閺?fù)雜模型中的附加成分很大程度上是偶然的擬合。因此，分類模型評(píng)估應(yīng)把模型復(fù)雜度考慮進(jìn)去 方法：悲觀誤差估計(jì)、最小描述長(zhǎng)度原則（MDL）

36、,悲觀誤差評(píng)估,悲觀誤差估計(jì)公式： Q(ti)為每個(gè)結(jié)點(diǎn)ti的罰分，e(T)為訓(xùn)練樣本集的錯(cuò)分樣本數(shù)，Nt為訓(xùn)練樣本總數(shù)，k為葉結(jié)點(diǎn)數(shù)。,例子1：如果罰分等于0.5，訓(xùn)練樣本集中樣本數(shù)為24個(gè)，我們構(gòu)建了7個(gè)葉結(jié)點(diǎn)的決策樹，訓(xùn)練樣本集的錯(cuò)分樣本數(shù)為4 根據(jù)公式我們得e(T)=(4+7*0.5)/24=0.3125 例子2：如果罰分等于0.5，訓(xùn)練樣本集中樣本數(shù)為24個(gè)，我們構(gòu)建了4個(gè)葉結(jié)點(diǎn)的決策樹，訓(xùn)練樣本集的錯(cuò)分樣本數(shù)為6 根據(jù)公式我們得e(T)=(6+4*0.5)/24=0.3333 當(dāng)罰分等于1時(shí)，例1，2為0.458，0.417 0.5的罰分項(xiàng)表示只要至少能夠改進(jìn)一個(gè)訓(xùn)練記錄的分類，結(jié)點(diǎn)就應(yīng)當(dāng)擴(kuò)充，因?yàn)閿U(kuò)展一個(gè)結(jié)點(diǎn)等價(jià)于總誤差增加0.5，代價(jià)比犯一個(gè)訓(xùn)練錯(cuò)誤小,最小描述