1.决策树简介
决策树(decision tree)是机器学习中一种非参数的监督学习算法,可用于分类与回归。其中分类决策树是基于变量特征对离散变量目标值进行分类的,可用于二分类或多分类;回归决策树是基于变量特征对连续变量目标值进行分类的,可用于连续变量的回归拟合。
![](/i/l/?n=24&i=blog/2188094/202404/2188094-20240403152354916-135452540.png)
从上图看,可知树形结构主要由结点(node)和有向边(directed edge)组成,结点有两种类型:内部结点(internal node),表示一个特征或属性;叶结点(leaf node) ,表示一个类。
分类
![](/i/l/?n=24&i=blog/2188094/202404/2188094-20240403124211296-791603647.png)
回归
![](/i/l/?n=24&i=blog/2188094/202404/2188094-20240403124904714-2079246202.png)
2.特征选择
特征选择是决定用哪个特征来划分特征空间,即在根结点和中间结点根据特征进行分枝,一般选择对训练数据具有较大分类能力的特征,特征分类能力大小常用的衡量指标是信息增益或信息增益比。
熵
在信息论与概率统计中,熵(entropy) 是表示随机变量不确定性的度量,即混乱程度。设X是一个取有限个值的离散随机变量,其概率分布为:
\[P(X=x_i)=p_i \ \quad \ i=1,2,\cdots,n \]那么随机变量X的熵定义为:
\[H(X)=-\Sigma_{i=1}^np_ilogp_i \]式中对数以2或e为底,熵的单位称作比特(bit)或纳特(nat),由于熵只依赖于X的分布,而与X的取值无关,因此可将X的熵记为:
\[H(p)=-\Sigma_{i=1}^np_ilogp_i \]熵越大,随机变量的不确定性就越大。从定义可知:\(0 \leq H(p) \leq logn\)
条件熵
表示在已知随机变量X的条件下随机变量Y的不确定性,即在给定X条件下Y的条件概率分布的熵对X的数学期望:
\[H(Y|X)=\Sigma_{i=1}^np_iH(Y|X=x_i) \]式中,\(p_i=P(X=x_i), \quad i=1,2,\cdots,n\)
当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时,所对应的熵与条件熵分别称为经验熵(empirical entropy) 和经验条件熵(empirical conditional entroy)。
信息增益
信息增益(information gain)表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。
\[g(D,A)=H(D)-H(D|A) \]\(g(D,A)\)—特征A对训练数据集D的信息增益;
\(H(D)\)—集合D的经验熵;
\(H(D|A)\)—特征A给定条件下D的经验条件熵。
决策树学习应用信息增益准则选择特征,不同特征往往具有不同的信息增益,信息增益大的特征具有更强的分类能力。
信息增益准则特征选择方法:
对训练数据集D,计算其每个特征的信息增益,并比较它们的大小,选择信息增益最大的特征。
条件假设:
设训练数据集为D,|D|表示样本个数;
设训练数据集D,有K个类\(C_k,k=1,2,\cdots,K\),\(|C_k|\)为类\(C_k\)的样本个数,\(\Sigma_{k=1}^{K}|C_k|=|D|\).
根据特征A的n个不同的取值{\(a_1,a_2,\cdots,a_n\)}将D划分为n个子集\(D_1,D_2,\cdots,D_n\),\(|D_i|\)为\(D_i\)的样本个数,\(\Sigma_{i=1}^n|D_i|=|D|\).
记子集\(D_i\)中属于类\(C_k\)的样本的集合为\(D_{ik}\),即\(D_{ik}=D_i \bigcap C_k\),\(|D_{ik}|\)为\(D_{ik}\)的样本个数。
算法流程:
- 计算数据集D的经验熵H(D)
- 计算特征A对数据集D的经验条件熵H(D|A)
- 计算信息增益\[g(D,A)=H(D)-H(D|A) \]
信息增益比
信息增益值的大小是相对于训练数据集而言的,并没有绝对意义。在分类问题困难是,也就是说训练数据集的经验熵大的时候,信息增益值也会偏大;反之,信息增益值会偏小。利用信息增益比(information gain ratio)可以对这一问题进行校正。
信息增益比\(g_R(D,A)\):
\[g_R(D,A)=\frac{g_{(D,A)}}{H(D)}=\frac{H(D)-H(D|A)}{H(D)} \]\(g(D,A)\)—特征A对训练数据集D的信息增益;
\(H(D)\)—集合D的经验熵;
\(H(D|A)\)—特征A给定条件下D的经验条件熵。
3.算法的优缺点
优点:
- 相对于黑盒模型(神经网络等),决策树是白盒模型,易于理解,并具有较强的逻辑解释性,树结构可进行可视化查看。
- 需要更少的数据预处理,其它算法技术通常需要进行数据标准化、虚拟变量变换和空值删除,而树类型的算法直接支持缺失值处理。
- 决策树算法的预测消耗时间为O(log(\(n_{sample}\))),\(n_{sample}\)是样本个数。
- 可用处理数值型和分类型数据,但是scikit-learn目前不支持分类型变量。
- 可以处理多分类问题。
- 可用验证集对训练模型进行测试,使模型训练更加可靠。
- 即使假设在某种程度上违背数据生成的真实模型,也能很好执行。
缺点:
- 决策树模型容易生成过于复杂的树结构,导致泛化能力较差,容易过拟合。可通过一些特定的机制,如剪枝,限制叶结点的最小样本数或最大树结构深度,避免模型过拟合。
- 决策树模型不够稳定,训练数据的微小变动也可能会导致生成完全不同的树结构模型。这个问题可通过使用集成方法进行缓解。
- 决策树的预测不是平衡和连续的,但是可以利用阶梯式近似估计,因此不适合外推预测使用。
- 即使是简单的分类问题,从多个方面考虑,学习最优决策树也会是一个NP问题。因此,实际决策树学习算法一般是启发性的,例如贪心算法,利用结点的局部最优化进行分枝。这种算法不能保证全局最优化,但可通过集成方法进行缓解,在随机选择特征和样本构建树模型。
- 有些概念很难使用决策树模型进行学习,因为决策树不容易表达它们,例如异或、奇偶或多路复用问题。
- 如果某些类占主导地位,决策树学习器会创建有偏见的树结构。因此,建议在决策树拟合之前对数据集进行平衡处理,例如可以平衡各类样本比例或对样本进行权重重新分布处理,加大少数样本的权重。
$ $
参考资料
- https://scikit-learn.org/stable/modules/tree.html
- 李航 —— 《统计学习方法 第2版》