決策樹又稱為判定樹，是運用于分類的一種樹結構，其中的每個内部節點代表對某一屬性的一次測試，每條邊代表一個測試結果，葉節點代表某個類或類的分布。 決策樹的決策過程需要從決策樹的根節點開始，待測資料與決策樹中的特征節點進行比較，并按照比較結果選擇選擇下一比較分支，直到葉子節點作為最終的決策結果。
特征選擇：從訓練資料的特征中選擇一個特征作為目前節點的分裂标準（特征選擇的标準不同産生了不同的特征決策樹算法）。
決策樹生成：根據所選特征評估标準，從上至下遞歸地生成子節點，直到資料集不可分則停止決策樹停止聲場。
剪枝：決策樹容易過拟合，需要剪枝來縮小樹的結構和規模（包括預剪枝和後剪枝）。
實作決策樹的算法包括id3、c4.5算法等。
id3算法是由ross quinlan提出的決策樹的一種算法實作，以資訊論為基礎，以資訊熵和資訊增益為衡量标準，進而實作對資料的歸納分類。
id3算法是建立在奧卡姆剃刀的基礎上：越是小型的決策樹越優于大的決策樹（be simple簡單理論）。
奧卡姆剃刀（occam's razor, ockham's razor），又稱“奧坎的剃刀”，是由14世紀邏輯學家、聖方濟各會修士奧卡姆的威廉（william of occam，約1285年至1349年）提出，他在《箴言書注》2卷15題說“切勿浪費較多東西，去做‘用較少的東西，同樣可以做好的事情’。簡單點說，便是：be simple。
id3算法可用于劃分标準稱型資料，但存在一些問題：
沒有剪枝過程，為了去除過渡資料比對的問題，可通過裁剪合并相鄰的無法産生大量資訊增益的葉子節點;
資訊增益的方法偏向選擇具有大量值的屬性，也就是說某個屬性特征索取的不同值越多，那麼越有可能作為分裂屬性，這樣是不合理的；
隻可以處理離散分布的資料特征
id3算法的核心思想是以資訊增益度量屬性選擇，選擇分裂後資訊增益最大的屬性進行分裂。
資訊熵（entropy）是用來衡量一個随機變量出現的期望值。如果資訊的不确定性越大，熵的值也就越大，出現的各種情況也就越多。
其中，s為所有事件集合，p為發生機率，c為特征總數。注意：熵是以2進制位的個數來度量編碼長度的，是以熵的最大值是log2c。
資訊增益（information gain）是指資訊劃分前後的熵的變化，也就是說由于使用這個屬性分割樣例而導緻的期望熵降低。也就是說，資訊增益就是原有資訊熵與屬性劃分後資訊熵（需要對劃分後的資訊熵取期望值）的內插補點，具體計算法如下：
其中，第二項為屬性a對s劃分的期望資訊。
初始化屬性集合和資料集合
計算資料集合資訊熵s和所有屬性的資訊熵，選擇資訊增益最大的屬性作為目前決策節點
更新資料集合和屬性集合（删除掉上一步中使用的屬性，并按照屬性值來劃分不同分支的資料集合）
依次對每種取值情況下的子集重複第二步
若子集隻包含單一屬性，則為分支為葉子節點，根據其屬性值标記。
完成所有屬性集合的劃分
注意：該算法使用了貪婪搜尋，從不回溯重新考慮之前的選擇情況。
c4.5算法是id3算法的一種改進。
用資訊增益率來選擇屬性，克服了用資訊增益選擇屬性偏向選擇多值屬性的不足
在構造樹的過程中進行剪枝
對連續屬性進行離散化
能夠對不完整的資料進行處理
設樣本集s按離散屬性f的c個不同的取值劃分為c個子集，則這c個子集的資訊熵為：
資訊增益率是資訊增益與資訊熵的比例，如下：
将連續型的屬性變量進行離散化處理形成決策樹的訓練集：
将需要處理的樣本（對應根節點）或樣本子集（對應子樹）按照連續變量的大小從小到大進行排序
假設該屬性對應不同的屬性值共n個，那麼總共有n-1個可能的候選分割值點，每個候選的分割門檻值點的值為上述排序後的屬性值中兩兩前後連續元素的中點
用資訊增益選擇最佳劃分
處理缺少屬性值的一種政策是賦給該節點所有對應訓練執行個體中該屬性最常見的值，另一種複雜的情況是為該節點每個可能出現的值賦予一個機率。
<a href="http://www.cnblogs.com/leoo2sk/archive/2010/09/19/decision-tree.html">http://www.cnblogs.com/leoo2sk/archive/2010/09/19/decision-tree.html</a>
<a href="http://blog.csdn.net/google19890102/article/details/28611225">http://blog.csdn.net/google19890102/article/details/28611225</a>
<a href="http://www.cnblogs.com/biyeymyhjob/archive/2012/07/23/2605208.html">http://www.cnblogs.com/biyeymyhjob/archive/2012/07/23/2605208.html</a>
決策樹