基本算法思路:
记号如下:
$T$: 树, $S$: 熵, $B$: 特征
$T_{ij}$: 第$i$层第$j$棵子树
$S_{ij}$: 第$i$层第$j$棵子树的熵
$\Delta S_{ij}^k$: 第$i$层第$j$棵子树的$k$划分产生的信息增益
$B_j^i$: 第$i$次划分后剩余的特征中的第$j$个特征
$step1$: 所有数据点作为根子树$T_{11}$,遍历特征${B_j^0}$,计算特征$Bj^0$划分产生的所有子树${T_{2k}}$的熵,算得${\Delta S_{11}^j }$
$step2$: 选择$\Delta S_{11}^j$最大的特征$B_j^0$进行划分,产生子树${ T_{2k} }$,剩余可选特征集${B_j^1}$
$step3$: 对于子树$T_{2k}$重复step1-2,直到满足step4的条件
$step4$: $1.$ 子树数据点个数小于指定值 或者$2.$ 子树达到指定深度 或者$3.$ 子树熵值低于指定值 或者$4.$ 无特征可继续分裂