首页 理论教育决策树:机器学习的经典方法

决策树:机器学习的经典方法

【摘要】:决策树是最经典的机器学习方法之一,它以树形结构将决策/分类过程展现出来,简单直观、解读性强,根据适用情况的不同,有时也被称为分类树或回归树。决策树呈现倒置的树形,即最上端为树的根,最下端为树的叶。机器学习中的决策树可以分为两个主要类型:分类树和回归树。[2000,3000]),则属于分类树范畴。虽然目前已有了在运行效率等方面进一步完善的算法C5.0,但由于C5.0多用于商业用途,C4.5仍是更为常用的决策树算法。

决策树是最经典的机器学习方法之一,它以树形结构将决策/分类过程展现出来,简单直观、解读性强,根据适用情况的不同,有时也被称为分类树或回归树。

简单来说,建立决策树的目的即是根据若干输入变量的值构造出一个相适应的模型,从而预测出目标/输出变量的值,并以树形结构呈现。

决策树呈现倒置的树形,即最上端为树的根,最下端为树的叶。从理论上概述决策树的构建过程,包括决策树的生成和生成树的剪枝两个步骤。

(1)决策树的生成

这一过程将初始的包含大量信息的数据集,按照一定的划分条件逐层分类至不可再分或不需再分,充分生成树。具体的,在每一次分类中,先找出各个可以作为分类变量的自变量的所有可能的划分条件,再对每一个自变量,比较在各个划分条件下所得的两个分支的差异大小,选出使得分支差异最大的划分条件作为该自变量的最优划分,再将各个自变量在最优划分下所得的两个分支的差异大小进行比较,选出差异最大者作为该节点的分类变量,并采用该变量的最优划分。

(2)生成树的剪枝

由于以上过程是没有停止条件的,所得到的生成树可能会非常大,对训练集很可能存在过拟合,即对训练数据有非常高的分类准确率,但是对于新数据的分类准确率较差。因此,为了保证生成树的推广能力,需要通过剪枝过程对复杂树的节点进行删减,控制树的复杂度,并由树的叶节点数来衡量复杂度。具体的,先找出固定叶节点数下拟合效果最优的树,即局部最优模型,再比较各个叶节点数下的局部最优模型,最终选择出全局最优模型。

机器学习中的决策树可以分为两个主要类型:分类树和回归树。分类树是针对目标变量为离散型的情况,即最终目标是预测各样本的所属类别,如根据天气预报来预测人们是否会打高尔夫;回归树则适用于目标变量为连续型,如预测出某人的月收入,可以建立回归树;当预测其月收入所属区间([1000,2000]?[2000,3000]),则属于分类树范畴。有两种使用最为普遍的决策树算法:CART(classification and regression trees)和C4.5(successor of ID3)。分类回归树CART是既可以建立分类树,也可构造回归树的算法,它是许多集成分类算法的基分类器,虽然各式分类算法不断涌现,但CART仍是使用最为广泛的分类技术。C4.5是ID3(iterative dichotomiser 3)的改进算法,两者都以熵(entropy)理论和信息增益(information gain)理论为基础,其算法的精髓所在,就是使用熵值或者信息增益值来确定使用哪个变量作为各节点的判定变量,而C4.5是为了解决ID3只能用于离散型变量,即仅可以构建分类树,且确定判定变量时偏向于选择取值较多的变量这两项主要缺陷而提出的。虽然目前已有了在运行效率等方面进一步完善的算法C5.0,但由于C5.0多用于商业用途,C4.5仍是更为常用的决策树算法。