分類基本概念、決策樹與模型評估.ppt

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

2、學(xué)公式的形式提供,數(shù)據(jù)分類一個兩步過程 (2),第二步，使用模型，對將來的或未知的對象進行分類 首先評估模型的預(yù)測準(zhǔn)確率 對每個測試樣本，將已知的類標(biāo)號和該樣本的學(xué)習(xí)模型類預(yù)測比較 模型在給定測試集上的準(zhǔn)確率是正確被模型分類的測試樣本的百分比 測試集要獨立于訓(xùn)練樣本集，否則會出現(xiàn)“過分適應(yīng)數(shù)據(jù)”的情況 如果準(zhǔn)確性能被接受，則分類規(guī)則就可用來對新數(shù)據(jù)進行分類,有監(jiān)督的學(xué)習(xí) VS. 無監(jiān)督的學(xué)習(xí),有監(jiān)督的學(xué)習(xí)（用于分類） 模型的學(xué)習(xí)在被告知每個訓(xùn)練樣本屬于哪個類的“監(jiān)督”下進行 新數(shù)據(jù)使用訓(xùn)練數(shù)據(jù)集中得到的規(guī)則進行分類 無監(jiān)督的學(xué)習(xí)（用于聚類） 每個訓(xùn)練樣本的類編號是未知的，要學(xué)習(xí)的類集合或數(shù)量也

3、可能是事先未知的 通過一系列的度量、觀察來建立數(shù)據(jù)中的類編號或進行聚類,分類模型的構(gòu)造方法,1.機器學(xué)習(xí)方法： 決策樹法 規(guī)則歸納 2.統(tǒng)計方法：知識表示是判別函數(shù)和原型事例 貝葉斯法 非參數(shù)法(近鄰學(xué)習(xí)或基于事例的學(xué)習(xí)) 3.神經(jīng)網(wǎng)絡(luò)方法： BP算法,模型表示是前向反饋神經(jīng)網(wǎng)絡(luò)模型 4.粗糙集(rough set)知識表示是產(chǎn)生式規(guī)則,一個決策樹的例子,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K, 80K,Splitting Attributes,訓(xùn)練數(shù)據(jù),模型: 決策樹,決策樹的另一個例子,ca

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

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

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

7、axInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced, 80K, 80K,測試數(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é)點 t相關(guān)聯(lián)的訓(xùn)練記錄集 算法步驟: 如果Dt 中所有記錄都屬于同一個類 yt, 則t是葉結(jié)點，用yt標(biāo)記 如果 Dt 中包含屬于多個類的記錄，則選擇一個屬

8、性測試條件，將記錄劃分成較小的子集。對于測試條件的每個輸出，創(chuàng)建一個子結(jié)點，并根據(jù)測試結(jié)果將Dt中的記錄分布到子結(jié)點中。然后，對于每個子結(jié)點，遞歸地調(diào)用該算法,Dt,?,Hunt算法,Dont Cheat,決策樹,Hunt算法采用貪心策略構(gòu)建決策樹. 在選擇劃分數(shù)據(jù)的屬性時，采取一系列局部最優(yōu)決策來構(gòu)造決策樹. 決策樹歸納的設(shè)計問題 如何分裂訓(xùn)練記錄 怎樣為不同類型的屬性指定測試條件? 怎樣評估每種測試條件? 如何停止分裂過程,決策樹,Hunt算法采用貪心策略構(gòu)建決策樹. 在選擇劃分數(shù)據(jù)的屬性時，采取一系列局部最優(yōu)決策來構(gòu)造決策樹. 決策樹歸納的設(shè)計問題 如何分裂訓(xùn)練記錄 怎樣為不同類型的屬性

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

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

11、不純性的測量,Gini Entropy classification error,不純性的測量: GINI,給定結(jié)點t的Gini值計算 : (p( j | t) 是在結(jié)點t中，類j發(fā)生的概率). 當(dāng)類分布均衡時，Gini值達到最大值 (1 - 1/nc) 相反當(dāng)只有一個類時，Gini值達到最小值0,計算 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)一個結(jié)點 p 分割成 k 個部分 (孩子), 劃分的質(zhì)量可由下面公式計算 ni = 孩子結(jié)點 i的記錄數(shù), n = 父結(jié)點 p的記錄數(shù).,二元屬性: 計算 GINI,對于二元屬性，結(jié)點被劃分成兩個部分 得到的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)稱屬性:計算Gini,多路劃分 二元劃分 一般多路劃分的Gini值比二元劃分小，這一結(jié)果并不奇怪，因為二元劃分實際上合并了多路劃分的某些輸出，自然降低了子集的純度,Multi-way split,Two-way split (find best partition of values),連續(xù)屬性: 計算 Gini,使用二元劃分 劃分點v選擇 N個記錄中所有屬性值作為劃分點 對每個劃分進行類計數(shù), A v and A v 計算每個候選點v的Gini指標(biāo)，并從中選擇具有最小值的候選劃分點 時間復(fù)雜度為(n2),連續(xù)屬性: 計算 Gini.,降低計算復(fù)雜性的方法, 將記

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

15、H對任意q連續(xù) 極值性：當(dāng)q都等于1K時 H達到最大值logK,熵-定義,基于 Information Gain的劃分,給定結(jié)點t的 Entropy值計算 : (p( j | t) 是在結(jié)點t中，類j發(fā)生的概率). 當(dāng)類分布均衡時， Entropy值達到最大值 (log nc) 相反當(dāng)只有一個類時，Gini值達到最小值0 Entropy 與 GINI相似,計算 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é)點 i的記錄數(shù), n = 結(jié)點 p的記錄數(shù). 在 ID3 and C4.5中使用,基于 Information Gain的劃分.,增益率（Gain Ratio）: 熵和Gini指標(biāo)等不純性趨向于有利于具有大量不同值的屬性!如：利用雇員id產(chǎn)生更純的劃分，但它卻毫無用處 每個劃分

17、相關(guān)聯(lián)的記錄數(shù)太少，將不能做出可靠的預(yù)測 解決該問題的策略有兩種： 限制測試條件只能是二元劃分 使用增益率。K越大Split Info越大增益率越小,基于 Classification Error的劃分,給定結(jié)點t的 Classification Error值計算 : 當(dāng)類分布均衡時， error值達到最大值 (1 - 1/nc) 相反當(dāng)只有一個類時， error值達到最小值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)建決策樹. 在選擇劃分數(shù)據(jù)的屬性時，采取一系列局部最優(yōu)決策來構(gòu)造決策樹. 決策樹歸納的設(shè)計問題 如何分裂訓(xùn)練記錄 怎樣為不同類型的屬性指定測試條件? 怎樣評估每種測試條件? 如何停止分裂過程,停止分裂過程,當(dāng)所有的記錄屬于同一類時，停止分裂 當(dāng)所有的記錄都有相同的屬性時，停止分裂 提前終止樹的生長,三種著名的決策樹,Cart：基本的決策樹算法 Id3：利用增益

19、比不純性，樹采用二叉樹，停止準(zhǔn)則為當(dāng)所有的記錄屬于同一類時，停止分裂，或當(dāng)所有的記錄都有相同的屬性時，停止分裂 C4.5：id3的改進版本，也是最流行的分類數(shù)算法。采用多重分支和剪枝技術(shù)。,決策樹,特點: 決策樹是一種構(gòu)建分類模型的非參數(shù)方法 不需要昂貴的的計算代價 決策樹相對容易解釋 決策樹是學(xué)習(xí)離散值函數(shù)的典型代表 決策數(shù)對于噪聲的干擾具有相當(dāng)好的魯棒性 冗余屬性不會對決策樹的準(zhǔn)確率造成不利影響 數(shù)據(jù)碎片問題。隨著數(shù)的生長，可能導(dǎo)致葉結(jié)點記錄數(shù)太少，對于葉結(jié)點代表的類，不能做出具有統(tǒng)計意義的判決 子樹可能在決策樹中重復(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),模型過分擬合和擬合不足,分類模型的誤差大致分為兩種： 訓(xùn)練誤差：是在訓(xùn)練記錄上誤分類樣本比例 泛化誤差：是模型在未知記錄上的期望誤差 一個好的分類模型不僅要能夠很好的擬合訓(xùn)練數(shù)據(jù)，而且對未知樣本也要能準(zhǔn)確分類。 換句話說，一個好的分類模型必須具有低訓(xùn)練誤差和低泛化誤差。 當(dāng)訓(xùn)練數(shù)據(jù)擬合太好的模型，其泛化誤差可能比具有較高訓(xùn)練誤差的模型高，這種情況成為模型過分擬合,模型過分擬合和擬合不足,當(dāng)決策樹很小時，訓(xùn)練和檢驗誤差都很大，這種情況稱為模型擬合不足。出現(xiàn)擬合不足的原因是模型尚未學(xué)習(xí)到數(shù)據(jù)的真實結(jié)構(gòu)。 隨著決策樹中結(jié)點數(shù)的增加，模型的訓(xùn)

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

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

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

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

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