本文討論的決策樹主要是基於id3演算法實現的離散決策樹生成。id3演算法的基本思想是貪心演算法，採用自上而下的分而治之的方法構造決策樹。首先檢測訓練資料集的所有特徵，選擇資訊增益最大的特徵a建立決策樹根節點，由該特徵的不同取值建立分枝，對各分枝的例項子集遞迴，用該方法建立樹的節點和分枝，直到某一子集中的資料都屬於同一類別，或者沒有特徵可以在用於對資料進行分割。
id3演算法總是選擇具有最高資訊增益(或最大熵壓縮)的屬性作為當前結點的測試屬性。該屬性使得結果劃分中的樣本分類所需的資訊量最小，並反映劃分的最小隨機性或「不純性」。這種資訊理論方法使得對乙個物件分類所需的期望測試數目達到最小，並盡量確保一棵簡單的(但不必是最簡單的)樹來刻畫相關的資訊。
在id3演算法中，計算資訊增益時，由於資訊增益存在乙個內在偏置，它偏袒具有較多值的屬性，太多的屬性值把訓練樣例分割成非常小的空間。因此，這個屬性可能會有非常高的資訊增益，而且被選作樹的根結點的決策屬性，並形成一棵深度只為一級但卻非常寬的樹，這棵樹可以理想地分類訓練資料。但是這個決策樹對於測試資料的分類效能可能會相當差，因為它過分地完美地分割了訓練資料，不是乙個好的分類器。
在關於id3演算法的研究中，通過對五種包含噪音的學習樣例的實驗發現，多數情況下過度擬合導致決策樹的精度降低了10%一25%。過度擬合不僅影響決策樹對未知例項的分類精度，而且還會導致決策樹的規模增大。一方面，葉子節點隨分割不斷增多。
在極端的情況下，在一棵完成分割的決策樹中，每個葉子節點中只包含乙個例項。此時決策樹在學習樣例上的分類精度達到100%，而其葉子節點的數目等於學習樣例中例項的數目。但是顯然這棵決策樹對任何未見的例項都是毫無意義的。
另一方面，決策樹不斷向下生長，導致樹的深度增加。因為每一條自根節點到葉子節點的路徑都對應一條規則，所以樹的深度越大，其對應的規則越長。作為一種蘊含於學習樣例中的知識，這樣一組過長的規則集合是很難被人理解的。
過度擬合現象的存在，無論是對決策樹的分類精度，還是對其規模以及可理解性都產生了不利的影響。因此對與決策樹的剪枝是非常有必要的。
一般情況下可以使用如下兩類方法來減小決策樹的規模:
(l)在決策樹完美分割學習樣例之前，停止決策樹的生長。這種提早停止樹生長的
方法，稱為預剪枝方法。
(2)與預剪枝方法盡量避免過度分割的思想不同，一般情況下即使決策樹可能出現過度擬合現象，演算法依然允許其充分生長。在決策樹完全生長之後，通過特定標準去掉原決策樹中的某些子樹。通常稱這種方法為後剪枝方法。
預剪枝方法實際上是對決策樹停止標準的修改。在原始的id3演算法中，節點的分割一直到節點中的例項屬於同一類別時才停止。對於包含較少例項的節點，可能被分割為單一例項節點。
為了避免這種情況，我們給出乙個停止閾值a。當由乙個節點分割導致的最大的不純度下降小於a時，就把該節點看作是乙個葉子節點。在該方法中，閾值a的選擇對決策樹具有很大的影響。
當閾值a選擇過大時，節點在不純度依然很高時就停止分割了。此時由於生長不足，導致決策樹過小，分類的錯誤率過高。假設在乙個兩類問題中，根節點root一共包含100個學習樣例，其中正例和負例均為50。
並且使用屬性b可以將正例與負例完全分開，即決策樹在學習樣例上的分類精度r(t)=100%。由資訊增益公式可知，使用屬性b分割節點可以得到不純度下降的最大值0.5。
如果設a=0.7，因為gain(root，a)=0.5<0.
7，所以根節點root不需要分割。此時導致決策樹在學習樣例上的分類精度下降為r(t)=50%。當閾值a選擇過小時，例如a近似為0，節點的分割過程近似等同於原始的分割過程。
由此可見，預剪枝方法雖然原理簡單，但是在實際應用中，閾值a的選擇存在相當大的主觀性。如何精確的給出適當的閾值a以獲得適當規模的決策樹是十分困難的。
決策樹是一種樹形結構。一棵樹是乙個或者多個節點的有限集合t，使得
1.有乙個特別指定的節點，叫做樹的根節點;
2.除根節點以外，剩餘的節點被劃分成m>=0個不相交的集合tl，…，tm，而且每乙個集合也都是樹。樹tl，…，tm稱為這個根節點的子樹。
根據上述樹的定義，可以直觀地將決策樹的後剪枝看作是去掉某些子樹中除根節點外所有節點的過程，如圖1所示。移除子樹後，還需要對新生成的葉子節點賦予乙個類別標誌，一般是葉子節點中所佔比例最大的類別標誌。
圖1 決策樹剪枝過程
代價複雜度剪枝過程分成兩個階段:第一階段，首先由原決策樹通過某種剪枝策略生成一系列決策樹t0，tl，…，tk。其中t。
是由決策樹生成演算法推導出來的屬性決策樹，ti十1是依次刪除ti的一棵或者多棵後生成的。重複此過程，直到最後的決策樹tk只含有乙個葉子結點。
第二階段，我們對上一階段得到的決策樹進行評估，最終選擇一棵最好的作為剪枝後的決策樹。
考慮包含n個樣例的訓練集合，通過決策樹生成演算法，如id3，我們可以推導出一棵屬性決策樹。假定這棵決策樹會將其中的e個樣例錯誤分類，再定義l(t)是決策樹t中葉子結點的數目，等人定義決策樹t的代價複雜度為
對決策樹t的一棵子樹s，我們將能劃分到子樹s中的所有樣例的最普遍類別標籤稱之為最可能葉子。從原決策樹t。開始，為了從決策樹ti產生ti十1，我們遍歷每乙個非葉子子樹ti來找到最小的a值，用子樹中最可能葉子代替一棵或多棵值為a的子樹。
在第二階段，我們從上一階段生成的一系列決策樹中，以可靠性為標準找出一棵最好的決策樹。如果繼續使用生成決策樹時的訓練樣例集合對決策樹的錯誤率進行評估，觀察錯誤率可能過於樂觀，也就是說，對於未見樣例的錯誤率可能高於此值。因此，我們使用乙個單獨的測試樣例集合，其中包含n』個樣例，用於估計對子樹ti的分類錯誤率。
假設e』是所有子樹ti中最小的觀察錯誤率，定義e』的標準錯誤為
最後我們從所有子樹中選擇觀察錯誤數不超過e』+se伍』)中最小的子樹，作為剪枝後的子樹。
實踐教學的重要性與必要性
摘要 數學課程標準 指出 有效的數學學習活動不能單純地依賴模仿記憶，動手實踐 自主 與合作交流是學生學習數學的重要方式 教學的質量和高效一直是學校和教師用盡心思和方法去追求的，那麼在我們的傳統課堂上增加什麼的分量會讓教學進行的更順利，甚至達到事半功倍的效果呢，那就是實踐教學。關鍵詞 實踐教學 有效教...
建築節能的內涵與必要性
一 建築節能的內涵 建築節能是指在建築物的規劃 設計 新建 改建 擴建 改造和使用過程中，執行節能標準，採用節能型的技術 工藝 裝置 材料和產品，提高保溫隔熱性能和採暖供熱 空調製冷制熱系統效率，加強建築物用能系統的執行管理，利用可再生能源，在保證室內熱環境質量的前提下，減少供熱 空調製冷制熱 照明...
推行表現性評價方法的必要性 張丹
學員編號 中等職業學校專業骨幹教師 國家級 培訓 推行表現性價方法的必要性 培訓專業 建設與管理 學員姓名張丹 指導教師李書琴 完成日期 2013年6月 中國陝西楊凌 推行表現性評價方法的必要性 張丹洛陽鐵路資訊工程學校 摘要 目前中職學校的學風令人堪憂，這與中職生生源狀況和他們的學習習慣有關，也與...