决策树

信息熵: 随机变量的不确定性的度量.
$H(X)=-\sum_{i=1}^{n} p_{i} \log p_{i}$
$\leq H(X) \leq \log n$
信息增益: 得知特征X的信息而使得类Y的信息的不确定性减少的程度.
$g (Y, X) = H (Y) ? H (Y │ X)$

信息增益算法

输入:训练数据集D和特征A
输出:特征A对训练数据集D的信息增益g(D,A)

计算数据集D的经验熵H(D)
计算特征A对数据D的经验条件熵H(D|A)
$H(D)=-\sum_{i=1}^{n} \frac{\left|C_{k}\right|}{|D|} \log _{2} \frac{\left|C_{k}\right|}{|D|}$
计算信息增益
$g (D, A) = H (D) ? H (D │ A)$

ID3算法

思想: 在决策树各个节点上应用信息增益准则选择特征, 递归地构建决策树.
方法:从根节点出发, 对结点计算所有可能的特征的信息增益, 选择信息增益最大的特征作为节点的特征, 并递归构建决策树.
(ID3相当于用极大似然法进行概率模型的选择)
输入: 训练数据集D, 特征集A, 阈值ε
输出: 决策树T

若D中所有实例属于同一类 $C_k$ , 则T为单节点数, 并将类 $C_k$ 作为该节点的类标记,返回T.
若A=?, 则T为单节点树, 并将D中实例数最大的类 $C_k$ 作为该节点的类标记, 返回T.
否则,安装信息增益算法, 计算A中各特征对D的信息增益, 选择信息增益最大的特征 $A_g$ .
若A_g的信息增益小于阈值ε,则设置T为单节点树, 并将D 中实例数最大的类C_k作为该节点的类标记, 返回T.
否则,对 $A_g$ 的每一可能值 $a_i$ , 依 $A_g=a_i$ 将D分割为若干非空子集 $D_i$ , 将 $D_i$ 中实例数最大的类作为标记,构建子节点, 由结点及其子结点构成树T, 返回T.
对第i个子结点, 以 $D_i$ 为训练集, 以A- ${A_g}$ 为特征集, 递归调用(1)~(5), 得到子树 $T_i$ , 返回 $T_i$

Cart 树

Cart树是二叉树,每次分裂产生两个子节点.

Cart 分类树

采用Gini指数选择最优特征, Gini指数反应样本集合的不确定性
$\operatorname{Gini}(p)=\sum_{i=1}^{n} p_{k}\left(1-p_{k}\right)=1-\sum_{k=1}^{K} p_{k}^{2}$
其中假设有k个类, $p_k$ 表样本点属于第k个类的概率.
在特征A的条件下,集合D的基尼指数定义为:
$\operatorname{Gini}(D, A)=\frac{\left|D_{1}\right|}{|D|} \operatorname{Gini}\left(D_{1}\right)+\frac{\left|D_{2}\right|}{|D|} \operatorname{Gini}\left(D_{2}\right)$
选取Gini指数最小的特征作为划分特征

CART回归树

思想: 将输入空间划分为M个单元(R1, R2, …, $R_M$ ), 并且在每个单元 $R_m$ 上有一个固定的输出值 $c_m$
回归模型:
$f(x)=\sum_{m=1}^{M} c_{m} I\left(x \in R_{m}\right)$
训练误差:
$\sum_{x_{i} \in R_{m}}\left(y_{i}-f\left(x_{i}\right)\right)^{2}$
单元 $R_m$ 上的最优输出值 $c_m^*$
$c_{m}^{*}=\operatorname{ave}\left(y_{i} \mid x_{i} \in R_{m}\right)$
空间划分
采用启发式,选择第j个变量 $x^{j}$ 和它取值s, 作为切分变量和切分点,并定义两个区域
$R_{1}(j, s)=\left\{x \mid x^{(j)} \leq s\right\}, \quad R_{2}(j, s)=\left\{x \mid x^{(j)} \geq s\right\}$
最优化切分点
$\min _{j, s}\left[\min _{c_{1}} \sum_{x_{i} \in R_{1}(j, s)}\left(y_{i}-c_{1}\right)^{2}+\min _{c_{2}} \sum_{x_{i} \in R_{2}(j, s)}\left(y_{i}-c_{2}\right)^{2}\right]$