基本概念、決策樹與模型評(píng)價(jià)(ppt 92頁).ppt

數(shù)據(jù)挖掘分類 基本概念 決策樹與模型評(píng)價(jià) 第4章分類 基本概念 決策樹與模型評(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ù)學(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ù)量也可能是事先未知的通過一系列的度量 觀察來建立數(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 粗糙集 roughset 知識(shí)表示是產(chǎn)生式規(guī)則 一個(gè)決策樹的例子 Refund MarSt TaxInc YES NO NO NO Yes No Married Single Divorced 80K 80K SplittingAttributes 訓(xùn)練數(shù)據(jù) 模型 決策樹 決策樹的另一個(gè)例子 categorical 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)行分類通過將樣本的屬性值與決策樹相比較 為了對(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ù) DecisionTree 一個(gè)決策樹的例子 Refund MarSt TaxInc YES NO NO NO Yes No Married Single Divorced 80K 80K SplittingAttributes 訓(xùn)練數(shù)據(jù) 模型 決策樹 應(yīng)用決策樹進(jìn)行分類 測(cè)試數(shù)據(jù) Startfromtherootoftree 應(yīng)用決策樹進(jìn)行分類 測(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 TaxInc YES NO NO NO Yes No Married Single Divorced 80K 80K 測(cè)試數(shù)據(jù) AssignCheatto No 決策樹分類 DecisionTree 決策樹 有許多決策樹算法 Hunt算法信息增益 Informationgain ID3 增益比率 Gainration C4 5 基尼指數(shù) Giniindex 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è)屬性測(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算法 Don tCheat 決策樹 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)練記錄怎樣為不同類型的屬性指定測(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ù)屬性的劃分 多路劃分 vi A vi 1 i 1 k 二元?jiǎng)澐?A v or A v 考慮所有的劃分點(diǎn) 選擇一個(gè)最佳劃分點(diǎn)v 基于連續(xù)屬性的劃分 決策樹 決策樹歸納的設(shè)計(jì)問題如何分裂訓(xùn)練記錄怎樣為不同類型的屬性指定測(cè)試條件 怎樣評(píng)估每種測(cè)試條件 如何停止分裂過程 怎樣選擇最佳劃分 在劃分前 10個(gè)記錄class0 10個(gè)記錄class1 怎樣選擇最佳劃分 選擇最佳劃分的度量通常是根據(jù)劃分后子結(jié)點(diǎn)不純性的程度 不純性的程度越低 類分布就越傾斜結(jié)點(diǎn)不純性的度量 不純性大 不純性小 怎樣找到最佳劃分 B Yes No NodeN3 NodeN4 A Yes No NodeN1 NodeN2 劃分前 Gain M0 M12vsM0 M34 結(jié)點(diǎn)不純性的測(cè)量 GiniEntropyclassificationerror 不純性的測(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 0P C2 6 6 1Gini 1 P C1 2 P C2 2 1 0 1 0 P C1 1 6P C2 5 6Gini 1 1 6 2 5 6 2 0 278 P C1 2 6P 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 Yes No NodeN1 NodeN2 Gini N1 1 5 6 2 2 6 2 0 194Gini N2 1 1 6 2 4 6 2 0 528 Ginisplit 7 12 0 194 5 12 0 528 0 333 標(biāo)稱屬性 計(jì)算Gini 多路劃分二元?jiǎng)澐忠话愣嗦穭澐值腉ini值比二元?jiǎng)澐中?這一結(jié)果并不奇怪 因?yàn)槎獎(jiǎng)澐謱?shí)際上合并了多路劃分的某些輸出 自然降低了子集的純度 Multi waysplit Two waysplit findbestpartitionofvalues 連續(xù)屬性 計(jì)算Gini 使用二元?jiǎng)澐謩澐贮c(diǎn)v選擇N個(gè)記錄中所有屬性值作為劃分點(diǎn)對(duì)每個(gè)劃分進(jìn)行類計(jì)數(shù) A vandA v計(jì)算每個(gè)候選點(diǎn)v的Gini指標(biāo) 并從中選擇具有最小值的候選劃分點(diǎn)時(shí)間復(fù)雜度為 n2 連續(xù)屬性 計(jì)算Gini 降低計(jì)算復(fù)雜性的方法 將記錄進(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ù)性 H對(duì)任意q連續(xù)極值性 當(dāng)q都等于1 K時(shí)H達(dá)到最大值logK 熵 定義 基于InformationGain的劃分 給定結(jié)點(diǎn)t的Entropy值計(jì)算 p j t 是在結(jié)點(diǎn)t中 類j發(fā)生的概率 當(dāng)類分布均衡時(shí) Entropy值達(dá)到最大值 lognc 相反當(dāng)只有一個(gè)類時(shí) Gini值達(dá)到最小值0Entropy與GINI相似 計(jì)算Entropy的例子 P C1 0 6 0P C2 6 6 1Entropy 0log0 1log1 0 0 0 P C1 1 6P C2 5 6Entropy 1 6 log2 1 6 5 6 log2 1 6 0 65 P C1 2 6P C2 4 6Entropy 2 6 log2 2 6 4 6 log2 4 6 0 92 基于InformationGain的劃分 InformationGain ni 孩子結(jié)點(diǎn)i的記錄數(shù) n 結(jié)點(diǎn)p的記錄數(shù) 在ID3andC4 5中使用 基于InformationGain的劃分 增益率 GainRatio 熵和Gini指標(biāo)等不純性趨向于有利于具有大量不同值的屬性 如 利用雇員id產(chǎn)生更純的劃分 但它卻毫無用處每個(gè)劃分相關(guān)聯(lián)的記錄數(shù)太少 將不能做出可靠的預(yù)測(cè)解決該問題的策略有兩種 限制測(cè)試條件只能是二元?jiǎng)澐质褂迷鲆媛?K越大SplitInfo越大增益率越小 基于ClassificationError的劃分 給定結(jié)點(diǎn)t的ClassificationError值計(jì)算 當(dāng)類分布均衡時(shí) error值達(dá)到最大值 1 1 nc 相反當(dāng)只有一個(gè)類時(shí) error值達(dá)到最小值0 例子 P C1 0 6 0P C2 6 6 1Error 1 max 0 1 1 1 0 P C1 1 6P C2 5 6Error 1 max 1 6 5 6 1 5 6 1 6 P C1 2 6P C2 4 6Error 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 利用增益比不純性 樹采用二叉樹 停止準(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ù)問題 Samesubtreeappearsinmultiplebranches 決策邊界 斜決策樹 模型過分?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)練誤差和檢驗(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)集中記錄的誤分類 噪聲導(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合可能出現(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)候選屬性多 訓(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ù)雜度 奧卡姆剃刀 Occam sRazor 給定兩個(gè)具有相同泛化誤差的模型 較簡(jiǎn)單的模型比復(fù)雜的模型更可取因?yàn)閺?fù)雜模型中的附加成分很大程度上是偶然的擬合 因此 分類模型評(píng)估應(yīng)把模型復(fù)雜度考慮進(jìn)去方法 悲觀誤差估計(jì) 最小描述長(zhǎng)度原則 MDL 悲觀誤差評(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 4170 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ò)誤小 最小描述長(zhǎng)度 MDL Cost Model Data Cost Data Model Cost Model Cost是傳輸總代價(jià) 最小化cost值 Cost Data Model 是誤分類記錄編碼的開銷 Cost Model 是模型編碼的開銷 使用確認(rèn)集 該方法中 不是用訓(xùn)練集估計(jì)泛化誤差 而是把原始的訓(xùn)練數(shù)據(jù)集分為兩個(gè)較小的子集 一個(gè)子集用于訓(xùn)練 而另一個(gè)稱為確認(rèn)集 用于估計(jì)泛化誤差 該方法為評(píng)估模型在未知樣本上的性能提供了較好辦法 處理決策樹中的過分?jǐn)M合 先剪枝 EarlyStoppingRule 樹增長(zhǎng)算法在產(chǎn)生完全擬合整個(gè)訓(xùn)練數(shù)據(jù)集的之前就停止決策樹的生長(zhǎng)為了做到這一點(diǎn) 需要采用更具限制性的結(jié)束條件 當(dāng)結(jié)點(diǎn)的記錄