1. 决策树的模型
1.1. 特征的选择
决定用哪个特征来划分特征空间。
通过信息增益选取对训练数据具有分类能力的特征。
信息增益g(D,A)定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差,即
信息熵增益准则的特征选择方法:对训练数据集(或子集)D,计算其每个特征的信息增益,并比较它们的大小,选择信息增益最大的特征。
1.2. 决策树的生成
生成最优决策树是NP完全问题。
因此使用启发式方法,生成次最优决策树。
即递归选择最优特征。
1.3. 决策树的修剪
生成的决策树容易发生过拟合,需要修剪。
决策树的生成是寻找局部最优的决策树。
决策树的修剪则是寻找全局最优的决策树。
决策树的剪枝往往通过极小化决策树整体的损失函数来实现
定义:
T:修剪前的决策树
|T|:T的叶子结点树
t:T的某个叶结点
:叶结点t的样本数
:叶结点t的样本中标签为k的样本树
:叶结点t上的经验熵
a:参数,
损失函数:
说明:
公式(1)中的第1项为模型对训练数据预测误差,代表模型的模拟度
公式(1)代表模型的复杂度
公式(1)中的a代表平衡模型拟合度和复杂度之间的关系
损失函数极小化 = 正则化的极大似然估计