决策树

约 757 个字 预计阅读时间 3 分钟

定义

决策树(Decsion Tree)通过树状结构来表示决策过程，每个节点表示一个特征或者属性的测试，每个分支表示测试的结果，每个叶节点表示一个类别或值，可以认为是if-then规则的集合，也可以认为是定义在特征空间和类空间的条件概率分布。

策略

决策树学习本质上是从训练集归纳出一套分类规则，与训练集不矛盾的决策树可能有多个，也可能一个也没有。我们需要的是一个与训练集矛盾较小的决策树，同时具有很好的泛化能力。

决策树的损失函数通常是正则化的极大似然估计函数。但是事实上求解最优决策树是NPC，因为只能用近似算法求解。大体流程是特征选择，决策树生成和决策树剪枝。

求解

在构建决策树时要基于某种标准，没有分类能力的特征就不应该被选择，常见的标准有：

信息增益

在信息论与概率统计中，熵(entropy)表示随机变量不确定性的度量。设X是一个取值有限的离散随机变量，其概率分布律为\(P(X=x_i)=p_i \(，则其信息熵为\)H(X)=-\Sigma_{i=1}^np_i\log(p_i) \(，特别地，定义\)0\log(0)=0 \(，通常以2为对数或者以e为对数。对于二元随机变量\)X,Y\)，$H(X|Y) \(是\)Y \(给定条件下\)X $的条件熵。当概率是来自数据估计时就称作经验熵和经验条件熵。

信息增益定义是集合D的经验熵与特征A给定条件下经验熵之差，计算公式为$g(D,A)=H(D)-H(D|A) $

信息增益比

信息增益存在偏向于选择值较多的特征的问题。使用信息增益比可以对这一问题进行校正。信息增益比定义为$g_R(D,A)=\frac{g(D,A)}{H_A(D)} \(，其中\)H_A(D)=-\Sigma_{i=1}^n\frac{|D_i|}{D}\log_2\frac{|D_i|}{D} $

算法

ID3 算法

ID3 算法的核心是在决策树的各个节点上使用信息增益选择特征，递归地构建决策树。具体而言：从根节点开始，计算所有特征对当前节点的信息增益，选择信息增益最大的特征作为节点特征，由该特征的不同取值建立子节点，然后递归至没有特征或者信息增益很小为止。ID3算法只有树的生成，该算法容易过拟合。

C4.5的生成算法

把信息增益改成信息增益比

剪枝

单纯生成决策树非常容易过拟合，因为树太复杂了，所以我们要设法简化树（即剪枝

决策树的剪枝往往通过极小化决策树的损失函数来实现