决策树模型因为其特征预处理简单、易于集成学习、良好的拟合能力及解释性,是应用最广泛的机器学习模型之一。
不同于线性模型【数学描述:f(W*X +b)】是通过数据样本学习各个特征的合适权重,加权后做出决策。决策树会选择合适特征并先做特征划分后,再做出决策(也就是决策边界是非线性的,这提高了模型的非线性能力)。
决策树呈树形结构,更通俗来讲,树模型的数学描述就是“分段函数”。如下一个简单判别西瓜质量的决策树模型示例(注:以下西瓜示例,数据随机杜撰的,请忽略这么小的西瓜瓜~):
学习这样树模型的过程,简单来说就是从有监督的数据经验中学习一个较优的树模型的结构:包含了依次地选择特征、确定特征阈值做划分的内部节点及最终输出叶子节点的数值或类别结果。
从上述例子,我们可以将树模型的学习可以归到经典机器学习的4个要素:
树模型通过结合这几个要素,更快更好地划分特征空间,得出比较准确的决策。如下对这几个要素具体解析。
树模型的结构也就是个分段函数,包含了 选定特征做阈值划分(内部节点),以及划分后赋值的分数或类别决策(叶子节点)。
学习树模型的关键在于依据某些学习目标/指标(如划分准确度、信息熵、Gini不纯度、均方误差的增益量)去选择当前最优的特征并对样本的特征空间做非线性准确的划分,如上面西瓜的例子选择了一个特征做了一次划分(一刀切),通常情况下仅仅一刀切的划分准确度是不够的,可能还要在前面划分的样本基础上,继续多划分几次(也就多个切分条件的分段函数,如 if a>300 且特征b>10 且特征c<100, then 决策结果1;),以达到更高的准确度(纯度)。
但是,随着切分次数的变多,树的复杂度提高也就容易过拟合,相应每个切分出的小子特征空间的统计信息可能只是噪音。减少树生长过程的过拟合的风险,一个重要的方法就是树的剪枝,剪枝是一种正则化:由于决策树容易对数据产生过拟合,即生长出结构过于复杂的树模型,这时局部的特征空间会越分越“小”得到了不靠谱的“统计噪声”。通过剪枝算法可以降低复杂度,减少过拟合的风险。
决策树剪枝的目的是极小化经验损失+结构损失,基本策略有”预剪枝“和”后剪枝“两种策略:①预剪枝:是在决策树生成过程中,限制划分的最大深度、叶子节点数和最小样本数目等,以减少不必要的模型复杂度;②后剪枝:是先从训练集生成一棵完整的决策树,然后用用验证集自底向上地对非叶结点进行考察,若将该节点对应的子树替换为叶子结点(剪枝)能带来决策树的泛化性能提升(即目标函数损失更小,常用目标函数如:loss = 模型经验损失bias+ 模型结构损失α|T|, T为节点数目, α为系数),则将该子树替换为叶子结点。
实践中可以发现,浅层的树很容易欠拟合,而通过加深树的深度,虽然可以提高训练集的准确度,却很容易过拟合。
这个角度来看,单个树模型是比较弱的,且很容易根据特征选择、深度等超参数调节各树模型的多样性。正因为这些特点,决策树很适合通过结合多个的树模型做集成学习进一步提升模型效果。
集成学习是结合一些的基学习器共同学习,来改进其泛化能力和鲁棒性的方法,主流的有两种集成思想:
树模型天然具有非线性的特点,但与此有个缺陷,树模型却学习不好简单的线性回归!可以简单构想下传统决策树表达 y=|2x|这样规律,需要怎么做?如 if x=1,then 2; x =3, then 6 .....;
这样穷举显然不可能的。这里介绍下线性决策树,其实原理也很简单:把线性回归加到决策树的叶子节点里面(特征划分完后,再用线性模型拟合做决策)。一个简单线性树模型用分段函数来表示如:if x >0, then 2x;
代表模型有 linear decision tree, GBDT-PL等模型。
上文有提到,树模型的学习目标就是让各组的划分的准确率(纯度)都比较高,减小划分误差损失(此处忽略了结构损失T)。能达成划分前后损失差异效果类似的指标有很多:信息熵、基尼系数、MSE损失函数等等 都可以评估划分前后的纯度的增益 ,其实都是对分类误差的一种衡量,不同指标也对应这不同类型的决策树方法。
使用信息增益做特征划分的缺点是:信息增益偏向取值较多的特征。当特征的取值较多时,根据此特征划分更容易得到纯度更高的子集,因此划分之后的熵更低,由于划分前的熵是一定的,因此信息增益更大,因此信息增益比较偏向取值较多的特征。
信息增益比也就是信息增益除以信息熵,这样可以减少偏向取值较多信息熵较大的特征。
相应的,使用信息增益比缺点是:信息增益比偏向取值较少的特征。综上两种指标,可以在候选特征中找出信息增益高于平均水平的特征,然后在这些特征中再选择信息增益率最高的特征。
与信息熵一样(信息熵 如下式)
基尼系数表征的也是事件的不确定性(不纯度),也都可以看做是对分类误差率的衡量。
我们将熵定义式中的“-log(pi)”替换为 1-pi 也就是基尼系数,因为-log(pi)的泰勒近似展开第一项就是1-pi。基尼系数简单来看就是熵的“平替版”,在衡量分类误差的同时,也简化了大量计算。
(注:由于分类误差为分段函数=1-max(p, 1-p) ,不便于微分计算,实际中也比较少直接用)
当Cart应用于回归任务,平方误差损失也就是Cart回归树的生长指标。
确认学习目标,而依据这个指标去学习具体树结构的方法(优化算法),基本上有几种思路:
树模型也就是基于已知数据上, 通过以学习目标(降低各划分节点的误差率)为指导,启发式地选择特征去划分特征空间,以各划分的叶子节点做出较"优"的决策结果。所以,树模型有非常强的非线性能力,但是,由于是基于划分的局部样本做决策,过深(划分很多次)的树,局部样本的统计信息可能失准,容易过拟合。