决策树的模型

特征的选择

决定用哪个特征来划分特征空间。通过信息增益选取对训练数据具有分类能力的特征。

信息增益g(D,A)定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即

g(D, A) = H(D) - H(D|A)

信息熵增益准则的特征选择方法：对训练数据集（或子集）D，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。

生成最优决策树是NP完全问题。因此使用启发式方法，生成次最优决策树。即递归选择最优特征。

生成的决策树容易发生过拟合，需要修剪。决策树的生成是寻找局部最优的决策树。决策树的修剪则是寻找全局最优的决策树。

决策树的剪枝往往通过极小化决策树整体的损失函数来实现定义： T：修剪前的决策树 |T|：T的叶子结点树 t：T的某个叶结点 $N_t$ ：叶结点t的样本数 $N_{tk}$ ：叶结点t的样本中标签为k的样本树 $H_t(T)$ ：叶结点t上的经验熵 a：参数， $a \ge 0$ 损失函数：

\begin{aligned} C_a(T) = C(T) + a|T| && {1} C(T) = \sum^{|T|}N_tH_t(T) && {2} p_k = \frac{N_{tk}}{N_t} && {3} H_t(T) = -\sum^Kp_k\log p_k && {4} \end{aligned}

说明：公式（1）中的第1项为模型对训练数据预测误差，代表模型的模拟度公式（1）代表模型的复杂度公式（1）中的a代表平衡模型拟合度和复杂度之间的关系

损失函数极小化 = 正则化的极大似然估计

Last updated 4 years ago

特征的选择

决定用哪个特征来划分特征空间。通过信息增益选取对训练数据具有分类能力的特征。

信息增益g(D,A)定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即

g(D, A) = H(D) - H(D|A)

信息熵增益准则的特征选择方法：对训练数据集（或子集）D，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。

决策树的修剪

生成的决策树容易发生过拟合，需要修剪。决策树的生成是寻找局部最优的决策树。决策树的修剪则是寻找全局最优的决策树。

决策树的剪枝往往通过极小化决策树整体的损失函数来实现定义： T：修剪前的决策树 |T|：T的叶子结点树 t：T的某个叶结点

N_t

：叶结点t的样本数

N_{tk}

：叶结点t的样本中标签为k的样本树

H_t(T)

：叶结点t上的经验熵 a：参数，

a \ge 0

损失函数：

\begin{aligned} C_a(T) = C(T) + a|T| && {1} C(T) = \sum^{|T|}N_tH_t(T) && {2} p_k = \frac{N_{tk}}{N_t} && {3} H_t(T) = -\sum^Kp_k\log p_k && {4} \end{aligned}

损失函数极小化 = 正则化的极大似然估计