決策樹算法及其應用(ppt 41頁)

決策樹算法及其應用目錄：
1、概述
2、預備知識
3、捕捉變化數據的挖掘方法
4、小結

決策樹算法及其應用內容提要：
決策樹算法：
基本算法（貪心算法）
自上而下分而治之的方法
開始時，所有的數據都在根節點
屬性都是種類字段 (如果是連續的，將其離散化)
所有記錄用所選屬性遞歸的進行分割
屬性的選擇是基於一個啟發式規則或者一個統計的度量 (如, information gain)
停止分割的條件
一個節點上的數據都是屬於同一個類別
沒有屬性可以再用於對數據進行分割
……

兩種剪枝標準：
最小描述長度原則(MDL)
思想：最簡單的解釋最期望的
做法：對Decision-Tree 進行二進位編碼，編碼所需二進位最少的樹即為“最佳剪枝樹”
期望錯誤率最小原則
思想：選擇期望錯誤率最小的子樹進行剪枝
對樹中的內部節點計算其剪枝/不剪枝可能出現的期望錯誤率，比較後加以取舍
……

算法比較：
Sprint: 傳統的二階段“構造－剪枝”算法
Public(1):用保守的估計值1取代欲擴展節點的代價下界
Public(S):考慮具有分裂點的子樹，同時計算為確定分裂節點及其屬性的代價下界
Public(V):比前者準確，需計算確定結點上屬性值的代價下界

..............................