決策樹的生成—ID3算法

---

算法由來：

決策樹算法最開始是由Hunt Earl B提出的CLS(Concept Learning System)，但是沒有給出采用什么方法選擇最優特征，后面羅斯昆（J. Ross Quinlan）提出ID3算法，使用 [信息增益] 確定最優特征，之后羅斯昆又對ID3算法進行了優化改進，得到 C4.5算法，并用 信息增益比來確定最優特征。兩種算法本質是差不多的，只是確定最優特征的方法不同，ID3算法偏向于選擇數量較多的某一特征，C4.5算法偏向于某一特征單位數量的選擇。

ID3算法

輸入：訓練數據集D、特征集A、閾值$\in$
輸出：決策樹T

判斷T是否需要選擇特征生成決策樹：

——若D中所有實例屬于同一類，則T為單結點樹，記錄實例類別$C_k$以此作為該結點的類標記，并返回T:
——若D中所有實例無任何特征$(A=?)$,則T為單結點樹，記錄D中實例個數最多類別$C_k$,以此作為該結點的類標記，并返回T;

否則，計算A中各特征的信息增益，并選擇信息增益最大的特征Ag:

——若Ag的信息增益小于，則T為單結點樹，記錄D中實例個數最多類別$C_k$,以此作為該結點的類標記，并返回T;
——否則，按照Ag的每個可能值$a_i$,將D分為若干非空子集$D_i$,將$D_i$中實例個數最多的類別作為標記，構建子結點，以結點和其子節點構成T,并返回T;

第i個子結點，以$D_i$為訓練集，A一Ag為特征集合，遞歸地調用以上步驟，得到子樹$T_i$并返回。

決策樹思想的核心在于當每個迭代出來的訓練集計算出的最大信息增益小于閾值時，生成單結點樹才可終止。

---

例題：

計算出來的各個特征的經驗熵、經驗條件熵、信息增益如下：

最大信息增益為自己的房子這個特征，分為兩類：有房子和無房子，有房子的設置單一節點為同意貸款，沒有房子的訓練數據集作為新的訓練數據集$D_2$,再從剩下的特征中計算信息增益，選擇最大信息增益的特征。

以特征：年齡為$A_1$, 有工作為$A_2$, 信貸情況為$A_3$

信息增益公式：
$$g\left(D_2,A_i\right)=H\left(D_2\right)?H\left(D_2\mid A_i\right)$$
經驗熵：
$$\begin{array}{rl}H\left(D_2\right)& =?\frac{6}{9}{\log }_2\left(\frac{6}{9}\right)?\frac{3}{9}{\log }_2\left(\frac{3}{9}\right)\\ & =0.918\end{array}$$
特征：年齡

計算：

青年：

$$\begin{array}{rl}& w_1=\frac{\left|D_{21}\right|}{\left|D_2\right|}=\frac{4}{9}\\ & H\left(D_{21}\right)=?\frac{1}{4}{\log }_2\frac{1}{4}?\frac{3}{4}{\log }_2\frac{3}{4}=0.811\end{array}$$
? 中年：
$$\begin{array}{rl}& w_2=\frac{\left|D_{21}\right|}{\left|D_2\right|}=\frac{2}{9}\\ & H\left(D_{22}\right)=0\end{array}$$
? 老年：
$$\begin{array}{rl}& w_3=\frac{\left|D_{23}\right|}{\left|D_2\right|}=\frac{3}{9}\\ & H\left(D_{23}\right)=?\frac{2}{3}{\log }_2\frac{2}{3}?\frac{1}{3}{\log }_2\frac{1}{3}=0.918\end{array}$$
經驗條件熵：
$$\begin{array}{rl}H\left(D_2\mid A_1\right)& =w_{1}H\left(D_{21}\right)+w_{2}H\left(D_{22}\right)+w_{3}H\left(D_{23}\right)\\ & =0.360+0+0.307\\ & =0.667\end{array}$$
特征：是否有工作

計算：
有工作：
$$\begin{array}{rl}& w_1=\frac{\left|D_{22}\right|}{\left|D_2\right|}=\frac{3}{9}\\ & H\left(D_{22}\right)=0\end{array}$$
? 沒有工作：
$$\begin{array}{rl}& w_2=\frac{\left|D_{22}\right|}{\left|D_2\right|}=\frac{6}{9}\\ & H\left(D_{22}\right)=0\end{array}$$
經驗條件熵：
$$H(D_2|A_3)=w_{1}H(d_{21})+w_{2}H(D_{22})=0$$

特征：信貸情況

計算：

非常好：

$$\begin{array}{rl}& w_1=\frac{\left|D_{23}\right|}{\left|D_2\right|}=\frac{1}{9}\\ & H\left(D_{23}\right)=0\end{array}$$
? 好：
$$\begin{array}{rl}& w_2=\frac{\left|D_{23}\right|}{\left|D_2\right|}=\frac{3}{9}\\ & H\left(D_{23}\right)=?\frac{2}{3}{\log }_2\frac{2}{3}?\frac{1}{3}{\log }_2\frac{1}{3}\end{array}$$
? 老年：
$$\begin{array}{rl}& w_1=\frac{\left|D_{23}\right|}{\left|D_2\right|}=\frac{5}{9}\\ & H\left(D_{23}\right)=?\frac{1}{5}{\log }_2\frac{1}{5}?\frac{4}{5}{\log }_2\frac{4}{5}\end{array}$$
經驗條件熵：
$$\begin{array}{rl}H\left(D_2\mid A_3\right)& =w_{1}H\left(D_{21}\right)+w_{2}H\left(D_{22}\right)+w_{3}H\left(D_{23}\right)=0.444\end{array}$$
綜合：
比較發現，特征為：是否有工作信息增益最大，所以下一個特征選它。

通過這個例子，整顆決策樹只用了兩個特征，他們的子集都屬于一個類別的，對于有房子都是同意貸款，對于沒有房子都是不同意貸款，滿足單一葉結點，決策樹生成。

總結

以上是生活随笔為你收集整理的决策树的生成—ID3算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。